1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 #ifndef ARY_SYMTREE_NODE_HXX 25 #define ARY_SYMTREE_NODE_HXX 26 27 28 // USED SERVICES 29 // BASE CLASSES 30 // OTHER 31 32 33 34 namespace ary 35 { 36 namespace symtree 37 { 38 39 40 41 /** Represents a node in a tree of symbols like a namespace tree or a 42 directory tree. 43 44 @tpl NODE_TRAITS 45 Needs to define the types: 46 entity_base_type: The type of the entities in that storage, 47 e.g. ->ary::cpp::CodeEntity. 48 id_type: The type of the ids of those entities, 49 e.g. ->ary::cpp::Ce_id. 50 51 Needs to define the functions: 52 1. static entity_base_type & 53 EntityOf_( 54 id_type i_id ); 55 2. static symtree::Node<LeNode_Traits> * 56 NodeOf_( 57 const entity_base_type & 58 i_entity ); 59 3. static const String & 60 LocalNameOf_( 61 const entity_base_type & 62 i_entity ); 63 4. static entity_base_type * 64 ParentOf_( 65 const entity_base_type & 66 i_entity ); 67 5. template <class KEY> 68 static id_t Search_( 69 const entity_base_type & 70 i_entity, 71 const KEY & i_localKey ); 72 */ 73 template <class NODE_TRAITS> 74 class Node 75 { 76 public: 77 typedef Node<NODE_TRAITS> node_self; 78 typedef typename NODE_TRAITS::entity_base_type entity_t; 79 typedef typename NODE_TRAITS::id_type id_t; 80 81 82 // LIFECYCLE 83 /// @attention Always needs to be followed by ->Assign_Entity()! 84 Node(); 85 explicit Node( 86 entity_t & i_entity ); 87 void Assign_Entity( 88 entity_t & i_entity ); 89 ~Node(); 90 // INQUIRY 91 id_t Id(); 92 const String Name() const; 93 int Depth() const; 94 const entity_t & Entity() const; 95 const node_self * Parent() const; 96 97 /** Gets a child with a specific name and of a specific type. 98 99 There may be more childs with the same name. 100 101 @return id_t(0), if no matching child is found. 102 */ 103 template <class KEY> 104 typename NODE_TRAITS::id_type 105 Search( 106 const KEY & i_localKey ) const 107 { 108 // Inline here to workaround SUNW8 compiler bug, works in SUNW12. 109 return NODE_TRAITS::Search_(Entity(), i_localKey); 110 } 111 112 113 /** Gets a child with a specific qualified name below this node. 114 115 The child may not exists. 116 */ 117 template <class KEY> 118 void SearchBelow( 119 id_t & o_return, // Workaround SUNW8 compiler bug 120 StringVector::const_iterator 121 i_qualifiedSearchedName_begin, 122 StringVector::const_iterator 123 i_qualifiedSearchedName_end, 124 const KEY & i_localKey ) const; 125 126 /** Gets a child with a specific qualified name, either below this node 127 or below any of the parent nodes. 128 129 The child may not exists. 130 */ 131 template <class KEY> 132 void SearchUp( 133 id_t & o_return, // Workaround SUNW8 compiler bug 134 StringVector::const_iterator 135 i_qualifiedSearchedName_begin, 136 StringVector::const_iterator 137 i_qualifiedSearchedName_end, 138 const KEY & i_localKey ) const; 139 // ACCESS 140 entity_t & Entity(); 141 node_self * Parent(); 142 143 private: 144 // Forbid copying: 145 Node(const node_self&); 146 node_self& operator=(const node_self&); 147 148 // Locals 149 void InitDepth(); 150 node_self * Get_Parent() const; 151 node_self * NodeOf( 152 id_t i_id ) const; 153 154 // DATA 155 entity_t * pEntity; 156 int nDepth; 157 }; 158 159 160 161 162 // IMPLEMENTATION 163 164 template <class NODE_TRAITS> 165 inline const typename Node<NODE_TRAITS>::entity_t & 166 Node<NODE_TRAITS>::Entity() const 167 { 168 csv_assert(pEntity != 0); 169 return *pEntity; 170 } 171 172 template <class NODE_TRAITS> 173 inline Node<NODE_TRAITS> * 174 Node<NODE_TRAITS>::NodeOf(id_t i_id) const 175 { 176 if (i_id.IsValid()) 177 return NODE_TRAITS::NodeOf_(NODE_TRAITS::EntityOf_(i_id)); 178 return 0; 179 } 180 181 template <class NODE_TRAITS> 182 inline Node<NODE_TRAITS> * 183 Node<NODE_TRAITS>::Get_Parent() const 184 { 185 entity_t * 186 parent = NODE_TRAITS::ParentOf_(Entity()); 187 if (parent != 0) 188 return NODE_TRAITS::NodeOf_(*parent); 189 return 0; 190 } 191 192 template <class NODE_TRAITS> 193 Node<NODE_TRAITS>::Node() 194 : pEntity(0), 195 nDepth(0) 196 { 197 } 198 199 template <class NODE_TRAITS> 200 Node<NODE_TRAITS>::Node(entity_t & i_entity) 201 : pEntity(&i_entity), 202 nDepth(0) 203 { 204 InitDepth(); 205 } 206 207 template <class NODE_TRAITS> 208 void 209 Node<NODE_TRAITS>::Assign_Entity(entity_t & i_entity) 210 { 211 pEntity = &i_entity; 212 InitDepth(); 213 } 214 215 template <class NODE_TRAITS> 216 Node<NODE_TRAITS>::~Node() 217 { 218 } 219 220 template <class NODE_TRAITS> 221 inline typename Node<NODE_TRAITS>::id_t 222 Node<NODE_TRAITS>::Id() 223 { 224 return NODE_TRAITS::IdOf(Entity()); 225 } 226 227 template <class NODE_TRAITS> 228 inline const String 229 Node<NODE_TRAITS>::Name() const 230 { 231 return NODE_TRAITS::LocalNameOf_(Entity()); 232 } 233 234 template <class NODE_TRAITS> 235 inline int 236 Node<NODE_TRAITS>::Depth() const 237 { 238 return nDepth; 239 } 240 241 template <class NODE_TRAITS> 242 inline const Node<NODE_TRAITS> * 243 Node<NODE_TRAITS>::Parent() const 244 { 245 return Get_Parent(); 246 } 247 248 template <class NODE_TRAITS> 249 template <class KEY> 250 void 251 Node<NODE_TRAITS>::SearchBelow( 252 id_t & o_return, // Workaround SUNW8 compiler bug 253 StringVector::const_iterator i_qualifiedSearchedName_begin, 254 StringVector::const_iterator i_qualifiedSearchedName_end, 255 const KEY & i_localKey ) const 256 { 257 if (i_qualifiedSearchedName_begin != i_qualifiedSearchedName_end) 258 { 259 id_t 260 next = Search(*i_qualifiedSearchedName_begin); 261 if (next.IsValid()) 262 { 263 const node_self * 264 subnode = NodeOf(next); 265 if (subnode != 0) 266 { 267 subnode->SearchBelow( o_return, 268 i_qualifiedSearchedName_begin+1, 269 i_qualifiedSearchedName_end , 270 i_localKey ); 271 return; 272 } 273 } 274 o_return = id_t(0); 275 return; 276 } 277 278 o_return = Search(i_localKey); 279 } 280 281 template <class NODE_TRAITS> 282 template <class KEY> 283 void 284 Node<NODE_TRAITS>::SearchUp( 285 id_t & o_return, // Workaround SUNW8 compiler bug 286 StringVector::const_iterator i_qualifiedSearchedName_begin, 287 StringVector::const_iterator i_qualifiedSearchedName_end, 288 const KEY & i_localKey ) const 289 { 290 SearchBelow( o_return, 291 i_qualifiedSearchedName_begin, 292 i_qualifiedSearchedName_end, 293 i_localKey ); 294 if (o_return.IsValid()) 295 return; 296 297 node_self * 298 parent = Get_Parent(); 299 if (parent != 0) 300 { 301 parent->SearchUp( o_return, 302 i_qualifiedSearchedName_begin, 303 i_qualifiedSearchedName_end, 304 i_localKey ); 305 } 306 } 307 308 template <class NODE_TRAITS> 309 typename Node<NODE_TRAITS>::entity_t & 310 Node<NODE_TRAITS>::Entity() 311 { 312 csv_assert(pEntity != 0); 313 return *pEntity; 314 } 315 316 template <class NODE_TRAITS> 317 inline Node<NODE_TRAITS> * 318 Node<NODE_TRAITS>::Parent() 319 { 320 return Get_Parent(); 321 } 322 323 template <class NODE_TRAITS> 324 void 325 Node<NODE_TRAITS>::InitDepth() 326 { 327 Node<NODE_TRAITS> * 328 pp = Get_Parent(); 329 if (pp != 0) 330 nDepth = pp->Depth() + 1; 331 else 332 nDepth = 0; 333 } 334 335 336 337 338 } // namespace symtree 339 } // namespace ary 340 #endif 341