Logo Search packages:      
Sourcecode: ragel version File versions

dlcommon.h

/*
 *  Copyright 2001 Adrian Thurston <adriant@ragel.ca>
 */

/*  This file is part of Aapl.
 *
 *  Aapl is free software; you can redistribute it and/or modify it under the
 *  terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  Aapl 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 Lesser General Public License for
 *  more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
 *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/* This header is not wrapped in ifndef becuase it is not intended to
 * be included by the user. */

#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif

#if defined( DOUBLELIST_VALUE )
/**
 * \brief Double list element for DListVal.
 *
 * DListValEl stores the type T of DListVal by value. 
 */
template <class T> struct DListValEl
{
      /**
       * \brief Construct a DListValEl with a given value.
       *
       * The only constructor available initializes the value element. This
       * enforces that DListVal elements are never created without having their
       * value intialzed by the user. T's copy constructor is used to copy the
       * value in.
       */
      DListValEl( const T &val ) : value(val) { }

      /**
       * \brief Value stored by the list element.
       *
       * Value is always copied into new list elements using the copy
       * constructor.
       */
      T value;

      /**
       * \brief List previous pointer.
       *
       * Points to the previous item in the list. If this is the first item in
       * the list, then prev is NULL. If this element is not in a list then
       * prev is undefined.
       */
      DListValEl<T> *prev;

      /**
       * \brief List next pointer.
       *
       * Points to the next item in the list. If this is the list item in the
       * list, then next is NULL. If this element is not in a list then next is
       * undefined.
       */
      DListValEl<T> *next;
};
#else

#ifndef __AAPL_DOUBLE_LIST_EL
#define __AAPL_DOUBLE_LIST_EL
/**
 * \brief Double list element properties.
 *
 * This class can be inherited to make a class suitable to be a double list
 * element. It simply provides the next and previous pointers. An alternative
 * is to put the next and previous pointers in the class directly.
 */
00084 template <class Element> struct DListEl
{
      /**
       * \brief List previous pointer.
       *
       * Points to the previous item in the list. If this is the first item in
       * the list, then prev is NULL. If this element is not in a list then
       * prev is undefined.
       */
00093       Element *prev;

      /**
       * \brief List next pointer.
       *
       * Points to the next item in the list. If this is the list item in the
       * list, then next is NULL. If this element is not in a list then next is
       * undefined.
       */
00102       Element *next;
};
#endif /* __AAPL_DOUBLE_LIST_EL */

#endif

