COPASI API  4.16.103
CCopasiTree.h
Go to the documentation of this file.
1 /* Begin CVS Header
2  $Source: /Volumes/Home/Users/shoops/cvs/copasi_dev/copasi/utilities/CCopasiTree.h,v $
3  $Revision: 1.23 $
4  $Name: $
5  $Author: shoops $
6  $Date: 2012/05/17 16:38:34 $
7  End CVS Header */
8 
9 // Copyright (C) 2012 - 2011 by Pedro Mendes, Virginia Tech Intellectual
10 // Properties, Inc., University of Heidelberg, and The University
11 // of Manchester.
12 // All rights reserved.
13 
14 // Copyright (C) 2008 by Pedro Mendes, Virginia Tech Intellectual
15 // Properties, Inc., EML Research, gGmbH, University of Heidelberg,
16 // and The University of Manchester.
17 // All rights reserved.
18 
19 // Copyright (C) 2001 - 2007 by Pedro Mendes, Virginia Tech Intellectual
20 // Properties, Inc. and EML Research, gGmbH.
21 // All rights reserved.
22 
23 /**
24  * CCopasiTree class.
25  * The template class CCopasiTree describes a tree of Nodes.
26  *
27  * Created for COPASI by Stefan Hoops 2003
28  */
29 
30 #ifndef COPASI_CCopasiTree
31 #define COPASI_CCopasiTree
32 
33 #include <iterator>
34 #include <set>
35 #include <cstddef>
36 
37 template < class _Node > class CCopasiTree;
38 
39 template <class _Node>
40 std::ostream & operator<< (std::ostream & os, const CCopasiTree< _Node > & A);
41 
42 /**
43  * The template class CCopasiTree takes as template argument a class
44  * derived from the class CCopasiNode. It allows the construction of
45  * a tree with four simple methods. It assures that each node in the
46  * tree is unique.
47  *
48  * In addition it provides a forward iterator useful to traverse the
49  * tree.
50  *
51  * Note: The tree takes ownership of all nodes. Therefore, you must not use
52  * pointers to automatically created nodes in the attachNode() Function
53  * unless you use the detach node function prior to the destruction of
54  * the tree.
55  */
56 template < class _Node > class CCopasiTree
57 {
58 public:
59  typedef _Node Node;
60 
61  // Attributes
62 private:
63  /**
64  * The root of the tree
65  */
66  _Node * mpRoot;
67 
68  /**
69  * The list of all nodes. This is used to keep the tree consistent
70  * by avoiding multiple inserts of the same node.
71  */
72  std::set<_Node *> mList;
73 
74 public:
75  /**
76  * A forward iterator used to traverse the tree.
77  */
78 #if (defined __GNUC__ && __GNUC__ < 3 && !defined __APPLE_CC__)
79  class iterator: public std::forward_iterator< _Node, ptrdiff_t >
80 #else
81  class iterator:
82  public std::iterator< std::forward_iterator_tag, _Node, ptrdiff_t >
83 #endif
84 
85  {
86  private:
87  /**
88  * A pointer to the current node.
89  */
90  _Node * mCurrent;
91 
92  public:
93  /**
94  * Default constructor.
95  * Note: When no argument is given the iterator points to the end of
96  * the tree.
97  * @param Node * begin (default NULL)
98  */
99  iterator(_Node * begin = NULL):
100  mCurrent(begin)
101  {}
102 
103  /**
104  * Copy constructor
105  * @param const iterator & src
106  */
107  iterator(const iterator & src):
108  mCurrent(src.mCurrent)
109  {}
110 
111  /**
112  * Destructor
113  */
115 
116  /**
117  * Dereference operator * returns the node the iterator points to.
118  * @return Node &
119  */
120  _Node & operator*() const {return * mCurrent;}
121 
122  /**
123  * Dereference operator * returns the node the iterator points to.
124  * @return Node &
125  */
126  _Node * operator->() const {return mCurrent;}
127 
128  /**
129  * Comparison operator !=
130  * @param const iterator &rhs
131  * @return bool not-equal
132  */
133  bool operator!=(const iterator &rhs)
134  {return (mCurrent != rhs.mCurrent);}
135 
136  /**
137  * Assignment operator from a node to an iterator
138  * @param Node * pNode
139  * @return iterator &
140  */
141  iterator & operator=(_Node * pNode)
142  {
143  mCurrent = pNode;
144  return *this;
145  }
146 
147  public:
148  /**
149  * Prefix increment operator ++
150  * @return iterator &
151  */
153  {
154  mCurrent = (_Node *) mCurrent->getNext();
155 
156  return *this;
157  }
158  };
159 
160  /**
161  * A const forward iterator used to traverse the tree.
162  */
163 #if (defined __GNUC__ && __GNUC__ < 3 && !defined __APPLE_CC__)
164  class const_iterator: public std::forward_iterator< _Node, ptrdiff_t >
165 #else
167  public std::iterator< std::forward_iterator_tag, _Node, ptrdiff_t >
168 #endif
169 
170  {
171  private:
172  /**
173  * A pointer to the current node.
174  */
175  const _Node * mCurrent;
176 
177  public:
178  /**
179  * Default constructor.
180  * Note: When no argument is given the iterator points to the end of
181  * the tree.
182  * @param Node * begin (default NULL)
183  */
184  const_iterator(const _Node * begin = NULL):
185  mCurrent(begin)
186  {}
187 
188  /**
189  * Copy constructor
190  * @param const iterator & src
191  */
193  mCurrent(src.mCurrent)
194  {}
195 
196  /**
197  * Destructor
198  */
200 
201  /**
202  * Dereference operator * returns the node the iterator points to.
203  * @return Node &
204  */
205  const _Node & operator*() const {return * mCurrent;}
206 
207  /**
208  * Dereference operator * returns the node the iterator points to.
209  * @return Node &
210  */
211  const _Node * operator->() const {return mCurrent;}
212 
213  /**
214  * Comparison operator !=
215  * @param const iterator &rhs
216  * @return bool not-equal
217  */
218  bool operator!=(const const_iterator &rhs)
219  {return (mCurrent != rhs.mCurrent);}
220 
221  /**
222  * Assignment operator from a node to an iterator
223  * @param Node * pNode
224  * @return iterator &
225  */
226  const_iterator & operator=(const _Node * pNode)
227  {
228  mCurrent = pNode;
229  return *this;
230  }
231 
232  public:
233  /**
234  * Prefix increment operator ++
235  * @return iterator &
236  */
238  {
239  mCurrent = (_Node *) mCurrent->getNext();
240 
241  return *this;
242  }
243  };
244 
245  // Operations
246 public:
247  /**
248  * Default constructor
249  */
251  mpRoot(new _Node),
252  mList()
253  {mList.insert(mpRoot);}
254 
255  /**
256  * Destructor
257  */
259 
260  /**
261  * Retrieve an iterator pointing to the beginning of the tree
262  * @return iterator begin
263  */
264  iterator begin() const {return iterator(mpRoot);}
265 
266  /**
267  * Retrieve an iterator pointing beyond the end of the tree
268  * @return iterator end
269  */
270  iterator end() const {return iterator(NULL);}
271 
272  /**
273  * Retrieve the root node of the tree
274  * @return Node * root
275  */
276  _Node * getRoot() {return mpRoot;}
277 
278  /**
279  * Retrieve the data of the Tree.
280  * @return Data data
281  */
282  typename _Node::Data getData() const {return mpRoot->getData();}
283 
284  /**
285  * Attach a Node to the tree
286  * Note: If pAfterChild == pParent then the child will be inserted as
287  * the first child
288  * @param Node * pNode
289  * @param Node * pParent (default: NULL equivalent to the root of the tree)
290  * @param Node * pAfterChild (default: NULL at the end of the children)
291  * @return bool Success
292  */
293  bool attachNode(_Node * pNode,
294  _Node * pParent = NULL,
295  _Node * pAfterChild = NULL)
296  {
297  bool Success = true;
298 
299  if (mList.count(pNode))
300  return false; // Node already in tree.
301 
302  if (pAfterChild && !mList.count(pAfterChild))
303  return false; // Invalid insertion point.
304 
305  if (pParent)
306  {
307  if (mList.count(pParent))
308  Success = pParent->addChild(pNode, pAfterChild);
309  else
310  Success = false; // Invalid parent.
311  }
312  else
313  Success = mpRoot->addChild(pNode, pAfterChild);
314 
315  if (Success)
316  {
317  iterator it = pNode;
318  iterator end = (_Node *) it->getNextNonChild();
319 
320  for (; it != end; ++it)
321  mList.insert(&*it);
322  }
323 
324  return Success;
325  }
326 
327  /**
328  * Remove the given node of the tree
329  * @param Node * pNode
330  * @return bool Success
331  */
332  bool removeNode(_Node * pNode)
333  {
334  if (!pNode) return false; // Nothing to remove.
335 
336  if (pNode == mpRoot) return false; // Root must not be removed.
337 
338  iterator it = pNode;
339  iterator end = (_Node *) it->getNextNonChild();
340 
341  for (; it != end; ++it)
342  mList.erase(&*it);
343 
344  delete pNode;
345 
346  return true;
347  }
348 
349  /**
350  * Move a given node from its current place in the tree to the
351  * one specified by pParent and pAfterChild. The insertion
352  * behavior is similar to addChild().
353  * @param Node * pNode
354  * @param Node * pParent (default: NULL equivalent to the root of the tree)
355  * @param Node * pAfterChild (default: NULL at the end of the children)
356  * @return bool Success
357  */
358  bool moveNode(_Node * pNode, _Node * pParent = NULL, _Node * pAfterChild = NULL)
359  {
360  detachNode(pNode);
361  return attachNode(pNode, pParent, pAfterChild);
362  }
363 
364  /**
365  * Detach node.
366  * Node: After detachment of a node the tree no longer has the ownership.
367  * @param Node * pNode
368  * @return bool Success
369  */
370  bool detachNode(_Node * pNode)
371  {
372  if (!pNode) return false; // Nothing to do.
373 
374  if (pNode == mpRoot) return false; // Root must not be detached
375 
376  iterator it = pNode;
377  iterator end = (_Node *) it->getNextNonChild();
378 
379  for (; it != end; ++it)
380  mList.erase(&*it);
381 
382  return pNode->getParent()->removeChild(pNode);
383  }
384 
385 #if defined _MSC_VER && _MSC_VER < 1201 // 1200 Identifies Visual C++ 6.0
386  friend std::ostream & operator << (std::ostream & os,
387  const CCopasiTree< _Node > & A);
388 #else
389  friend std::ostream & operator << <>(std::ostream & os,
390  const CCopasiTree< _Node > & A);
391 #endif // WIN32
392 };
393 
394 template <class _Node>
395 std::ostream & operator<< (std::ostream & os,
396  const CCopasiTree< _Node > & A)
397 {
398  typename CCopasiTree< _Node >::iterator it = A.begin();
399  typename CCopasiTree< _Node >::iterator end = A.end();
400 
401  for (; it != end && &*it != NULL; ++it)
402  os << &*it << ": parent: " << it->getParent()
403  << ", child: " << it->getChild()
404  << ", sibling: " << it->getSibling() << std::endl;
405 
406  os << std::endl;
407  return os;
408 }
409 
410 #endif // COPASI_CCopasiTree
bool operator!=(const const_iterator &rhs)
Definition: CCopasiTree.h:218
#define pdelete(p)
Definition: copasi.h:215
const_iterator & operator=(const _Node *pNode)
Definition: CCopasiTree.h:226
iterator(const iterator &src)
Definition: CCopasiTree.h:107
_Node Node
Definition: CCopasiTree.h:59
bool attachNode(_Node *pNode, _Node *pParent=NULL, _Node *pAfterChild=NULL)
Definition: CCopasiTree.h:293
iterator begin() const
Definition: CCopasiTree.h:264
_Node * mpRoot
Definition: CCopasiTree.h:66
const_iterator & operator++()
Definition: CCopasiTree.h:237
_Node * operator->() const
Definition: CCopasiTree.h:126
const _Node & operator*() const
Definition: CCopasiTree.h:205
bool removeNode(_Node *pNode)
Definition: CCopasiTree.h:332
const_iterator(const _Node *begin=NULL)
Definition: CCopasiTree.h:184
iterator end() const
Definition: CCopasiTree.h:270
bool operator!=(const iterator &rhs)
Definition: CCopasiTree.h:133
iterator & operator++()
Definition: CCopasiTree.h:152
_Node * getRoot()
Definition: CCopasiTree.h:276
iterator & operator=(_Node *pNode)
Definition: CCopasiTree.h:141
bool moveNode(_Node *pNode, _Node *pParent=NULL, _Node *pAfterChild=NULL)
Definition: CCopasiTree.h:358
const _Node * operator->() const
Definition: CCopasiTree.h:211
const_iterator(const const_iterator &src)
Definition: CCopasiTree.h:192
std::set< _Node * > mList
Definition: CCopasiTree.h:72
_Node::Data getData() const
Definition: CCopasiTree.h:282
friend std::ostream & operator<<(std::ostream &os, const CCopasiTree< _Node > &A)
Definition: CCopasiTree.h:395
_Node & operator*() const
Definition: CCopasiTree.h:120
iterator(_Node *begin=NULL)
Definition: CCopasiTree.h:99
bool detachNode(_Node *pNode)
Definition: CCopasiTree.h:370
std::ostream & operator<<(std::ostream &os, const CCopasiTree< _Node > &A)
Definition: CCopasiTree.h:395