home *** CD-ROM | disk | FTP | other *** search
/ Power GUI Programming with VisualAge C++ / powergui.iso / trialva / ibmcppw / samples / compiler / authors / treenode.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-20  |  11.0 KB  |  246 lines
  1. //+----------------------------------------------------------------------------+
  2. //| TREENODE.CPP                                                               |
  3. //|                                                                            |
  4. //| COPYRIGHT:                                                                 |
  5. //| ----------                                                                 |
  6. //|  Copyright (C) International Business Machines Corp., 1992,1993.           |
  7. //|                                                                            |
  8. //| DISCLAIMER OF WARRANTIES:                                                  |
  9. //| -------------------------                                                  |
  10. //|  The following [enclosed] code is sample code created by IBM Corporation.  |
  11. //|  This sample code is not part of any standard IBM product and is provided  |
  12. //|  to you solely for the purpose of assisting you in the development of      |
  13. //|  your applications.  The code is provided "AS IS", without warranty of     |
  14. //|  any kind.  IBM shall not be liable for any damages arising out of your    |
  15. //|  use of the sample code, even if they have been advised of the             |
  16. //|  possibility of such damages.                                              |
  17. //|                                                                            |
  18. //| REVISION LEVEL: 1.0                                                        |
  19. //| ---------------                                                            |
  20. //|                                                                            |
  21. //+----------------------------------------------------------------------------+
  22. //| Class Name  : TREENODE                                                     |
  23. //| Purpose     : This class encapulates the behaviour of a data structure     |
  24. //|               known as an n-ary Tree.                                      |
  25. //| Author      : njC Sales                                                    |
  26. //| Date        : 27 October 1992                                              |
  27. //+----------------------------------------------------------------------------+
  28.  
  29. #include "treenode.hpp"
  30.  
  31. //+----------------------------------------------------------------------------+
  32. //| Copy Constructor                                                           |
  33. //+----------------------------------------------------------------------------+
  34. TreeNode::TreeNode(const TreeNode &node) :
  35.    myState(node.myState),
  36.    TreeLink(node) {}
  37.  
  38. //+----------------------------------------------------------------------------+
  39. //| Assignment                                                                 |
  40. //+----------------------------------------------------------------------------+
  41. TreeNode &TreeNode::operator= (const TreeNode &node)
  42. {
  43.    if (this != &node)
  44.    {
  45.       myState= node.myState;
  46.       *((TreeLink *)this)= node;
  47.    }
  48.    return *this;
  49. }
  50.  
  51. //+----------------------------------------------------------------------------+
  52. //|              Tree Alteration Member Functions                              |
  53. //|                                                                            |
  54. //| Function: addChild                                                         |
  55. //| Purpose : Make ourselves a surrogate parent of a TreeNode                  |
  56. //| Note    : For safety, we invoke the delink function to free up all current |
  57. //|           associations, if they exist. This prevents dangling pointers     |
  58. //|           from coming back and haunting us.                                |
  59. //+----------------------------------------------------------------------------+
  60. TreeNode *TreeNode::addChild(TreeNode *node)
  61. {
  62.    if (0 != delink(node))
  63.       return adopt(this, node);
  64.    else
  65.       return 0;
  66. }
  67.  
  68. TreeNode *TreeNode::addChild(TreeNode &node)
  69. {
  70.    if (0 != delink(&node))
  71.       return adopt(this, &node);
  72.    else
  73.       return 0;
  74. }
  75.  
  76. //+----------------------------------------------------------------------------+
  77. //|              Tree Alteration Member Functions                              |
  78. //|                                                                            |
  79. //| Function: addSister                                                        |
  80. //| Purpose : Make a TreeNode a sister of ours                                 |
  81. //| Note    : For safety, we invoke the delink function to free up all current |
  82. //|           associations, if they exist. This prevents dangling pointers     |
  83. //|           from coming back and haunting us.                                |
  84. //+----------------------------------------------------------------------------+
  85. TreeNode *TreeNode::addSister(TreeNode *node)
  86. {
  87.    if (0 != delink(node))
  88.       return add(this, node);
  89.    else
  90.       return 0;
  91. }
  92.  
  93. TreeNode *TreeNode::addSister(TreeNode &node)
  94. {
  95.    if (0 != delink(&node))
  96.       return add(this, &node);
  97.    else
  98.       return 0;
  99. }
  100.  
  101. TreeNode *TreeNode::remove()
  102. {
  103.    return delink(this);
  104. }
  105.  
  106. //+----------------------------------------------------------------------------+
  107. //| Friend functions: adopt, insert, addfirst, add, delink                     |
  108. //|                                                                            |
  109. //| These functions have been made friends because they work on multiple       |
  110. //| TreeLink instances.                                                        |
  111. //+----------------------------------------------------------------------------+
  112.  
  113. //+----------------------------------------------------------------------------+
  114. //| Function: adopt                                                            |
  115. //| Returns:  A pointer to the parent                                          |
  116. //+----------------------------------------------------------------------------+
  117. TreeNode *adopt(TreeNode *parent, TreeNode *child)
  118. {
  119.    BOOL parentType;
  120.    if (parent->isUndefined())
  121.    {
  122.       //+----------------------------------------------------------------------+
  123.       //| Simplest case: Set the parent and child pointers in the correct      |
  124.       //|                instances                                             |
  125.       //+----------------------------------------------------------------------+
  126.       parent->setChild(child);
  127.       child->setParent(parent);
  128.       parent->setState(TreeNode::Internal);
  129.       return parent;
  130.    }
  131.    else if(parent->isLeaf())
  132.    {
  133.       //+----------------------------------------------------------------------+
  134.       //| 1. Change the state from Leaf to Internal                            |
  135.       //| 2. Invoke addfirst() -- add the first child for this parent          |
  136.       //+----------------------------------------------------------------------+
  137.       parent->setState(TreeNode::Internal);
  138.       return addfirst(parent, child);
  139.    }
  140.    else if (parent->isInternal() |
  141.             parent->isTop())
  142.    {
  143.       //+----------------------------------------------------------------------+
  144.       //| 1. Traverse list of children to find the last one                    |
  145.       //| 2. Add this child to the list, using add() or addfirst().            |
  146.       //+----------------------------------------------------------------------+
  147.       TreeNode *pNode= 0, *pSav= 0;
  148.       for (pNode= (TreeNode *)parent->getChild();
  149.            pNode != 0;
  150.            pSav= pNode, pNode= (TreeNode *)pNode->getRight());
  151.  
  152.       if (0 == pSav)           // No children found -- add the first one
  153.          return addfirst(parent,child);
  154.       else
  155.       {
  156.          add(pSav, child);
  157.          return parent;
  158.       }
  159.    }
  160.    else
  161.    {
  162.       return 0;
  163.    }
  164. }
  165.  
  166. //+----------------------------------------------------------------------------+
  167. //| Function: insert                                                           |
  168. //+----------------------------------------------------------------------------+
  169. TreeNode *insert(TreeNode *currentChild, TreeNode *newChild)
  170. {
  171.    newChild->setRight(currentChild->getRight());
  172.    newChild->setLeft(currentChild);
  173.    currentChild->getRight()->setLeft(newChild);
  174.    currentChild->setRight(newChild);
  175.    return currentChild;
  176. }
  177.  
  178. //+----------------------------------------------------------------------------+
  179. //| Function: addfirst                                                         |
  180. //+----------------------------------------------------------------------------+
  181. TreeNode *addfirst(TreeNode *parent, TreeNode *newChild)
  182. {
  183.    newChild->clearLeft();
  184.    newChild->setParent(parent);
  185.    newChild->setRight(parent->getChild());
  186.  
  187.    if (0 != parent->getChild())       // this parent has children
  188.       parent->getChild()->setLeft(newChild);
  189.  
  190.    parent->setChild(newChild);
  191.    return parent;
  192. }
  193.  
  194. //+----------------------------------------------------------------------------+
  195. //| Function: add                                                              |
  196. //+----------------------------------------------------------------------------+
  197. TreeNode *add(TreeNode *currentChild, TreeNode *newChild)
  198. {
  199.    currentChild->setRight(newChild);
  200.    newChild->setLeft(currentChild);
  201.    newChild->setParent(currentChild->getParent());
  202.    newChild->clearRight();
  203.    return currentChild;
  204. }
  205.  
  206. //+----------------------------------------------------------------------------+
  207. //| Function: delink                                                           |
  208. //+----------------------------------------------------------------------------+
  209. TreeNode *delink(TreeNode *currentNode)
  210. {
  211.    // Check to ensure that we are not a lone, neighbourless node.
  212.    if ((0 != currentNode->getLeft()) |
  213.        (0 != currentNode->getRight()))
  214.    {
  215.       if (0 == currentNode->getLeft())
  216.       {
  217.          //+-------------------------------------------------------------------+
  218.          //| Nothing on our left means we're the eldest and we have to adjust  |
  219.          //| our parent's child pointer to point to our sibling on the right.  |
  220.          //+-------------------------------------------------------------------+
  221.          if (0 != currentNode->getParent())
  222.             currentNode->getParent()->setChild(currentNode->getRight());
  223.       }
  224.       else if (0 == currentNode->getRight())
  225.       {
  226.          //+-------------------------------------------------------------------+
  227.          //| Nothing on our right means we're the youngest and we have to      |
  228.          //| adjust the pointer of our next elder sibling.                     |
  229.          //+-------------------------------------------------------------------+
  230.          currentNode->getLeft()->clearRight();
  231.       }
  232.       else
  233.       {
  234.          //+-------------------------------------------------------------------+
  235.          //| We're in the middle.                                              |
  236.          //+-------------------------------------------------------------------+
  237.          currentNode->getLeft()->setRight(currentNode->getRight());
  238.          currentNode->getRight()->setLeft(currentNode->getLeft());
  239.       }
  240.    }
  241.    currentNode->clearParent();
  242.    currentNode->clearLeft();
  243.    currentNode->clearRight();
  244.    return currentNode;
  245. }
  246.