/*
 * CTree.cpp
 * $Id: CTree.cpp,v 1.6 2001/11/23 02:03:35 mjanich Exp $
 *
 * Copyright (C) 2001 Markus Janich
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * As a special exception to the GPL, the QGLViewer authors (Markus
 * Janich, Michael Meissner, Richard Guenther, Alexander Buck and Thomas
 * Woerner) give permission to link this program with Qt (non-)commercial
 * edition, and distribute the resulting executable, without including
 * the source code for the Qt (non-)commercial edition in the source
 * distribution.
 *
 */

    
// System
///////////
#include <stdlib.h>  // needed for 'exit()'


// Own
////////
#include "CTree.h"
   



// Function   : ~CTreeNode
// Parameters : 
// Purpose    : 
// Comments   : 
CTreeNode::~CTreeNode()
  /**************************************************************************************/
{
#ifdef DEBUG_TREE
  cerr << "called CTreeNode<NodeDataType>::~CTreeNode()" << endl;
#endif
}



// Function   : CTreeNode
// Parameters : const CTreeNode &cSource
// Purpose    : 
// Comments   : 
CTreeNode::CTreeNode(const CTreeNode &cSource)
  /**************************************************************************************/
{
  m_pcParent = cSource.m_pcParent;
  m_cChildrenList = cSource.m_cChildrenList;
}



// Function   : insert
// Parameters : CTreeNode *pcWhere,
//              CTreeNode *pcInsert
// Purpose    : 
// Comments   :
CTreeNode *CTreeNode::insert(CTreeNode *pcWhere, CTreeNode *pcInsert)
  /**************************************************************************************/
{
  CTreeNode *pcOldParent;

  pcOldParent = pcWhere->m_pcParent;
  // remove old node from children list of its parent node
  pcOldParent->m_cChildrenList.remove(pcWhere);

  // append old node to children list of new node
  pcInsert->m_cChildrenList.insertAsLast(pcWhere);      

  // add new node to children list of old parent
  pcOldParent->m_cChildrenList.insertAsLast(pcInsert);

  // set parent of new node to the old parent
  pcInsert->m_pcParent = pcOldParent;  
   
  // set parent of old node to the new node
  pcWhere->m_pcParent = pcInsert;       

  return pcOldParent;
}



// Function   : remove
// Parameters : CTreeNode *pcRemove
// Purpose    : 
// Comments   : 
void CTreeNode::remove(CTreeNode *pcRemove)
  /**************************************************************************************/
{
  if (pcRemove->m_pcParent) { // not a root node in a tree
    // delete the removing node from the parent's list
    pcRemove->m_pcParent->m_cChildrenList.remove(pcRemove);

    // add children of the removing node to the parent's list
    CListContainer<CTreeNode> *pIterator = pcRemove->m_cChildrenList.getFirst();
    while (pIterator) {
      pcRemove->m_pcParent->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator->getObject()->m_pcParent = pcRemove->m_pcParent;
      pIterator = pIterator->getNext();
    }
  }
  else {
    // make first child node to the new root
    CListContainer<CTreeNode> *pIterator = pcRemove->m_cChildrenList.getFirst();
    CTreeNode *pcParent = pIterator->getObject();
    pcParent->m_pcParent = NULL;
    pIterator = pIterator->getNext();
    
    // append other children to new root
    while (pIterator) {
      pIterator->getObject()->m_pcParent = pcParent;
      pcParent->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator = pIterator->getNext();
    }    
  }

  // delete removing  node
  pcRemove->m_cChildrenList.clear();
}



