home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cset21v1.zip / IBMCPP / SAMPLES / COMPILER / SAMPLE06 / TREENODE.CPP < prev    next >
Text File  |  1993-05-07  |  11KB  |  247 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 <os2.h>
  30. #include "treenode.hpp"
  31.  
  32. //+----------------------------------------------------------------------------+
  33. //| Copy Constructor                                                           |
  34. //+----------------------------------------------------------------------------+
  35. TreeNode::TreeNode(const TreeNode &node) :
  36.    myState(node.myState),
  37.    TreeLink(node) {}
  38.  
  39. //+----------------------------------------------------------------------------+
  40. //| Assignment                                                                 |
  41. //+----------------------------------------------------------------------------+
  42. TreeNode &TreeNode::operator= (const TreeNode &node)
  43. {
  44.    if (this != &node)
  45.    {
  46.       myState= node.myState;
  47.       *((TreeLink *)this)= node;
  48.    }
  49.    return *this;
  50. }
  51.  
  52. //+----------------------------------------------------------------------------+
  53. //|              Tree Alteration Member Functions                              |
  54. //|                                                                            |
  55. //| Function: addChild                                                         |
  56. //| Purpose : Make ourselves a surrogate parent of a TreeNode                  |
  57. //| Note    : For safety, we invoke the delink function to free up all current |
  58. //|           associations, if they exist. This prevents dangling pointers     |
  59. //|           from coming back and haunting us.                                |
  60. //+----------------------------------------------------------------------------+
  61. TreeNode *TreeNode::addChild(TreeNode *node)
  62. {
  63.    if (0 != delink(node))
  64.       return adopt(this, node);
  65.    else
  66.       return 0;
  67. }
  68.  
  69. TreeNode *TreeNode::addChild(TreeNode &node)
  70. {
  71.    if (0 != delink(&node))
  72.       return adopt(this, &node);
  73.    else
  74.       return 0;
  75. }
  76.  
  77. //+----------------------------------------------------------------------------+
  78. //|              Tree Alteration Member Functions                              |
  79. //|                                                                            |
  80. //| Function: addSister                                                        |
  81. //| Purpose : Make a TreeNode a sister of ours                                 |
  82. //| Note    : For safety, we invoke the delink function to free up all current |
  83. //|           associations, if they exist. This prevents dangling pointers     |
  84. //|           from coming back and haunting us.                                |
  85. //+----------------------------------------------------------------------------+
  86. TreeNode *TreeNode::addSister(TreeNode *node)
  87. {
  88.    if (0 != delink(node))
  89.       return add(this, node);
  90.    else
  91.       return 0;
  92. }
  93.  
  94. TreeNode *TreeNode::addSister(TreeNode &node)
  95. {
  96.    if (0 != delink(&node))
  97.       return add(this, &node);
  98.    else
  99.       return 0;
  100. }
  101.  
  102. TreeNode *TreeNode::remove()
  103. {
  104.    return delink(this);
  105. }
  106.  
  107. //+----------------------------------------------------------------------------+
  108. //| Friend functions: adopt, insert, addfirst, add, delink                     |
  109. //|                                                                            |
  110. //| These functions have been made friends because they work on multiple       |
  111. //| TreeLink instances.                                                        |
  112. //+----------------------------------------------------------------------------+
  113.  
  114. //+----------------------------------------------------------------------------+
  115. //| Function: adopt                                                            |
  116. //| Returns:  A pointer to the parent                                          |
  117. //+----------------------------------------------------------------------------+
  118. TreeNode *adopt(TreeNode *parent, TreeNode *child)
  119. {
  120.    BOOL parentType;
  121.    if (parent->isUndefined())
  122.    {
  123.       //+----------------------------------------------------------------------+
  124.       //| Simplest case: Set the parent and child pointers in the correct      |
  125.       //|                instances                                             |
  126.       //+----------------------------------------------------------------------+
  127.       parent->setChild(child);
  128.       child->setParent(parent);
  129.       parent->setState(TreeNode::Internal);
  130.       return parent;
  131.    }
  132.    else if(parent->isLeaf())
  133.    {
  134.       //+----------------------------------------------------------------------+
  135.       //| 1. Change the state from Leaf to Internal                            |
  136.       //| 2. Invoke addfirst() -- add the first child for this parent          |
  137.       //+----------------------------------------------------------------------+
  138.       parent->setState(TreeNode::Internal);
  139.       return addfirst(parent, child);
  140.    }
  141.    else if (parent->isInternal() |
  142.             parent->isTop())
  143.    {
  144.       //+----------------------------------------------------------------------+
  145.       //| 1. Traverse list of children to find the last one                    |
  146.       //| 2. Add this child to the list, using add() or addfirst().            |
  147.       //+----------------------------------------------------------------------+
  148.       TreeNode *pNode= 0, *pSav= 0;
  149.       for (pNode= (TreeNode *)parent->getChild();
  150.            pNode != 0;
  151.            pSav= pNode, pNode= (TreeNode *)pNode->getRight());
  152.  
  153.       if (0 == pSav)           // No children found -- add the first one
  154.          return addfirst(parent,child);
  155.       else
  156.       {
  157.          add(pSav, child);
  158.          return parent;
  159.       }
  160.    }
  161.    else
  162.    {
  163.       return 0;
  164.    }
  165. }
  166.  
  167. //+----------------------------------------------------------------------------+
  168. //| Function: insert                                                           |
  169. //+----------------------------------------------------------------------------+
  170. TreeNode *insert(TreeNode *currentChild, TreeNode *newChild)
  171. {
  172.    newChild->setRight(currentChild->getRight());
  173.    newChild->setLeft(currentChild);
  174.    currentChild->getRight()->setLeft(newChild);
  175.    currentChild->setRight(newChild);
  176.    return currentChild;
  177. }
  178.  
  179. //+----------------------------------------------------------------------------+
  180. //| Function: addfirst                                                         |
  181. //+----------------------------------------------------------------------------+
  182. TreeNode *addfirst(TreeNode *parent, TreeNode *newChild)
  183. {
  184.    newChild->clearLeft();
  185.    newChild->setParent(parent);
  186.    newChild->setRight(parent->getChild());
  187.  
  188.    if (0 != parent->getChild())       // this parent has children
  189.       parent->getChild()->setLeft(newChild);
  190.  
  191.    parent->setChild(newChild);
  192.    return parent;
  193. }
  194.  
  195. //+----------------------------------------------------------------------------+
  196. //| Function: add                                                              |
  197. //+----------------------------------------------------------------------------+
  198. TreeNode *add(TreeNode *currentChild, TreeNode *newChild)
  199. {
  200.    currentChild->setRight(newChild);
  201.    newChild->setLeft(currentChild);
  202.    newChild->setParent(currentChild->getParent());
  203.    newChild->clearRight();
  204.    return currentChild;
  205. }
  206.  
  207. //+----------------------------------------------------------------------------+
  208. //| Function: delink                                                           |
  209. //+----------------------------------------------------------------------------+
  210. TreeNode *delink(TreeNode *currentNode)
  211. {
  212.    // Check to ensure that we are not a lone, neighbourless node.
  213.    if ((0 != currentNode->getLeft()) |
  214.        (0 != currentNode->getRight()))
  215.    {
  216.       if (0 == currentNode->getLeft())
  217.       {
  218.          //+-------------------------------------------------------------------+
  219.          //| Nothing on our left means we're the eldest and we have to adjust  |
  220.          //| our parent's child pointer to point to our sibling on the right.  |
  221.          //+-------------------------------------------------------------------+
  222.          if (0 != currentNode->getParent())
  223.             currentNode->getParent()->setChild(currentNode->getRight());
  224.       }
  225.       else if (0 == currentNode->getRight())
  226.       {
  227.          //+-------------------------------------------------------------------+
  228.          //| Nothing on our right means we're the youngest and we have to      |
  229.          //| adjust the pointer of our next elder sibling.                     |
  230.          //+-------------------------------------------------------------------+
  231.          currentNode->getLeft()->clearRight();
  232.       }
  233.       else
  234.       {
  235.          //+-------------------------------------------------------------------+
  236.          //| We're in the middle.                                              |
  237.          //+-------------------------------------------------------------------+
  238.          currentNode->getLeft()->setRight(currentNode->getRight());
  239.          currentNode->getRight()->setLeft(currentNode->getLeft());
  240.       }
  241.    }
  242.    currentNode->clearParent();
  243.    currentNode->clearLeft();
  244.    currentNode->clearRight();
  245.    return currentNode;
  246. }
  247.