Public API Reference

csutil/list.h

Go to the documentation of this file.

/*
    Copyright (C) 2003 by Marten Svanfeldt
    influenced by Aapl by Adrian Thurston <[email protected]>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.
    
    This library 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
    Library General Public License for more details.
    
    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_UTIL_LIST_H__
#define __CS_UTIL_LIST_H__

#include "csextern.h"

template <class T>
class csList
{
protected:
  struct csListElement
  {
    csListElement(const T& d, csListElement* newnext, csListElement* newprev) :
      next(newnext), prev(newprev), data(d) {}

    csListElement* next;

    csListElement* prev;

    T data;
  };

  void Delete (csListElement *el);

public:
  csList() : head(0), tail(0) {}

  csList(const csList<T> &other);

  ~csList()
  { DeleteAll (); }

  class Iterator
  {
  public:
    Iterator() : ptr(0), visited(false), reversed(false)
    { }
    Iterator(const Iterator& r)
    { ptr = r.ptr; visited = r.visited; reversed = r.reversed; }
    Iterator(const csList<T> &list, bool reverse = false) :
      visited(false), reversed(reverse)
    {
      if (reverse) ptr = list.tail;
      else ptr = list.head;
    }
    Iterator& operator= (const Iterator& r)
    { ptr = r.ptr; visited = r.visited; reversed = r.reversed; return *this; }
    bool HasCurrent() const
    { return visited && ptr != 0; }
    bool HasNext() const
    { return ptr && (ptr->next || !visited); }
    bool HasPrevious() const
    { return ptr && (ptr->prev || !visited); }
    bool IsFirst() const
    { return ptr && ptr->prev == 0; }
    bool IsLast() const
    { return ptr && ptr->next == 0; }
    bool IsReverse() const
    { return reversed; }

    operator T*() const
    { return visited && ptr ? &ptr->data : 0; }
    T& operator *() const
    { CS_ASSERT(ptr != 0); return ptr->data; }
    T* operator->() const
    { return visited && ptr ? &ptr->data : 0; }

    void Clear ()
    {
      ptr = 0;
      visited = true;
    }
    T& Next ()
    {
      if (visited && ptr != 0)
        ptr = ptr->next;
      visited = true;
      CS_ASSERT(ptr != 0);
      return ptr->data;
    }
    T& Previous()
    {
      if (visited && ptr != 0)
        ptr = ptr->prev;
      visited = true;
      CS_ASSERT(ptr != 0);
      return ptr->data;
    }
    T& Prev() { return Previous(); } // Backward compatibility.

    Iterator& operator++()
    {
      if (visited && ptr != 0)
        ptr = ptr->next;
      visited = true;
      return *this;
    }
    Iterator& operator--()
    {
      if (visited && ptr != 0)
        ptr = ptr->prev;
      visited = true;
      return *this;
    }

    T& FetchCurrent () const
    {
      CS_ASSERT(visited && ptr != 0);
      return ptr->data;
    }
    T& FetchNext () const
    {
      CS_ASSERT(ptr != 0);
      return visited ? ptr->next->data : ptr->data;
    }
    T& FetchPrevious () const
    {
      CS_ASSERT(ptr != 0);
      return visited ? ptr->prev->data : ptr->data;
    }
    T& FetchPrev () const { return FetchPrevious(); } // Backward compat.

  protected:
    friend class csList<T>;
    Iterator (csListElement* element, bool visit = true, bool rev = false) :
      ptr(element), visited(visit), reversed(rev)
    {}

  private:
    csListElement* ptr;
    bool visited;
    bool reversed;
  };

  csList& operator=(const csList<T>& other);

  Iterator PushFront (const T& item);

  Iterator PushBack (const T& item);

  void InsertBefore(Iterator& it, const T& item);

  void InsertAfter(Iterator& it, const T& item);

  void MoveBefore(const Iterator& it, const Iterator& item);

  void MoveAfter(const Iterator& it, const Iterator& item);

  void Delete (Iterator& it);

  void DeleteAll();

  T& Front () const
  { return head->data; }
  T& Last () const
  { return tail->data; }

  bool PopFront ()
  {
    if (!head)
      return false;
    Delete (head);
    return true;
  }

  bool PopBack ()
  {
    if (!tail)
      return false;
    Delete (tail);
    return true;
  }
  
  bool IsEmpty () const
  {
    CS_ASSERT((head == 0 && tail == 0) || (head !=0 && tail != 0));
    return head == 0;
  }

private:
  friend class Iterator;
  csListElement *head, *tail;
};

template <class T>
inline csList<T>::csList(const csList<T> &other) : head(0), tail(0)
{
  csListElement* e = other.head;
  while (e != 0)
  {
    PushBack (e->data);
    e = e->next;
  }
}

template <class T>
inline csList<T>& csList<T>::operator= (const csList<T> &other)
{
  DeleteAll ();
  csListElement* e = other.head;
  while (e != 0)
  {
    PushBack (e->data);
    e = e->next;
  }
  return *this;
}

template <class T>
inline void csList<T>::DeleteAll ()
{
  csListElement *cur = head, *next = 0;
  while (cur != 0)
  {
    next = cur->next;
    delete cur;
    cur = next;
  }
  head = tail = 0;
}

template <class T>
inline typename csList<T>::Iterator csList<T>::PushBack (const T& e)
{
  csListElement* el = new csListElement (e, 0, tail);
  if (tail)
    tail->next = el;
  else
    head = el;
  tail = el;
  return Iterator(el);
}

template <class T>
inline typename csList<T>::Iterator csList<T>::PushFront (const T& e)
{
  csListElement* el = new csListElement (e, head, 0);
  if (head)
    head->prev = el;
  else
    tail = el;
  head = el;
  return Iterator (el);
}

template <class T>
inline void csList<T>::InsertAfter (Iterator &it, const T& item)
{
  CS_ASSERT(it.HasCurrent());
  csListElement* el = it.ptr;
  csListElement* next = el->next;
  csListElement* prev = el;
  csListElement* newEl = new csListElement (item, next, prev);
  if (!next) // this is the last element
    tail = newEl;
  else
    el->next->prev = newEl;
  el->next = newEl;
}

template <class T>
inline void csList<T>::InsertBefore (Iterator &it, const T& item)
{
  CS_ASSERT(it.HasCurrent());
  csListElement* el = it.ptr;
  csListElement* next = el;
  csListElement* prev = el->prev;
  csListElement* newEl = new csListElement (item, next, prev);
  if (!prev) // this is the first element
    head = newEl;
  else
    el->prev->next = newEl;
  el->prev = newEl;
}

template <class T>
inline void csList<T>::MoveAfter (const Iterator &it, const Iterator &item)
{
  CS_ASSERT(item.HasCurrent());
  csListElement* el_item = item.ptr;

  // Unlink the item.
  if (el_item->prev)
    el_item->prev->next = el_item->next;
  else
    head = el_item->next;
  if (el_item->next)
    el_item->next->prev = el_item->prev;
  else
    tail = el_item->prev;

  CS_ASSERT(it.HasCurrent());
  csListElement* el = it.ptr;
  csListElement* next = el->next;
  csListElement* prev = el;

  el_item->next = next;
  el_item->prev = prev;
  if (!next) // this is the last element
    tail = el_item;
  else
    el->next->prev = el_item;
  el->next = el_item;
}

template <class T>
inline void csList<T>::MoveBefore (const Iterator &it, const Iterator &item)
{
  CS_ASSERT(item.HasCurrent());
  csListElement* el_item = item.ptr;

  // Unlink the item.
  if (el_item->prev)
    el_item->prev->next = el_item->next;
  else
    head = el_item->next;
  if (el_item->next)
    el_item->next->prev = el_item->prev;
  else
    tail = el_item->prev;

  CS_ASSERT(it.HasCurrent());
  csListElement* el = it.ptr;
  csListElement* next = el;
  csListElement* prev = el->prev;

  el_item->next = next;
  el_item->prev = prev;
  if (!prev) // this is the first element
    head = el_item;
  else
    el->prev->next = el_item;
  el->prev = el_item;
}

template <class T>
inline void csList<T>::Delete (Iterator &it)
{
  CS_ASSERT(it.HasCurrent());
  csListElement* el = it.ptr;

  // Advance the iterator so we can delete the data it's using
  if (it.IsReverse())
    --it;
  else
    ++it;

  Delete(el);
}

template <class T>
inline void csList<T>::Delete (csListElement *el)
{
  CS_ASSERT(el != 0);

  // Fix the pointers of the 2 surrounding elements
  if (el->prev)
    el->prev->next = el->next;
  else
    head = el->next;

  if (el->next)
    el->next->prev = el->prev;
  else
    tail = el->prev;

  delete el;
}

#endif //__CS_UTIL_LIST_H__

---