yast2-core
TreeItem.h
Go to the documentation of this file.
1 /*---------------------------------------------------------------------\
2 | |
3 | __ __ ____ _____ ____ |
4 | \ \ / /_ _/ ___|_ _|___ \ |
5 | \ V / _` \___ \ | | __) | |
6 | | | (_| |___) || | / __/ |
7 | |_|\__,_|____/ |_| |_____| |
8 | |
9 | General Utilities |
10 | (C) SuSE GmbH |
11 \----------------------------------------------------------------------/
12 
13  File: TreeItem.h
14 
15  Purpose: Generic tree handling
16 
17  Author: Stefan Hundhammer <sh@suse.de>
18 
19 /-*/
20 
21 #ifndef TreeItem_h
22 #define TreeItem_h
23 
24 #include <string>
25 
26 
27 
28 
36 template<class PAYLOAD> class TreeItem
37 {
38 public:
39 
45  TreeItem<PAYLOAD> ( const PAYLOAD & val,
47  : _value( val )
48  , _parent( parent )
49  , _next( 0 )
50  , _firstChild( 0 )
51  {
52  if ( _parent )
53  _parent->addChild( this );
54  }
55 
56 
57 protected:
58 
65  TreeItem<PAYLOAD> ( PAYLOAD val,
66  bool autoAddChild,
68  : _value( val )
69  , _parent( parent )
70  , _next( 0 )
71  , _firstChild( 0 )
72  {
73  if ( _parent && autoAddChild )
74  _parent->addChild( this );
75  }
76 
77 
78 private:
85 
86 
87 public:
88 
93  virtual ~TreeItem<PAYLOAD> ()
94  {
95  TreeItem<PAYLOAD> * child = firstChild();
96 
97  while ( child )
98  {
99  TreeItem<PAYLOAD> * lastChild = child;
100  child = child->next();
101  delete lastChild;
102  }
103  }
104 
105 
109  const PAYLOAD & value() const { return _value; }
110 
118  void setValue( PAYLOAD newValue ) { _value = newValue; }
119 
123  TreeItem<PAYLOAD> * parent() const { return _parent; }
124 
128  TreeItem<PAYLOAD> * next() const { return _next; }
129 
134 
138  void setParent( TreeItem<PAYLOAD> * newParent ) { _parent = newParent; }
139 
143  void setNext( TreeItem<PAYLOAD> * newNext ) { _next = newNext; }
144 
148  void setFirstChild( TreeItem<PAYLOAD> * newFirstChild )
149  { _firstChild = newFirstChild; }
150 
151 
161  void addChild( TreeItem<PAYLOAD> * newChild )
162  {
163  if ( newChild )
164  {
165  newChild->setNext( firstChild() );
166  setFirstChild( newChild );
167  }
168  }
169 
170 
175  bool isChildOf( const TreeItem<PAYLOAD> * maybeParent ) const
176  {
177  const TreeItem<PAYLOAD> * child = this;
178 
179  while ( child )
180  {
181  if ( child == maybeParent )
182  return true;
183  child = child->parent();
184  }
185  return false;
186  }
187 
188 
189 protected:
190 
191  PAYLOAD _value;
195 };
196 
197 
198 
205 template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
206 {
207 public:
208 
214  SortedTreeItem<PAYLOAD> * parentItem = 0 )
215  : TreeItem<PAYLOAD> ( val, false, parentItem )
216  {
217  if ( parentItem )
218  {
219  // Hopefully we have a SortedTreeItem parent
220  SortedTreeItem<PAYLOAD> * sortParent =
221  dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
222 
223  if ( sortParent )
224  sortParent->insertChildSorted( this );
225  else // no SortedTreeItem parent - add unsorted
226  parentItem->addChild( this );
227  }
228  }
229 
230 
234  virtual ~SortedTreeItem<PAYLOAD> () {}
235 
236 
242  {
243  if ( ! newChild )
244  return;
245 
246  if ( ! firstChild() ||
247  newChild->value() < firstChild()->value() )
248  {
249  // Insert as first child
250 
251  newChild->setNext( firstChild() );
252  setFirstChild( newChild );
253  }
254  else
255  {
256  // Search correct place to insert
257 
258  TreeItem<PAYLOAD> * child = firstChild();
259 
260  while ( child->next() &&
261  child->next()->value() < newChild->value() )
262  {
263  child = child->next();
264  }
265 
266 
267  // Insert after 'child'
268 
269  newChild->setNext( child->next() );
270  child->setNext( newChild );
271  }
272  }
273 
274 
279  { return (SortedTreeItem<PAYLOAD> *) this->_parent; }
280 
285  { return (SortedTreeItem<PAYLOAD> *) this->_next; }
286 
291  { return (SortedTreeItem<PAYLOAD> *) this->_firstChild; }
292 
293 
294 private:
295 
302 };
303 
304 
305 
310 template<class ITEM, class PAYLOAD> inline
311 ITEM *
312 findDirectChild( ITEM * item, PAYLOAD searchVal )
313 {
314  TreeItem<PAYLOAD> * child = item->firstChild();
315 
316  while ( child )
317  {
318  if ( child->value() == searchVal )
319  return dynamic_cast<ITEM *> (child);
320 
321  child = child->next();
322  }
323 
324  return 0;
325 }
326 
327 
328 
329 #endif // TreeItem_h
TreeItem< PAYLOAD > * next() const
Definition: TreeItem.h:128
SortedTreeItem< PAYLOAD > * parent() const
Definition: TreeItem.h:278
SortedTreeItem< PAYLOAD > * firstChild() const
Definition: TreeItem.h:290
TreeItem< PAYLOAD > * firstChild() const
Definition: TreeItem.h:133
void setValue(PAYLOAD newValue)
Definition: TreeItem.h:118
SortedTreeItem< PAYLOAD > * next() const
Definition: TreeItem.h:284
TreeItem< PAYLOAD > * _firstChild
Definition: TreeItem.h:194
Template class for tree items that maintain sort order.
Definition: TreeItem.h:205
const PAYLOAD & value() const
Definition: TreeItem.h:109
void setParent(TreeItem< PAYLOAD > *newParent)
Definition: TreeItem.h:138
TreeItem< PAYLOAD > * _next
Definition: TreeItem.h:193
Template class for tree items that can handle tree children in a generic way - firstChild(), next() and parent(). Each item stores one value of type 'PAYLOAD'.
Definition: TreeItem.h:36
bool isChildOf(const TreeItem< PAYLOAD > *maybeParent) const
Definition: TreeItem.h:175
TreeItem< PAYLOAD > * parent() const
Definition: TreeItem.h:123
TreeItem< PAYLOAD > & operator=(const TreeItem< PAYLOAD > &)
Definition: TreeItem.h:84
TreeItem< PAYLOAD > * _parent
Definition: TreeItem.h:192
void insertChildSorted(SortedTreeItem< PAYLOAD > *newChild)
Definition: TreeItem.h:241
void addChild(TreeItem< PAYLOAD > *newChild)
Definition: TreeItem.h:161
PAYLOAD _value
Definition: TreeItem.h:191
void setNext(TreeItem< PAYLOAD > *newNext)
Definition: TreeItem.h:143
ITEM * findDirectChild(ITEM *item, PAYLOAD searchVal)
Definition: TreeItem.h:312
void setFirstChild(TreeItem< PAYLOAD > *newFirstChild)
Definition: TreeItem.h:148
SortedTreeItem< PAYLOAD > & operator=(const SortedTreeItem< PAYLOAD > &)
Definition: TreeItem.h:301

Generated on a sunny day for yast2-core by doxygen 1.8.6