/* * Copyright (C) 2007-2008 Xagasoft, All rights reserved. * * This file is part of the libbu++ library and is released under the * terms of the license contained in the file LICENSE. */ #ifndef BU_LIST_H #define BU_LIST_H #include #include "bu/exceptionbase.h" #include "bu/util.h" namespace Bu { template struct ListLink { value *pValue; ListLink *pNext; ListLink *pPrev; }; /** * Linked list template container. This class is similar to the stl list * class except for a few minor changes. First, it doesn't mimic a stack or * queue, use the Stack or Queue clasess for that. Second, when const, all * members are only accessable const. Third, erasing a location does not * invalidate the iterator, it simply points to the next valid location, or * end() if there are no more. * *@param value (typename) The type of data to store in your list *@param valuealloc (typename) Memory Allocator for your value type *@param linkalloc (typename) Memory Allocator for the list links. *@ingroup Containers */ template, typename valuealloc=std::allocator, typename linkalloc=std::allocator > > class List { private: typedef struct ListLink Link; typedef class List MyType; public: struct const_iterator; struct iterator; List() : pFirst( NULL ), pLast( NULL ), nSize( 0 ) { } List( const MyType &src ) : pFirst( NULL ), pLast( NULL ), nSize( 0 ) { for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) { append( *pCur->pValue ); } } ~List() { clear(); } /** * Assignment operator. *@param src (const MyType &) The list to assign to your list. */ MyType &operator=( const MyType &src ) { clear(); for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) { append( *pCur->pValue ); } return *this; } MyType &operator+=( const value &v ) { append( v ); return *this; } MyType &operator+=( const MyType &src ) { append( src ); return *this; } /** * Clear the data from the list. */ void clear() { Link *pCur = pFirst; for(;;) { if( pCur == NULL ) break; va.destroy( pCur->pValue ); va.deallocate( pCur->pValue, 1 ); Link *pTmp = pCur->pNext; la.destroy( pCur ); la.deallocate( pCur, 1 ); pCur = pTmp; } pFirst = pLast = NULL; nSize = 0; } void enqueue( const value &v ) { append( v ); } value dequeue() { value v = *pFirst->pValue; erase( begin() ); return v; } /** * Append a value to the list. *@param v (const value_type &) The value to append. */ void append( const value &v ) { Link *pNew = la.allocate( 1 ); pNew->pValue = va.allocate( 1 ); va.construct( pNew->pValue, v ); nSize++; if( pFirst == NULL ) { // Empty list pFirst = pLast = pNew; pNew->pNext = pNew->pPrev = NULL; } else { pNew->pNext = NULL; pNew->pPrev = pLast; pLast->pNext = pNew; pLast = pNew; } } void append( const MyType &rSrc ) { for( typename MyType::const_iterator i = rSrc.begin(); i != rSrc.end(); i++ ) { append( *i ); } } /** * Prepend a value to the list. *@param v (const value_type &) The value to prepend. */ void prepend( const value &v ) { Link *pNew = la.allocate( 1 ); pNew->pValue = va.allocate( 1 ); va.construct( pNew->pValue, v ); nSize++; if( pFirst == NULL ) { // Empty list pFirst = pLast = pNew; pNew->pNext = pNew->pPrev = NULL; } else { pNew->pNext = pFirst; pNew->pPrev = NULL; pFirst->pPrev = pNew; pFirst = pNew; } } /** * Prepend another list to the front of this one. This will prepend * the rSrc list in reverse order...I may fix that later. */ void prepend( const MyType &rSrc ) { for( typename MyType::const_iterator i = rSrc.begin(); i != rSrc.end(); i++ ) { prepend( *i ); } } void insert( MyType::iterator &i, const value &v ) { Link *pAfter = i.pLink; if( pAfter == NULL ) { append( v ); return; } Link *pPrev = pAfter->pPrev; if( pPrev == NULL ) { prepend( v ); return; } Link *pNew = la.allocate( 1 ); pNew->pValue = va.allocate( 1 ); va.construct( pNew->pValue, v ); nSize++; pNew->pNext = pAfter; pNew->pPrev = pPrev; pAfter->pPrev = pNew; pPrev->pNext = pNew; } /** * Insert a new item in sort order by searching for the first item that * is larger and inserting this before it, or at the end if none are * larger. If this is the only function used to insert data in the * List all items will be sorted. To use this, the value type must * support the > operator. */ void insertSorted( const value &v ) { Link *pNew = la.allocate( 1 ); pNew->pValue = va.allocate( 1 ); va.construct( pNew->pValue, v ); nSize++; if( pFirst == NULL ) { // Empty list pFirst = pLast = pNew; pNew->pNext = pNew->pPrev = NULL; return; } else { Link *pCur = pFirst; for(;;) { if( !cmp( v, *(pCur->pValue)) ) { pNew->pNext = pCur; pNew->pPrev = pCur->pPrev; pCur->pPrev = pNew; if( pNew->pPrev == NULL ) pFirst = pNew; else pNew->pPrev->pNext = pNew; return; } pCur = pCur->pNext; if( pCur == NULL ) { pNew->pNext = NULL; pNew->pPrev = pLast; pLast->pNext = pNew; pLast = pNew; return; } } } } /** * An iterator to iterate through your list. */ typedef struct iterator { friend struct const_iterator; friend class List; private: Link *pLink; MyType *pList; bool bOffFront; iterator( MyType *pList ) : pLink( NULL ), pList( pList ) { } iterator( Link *pLink, MyType *pList ) : pLink( pLink ), pList( pList ) { } public: iterator() : pLink( NULL ), pList( NULL ) { } iterator( const iterator &i ) : pLink( i.pLink ), pList( i.pList ) { } /** * Equals comparison operator. *@param oth (const iterator &) The iterator to compare to. *@returns (bool) Are they equal? */ bool operator==( const iterator &oth ) const { return ( pLink == oth.pLink ); } /** * Equals comparison operator. *@param pOth (const Link *) The link to compare to. *@returns (bool) Are they equal? */ bool operator==( const Link *pOth ) const { return ( pLink == pOth ); } /** * Not equals comparison operator. *@param oth (const iterator &) The iterator to compare to. *@returns (bool) Are they not equal? */ bool operator!=( const iterator &oth ) const { return ( pLink != oth.pLink ); } /** * Not equals comparison operator. *@param pOth (const Link *) The link to compare to. *@returns (bool) Are they not equal? */ bool operator!=( const Link *pOth ) const { return ( pLink != pOth ); } /** * Dereference operator. *@returns (value_type &) The value. */ value &operator*() { return *(pLink->pValue); } /** * Pointer access operator. *@returns (value_type *) A pointer to the value. */ value *operator->() { return pLink->pValue; } iterator &operator++() { if( pLink == NULL ) pLink = (bOffFront)?(pList->pFirst):(NULL); else pLink = pLink->pNext; bOffFront = false; return *this; } iterator &operator--() { if( pLink == NULL ) pLink = (bOffFront)?(NULL):(pList->pLast); else pLink = pLink->pPrev; bOffFront = true; return *this; } iterator &operator++( int ) { if( pLink == NULL ) pLink = (bOffFront)?(pList->pFirst):(NULL); else pLink = pLink->pNext; bOffFront = false; return *this; } iterator &operator--( int ) { if( pLink == NULL ) pLink = (bOffFront)?(NULL):(pList->pLast); else pLink = pLink->pPrev; bOffFront = true; return *this; } operator bool() { return pLink != NULL; } bool isValid() { return pLink != NULL; } /** * Assignment operator. *@param oth (const iterator &) The other iterator to set this * one to. */ iterator &operator=( const iterator &oth ) { pLink = oth.pLink; return *this; } } iterator; /** *@see iterator */ typedef struct const_iterator { friend class List; private: Link *pLink; const MyType *pList; bool bOffFront; const_iterator( const MyType *pList ) : pLink( NULL ), pList( pList ) { } const_iterator( Link *pLink, const MyType *pList ) : pLink( pLink ), pList( pList ) { } public: const_iterator() : pLink( NULL ), pList( NULL ) { } const_iterator( const iterator &i ) : pLink( i.pLink ), pList( i.pList ) { } bool operator==( const const_iterator &oth ) const { return ( pLink == oth.pLink ); } bool operator==( const Link *pOth ) const { return ( pLink == pOth ); } bool operator!=( const const_iterator &oth ) const { return ( pLink != oth.pLink ); } bool operator!=( const Link *pOth ) const { return ( pLink != pOth ); } const value &operator*() { return *(pLink->pValue); } const value *operator->() { return pLink->pValue; } const_iterator &operator++() { if( pLink == NULL ) pLink = (bOffFront)?(pList->pFirst):(NULL); else pLink = pLink->pNext; bOffFront = false; return *this; } const_iterator &operator--() { if( pLink == NULL ) pLink = (bOffFront)?(NULL):(pList->pLast); else pLink = pLink->pPrev; bOffFront = true; return *this; } const_iterator &operator++( int ) { if( pLink == NULL ) pLink = (bOffFront)?(pList->pFirst):(NULL); else pLink = pLink->pNext; bOffFront = false; return *this; } const_iterator &operator--( int ) { if( pLink == NULL ) pLink = (bOffFront)?(NULL):(pList->pLast); else pLink = pLink->pPrev; bOffFront = true; return *this; } const_iterator &operator=( const iterator &oth ) { pLink = oth.pLink; return *this; } const_iterator &operator=( const const_iterator &oth ) { pLink = oth.pLink; return *this; } operator bool() { return pLink != NULL; } bool isValid() { return pLink != NULL; } } const_iterator; /** * Get an iterator pointing to the first item in the list. *@returns (iterator) */ iterator begin() { return iterator( pFirst, this ); } /** * Get a const iterator pointing to the first item in the list. *@returns (const const_iterator) */ const_iterator begin() const { return const_iterator( pFirst, this ); } /** * Get an iterator pointing to a place just past the last item in * the list. *@returns (const Link *) */ const iterator end() { return iterator( NULL, this ); } /** * Get an iterator pointing to a place just past the last item in * the list. *@returns (const Link *) */ const const_iterator end() const { return const_iterator( NULL, this ); } /** * Erase an item from the list. *@param i (iterator) The item to erase. */ void erase( iterator i ) { Link *pCur = i.pLink; if( pCur == NULL ) return; Link *pPrev = pCur->pPrev; if( pPrev == NULL ) { va.destroy( pCur->pValue ); va.deallocate( pCur->pValue, 1 ); pFirst = pCur->pNext; la.destroy( pCur ); la.deallocate( pCur, 1 ); if( pFirst == NULL ) pLast = NULL; else pFirst->pPrev = NULL; nSize--; } else { va.destroy( pCur->pValue ); va.deallocate( pCur->pValue, 1 ); Link *pTmp = pCur->pNext; la.destroy( pCur ); la.deallocate( pCur, 1 ); pPrev->pNext = pTmp; if( pTmp != NULL ) pTmp->pPrev = pPrev; nSize--; } } /** * Erase an item from the list if you already know the item. *@param ob The item to find and erase. */ void erase( const value &v ) { for( iterator i = begin(); i != end(); i++ ) { if( (*i) == v ) { erase( i ); return; } } } /** * Get the current size of the list. *@returns (int) The current size of the list. */ long getSize() const { return nSize; } /** * Get the first item in the list. *@returns (value_type &) The first item in the list. */ value &first() { return *pFirst->pValue; } /** * Get the first item in the list. *@returns (const value_type &) The first item in the list. */ const value &first() const { return *pFirst->pValue; } /** * Get the last item in the list. *@returns (value_type &) The last item in the list. */ value &last() { return *pLast->pValue; } /** * Get the last item in the list. *@returns (const value_type &) The last item in the list. */ const value &last() const { return *pLast->pValue; } bool isEmpty() const { return (nSize == 0); } private: Link *pFirst; Link *pLast; linkalloc la; valuealloc va; long nSize; cmpfunc cmp; }; class Formatter; Formatter &operator<<( Formatter &rOut, char *sStr ); Formatter &operator<<( Formatter &rOut, signed char c ); template Formatter &operator<<( Formatter &f, const Bu::List &l ) { f << '['; for( typename Bu::List::const_iterator i = l.begin(); i; i++ ) { if( i != l.begin() ) f << ", "; f << *i; } f << ']'; return f; } } #endif