/* Doubly Linked List */
00109 template <DLMEL_TEMPDEF> class DList
{
public:
      /** \brief Initialize an empty list. */
00113       DList() : head(0), tail(0), listLen(0) {}

#ifdef DOUBLELIST_VALUE
      /** 
       * \brief Perform a deep copy of the list.
       * 
       * The elements of the other list are duplicated and put into this list.
       * Elements are copied using the copy constructor.
       */
      DList(const DList &other);

      /**
       * \brief Clear the double list contents.
       *
       * All elements are deleted.
       */
      ~DList() { empty(); }

      /**
       * \brief Assign another list into this list using a deep copy.
       *
       * The elements of the other list are duplicated and put into this list.
       * Each list item is created using the copy constructor. If this list
       * contains any elements before the copy, they are deleted first.
       *
       * \returns A reference to this.
       */
      DList &operator=(const DList &other);
#else
      /** 
       * \brief Perform a shallow copy of the list. 
       */
      DList(const DList &other);

      /**
       * \brief Abandon all elements in the list. 
       *
       * List elements are not deleted.
       */
00152       ~DList() {}

      /**
       * \brief Perform a shallow copy of the list.
       *
       * Performs a shallow copy of another list into this list. If this list is
       * non-empty then its contents are abandoned (not freed).
       *
       * \returns A reference to this.
       */
      DList &operator=(const DList &other);
#endif

      /**
       * \brief Shallow copy another list into this list.
       *
       * The elements of the other list are copied in by reference. The two
       * lists will share the same list elements. If this list contains any
       * elements before the copy, then they are abandoned. If either of the
       * lists are modified after a shallow copy, the other list may become
       * corrupted.
       */
      void shallowCopy(const DList &other);


      /** 
       * \brief Perform a deep copy of the list. 
       *
       * Each element is duplicated for the new list. Copy constructors are used
       * to create the new elements. If this list contains items, they are first
       * deleted.
       */
      void deepCopy(const DList &other);


#ifdef DOUBLELIST_VALUE
      /**
       * \brief Make a new element and prepend it to the front of the list.
       *
       * The item is copied into the new element using the copy constructor.
       * Equivalent to list.addBefore(list.head, item).
       */
      void prepend(const T &item);

      /**
       * \brief Make a new element and append it to the end of the list.
       *
       * The item is copied into the new element using the copy constructor.
       * Equivalent to list.addAfter(list.tail, item).
       */
      void append(const T &item);

      /**
       * \brief Make a new element and insert it immediately after an element in
       * the list.
       *
       * The item is copied into the new element using the copy constructor. If
       * prev_el is NULL then the new element is prepended to the front of the
       * list. If prev_el is not already in the list then undefined behaviour
       * results.  Equivalent to list.addAfter(prev_el, new DListValEl(item)).
       */
      void addAfter(Element *prev_el, const T &item);

      /**
       * \brief Make a new element and insert it immediately before an element
       * in the list. 
       *
       * The item is copied into the new element using the copy construcotor. If
       * next_el is NULL then the new element is appended to the end of the
       * list.  If next_el is not already in the list then undefined behaviour
       * results.  Equivalent to list.addBefore(next_el, new DListValEl(item)).
       */
      void addBefore(Element *next_el, const T &item);
#endif

      /**
       * \brief Prepend a single element to the front of the list.
       *
       * If new_el is already an element of some list, then undefined behaviour
       * results. Equivalent to list.addBefore(list.head, new_el).
       */
00233       void prepend(Element *new_el) { addBefore(head, new_el); }

      /**
       * \brief Append a single element to the end of the list.
       *
       * If new_el is alreay an element of some list, then undefined behaviour
       * results.  Equivalent to list.addAfter(list.tail, new_el).
       */
00241       void append(Element *new_el)  { addAfter(tail, new_el); }

      /**
       * \brief Prepend an entire list to the beginning of this list.
       *
       * All items are moved, not copied. Afterwards, the other list is emtpy.
       * All items are prepended at once, so this is an O(1) operation.
       * Equivalent to list.addBefore(list.head, dl).
       */
00250       void prepend(DList &dl)       { addBefore(head, dl); }

      /**
       * \brief Append an entire list to the end of the list.
       *
       * All items are moved, not copied. Afterwards, the other list is empty.
       * All items are appened at once, so this is an O(1) operation.
       * Equivalent to list.addAfter(list.tail, dl).
       */
00259       void append(DList &dl)        { addAfter(tail, dl); }

      void addAfter(Element *prev_el, Element *new_el);
      void addBefore(Element *next_el, Element *new_el);

      void addAfter(Element *prev_el, DList &dl);
      void addBefore(Element *next_el, DList &dl);

      /**
       * \brief Detach the head of the list
       *
       * The element detached is not deleted. If there is no head of the list
       * (the list is empty) then undefined behaviour results.  Equivalent to
       * list.detach(list.head).
       *
       * \returns The element detached.
       */
00276       Element *detachFirst()        { return detach(head); }

      /**
       * \brief Detach the tail of the list
       *
       * The element detached is not deleted. If there is no tail of the list
       * (the list is empty) then undefined behaviour results.  Equivalent to
       * list.detach(list.tail).
       *
       * \returns The element detached.
       */
00287       Element *detachLast()         { return detach(tail); }

      /* Detaches an element from the list. Does not free any memory. */
      Element *detach(Element *el);

      /**
       * \brief Detach and delete the first element in the list.
       *
       * If there is no first element (the list is empty) then undefined
       * behaviour results.  Equivalent to delete list.detach(list.head);
       */
00298       void removeFirst()         { delete detach( head ); }

      /**
       * \brief Detach and delete the last element in the list.
       *
       * If there is no last element (the list is emtpy) then undefined
       * behaviour results.  Equivalent to delete list.detach(list.tail);
       */
00306       void removeLast()          { delete detach( tail ); }

      /**
       * \brief Detach and delete an element from the list.
       *
       * If the element is not in the list, then undefined behaviour results.
       * Equivalent to delete list.detach(el);
       */
00314       void remove(Element *el)   { delete detach( el ); }
      
      void empty();
      void abandon();

      /** \brief The number of elements in the list. */
00320       long length() const { return listLen; }

      /** \brief Head and tail of the linked list. */
00323       Element *head, *tail;

      /** \brief The number of element in the list. */
00326       long listLen;

      /* Convenience access. */
      long size() const           { return listLen; }

      /* Forward this so a ref can be used. */
      struct Iter;

      /* Class for setting the iterator. */
      struct IterFirst { IterFirst( const DList &l ) : l(l) { } const DList &l; };
      struct IterLast { IterLast( const DList &l ) : l(l) { } const DList &l; };
      struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
      struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };

      /**
       * \brief Double List Iterator. 
       * \ingroup iterators
       */