// Function   : remove
// Parameters : CTreeTraverserBase *pcTraverser
// Purpose    : Removes the node which the iterater points to.
// Comments   : 
void CTreeNode::remove(CTreeTraverserBase *pcTraverser)
  /**************************************************************************************/
{
  // remove node from the tree AND from the traverser
  CTreeNode *pcParent = pcTraverser->getCurrentNode()->m_pcParent;

  if (pcParent) { // not root node
    // delete the removing node from the parent's list
    pcParent->m_cChildrenList.remove(pcTraverser->getCurrentNode());

    // add children of the removing node to the parent's list
    CListContainer<CTreeNode> *pIterator = pcTraverser->getCurrentNode()->m_cChildrenList.getFirst();
    while (pIterator) {
      pcParent->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator->getObject()->m_pcParent = pcParent;
      pIterator = pIterator->getNext();
    }
  }
  else {
    // make first child node to the new root
    CListContainer<CTreeNode> *pIterator = pcTraverser->getCurrentNode()->m_cChildrenList.getFirst();
    pcParent = pIterator->getObject();
    pcParent->m_pcParent = NULL;
    pIterator = pIterator->getNext();
    
    // append other children to new root
    while (pIterator) {
      pIterator->getObject()->m_pcParent = pcParent;
      pcParent->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator = pIterator->getNext();
    }    
  }

  // delete removing  node
  pcTraverser->getCurrentNode()->m_cChildrenList.clear();
  pcTraverser->removeCurrentNode();

  return;
}



// Function   : replace
// Parameters : CTreeNode *pcReplace, CTreeNode *pcWith
// Purpose    : 
// Comments   : 
void CTreeNode::replace(CTreeNode *pcReplace, CTreeNode *pcWith)
/**************************************************************************************/
{
  if (pcReplace->m_pcParent) { // not a root node in a tree
    // delete the removing node from the parent's list
    // and append the new one
    pcReplace->m_pcParent->m_cChildrenList.remove(pcReplace);
    pcReplace->m_pcParent->m_cChildrenList.insertAsLast(pcWith);
    pcWith->m_pcParent = pcReplace->m_pcParent;

    // add children of the removing node to the list of the new node
    CListContainer<CTreeNode> *pIterator = pcReplace->m_cChildrenList.getFirst();
    while (pIterator) {
      pcWith->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator->getObject()->m_pcParent = pcWith;
      pIterator = pIterator->getNext();
    }
  }
  else {  // make replacing node to the new root
    // append other children to new root
    CListContainer<CTreeNode> *pIterator = pcReplace->m_cChildrenList.getFirst();
    while (pIterator) {
      pIterator->getObject()->m_pcParent = pcWith;
      pcWith->m_cChildrenList.insertAsLast(pIterator->getObject());
      pIterator = pIterator->getNext();
    }    
  }

  // delete removing node
  pcReplace->m_cChildrenList.clear();
  delete pcReplace;
}



// Function   : operator=
// Parameters : const CTreeNode<NodeDataType> &cSource
// Purpose    : 
// Comments   : 
CTreeNode &CTreeNode::operator=(const CTreeNode &cSource)
/**************************************************************************************/
{
  if (this == &cSource)
    return *this;

#ifdef DEBUG_TREE
  cerr << "called CTreeNode::operator=(...)" << endl;
#endif

  m_pcParent = cSource.m_pcParent;
  m_cChildrenList = cSource.m_cChildrenList;

  return *this;
}



// Function   : operator[]
// Parameters : int i
// Purpose    : 
// Comments   : 
CTreeNode &CTreeNode::operator[](int i) const
  /**************************************************************************************/
{
#ifdef DEBUG
  if (i<0 || i>=numChildren())
    cerr << "WARNING: Index out of Range in CTreeNode::operator[](int)" << endl;
#endif

  i = i<0 ? 0 : i;
  i = i>=numChildren() ? numChildren()-1 : i;

  if (i<0) {
    cout << "ERROR: Direct access to non existing child "
	 << "no. in CTreeNode::operator[](int)" << endl;
    exit(17);
  }

  return m_cChildrenList[i];
}



