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

C/C++ Source or Header | 1994-09-06 | 9.1 KB | 401 lines

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


// "CmTLinkedList" is the list copy constructor.
//
template <class T> CmTLinkedList<T>::CmTLinkedList(const CmTLinkedList<T>& L)
                                   : CmTContainer<T>(L)
{
  _first = _last = NULL;
  copy(L);
}


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


// "=" operator copies the contents of the input list into this list.
//
template <class T>
CmTLinkedList<T>& CmTLinkedList<T>::operator=(const CmTLinkedList<T>& L)
{
  if (&L != this)
  {
    removeAll();
    copy     (L);
  }
  return *this;
}


// "[]" indexing operator allows a list item to be accessed via an index.
//
template <class T> const T& CmTLinkedList<T>::operator[](int idx) const
{
  if (idx < 0 || idx >= _size) return _error;

  int         ii    = 0;
  CmTLink<T> *rover = _first;
  while (rover && ii < idx)
  {
    rover = rover->_next;
    ii++;
  }
  return (rover) ? rover->_data : _error;
}


// "add" adds the specified item to the end of this list.
//
template <class T> Bool CmTLinkedList<T>::add(const T& rObj)
{
  return append(rObj);
}


// "append" adds the specified item to the end of this list.
//
template <class T> Bool CmTLinkedList<T>::append(const T& obj)
{
  CmTLink<T> *newlink = new CmTLink<T>(obj);
  if (!newlink) return FALSE;

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


// "prepend" adds the specified item to the beginning of this list.
//
template <class T> Bool CmTLinkedList<T>::prepend(const T& obj)
{
  CmTLink<T> *newlink = new CmTLink<T>(obj);
  if (!newlink) return FALSE;

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


// "insertAfter" searches for the first item equal to the specified
// item in the list and inserts the second item immediately after.
//
template <class T>
Bool CmTLinkedList<T>::insertAfter(const T& after, const T& rObj)
{
  if (!_first) return FALSE;

  CmTLink<T> *rover = _first;
  Bool        found = FALSE;
  while (rover && !found)
  {
    if (rover->_data == after) found = TRUE;
    else                       rover = rover->_next;
  }

  if (!found) return FALSE;

  CmTLink<T> *newlink = new CmTLink<T>(rObj);
  if (!newlink) return FALSE;
  newlink->_next = rover->_next;
  rover->_next   = newlink;
  if (rover == _last) _last = newlink;
  _size++;
  return TRUE;
}


// "insertBefore" searches for the first item equal to the specified
// item in the list and inserts the second item immediately before.
//
template <class T>
Bool CmTLinkedList<T>::insertBefore(const T& before, const T& rObj)
{
  if (!_first) return FALSE;

  CmTLink<T> *rover1 = _first;
  CmTLink<T> *rover2 = _first;

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

  if (rover1 == NULL) return FALSE;

  CmTLink<T> *newlink = new CmTLink<T>(rObj);
  if (rover1 == rover2)
  {
    newlink->_next = _first;
    _first         = newlink;
  }
  else
  {
    newlink->_next = rover2->_next;
    rover2->_next  = newlink;
  }
  _size++;
  return TRUE;
}


// "remove" removes the item equal to the specified item from the list.
//
template <class T> Bool CmTLinkedList<T>::remove(const T& rObj)
{
  if (!_first) return FALSE;                      // Empty list.

  if (_first->_data == rObj)                      // Item to remove is
  {                                               // first in the list.
    removeFirst();
    return TRUE;
  }

  if (_last->_data == rObj)                       // Item to remove is
  {                                               // last in the list.
    removeLast();
    return TRUE;
  }

  CmTLink<T> *rover1 = _first;                   // Search for item to
  CmTLink<T> *rover2 = _first;                   // remove.

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

  if (rover1 == NULL) return FALSE;               // Item was not found.
  rover2->_next = rover2->_next->_next;           // Remove link from list.

  delete rover1;                                  // Delete the link.
  _size--;
  return TRUE;
}


// "removeFirst" removes and returns the first item in the list.
//
template <class T> T CmTLinkedList<T>::removeFirst()
{
  if (!_first) return _error;
  T           ret  = _first->_data;
  CmTLink<T> *temp = _first;
  _first = _first->_next;
  if (!_first) _last = NULL;
  delete temp;
  _size--;
  return ret;
}


// "removeLast" removes and returns the last item in the list.
//
template <class T> T CmTLinkedList<T>::removeLast()
{
  if (!_last) return _error;
  if (_last == _first)
  {
    T ret = _first->_data;
    delete _first;
    _first = _last = NULL;
    _size  = 0;
    return ret;
  }

  CmTLink<T> *rover = _first;
  while (rover->_next->_next)
    rover = rover->_next;
  T ret = rover->_next->_data;
  delete rover->_next;
  _last = rover;
  _last->_next = NULL;
  _size--;
  return ret;
}


// "lookup" searches for the item equal to the specified item in the
// list and returns the first occurrence.
//
template <class T> const T& CmTLinkedList<T>::lookup(const T& rObj) const
{
  CmTLink<T> *rover = _first;
  Bool        found = FALSE;
  while (rover && !found)
  {
    if (rover->_data == rObj) found = TRUE;
    else                      rover = rover->_next;
  }
  return (found) ? rover->_data : _error;
}


// "first" returns a pointer to the first object in the list.
//
template <class T> const T& CmTLinkedList<T>::first() const
{
  return (_first) ? _first->_data : _error;
}


// "last" returns a pointer to the last object in the list.
//
template <class T> const T& CmTLinkedList<T>::last() const
{
  return (_last ) ? _last->_data  : _error;
}


// "contains" checks to see if the item equal to the specified item
// is contained in this list.
//
template <class T> Bool CmTLinkedList<T>::contains(const T& rObj) const
{
  CmTLink<T> *rover = _first;
  Bool        found = FALSE;
  while (rover && !found)
  {
    if (rover->_data == rObj) found = TRUE;
    else                      rover = rover->_next;
  }
  return found;
}


// "occurrences" counts the number of occurrences of the specified item.
//
template <class T> unsigned CmTLinkedList<T>::occurrences(const T& rObj) const
{
  CmTLink<T> *rover = _first;
  unsigned    occur = 0;
  while (rover)
  {
    if (rover->_data == rObj) occur++;
    rover = rover->_next;
  }
  return occur;
}


// "removeAll" clears the contents of this list.
//
template <class T> void CmTLinkedList<T>::removeAll()
{
  CmTLink<T> *temp, *rover = _first;
  while (rover)
  {
    temp = rover->_next;
    delete rover;
    rover = temp;
  }
  _first = _last = NULL;
  _size  = 0;
}


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


// "CmTLinkedListIterator" is the iterator constructor.
//
template <class T>
CmTLinkedListIterator<T>::CmTLinkedListIterator(const CmTLinkedList<T>& L)
                                      : _list(L), _link(L._first)
{}


// "done" returns TRUE if the iterator can advance no further.
//
template <class T> Bool CmTLinkedListIterator<T>::done() const
{
  return (!_link);
}


// "next" returns the current list item and increments the iterator to
// the next item in the list.
//
template <class T> const T& CmTLinkedListIterator<T>::next()
{
  if (!_link) return _list._error;
  CmTLink<T> *temp = _link;
  _link = _link->_next;
  return temp->_data;
}


// "previous" backs the iterator up one object and returns that object.
//
template <class T> const T& CmTLinkedListIterator<T>::previous()
{
  if (!_link) return _list._error;
  CmTLink<T> *temp = _link;
  if (_link == _list._first)
    _link = NULL;
  else
  {
    CmTLink<T> *rover = _list._first;
    while (rover && rover->_next != _link)
      rover = rover->_next;
    _link = rover;
  }
  return temp->_data;
}


// "current" returns the current item in the list.
//
template <class T> const T& CmTLinkedListIterator<T>::current() const
{
  return (_link) ? _link->_data : _list._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTLinkedListIterator<T>::first()
{
  _link = _list._first;
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTLinkedListIterator<T>::last()
{
  _link = _list._last;
}