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

Text File | 1994-09-06 | 5.6 KB | 276 lines

// CmTRing.cc
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Ring (circular linked list) template implementation.
// -----------------------------------------------------------------


// "CmRing" is the ring copy constructor.
//
template <class T> CmTRing<T>::CmTRing(const CmTRing<T>& R)
                             : CmTContainer<T>(R)
{
  _top = _last = NULL;
  copy(R);
}


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


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


// "add" adds the specified item to the top of the ring.
//
template <class T> Bool CmTRing<T>::add(const T& rObj)
{
  CmTRingNode<T> *newnode = new CmTRingNode<T>(rObj);
  if (!newnode) return FALSE;

  if (!_top)
  {
    _top = _last = newnode;
    newnode->_next = _top;
  }
  else
  {
    newnode->_next = _top;
    _top           = newnode;
    _last->_next   = newnode;
  }
  _size++;
  return TRUE;
}


// "remove" removes the first occurrence of an item which is equal to the
// specified item.
//
template <class T> Bool CmTRing<T>::remove(const T& rObj)
{
  if (!_top) return FALSE;

  if (_top->_data == rObj) return removeTop();

  CmTRingNode<T> *rover1 = _top;
  CmTRingNode<T> *rover2 = _top;

  while (rover1 != NULL && rover1->_data != rObj)
  {
    rover2 = rover1;
    rover1 = rover1->_next;
  }

  if (rover1 == NULL) return FALSE;

  if (rover1 == _last) _last = rover2;
  rover2->_next = rover2->_next->_next;

  delete rover1;
  _size--;
  return TRUE;
}


// "removeTop" removes the top item from the ring.
//
template <class T> Bool CmTRing<T>::removeTop()
{
  if (!_top) return FALSE;

  if (_size == 1)
  {
    delete _top;
    _top = _last = NULL;
  }
  else
  {
    CmTRingNode<T> *temp = _top;
    _top = _top->_next;
    _last->_next = _top;
    delete temp;
  }
  _size--;
  return TRUE;
}


// "lookup" returns the first occurrence of an item which is equal to
// the specified item.
//
template <class T> const T& CmTRing<T>::lookup(const T& rObj) const
{
  if (!_top) return _error;
  CmTRingNode<T> *rover = _top;
  CmTRingNode<T> *temp  = NULL;
  int             ii    = 0;
  while (ii < _size && !temp)
  {
    if (rover->_data == rObj)
      temp  = rover;
    else
    {
      rover = rover->_next;
      ii++;
    }
  }
  return (temp) ? temp->_data : _error;
}


// "contains" returns TRUE if the ring contains an item which is equal
// to the specified object.
//
template <class T> Bool CmTRing<T>::contains(const T& rObj) const
{
  if (!_top) return NULL;
  CmTRingNode<T> *rover = _top;
  int             ii    = 0;
  Bool            found = FALSE;
  while (ii < _size && !found)
  {
    if (rover->_data == rObj)
      found = TRUE;
    else
    {
      rover = rover->_next;
      ii++;
    }
  }
  return found;
}


// "occurrences" counts the number of items that are equal to the specified
// item.
//
template <class T> unsigned CmTRing<T>::occurrences(const T& rObj) const
{
  if (!_top) return 0;
  CmTRingNode<T> *rover = _top;
  int             ii    = 0;
  unsigned        occur = 0;
  while (ii < _size)
  {
    if (rover->_data == rObj) occur++;
    rover = rover->_next; ii++;
  }
  return occur;
}


// "removeAll" removes all of the items from the ring.
//
template <class T> void CmTRing<T>::removeAll()
{
  CmTRingNode<T> *rover = _top;
  int             ii    = 0;
  while (ii < _size)
  {
    CmTRingNode<T> *temp = rover->_next;
    delete rover;
    rover = temp;
    ii++;
  }
  _top  = _last = NULL;
  _size = 0;
}


// "top" returns a pointer to the top object in the ring.
//
template <class T> const T& CmTRing<T>::top() const
{
  return (_top) ? _top->_data : _error;
}


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


// "done" checks to see if done iterating.  (Always FALSE for a ring.)
//
template <class T> Bool CmTRingIterator<T>::done() const
{
  return FALSE;
}


// "next" returns the current ring item and advances the iterator
// to the next item.
//
template <class T> const T& CmTRingIterator<T>::next()
{
  if (!_node) return _ring._error;
  CmTRingNode<T> *rval = _node;
  _node = _node->_next;
  return rval->_data;
}


// "previous" backs the iterator up one item and returns that item.
//
template <class T> const T& CmTRingIterator<T>::previous()
{
  if (!_node) return _ring._error;
  const T& rval = _node->_data;

  if (_node == _ring._top)
    _node = _ring._last;
  else
  {
    CmTRingNode<T> *rover = _ring._top;
    while (rover && rover->_next != _node)
      rover = rover->_next;
    _node = rover;
  }
  return rval;
}


// "current" returns the current object in the ring.
//
template <class T> const T& CmTRingIterator<T>::current() const
{
  return (_node) ? _node->_data : _ring._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTRingIterator<T>::first()
{
  _node = _ring._top;
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTRingIterator<T>::last()
{
  _node = _ring._last;
}