shore::d2tree< XCompare, YCompare, XYCompare > Class Template Reference

2d-tree: index-sort containers of 2-dimensional data for range queries More...

Public Member Functions
	d2tree (XCompare cx, YCompare cy, XYCompare cxy)
	Contruct an object that uses the given comparators.
	d2tree (XCompare cx, YCompare cy)
	Contruct an object that uses the given comparators. More...
template<typename Iterator >
void	build (Iterator beg, Iterator end)
	Build the index data structure. More...
template<typename Iterator , typename Key_t >
std::vector< Iterator >	search_including (Iterator beg, Iterator end, const Key_t &key) const
	Find all ranges that contain the given range. More...
template<typename Iterator , typename Key_t >
std::vector< Iterator >	search_included (Iterator beg, Iterator end, const Key_t &key) const
	Find all ranges that are contained by the given range. More...
template<typename Iterator , typename Key_t >
std::vector< Iterator >	search_overlapping (Iterator beg, Iterator end, const Key_t &key) const
	Find all ranges that overlap the given range (end is exlusive) More...
template<typename Iterator , typename Key_t >
std::vector< Iterator >	search_nearest_upstream (Iterator beg, Iterator end, const Key_t &key) const
	Find the elements with the smallest first dimension that is equal or larger than the second dimension of key. More...
template<typename Iterator , typename Key_t >
std::vector< Iterator >	search_nearest_downstream (Iterator beg, Iterator end, const Key_t &key) const
	Find the elements with the largest second dimension that is equal or smaller than the first dimension of key. More...

Detailed Description

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>
class shore::d2tree< XCompare, YCompare, XYCompare >

2d-tree: index-sort containers of 2-dimensional data for range queries

Constructor & Destructor Documentation

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

shore::d2tree< XCompare, YCompare, XYCompare >::d2tree ( XCompare  cx, YCompare  cy  )

inline

Contruct an object that uses the given comparators.

The third comparator is not required for all algorithms, so it may be omitted.

Member Function Documentation

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator >

void shore::d2tree< XCompare, YCompare, XYCompare >::build ( Iterator  beg, Iterator  end  )

inline

Build the index data structure.

This requires xcmp and ycmp.

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator , typename Key_t >

std::vector<Iterator> shore::d2tree< XCompare, YCompare, XYCompare >::search_included ( Iterator  beg, Iterator  end, const Key_t &  key  ) const

inline

Find all ranges that are contained by the given range.

( beg <= S ) && (end >= E) This requires xcmp, ycmp.

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator , typename Key_t >

std::vector<Iterator> shore::d2tree< XCompare, YCompare, XYCompare >::search_including ( Iterator  beg, Iterator  end, const Key_t &  key  ) const

inline

Find all ranges that contain the given range.

( beg >= S ) && (end <= E) This requires xcmp, ycmp.

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator , typename Key_t >

std::vector<Iterator> shore::d2tree< XCompare, YCompare, XYCompare >::search_nearest_downstream ( Iterator  beg, Iterator  end, const Key_t &  key  ) const

inline

Find the elements with the largest second dimension that is equal or smaller than the first dimension of key.

This requires xcmp, ycmp, xycmp.

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator , typename Key_t >

std::vector<Iterator> shore::d2tree< XCompare, YCompare, XYCompare >::search_nearest_upstream ( Iterator  beg, Iterator  end, const Key_t &  key  ) const

inline

Find the elements with the smallest first dimension that is equal or larger than the second dimension of key.

This requires xcmp, ycmp, xycmp.

template<typename XCompare, typename YCompare = XCompare, typename XYCompare = XCompare>

template<typename Iterator , typename Key_t >

std::vector<Iterator> shore::d2tree< XCompare, YCompare, XYCompare >::search_overlapping ( Iterator  beg, Iterator  end, const Key_t &  key  ) const

inline

Find all ranges that overlap the given range (end is exlusive)

( beg < E ) && (end > S) This requires xcmp, ycmp, xycmp.

---

The documentation for this class was generated from the following file:

• shore/algo/d2tree.hpp