PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmtbtree.cc

Text File | 1994-09-06 | 19.1 KB | 642 lines

// CmTBTree.cc
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// BTree template implementation.
// -----------------------------------------------------------------


// "CmTBTree" is the default tree constructor.
//
template <class T> CmTBTree<T>::CmTBTree(unsigned ordr)
{
  _order = (ordr >= 3) ? ordr : 3;
  _root  = NULL;
}


// "CmTBTree" is the tree copy constructor.
//
template <class T> CmTBTree<T>::CmTBTree(const CmTBTree<T>& Tr)
                              : CmTContainer<T>(Tr)
{
  _order = Tr._order;
  _root  = NULL;
  copy(Tr);
}


// "~CmTBTree" is the tree destructor.
//
template <class T> CmTBTree<T>::~CmTBTree()
{
  removeAll();
}


// "=" assignment operator copies the specified tree into this tree.
//
template <class T> CmTBTree<T>& CmTBTree<T>::operator=(const CmTBTree<T>& Tr)
{
  if (&Tr != this)
  {
    removeAll();
    _order = Tr._order;
    copy(Tr);
  }
  return *this;
}


// "order" returns the tree order.
//
template <class T> unsigned CmTBTree<T>::order() const
{
  return _order;
}


// "height" returns the current tree height.
//
template <class T> unsigned CmTBTree<T>::height() const
{
  CmTBTreeNode<T> *rover = _root;
  unsigned         ht    = 0;
  while (rover)
  {
    ht++;
    rover = rover->_children[0];
  }
  return ht;
}


// "add" adds a new item to this tree.
//
template <class T> Bool CmTBTree<T>::add(const T& rObj)
{
  T                data  = rObj;             // Initialize data object.
  CmTBTreeNode<T> *child = NULL;             // Initialize child.
  CmTBTreeNode<T> *rover = nodeSearch(rObj); // Find node to insert into.
  Bool             done  = FALSE;            // Loop flag.

  while (rover && !done)                     // Loop.
  {
    int idx = rover->shouldGo(data);         // Get position for new object.
    rover->addAt(idx, data, child, 1);       // Add new data and child to node.
    if (rover->_total <= _order-1)           // Data fits so exit.
      done = TRUE;
    else
    {
      data = rover->_data[(rover->_total) / 2];         // Data doesn't fit.
      CmTBTreeNode<T> *newRight = rover->split(_order); // Split the node.
      if (!newRight) return FALSE;                      // Split unsuccessful.
      child = newRight;                                 // Set new child right.
      rover = rover->_parent;                           // Move to parent.
    }
  }

  if (!done)                                    // Not done, create a
  {                                             // new root.
    CmTBTreeNode<T> *newRoot  = new CmTBTreeNode<T>(NULL, _order);
    newRoot->_children[0] = _root;              // Old root is child of new.
    newRoot->_children[1] = child;              // Stray child is also child.
    newRoot->_data    [0] = data;               // Data is lone root object.
    newRoot->_total       = 1;                  // New root contains 1.

    if (_root)                                  // Set parentage of children
    {                                           // if not first time in.
      child->_parent = newRoot;
     _root->_parent  = newRoot;
    }
    _root = newRoot;                            // New root is now root.
  }
  _size++;                                      // Bump size and split.
  return TRUE;
}


