Covertree.h

Go to the documentation of this file.

 
#ifndef _COVERTREE_H
#define _COVERTREE_H
 
#include <map>
class Observation;
 
class Covertree{
 
   /* Cover tree node. Consists of arbitrarily many points P, as long as they
    * have distance 0 to each other. Keeps track of its children.  */
   class CoverTreeNode{
      private:
         //_childMap[i] is a vector of the node's children at level i
         std::map<int,std::vector<CoverTreeNode*> > _childMap;
         //_observations is all of the points with distance 0 which are not equal.
         std::vector<Observation> _observations;
      public:
         CoverTreeNode(const Observation& o);
         void addChild(int level, CoverTreeNode* p);
         void addObservation(const Observation& o);
         double distance(const CoverTreeNode& p) const;
         bool   isSingle() const;
         bool   hasObservation(const Observation& o) const;
         std::vector<CoverTreeNode*> getChildren(int level) const;
         const Observation& getObservation() const;
         const std::vector<Observation>& getObservations() { return _observations; }
         void removeChild(int level, CoverTreeNode* p);
         void removeObservation(const Observation& o);
 
         std::vector<CoverTreeNode*> getAllChildren() const;
     }; // CoverTreeNode class
   private:
   typedef std::pair<double, CoverTreeNode*> distNodePair;
 
   CoverTreeNode *_root;
   unsigned int   _numNodes;
   int            _maxLevel;   //base^_maxLevel should be the max distance
   //between any 2 points
   int            _minLevel;   //A level beneath which there are no more new nodes.
 
   /* Finds the node in Q with the minimum distance to p. Returns a pair
    * consisting of this node and the distance.  */
   distNodePair distance(const Observation& p,const std::vector<CoverTreeNode*>& Q);
   bool insert_rec(const Observation& p, const std::vector<distNodePair>& Qi,const int& level);
 
   std::vector<CoverTreeNode*> kNearestNodes(const Observation& o, const unsigned int& k) const;
   void remove_rec(const Observation& p, std::map<int,std::vector<distNodePair> >& coverSets, int level, bool& multi);
 
   public:
   double base;
 
   Covertree(int maxDist,const std::vector<Observation>& points=std::vector<Observation>()); 
   ~Covertree();
 
   void insert(const Observation& newObservation);
 
   bool isValidTree() const;
 
 
   void remove(const Observation& p);
 
   std::vector<Observation> kNearestNeighbors(const Observation& p, const unsigned int& k) const;
 
   int get_numberofobs();
 
   CoverTreeNode* getRoot() const;
 
   void print() const;
};
#endif //_COVERTREE_H