00344       struct Iter
      {
            /* Default construct. */
            Iter() : ptr(0) { }

            /* Construct from a double list. */
            Iter( const DList &dl )      : ptr(dl.head) { }
            Iter( Element *el )          : ptr(el) { }
            Iter( const IterFirst &dlf ) : ptr(dlf.l.head) { }
            Iter( const IterLast &dll )  : ptr(dll.l.tail) { }
            Iter( const IterNext &dln )  : ptr(dln.i.ptr->BASE_EL(next)) { }
            Iter( const IterPrev &dlp )  : ptr(dlp.i.ptr->BASE_EL(prev)) { }

            /* Assign from a double list. */
            Iter &operator=( const DList &dl )     { ptr = dl.head; return *this; }
            Iter &operator=( Element *el )         { ptr = el; return *this; }
            Iter &operator=( const IterFirst &af ) { ptr = af.l.head; return *this; }
            Iter &operator=( const IterLast &al )  { ptr = al.l.tail; return *this; }
            Iter &operator=( const IterNext &an )  { ptr = an.i.ptr->BASE_EL(next); return *this; }
            Iter &operator=( const IterPrev &ap )  { ptr = ap.i.ptr->BASE_EL(prev); return *this; }

            /** \brief Less than end? */
00366             bool lte() const    { return ptr != 0; }

            /** \brief At end? */
00369             bool end() const    { return ptr == 0; }

            /** \brief Greater than beginning? */
00372             bool gtb() const { return ptr != 0; }

            /** \brief At beginning? */
00375             bool beg() const { return ptr == 0; }

            /** \brief At first element? */
00378             bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }

            /** \brief At last element? */
00381             bool last() const  { return ptr && ptr->BASE_EL(next) == 0; }

            /** \brief Implicit cast to Element*. */
00384             operator Element*() const   { return ptr; }

            /** \brief Dereference operator returns Element&. */
00387             Element &operator *() const { return *ptr; }

            /** \brief Arrow operator returns Element*. */
00390             Element *operator->() const { return ptr; }

            /** \brief Move to next item. */
00393             inline Element *operator++()      { return ptr = ptr->BASE_EL(next); }

            /** \brief Move to next item. */
00396             inline Element *increment()       { return ptr = ptr->BASE_EL(next); }

            /** \brief Move to next item. */
            inline Element *operator++(int);

            /** \brief Move to previous item. */
00402             inline Element *operator--()      { return ptr = ptr->BASE_EL(prev); }

            /** \brief Move to previous item. */
00405             inline Element *decrement()       { return ptr = ptr->BASE_EL(prev); }

            /** \brief Move to previous item. */
            inline Element *operator--(int);

            /** \brief Return the next item. Does not modify this. */
00411             inline IterNext next() const { return IterNext(*this); }

            /** \brief Return the prev item. Does not modify this. */
00414             inline IterPrev prev() const { return IterPrev(*this); }

            /** \brief The iterator is simply a pointer. */
00417             Element *ptr;
      };

      /** \brief Return first element. */
00421       IterFirst first()  { return IterFirst(*this); }

      /** \brief Return last element. */
00424       IterLast last()    { return IterLast(*this); }
};

#ifdef DOUBLELIST_VALUE

/* Copy constructor, does a deep copy of other. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE>::
		DList(const DList<DLMEL_TEMPUSE> &other) :
                  head(0), tail(0), listLen(0)
{
      Element *el = other.head;
      while( el != 0 ) {
            append( new Element(*el) );
            el = el->BASE_EL(next);
      }
}

/* Assignement operator does deep copy. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
		operator=(const DList &other)
{
      /* Loose the old list. The value list assumes items were allocated on the
       * heap by ourselves. It assumes ownership. */
      empty();

      Element *el = other.head;
      while( el != 0 ) {
            append( new Element(*el) );
            el = el->BASE_EL(next);
      }
      return *this;
}

#else 

/* Copy constructor, does a shallow copy. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE>::
		DList(const DList<DLMEL_TEMPUSE> &other)
:
      head(other.head), 
      tail(other.tail), 
      listLen(other.listLen)
{
}

/* Assignment does a shallow copy. */
template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>::
00471 		operator=(const DList &other)
{
      head = other.head;
      tail = other.tail;
      listLen = other.listLen;
      return *this;
}
#endif

