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/Tree_base.h $ 7 // $Id: Tree_base.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_TREE_BASE_H 14 #define CGAL_TREE_BASE_H 15 16 #include <CGAL/license/SearchStructures.h> 17 18 19 #include <iterator> 20 #include <iostream> 21 #include <functional> 22 #include <list> 23 #include <vector> 24 #include <CGAL/assertions.h> 25 #include <CGAL/Tree_assertions.h> 26 27 #ifndef CGAL_TREE_BASE_nullptr 28 #define CGAL_TREE_BASE_nullptr 0 29 #endif 30 31 #define stlvector 32 33 namespace CGAL { 34 35 //link type definition of an ordinary vertex of the tree 36 template < typename Node > 37 struct Tree_node_base { 38 Node *parent_link; 39 Node *left_link; 40 Node *right_link; Tree_node_baseTree_node_base41 Tree_node_base() 42 : parent_link(0), left_link(0), right_link(0) 43 {} Tree_node_baseTree_node_base44 Tree_node_base(Node* ll, Node* rl) 45 : parent_link(0), left_link(ll), right_link(rl) 46 {} 47 }; 48 49 50 // ------------------------------------------------------------------- 51 // pure virtual abstract base class. 52 // Designed according to the Prototype Design Pattern 53 // A tree class has to be derived from this class. 54 55 template <class C_Data, class C_Window> 56 class Tree_base 57 { 58 59 protected: 60 Tree_base(Tree_base const &); // prevent access 61 void operator= (Tree_base const &); // prevent access 62 63 public: 64 typedef double vit; 65 typedef int lit; 66 typedef int lbit; 67 typedef double vbit; 68 typedef char oit; 69 // typedef std::vector<C_Data>::iterator vit; 70 //typedef std::list<C_Data>::iterator lit; 71 //typedef std::back_insert_iterator<lit> lbit; 72 //typedef std::back_insert_iterator<vit> vbit; 73 typedef Tree_base<C_Data, C_Window> Tree_base_type; Tree_base()74 Tree_base() {} ~Tree_base()75 virtual ~Tree_base() {} 76 77 // 'clone()' returns an object which can be used as argument to 'delete' 78 virtual Tree_base<C_Data, C_Window> *clone() const = 0; 79 //virtual Tree_base_type *clone() const = 0; 80 81 // 'make_tree()' returns an object which can be used as argument to 'delete' 82 virtual bool make_tree(const typename std::list<C_Data>::iterator& beg, 83 const typename std::list<C_Data>::iterator& end, 84 lit *dummy=0) =0; 85 #ifdef stlvector 86 virtual bool make_tree(const typename std::vector<C_Data>::iterator& beg, 87 const typename std::vector<C_Data>::iterator& end, 88 vit *dummy=0) =0; 89 #endif 90 #ifdef carray 91 virtual bool make_tree(const C_Data *beg, 92 const C_Data *end) =0; 93 #endif 94 virtual std::back_insert_iterator< std::list<C_Data> > 95 window_query(C_Window const &win, std::back_insert_iterator< 96 std::list<C_Data> > out,lbit *dummy=0 ) = 0; 97 virtual std::back_insert_iterator< std::vector<C_Data> > 98 window_query(C_Window const &win, std::back_insert_iterator< 99 std::vector<C_Data> > out,vbit *dummy=0) = 0; 100 #ifdef carray 101 virtual C_Data * window_query( C_Window const &win, 102 C_Data * out) = 0; 103 #endif 104 #ifdef ostreamiterator 105 typedef std::ostream_iterator< C_Data> oit; 106 virtual std::ostream_iterator< C_Data> window_query( C_Window const &win, 107 std::ostream_iterator< C_Data> out, 108 oit *dummy=0 ) = 0; 109 #endif 110 virtual std::back_insert_iterator< std::list< C_Data> > 111 enclosing_query( C_Window const &win, std::back_insert_iterator< 112 std::list< C_Data> > out, lbit *dummy=0 ) = 0; 113 virtual std::back_insert_iterator< std::vector< C_Data> > 114 enclosing_query( C_Window const &win, std::back_insert_iterator< 115 std::vector< C_Data> > out,vbit *dummy=0 ) = 0; 116 #ifdef carray 117 virtual C_Data * enclosing_query( C_Window const &win, 118 C_Data *out) = 0; 119 #endif 120 #ifdef ostreamiterator 121 virtual std::ostream_iterator< C_Data> enclosing_query( C_Window const &win, 122 std::ostream_iterator< C_Data> out, 123 oit *dummy=0) = 0; 124 #endif 125 virtual bool is_inside( C_Window const &win, 126 C_Data const& object) const =0; 127 virtual bool is_anchor()const =0; 128 virtual bool is_valid()const =0; 129 }; 130 131 132 // ------------------------------------------------------------------- 133 // Tree Anchor: this class is used as a recursion anchor. 134 // The derived tree classes can be nested. Use this class as the 135 // most inner class. This class is doing nothin exept stopping the recursion 136 137 template <class C_Data, class C_Window> 138 class Tree_anchor: public Tree_base< C_Data, C_Window> 139 { 140 public: 141 // Construct a factory with the given factory as sublayer Tree_anchor()142 Tree_anchor() {} ~Tree_anchor()143 virtual ~Tree_anchor(){} clone()144 Tree_base<C_Data, C_Window> *clone() const { return new Tree_anchor(); } 145 typedef Tree_base<C_Data, C_Window> tbt; 146 // Tree_base_type *clone() const { return new Tree_anchor(); } 147 148 bool make_tree(const typename std::list< C_Data>::iterator& /*beg*/, 149 const typename std::list< C_Data>::iterator& /*end*/, 150 typename tbt::lit * =0) 151 { 152 return true; 153 } 154 #ifdef stlvector 155 bool make_tree(const typename std::vector< C_Data>::iterator& /*beg*/, 156 const typename std::vector< C_Data>::iterator& /*end*/, 157 typename tbt::vit * =0) 158 { 159 return true; 160 } 161 #endif 162 #ifdef carray make_tree(const C_Data *,const C_Data *)163 bool make_tree(const C_Data * /*beg*/, 164 const C_Data * /*end*/) 165 { 166 return true; 167 } 168 #endif 169 std::back_insert_iterator< std::list< C_Data> > 170 window_query( 171 C_Window const &, 172 std::back_insert_iterator< std::list< C_Data> > out, 173 typename tbt::lbit * =0){ 174 return out; 175 } 176 177 std::back_insert_iterator< std::vector< C_Data> > 178 window_query( C_Window const &, 179 std::back_insert_iterator< std::vector< C_Data> > out, 180 typename tbt::vbit * =0){ 181 return out; 182 } 183 #ifdef carray window_query(C_Window const &,C_Data * out)184 C_Data * window_query( C_Window const &, 185 C_Data * out){ 186 return out; 187 } 188 #endif 189 #ifdef ostreamiterator 190 std::ostream_iterator< C_Data> window_query( C_Window const &, 191 std::ostream_iterator< C_Data> out, 192 typename tbt::oit *dummy=0){ 193 return out; 194 } 195 #endif 196 std::back_insert_iterator< std::list< C_Data> > enclosing_query( C_Window const &, 197 std::back_insert_iterator< std::list< C_Data> > out, 198 typename tbt::lbit * =0){ 199 return out; 200 } 201 std::back_insert_iterator< std::vector< C_Data> > enclosing_query( C_Window const &, 202 std::back_insert_iterator< std::vector< C_Data> > out, 203 typename tbt::vbit * =0){ 204 return out; 205 } 206 #ifdef carray enclosing_query(C_Window const &,C_Data * out)207 C_Data * enclosing_query( C_Window const &, 208 C_Data * out){ 209 return out; 210 } 211 #endif 212 #ifdef ostreamiterator 213 std::ostream_iterator< C_Data> enclosing_query( C_Window const &, 214 std::ostream_iterator< C_Data> out, 215 typename tbt::oit *dummy=0){ 216 return out; 217 } 218 #endif is_valid()219 bool is_valid()const{ return true;} 220 221 protected: 222 is_inside(C_Window const &,C_Data const &)223 bool is_inside( C_Window const &, 224 C_Data const&) const 225 { 226 return true; 227 } is_anchor()228 bool is_anchor()const {return true;} 229 }; 230 231 } //namespace CGAL 232 233 #endif 234