source: issm/trunk-jpl/src/c/classes/kriging/Covertree.h

Last change on this file was 26469, checked in by Mathieu Morlighem, 3 years ago

CHG: removing extraneous lines
File size: 4.2 KB
Line 
1
2#ifndef _COVERTREE_H
3#define _COVERTREE_H
4
5#include <map>
6class Observation;
7
8class Covertree{
9
10 /* Cover tree node. Consists of arbitrarily many points P, as long as they
11 * have distance 0 to each other. Keeps track of its children. */
12 class CoverTreeNode{
13 private:
14 //_childMap[i] is a vector of the node's children at level i
15 std::map<int,std::vector<CoverTreeNode*> > _childMap;
16 //_observations is all of the points with distance 0 which are not equal.
17 std::vector<Observation> _observations;
18 public:
19 CoverTreeNode(const Observation& o);
20 /**
21 * Returns the children of the node at level i. Note that this means
22 * the children exist in cover set i-1, not level i.
23 *
24 * Does not include the node itself, though technically every node
25 * has itself as a child in a cover tree.
26 */
27 void addChild(int level, CoverTreeNode* p);
28 void addObservation(const Observation& o);
29 double distance(const CoverTreeNode& p) const;
30 bool isSingle() const;
31 bool hasObservation(const Observation& o) const;
32 std::vector<CoverTreeNode*> getChildren(int level) const;
33 const Observation& getObservation() const;
34 const std::vector<Observation>& getObservations() { return _observations; }
35 void removeChild(int level, CoverTreeNode* p);
36 void removeObservation(const Observation& o);
37
38 /**
39 * Return every child of the node from any level. This is handy for
40 * the destructor.
41 */
42 std::vector<CoverTreeNode*> getAllChildren() const;
43 }; // CoverTreeNode class
44 private:
45 typedef std::pair<double, CoverTreeNode*> distNodePair;
46
47 CoverTreeNode *_root;
48 unsigned int _numNodes;
49 int _maxLevel; //base^_maxLevel should be the max distance
50 //between any 2 points
51 int _minLevel; //A level beneath which there are no more new nodes.
52
53 /* Finds the node in Q with the minimum distance to p. Returns a pair
54 * consisting of this node and the distance. */
55 distNodePair distance(const Observation& p,const std::vector<CoverTreeNode*>& Q);
56 /**
57 * Recursive implementation of the insert algorithm (see paper).
58 */
59 bool insert_rec(const Observation& p, const std::vector<distNodePair>& Qi,const int& level);
60
61 std::vector<CoverTreeNode*> kNearestNodes(const Observation& o, const unsigned int& k) const;
62 void remove_rec(const Observation& p, std::map<int,std::vector<distNodePair> >& coverSets, int level, bool& multi);
63
64 public:
65 double base;
66
67 /**
68 * Constructs a cover tree which begins with all points in points.
69 *
70 * maxDist should be the maximum distance that any two points
71 * can have between each other. IE p.distance(q) < maxDist for all
72 * p,q that you will ever try to insert. The cover tree may be invalid
73 * if an inaccurate maxDist is given.
74 */
75
76 Covertree(int maxDist,const std::vector<Observation>& points=std::vector<Observation>());
77 ~Covertree();
78
79 /**
80 * Insert newPoint into the cover tree. If newPoint is already present,
81 * (that is, newPoint==p for some p already in the tree), then the tree
82 * is unchanged. If p.distance(newPoint)==0.0 but newPoint!=p, then
83 * newPoint WILL be inserted and both points may be returned in k-nearest-
84 * neighbor searches.
85 */
86 void insert(const Observation& newObservation);
87
88 /**
89 * Just for testing/debugging. Returns true iff the cover tree satisfies the
90 * the covering tree invariants (every node in level i is greater than base^i
91 * distance from every other node, and every node in level i is less than
92 * or equal to base^i distance from its children). See the cover tree
93 * papers for details.
94 */
95 bool isValidTree() const;
96
97 /**
98 * Remove point p from the cover tree. If p is not present in the tree,
99 * it will remain unchanged. Otherwise, this will remove exactly one
100 * point q from the tree satisfying p==q.
101 */
102 void remove(const Observation& p);
103
104 /**
105 * Returns the k nearest points to p in order (the 0th element of the vector
106 * is closest to p, 1th is next, etc). It may return greater than k points
107 * if there is a tie for the kth place.
108 */
109 std::vector<Observation> kNearestNeighbors(const Observation& p, const unsigned int& k) const;
110
111 int get_numberofobs();
112
113 CoverTreeNode* getRoot() const;
114
115 /**
116 * Print the cover tree.
117 */
118 void print() const;
119};
120#endif //_COVERTREE_H
Note: See TracBrowser for help on using the repository browser.