// "remove" removes an item equal to the specified item from the tree.
//
template <class T> Bool CmTBTree<T>::remove(const T& rObj)
{
  CmTBTreeNode<T> *node = lookupNode(rObj);     // Find node where object is.
  if (!node) return FALSE;                      // No object, exit.

  int idx = node->index(rObj);                  // Get index of object in node.
  if (idx == -1) return FALSE;                  // No object, exit.
  _size--;                                      // Decrement size.

  if (node->_children[0])                       // If node is not leaf, swap
  {                                             // object with object at left
    CmTBTreeNode<T> *rover = node->_children[idx+1];  // most side of right.
    while (rover->_children[0]) rover = rover->_children[0];
    node->_data[idx] = rover->_data[0];
    node = rover;
    idx  = 0;
  }

  node->removeAt(idx);                         // Remove object from node.
  unsigned minkeys = minKeys(_order);          // Save min allowable keys.

  while (node != _root && node->_total < minkeys)  // Start looping if number
  {                                                // of keys fell below min.
    int nodeIdx = node->_parent->index(node);  // Save index of node in parent.
    if (nodeIdx == -1) return FALSE;

    if (node->_parent->_children[nodeIdx+1])   // If node has a right sibling,
    {
      CmTBTreeNode<T> *sib = node->_parent->_children[nodeIdx+1];
      CmTBTreeNode<T> *par = node->_parent;

      // If the right sibling has keys to spare, move the left most key in
      // the right sibling up to the parent.  Take the parent key parenting
      // this node and move that key into this node.  Exit.
      if (sib->_total > minkeys)
      {
        node->addAt(node->_total, par->_data[nodeIdx], sib->_children[0], 1);
        if (sib->_children[0]) sib->_children[0]->_parent = node;
        par->_data[nodeIdx] = sib->_data[0];
        sib->removeAt(0);
        return TRUE;
      }

      // The right sibling has no keys to spare, so we need to combine the
      // remaining keys in this node with the parent key parenting this node
      // and the keys of the right sibling to form one node.
      node->addAt(node->_total, par->_data[nodeIdx], sib->_children[0], 1);
      for (int ii = 0; ii < sib->_total; ii++)
      {
        node->addAt(node->_total, sib->_data[ii], sib->_children[ii+1], 1);
        if (sib->_children[ii+1]) sib->_children[ii+1]->_parent = node;
      }
      delete sib;
      par->removeAt(nodeIdx);
      node = par;
    }

    else if (node->_parent->_children[nodeIdx-1]) // If node has left sibling,
    {
      CmTBTreeNode<T> *sib = node->_parent->_children[nodeIdx-1];
      CmTBTreeNode<T> *par = node->_parent;

      // If the left sibling has keys to spare, move the right most key in
      // the left sibling up to the parent.  Take the parent key parenting
      // the left sibling and move that key into this node.  Exit.
      if (sib->_total > minkeys)
      {
        node->addAt(0, par->_data[nodeIdx-1], sib->_children[sib->_total], 0);
        if (sib->_children[sib->_total])
          sib->_children[sib->_total]->_parent = node;
        par->_data[nodeIdx-1] = sib->_data[sib->_total-1];
        sib->removeAt(sib->_total-1);
        return TRUE;
      }

      // The left sibling has no keys to spare, so we need to combine the
      // keys in the left sibling with the parent key parenting the left
      // sibling and the keys of this node to form one node.
      sib->addAt(sib->_total, par->_data[nodeIdx-1], node->_children[0], 1);
      for (int ii = 0; ii < node->_total; ii++)
      {
        sib->addAt(sib->_total, node->_data[ii], node->_children[ii+1], 1);
        if (node->_children[ii+1]) node->_children[ii+1]->_parent = sib;
      }
      delete node;
      par->removeAt(nodeIdx-1);
      node = par;
    }
  }

  if (node->_total == 0)                // If only the root node is left,
  {                                     // and it has no keys, then delete
    CmTBTreeNode<T> *temp = _root;      // delete the root node and make
    _root = _root->_children[0];        // it's left most child the new
    delete temp;                        // root node.
  }
  if (_root && _root->_parent) _root->_parent = NULL;
  return TRUE;
}


// "lookup" returns an item equal to the specified item in the tree.
//
template <class T> const T& CmTBTree<T>::lookup(const T& rObj) const
{
  if (!_root) return _error;                // Empty tree.

  CmTBTreeNode<T> *node = lookupNode(rObj); // Find node where object is.
  if (!node) return _error;

  int idx = node->index(rObj);
  return (idx == -1) ? _error : node->_data[idx];
}


// "contains" checks if the tree contains any items equal to the
// specified item.
//
template <class T> Bool CmTBTree<T>::contains(const T& rObj) const
{
  if (!_root) return NULL;                  // Empty tree.

  CmTBTreeNode<T> *node = lookupNode(rObj); // Find node where object is.
  if (!node) return FALSE;

  int idx = node->index(rObj);
  return (idx != -1) ? TRUE : FALSE;
}


// "occurrences" counts the number of items equal to the specified
// item in the tree.
//
template <class T> unsigned CmTBTree<T>::occurrences(const T& rObj) const
{
  unsigned            occur = 0;
  CmTBTreeIterator<T> iterator(*this);
  while (!iterator.done())
    if (rObj == iterator.next()) occur++;
  return occur;
}


// "removeAll" removes all items from the tree.
//
template <class T> void CmTBTree<T>::removeAll()
{
  removeNodes(_root);
  _root = NULL;
  _size = 0;
}


// "newIterator" creates and returns a tree iterator.
//
template <class T> CmTIterator<T>* CmTBTree<T>::newIterator() const
{
  return new CmTBTreeIterator<T>(*this);
}


// "nodeSearch" returns the node where the specified item should be
// inserted.
//
template <class T>
CmTBTreeNode<T>* CmTBTree<T>::nodeSearch(const T& rObj) const
{
  CmTBTreeNode<T> *rover = _root;
  CmTBTreeNode<T> *found = NULL;

  while (rover && !found)
  {
    int idx = rover->shouldGo(rObj);
    if (rover->_children[idx]) rover = rover->_children[idx];
    else                       found = rover;
  }
  return found;
}


