Go to the documentation of this file.
1 /*
3  *
4  * Created on: 21.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7
10
11 #include <vector>
12 #include <memory>
13 #include <cmath>
14 #include <omp.h>
15 #include <functional>
17
18 namespace NetworKit {
19
20 template <class T>
23 public:
31  QuadtreeCartesianEuclid(Point<double> lower = Point<double>({0.0, 0.0}), Point<double> upper = Point<double>({1.0, 1.0}), bool theoreticalSplit=false, count capacity=1000) {
32  assert(lower.getDimensions() == upper.getDimensions());
33  root = QuadNodeCartesianEuclid<T>(lower, upper, capacity, theoreticalSplit);
34  this->lower = lower;
35  this->upper = upper;
36  }
37
38  QuadtreeCartesianEuclid(const vector<Point<double> > &positions, const vector<T> &content, bool theoreticalSplit=false, count capacity=1000) {
39  const count n = positions.size();
40  assert(content.size() == n);
41  assert(n > 0);
42
43  this->dimension = positions[0].getDimensions();
44  vector<double> lowerValue(dimension);
45  vector<double> upperValue(dimension);
46  for (index d = 0; d < dimension; d++) {
47  lowerValue[d] = positions[0].at(d);
48  upperValue[d] = positions[0].at(d);
49  }
50
51  for (Point<double> pos : positions) {
52  assert(pos.getDimensions() == dimension);
53  for (index d = 0; d < dimension; d++) {
54  if (pos[d] < lowerValue[d]) lowerValue[d] = pos[d];
55  if (pos[d] > upperValue[d]) upperValue[d] = pos[d];
56  }
57  }
58
59  //the upper limit is open, so it needs to be above the points
60  for (index d = 0; d < dimension; d++) {
61  upperValue[d] = std::nextafter(upperValue[d], std::numeric_limits<double>::max());
62  }
63  this->lower = Point<double>(lowerValue);
64  this->upper = Point<double>(upperValue);
65
66  root = QuadNodeCartesianEuclid<T>(lower, upper, capacity, theoreticalSplit);
67  for (index i = 0; i < n; i++) {
68  assert(content[i] < n);
70  }
71  }
72
78  void addContent(T newcomer, Point<double> pos) {
80  }
81
87  bool removeContent(T toRemove, Point<double> pos) {
88  return root.removeContent(toRemove, pos);
89  }
90
96  vector<T> getElements() const {
97  return root.getElements();
98  }
99
100  void extractCoordinates(vector<Point<double> > &posContainer) const {
101  root.getCoordinates(posContainer);
102  }
103
104  void getElementsInEuclideanCircle(const Point<double> circleCenter, const double radius, vector<T> &circleDenizens) const {
105  root.getElementsInEuclideanCircle(circleCenter, radius, circleDenizens);
106  }
107
108  template<typename L>
109  count getElementsProbabilistically(Point<double> euQuery, L prob, vector<T> &circleDenizens) {
110  return root.getElementsProbabilistically(euQuery, prob, circleDenizens);
111  }
112
113  void recount() {
114  root.recount();
115  }
116
117  count size() const {
118  return root.size();
119  }
120
121  count height() const {
122  return root.height();
123  }
124
125  count countLeaves() const {
126  return root.countLeaves();
127  }
128
130  return root.indexSubtree(nextID);
131  }
132
134  return root.getCellID(pos);
135  }
136
137  void reindex() {
138  #pragma omp parallel
139  {
140  #pragma omp single nowait
141  {
142  root.reindex(0);
143  }
144  }
145  }
146
150  void trim() {
151  root.trim();
152  }
153
154 private:
156  Point<double> lower;
157  Point<double> upper;
158  count dimension;
159 };
160 }
161
162 #endif /* QUADTREE_H_ */
index indexSubtree(index nextID)
uint64_t index
Typedefs.
Definition: Globals.h:20
count getElementsProbabilistically(Point< double > euQuery, L prob, vector< T > &circleDenizens)
vector< T > getElements() const
Get all elements, regardless of position.
QuadtreeCartesianEuclid(Point< double > lower=Point< double >({0.0, 0.0}), Point< double > upper=Point< double >({1.0, 1.0}), bool theoreticalSplit=false, count capacity=1000)
void extractCoordinates(vector< Point< double > > &posContainer) const
bool removeContent(T toRemove, Point< double > pos)
count countLeaves() const
index getCellID(Point< double > pos) const
uint64_t count
Definition: Globals.h:21
void getElementsInEuclideanCircle(const Point< double > circleCenter, const double radius, vector< T > &circleDenizens) const
void trim()
trims the vectors used to hold the content in the leaf cells.
void reindex()