libyui-ncurses
Loading...
Searching...
No Matches
tnode.h
1/*
2 Copyright (C) 2000-2012 Novell, Inc
3 This library is free software; you can redistribute it and/or modify
4 it under the terms of the GNU Lesser General Public License as
5 published by the Free Software Foundation; either version 2.1 of the
6 License, or (at your option) version 3.0 of the License. This library
7 is distributed in the hope that it will be useful, but WITHOUT ANY
8 WARRANTY; without even the implied warranty of MERCHANTABILITY or
9 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
10 License for more details. You should have received a copy of the GNU
11 Lesser General Public License along with this library; if not, write
12 to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
13 Floor, Boston, MA 02110-1301 USA
14*/
15
16
17/*-/
18
19 File: tnode.h
20
21 Author: Michael Andres <ma@suse.de>
22
23/-*/
24
25#ifndef tnode_h
26#define tnode_h
27
28#include <iosfwd>
29
43template <class n_value> class tnode
44{
45
46 tnode & operator=( const tnode & );
47 tnode( const tnode & );
48
49protected:
50
51 typedef tnode<n_value> self;
52
53 mutable n_value val;
54
55private:
56
57 self * parent;
58 self * psibling; // prev sibling
59 self * nsibling; // next sibling
60 self * fchild; // first child
61 self * lchild; // last child
62
63 // Disconnect from old parent, connect to new parent *p*.
64 //
65 // If *s* is specified (not nilptr), insert this
66 // as its previous sibling (if *behind* is false)
67 // or as its next sibling (if *behind* is true).
68 //
69 // If *s* is omitted (nilptr), become the first (behind==false) or last
70 // (behind=true) child
71 //
72 // In case *s* is specified but is not in fact a child of *p* then it is
73 // treated as omitted.
74 //
75 // @param p new parent
76 // @param s reference sibling
77 // @param behind true: insert after *s*; false: insert before *s*
78 // @return true on success;
79 // false on failure (*p* is myself or a descendant of mine)
80 bool DoReparentTo( self & p, self * s, bool behind )
81 {
82
83 if ( &p == this || p.IsDescendantOf( this ) )
84 return false;
85
86 Disconnect();
87
88 parent = &p;
89
90 PreReparent();
91
92 if ( !s || s->parent != parent ) // using default sibling
93 s = behind ? parent->lchild : parent->fchild;
94
95 if ( !s )
96 {
97 // no sibling, so we'll be the only child
98 parent->fchild = parent->lchild = this;
99 }
100 else
101 {
102 if ( behind )
103 {
104 psibling = s;
105 nsibling = s->nsibling;
106 s->nsibling = this;
107
108 if ( nsibling )
109 nsibling->psibling = this;
110 else
111 parent->lchild = this;
112 }
113 else
114 {
115 psibling = s->psibling;
116 nsibling = s;
117 s->psibling = this;
118
119 if ( psibling )
120 psibling->nsibling = this;
121 else
122 parent->fchild = this;
123 }
124 }
125
126 PostReparent();
127
128 return true;
129 }
130
131protected:
132
133 virtual void PreDisconnect() {}
134
135 virtual void PostDisconnect() {}
136
137 virtual void PreReparent() {}
138
139 virtual void PostReparent() {}
140
141public:
142
145 tnode( n_value v, self * p = 0, bool behind = true )
146 : val( v )
147 , parent( 0 )
148 , psibling( 0 )
149 , nsibling( 0 )
150 , fchild( 0 )
151 , lchild( 0 )
152 {
153 if ( p )
154 DoReparentTo( *p, 0, behind );
155 }
156
159 tnode( n_value v, self & p, bool behind = true )
160 : val( v )
161 , parent( 0 )
162 , psibling( 0 )
163 , nsibling( 0 )
164 , fchild( 0 )
165 , lchild( 0 )
166 {
167 DoReparentTo( p, 0, behind );
168 }
169
173 tnode( n_value v, self & p, self & s, bool behind = true )
174 : val( v )
175 , parent( 0 )
176 , psibling( 0 )
177 , nsibling( 0 )
178 , fchild( 0 )
179 , lchild( 0 )
180 {
181 DoReparentTo( p, &s, behind );
182 }
183
184
185 virtual ~tnode()
186 {
187 while ( fchild )
188 fchild->Disconnect();
189
190 Disconnect();
191 }
192
195 {
196 if ( !parent )
197 return;
198
199 PreDisconnect();
200
201 if ( psibling )
202 psibling->nsibling = nsibling;
203 else
204 parent->fchild = nsibling;
205
206 if ( nsibling )
207 nsibling->psibling = psibling;
208 else
209 parent->lchild = psibling;
210
211 parent = psibling = nsibling = 0;
212
213 PostDisconnect();
214 }
215
222 bool ReparentTo( self & p, bool behind = true )
223 {
224 return DoReparentTo( p, 0, behind );
225 }
226
239 bool ReparentTo( self & p, self & s, bool behind = true )
240 {
241 return DoReparentTo( p, &s, behind );
242 }
243
244
245 n_value & Value() const { return val; }
246
248 n_value & operator()() const { return Value(); }
249
250 self * Parent() { return parent; }
251
252 const self * Parent() const { return parent; }
253
255 self * Psibling() { return psibling; }
256
258 const self * Psibling() const { return psibling; }
259
261 self * Nsibling() { return nsibling; }
262
264 const self * Nsibling() const { return nsibling; }
265
267 self * Fchild() { return fchild; }
268
270 const self * Fchild() const { return fchild; }
271
273 self * Lchild() { return lchild; }
274
276 const self * Lchild() const { return lchild; }
277
278 bool HasParent() const { return parent; }
279
280 bool HasSiblings() const { return psibling || nsibling; }
281
282 bool HasChildren() const { return fchild; }
283
284 bool IsParentOf( const self & c ) const { return c.parent == this; }
285
286 bool IsSiblingOf( const self & s ) const { return parent && s.parent == parent; }
287
288 bool IsChildOf( const self & p ) const { return parent == &p; }
289
291 unsigned Depth() const
292 {
293 self * l = const_cast<self *>( this );
294 unsigned level = 0;
295
296 while ( l->parent )
297 {
298 l = l->parent;
299 ++level;
300 }
301
302 return level;
303 }
304
305 // tree walk
306
307 bool IsDescendantOf( const self & n ) const
308 {
309 for ( const self * l = parent; l; l = l->parent )
310 {
311 if ( l == &n )
312 return true;
313 }
314
315 return false;
316 }
317
318 bool IsDescendantOf( const self * n ) const
319 {
320 return( n && IsDescendantOf( *n ) );
321 }
322
325 {
326 self * l = this;
327
328 while ( l->parent )
329 l = l->parent;
330
331 return *l;
332 }
333
337 self * Next( bool restart = false )
338 {
339 if ( fchild ) // down first
340 return fchild;
341
342 self * l = this; // then next
343
344 while ( !l->nsibling )
345 {
346 if ( l->parent )
347 l = l->parent;
348 else
349 return restart ? l : 0; // at Top()
350 }
351
352 return l->nsibling;
353 }
354
355 self * Prev( bool restart = false )
356 {
357 if ( !psibling && parent )
358 return parent;
359
360 if ( !psibling && !restart )
361 return 0;
362
363 // have psibling or at Top() and restart:
364 self * l = psibling ? psibling : this;
365
366 while ( l->lchild )
367 l = l->lchild;
368
369 return l;
370 }
371
373 self * Next( self *& c, bool restart = false )
374 {
375 return c = Next( restart );
376 }
377
379 self * Prev( self *& c, bool restart = false )
380 {
381 return c = Prev( restart );
382 }
383
384 // const versions
385
386 const self & Top() const
387 {
388 return const_cast<self *>( this )->Top();
389 }
390
391 const self * Next( bool restart = false ) const
392 {
393 return const_cast<self *>( this )->Next( restart );
394 }
395
396 const self * Prev( bool restart = false ) const
397 {
398 return const_cast<self *>( this )->Prev( restart );
399 }
400
401 const self * Next( const self *& c, bool restart = false ) const
402 {
403 return c = const_cast<self *>( this )->Next( restart );
404 }
405
406 const self * Prev( const self *& c, bool restart = false ) const
407 {
408 return c = const_cast<self *>( this )->Prev( restart );
409 }
410
411};
412
413#endif // tnode_h
Definition tnode.h:44
n_value & operator()() const
Alias for Value.
Definition tnode.h:248
self * Lchild()
Last child.
Definition tnode.h:273
self * Nsibling()
Next sibling.
Definition tnode.h:261
self * Prev(self *&c, bool restart=false)
Return Prev and assign it to c.
Definition tnode.h:379
void Disconnect()
Disconnect from the parent and siblings, but keep children.
Definition tnode.h:194
const self * Psibling() const
Previous sibling.
Definition tnode.h:258
tnode(n_value v, self &p, bool behind=true)
Definition tnode.h:159
bool ReparentTo(self &p, self &s, bool behind=true)
Definition tnode.h:239
const self * Nsibling() const
Next sibling.
Definition tnode.h:264
self * Psibling()
Previous sibling.
Definition tnode.h:255
tnode(n_value v, self *p=0, bool behind=true)
Definition tnode.h:145
self * Next(self *&c, bool restart=false)
Return Next and assign it to c.
Definition tnode.h:373
self * Next(bool restart=false)
Definition tnode.h:337
unsigned Depth() const
Depth: zero if no parent, otherwise 1 + parent's depth.
Definition tnode.h:291
const self * Fchild() const
First child.
Definition tnode.h:270
const self * Lchild() const
Last child.
Definition tnode.h:276
bool ReparentTo(self &p, bool behind=true)
Definition tnode.h:222
self * Fchild()
First child.
Definition tnode.h:267
tnode(n_value v, self &p, self &s, bool behind=true)
Definition tnode.h:173
self & Top()
Root of the tree.
Definition tnode.h:324