// Function   : isEqual
// Parameters : const CTreeNode &cNode
// Purpose    : 
// Comments   : 
bool CTreeNode::isEqual(const CTreeNode *pcNode) const
  /**************************************************************************************/
{
  if (pcNode->numChildren() != numChildren())
    return false;

  bool fEqual = true;
  CListContainer<CTreeNode> *pIterator1 = pcNode->m_cChildrenList.getFirst();
  CListContainer<CTreeNode> *pIterator2 = m_cChildrenList.getFirst();

  while (pIterator1 && fEqual) {
    fEqual = (pIterator1->getObject() == pIterator2->getObject());
    pIterator1 = pIterator1->getNext();
    pIterator2 = pIterator2->getNext();
  }

  return ((m_pcParent == pcNode->m_pcParent) && fEqual);
}



// Function   : operator<<
// Parameters : ostream &out,const CTreeNode *pcTreeNode
// Purpose    : 
// Comments   : 
ostream &operator<<(ostream &out, CTreeNode *pcTreeNode)
  /**************************************************************************************/
{
  pcTreeNode->print(out);

  return out;
}



// Function   : print
// Parameters : ostream &out
// Purpose    : 
// Comments   : 
void CTreeNode::print(ostream &out) const
  /**************************************************************************************/
{
  out << "No Data";
}



// Function   : printTree
// Parameters : ostream &out
// Purpose    : 
// Comments   : 
void CTreeNode::printTree(ostream &out) const
  /**************************************************************************************/
{
  int i, count;
  CList<CTreeNode> cTmpList;  // temp FIFO queue
  CListContainer<CTreeNode> *pIterator;

  print(out);
  out << endl;
  for (i=0; i<numChildren(); ++i) {
    cTmpList.insertAsLast(&m_cChildrenList[i]);
  }
  count = cTmpList.getNumObjects();

  while (cTmpList.getNumObjects() != 0) {
    pIterator = cTmpList.getFirst();

    // print data of current node
    pIterator->getObject()->print(out);
    out << " ";

    // add children of current node to FIFO queue
    for (i=0; i<pIterator->getObject()->numChildren(); ++i) {
      cTmpList.insertAsLast(&pIterator->getObject()->m_cChildrenList[i]);
    }

    // remove current node from queue
    cTmpList.remove(pIterator);
    if (--count == 0) {
      count = cTmpList.getNumObjects();
      out << endl;
    }
  }
}


////////////////////////////////////////////////////////////////////////////////////////



// Function   : CDepthFirstTraverser
// Parameters : const CTreeNode<NodeDataType> &cNode
// Purpose    : constructor
// Comments   : 
CDepthFirstTraverser::CDepthFirstTraverser(CTreeNode *pcNode)
  /**************************************************************************************/
{
  parseSubTree(pcNode);
  m_pcCurrentNode = m_cNodeList.getFirst();

  m_fAtStart = true;
  m_fAtEnd = false;
  m_nLastOp = -1;
}



// Function   : parseSubTree
// Parameters : CTreeNode *pcNode
// Purpose    : 
// Comments   : 
void CDepthFirstTraverser::parseSubTree(CTreeNode *pcNode)
  /**************************************************************************************/
{
  // Make a list of the tree nodes
  CListContainer<CTreeNode> *pIterator;

  m_cNodeList.insertAsLast(pcNode);
  pIterator = pcNode->getChildrenList().getFirst();
  while (pIterator) {
    parseSubTree(pIterator->getObject());
    pIterator = pIterator->getNext();
  }
}



// Function   : atStart
// Parameters : 
// Purpose    : 
// Comments   : 
bool CDepthFirstTraverser::atStart()
  /**************************************************************************************/
{
  return m_fAtStart;
}



// Function   : atEnd
// Parameters : 
// Purpose    : 
// Comments   : 
bool CDepthFirstTraverser::atEnd()
  /**************************************************************************************/
{
  return m_fAtEnd;
}



