You can clone with
Cannot retrieve contributors at this time
This is a C++ implementation of the cover tree datastructure. Implements thecover tree algorithms for insert, removal, and k-nearest-neighbor search.To build simply type make in the terminal from the project directory. Do./test to run the tests. Look in test.cc for example code of how to use thecover tree.Relevant links:https://secure.wikimedia.org/wikipedia/en/wiki/Cover_tree - Wikipedia's pageon cover trees.http://hunch.net/~jl/projects/cover_tree/cover_tree.html - John Langford's (oneof the inventors of cover trees) page on cover trees with links to papers.To use the Cover Tree, you must implement your own Point class. CoverTreePointis provided for testing and as an example. Your Point class must implement thefollowing functions:double YourPoint::distance(const YourPoint& p);bool YourPoint::operator==(const YourPoint& p);and optionally (for debugging/printing only):void YourPoint::print();The distance function must be a Metric, meaning (from Wikipedia):1: d(x, y) = 0 if and only if x = y2: d(x, y) = d(y, x) (symmetry)3: d(x, z) =< d(x, y) + d(y, z) (subadditivity / triangle inequality).See https://secure.wikimedia.org/wikipedia/en/wiki/Metric_%28mathematics%29for details.Actually, 1 does not exactly need to hold for this implementation; you canprovide, for example, names for your points which are unrelated to distancebut important for equality. You can insert multiple points with distance 0 toeach other and the tree will keep track of them, but you cannot insert multiplepoints that are equal to each other; attempting to insert a point thatalready exists in the tree will not alter the tree at all.If you do not want to allow multiple nodes with distance 0, then just makeyour equality operator always return true when distance is 0.TODO:-The papers describe batch insert and batch-nearest-neighbors algorithms whichmay be worth implementing.-Try using a third "upper bound" argument for distance functions, beyond whichthe distance does not need to be calculated, to improve efficiency in practice.