libyui-ncurses  2.44.1
 All Classes Functions Variables
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 
30 
31 template <class n_value> class tnode
32 {
33 
34  tnode & operator=( const tnode & );
35  tnode( const tnode & );
36 
37 protected:
38 
39  typedef tnode<n_value> self;
40 
41  mutable n_value val;
42 
43 private:
44 
45  self * parent;
46  self * psibling;
47  self * nsibling;
48  self * fchild;
49  self * lchild;
50 
51 
52  bool DoReparentTo( self & p, self * s, const bool behind )
53  {
54 
55  if ( &p == this || p.IsDescendantOf( this ) )
56  return false;
57 
58  Disconnect();
59 
60  parent = &p;
61 
62  PreReparent();
63 
64  if ( !s || s->parent != parent ) // using default sibling
65  s = behind ? parent->lchild : parent->fchild;
66 
67  if ( !s )
68  {
69  // no sibling, so we'll be the only child
70  parent->fchild = parent->lchild = this;
71  }
72  else
73  {
74  if ( behind )
75  {
76  psibling = s;
77  nsibling = s->nsibling;
78  s->nsibling = this;
79 
80  if ( nsibling )
81  nsibling->psibling = this;
82  else
83  parent->lchild = this;
84  }
85  else
86  {
87  psibling = s->psibling;
88  nsibling = s;
89  s->psibling = this;
90 
91  if ( psibling )
92  psibling->nsibling = this;
93  else
94  parent->fchild = this;
95  }
96  }
97 
98  PostReparent();
99 
100  return true;
101  }
102 
103 protected:
104 
105  virtual void PreDisconnect() {}
106 
107  virtual void PostDisconnect() {}
108 
109  virtual void PreReparent() {}
110 
111  virtual void PostReparent() {}
112 
113 public:
114 
115  tnode( n_value v, self * p = 0, const bool behind = true )
116  : val( v )
117  , parent( 0 )
118  , psibling( 0 )
119  , nsibling( 0 )
120  , fchild( 0 )
121  , lchild( 0 )
122  {
123  if ( p )
124  DoReparentTo( *p, 0, behind );
125  }
126 
127  tnode( n_value v, self & p, const bool behind = true )
128  : val( v )
129  , parent( 0 )
130  , psibling( 0 )
131  , nsibling( 0 )
132  , fchild( 0 )
133  , lchild( 0 )
134  {
135  DoReparentTo( p, 0, behind );
136  }
137 
138  tnode( n_value v, self & p, self & s, const bool behind = true )
139  : val( v )
140  , parent( 0 )
141  , psibling( 0 )
142  , nsibling( 0 )
143  , fchild( 0 )
144  , lchild( 0 )
145  {
146  DoReparentTo( p, &s, behind );
147  }
148 
149 
150  virtual ~tnode()
151  {
152  while ( fchild )
153  fchild->Disconnect();
154 
155  Disconnect();
156  }
157 
158 
159  void Disconnect()
160  {
161  if ( !parent )
162  return;
163 
164  PreDisconnect();
165 
166  if ( psibling )
167  psibling->nsibling = nsibling;
168  else
169  parent->fchild = nsibling;
170 
171  if ( nsibling )
172  nsibling->psibling = psibling;
173  else
174  parent->lchild = psibling;
175 
176  parent = psibling = nsibling = 0;
177 
178  PostDisconnect();
179  }
180 
181  bool ReparentTo( self & p, const bool behind = true )
182  {
183  return DoReparentTo( p, 0, behind );
184  }
185 
186  bool ReparentTo( self & p, self & s, const bool behind = true )
187  {
188  return DoReparentTo( p, &s, behind );
189  }
190 
191 
192  n_value & Value() const { return val; }
193 
194  n_value & operator()() const { return Value(); }
195 
196  self * Parent() { return parent; }
197 
198  const self * Parent() const { return parent; }
199 
200  self * Psibling() { return psibling; }
201 
202  const self * Psibling() const { return psibling; }
203 
204  self * Nsibling() { return nsibling; }
205 
206  const self * Nsibling() const { return nsibling; }
207 
208  self * Fchild() { return fchild; }
209 
210  const self * Fchild() const { return fchild; }
211 
212  self * Lchild() { return lchild; }
213 
214  const self * Lchild() const { return lchild; }
215 
216  bool HasParent() const { return parent; }
217 
218  bool HasSiblings() const { return psibling || nsibling; }
219 
220  bool HasChildren() const { return fchild; }
221 
222  bool IsParentOf( const self & c ) const { return c.parent == this; }
223 
224  bool IsSiblingOf( const self & s ) const { return parent && s.parent == parent; }
225 
226  bool IsChildOf( const self & p ) const { return parent == &p; }
227 
228  unsigned Depth() const
229  {
230  self * l = const_cast<self *>( this );
231  unsigned level = 0;
232 
233  while ( l->parent )
234  {
235  l = l->parent;
236  ++level;
237  }
238 
239  return level;
240  }
241 
242  // tree walk
243 
244  bool IsDescendantOf( const self & n ) const
245  {
246  for ( const self * l = parent; l; l = l->parent )
247  {
248  if ( l == &n )
249  return true;
250  }
251 
252  return false;
253  }
254 
255  bool IsDescendantOf( const self * n ) const
256  {
257  return( n && IsDescendantOf( *n ) );
258  }
259 
260  self & Top()
261  {
262  self * l = this;
263 
264  while ( l->parent )
265  l = l->parent;
266 
267  return *l;
268  }
269 
270  self * Next( const bool restart = false )
271  {
272  if ( fchild ) // down first
273  return fchild;
274 
275  self * l = this; // then next
276 
277  while ( !l->nsibling )
278  {
279  if ( l->parent )
280  l = l->parent;
281  else
282  return restart ? l : 0; // at Top()
283  }
284 
285  return l->nsibling;
286  }
287 
288  self * Prev( const bool restart = false )
289  {
290  if ( !psibling && parent )
291  return parent;
292 
293  if ( !psibling && !restart )
294  return 0;
295 
296  // have psibling or at Top() and restart:
297  self * l = psibling ? psibling : this;
298 
299  while ( l->lchild )
300  l = l->lchild;
301 
302  return l;
303  }
304 
305  self * Next( self *& c, const bool restart = false )
306  {
307  return c = Next( restart );
308  }
309 
310  self * Prev( self *& c, const bool restart = false )
311  {
312  return c = Prev( restart );
313  }
314 
315  // const versions
316 
317  const self & Top() const
318  {
319  return const_cast<self *>( this )->Top();
320  }
321 
322  const self * Next( const bool restart = false ) const
323  {
324  return const_cast<self *>( this )->Next( restart );
325  }
326 
327  const self * Prev( const bool restart = false ) const
328  {
329  return const_cast<self *>( this )->Prev( restart );
330  }
331 
332  const self * Next( const self *& c, const bool restart = false ) const
333  {
334  return c = const_cast<self *>( this )->Next( restart );
335  }
336 
337  const self * Prev( const self *& c, const bool restart = false ) const
338  {
339  return c = const_cast<self *>( this )->Prev( restart );
340  }
341 
342 };
343 
344 
345 #endif // tnode_h
Definition: tnode.h:31