/* Explicit shallow copy. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
00482 		shallowCopy(const DList &other)
{
      head = other.head;
      tail = other.tail;
      listLen = other.listLen;
}

/* Deep copy another list in. Empties the current list. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
00491 		deepCopy(const DList &other)
{
      /* Loose the old list. The value list assumes items were allocated on the
       * heap by ourselves. It assumes ownership. */
      empty();

      Element *el = other.head;
      while( el != 0 ) {
            append( new Element(*el) );
            el = el->BASE_EL(next);
      }
}


#ifdef DOUBLELIST_VALUE

/* Prepend a new item. Inlining this bloats the caller with new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		prepend(const T &item)
{
      addBefore(head, new Element(item)); 
}

/* Append a new item. Inlining this bloats the caller with the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		append(const T &item)
{
      addAfter(tail, new Element(item));
}

/* Add a new item after a prev element. Inlining this bloats the caller with
 * the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		addAfter(Element *prev_el, const T &item)
{
      addAfter(prev_el, new Element(item));
}

/* Add a new item before a next element. Inlining this bloats the caller with
 * the new overhead. */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		addBefore(Element *next_el, const T &item)
{
      addBefore(next_el, new Element(item));
}

#endif

/*
 * The larger iterator operators.
 */

/* Postfix ++ */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
00545 		operator++(int)       
{
      Element *rtn = ptr; 
      ptr = ptr->BASE_EL(next);
      return rtn;
}

/* Postfix -- */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter::
00554 		operator--(int)       
{
      Element *rtn = ptr;
      ptr = ptr->BASE_EL(prev);
      return rtn;
}

/**
 * \brief Insert an element immediately after an element in the list.
 *
 * If prev_el is NULL then new_el is prepended to the front of the list. If
 * prev_el is not in the list or if new_el is already in a list, then
 * undefined behaviour results.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
00569 		addAfter(Element *prev_el, Element *new_el)
{
      /* Set the previous pointer of new_el to prev_el. We do
       * this regardless of the state of the list. */
      new_el->BASE_EL(prev) = prev_el; 

      /* Set forward pointers. */
      if (prev_el == 0) {
            /* There was no prev_el, we are inserting at the head. */
            new_el->BASE_EL(next) = head;
            head = new_el;
      } 
      else {
            /* There was a prev_el, we can access previous next. */
            new_el->BASE_EL(next) = prev_el->BASE_EL(next);
            prev_el->BASE_EL(next) = new_el;
      } 

      /* Set reverse pointers. */
      if (new_el->BASE_EL(next) == 0) {
            /* There is no next element. Set the tail pointer. */
            tail = new_el;
      }
      else {
            /* There is a next element. Set it's prev pointer. */
            new_el->BASE_EL(next)->BASE_EL(prev) = new_el;
      }

      /* Update list length. */
      listLen++;
}

/**
 * \brief Insert an element immediatly before an element in the list.
 *
 * If next_el is NULL then new_el is appended to the end of the list. If
 * next_el is not in the list or if new_el is already in a list, then
 * undefined behaviour results.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
00609 		addBefore(Element *next_el, Element *new_el)
{
      /* Set the next pointer of the new element to next_el. We do
       * this regardless of the state of the list. */
      new_el->BASE_EL(next) = next_el; 

      /* Set reverse pointers. */
      if (next_el == 0) {
            /* There is no next elememnt. We are inserting at the tail. */
            new_el->BASE_EL(prev) = tail;
            tail = new_el;
      } 
      else {
            /* There is a next element and we can access next's previous. */
            new_el->BASE_EL(prev) = next_el->BASE_EL(prev);
            next_el->BASE_EL(prev) = new_el;
      } 

      /* Set forward pointers. */
      if (new_el->BASE_EL(prev) == 0) {
            /* There is no previous element. Set the head pointer.*/
            head = new_el;
      }
      else {
            /* There is a previous element, set it's next pointer to new_el. */
            new_el->BASE_EL(prev)->BASE_EL(next) = new_el;
      }

      /* Update list length. */
      listLen++;
}

