libyui  3.4.2
TreeItem.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: TreeItem.h
20 
21  Author: Stefan Hundhammer <sh@suse.de>
22 
23 /-*/
24 
25 #ifndef TreeItem_h
26 #define TreeItem_h
27 
28 #include <string>
29 
30 
31 
32 
33 /**
34  * Template class for tree items that can handle tree children in a
35  * generic way - firstChild(), next() and parent(). Each item stores one value
36  * of type 'PAYLOAD'.
37  *
38  * Class 'PAYLOAD' needs to provide operator=().
39  **/
40 template<class PAYLOAD> class TreeItem
41 {
42 public:
43 
44  /**
45  * Constructor. Creates a new tree item with value "val" and inserts it
46  * ( without maintaining any meaningful sort order! ) into the children list
47  * of "parent".
48  **/
49  TreeItem<PAYLOAD> ( const PAYLOAD & val,
51  : _value( val )
52  , _parent( parent )
53  , _next(0)
54  , _firstChild(0)
55  {
56  if ( _parent )
57  _parent->addChild( this );
58  }
59 
60 
61 protected:
62 
63  /**
64  * Constructor to be called for derived classes: Decide whether or not to
65  * automatically insert this item into the parent's children list. Useful
66  * for derived classes that want to maintain a specific sort order among
67  * children.
68  **/
69  TreeItem<PAYLOAD> ( PAYLOAD val,
70  bool autoAddChild,
71  TreeItem<PAYLOAD> * parent = 0 )
72  : _value( val )
73  , _parent( parent )
74  , _next(0)
75  , _firstChild(0)
76  {
77  if ( _parent && autoAddChild )
78  _parent->addChild( this );
79  }
80 
81 
82 private:
83  /**
84  * Private ( i.e. disabled ) copy constructor and operator=()
85  * - neither makes any sense with this class.
86  **/
88  TreeItem<PAYLOAD> & operator= ( const TreeItem<PAYLOAD> & ) {}
89 
90 
91 public:
92 
93  /**
94  * Destructor. Takes care of children - they will be deleted along with
95  * this item.
96  **/
97  virtual ~TreeItem<PAYLOAD> ()
98  {
99  TreeItem<PAYLOAD> * child = firstChild();
100 
101  while ( child )
102  {
103  TreeItem<PAYLOAD> * lastChild = child;
104  child = child->next();
105  delete lastChild;
106  }
107  }
108 
109 
110  /**
111  * Returns this item's value, the "payload".
112  **/
113  const PAYLOAD & value() const { return _value; }
114 
115  /**
116  * Set this item's value, the "payload".
117  *
118  * If the sort order among children of one level is important, overwrite
119  * this method and change the sort order according to the new value.
120  * The template class itself never calls this.
121  **/
122  void setValue( PAYLOAD newValue ) { _value = newValue; }
123 
124  /**
125  * Returns this item's parent or 0 if there is none.
126  **/
127  TreeItem<PAYLOAD> * parent() const { return _parent; }
128 
129  /**
130  * Returns this item's next sibling or 0 if there is none.
131  **/
132  TreeItem<PAYLOAD> * next() const { return _next; }
133 
134  /**
135  * Returns this item's first child or 0 if there is none.
136  **/
137  TreeItem<PAYLOAD> * firstChild() const { return _firstChild; }
138 
139  /**
140  * Sets this item's parent.
141  **/
142  void setParent( TreeItem<PAYLOAD> * newParent ) { _parent = newParent; }
143 
144  /**
145  * Sets this item's next sibling.
146  **/
147  void setNext( TreeItem<PAYLOAD> * newNext ) { _next = newNext; }
148 
149  /**
150  * Sets this item's first child.
151  **/
152  void setFirstChild( TreeItem<PAYLOAD> * newFirstChild )
153  { _firstChild = newFirstChild; }
154 
155 
156  /**
157  * Add a child to the internal children list - usually called from within
158  * the child's default constructor.
159  *
160  * This default method does not maintain any meaningful sorting order -
161  * derived classes that require this might want to use the other
162  * constructor ( with 'autoAddChild' set to 'false' ) take care of child
163  * insertion themselves.
164  **/
165  void addChild( TreeItem<PAYLOAD> * newChild )
166  {
167  if ( newChild )
168  {
169  newChild->setNext( firstChild() );
170  setFirstChild( newChild );
171  }
172  }
173 
174 
175 protected:
176 
177  PAYLOAD _value;
178  TreeItem<PAYLOAD> * _parent;
179  TreeItem<PAYLOAD> * _next;
180  TreeItem<PAYLOAD> * _firstChild;
181 };
182 
183 
184 
185 /**
186  * Template class for tree items that maintain sort order.
187  *
188  * Class 'PAYLOAD' to provide operator<() in addition to what template
189  *'TreeItem' requires.
190  **/
191 template<class PAYLOAD> class SortedTreeItem: public TreeItem<PAYLOAD>
192 {
193 public:
194 
195  /**
196  * Constructor. Creates a new tree item with value "val" and inserts it in
197  * ascending sort order into the children list of "parent".
198  **/
200  SortedTreeItem<PAYLOAD> * parentItem = 0 )
201  : TreeItem<PAYLOAD> ( val, false, parentItem )
202  {
203  if ( parentItem )
204  {
205  // Hopefully we have a SortedTreeItem parent
206  SortedTreeItem<PAYLOAD> * sortParent =
207  dynamic_cast<SortedTreeItem<PAYLOAD> *> ( parentItem );
208 
209  if ( sortParent )
210  sortParent->insertChildSorted( this );
211  else // no SortedTreeItem parent - add unsorted
212  parentItem->addChild( this );
213  }
214  }
215 
216 
217  /**
218  * Destructor.
219  **/
220  virtual ~SortedTreeItem<PAYLOAD> () {}
221 
222 
223  /**
224  * Insert a child into the internal children list in ascending sort order.
225  * Called from the new child's constructor, thus 'public'.
226  **/
228  {
229  if ( ! newChild )
230  return;
231 
232  if ( ! firstChild() ||
233  newChild->value() < firstChild()->value() )
234  {
235  // Insert as first child
236 
237  newChild->setNext( firstChild() );
238  this->setFirstChild( newChild );
239  }
240  else
241  {
242  // Search correct place to insert
243 
244  TreeItem<PAYLOAD> * child = firstChild();
245 
246  while ( child->next() &&
247  child->next()->value() < newChild->value() )
248  {
249  child = child->next();
250  }
251 
252 
253  // Insert after 'child'
254 
255  newChild->setNext( child->next() );
256  child->setNext( newChild );
257  }
258  }
259 
260 
261  /**
262  * Returns this item's parent or 0 if there is none.
263  **/
266 
267  /**
268  * Returns this item's next sibling or 0 if there is none.
269  **/
272 
273  /**
274  * Returns this item's first child or 0 if there is none.
275  **/
278 
279 
280 private:
281 
282  /**
283  * Private ( i.e. disabled ) copy constructor and operator=()
284  * - neither makes any sense with this class.
285  **/
287  SortedTreeItem<PAYLOAD> & operator= ( const SortedTreeItem<PAYLOAD> & ) {}
288 };
289 
290 
291 
292 /**
293  * Find a direct child ( i.e., non-recursive ) with value "searchVal".
294  * Returns 0 if there is no such child.
295  **/
296 template<class ITEM, class PAYLOAD> inline
297 ITEM *
298 findDirectChild( ITEM * item, PAYLOAD searchVal )
299 {
300  TreeItem<PAYLOAD> * child = item->firstChild();
301 
302  while ( child )
303  {
304  if ( child->value() == searchVal )
305  return dynamic_cast<ITEM *> ( child );
306 
307  child = child->next();
308  }
309 
310  return 0;
311 }
312 
313 
314 
315 #endif // TreeItem_h
SortedTreeItem< PAYLOAD > * next() const
Returns this item&#39;s next sibling or 0 if there is none.
Definition: TreeItem.h:270
SortedTreeItem< PAYLOAD > * firstChild() const
Returns this item&#39;s first child or 0 if there is none.
Definition: TreeItem.h:276
void setValue(PAYLOAD newValue)
Set this item&#39;s value, the "payload".
Definition: TreeItem.h:122
Template class for tree items that maintain sort order.
Definition: TreeItem.h:191
SortedTreeItem< PAYLOAD > * parent() const
Returns this item&#39;s parent or 0 if there is none.
Definition: TreeItem.h:264
void setParent(TreeItem< PAYLOAD > *newParent)
Sets this item&#39;s parent.
Definition: TreeItem.h:142
Template class for tree items that can handle tree children in a generic way - firstChild(), next() and parent().
Definition: TreeItem.h:40
const PAYLOAD & value() const
Returns this item&#39;s value, the "payload".
Definition: TreeItem.h:113
TreeItem< PAYLOAD > * firstChild() const
Returns this item&#39;s first child or 0 if there is none.
Definition: TreeItem.h:137
TreeItem< PAYLOAD > * next() const
Returns this item&#39;s next sibling or 0 if there is none.
Definition: TreeItem.h:132
void insertChildSorted(SortedTreeItem< PAYLOAD > *newChild)
Insert a child into the internal children list in ascending sort order.
Definition: TreeItem.h:227
void addChild(TreeItem< PAYLOAD > *newChild)
Add a child to the internal children list - usually called from within the child&#39;s default constructo...
Definition: TreeItem.h:165
void setNext(TreeItem< PAYLOAD > *newNext)
Sets this item&#39;s next sibling.
Definition: TreeItem.h:147
void setFirstChild(TreeItem< PAYLOAD > *newFirstChild)
Sets this item&#39;s first child.
Definition: TreeItem.h:152
TreeItem< PAYLOAD > * parent() const
Returns this item&#39;s parent or 0 if there is none.
Definition: TreeItem.h:127