Lightweight, header-only C++ library which implements a collection of multi-dimensional search structures.
mdsearch requires the following header-only Boost libraries:
- Boost.Unordered
- Boost.Functional/Hash
- Boost.Lexical_Cast
The minimum supported version of Boost is 1.41.
Each index structure is represented as a templated class, where the template parameter is the dimensionality of the data the structure is storing. These classes implement the following methods:
bool insert(point)-- insert unique point into the structure. Returns true if point insertion was successful and false if point is already being stored and has not been inserted.bool remove(point)-- delete point from structure. Returns true if the point was found and deleted successful and false if the point was not found.bool query(point)-- return true if point is being stored in structure and false otherwise.
The library comes with a program that generates random points and performs a
set of correctness and performance tests on each index structure. This program
is contained within the test_structures.cpp file, and shows examples of
how to construct and use the implemented index structures.
test_core.cpp contains a program that tests the correctness of the
library's core data types. This shows how to construct points and boundaries
compatible with the index structures.
###Storage Type Requirements
Generally, floating-point types are stored in multi-dimensional points.
However, the Point class and all the structures in mdsearch can store any
type. The Point, Boundary and structure classes will use the type specified in
their second template parameter, ELEM_TYPE.
To allow an arbitrary type ELEM_TYPE to be used with the structures, the
following free functions must be implemented:
bool operator==(const ELEM_TYPE&, const ELEM_TYPE&)bool operator!=(const ELEM_TYPE&, const ELEM_TYPE&)bool operator<=(const ELEM_TYPE&, const ELEM_TYPE&)bool operator>=(const ELEM_TYPE&, const ELEM_TYPE&)bool operator<(const ELEM_TYPE&, const ELEM_TYPE&)bool operator>(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE operator+(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE operator-(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE operator*(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE operator/(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE std::min(const ELEM_TYPE&, const ELEM_TYPE&)ELEM_TYPE std::max(const ELEM_TYPE&, const ELEM_TYPE&)
The following member functions must also be implemented:
ELEM_TYPE& ELEM_TYPE::operator=(const ELEM_TYPE&)ELEM_TYPE& ELEM_TYPE::operator+=(const ELEM_TYPE&)ELEM_TYPE& ELEM_TYPE::operator-=(const ELEM_TYPE&)ELEM_TYPE& ELEM_TYPE::operator*=(const ELEM_TYPE&)ELEM_TYPE& ELEM_TYPE::operator/=(const ELEM_TYPE&)