PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmlist.cpp

C/C++ Source or Header | 1994-09-06 | 7.9 KB | 360 lines

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

#include <cm/include/cmlist.h>


// "CmLinkedList" is the list copy constructor.
//
CmLinkedList::CmLinkedList(const CmLinkedList& Li)
{
  _first = _last = NULL;
  copy(Li);
}


// "~CmLinkedList" is the list destructor.
//
CmLinkedList::~CmLinkedList()
{
  removeAll();
}


// "=" assignment operator copies the contents of the specified list
// into this list.
//
CmLinkedList& CmLinkedList::operator=(const CmLinkedList& Li)
{
  if (&Li != this)
  {
    removeAll();
    copy     (Li);
  }
  return *this;
}


// "[]" indexing operator allows an object to be retrieved from the
// list by index like an array.
//
CmObject* CmLinkedList::operator[](int idx) const
{
  if (idx < 0 || idx >= _size) return NULL;

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


// "add" adds the specified object to the end of this list.
//
Bool CmLinkedList::add(CmObject* pObj)
{
  return append(pObj);
}


// "append" adds the specified object to the end of this list.
//
Bool CmLinkedList::append(CmObject* pObj)
{
  if (!pObj) return FALSE;
  CmLink *newlink = new CmLink(pObj);
  if (!newlink) return FALSE;

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


// "prepend" adds the specified object to the start of this list.
//
Bool CmLinkedList::prepend(CmObject* pObj)
{
  if (!pObj) return FALSE;
  CmLink *newlink = new CmLink(pObj);
  if (!newlink) return FALSE;

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


// "insertAfter" searches for the first occurrence of an object that
// isEqual to the first specified object and inserts the second
// specified object immediately after.
//
Bool CmLinkedList::insertAfter(CmObject* after, CmObject* pObj)
{
  if (!after || !pObj || !_first) return FALSE;

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

  if (!found) return FALSE;

  CmLink *newlink = new CmLink(pObj);
  if (!newlink) return FALSE;
  newlink->_next = rover->_next;
  rover->_next = newlink;
  if (rover == _last) _last = newlink;
  _size++;
  return TRUE;
}


// "insertBefore" searches for the first occurrence of an object that
// isEqual to the first specified object and inserts the second
// specified object immediately before.
//
Bool CmLinkedList::insertBefore(CmObject* before, CmObject* pObj)
{
  if (!before || !pObj || !_first) return FALSE;

  CmLink *rover1 = _first;
  CmLink *rover2 = _first;

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

  if (rover1 == NULL) return FALSE;

  CmLink *newlink = new CmLink(pObj);
  if (rover1 == rover2)
  {
    newlink->_next = _first;
    _first         = newlink;
  }
  else
  {
    newlink->_next = rover2->_next;
    rover2->_next  = newlink;
  }
  _size++;
  return TRUE;
}


// "remove" removes the first occurrence of an object that isEqual
// to the specified object from the list.
//
Bool CmLinkedList::remove(CmObject* pObj)
{
  if (!pObj || !_first) return FALSE;   // Return if no objects.

  if (_first->_data->isEqual(pObj))     // Object to remove is first.
  {
    CmObject* pObj = removeFirst();
    if (!pObj) return FALSE;
    if (ownsObjects()) delete pObj;
    return TRUE;
  }

  CmLink *rover1 = _first;              // Search for object to remove.
  CmLink *rover2 = _first;

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

  if (rover1 == NULL) return FALSE;     // Object was not found.

  if (rover1 == _last)                  // Object was last in list.
  {
    CmObject* pObj = removeLast();
    if (!pObj) return FALSE;
    if (ownsObjects()) delete pObj;
    return TRUE;
  }

  rover2->_next = rover2->_next->_next;     // Remove object from list.

  if (ownsObjects()) delete rover1->_data;  // Delete if object if owned.
  delete rover1;                            // Delete link.
  _size--;
  return TRUE;
}


// "removeFirst" removes the first object from the list.  The object is
// not deleted regardless of the ownership.
//
CmObject* CmLinkedList::removeFirst()
{
  if (!_first) return NULL;

  CmObject *pObj = _first->_data;
  CmLink   *temp = _first;
  _first = _first->_next;
  if (!_first) _last = NULL;
  delete temp;
  _size--;
  return pObj;
}


// "removeLast" removes the last object from the list.  The object is
// not deleted regardless of the ownership.
//
CmObject* CmLinkedList::removeLast()
{
  if (!_last) return NULL;
  if (_last == _first) return removeFirst();

  CmLink *rover = _first;
  while (rover->_next->_next)
    rover = rover->_next;
  CmObject *pObj = rover->_next->_data;
  delete rover->_next;
  _last = rover;
  _last->_next = NULL;
  _size--;
  return pObj;
}


// "lookup" returns the first occurrence of an object which isEqual
// to the specified object.
//
CmObject* CmLinkedList::lookup(CmObject* pObj) const
{
  if (!pObj || !_first) return FALSE;

  CmLink *rover = _first;
  Bool    found = FALSE;
  while (rover && !found)
  {
    if (rover->_data->isEqual(pObj)) found = TRUE;
    else                             rover = rover->_next;
  }
  return (found) ? rover->_data : NULL;
}


// "contains" checks to see if an object that isEqual to the specified
// object exists in the list.
//
Bool CmLinkedList::contains(CmObject* pObj) const
{
  if (!pObj || !_first) return FALSE;

  CmLink *rover = _first;
  Bool    found = FALSE;
  while (rover && !found)
  {
    if (rover->_data->isEqual(pObj)) found = TRUE;
    else                             rover = rover->_next;
  }
  return found;
}


// "occurrences" returns the number of objects in the list
// isEqual to the specified object.
//
unsigned CmLinkedList::occurrences(CmObject* pObj) const
{
  if (!pObj || !_first) return 0;

  CmLink   *rover = _first;
  unsigned  total = 0;
  while (rover)
  {
    if (rover->_data->isEqual(pObj)) total++;
    rover = rover->_next;
  }
  return total;
}


// "removeAll" removes all the objects from the list.
//
void CmLinkedList::removeAll()
{
  CmLink *temp, *rover = _first;
  while (rover)
  {
    temp = rover->_next;
    if (ownsObjects()) delete rover->_data;
    delete rover;
    rover = temp;
  }
  _size  = 0;
  _first = _last = NULL;
}


// "newIterator" creates and returns a list iterator.
//
CmIterator* CmLinkedList::newIterator() const
{
  return new CmLinkedListIterator(*this);
}


// "next" returns the current object in the list and increments the
// iterator to the next link.
//
CmObject* CmLinkedListIterator::next()
{
  if (!_link) return NULL;
  CmObject *rval = _link->_data;
  _link = _link->_next;
  return rval;
}


// "previous" backs the iterator up one object and returns that object.
//
CmObject* CmLinkedListIterator::previous()
{
  if (!_link) return NULL;
  CmObject *rval = _link->_data;
  if (_link == _list._first)
    _link = NULL;
  else
  {
    CmLink *rover = _list._first;
    while (rover && rover->_next != _link)
      rover = rover->_next;
    _link = rover;
  }
  return rval;
}