// "lookupNode" returns the node where the specified item is located.
//
template <class T>
CmTBTreeNode<T>* CmTBTree<T>::lookupNode(const T& rObj) const
{
  if (!_root) return NULL;

  CmTBTreeNode<T> *rover = _root;         // Start at root node.
  CmTBTreeNode<T> *ret   = NULL;
  while (rover && !ret)
  {
    int idx = rover->index(rObj);         // Is object in node?
    if (idx != -1)
      ret = rover;                        // Yes.
    else
    {
      idx   = rover->shouldGo(rObj);      // No.  Set node to point to
      rover = rover->_children[idx];      // child where object would be.
    }
  }
  return ret;
}


// "removeNodes" removes all the child nodes from the specified node.
//
template <class T> void CmTBTree<T>::removeNodes(CmTBTreeNode<T>* pNode)
{
  if (pNode)
  {
    for (int ii = 0; ii < pNode->_total; ii++)
      removeNodes(pNode->_children[ii]);
    removeNodes(pNode->_children[pNode->_total]);
    delete pNode;
  }
}


// "minKeys" returns the minimum number of items that a non-root node
// can contain.
//
template <class T> unsigned CmTBTree<T>::minKeys(unsigned ordr)
{
  return (((ordr / 2) * 2) == ordr) ? (ordr / 2) - 1 : (ordr / 2);
}


// "CmTBTreeNode" is the node constructor.
//
template <class T>
CmTBTreeNode<T>::CmTBTreeNode(CmTBTreeNode<T>* parent, unsigned order)
{
  _total    = 0;
  _parent   = parent;
  _data     = new T[order];
  _children = new CmTBTreeNode<T>*[order+1];
  if (_data && _children) clear(order);
}


// "~CmTBTreeNode" is the node destructor.
//
template <class T> CmTBTreeNode<T>::~CmTBTreeNode()
{
  delete[] _data;
  delete[] _children;
}


// "shouldGo" returns the index where the specified object should
// be inserted in the data list.
//
template <class T> int CmTBTreeNode<T>::shouldGo(const T& rObj)
{
  if (_total == 0) return 0;

  if (rObj <  _data[0])        return 0;
  if (rObj >= _data[_total-1]) return _total;

  int idx = -1, ii = _total - 1;
  while (ii >= 0 && idx == -1)
    if (rObj >= _data[ii--]) idx = ii+2;
  return idx;
}


// "index" returns the index of the specified item in the data list.
//
template <class T> int CmTBTreeNode<T>::index(const T& rObj)
{
  if (_total == 0) return -1;
  int idx = -1, ii = 0;
  while (ii < _total && idx == -1)
    if (rObj == _data[ii++]) idx = ii-1;
  return idx;
}


// "index" returns the index of the specified node in the child list.
//
template <class T> int CmTBTreeNode<T>::index(CmTBTreeNode<T>* pNode)
{
  if (_total == 0 || !pNode) return -1;
  int idx = -1, ii = 0;
  while (ii <= _total && idx == -1)
    if (pNode == _children[ii++]) idx = ii-1;
  return idx;
}


// "addAt" adds the specified item/child pair at the specified index.
//
template <class T>
Bool CmTBTreeNode<T>::addAt(int idx, const T& rObj, CmTBTreeNode<T>* pNode,
                            int offset)
{
  if (offset == 0) _children[_total+1] = _children[_total];
  for (int ii = _total; ii > idx; ii--)     // Slide other stuff to make
  {                                         // room.
    _data    [ii       ] = _data    [ii-1];
    _children[ii+offset] = _children[ii+offset-1];
  }

  _data    [idx       ] = rObj;             // Insert object and child.
  _children[idx+offset] = pNode;
  _total++;
  return TRUE;
}


// "removeAt" removes the item/child pairs at the specified index.
//
template <class T> Bool CmTBTreeNode<T>::removeAt(int idx)
{
  if (idx < 0 || idx >= _total) return FALSE;

  for (int ii = idx; ii < _total-1; ii++)
  {
    _data    [ii  ] = _data    [ii+1];
    _children[ii+1] = _children[ii+2];
  }
  _children[_total  ] = NULL;
  _total--;
  return TRUE;
}


// "clear" nulls out all the child pointers in the node.
//
template <class T> void CmTBTreeNode<T>::clear(int order)
{
  for (int ii = 0; ii <= order; ii++)
    _children[ii] = NULL;
}


