//+----------------------------------------------------------------------------+
//| TREENODE.CPP                                                               |
//|                                                                            |
//| COPYRIGHT:                                                                 |
//| ----------                                                                 |
//|  Copyright (C) International Business Machines Corp., 1992,1993.           |
//|                                                                            |
//| DISCLAIMER OF WARRANTIES:                                                  |
//| -------------------------                                                  |
//|  The following [enclosed] code is sample code created by IBM Corporation.  |
//|  This sample code is not part of any standard IBM product and is provided  |
//|  to you solely for the purpose of assisting you in the development of      |
//|  your applications.  The code is provided "AS IS", without warranty of     |
//|  any kind.  IBM shall not be liable for any damages arising out of your    |
//|  use of the sample code, even if they have been advised of the             |
//|  possibility of such damages.                                              |
//|                                                                            |
//| REVISION LEVEL: 1.0                                                        |
//| ---------------                                                            |
//|                                                                            |
//+----------------------------------------------------------------------------+
//| Class Name  : TREENODE                                                     |
//| Purpose     : This class encapulates the behaviour of a data structure     |
//|               known as an n-ary Tree.                                      |
//| Author      : njC Sales                                                    |
//| Date        : 27 October 1992                                              |
//+----------------------------------------------------------------------------+

#include <os2.h>
#include "treenode.hpp"

//+----------------------------------------------------------------------------+
//| Copy Constructor                                                           |
//+----------------------------------------------------------------------------+
TreeNode::TreeNode(const TreeNode &node) :
   myState(node.myState),
   TreeLink(node) {}

//+----------------------------------------------------------------------------+
//| Assignment                                                                 |
//+----------------------------------------------------------------------------+
TreeNode &TreeNode::operator= (const TreeNode &node)
{
   if (this != &node)
   {
      myState= node.myState;
      *((TreeLink *)this)= node;
   }
   return *this;
}

//+----------------------------------------------------------------------------+
//|              Tree Alteration Member Functions                              |
//|                                                                            |
//| Function: addChild                                                         |
//| Purpose : Make ourselves a surrogate parent of a TreeNode                  |
//| Note    : For safety, we invoke the delink function to free up all current |
//|           associations, if they exist. This prevents dangling pointers     |
//|           from coming back and haunting us.                                |
//+----------------------------------------------------------------------------+
TreeNode *TreeNode::addChild(TreeNode *node)
{
   if (0 != delink(node))
      return adopt(this, node);
   else
      return 0;
}

TreeNode *TreeNode::addChild(TreeNode &node)
{
   if (0 != delink(&node))
      return adopt(this, &node);
   else
      return 0;
}

//+----------------------------------------------------------------------------+
//|              Tree Alteration Member Functions                              |
//|                                                                            |
//| Function: addSister                                                        |
//| Purpose : Make a TreeNode a sister of ours                                 |
//| Note    : For safety, we invoke the delink function to free up all current |
//|           associations, if they exist. This prevents dangling pointers     |
//|           from coming back and haunting us.                                |
//+----------------------------------------------------------------------------+
TreeNode *TreeNode::addSister(TreeNode *node)
{
   if (0 != delink(node))
      return add(this, node);
   else
      return 0;
}

TreeNode *TreeNode::addSister(TreeNode &node)
{
   if (0 != delink(&node))
      return add(this, &node);
   else
      return 0;
}

TreeNode *TreeNode::remove()
{
   return delink(this);
}

//+----------------------------------------------------------------------------+
//| Friend functions: adopt, insert, addfirst, add, delink                     |
//|                                                                            |
//| These functions have been made friends because they work on multiple       |
//| TreeLink instances.                                                        |
//+----------------------------------------------------------------------------+

