Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Definition

An object of the class Range_tree_k is a k-dimensional range tree that can store k-dimensional keys of type Key. The class allows to perform window queries on the keys. The class Range_tree_k is parameterized with a range tree traits class Traits that defines, among other things, the type of the Key.

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

#include <CGAL/Range_tree_k.h>

Types

Range_tree_k <Traits>::Traits
the type of the range tree traits class.

typedef Traits::Key
Key;

typedef Traits::Interval
Interval;

Creation

Range_tree_k <Traits> R;
Introduces an empty range tree R.


template < class ForwardIterator >
Range_tree_k <Traits> R ( ForwardIterator first, ForwardIterator last);
Introduces a range tree R and initializes it with the data in the range [first, last).
Precondition: value_type(first) == Traits::Key.

Operations

template < class ForwardIterator >
void
R.make_tree (
ForwardIterator first,
ForwardIterator last)
Introduces a range tree R and initializes it with the data in the range [first, last). This function can only be applied once on an empty range tree.
Precondition: value_type(first) == Traits::Key.

template < class OutputIterator >
OutputIterator R.window_query ( Interval window, OutputIterator out)
writes all data that are 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::Key.

Example

The following piece of code creates a number of 2-dimensional points that have a character associated with it, and constructs a 2-dimensional range tree for these data. Then a window query is performed. The result is written to standard output. 


#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Range_segment_tree_traits.h>
#include <CGAL/Range_tree_k.h>

typedef CGAL::Cartesian<double> Representation;
typedef CGAL::Range_tree_map_traits_2<Representation, char> Traits;
typedef CGAL::Range_tree_2<Traits> Range_tree_2_type;

void main()
{
  typedef Traits::Key Key;                
  typedef Traits::Interval Interval;    

  std::vector<Key> InputList, OutputList;
  InputList.push_back(Key(CGAL::Point_2<Representation>(8,5.1), 'a'));
  InputList.push_back(Key(CGAL::Point_2<Representation>(1,1.1), 'b'));
  InputList.push_back(Key(CGAL::Point_2<Representation>(3,2.1), 'c'));

  Range_tree_2_type Range_tree_2(InputList.begin(),InputList.end());
  Interval win(Interval(CGAL::Point_2<Rep>(4,8.1),CGAL::Point_2<Rep>(5,8.2)));
  cerr << "\n Window Query:\n ";
  Range_tree_2.window_query(win, std::back_inserter(OutputList));
  std::vector<Key>::iterator current=OutputList.begin();
  while(current!=OutputList.end())
  {
    cout << (*current).first.x() << "," << (*current).first.y()
         << ":" << (*current++).second << endl;
  }
}

Next: Class declaration of Segment_tree_k <Traits>
Navigation: Up, Table of Contents, Bibliography, Index, Title Page
The GALIA project. Jan 18, 2000.