1 // Implementation: Testprogram for 4-dimensional Segment Trees
2 // A four dimensional Segment Tree is defined in this class.
3 // Ti is the type of each dimension of the tree.
4
5 #include <iostream>
6 #include <CGAL/Segment_tree_k.h>
7 #include "include/Tree_Traits.h"
8 #include <vector>
9 #include <iterator>
10 #include <list>
11
12 typedef CGAL::Segment_tree_4<CGAL::Tree_traits_4> Segment_tree_4_type;
13
main()14 int main()
15 {
16
17 typedef CGAL::Tree_traits_4::Interval Interval;
18 typedef CGAL::Tree_traits_4::Key Key;
19 // definition of the two-dimensional segment tree
20 std::list<Interval> InputList, OutputList, N;
21
22 // insertion of the tree elements into the sequence container
23 InputList.push_back(Interval(Key(1, 4, 5, 2.5), Key(2,5,7, 4.7)));
24 InputList.push_back(Interval(Key(2,6.7,5, 3.5), Key(4,6.9, 8, 7.9)));
25 InputList.push_back(Interval(Key(2,4.55, 8, 5.5), Key(5, 7.88, 10, 9.9)));
26 InputList.push_back(Interval(Key(2, 4.66, 5, 4.6), Key(6, 8.99, 8, 8.4)));
27
28 // creation of the segment tree
29 std::list<Interval>::iterator first = InputList.begin();
30 std::list<Interval>::iterator last = InputList.end();
31
32 Segment_tree_4_type Segment_tree_4(first,last);
33
34 // perform a window query
35 Interval a(Key(3,4.88, 6, 5.4), Key(6, 8.999, 9, 8.6));
36 Segment_tree_4.window_query(a,std::back_inserter(OutputList));
37
38 // output of the querey elements on stdout
39 std::list<Interval>::iterator j = OutputList.begin();
40 std::cerr << "\n window_query (3,4.88, 6, 5.4),(6, 8.999, 9, 8.6)\n";
41 while(j!=OutputList.end())
42 {
43 std::cerr << (*j).first.key_1 << "," << (*j).first.key_2 << ", "
44 << (*j).first.key_3 << ", " << (*j).first.key_4 << "-"
45 << (*j).second.key_1 << "," << (*j).second.key_2 << ", "
46 << (*j).second.key_3 << " , " << (*j).second.key_4 << std::endl;
47 j++;
48 }
49 Interval b(Key(2,6.8,9, 5.9),Key(3,7,10, 6.7));
50 Segment_tree_4.enclosing_query(b,std::back_inserter(N));
51 j = N.begin();
52 std::cerr << "\n enclosing_query (2,6.8,9, 5.9), (3,7,10, 6.7)\n";
53 while(j!=N.end())
54 {
55 std::cerr << (*j).first.key_1 << "," << (*j).first.key_2 << ", "
56 << (*j).first.key_3 << ", " << (*j).first.key_4 << "-"
57 << (*j).second.key_1 << "," << (*j).second.key_2 << ", "
58 << (*j).second.key_3 << " , " << (*j).second.key_4 << std::endl;
59 j++;
60 }
61 if(Segment_tree_4.segment_tree_4->is_valid())
62 std::cerr << "Tree is valid\n";
63 else
64 std::cerr << "Tree is not valid\n";
65 return 0;
66 }
67