// "split" splits the node returning the new right node.
//
template <class T> CmTBTreeNode<T>* CmTBTreeNode<T>::split(unsigned ordr)
{
  CmTBTreeNode<T> *newRight = new CmTBTreeNode<T>(_parent, ordr);
  if (!newRight) return NULL;

  int ix = 0, midIdx = _total / 2;
  for (int ii = midIdx+1; ii <= _total; ii++, ix++)
  {
    if (ii != _total)
    {
      newRight->_data[ix] = _data[ii];
      newRight->_total++;
    }
    newRight->_children[ix] = _children[ii];
    _children[ii] = NULL;
    if (newRight->_children[ix]) newRight->_children[ix]->_parent = newRight;
  }
  _total = midIdx;
  return newRight;
}


// "CmTBTreeIterator" is the iterator constructor.
//
template <class T> CmTBTreeIterator<T>::CmTBTreeIterator(const CmTBTree<T> &Tr)
                                       : _tree(Tr)
{
  _node  = _tree._root;
  _index = 0;
  if (_node)                                 // Descend all the way down left.
    while (_node->_children[0])
      _node = _node->_children[0];
}


// "done" checks if the iterator is at the end of the tree.
//
template <class T> Bool CmTBTreeIterator<T>::done() const
{
  return (!_node);
}


// "next" returns the current item and advances the iterator.
//
template <class T> const T& CmTBTreeIterator<T>::next()
{
  const T& retValue = current();              // Save current item.

  if (_node->_children[_index+1])             // Traverse all the way down
  {                                           // the left part of the next
    _node = _node->_children[_index+1];       // child branch.
    while (_node->_children[0])
      _node = _node->_children[0];
    _index = 0;
    return retValue;
  }

  if (_index < _node->_total-1)               // No child branches, but there
  {                                           // are still objects in this
    _index++;                                 // node so bump the index and
    return retValue;                          // exit.
  }

  Bool done = FALSE;                          // Need to back up the tree.
  while (!done)
  {
    if (!_node->_parent)                      // If node has no parent, we
    {                                         // are done iterating.
      _node = NULL;
      done  = TRUE;
    }

    else                                      // Node has parent.
    {
      int idx = _node->_parent->index(_node); // What branch were we just in.
      if (idx == -1)                          // Error! - shouldn't happen.
      {
        _node = NULL;
        done  = TRUE;
      }
      else                                    // Got the branch.
      {
        _node = _node->_parent;               // Move up to parent.
        if (idx < _node->_total)              // If not end of data list,
        {                                     // bump index and exit.
          _index = idx;
          done = TRUE;
        }
      }
    }
  }
  return retValue;                            // Return the object.
}


// "previous" backs the iterator up one item and returns that item.
//
template <class T> const T& CmTBTreeIterator<T>::previous()
{
  const T& retValue = current();              // Save current item.

  if (_node->_children[_index])               // Traverse all the way down
  {                                           // the right part of the
    _node = _node->_children[_index];         // previous child branch.
    while (_node->_total && _node->_children[_node->_total-1])
      _node = _node->_children[_node->_total];
    _index = _node->_total-1;
    return retValue;
  }

  if (_index > 0)                             // No child branches, but there
  {                                           // are still objects in this
    _index--;                                 // node so decrement the index
    return retValue;                          // and exit.
  }

  Bool done = FALSE;                          // Need to back up the tree.
  while (!done)
  {
    if (!_node->_parent)                      // If node has no parent, we
    {                                         // are done iterating.
      _node = NULL;
      done  = TRUE;
    }

    else                                      // Node has parent.
    {
      int idx = _node->_parent->index(_node); // What brach were we just in?
      if (idx == -1)                          // Error! - shouldn't happen.
      {
        _node = NULL;
        done  = TRUE;
      }
      else                                    // Got the branch.
      {
        _node = _node->_parent;               // Move up to parent.
        if (idx > 0)                          // If not at beginning,
        {                                     // decrement index and exit.
          _index = idx - 1;
          done   = TRUE;
        }
      }
    }
  }
  return retValue;                            // Return the item.
}


// "current" returns the current item.
//
template <class T> const T& CmTBTreeIterator<T>::current() const
{
  return (_node) ? _node->_data[_index] : _tree._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTBTreeIterator<T>::first()
{
  _node  = _tree._root;
  _index = 0;

  if (_node)
    while (_node->_children[0])
      _node = _node->_children[0];
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTBTreeIterator<T>::last()
{
  _node = _tree._root;
  if (_node)
  {
    while (_node->_children[_node->_total])
      _node = _node->_children[_node->_total];
    _index = _node->_total - 1;
  }
}