diff options
Diffstat (limited to 'aapl/dlcommon.h')
| -rw-r--r-- | aapl/dlcommon.h | 790 |
1 files changed, 790 insertions, 0 deletions
diff --git a/aapl/dlcommon.h b/aapl/dlcommon.h new file mode 100644 index 0000000..91dff25 --- /dev/null +++ b/aapl/dlcommon.h @@ -0,0 +1,790 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@complang.org> + */ + +/* 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. + */ +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. + */ + 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. + */ + Element *next; +}; +#endif /* __AAPL_DOUBLE_LIST_EL */ + +#endif + +/* Doubly Linked List */ +template <DLMEL_TEMPDEF> class DList +{ +public: + /** \brief Initialize an empty list. */ + DList() : head(0), tail(0), listLen(0) {} + + /** + * \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); + +#ifdef DOUBLELIST_VALUE + /** + * \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); + + /** + * \brief Transfer the contents of another list into this list. + * + * The elements of the other list moved in. The other list will be empty + * afterwards. If this list contains any elements before the copy, then + * they are deleted. + */ + void transfer(DList &other); +#else + /** + * \brief Abandon all elements in the list. + * + * List elements are not deleted. + */ + ~DList() {} + + /** + * \brief Perform a deep copy of the list. + * + * 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 abandoned. + * + * \returns A reference to this. + */ + DList &operator=(const DList &other); + + /** + * \brief Transfer the contents of another list into this list. + * + * The elements of the other list moved in. The other list will be empty + * afterwards. If this list contains any elements before the copy, they + * are abandoned. + */ + void transfer(DList &other); +#endif + + +#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). + */ + 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). + */ + 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). + */ + 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). + */ + 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. + */ + 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. + */ + 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); + */ + 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); + */ + 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); + */ + void remove(Element *el) { delete detach( el ); } + + void empty(); + void abandon(); + + /** \brief The number of elements in the list. */ + long length() const { return listLen; } + + /** \brief Head and tail of the linked list. */ + Element *head, *tail; + + /** \brief The number of element in the list. */ + 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 + */ + 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? */ + bool lte() const { return ptr != 0; } + + /** \brief At end? */ + bool end() const { return ptr == 0; } + + /** \brief Greater than beginning? */ + bool gtb() const { return ptr != 0; } + + /** \brief At beginning? */ + bool beg() const { return ptr == 0; } + + /** \brief At first element? */ + bool first() const { return ptr && ptr->BASE_EL(prev) == 0; } + + /** \brief At last element? */ + bool last() const { return ptr && ptr->BASE_EL(next) == 0; } + + /** \brief Implicit cast to Element*. */ + operator Element*() const { return ptr; } + + /** \brief Dereference operator returns Element&. */ + Element &operator *() const { return *ptr; } + + /** \brief Arrow operator returns Element*. */ + Element *operator->() const { return ptr; } + + /** \brief Move to next item. */ + inline Element *operator++() { return ptr = ptr->BASE_EL(next); } + + /** \brief Move to next item. */ + inline Element *increment() { return ptr = ptr->BASE_EL(next); } + + /** \brief Move to next item. */ + inline Element *operator++(int); + + /** \brief Move to previous item. */ + inline Element *operator--() { return ptr = ptr->BASE_EL(prev); } + + /** \brief Move to previous item. */ + 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. */ + inline IterNext next() const { return IterNext(*this); } + + /** \brief Return the prev item. Does not modify this. */ + inline IterPrev prev() const { return IterPrev(*this); } + + /** \brief The iterator is simply a pointer. */ + Element *ptr; + }; + + /** \brief Return first element. */ + IterFirst first() { return IterFirst(*this); } + + /** \brief Return last element. */ + IterLast last() { return IterLast(*this); } +}; + +/* 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); + } +} + +#ifdef DOUBLELIST_VALUE + +/* Assignement operator does deep copy. */ +template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>:: + operator=(const DList &other) +{ + /* Free the old list. The value list assumes items were allocated on the + * heap by itself. */ + empty(); + + Element *el = other.head; + while( el != 0 ) { + append( new Element(*el) ); + el = el->BASE_EL(next); + } + return *this; +} + +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + transfer(DList &other) +{ + /* Free the old list. The value list assumes items were allocated on the + * heap by itself. */ + empty(); + + head = other.head; + tail = other.tail; + listLen = other.listLen; + + other.abandon(); +} + +#else + +/* Assignement operator does deep copy. */ +template <DLMEL_TEMPDEF> DList<DLMEL_TEMPUSE> &DList<DLMEL_TEMPUSE>:: + operator=(const DList &other) +{ + Element *el = other.head; + while( el != 0 ) { + append( new Element(*el) ); + el = el->BASE_EL(next); + } + return *this; +} + +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>:: + transfer(DList &other) +{ + head = other.head; + tail = other.tail; + listLen = other.listLen; + + other.abandon(); +} + +#endif + +#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:: + operator++(int) +{ + Element *rtn = ptr; + ptr = ptr->BASE_EL(next); + return rtn; +} + +/* Postfix -- */ +template <DLMEL_TEMPDEF> Element *DList<DLMEL_TEMPUSE>::Iter:: + 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>:: + 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>:: + 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>:: + 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. + */ +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. + */ +template <DLMEL_TEMPDEF> void DList<DLMEL_TEMPUSE>::abandon() +{ + head = tail = 0; + listLen = 0; +} + +#ifdef AAPL_NAMESPACE +} +#endif |