// Function   : operator++
// Parameters : 
// Purpose    : 
// Comments   : 
const CTreeNode *CDepthFirstTraverser::operator++()
  /**************************************************************************************/
{
  m_nLastOp = 0;
  if (m_pcCurrentNode->getNext()==0) {
    m_fAtEnd = true;
    return NULL;
  }

  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  m_fAtStart = false;
  m_pcCurrentNode = m_pcCurrentNode->getNext();
  
  return pTmp->getObject();
}



// Function   : operator++
// Parameters : int dummy
// Purpose    : 
// Comments   : 
const CTreeNode *CDepthFirstTraverser::operator++(int dummy)
  /**************************************************************************************/
{
  m_nLastOp = 0;
  if (m_pcCurrentNode->getNext()==0) {
    m_fAtEnd = true;
    return NULL;
  }

  m_fAtStart = false;
  m_pcCurrentNode = m_pcCurrentNode->getNext();

  return m_pcCurrentNode->getObject();
}


#if 0  // FIXME:
// Function   : operator--
// Parameters : 
// Purpose    : 
// Comments   : 
const CTreeNode *CDepthFirstTraverser::operator--()
  /**************************************************************************************/
{
  m_nLastOp = 1;
  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  m_pcNextNode = m_pcCurrentNode;
  m_pcCurrentNode = m_pcCurrentNode->getPrev();
  m_pcPrevNode = m_pcCurrentNode->getPrev();;
  
  return pTmp->getObject();
}



// Function   : operator--
// Parameters : int dummy
// Purpose    : 
// Comments   : 
const CTreeNode *CDepthFirstTraverser::operator--(int dummy)
  /**************************************************************************************/
{
  m_nLastOp = 1;
  m_pcNextNode = m_pcCurrentNode;
  m_pcCurrentNode = m_pcCurrentNode->getPrev();
  m_pcPrevNode = m_pcCurrentNode->getPrev();;

  return m_pcCurrentNode->getObject();
}
#endif


// Function   : getCurrentNode
// Parameters : 
// Purpose    : 
// Comments   : 
CTreeNode *CDepthFirstTraverser::getCurrentNode() const
  /**************************************************************************************/
{
  return m_pcCurrentNode->getObject();
}



// Function   : removeCurrentNode
// Parameters : 
// Purpose    : 
// Comments   : 
void CDepthFirstTraverser::removeCurrentNode()
  /**************************************************************************************/
{
  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  switch (m_nLastOp) {
  case 0: // operator++
    if (m_pcCurrentNode->getPrev())
      m_pcCurrentNode = m_pcCurrentNode->getPrev();
    else if (m_pcCurrentNode->getNext())
      m_pcCurrentNode = m_pcCurrentNode->getNext();
    else {
      m_pcCurrentNode = 0;
      m_fAtStart = m_fAtEnd = true;
    }
    break;
  case 1: // operator--
    if (m_pcCurrentNode->getNext())
      m_pcCurrentNode = m_pcCurrentNode->getNext();
    else if (m_pcCurrentNode->getPrev())
      m_pcCurrentNode = m_pcCurrentNode->getPrev();
    else {
      m_pcCurrentNode = 0;
      m_fAtStart = m_fAtEnd = true;
    }
    break;
  default:
    break;
  }
  
  m_cNodeList.remove(pTmp);
}



// Function   : CBreathFirstTraverser
// Parameters : const CTreeNode *pcNode
// Purpose    : 
// Comments   : 
CBreathFirstTraverser::CBreathFirstTraverser(CTreeNode *pcNode)
  /**************************************************************************************/
{
  // Make a list of the tree nodes
  int i;
  CListContainer<CTreeNode> *pIterator;

  m_cNodeList.insertAsLast(pcNode);
  m_pcCurrentNode = pIterator = m_cNodeList.getFirst();
  while (pIterator) {
    // add children of current node to list
    for (i=0; i<pIterator->getObject()->numChildren(); ++i) {
      m_cNodeList.insertAsLast(&(*pIterator->getObject())[i]);
    }
    pIterator = pIterator->getNext();
  }

  m_fAtStart = true;
  m_fAtEnd = false;
  m_nLastOp = -1;
}



