Rectangle Set

API Reference

template <typename _Key, typename _Value>
class rectangle_set

Public Types

typedef _Key key_type
typedef _Value value_type
typedef inner_type::search_result_type search_result_type

Public Functions

rectangle_set()
rectangle_set(const rectangle_set &r)
~rectangle_set()
rectangle_set &operator=(const rectangle_set &r)
bool operator==(const rectangle_set &r) const

Equality between two instances of rectangle_set is evaluated based on the stored rectangle instances; their pointer values and geometries.

bool operator!=(const rectangle_set &r) const
bool insert(key_type x1, key_type y1, key_type x2, key_type y2, value_type data)

Insert a new rectangle (and data associated with it) into the set. Note that insertion of duplicate data instance is not allowed. A data is considered a duplicate if its pointer value is identical to one of the data instances already stored within. Also note that the end point of a rectangle is non-inclusive; a rectangle of (x1,y1) - (x2,y2) means that the rectangle spans x1 <= x < x2 and y1 <= y < y2.

Return
true if a rectangle successfully inserted, false otherwise.
Parameters
  • x1: lower x coordinate of the rectangle. Inclusive.
  • y1: lower y coordinate of the rectangle. Inclusive.
  • x2: upper x coordinate of the rectangle. Non-inclusive.
  • y2: upper y coordinate of the rectangle. Non-inclusive.
  • data: pointer to data instance associated with this rectangle. Note that the caller is responsible for managing the life cycle of the data instance.

bool search(key_type x, key_type y, search_result_type &result)

Search and collect all rectangles that contains a given point.

Return
true if the search is successful, false otherwise.
Parameters
  • x: x coordinate of a query point.
  • y: y coordinate of a query point.
  • result: array of pointers to rectangle instances.

search_result search(key_type x, key_type y)

Search and collect all rectangles containing a given point.

Return
object containing the result of the search, which can be accessed via iterator.
Parameters
  • x: x coordinate of a query point.
  • y: y coordinate of a query point.

void remove(value_type data)

Remove a rectangle instance pointed to by a given pointer.

Parameters
  • data: pointer that points to the rectangle instance you wish to remove from the set.

void clear()

Clear all rectangles stored in the set.

size_t size() const

Return the number of rectangles currently stored in the set.

Return
number of stored rectangles.

bool empty() const

Check whether or not the set is empty.

Return
true if the set is empty, false otherwise.

class search_result : public mdds::segment_tree<_Key, _Value>::search_result_base

Most of the implementation of search_result and its iterator is in segment_tree since the iteration logic is identical & depends on the segment_tree internals.

Public Types

template<>
typedef inner_type::search_result_base::res_chains_type res_chains_type
template<>
typedef inner_type::search_result_base::res_chains_ptr res_chains_ptr
template<>
typedef inner_type::data_chain_type data_chain_type

Public Functions

template<>
search_result()
template<>
search_result(const search_result &r)
template<>
search_result::iterator begin()
template<>
search_result::iterator end()
class iterator : public mdds::segment_tree<_Key, _Value>::iterator_base

Public Functions

template<>
iterator()

Friends

friend mdds::rectangle_set::rectangle_set< _Key, _Value >::search_result