path: root/src/stable/list.h

/*
 * Copyright (C) 2007-2014 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 <memory>
#include "bu/exceptionbase.h"
#include "bu/sharedcore.h"
#include "bu/archivebase.h"
#include "bu/heap.h"

namespace Bu
{
    /** @cond DEVEL */
    template<typename value>
    struct ListLink
    {
        value *pValue;
        ListLink *pNext;
        ListLink *pPrev;
    };

    template<typename value, typename valuealloc, typename linkalloc>
    class List;

    template<typename value, typename valuealloc, typename linkalloc>
    struct ListCore
    {
    friend class List<value, valuealloc, linkalloc>;
    friend class SharedCore<
        List<value, valuealloc, linkalloc>,
        ListCore<value, valuealloc, linkalloc>
        >;
    private:
        typedef struct ListLink<value> Link;
        ListCore() :
            pFirst( NULL ),
            pLast( NULL ),
            nSize( 0 )
        { }

        virtual ~ListCore()
        {
            clear();
        }

        Link *pFirst;
        Link *pLast;
        long nSize;
        linkalloc la;
        valuealloc va;
        
        /**
         * Append a value to the list.
         *@param v (const value_type &) The value to append.
         */
        Link *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;
            }
            return pNew;
        }
        
        /**
         * Prepend a value to the list.
         *@param v (const value_type &) The value to prepend.
         */
        Link *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;
            }
            return pNew;
        }
        
        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;
        }
        
        Link *insert( Link *pLink, const value &v )
        {
            Link *pAfter = pLink;
            if( pAfter == NULL )
            {
                return append( v );
            }
            Link *pPrev = pAfter->pPrev;
            if( pPrev == NULL )
            {
                return prepend( v );
            }

            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;

            return pNew;
        }

        /**
         * Erase an item from the list.
         *@param i (iterator) The item to erase.
         */
        void erase( Link *pLink )
        {
            Link *pCur = 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;
                else
                    pLast = pPrev;
                nSize--;
            }
        }
    };
    /** @endcond */

    /**
     * Linked list template container.  This class is similar to the stl list
     * class except for a few minor changes.  First, when const, all
     * members are only accessable const.  Second, erasing a location does not
     * invalidate the iterator used, it simply points to the next valid
     * location, or end() if there are no more.  Other iterators pointing to
     * the deleted record will, of course, no longer be valid.
     *
     *@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.
     *@extends SharedCore
     *@ingroup Containers
     */
    template<typename value, typename valuealloc=std::allocator<value>,
        typename linkalloc=std::allocator<struct ListLink<value> > >
    class List /** @cond */ : public SharedCore<
                 List<value, valuealloc, linkalloc>,
                 ListCore<value, valuealloc, linkalloc>
                 > /** @endcond */
    {
    private:
        typedef struct ListLink<value> Link;
        typedef class List<value, valuealloc, linkalloc> MyType;
        typedef struct ListCore<value, valuealloc, linkalloc> Core;

    protected:
        using SharedCore<MyType, Core>::core;
        using SharedCore<MyType, Core>::_hardCopy;
        using SharedCore<MyType, Core>::_allocateCore;

    public:
        class const_iterator;
        class iterator;

        List()
        {
        }

        List( const MyType &src ) :
            SharedCore<MyType, Core >( src )
        {
        }
        
        List( const value &v )
        {
            append( v );
        }

        ~List()
        {
        }

        MyType &operator+=( const value &v )
        {
            _hardCopy();
            append( v );
            return *this;
        }

        MyType &operator-=( const value &v )
        {
            return erase( v );
        }

        MyType &operator+=( const MyType &src )
        {
            _hardCopy();
            append( src );
            return *this;
        }
        
        MyType operator+( const MyType &src )
        {
            MyType lNew( *this );
            lNew += src;
            return lNew;
        }

        bool operator==( const MyType &rhs ) const
        {
            if( getSize() != rhs.getSize() )
                return false;

            for( typename MyType::const_iterator a = begin(), b = rhs.begin();
                 a; a++, b++ )
            {
                if( *a != *b )
                    return false;
            }

            return true;
        }

        bool operator!=( const MyType &rhs ) const
        {
            return !(*this == rhs);
        }

        /**
         * Clear the data from the list.
         */
        void clear()
        {
            _hardCopy();
            core->clear();
        }

        MyType &enqueue( const value &v )
        {
            _hardCopy();
            append( v );

            return *this;
        }

        value dequeue()
        {
            // _hardCopy();  erase will call this for me
            value v = *core->pFirst->pValue;

            erase( begin() );

            return v;
        }

        MyType &push( const value &v )
        {
            _hardCopy();
            prepend( v );

            return *this;
        }

        MyType &pop()
        {
            _hardCopy();
            erase( begin() );

            return *this;
        }

        value peekPop()
        {
            value v = first();
            pop();
            return v;
        }

        value &peek()
        {
            return first();
        }

        /**
         * Append a value to the list.
         *@param v (const value_type &) The value to append.
         */
        MyType &append( const value &v )
        {
            _hardCopy();
            core->append( v );

            return *this;
        }

        MyType &append( const MyType &rSrc )
        {
            _hardCopy();
            for( typename MyType::const_iterator i = rSrc.begin();
                 i != rSrc.end(); i++ )
            {
                core->append( *i );
            }

            return *this;
        }

        /**
         * Prepend a value to the list.
         *@param v (const value_type &) The value to prepend.
         */
        MyType &prepend( const value &v )
        {
            _hardCopy();
            core->prepend( v );

            return *this;
        }

        /**
         * Prepend another list to the front of this one.  This will prepend
         * the rSrc list in reverse order...I may fix that later.
         */
        MyType &prepend( const MyType &rSrc )
        {
            _hardCopy();
            for( typename MyType::const_iterator i = rSrc.begin();
                 i != rSrc.end(); i++ )
            {
                core->prepend( *i );
            }

            return *this;
        }

        MyType &insert( MyType::iterator &i, const value &v )
        {
            _hardCopy();

            core->insert( i.pLink, v );

            return *this;
        }

        template<typename cmptype>
        void sort( cmptype cmp )
        {
            Heap<value, cmptype, valuealloc> hSort( cmp, getSize() );
            for( typename MyType::iterator i = begin(); i; i++ )
            {
                hSort.enqueue( *i );
            }
            clear();
            while( !hSort.isEmpty() )
            {
                append( hSort.dequeue() );
            }
        }

        void sort()
        {
            sort<__basicLTCmp<value> >();
        }

        template<typename cmptype>
        void sort()
        {
            Heap<value, cmptype, valuealloc> hSort( getSize() );
            for( typename MyType::iterator i = begin(); i; i++ )
            {
                hSort.enqueue( *i );
            }
            clear();
            while( !hSort.isEmpty() )
            {
                append( hSort.dequeue() );
            }
        }

        /**
         * 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.
         */
        template<typename cmptype>
        iterator insertSorted( cmptype cmp, const value &v )
        {
            _hardCopy();
            if( core->pFirst == NULL )
            {
                // Empty list
                return iterator( core->append( v ) );
            }
            else
            {
                Link *pCur = core->pFirst;
                for(;;)
                {
                    if( cmp( v, *(pCur->pValue)) )
                    {
                        return iterator( core->insert( pCur, v ) );
                    }
                    pCur = pCur->pNext;
                    if( pCur == NULL )
                    {
                        return iterator( core->append( v ) );
                    }
                }
            }
        }
        
        iterator insertSorted( const value &v )
        {
            return insertSorted<__basicLTCmp<value> >( v );
        }

        template<typename cmptype>
        iterator insertSorted( const value &v )
        {
            cmptype cmp;
            return insertSorted( cmp, v );
        }

        /**
         * An iterator to iterate through your list.
         */
        class iterator
        {
            friend class const_iterator;
            friend class List<value, valuealloc, linkalloc>;
        private:
            Link *pLink;

            iterator( Link *pLink ) :
                pLink( pLink )
            {
            }

        public:
            iterator() :
                pLink( NULL )
            {
            }

            iterator( const iterator &i ) :
                pLink( i.pLink )
            {
            }

            /**
             * 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 )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past end of list.");
                pLink = pLink->pNext;
                return *this;
            }

            iterator &operator--()
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past begining of list.");
                pLink = pLink->pPrev;
                return *this;
            }
            
            iterator &operator++( int )
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past end of list.");
                pLink = pLink->pNext;
                return *this;
            }

            iterator &operator--( int )
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past begining of list.");
                pLink = pLink->pPrev;
                return *this;
            }

            iterator operator+( int iDelta )
            {
                iterator ret( *this );
                for( int j = 0; j < iDelta; j++ )
                {
                    if( ret.pLink == NULL )
                        throw Bu::ExceptionBase(
                            "Attempt to iterate past begining of list.");
                    ret.pLink = ret.pLink->pNext;
                }
                return ret;
            }

            iterator operator-( int iDelta )
            {
                iterator ret( *this );
                for( int j = 0; j < iDelta; j++ )
                {
                    if( ret.pLink == NULL )
                        throw Bu::ExceptionBase(
                            "Attempt to iterate past begining of list.");
                    ret.pLink = ret.pLink->pPrev;
                }
                return ret;
            }

            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;
            }
        };
        
        /**
         *@see iterator
         */
        class const_iterator
        {
            friend class List<value, valuealloc, linkalloc>;
        private:
            Link *pLink;

            const_iterator( Link *pLink ) :
                pLink( pLink )
            {
            }

        public:
            const_iterator() :
                pLink( NULL )
            {
            }

            const_iterator( const iterator &i ) :
                pLink( i.pLink )
            {
            }

            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 )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past end of list.");
                pLink = pLink->pNext;
                return *this;
            }

            const_iterator &operator--()
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past begining of list.");
                pLink = pLink->pPrev;
                return *this;
            }
            
            const_iterator &operator++( int )
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past end of list.");
                pLink = pLink->pNext;
                return *this;
            }

            const_iterator &operator--( int )
            {
                if( pLink == NULL )
                    throw Bu::ExceptionBase(
                        "Attempt to iterate past begining of list.");
                pLink = pLink->pPrev;
                return *this;
            }

            const_iterator operator+( int iDelta )
            {
                const_iterator ret( *this );
                for( int j = 0; j < iDelta; j++ )
                {
                    if( ret.pLink == NULL )
                        throw Bu::ExceptionBase(
                            "Attempt to iterate past begining of list.");
                    ret.pLink = ret.pLink->pNext;
                }
                return ret;
            }

            const_iterator operator-( int iDelta )
            {
                const_iterator ret( *this );
                for( int j = 0; j < iDelta; j++ )
                {
                    if( ret.pLink == NULL )
                        throw Bu::ExceptionBase(
                            "Attempt to iterate past begining of list.");
                    ret.pLink = ret.pLink->pPrev;
                }
                return ret;
            }

            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;
            }
        };

        /**
         * Get an iterator pointing to the first item in the list.
         *@returns (iterator)
         */
        iterator begin()
        {
            _hardCopy();
            return iterator( core->pFirst );
        }

        /**
         * Get a const iterator pointing to the first item in the list.
         *@returns (const const_iterator)
         */
        const_iterator begin() const
        {
            return const_iterator( core->pFirst );
        }

        /**
         * Get an iterator pointing to a place just past the last item in
         *      the list.
         *@returns (const Link *)
         */
        const iterator end()
        {
            return iterator( NULL );
        }

        /**
         * 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 );
        }

        /**
         * Erase an item from the list.
         *@param i (iterator) The item to erase.
         */
        MyType &erase( iterator i )
        {
            _hardCopy();
            core->erase( i.pLink );

            return *this;
        }

        /**
         * Erase an item from the list.
         *@param i (iterator) The item to erase.
         */
        MyType &erase( const_iterator i )
        {
            _hardCopy();
            core->erase( i.pLink );

            return *this;
        }

        /**
         * Erase an item from the list if you already know the item.
         *@param v The item to find and erase.
         */
        MyType &erase( const value &v )
        {
            for( const_iterator i = begin(); i != end(); i++ )
            {
                if( (*i) == v )
                {
                    erase( i );
                    return *this;
                }
            }

            return *this;
        }
        
        /**
         * Erases the first item in the list, identical to pop, but better for
         * lists that aren't built as stacks, since you know where it will be
         * erasing from.
         */
        MyType &eraseFirst()
        {
            _hardCopy();
            erase( begin() );

            return *this;
        }
        
        /**
         * Erases the last item in the list.
         */
        MyType &eraseLast()
        {
            _hardCopy();
            core->erase( core->pLast ); 

            return *this;
        }

        iterator find( const value &v )
        {
            for( iterator i = begin(); i; i++ )
            {
                if( (*i) == v )
                    return i;
            }

            return end();
        }

        const_iterator find( const value &v ) const
        {
            for( const_iterator i = begin(); i; i++ )
            {
                if( (*i) == v )
                    return i;
            }

            return end();
        }

        /**
         * Get the current size of the list.
         *@returns (int) The current size of the list.
         */
        long getSize() const
        {
            return core->nSize;
        }

        /**
         * Get the first item in the list.
         *@returns (value_type &) The first item in the list.
         */
        value &first()
        {
            if( core->pFirst->pValue == NULL )
                throw Bu::ExceptionBase("Attempt to read first element from empty list.");
            _hardCopy();
            return *core->pFirst->pValue;
        }
        
        /**
         * Get the first item in the list.
         *@returns (const value_type &) The first item in the list.
         */
        const value &first() const
        {
            if( core->pFirst->pValue == NULL )
                throw Bu::ExceptionBase("Attempt to read first element from empty list.");
            return *core->pFirst->pValue;
        }
        
        /**
         * Get the last item in the list.
         *@returns (value_type &) The last item in the list.
         */
        value &last()
        {
            _hardCopy();
            return *core->pLast->pValue;
        }
        
        /**
         * Get the last item in the list.
         *@returns (const value_type &) The last item in the list.
         */
        const value &last() const
        {
            return *core->pLast->pValue;
        }

        bool isEmpty() const
        {
            return (core->nSize == 0);
        }
    
    protected:
        virtual Core *_copyCore( Core *src )
        {
            Core *pRet = _allocateCore();
            for( Link *pCur = src->pFirst; pCur; pCur = pCur->pNext )
            {
                pRet->append( *pCur->pValue );
            }
            return pRet;
        }

    private:
    };

    class Formatter;
    Formatter &operator<<( Formatter &rOut, const char *sStr );
    Formatter &operator<<( Formatter &rOut, signed char c );
    template<typename a, typename b, typename c>
    Formatter &operator<<( Formatter &f, const Bu::List<a,b,c> &l )
    {
        f << '[';
        for( typename Bu::List<a,b,c>::const_iterator i = l.begin(); i; i++ )
        {
            if( i != l.begin() )
                f << ", ";
            f << *i;
        }
        f << ']';

        return f;
    }

    template<typename value, typename a, typename b>
    ArchiveBase &operator<<( ArchiveBase &ar, const List<value,a,b> &h )
    {
        ar << h.getSize();
        for( typename List<value>::const_iterator i = h.begin(); i != h.end(); i++ )
        {
            ar << (*i);
        }

        return ar;
    }

    template<typename value, typename a, typename b>
    ArchiveBase &operator>>( ArchiveBase &ar, List<value,a,b> &h )
    {
        h.clear();
        long nSize;
        ar >> nSize;

        for( long j = 0; j < nSize; j++ )
        {
            value v;
            ar >> v;
            h.append( v );
        }

        return ar;
    }

}

#endif