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
Search(const KEY & i_localKey) const105 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 &
Entity() const166 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> *
NodeOf(id_t i_id) const174 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> *
Get_Parent() const183 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>
Node()193 Node<NODE_TRAITS>::Node()
194 : pEntity(0),
195 nDepth(0)
196 {
197 }
198
199 template <class NODE_TRAITS>
Node(entity_t & i_entity)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
Assign_Entity(entity_t & i_entity)209 Node<NODE_TRAITS>::Assign_Entity(entity_t & i_entity)
210 {
211 pEntity = &i_entity;
212 InitDepth();
213 }
214
215 template <class NODE_TRAITS>
~Node()216 Node<NODE_TRAITS>::~Node()
217 {
218 }
219
220 template <class NODE_TRAITS>
221 inline typename Node<NODE_TRAITS>::id_t
Id()222 Node<NODE_TRAITS>::Id()
223 {
224 return NODE_TRAITS::IdOf(Entity());
225 }
226
227 template <class NODE_TRAITS>
228 inline const String
Name() const229 Node<NODE_TRAITS>::Name() const
230 {
231 return NODE_TRAITS::LocalNameOf_(Entity());
232 }
233
234 template <class NODE_TRAITS>
235 inline int
Depth() const236 Node<NODE_TRAITS>::Depth() const
237 {
238 return nDepth;
239 }
240
241 template <class NODE_TRAITS>
242 inline const Node<NODE_TRAITS> *
Parent() const243 Node<NODE_TRAITS>::Parent() const
244 {
245 return Get_Parent();
246 }
247
248 template <class NODE_TRAITS>
249 template <class KEY>
250 void
SearchBelow(id_t & o_return,StringVector::const_iterator i_qualifiedSearchedName_begin,StringVector::const_iterator i_qualifiedSearchedName_end,const KEY & i_localKey) const251 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
SearchUp(id_t & o_return,StringVector::const_iterator i_qualifiedSearchedName_begin,StringVector::const_iterator i_qualifiedSearchedName_end,const KEY & i_localKey) const284 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 &
Entity()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> *
Parent()318 Node<NODE_TRAITS>::Parent()
319 {
320 return Get_Parent();
321 }
322
323 template <class NODE_TRAITS>
324 void
InitDepth()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