---

t_list.h

/* liblookdb: t_list.h - List looking like a cut down  stl deque 
    Copyright (C) 1998-2001 LOOK Systems

    This library 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.

    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
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#ifndef LIBLOOKDB_T_LIST_H
#define LIBLOOKDB_T_LIST_H

// $Id: t_list.h,v 1.6 2001/07/04 15:53:22 clive Exp $

#include "lookcompileropts.h"

#include "stddef.h"

namespace look {

#ifdef WIN32
#pragma warning( disable : 4284 )
#pragma warning( disable : 4786 )
#pragma warning( disable : 4251 )
#endif


template<class tBody>
class LookTLList
{
protected:
        struct ListItem
        {
        public:
                ListItem( const tBody &theItem,
                        ListItem *thePrevious = NULL,
                        ListItem *theNext = NULL )
                        : itsPrevious( thePrevious ),
                        itsNext( theNext ),
                        itsItem( theItem )
                {}
                
                ListItem *itsPrevious;
                ListItem *itsNext;
                tBody itsItem;
        };

protected:

        ListItem *itsFirstItem;
        ListItem *itsLastItem;
        ListItem *itsMemoryItem;   // mutable?  // Not on cxx5 - xian
        size_t itsMemoryItemNumber;// mutable?
        size_t itsNumberOfItems;

        // implemented functions

        // Appends the given tBody to the end of the list.
        void append( const tBody &a )
        {
                ListItem *aNewItem = new ListItem( a,
                        itsLastItem,
                        NULL );
                if( itsLastItem != NULL )
                {
                        itsLastItem -> itsNext = aNewItem;
                        itsLastItem = aNewItem;
                }
                else
                {
                        itsMemoryItem = itsFirstItem = itsLastItem = aNewItem;
                        itsMemoryItemNumber = 0;
                }
                itsNumberOfItems++;
        }

        // prepends the given tBody to the end of the list.
        void prepend( const tBody &a )
        {
                ListItem *aNewItem = new ListItem( a,
                        NULL,
                        itsFirstItem );
                if( itsFirstItem != NULL )
                {
                        itsFirstItem -> itsPrevious = aNewItem;
                        itsFirstItem = aNewItem;
                }
                else
                {
                        itsFirstItem = itsLastItem = aNewItem;
                }
                
                itsMemoryItem = aNewItem;
                itsMemoryItemNumber = 0;
                itsNumberOfItems++;
        }

        void InvalidateMemoryIterator( void )
        {
                itsMemoryItem = itsFirstItem;
                itsMemoryItemNumber = 0;
        }

        // Move the list iterator to the given index.
        void MoveMemoryIteratorToItemAt( size_t i ) const
        {
                // cast away const so we can access our memory bits
                LookTLList<tBody> * const localThis = (LookTLList<tBody> * const) this;

                if( itsNumberOfItems == 0 || itsMemoryItemNumber == i
                        || itsNumberOfItems < i )
                {
                        return;
                }
                
                if( i < itsNumberOfItems - i )
                {
                        if( itsMemoryItemNumber > i && itsMemoryItemNumber - i > i )
                        {
                                localThis->itsMemoryItemNumber = 0;
                                localThis->itsMemoryItem = itsFirstItem;
                        }
                }
                else
                {
                        if( itsMemoryItemNumber < i && i - itsMemoryItemNumber > i )
                        {
                                localThis->itsMemoryItemNumber = itsNumberOfItems - 1;
                                localThis->itsMemoryItem = itsLastItem;
                        }
                }
                
                if( itsMemoryItemNumber < i )
                {
                        size_t Count;
                        for( Count = itsMemoryItemNumber; Count < i; Count++ )
                        {
                                localThis->itsMemoryItem = itsMemoryItem->itsNext;
                        }
                }
                else
                {
                        size_t Count;
                        for( Count = itsMemoryItemNumber; Count > i; Count-- )
                        {
                                localThis->itsMemoryItem = itsMemoryItem->itsPrevious;
                        }
                }
                localThis->itsMemoryItemNumber = i;
        }

public:

        // ======================================

        // iterator things
        // the iterator bypasses the list's idea of iterators

        class iterator;
        friend class iterator;

        class iterator
        {
        public:
                friend class LookTLList<tBody>;

                iterator()
                        : itsItem( NULL ),
                        itsList( NULL )
                {
                }

                ~iterator()
                {
                }


                iterator( const LookTLList<tBody>* theList, ListItem* theItem )
                        : itsItem( theItem ),
                        itsList( (LookTLList<tBody>*) theList )
                {
                }

                iterator& operator++()
                {
                        if( itsItem )
                        {
                                itsItem = itsItem->itsNext;
                        }
                        return *this;
                }

                iterator operator++(int)
                {
                        iterator temp( *this );
                        if( itsItem )
                        {
                                itsItem = itsItem->itsNext;
                        }
                        return temp;
                }

                iterator& operator--()
                {
                        if( itsItem )
                        {
                                itsItem = itsItem->itsPrevious;
                        }
                        else if( itsList )
                        {
                                itsItem = itsList->itsLastItem;
                        }

                        return *this;
                }

                iterator operator--(int)
                {
                        iterator temp( *this );
                        if( itsItem )
                        {
                                itsItem = itsItem->itsPrevious;
                        }
                        else if( itsList )
                        {
                                itsItem = itsList->itsLastItem;
                        }
                        return temp;
                }
                
                iterator& operator+=( size_t theChange )
                {
                        for( size_t loop = 0; loop < theChange; loop++ )
                        {
                                ++(*this);
                        }
                        return *this;
                }

                iterator& operator-=( size_t theChange )
                {
                        for( size_t loop = 0; loop < theChange; loop++ )
                        {
                                --(*this);
                        }
                        return *this;
                }

                bool operator!=( const iterator& anIter )
                {
                        return( itsItem != anIter.itsItem );
                }

                bool operator==( const iterator& anIter )
                {
                        return( itsItem == anIter.itsItem );
                }

        // the useful access ops
                tBody& operator*() const
                {
                        return itsItem->itsItem;
                }

                tBody* operator->() const
                {
                        return (&**this);
                }

        protected:
                ListItem* itsItem;
                LookTLList<tBody>* itsList;
        };

        typedef iterator const_iterator;

        class reverse_iterator;
        friend class reverse_iterator;

        class reverse_iterator
        {
        public:
                friend class LookTLList<tBody>;

                reverse_iterator()
                        : itsItem( NULL ),
                        itsList( NULL )
                {
                }

                ~reverse_iterator()
                {
                }

                reverse_iterator( const LookTLList<tBody>* theList, ListItem* theItem )
                        : itsItem( theItem ),
                        itsList( (LookTLList<tBody>*) theList )
                {
                }

                reverse_iterator& operator++()
                {
                        if( itsItem )
                        {
                                itsItem = itsItem->itsPrevious;
                        }
                        else if( itsList )
                        {
                                itsItem = itsList->itsLastItem;
                        }
                        return *this;
                }

                reverse_iterator operator++(int)
                {
                        reverse_iterator temp( *this );
                        if( itsItem )
                        {
                                itsItem = itsItem->itsPrevious;
                        }
                        else if( itsList )
                        {
                                itsItem = itsList->itsLastItem;
                        }
                        return temp;
                }

                reverse_iterator& operator--()
                {
                        if( itsItem )
                        {
                                itsItem = itsItem->itsNext;
                        }

                        return *this;
                }

                reverse_iterator operator--(int)
                {
                        reverse_iterator temp( *this );
                        if( itsItem )
                        {
                                itsItem = itsItem->itsNext;
                        }
                        return temp;
                }

                reverse_iterator& operator+=( size_t theChange )
                {
                        for( size_t loop = 0; loop < theChange; loop++ )
                        {
                                ++(*this);
                        }
                        return *this;
                }

                reverse_iterator& operator-=( size_t theChange )
                {
                        for( size_t loop = 0; loop < theChange; loop++ )
                        {
                                --(*this);
                        }
                        return *this;
                }

                bool operator!=( const reverse_iterator& anIter )
                {
                        return( itsItem != anIter.itsItem );
                }

                bool operator==( const reverse_iterator& anIter )
                {
                        return( itsItem == anIter.itsItem );
                }
                
                // the useful access ops
                tBody& operator*() const
                {
                        if( itsItem )
                        {
                                return itsItem->itsPrevious->itsItem;
                        }
                        else
                        {
                                return itsList->itsLastItem->itsItem;
                        }
                }

                tBody* operator->() const
                {
                        return (&**this);
                }

        protected:
                ListItem* itsItem;
                LookTLList<tBody>* itsList;
        };

        typedef reverse_iterator const_reverse_iterator;

        reverse_iterator rbegin( void ) const
        {
                return reverse_iterator( this, NULL );
        }

        reverse_iterator rend( void ) const
        {
                return reverse_iterator( this, itsFirstItem );
        }

        iterator begin( void ) const
        {
                return iterator( this, itsFirstItem );
        }

        iterator end( void ) const
        {
                return iterator( this, NULL );
        }


        iterator insert( iterator anIt, const tBody& theThing )
        {
                if( anIt == end() )
                {
                        append( theThing );
                        return (--end());  // apologies for prefix--
                }
                else if( anIt == begin() )
                {
                        prepend( theThing );
                        return begin();
                }
                
                ListItem* aCurrentItem = anIt.itsItem;

                ListItem *aNewItem = new ListItem( theThing,
                        aCurrentItem->itsPrevious,
                        aCurrentItem );
                if( aCurrentItem->itsPrevious != NULL)
                {
                        aCurrentItem->itsPrevious->itsNext = aNewItem;
                }

                aCurrentItem->itsPrevious = aNewItem;
                
                itsNumberOfItems++;
                InvalidateMemoryIterator();

                return iterator( this, aNewItem );
        }

        iterator erase( iterator anIt )
        {
                ListItem* aCurrentItem = anIt.itsItem;

                if( aCurrentItem->itsPrevious != NULL )
                {
                        aCurrentItem->itsPrevious->itsNext =
                                aCurrentItem->itsNext;
                }
                else
                {
                        itsFirstItem = aCurrentItem->itsNext;
                }
                if( aCurrentItem->itsNext != NULL )
                {
                        aCurrentItem->itsNext->itsPrevious =
                                aCurrentItem->itsPrevious;
                }
                else
                {
                        itsLastItem = aCurrentItem->itsPrevious;
                }
                
                iterator returnIt( this, aCurrentItem->itsNext );

                delete aCurrentItem;
                
                itsNumberOfItems--;
                InvalidateMemoryIterator();

                return returnIt;
        }

        iterator erase(iterator first, iterator last)
        {
                while( first != last )
                {
                        first = erase( first );
                }
                return first;
        }

// Clear the list calling the destructor for the tBodys.
        void clear( void )
        {
                erase( begin(), end() );
        }

        LookTLList()
                :       itsFirstItem( NULL ),
                itsLastItem( NULL ),
                itsMemoryItem( NULL ),
                itsMemoryItemNumber( 0 ),
                itsNumberOfItems( 0 )
        {
        }
        
        ~LookTLList()
        {
                clear();
        }
        
        // STL named methods

        void push_back( const tBody &a )
        {
                append( a );
        }

        void push_front( const tBody &a )
        {
                prepend( a );
        }

        void pop_back( void )
        {
                erase( --end() );
        }

        void pop_front( void )
        {
                erase( begin() );
        }

        tBody& back( void )
        {
                return (*(--end()));
        }

        tBody& front( void )
        {
                return (*begin());
        }


        void pushIfAbsent( const tBody &a )
        {
                iterator anIter = begin();
                for (; anIter != end(); anIter++) {
                        if (*anIter == a) return;       // do nothing if found
                }
                push_back(a);
        }

        // Return the tBody at the specified position.
        // 'memory' bits to avoid unnecessary list traversal

        tBody& at( size_t i ) const
        {
                MoveMemoryIteratorToItemAt( i );
                return itsMemoryItem->itsItem;
        }

        size_t size( void ) const
        {
                return itsNumberOfItems;
        }

        tBody& operator[]( size_t i ) const
        {
                return at( i );
        }

        void assign( const_iterator first, const_iterator last )
        {
                clear();
                for( ; first != last; first++ )
                {
                        push_back( *first );
                }
        }

        bool empty( void )
        {
                return( itsNumberOfItems == 0 );
        }

        typedef tBody value_type;
};


} // end of "look" namespace
#endif

---