// Function   : 
// Parameters : 
// Purpose    : 
// Comments   : 
bool CBreathFirstTraverser::atStart()
  /**************************************************************************************/
{
  return m_fAtStart;
}



// Function   : 
// Parameters : 
// Purpose    : 
// Comments   : 
bool CBreathFirstTraverser::atEnd()
  /**************************************************************************************/
{
  return m_fAtEnd;
}



// Function   : operator++
// Parameters : 
// Purpose    : 
// Comments   : 
const CTreeNode *CBreathFirstTraverser::operator++()
  /**************************************************************************************/
{
  m_nLastOp = 0;
  if (m_pcCurrentNode->getNext()==0) {
    m_fAtEnd = true;
    return 0;
  }

  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  m_fAtStart = false;
  m_pcCurrentNode = m_pcCurrentNode->getNext();

  return pTmp->getObject();
}



// Function   : operator++
// Parameters : int dummy
// Purpose    : 
// Comments   : 
const CTreeNode *CBreathFirstTraverser::operator++(int dummy)
  /**************************************************************************************/
{
  m_nLastOp = 0;
  if (m_pcCurrentNode->getNext()==0) {
    m_fAtEnd = true;
    return 0;
  }

  m_fAtStart = false;
  m_pcCurrentNode = m_pcCurrentNode->getNext();

  return m_pcCurrentNode->getObject();
}



#if 0 /// FIXME:
// Function   : operator--
// Parameters : 
// Purpose    : 
// Comments   : 
const CTreeNode *CBreathFirstTraverser::operator--()
  /**************************************************************************************/
{
  m_nLastOp = 1;
  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  m_pcNextNode = m_pcCurrentNode;
  m_pcCurrentNode = m_pcCurrentNode->getPrev();
  m_pcPrevNode = m_pcCurrentNode->getPrev();;

  return pTmp->getObject();
}



// Function   : operator--
// Parameters : int dummy
// Purpose    : 
// Comments   : 
const CTreeNode *CBreathFirstTraverser::operator--(int dummy)
  /**************************************************************************************/
{
  m_nLastOp = 1;
  m_pcNextNode = m_pcCurrentNode;
  m_pcCurrentNode = m_pcCurrentNode->getPrev();
  m_pcPrevNode = m_pcCurrentNode->getPrev();;

  return m_pcCurrentNode->getObject();
}
#endif


// Function   : getCurrentNode
// Parameters : 
// Purpose    : 
// Comments   : 
CTreeNode *CBreathFirstTraverser::getCurrentNode() const
  /**************************************************************************************/
{
  return m_pcCurrentNode->getObject();
}



// Function   : removeCurrentNode
// Parameters : 
// Purpose    : 
// Comments   : 
void CBreathFirstTraverser::removeCurrentNode()
  /**************************************************************************************/
{
  CListContainer<CTreeNode> *pTmp = m_pcCurrentNode;

  switch (m_nLastOp) {
  case 0: // operator++
    if (m_pcCurrentNode->getPrev())
      m_pcCurrentNode = m_pcCurrentNode->getPrev();
    else if (m_pcCurrentNode->getNext())
      m_pcCurrentNode = m_pcCurrentNode->getNext();
    else {
      m_pcCurrentNode = 0;
      m_fAtStart = m_fAtEnd = true;
    }
    break;
  case 1: // operator--
    if (m_pcCurrentNode->getNext())
      m_pcCurrentNode = m_pcCurrentNode->getNext();
    else if (m_pcCurrentNode->getPrev())
      m_pcCurrentNode = m_pcCurrentNode->getPrev();
    else {
      m_pcCurrentNode = 0;
      m_fAtStart = m_fAtEnd = true;
    }
    break;
  default:
    break;
  }
  
  m_cNodeList.remove(pTmp);
}