1 // Copyright (c) 1997 ETH Zurich (Switzerland). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/SearchStructures/include/CGAL/Range_tree_k.h $ 7 // $Id: Range_tree_k.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Gabriele Neyer 12 13 #ifndef CGAL_RANGE_TREE_K_H 14 #define CGAL_RANGE_TREE_K_H 15 16 #include <CGAL/license/SearchStructures.h> 17 18 19 // Predefined k-dimensional Range Trees (k=1..4) 20 // The trees can either be templated with d arbitrary types 21 // (e.g., Range_tree_3) 22 // or with an unary type for each dimension 23 // (e.g., Range_tree_uni_4). 24 // The container class and sequence container class as well as the 25 // interfaces are defined in these classes. 26 27 #include <iostream> 28 #include <iterator> 29 #include <CGAL/Tree_base.h> 30 #include <CGAL/Tree_traits.h> 31 #include <CGAL/Range_tree_d.h> 32 33 //------------------------------------------------------------------- 34 // A one dimensional Range Tree is defined in this class. 35 // Ti is the type of each dimension of the tree. 36 37 namespace CGAL { 38 39 40 template <class C_Traits_1> 41 class Range_tree_1 42 { 43 44 public: 45 typedef C_Traits_1 Traits; 46 typedef typename C_Traits_1::Key Key; 47 typedef typename C_Traits_1::Interval Interval; 48 typedef typename C_Traits_1::Key_1 Key_1; 49 typedef typename C_Traits_1::key_1 key_1; 50 typedef typename C_Traits_1::low_1 low_1; 51 typedef typename C_Traits_1::high_1 high_1; 52 typedef typename C_Traits_1::compare_1 compare_1; 53 54 55 typedef tree_point_traits<Key, Interval, Key_1, 56 key_1, low_1, high_1, compare_1> I1; 57 58 typedef Tree_anchor<Key, Interval> Tree_anchor_type; 59 Tree_anchor_type *anchor; 60 61 typedef Range_tree_d<Key, Interval, I1> Range_tree_1_type; 62 Range_tree_1_type * range_tree_1; 63 64 Range_tree_1()65 Range_tree_1() 66 { 67 anchor = new Tree_anchor_type; 68 range_tree_1 = new Range_tree_1_type(*anchor); 69 } 70 71 template <class T> Range_tree_1(const T & first,const T & last)72 Range_tree_1(const T& first, 73 const T& last) 74 : anchor(new Tree_anchor_type), range_tree_1(new Range_tree_1_type(*anchor)) 75 { 76 range_tree_1->make_tree(first,last); 77 } 78 79 template <class T> make_tree(const T & first,const T & last)80 bool make_tree(const T& first, 81 const T& last) 82 { 83 delete range_tree_1; 84 delete anchor; 85 anchor = new Tree_anchor_type; 86 range_tree_1 = new Range_tree_1_type(*anchor); 87 return range_tree_1->make_tree(first,last); 88 } 89 90 template <class T> window_query(Interval const & win,const T & result)91 T window_query(Interval const &win, 92 const T& result) 93 { 94 return range_tree_1->window_query(win, result); 95 } 96 ~Range_tree_1()97 ~Range_tree_1() 98 { 99 if (range_tree_1!=0) 100 delete range_tree_1; 101 if (anchor!=0) 102 delete anchor; 103 } 104 105 }; 106 107 108 //------------------------------------------------------------------- 109 // A two dimensional Range Tree is defined in this class. 110 // Ti is the type of each dimension of the tree. 111 112 template <class C_Traits_2> 113 class Range_tree_2 114 { 115 116 public: 117 typedef C_Traits_2 Traits; 118 typedef typename C_Traits_2::Key Key; 119 typedef typename C_Traits_2::Interval Interval; 120 typedef typename C_Traits_2::Key_2 Key_2; 121 typedef typename C_Traits_2::Key_1 Key_1; 122 typedef typename C_Traits_2::key_1 key_1; 123 typedef typename C_Traits_2::key_2 key_2; 124 typedef typename C_Traits_2::low_1 low_1; 125 typedef typename C_Traits_2::high_1 high_1; 126 typedef typename C_Traits_2::low_2 low_2; 127 typedef typename C_Traits_2::high_2 high_2; 128 typedef typename C_Traits_2::compare_1 compare_1; 129 typedef typename C_Traits_2::compare_2 compare_2; 130 131 132 typedef tree_point_traits<Key, Interval, 133 Key_1, key_1, low_1, high_1, compare_1> I1; 134 135 typedef tree_point_traits<Key, Interval, 136 Key_2, key_2, low_2, high_2, compare_2> I2; 137 138 139 typedef Tree_anchor<Key, Interval> Tree_anchor_type; 140 Tree_anchor_type *anchor; 141 142 typedef Range_tree_d<Key, Interval, I2> Range_tree_1_type; 143 Range_tree_1_type * range_tree_1; 144 145 typedef Range_tree_d<Key, Interval, I1> Range_tree_2_type; 146 Range_tree_2_type *range_tree_2; 147 148 Range_tree_2()149 Range_tree_2() 150 : anchor(new Tree_anchor_type), 151 range_tree_1(new Range_tree_1_type(*anchor)), 152 range_tree_2(new Range_tree_2_type(*range_tree_1)) 153 {} 154 155 template <class T> Range_tree_2(const T & first,const T & last)156 Range_tree_2(const T& first, 157 const T& last) 158 : anchor(new Tree_anchor_type), 159 range_tree_1(new Range_tree_1_type(*anchor)), 160 range_tree_2(new Range_tree_2_type(*range_tree_1)) 161 { 162 range_tree_2->make_tree(first,last); 163 } 164 165 template <class T> make_tree(const T & first,const T & last)166 bool make_tree(const T& first, 167 const T& last) 168 { 169 delete range_tree_2; 170 delete range_tree_1; 171 delete anchor; 172 anchor = new Tree_anchor_type; 173 range_tree_1 = new Range_tree_1_type(*anchor); 174 range_tree_2 = new Range_tree_2_type(*range_tree_1); 175 return range_tree_2->make_tree(first,last); 176 } 177 178 template <class T> window_query(Interval const & win,const T & result)179 T window_query(Interval const &win, 180 const T& result) 181 { 182 return range_tree_2->window_query(win, result); 183 } 184 ~Range_tree_2()185 ~Range_tree_2() 186 { 187 if (range_tree_2!=0) 188 delete range_tree_2; 189 if (range_tree_1!=0) 190 delete range_tree_1; 191 if (anchor!=0) 192 delete anchor; 193 } 194 }; 195 196 //------------------------------------------------------------------- 197 // A three dimensional Range Tree is defined in this class. 198 // Ti is the type of each dimension of the tree. 199 template <class C_Traits_3> 200 class Range_tree_3 201 { 202 public: 203 typedef C_Traits_3 Traits; 204 typedef typename C_Traits_3::Key Key; 205 typedef typename C_Traits_3::Interval Interval; 206 typedef typename C_Traits_3::Key_1 Key_1; 207 typedef typename C_Traits_3::Key_2 Key_2; 208 typedef typename C_Traits_3::Key_3 Key_3; 209 typedef typename C_Traits_3::key_1 key_1; 210 typedef typename C_Traits_3::key_2 key_2; 211 typedef typename C_Traits_3::key_3 key_3; 212 typedef typename C_Traits_3::low_1 low_1; 213 typedef typename C_Traits_3::high_1 high_1; 214 typedef typename C_Traits_3::low_2 low_2; 215 typedef typename C_Traits_3::high_2 high_2; 216 typedef typename C_Traits_3::low_3 low_3; 217 typedef typename C_Traits_3::high_3 high_3; 218 typedef typename C_Traits_3::compare_1 compare_1; 219 typedef typename C_Traits_3::compare_2 compare_2; 220 typedef typename C_Traits_3::compare_3 compare_3; 221 222 typedef tree_point_traits<Key, Interval, Key_1, 223 key_1, low_1, high_1, compare_1> I1; 224 225 typedef tree_point_traits<Key, Interval, Key_2, 226 key_2, low_2, high_2, compare_2> I2; 227 228 typedef tree_point_traits<Key, Interval, Key_3, 229 key_3, low_3, high_3, compare_3> I3; 230 231 typedef Tree_anchor<Key, Interval> Tree_anchor_type; 232 Tree_anchor_type *anchor; 233 234 typedef Range_tree_d<Key, Interval, I3> Range_tree_1_type; 235 Range_tree_1_type * range_tree_1; 236 237 typedef Range_tree_d<Key, Interval, I2> Range_tree_2_type; 238 Range_tree_2_type * range_tree_2; 239 240 typedef Range_tree_d<Key, Interval, I1> Range_tree_3_type; 241 Range_tree_3_type *range_tree_3; 242 Range_tree_3()243 Range_tree_3() 244 : anchor(new Tree_anchor_type), 245 range_tree_1(new Range_tree_1_type(*anchor)), 246 range_tree_2(new Range_tree_2_type(*range_tree_1)), 247 range_tree_3(new Range_tree_3_type(*range_tree_2)) 248 {} 249 250 template <class T> Range_tree_3(const T & first,const T & last)251 Range_tree_3(const T& first, 252 const T& last) 253 : anchor(new Tree_anchor_type), 254 range_tree_1(new Range_tree_1_type(*anchor)), 255 range_tree_2(new Range_tree_2_type(*range_tree_1)), 256 range_tree_3(new Range_tree_3_type(*range_tree_2)) 257 { 258 range_tree_3->make_tree(first,last); 259 } 260 261 template <class T> make_tree(const T & first,const T & last)262 bool make_tree(const T& first, 263 const T& last) 264 { 265 delete range_tree_3; 266 delete range_tree_2; 267 delete range_tree_1; 268 delete anchor; 269 anchor = new Tree_anchor_type; 270 range_tree_1 = new Range_tree_1_type(*anchor); 271 range_tree_2 = new Range_tree_2_type(*range_tree_1); 272 range_tree_3 = new Range_tree_3_type(*range_tree_2); 273 return range_tree_3->make_tree(first,last); 274 } 275 276 template <class T> window_query(Interval const & win,const T & result)277 T window_query(Interval const &win, 278 const T& result) 279 { 280 return range_tree_3->window_query(win, result); 281 } 282 ~Range_tree_3()283 ~Range_tree_3() 284 { 285 if (range_tree_3!=0) 286 delete range_tree_3; 287 if (range_tree_2!=0) 288 delete range_tree_2; 289 if (range_tree_1!=0) 290 delete range_tree_1; 291 if (anchor!=0) 292 delete anchor; 293 } 294 }; 295 296 297 //------------------------------------------------------------------- 298 // A three dimensional Range Tree is defined in this class. 299 // Ti is the type of each dimension of the tree. 300 301 template <class C_Traits_4> 302 class Range_tree_4 303 { 304 public: 305 typedef C_Traits_4 Traits; 306 typedef typename C_Traits_4::Key Key; 307 typedef typename C_Traits_4::Interval Interval; 308 typedef typename C_Traits_4::Key_1 Key_1; 309 typedef typename C_Traits_4::Key_2 Key_2; 310 typedef typename C_Traits_4::Key_3 Key_3; 311 typedef typename C_Traits_4::Key_4 Key_4; 312 typedef typename C_Traits_4::key_1 key_1; 313 typedef typename C_Traits_4::key_2 key_2; 314 typedef typename C_Traits_4::key_4 key_4; 315 typedef typename C_Traits_4::key_3 key_3; 316 typedef typename C_Traits_4::low_1 low_1; 317 typedef typename C_Traits_4::high_1 high_1; 318 typedef typename C_Traits_4::low_2 low_2; 319 typedef typename C_Traits_4::high_2 high_2; 320 typedef typename C_Traits_4::low_3 low_3; 321 typedef typename C_Traits_4::high_3 high_3; 322 typedef typename C_Traits_4::low_4 low_4; 323 typedef typename C_Traits_4::high_4 high_4; 324 typedef typename C_Traits_4::compare_1 compare_1; 325 typedef typename C_Traits_4::compare_2 compare_2; 326 typedef typename C_Traits_4::compare_3 compare_3; 327 typedef typename C_Traits_4::compare_4 compare_4; 328 329 typedef tree_point_traits<Key, Interval, Key_1, 330 key_1, low_1, high_1, compare_1> I1; 331 332 typedef tree_point_traits<Key, Interval, Key_2, 333 key_2, low_2, high_2, compare_2> I2; 334 335 typedef tree_point_traits<Key, Interval, Key_3, 336 key_3, low_3, high_3, compare_3> I3; 337 338 typedef tree_point_traits<Key, Interval, Key_4, 339 key_4, low_4, high_4, compare_4> I4; 340 341 typedef Tree_anchor<Key, Interval> Tree_anchor_type; 342 Tree_anchor_type *anchor; 343 344 typedef Range_tree_d<Key, Interval, I4> Range_tree_1_type; 345 Range_tree_1_type * range_tree_1; 346 347 typedef Range_tree_d<Key, Interval, I3> Range_tree_2_type; 348 Range_tree_2_type * range_tree_2; 349 350 typedef Range_tree_d<Key, Interval, I2> Range_tree_3_type; 351 Range_tree_3_type *range_tree_3; 352 353 typedef Range_tree_d<Key, Interval, I1> Range_tree_4_type; 354 Range_tree_4_type *range_tree_4; 355 Range_tree_4()356 Range_tree_4() 357 : anchor(new Tree_anchor_type), 358 range_tree_1(new Range_tree_1_type(*anchor)), 359 range_tree_2(new Range_tree_2_type(*range_tree_1)), 360 range_tree_3(new Range_tree_3_type(*range_tree_2)), 361 range_tree_4(new Range_tree_4_type(*range_tree_3)) 362 {} 363 364 template <class T> Range_tree_4(const T & first,const T & last)365 Range_tree_4(const T& first, 366 const T& last) 367 : anchor(new Tree_anchor_type), 368 range_tree_1(new Range_tree_1_type(*anchor)), 369 range_tree_2(new Range_tree_2_type(*range_tree_1)), 370 range_tree_3(new Range_tree_3_type(*range_tree_2)), 371 range_tree_4(new Range_tree_4_type(*range_tree_3)) 372 { 373 range_tree_4->make_tree(first,last); 374 } 375 376 template <class T> make_tree(const T & first,const T & last)377 bool make_tree(const T& first, 378 const T& last) 379 { 380 delete range_tree_4; 381 delete range_tree_3; 382 delete range_tree_2; 383 delete range_tree_1; 384 delete anchor; 385 anchor = new Tree_anchor_type; 386 range_tree_1 = new Range_tree_1_type(*anchor); 387 range_tree_2 = new Range_tree_2_type(*range_tree_1); 388 range_tree_3 = new Range_tree_3_type(*range_tree_2); 389 range_tree_4 = new Range_tree_4_type(*range_tree_3); 390 return range_tree_4->make_tree(first,last); 391 } 392 393 template <class T> window_query(Interval const & win,const T & result)394 T window_query(Interval const &win, 395 const T& result) 396 { 397 return range_tree_4->window_query(win, result); 398 } 399 ~Range_tree_4()400 ~Range_tree_4() 401 { 402 if (range_tree_4!=0) 403 delete range_tree_4; 404 if (range_tree_3!=0) 405 delete range_tree_3; 406 if (range_tree_2!=0) 407 delete range_tree_2; 408 if (range_tree_1!=0) 409 delete range_tree_1; 410 if (anchor!=0) 411 delete anchor; 412 } 413 }; 414 415 } //namespace CGAL 416 417 #endif 418