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