//+----------------------------------------------------------------------------+
//| Function: adopt                                                            |
//| Returns:  A pointer to the parent                                          |
//+----------------------------------------------------------------------------+
TreeNode *adopt(TreeNode *parent, TreeNode *child)
{
   BOOL parentType;
   if (parent->isUndefined())
   {
      //+----------------------------------------------------------------------+
      //| Simplest case: Set the parent and child pointers in the correct      |
      //|                instances                                             |
      //+----------------------------------------------------------------------+
      parent->setChild(child);
      child->setParent(parent);
      parent->setState(TreeNode::Internal);
      return parent;
   }
   else if(parent->isLeaf())
   {
      //+----------------------------------------------------------------------+
      //| 1. Change the state from Leaf to Internal                            |
      //| 2. Invoke addfirst() -- add the first child for this parent          |
      //+----------------------------------------------------------------------+
      parent->setState(TreeNode::Internal);
      return addfirst(parent, child);
   }
   else if (parent->isInternal() |
            parent->isTop())
   {
      //+----------------------------------------------------------------------+
      //| 1. Traverse list of children to find the last one                    |
      //| 2. Add this child to the list, using add() or addfirst().            |
      //+----------------------------------------------------------------------+
      TreeNode *pNode= 0, *pSav= 0;
      for (pNode= (TreeNode *)parent->getChild();
           pNode != 0;
           pSav= pNode, pNode= (TreeNode *)pNode->getRight());

      if (0 == pSav)           // No children found -- add the first one
         return addfirst(parent,child);
      else
      {
         add(pSav, child);
         return parent;
      }
   }
   else
   {
      return 0;
   }
}

//+----------------------------------------------------------------------------+
//| Function: insert                                                           |
//+----------------------------------------------------------------------------+
TreeNode *insert(TreeNode *currentChild, TreeNode *newChild)
{
   newChild->setRight(currentChild->getRight());
   newChild->setLeft(currentChild);
   currentChild->getRight()->setLeft(newChild);
   currentChild->setRight(newChild);
   return currentChild;
}

//+----------------------------------------------------------------------------+
//| Function: addfirst                                                         |
//+----------------------------------------------------------------------------+
TreeNode *addfirst(TreeNode *parent, TreeNode *newChild)
{
   newChild->clearLeft();
   newChild->setParent(parent);
   newChild->setRight(parent->getChild());

   if (0 != parent->getChild())       // this parent has children
      parent->getChild()->setLeft(newChild);

   parent->setChild(newChild);
   return parent;
}

//+----------------------------------------------------------------------------+
//| Function: add                                                              |
//+----------------------------------------------------------------------------+
TreeNode *add(TreeNode *currentChild, TreeNode *newChild)
{
   currentChild->setRight(newChild);
   newChild->setLeft(currentChild);
   newChild->setParent(currentChild->getParent());
   newChild->clearRight();
   return currentChild;
}

//+----------------------------------------------------------------------------+
//| Function: delink                                                           |
//+----------------------------------------------------------------------------+
TreeNode *delink(TreeNode *currentNode)
{
   // Check to ensure that we are not a lone, neighbourless node.
   if ((0 != currentNode->getLeft()) |
       (0 != currentNode->getRight()))
   {
      if (0 == currentNode->getLeft())
      {
         //+-------------------------------------------------------------------+
         //| Nothing on our left means we're the eldest and we have to adjust  |
         //| our parent's child pointer to point to our sibling on the right.  |
         //+-------------------------------------------------------------------+
         if (0 != currentNode->getParent())
            currentNode->getParent()->setChild(currentNode->getRight());
      }
      else if (0 == currentNode->getRight())
      {
         //+-------------------------------------------------------------------+
         //| Nothing on our right means we're the youngest and we have to      |
         //| adjust the pointer of our next elder sibling.                     |
         //+-------------------------------------------------------------------+
         currentNode->getLeft()->clearRight();
      }
      else
      {
         //+-------------------------------------------------------------------+
         //| We're in the middle.                                              |
         //+-------------------------------------------------------------------+
         currentNode->getLeft()->setRight(currentNode->getRight());
         currentNode->getRight()->setLeft(currentNode->getLeft());
      }
   }
   currentNode->clearParent();
   currentNode->clearLeft();
   currentNode->clearRight();
   return currentNode;
}
