Definition

An object of the class Segment_tree_k is a $$k-dimensional segment tree that can store k-dimensional intervals of type Interval. The class allows to perform window queries, enclosing queries, and inverse range queries on the keys. The class Segment_tree_k is parameterized with a segment tree traits class Traits that defines, among other things, the type of the Interval. In order to perform an inverse range query, a range query of $$ width has to be performed. We prefered not to offer an extra function for this sort of query, since the inverse range query is a special case of the range query. Furthermore, offering an inverse range query in the segment tree class implies offering this function also in the range tree class and having an extra item in the traits class that accesses the inverse range query point.

CGAL provides traits class implementations that allow to use the segment tree with point classes from the CGAL kernel as keys. These classes are presented in Section . In Section  we give the requirements that segment tree traits classes must fulfill. This allows the advanced user to develop further segment tree traits classes.

#include <CGAL/Segment_tree_k.h>

Types

Segment_tree_k <Traits>::Traits
	the type of the segment tree traits class.

typedef Traits::Key
	Key;
typedef Traits::Interval
	Interval;

Creation

Segment_tree_k <Traits> S;
	Introduces an empty segment tree S.
template < class ForwardIterator >
Segment_tree_k <Traits> S ( ForwardIterator first, ForwardIterator last);
	Introduces a segment tree S and initializes it with the data in the range [first, last). Precondition: value_type(first) == Traits::Interval.

Operations

template < class ForwardIterator >
void	S.make_tree ( ForwardIterator first, ForwardIterator last)
		Introduces a segment tree S and initializes it with the data in the range [first, last). This function can only be applied once on an empty segment tree. Precondition: value_type(first) == Traits::Interval.
template < class OutputIterator >
OutputIterator	S.window_query ( Interval window, OutputIterator out)
		writes all intervals that have non empty intersection with interval window to the container where out points to, and returns an output iterator that points to the last location the function wrote to. Precondition: value_type(out) == Traits::Interval.
template < class OutputIterator >
OutputIterator	S.enclosing_query ( Interval window, OutputIterator out)
		writes all intervals that enclose in the interval window to the container where out points to, and returns an output iterator that points to the last location the function wrote to. Precondition: value_type(out) == Traits::Interval.

Example

The following piece of code creates some 2-dimensional intervals and constructs a 2-dimensional segment tree for these data. Then a window query and an enclosing query is performed. The result is written to standard output.

#include <CGAL/Homogeneous.h>
#include <CGAL/Point_2.h>
#include <CGAL/Segment_tree_k.h>
#include <CGAL/Range_segment_tree_traits.h>

typedef CGAL::Cartesian<double> Representation;
typedef CGAL::Range_segment_tree_traits_2<Representation> Traits;
typedef CGAL::Segment_tree_2<Traits > Segment_tree_2_type;

int main()
{
  typedef Traits::Key Key;              /* is a CGAL::Point_2<Rep> */
  typedef Traits::Interval Interval;    /* is a std::pair<Key,Key> */
  std::list<Interval> InputList, OutputList, N;

  InputList.push_back(Interval(Key(1,5), Key(2,7)));
  InputList.push_back(Interval(Key(2,7), Key(3,8)));
  InputList.push_back(Interval(Key(6,9), Key(9,13)));
  InputList.push_back(Interval(Key(1,3), Key(3,9)));
 
  Segment_tree_2_type Segment_tree_2(InputList.begin(), InputList.end());

  Interval a(Key(3,6), Key(7,12));
  Segment_tree_2.window_query(a,std::back_inserter(OutputList));

  /* output of the query elements on stdout */
  std::list<Interval>::iterator j = OutputList.begin();
  cout << "\n window_query \n";
  while(j!=OutputList.end())
  {
    cout << (*j).first.x() << "-" << (*j).second.x() << " " 
         << (*j).first.y() << "-" << (*j++).second.y() << endl; 
  }
  Interval b(Key(6,10),Key(7,11));
  Segment_tree_2.enclosing_query(b,std::back_inserter(OutputList));
  cout << "\n enclosing_query \n";
  while(j!=OutputList.end())
  {
    cout << (*j).first.x() << "-" << (*j).second.x() << " " 
         << (*j).first.y() << "-" << (*j++).second.y() << endl; 
  }
}