/**
 * \brief Insert an entire list immediatly after an element in this list.
 *
 * Elements are moved, not copied. Afterwards, the other list is empty. If
 * prev_el is NULL then the elements are prepended to the front of the list.
 * If prev_el is not in the list then undefined behaviour results. All
 * elements are inserted into the list at once, so this is an O(1) operation.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		addAfter( Element *prev_el, DList<DLMEL_TEMPUSE> &dl )
{
      /* Do not bother if dl has no elements. */
      if ( dl.listLen == 0 )
            return;

      /* Set the previous pointer of dl.head to prev_el. We do
       * this regardless of the state of the list. */
      dl.head->BASE_EL(prev) = prev_el; 

      /* Set forward pointers. */
      if (prev_el == 0) {
            /* There was no prev_el, we are inserting at the head. */
            dl.tail->BASE_EL(next) = head;
            head = dl.head;
      } 
      else {
            /* There was a prev_el, we can access previous next. */
            dl.tail->BASE_EL(next) = prev_el->BASE_EL(next);
            prev_el->BASE_EL(next) = dl.head;
      } 

      /* Set reverse pointers. */
      if (dl.tail->BASE_EL(next) == 0) {
            /* There is no next element. Set the tail pointer. */
            tail = dl.tail;
      }
      else {
            /* There is a next element. Set it's prev pointer. */
            dl.tail->BASE_EL(next)->BASE_EL(prev) = dl.tail;
      }

      /* Update the list length. */
      listLen += dl.listLen;

      /* Empty out dl. */
      dl.head = dl.tail = 0;
      dl.listLen = 0;
}

/**
 * \brief Insert an entire list immediately before an element in this list.
 *
 * Elements are moved, not copied. Afterwards, the other list is empty. If
 * next_el is NULL then the elements are appended to the end of the list. If
 * next_el is not in the list then undefined behaviour results. All elements
 * are inserted at once, so this is an O(1) operation.
 */
template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::
		addBefore( Element *next_el, DList<DLMEL_TEMPUSE> &dl )
{
      /* Do not bother if dl has no elements. */
      if ( dl.listLen == 0 )
            return;

      /* Set the next pointer of dl.tail to next_el. We do
       * this regardless of the state of the list. */
      dl.tail->BASE_EL(next) = next_el; 

      /* Set reverse pointers. */
      if (next_el == 0) {
            /* There is no next elememnt. We are inserting at the tail. */
            dl.head->BASE_EL(prev) = tail;
            tail = dl.tail;
      } 
      else {
            /* There is a next element and we can access next's previous. */
            dl.head->BASE_EL(prev) = next_el->BASE_EL(prev);
            next_el->BASE_EL(prev) = dl.tail;
      } 

      /* Set forward pointers. */
      if (dl.head->BASE_EL(prev) == 0) {
            /* There is no previous element. Set the head pointer.*/
            head = dl.head;
      }
      else {
            /* There is a previous element, set it's next pointer to new_el. */
            dl.head->BASE_EL(prev)->BASE_EL(next) = dl.head;
      }

      /* Update list length. */
      listLen += dl.listLen;

      /* Empty out dl. */
      dl.head = dl.tail = 0;
      dl.listLen = 0;
}


/**
 * \brief Detach an element from the list.
 *
 * The element is not deleted. If the element is not in the list, then
 * undefined behaviour results.
 *
 * \returns The element detached.
 */
template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::
00749 		detach(Element *el)
{
      /* Set forward pointers to skip over el. */
      if (el->BASE_EL(prev) == 0) 
            head = el->BASE_EL(next); 
      else {
            el->BASE_EL(prev)->BASE_EL(next) =
                        el->BASE_EL(next); 
      }

      /* Set reverse pointers to skip over el. */
      if (el->BASE_EL(next) == 0) 
            tail = el->BASE_EL(prev); 
      else {
            el->BASE_EL(next)->BASE_EL(prev) =
                        el->BASE_EL(prev); 
      }

      /* Update List length and return element we detached. */
      listLen--;
      return el;
}

/**
 * \brief Clear the list by deleting all elements.
 *
 * Each item in the list is deleted. The list is reset to its initial state.
 */
00777 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::empty()
{
      Element *nextToGo = 0, *cur = head;
      
      while (cur != 0)
      {
            nextToGo = cur->BASE_EL(next);
            delete cur;
            cur = nextToGo;
      }
      head = tail = 0;
      listLen = 0;
}

/**
 * \brief Clear the list by forgetting all elements.
 *
 * All elements are abandoned, not deleted. The list is reset to it's initial
 * state.
 */
00797 template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::abandon()
{
      head = tail = 0;
      listLen = 0;
}

#ifdef AAPL_NAMESPACE
}
#endif

Generated by  Doxygen 1.6.0   Back to index