NCBI C++ ToolKit
tree_model.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef GUI_WIDGETS_PHY_TREE___TREE_MODEL__HPP
2 #define GUI_WIDGETS_PHY_TREE___TREE_MODEL__HPP
3 
4 /* $Id: tree_model.hpp 38346 2017-04-27 13:24:57Z falkrb $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Bob Falk
30  *
31  * File Description:
32  *
33  */
34 
35 #include <corelib/ncbistd.hpp>
36 #include <corelib/ncbi_tree.hpp>
37 
39 
40 /////////////////////////////////////////////////////////////////////////////
41 ///
42 /// Bi-directionaly linked N way tree allocated in a contiguous memory
43 /// block. Links are represented as indexes into the array.
44 ///
45 
46 
47 /// Index type for tree
48 typedef size_t TTreeIdx;
49 
50 /// Global define for a NULL link in the tree used for comparison
51 #define NULL_TREE_IDX static_cast<TTreeIdx>(-1)
52 
53 /// Base class for nodes in the tree. Takes a data template parameter to allow
54 /// additional storage.
55 template <class TData>
57 {
58 public:
59  typedef TData TValueType;
60  typedef size_t TTreeIdx;
61 
62  typedef vector<TTreeIdx> TNodeList;
63  typedef typename TNodeList::iterator TNodeList_I;
64  typedef typename TNodeList::const_iterator TNodeList_CI;
65  typedef typename TNodeList::reverse_iterator TNodeList_RI;
66  typedef typename TNodeList::const_reverse_iterator TNodeList_CRI;
67 
68 
69 public:
70  /// Construct an empty node (null parent)
72 
73  /// Set index of nodes parent
74  ///
75  /// @param
76  /// parent_idx index of parent node in the array
77  void SetParent(TTreeIdx parent_idx) {m_ParentNode = parent_idx;}
78 
79  /// Get node's parent
80  ///
81  /// @return index of parent node or null index if root
82  TTreeIdx GetParent() const { return m_ParentNode; }
83 
84  /// Set the parent index to Null() e.g. for root node
85  void RemoveParent() { m_ParentNode = Null(); }
86 
87  /// Check if the node has a parent
88  ///
89  /// @return index of parent node or null index if root
90  bool HasParent() const { return (m_ParentNode != Null()); }
91 
92  /// Add a child node
93  ///
94  /// @param
95  /// child_idx index of parent node in the array
96  void AddChild(TTreeIdx child_idx);
97 
98  /// Remove child node if it is a child of this node
99  ///
100  /// @param
101  /// child_idx index of child node to be removed
102  void RemoveChild(TTreeIdx child_idx);
103 
104  /// Check if another node is a child of this node
105  ///
106  /// @param
107  /// child_idx index of node to be checked
108  /// @return true if child_idx is a child of this node
109  bool HasChild(TTreeIdx child_idx) const;
110 
111  /// Static function that returns the null value. NULL_TREE_IDX
112  /// can also be used as the null value.
113  ///
114  /// @return the numeric index value used to represent NULL
115  static TTreeIdx Null();
116 
117  /// Report whether this is a leaf node
118  ///
119  /// @return TRUE if this is a leaf node (has no children),
120  /// false otherwise
121  bool IsLeaf() const { return m_ChildNodes.empty(); };
122 
123  /// Return the indices of this node's child nodes.
124  ///
125  /// @return list of the children of this node
127  const TNodeList& GetChildren() const { return m_ChildNodes; }
128 
129  /// Return const iterator to first subnode index.
130  TNodeList_CI SubNodeBegin() const { return m_ChildNodes.begin(); }
131 
132  /// Return iterator to first subnode index.
133  TNodeList_I SubNodeBegin() { return m_ChildNodes.begin(); }
134 
135  /// Return const iterator to end of subnode list
136  TNodeList_CI SubNodeEnd() const { return m_ChildNodes.end(); }
137 
138  /// Return iterator to end of subnode list
139  TNodeList_I SubNodeEnd() { return m_ChildNodes.end(); }
140 
141  /// Return const reverse iterator to (reverse) of begin of subnode array
142  TNodeList_CRI SubNodeRBegin() const { return m_ChildNodes.rbegin(); }
143 
144  /// Return reverse iterator to (reverse) begin of subnode array
145  TNodeList_RI SubNodeRBegin() { return m_ChildNodes.rbegin(); }
146 
147  /// Return const reverse iterator to (reverse) end of subnode array
148  TNodeList_CRI SubNodeREnd() const { return m_ChildNodes.rend(); }
149 
150  /// Return reverse iterator to (reverse) end of subnode array
151  TNodeList_RI SubNodeREnd() { return m_ChildNodes.rend(); }
152 
153  /// Remove connections to parent and children of this node
155 
156  /// Set the value-object for the node
157  void SetValue(const TData& data) { m_Data = data; }
158  /// Return the value object for the node
159  TData& GetValue() { return m_Data; }
160  const TData& GetValue() const { return m_Data; }
161 
162  /// Return the value object for the node using de-referenceing semantics
163  TData& operator*() { return m_Data; }
164  const TData& operator*() const { return m_Data; }
165 
166  TData* operator->() { return &m_Data; }
167  const TData* operator->() const { return &m_Data; }
168 
169 protected:
170  /// Index of parent node to this node. ==Null() if this is the root node
172  /// Indices of all the children of this node
173  vector<TTreeIdx> m_ChildNodes;
174  /// Data object
175  TData m_Data;
176 };
177 
178 
179 template<class TNode>
180 class CTreeModel : public CObject
181 {
182 public:
183  typedef TNode TNodeType;
184  typedef typename std::vector<TNodeType> TNodeVecType;
185  typedef typename TNode::TValueType TValueType;
186  typedef typename TNode::TTreeIdx TTreeIdx;
187 
188  typedef typename TNodeType::TNodeList TNodeList;
193 
194 public:
195  /// Create empty tree. Tree is not valid at this point (no nodes)
197  virtual ~CTreeModel() {}
198 
199  /// Remove all nodes (empty array) and set root index to Null
200  void Clear();
201 
202  /// Return a reference to the node at the given index
203  ///
204  /// @param
205  /// idx index of the node to be returned
206  /// @return reference to the node at index 'idx'
207  TNodeType& GetNode(TTreeIdx idx) { return m_Nodes[size_t(idx)]; }
208  const TNode& GetNode(TTreeIdx idx) const { return m_Nodes[size_t(idx)]; }
209 
210  /// Use operator[] to return a reference to the node at 'idx'.
211  TNodeType& operator[](TTreeIdx idx) { return m_Nodes[size_t(idx)]; }
212  const TNode& operator[](TTreeIdx idx) const { return m_Nodes[size_t(idx)]; }
213 
214 
215  /// Get the number of nodes currently in the array
216  ///
217  /// @return - the number of nodes (but some may be collapsed)
218  size_t GetSize() const { return m_Nodes.size(); }
219 
220  /// Get the number of displayed nodes in current tree layout
221  ///
222  /// @return - the number of displayed (active) nodes
223  size_t GetNumNodes() const { return m_NumNodes; }
224 
225  /// Set the number of displayed nodes in current tree layout
226  ///
227  /// @param
228  /// count - number of nodes
229  void SetNumNodes(int count) { m_NumNodes=count; }
230 
231 
232  /// Return a reference to the parent node of the given node. Throws
233  /// exception if the given node is root
234  ///
235  /// @param
236  /// node - the node whose parent is to be returned
237  /// @return - reference to node's parent, if node is not root
239  const TNodeType& GetParent(TNodeType& node) const;
240 
241  /// Return a reference to the 'value' object of a node
242  ///
243  /// @param
244  /// idx - index of the node
245  /// @return - reference to the value object held by the node at 'idx'
247  { return m_Nodes[size_t(idx)].GetValue(); }
248  const TValueType& GetNodeValue(TTreeIdx idx) const
249  { return m_Nodes[size_t(idx)].GetValue(); }
250 
251  /// Return a reference to the root node of the tree
252  ///
253  /// @return - reference to the root node
255  const TNode& GetRoot() const { return m_Nodes[m_RootIdx]; }
256 
257  /// Set the index of the root node of the tree. This is initially
258  /// 0 but the root index can move around with sorting, edits etc.
259  ///
260  /// @param
261  /// idx - the index for the tree's root node
262  void SetRootIdx(TTreeIdx idx) { m_RootIdx = idx; }
263 
264  /// Return the index of the root node
265  ///
266  /// @return the root node index
267  TTreeIdx GetRootIdx() const { return m_RootIdx; }
268 
269  /// Remove the node at 'child_idx' from its parent 'parent_idx'
270  /// Nothing is done if the node 'child_idx' is not a child of that parent
271  ///
272  /// @param
273  /// parent_idx - the index of the parent node
274  /// child_idx - the index of the child node
275  void RemoveChild(TTreeIdx parent_idx, TTreeIdx child_idx);
276 
277  /// Add the node at 'child_idx' to the children 'parent_idx'.
278  /// This does not check to see if the node is already a child.
279  ///
280  /// @param
281  /// parent_idx - the index of the parent node
282  /// child_idx - the index of the child node
283  void AddChild(TTreeIdx parent_idx, TTreeIdx child_idx);
284 
285  /// Sets the root idx to be 'idx' and updates the tree so that
286  /// all nodes above the new root become children of that node
287  ///
288  /// @param
289  /// idx - the new root node
290  void ReRoot(TTreeIdx idx);
291 
292  /// Add a new default node to the tree and return its index
293  ///
294  /// @return - the index of the new node
296 
297  /// Add a copy of node 'node' to the tree and return its index
298  ///
299  /// @param
300  /// node - the node from which to copy the new node
301  /// @return - the index of the new node
302  TTreeIdx AddNode(const TNode& node);
303 
304  /// Allocate the memory in advance, if you know how big the tree will be
305  ///
306  /// @param
307  /// target_size - the number of nodes that will be in the tree
308  void Reserve(size_t target_size);
309 
310  /// Return the index value that represents a NULL node
311  static TTreeIdx Null();
312 
313 protected:
314  /// Convert parents of node_idx to be its children
315  virtual void x_ConvertUpstream(TTreeIdx node_idx);
316 
317  /// The list of nodes in the tree
319 
320  /// Number of nodes in tree (not including collapsed/hidden nodes)
322 
323  /// The index of the root node within the tree
325 };
326 
327 /////////////////////////////////////////////////////////////////////////////
328 //
329 // Tree algorithms
330 //
331 
332 
333 /// Depth-first tree traversal algorithm.
334 ///
335 /// Takes tree and visitor function and calls function for every
336 /// node in the subtree rooted at node_idx
337 ///
338 /// Functor should have the next prototype:
339 /// ETreeTraverseCode Func(TTreeType& tree, TTreeType::TTreeIdx node, int delta)
340 /// where node is a reference to the visited node index and delta_level
341 /// reflects the current traverse direction(depth wise) in the tree,
342 /// 0 - algorithm stays is on the same level
343 /// 1 - we are going one level deep into the tree (from the root)
344 /// -1 - we are traveling back by one level (getting close to the root)
345 ///
346 /// The specificts of the algorithm is that it calls visitor both on the
347 /// way from the root to leafs and on the way back
348 /// Using this template we can implement both variants of tree
349 /// traversal (pre-order and post-order)
350 /// Visitor controls the traversal by returning ETreeTraverseCode
351 ///
352 /// @sa ETreeTraverseCode
353 ///
354 template<class TTreeModel, class Fun>
355 Fun TreeDepthFirst(TTreeModel& tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
356 {
357  typedef typename TTreeModel::TNodeType TNodeType;
358 
359  int delta_level = 0;
360  ETreeTraverseCode stop_scan;
361 
362  stop_scan = func(tree_model, node_idx, delta_level);
363  switch (stop_scan) {
364  case eTreeTraverseStop:
366  return func;
367  case eTreeTraverse:
368  break;
369  }
370 
371  delta_level = 1;
372  TNodeType* tr = &tree_model[node_idx];
373 
374  typedef typename TNodeType::TNodeList_I TTreeNodeIterator;
375 
376  TTreeNodeIterator it = tr->SubNodeBegin();
377  TTreeNodeIterator it_end = tr->SubNodeEnd();
378 
379  if (it == it_end)
380  return func;
381 
382  stack<TTreeNodeIterator> tree_stack;
383 
384  while (true) {
385  tr = &tree_model[*it];
386  stop_scan = func(tree_model, *it, delta_level);
387  switch (stop_scan) {
388  case eTreeTraverseStop:
389  return func;
390  case eTreeTraverse:
392  break;
393  }
394  if ( (stop_scan != eTreeTraverseStepOver) &&
395  (delta_level >= 0) &&
396  (!tr->IsLeaf())) { // sub-node, going down
397  tree_stack.push(it);
398  it = tr->SubNodeBegin();
399  it_end = tr->SubNodeEnd();
400  delta_level = 1;
401  continue;
402  }
403  ++it;
404  if (it == it_end) { // end of level, going up
405  if (tree_stack.empty()) {
406  break;
407  }
408  it = tree_stack.top();
409  tree_stack.pop();
410  tr = &tree_model[*it];
411  it_end = tree_model[tr->GetParent()].SubNodeEnd();
412  delta_level = -1;
413  continue;
414  }
415  // same level
416  delta_level = 0;
417 
418  } // while
419 
420  func(tree_model, node_idx, -1);
421  return func;
422 }
423 
424 
425 /// Calls TreeDepthFirst with the root node of 'tree_model'
426 ///
427 template<class TTreeModel, class Fun>
428 Fun TreeDepthFirst(TTreeModel& tree_model, Fun func)
429 {
430  return TreeDepthFirst(tree_model, tree_model.GetRootIdx(), func);
431 }
432 
433 /// Depth-first tree traversal which allows the traversed tree to update the
434 /// list of child nodes at the current node while iterating. Otherwise
435 /// identical to TreeDepthFirst
436 ///
437 template<class TTreeModel>
438 struct NodeListIter {
439  typedef typename TTreeModel::TNodeType TNodeType;
440  typedef typename TTreeModel::TNodeList TNodeList;
441  typedef typename TNodeType::TNodeList_I TTreeNodeIterator;
442 
444  : m_node_list(tr->GetChildren()), m_it(m_node_list.begin()) {}
445 
446  NodeListIter(const NodeListIter& rhs) { *this = rhs; }
447 
449  size_t off = rhs.m_it - rhs.m_node_list.begin();
450  m_node_list = rhs.m_node_list;
451  m_it = m_node_list.begin() + off;
452  return *this;
453  }
454 
455  void SetNode(TNodeType* tr)
456  { m_node_list = tr->GetChildren(); m_it = m_node_list.begin(); }
457 
460 };
461 
462 template<class TTreeModel, class Fun>
463 Fun TreeDepthFirstInvarient(TTreeModel& tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
464 {
465  typedef typename TTreeModel::TNodeType TNodeType;
466  typedef typename TNodeType::TNodeList_I TTreeNodeIterator;
467 
468  int delta_level = 0;
469  ETreeTraverseCode stop_scan;
470 
471  stop_scan = func(tree_model, node_idx, delta_level);
472  switch (stop_scan) {
473  case eTreeTraverseStop:
475  return func;
476  case eTreeTraverse:
477  break;
478  }
479 
480  delta_level = 1;
481  TNodeType* tr = &tree_model[node_idx];
482 
483  NodeListIter<TTreeModel> node_iter(tr);
484 
485  TTreeNodeIterator it_end = node_iter.m_node_list.end();
486 
487  if (node_iter.m_it == it_end)
488  return func;
489 
490  stack<NodeListIter<TTreeModel> > tree_stack;
491 
492  while (true) {
493  tr = &tree_model[*node_iter.m_it];
494  stop_scan = func(tree_model, *node_iter.m_it, delta_level);
495  switch (stop_scan) {
496  case eTreeTraverseStop:
497  return func;
498  case eTreeTraverse:
500  break;
501  }
502  if ( (stop_scan != eTreeTraverseStepOver) &&
503  (delta_level >= 0) &&
504  (!tr->IsLeaf())) { // sub-node, going down
505  tree_stack.push(node_iter);
506  node_iter.SetNode(tr);
507  //it = tr->SubNodeBegin();
508  it_end = node_iter.m_node_list.end();
509  delta_level = 1;
510  continue;
511  }
512  ++node_iter.m_it;
513  if (node_iter.m_it == it_end) { // end of level, going up
514  if (tree_stack.empty()) {
515  break;
516  }
517  node_iter = tree_stack.top();
518  tree_stack.pop();
519  tr = &tree_model[*node_iter.m_it];
520  it_end = node_iter.m_node_list.end();
521  delta_level = -1;
522  continue;
523  }
524  // same level
525  delta_level = 0;
526 
527  } // while
528 
529  func(tree_model, node_idx, -1);
530  return func;
531 }
532 
533 /// Calls TreeDepthFirstInvarient with the root node of 'tree_model'
534 ///
535 template<class TTreeModel, class Fun>
536 Fun TreeDepthFirstInvarient(TTreeModel& tree_model, Fun func)
537 {
538  return TreeDepthFirstInvarient(tree_model, tree_model.GetRootIdx(), func);
539 }
540 
541 ///////////////////////////////////////////////////////////////////////////////
542 /// Breadth-first tree traversall
543 ///
544 /// Traverse the tree in breadth-first order
545 ///
546 /// Takes tree and visitor function and calls function for every
547 /// node in the subtree rooted at node_idx
548 ///
549 /// Functor should have the next prototype:
550 /// ETreeTraverseCode Func(TTreeType& tree, TTreeType::TTreeIdx node, int delta)
551 /// where node is a reference to the visited node index and delta_level
552 /// reflects the current traverse direction(depth wise) in the tree,
553 /// 0 - algorithm stays on the same level
554 /// 1 - we are going one level deep into the tree (from the root)
555 ///
556 ///
557 ///
558 /// @sa ETreeTraverseCode
559 template<class TTreeModel, class Fun>
560 Fun TreeBreadthFirst(TTreeModel& tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
561 {
562  typedef typename TTreeModel::TNodeType TNodeType;
563  typedef typename TTreeModel::TTreeIdx TTreeIdx;
564 
565  int delta_level = 0;
566  ETreeTraverseCode stop_scan;
567 
568  stop_scan = func(tree_model, node_idx, delta_level);
569  switch (stop_scan) {
570  case eTreeTraverseStop:
572  return func;
573  case eTreeTraverse:
574  break;
575  }
576 
577  typedef typename TNodeType::TNodeList_I TTreeNodeIterator;
578 
579  queue<TTreeIdx> node_queue;
580  node_queue.push(node_idx);
581  int level_count = 1;
582  delta_level = 1;
583 
584  while (!node_queue.empty()) {
585  TTreeIdx node_idx = node_queue.front();
586  node_queue.pop();
587 
588  TNodeType* tr = &tree_model[node_idx];
589 
590  TTreeNodeIterator it = tr->SubNodeBegin();
591  TTreeNodeIterator it_end = tr->SubNodeEnd();
592  for (; it != it_end; ++it) {
593  stop_scan = func(tree_model, *it, delta_level);
594  switch (stop_scan) {
595  case eTreeTraverseStop:
596  return func;
597  case eTreeTraverse:
599  break;
600  }
601  if (stop_scan != eTreeTraverseStepOver) { // sub-node, queue for next pass
602  node_queue.push(*it);
603  }
604  // same level
605  delta_level = 0;
606  }
607 
608  // track current level so that we can set delta_level correctly
609  if (--level_count == 0) {
610  level_count = node_queue.size();
611  delta_level = 1;
612  }
613 
614  } // while
615 
616  func(tree_model, node_idx, -1);
617  return func;
618 }
619 
620 /// Calls TreeBreadthFirst with the root node of 'tree_model'
621 ///
622 template<class TTreeModel, class Fun>
623 Fun TreeBreadthFirst(TTreeModel& tree_model, Fun func)
624 {
625  return TreeBreadthFirst(tree_model, tree_model.GetRootIdx(), func);
626 }
627 
628 
629 
630 /////////////////////////////////////////////////////////////////////////////
631 //
632 // CTreeModelNode<TData> Implementation
633 //
634 
635 template <class TData>
637 
638 
639 template <class TData>
641 {
642 #ifdef _DEBUG
643  if (HasChild(child_idx)) {
644  LOG_POST("Trying to add duplicate child node: " << child_idx << " to another node");
645  return;
646  }
647 #endif
648 
649  m_ChildNodes.push_back(child_idx);
650 }
651 
652 template <class TData>
654 {
655  vector<TTreeIdx>::iterator iter = find(m_ChildNodes.begin(), m_ChildNodes.end(), child_idx);
656 
657  if (iter==m_ChildNodes.end()) {
658  return;
659  }
660 
661  m_ChildNodes.erase(iter);
662 }
663 
664 template <class TData>
665 bool CTreeModelNode<TData>::HasChild(size_t child_idx) const
666 {
667  return ( std::find(m_ChildNodes.begin(), m_ChildNodes.end(), child_idx) != m_ChildNodes.end());
668 }
669 
670 
671 /////////////////////////////////////////////////////////////////////////////
672 //
673 // CTreeModel<TNode> Implementation
674 //
675 
676 
677 template <class TNode>
679 
680 template<class TNode>
682 {
683  m_Nodes.clear();
684  m_NumNodes = 0;
685 
686  m_RootIdx = Null();
687 }
688 
689 template<class TNode>
691 {
692  if (node.GetParent() == TNodeType::Null())
693  NCBI_THROW(CException, eUnknown, "Attempt to retrieve NULL parent in tree");
694 
695  return m_Nodes[node.GetParent()];
696 }
697 
698 template<class TNode>
700 {
701  if (node.GetParent() == TNodeType::Null())
702  NCBI_THROW(CException, eUnknown, "Attempt to retrieve NULL parent in tree");
703 
704  return m_Nodes[node.GetParent()];
705 }
706 
707 template<class TNode>
709 {
710  m_Nodes[size_t(parent_idx)].RemoveChild(child_idx);
711  m_Nodes[size_t(child_idx)].SetParent(Null());
712 }
713 
714 template<class TNode>
715 void CTreeModel<TNode>::AddChild(TTreeIdx parent_idx, TTreeIdx child_idx)
716 {
717  m_Nodes[size_t(parent_idx)].AddChild(child_idx);
718  m_Nodes[size_t(child_idx)].SetParent(parent_idx);
719 }
720 
721 template<class TNode>
723 {
724  if (m_RootIdx == idx)
725  return;
726 
727  if (idx >= m_Nodes.size())
728  return;
729 
730  x_ConvertUpstream(idx);
731 
732  m_RootIdx = idx;
733 }
734 
735 template<class TNode>
737 {
738  TTreeIdx parent_idx = m_Nodes[node_idx].GetParent();
739 
740  if (parent_idx != Null()) {
741  RemoveChild(parent_idx, node_idx);
742  x_ConvertUpstream(parent_idx);
743  AddChild(node_idx, parent_idx);
744  }
745 }
746 
747 
748 template<class TNode>
750 {
751  m_Nodes.push_back(TNode());
752  size_t idx = m_Nodes.size()-1;
753 
754  return TTreeIdx(idx);
755 }
756 
757 template<class TNode>
759 {
760  size_t idx = m_Nodes.size();
761 
762  m_Nodes.push_back(node);
763  return TTreeIdx(idx);
764 }
765 
766 template<class TNode>
767 void CTreeModel<TNode>::Reserve(size_t target_size)
768 {
769  // ensure size is at least equal to target size
770  m_Nodes.reserve(target_size);
771 }
772 
774 
775 #endif // GUI_WIDGETS_PHY_TREE___TREE_MODEL__HPP
CObject –.
Definition: ncbiobj.hpp:180
Base class for nodes in the tree.
Definition: tree_model.hpp:57
const TData & operator*() const
Definition: tree_model.hpp:164
const TData & GetValue() const
Definition: tree_model.hpp:160
TData * operator->()
Definition: tree_model.hpp:166
void RemoveChild(TTreeIdx child_idx)
Remove child node if it is a child of this node.
Definition: tree_model.hpp:653
TData m_Data
Data object.
Definition: tree_model.hpp:175
void RemoveParent()
Set the parent index to Null() e.g. for root node.
Definition: tree_model.hpp:85
TNodeList::reverse_iterator TNodeList_RI
Definition: tree_model.hpp:65
TNodeList_RI SubNodeRBegin()
Return reverse iterator to (reverse) begin of subnode array.
Definition: tree_model.hpp:145
TTreeIdx GetParent() const
Get node's parent.
Definition: tree_model.hpp:82
void ClearConnections()
Remove connections to parent and children of this node.
Definition: tree_model.hpp:154
TTreeIdx m_ParentNode
Index of parent node to this node. ==Null() if this is the root node.
Definition: tree_model.hpp:171
TData & operator*()
Return the value object for the node using de-referenceing semantics.
Definition: tree_model.hpp:163
TNodeList_CI SubNodeEnd() const
Return const iterator to end of subnode list.
Definition: tree_model.hpp:136
TNodeList & GetChildren()
Return the indices of this node's child nodes.
Definition: tree_model.hpp:126
TNodeList::iterator TNodeList_I
Definition: tree_model.hpp:63
void SetParent(TTreeIdx parent_idx)
Set index of nodes parent.
Definition: tree_model.hpp:77
TNodeList_CRI SubNodeRBegin() const
Return const reverse iterator to (reverse) of begin of subnode array.
Definition: tree_model.hpp:142
TNodeList_CRI SubNodeREnd() const
Return const reverse iterator to (reverse) end of subnode array.
Definition: tree_model.hpp:148
bool HasChild(TTreeIdx child_idx) const
Check if another node is a child of this node.
Definition: tree_model.hpp:665
CTreeModelNode()
Construct an empty node (null parent)
Definition: tree_model.hpp:71
TData & GetValue()
Return the value object for the node.
Definition: tree_model.hpp:159
TNodeList_I SubNodeBegin()
Return iterator to first subnode index.
Definition: tree_model.hpp:133
TNodeList_RI SubNodeREnd()
Return reverse iterator to (reverse) end of subnode array.
Definition: tree_model.hpp:151
TNodeList::const_reverse_iterator TNodeList_CRI
Definition: tree_model.hpp:66
bool HasParent() const
Check if the node has a parent.
Definition: tree_model.hpp:90
TNodeList::const_iterator TNodeList_CI
Definition: tree_model.hpp:64
const TNodeList & GetChildren() const
Definition: tree_model.hpp:127
const TData * operator->() const
Definition: tree_model.hpp:167
vector< TTreeIdx > TNodeList
Definition: tree_model.hpp:62
TNodeList_I SubNodeEnd()
Return iterator to end of subnode list.
Definition: tree_model.hpp:139
bool IsLeaf() const
Report whether this is a leaf node.
Definition: tree_model.hpp:121
static TTreeIdx Null()
Static function that returns the null value.
Definition: tree_model.hpp:636
TNodeList_CI SubNodeBegin() const
Return const iterator to first subnode index.
Definition: tree_model.hpp:130
vector< TTreeIdx > m_ChildNodes
Indices of all the children of this node.
Definition: tree_model.hpp:173
void AddChild(TTreeIdx child_idx)
Add a child node.
Definition: tree_model.hpp:640
void SetValue(const TData &data)
Set the value-object for the node.
Definition: tree_model.hpp:157
virtual ~CTreeModel()
Definition: tree_model.hpp:197
int m_NumNodes
Number of nodes in tree (not including collapsed/hidden nodes)
Definition: tree_model.hpp:321
const TNode & operator[](TTreeIdx idx) const
Definition: tree_model.hpp:212
void ReRoot(TTreeIdx idx)
Sets the root idx to be 'idx' and updates the tree so that all nodes above the new root become childr...
Definition: tree_model.hpp:722
virtual void x_ConvertUpstream(TTreeIdx node_idx)
Convert parents of node_idx to be its children.
Definition: tree_model.hpp:736
const TValueType & GetNodeValue(TTreeIdx idx) const
Definition: tree_model.hpp:248
const TNode & GetRoot() const
Definition: tree_model.hpp:255
TNodeType & GetParent(TNodeType &node)
Return a reference to the parent node of the given node.
Definition: tree_model.hpp:690
TNodeType::TNodeList_I TNodeList_I
Definition: tree_model.hpp:189
TNodeVecType m_Nodes
The list of nodes in the tree.
Definition: tree_model.hpp:318
TTreeIdx AddNode(const TNode &node)
Add a copy of node 'node' to the tree and return its index.
Definition: tree_model.hpp:758
TValueType & GetNodeValue(TTreeIdx idx)
Return a reference to the 'value' object of a node.
Definition: tree_model.hpp:246
const TNodeType & GetParent(TNodeType &node) const
Definition: tree_model.hpp:699
TNodeType & operator[](TTreeIdx idx)
Use operator[] to return a reference to the node at 'idx'.
Definition: tree_model.hpp:211
void Reserve(size_t target_size)
Allocate the memory in advance, if you know how big the tree will be.
Definition: tree_model.hpp:767
size_t GetNumNodes() const
Get the number of displayed nodes in current tree layout.
Definition: tree_model.hpp:223
static TTreeIdx Null()
Return the index value that represents a NULL node.
Definition: tree_model.hpp:678
size_t GetSize() const
Get the number of nodes currently in the array.
Definition: tree_model.hpp:218
void SetNumNodes(int count)
Set the number of displayed nodes in current tree layout.
Definition: tree_model.hpp:229
CTreeModel()
Create empty tree. Tree is not valid at this point (no nodes)
Definition: tree_model.hpp:196
TNodeType & GetNode(TTreeIdx idx)
Return a reference to the node at the given index.
Definition: tree_model.hpp:207
TNodeType::TNodeList_CRI TNodeList_CRI
Definition: tree_model.hpp:192
TNodeType::TNodeList_CI TNodeList_CI
Definition: tree_model.hpp:190
void Clear()
Remove all nodes (empty array) and set root index to Null.
Definition: tree_model.hpp:681
TNodeType::TNodeList_RI TNodeList_RI
Definition: tree_model.hpp:191
TNodeType & GetRoot()
Return a reference to the root node of the tree.
Definition: tree_model.hpp:254
void AddChild(TTreeIdx parent_idx, TTreeIdx child_idx)
Add the node at 'child_idx' to the children 'parent_idx'.
Definition: tree_model.hpp:715
TNodeType::TNodeList TNodeList
Definition: tree_model.hpp:188
const TNode & GetNode(TTreeIdx idx) const
Definition: tree_model.hpp:208
TNode TNodeType
Definition: tree_model.hpp:183
std::vector< TNodeType > TNodeVecType
Definition: tree_model.hpp:184
TTreeIdx GetRootIdx() const
Return the index of the root node.
Definition: tree_model.hpp:267
TNode::TValueType TValueType
Definition: tree_model.hpp:185
TTreeIdx AddNode()
Add a new default node to the tree and return its index.
Definition: tree_model.hpp:749
TNode::TTreeIdx TTreeIdx
Definition: tree_model.hpp:186
void RemoveChild(TTreeIdx parent_idx, TTreeIdx child_idx)
Remove the node at 'child_idx' from its parent 'parent_idx' Nothing is done if the node 'child_idx' i...
Definition: tree_model.hpp:708
void SetRootIdx(TTreeIdx idx)
Set the index of the root node of the tree.
Definition: tree_model.hpp:262
TTreeIdx m_RootIdx
The index of the root node within the tree.
Definition: tree_model.hpp:324
Include a standard set of the NCBI C++ Toolkit most basic headers.
char data[12]
Definition: iconv.c:80
#define LOG_POST(message)
This macro is deprecated and it's strongly recomended to move in all projects (except tests) to macro...
Definition: ncbidiag.hpp:226
#define NCBI_THROW(exception_class, err_code, message)
Generic macro to throw an exception, given the exception class, error code and message string.
Definition: ncbiexpt.hpp:704
@ eUnknown
Definition: app_popup.hpp:72
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
ETreeTraverseCode
Tree traverse code returned by the traverse predicate function.
Definition: ncbi_tree.hpp:51
@ eTreeTraverseStop
Stop traversal (return form algorithm)
Definition: ncbi_tree.hpp:53
@ eTreeTraverse
Keep traversal.
Definition: ncbi_tree.hpp:52
@ eTreeTraverseStepOver
Do not traverse current node (pick the next one)
Definition: ncbi_tree.hpp:54
Depth-first tree traversal which allows the traversed tree to update the list of child nodes at the c...
Definition: tree_model.hpp:438
NodeListIter(const NodeListIter &rhs)
Definition: tree_model.hpp:446
void SetNode(TNodeType *tr)
Definition: tree_model.hpp:455
TTreeNodeIterator m_it
Definition: tree_model.hpp:459
TTreeModel::TNodeType TNodeType
Definition: tree_model.hpp:439
TTreeModel::TNodeList TNodeList
Definition: tree_model.hpp:440
NodeListIter & operator=(const NodeListIter &rhs)
Definition: tree_model.hpp:448
TNodeType::TNodeList_I TTreeNodeIterator
Definition: tree_model.hpp:441
TNodeList m_node_list
Definition: tree_model.hpp:458
NodeListIter(TNodeType *tr)
Definition: tree_model.hpp:443
Fun TreeBreadthFirst(TTreeModel &tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
Breadth-first tree traversall.
Definition: tree_model.hpp:560
#define NULL_TREE_IDX
Global define for a NULL link in the tree used for comparison.
Definition: tree_model.hpp:51
Fun TreeDepthFirst(TTreeModel &tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
Depth-first tree traversal algorithm.
Definition: tree_model.hpp:355
size_t TTreeIdx
Bi-directionaly linked N way tree allocated in a contiguous memory block.
Definition: tree_model.hpp:48
Fun TreeDepthFirstInvarient(TTreeModel &tree_model, typename TTreeModel::TTreeIdx node_idx, Fun func)
Definition: tree_model.hpp:463
Modified on Sat Jun 15 11:48:06 2024 by modify_doxy.py rev. 669887