From dda94f3b53e02e117e6eb5758afa1410e1664c9f Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 15 May 2007 05:25:19 +0000 Subject: SPtr is now Bu::ified, and the List class now acts the way we think const lists should act, you can't change anything in there. I'm still debating changing the const_iterator to a constIterator, or something else that's more Bu::worthy. Heh, the namespaces are funny...ok...I'm really tired. --- src/list.h | 214 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 195 insertions(+), 19 deletions(-) (limited to 'src/list.h') diff --git a/src/list.h b/src/list.h index ec63496..4d16872 100644 --- a/src/list.h +++ b/src/list.h @@ -13,6 +13,15 @@ namespace Bu 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. + */ template, typename linkalloc=std::allocator > > class List { @@ -23,15 +32,59 @@ namespace Bu public: List() : pFirst( NULL ), - pLast( 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(); + } + + MyType &operator=( const MyType &src ) { + clear(); + for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) + { + append( *pCur->pValue ); + } + } + + void clear() + { + Link *pCur = pFirst; + for(;;) + { + if( pCur == NULL ) break; + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + pCur = pTmp; + } + pFirst = pLast = NULL; + nSize = 0; } - void append( value v ) + void append( const value &v ) { Link *pNew = la.allocate( sizeof( Link ) ); pNew->pValue = va.allocate( sizeof( value ) ); va.construct( pNew->pValue, v ); + nSize++; if( pFirst == NULL ) { // Empty list @@ -47,11 +100,12 @@ namespace Bu } } - void prepend( value v ) + void prepend( const value &v ) { Link *pNew = la.allocate( sizeof( Link ) ); pNew->pValue = va.allocate( sizeof( value ) ); va.construct( pNew->pValue, v ); + nSize++; if( pFirst == NULL ) { // Empty list @@ -83,22 +137,22 @@ namespace Bu } public: - bool operator==( const iterator &oth ) + bool operator==( const iterator &oth ) const { return ( pLink == oth.pLink ); } - bool operator==( const Link *pOth ) + bool operator==( const Link *pOth ) const { return ( pLink == pOth ); } - bool operator!=( const iterator &oth ) + bool operator!=( const iterator &oth ) const { return ( pLink != oth.pLink ); } - bool operator!=( const Link *pOth ) + bool operator!=( const Link *pOth ) const { return ( pLink != pOth ); } @@ -110,40 +164,128 @@ namespace Bu value *operator->() { - return pLink->pValue(); + return pLink->pValue; } - iterator operator++() + iterator &operator++() { if( pLink != NULL ) pLink = pLink->pNext; return *this; } - iterator operator--() + iterator &operator--() { if( pLink != NULL ) pLink = pLink->pPrev; return *this; } - iterator operator++( int ) + iterator &operator++( int ) { if( pLink != NULL ) pLink = pLink->pNext; return *this; } - iterator operator--( int ) + iterator &operator--( int ) { if( pLink != NULL ) pLink = pLink->pPrev; return *this; } - iterator operator=( const iterator &oth ) + iterator &operator=( const iterator &oth ) { pLink = oth.pLink; + return *this; + } + }; + + typedef struct const_iterator + { + friend class List; + private: + Link *pLink; + const_iterator() : + pLink( NULL ) + { + } + + const_iterator( Link *pLink ) : + pLink( pLink ) + { + } + + public: + 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 = pLink->pNext; + return *this; + } + + const_iterator &operator--() + { + if( pLink != NULL ) + pLink = pLink->pPrev; + return *this; + } + + const_iterator &operator++( int ) + { + if( pLink != NULL ) + pLink = pLink->pNext; + return *this; + } + + const_iterator &operator--( int ) + { + if( pLink != NULL ) + pLink = pLink->pPrev; + 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; } }; @@ -152,17 +294,50 @@ namespace Bu return iterator( pFirst ); } - const Link *end() + const const_iterator begin() const + { + return const_iterator( pFirst ); + } + + const Link *end() const { return NULL; } - int getSize() + void erase( iterator &i ) + { + Link *pCur = i.pLink; + Link *pPrev = pCur->pPrev; + if( pPrev == NULL ) + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + pFirst = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + if( pFirst == NULL ) + pLast = NULL; + nSize--; + i.pLink = pFirst; + } + else + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + pPrev->pNext = pTmp; + if( pTmp != NULL ) + pTmp->pPrev = pPrev; + nSize--; + i.pLink = pTmp; + } + } + + int getSize() const { - int j = 0; - for( Link *pCur = pFirst; pCur; pCur = pCur->pNext ) - j++; - return j; + return nSize; } private: @@ -170,6 +345,7 @@ namespace Bu Link *pLast; linkalloc la; valuealloc va; + int nSize; }; } -- cgit v1.2.3