spl/collection/List.h

/*
 *   This file is part of the Standard Portable Library (SPL).
 *
 *   SPL is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   SPL 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 General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with SPL.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef _tlist_h
#define _tlist_h

#include <spl/types.h>
#include <spl/Debug.h>

#include <spl/collection/Array.h>
#include <spl/Compare.h>
#include <spl/Exception.h>
#include <spl/collection/IEnumerable.h>
#include <spl/IIterator.h>
#include <spl/math/Math.h>
#include <spl/Memory.h>
#include <spl/RefCountPtr.h>

template<typename T>
class _listnode
{
public:
        _listnode *next;
        _listnode *prev;
        T data;
};

template<typename T>
class List : public IEnumerable<T>
{
private:
        inline void _Init()
        {
                m_head.data = T();
                m_head.next = &m_tail;
                m_head.prev = NULL;
                m_tail.data = T();
                m_tail.next = NULL;
                m_tail.prev = &m_head;
                m_count = 0;
        }

protected:
        _listnode<T> m_head;
        _listnode<T> m_tail;
        int m_count;

public:
        class Iterator : public IIterator<T>
        {
                friend class List<T>;

        private:
                _listnode<T> *m_current;

        public:
                Iterator()
                : m_current(NULL)
                {
                }

                Iterator(_listnode<T> *head)
                : m_current(head)
                {
                }

                Iterator(const Iterator& li)
                : m_current(li.m_current)
                {
                }

                virtual bool Next( )
                {
                        if (NULL == m_current || NULL == m_current->next)
                        {
                                // m_current is the tail node
                                return false;
                        }
                        m_current = m_current->next;
                        if (NULL == m_current->next)
                        {
                                // m_current is the tail node
                                return false;
                        }

                        ASSERT_MEM( m_current, sizeof( _listnode<T> ) );
                        return true;
                }

                virtual bool Prev( )
                {
                        if (NULL == m_current || NULL == m_current->prev)
                        {
                                // Head
                                return false;
                        }
                        m_current = m_current->prev;
                        if (NULL == m_current->prev)
                        {
                                // Head
                                return false;
                        }
                        return true;
                }

                virtual T Current()
                {
                        ASSERT_MEM( m_current, sizeof( _listnode<T> ) );
                        return m_current->data;
                }

                virtual T& CurrentRef()
                {
                        ASSERT_MEM( m_current, sizeof( _listnode<T> ) );
                        return m_current->data;
                }
        };
        
        List()
        {
                _Init();
        }

        List( const List<T>& list )
        {
                _Init();

                _listnode<T> *node = list.m_head.next;
                while ( node != &list.m_tail )
                {
                        ASSERT_MEM( node, sizeof( _listnode<T> ) );
                        Add( node->data );
                        node = node->next;
                }
        }

        ~List()
        {
                Clear();
        }

        List<T>& operator =( const List<T>& list )
        {
                Clear();

                _listnode<T> *node = list.m_head.next;
                while ( node != &list.m_tail )
                {
                        Add( node->data );
                        node = node->next;
                }
                return *this;
        }

        bool IsEmpty(  ) const
        {
                return m_head.next == &m_tail;
        }

        void Clear(  )
        {
                _listnode<T> *np;
                _listnode<T> *npnext;

                np = m_head.next;

                while ( np != &m_tail )
                {
                        ASSERT_MEM( np, sizeof( _listnode<T> ) );
                        npnext = np->next;
                        delete np;
                        np = npnext;
                }
                m_head.next = &m_tail;
                m_count = 0;
                ASSERT( IsEmpty(  ) );
        }

        void Add( T data )
        {
                _listnode<T> *np;
                np = new _listnode<T>();
                np->data = data;
                np->next = m_head.next;
                np->prev = &m_head;
                m_head.next->prev = np;
                m_head.next = np;
                m_count++;
        }

        inline Iterator Begin()
        {
                return Iterator(&m_head);
        }

        T& ElementAt( const int index ) const
        {
                int count = 0;
                _listnode<T> *np;

                np = m_head.next;
                while ( np != &m_tail && count < index )
                {
                        np = np->next;
                        count++;
                }
                if ( np == &m_tail )
                {
                        throw IndexOutOfBoundsException();
                }
                return np->data;
        }

        inline T& operator[] (const int idx) const
        {
                return ElementAt(idx);
        }

        void RemoveCurrent( Iterator& iter )
        {
                _listnode<T> *newcur = iter.m_current->prev;
                ASSERT( iter.m_current != &m_head && iter.m_current != &m_tail && iter.m_current != NULL );
                iter.m_current->prev->next = iter.m_current->next;
                iter.m_current->next->prev = iter.m_current->prev;
                ASSERT_MEM( iter.m_current, sizeof( _listnode<T> ) );
                delete iter.m_current;
                iter.m_current = newcur;
                m_count--;
        }

        T Pop()
        {
                _listnode<T> *cur = m_head.next;
                ASSERT( cur != &m_tail );
                m_head.next = cur->next;
                cur->next->prev = &m_head;
                T data = cur->data;
                m_count--;
                delete cur;
                return data;
        }

        T Peek() const
        {
                _listnode<T> *cur = m_head.next;
                if( cur == &m_tail )
                {
                        return NULL;
                }
                return cur->data;
        }

        T& PeekRef() const
        {
                _listnode<T> *cur = m_head.next;
                if( cur == &m_tail )
                {
                        return T();
                }
                return cur->data;
        }

        T Tail() const
        {
                _listnode<T> *cur = m_tail.prev;
                if( cur == &m_head )
                {
                        return T();
                }
                return cur->data;
        }

        T& TailRef() const
        {
                _listnode<T> *cur = m_tail.prev;
                if( cur == &m_head )
                {
                        return T();
                }
                return cur->data;
        }

        void RemoveTail(  )
        {
                _listnode<T> *cur = m_tail.prev;
                ASSERT( cur != &m_head && cur != &m_tail && cur != NULL );
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
                ASSERT_MEM( cur, sizeof( _listnode<T> ) );
                delete cur;
                m_count--;
        }

        void Remove( const T& data )
        {
                int count = 0;
                _listnode<T> *np;

                np = m_head.next;
                while ( np != &m_tail )
                {
                        if ( Compare::Equals(data, np->data) )
                        {
                                np->prev->next = np->next;
                                np->next->prev = np->prev;
                                ASSERT_MEM( np, sizeof( _listnode<T> ) );
                                delete np;
                                m_count--;
                                return;
                        }
                        np = np->next;
                        count++;
                }
        }

        inline int Count(  ) const
        {
                return m_count;
        }

        RefCountPtr<Array<T> > ToArray() const
        {
                RefCountPtr<Array<T> > ap(new Array<T>(m_count));

                Iterator iter = Begin();
                int pos = 0;
                while (iter.Next())
                {
                        ap->SetElementAt(pos++, iter.Current());
                }
                return ap;
        }

#ifdef DEBUG
        void ValidateMem() const
        {
                _listnode<T> *np = m_head.next;
                while ( np != &m_tail )
                {
                        ASSERT_MEM( np, sizeof(_listnode<T>) );
                        ValidateType( np->data );
                        np = np->next;
                }
                ValidateType(m_head.data);
                ValidateType(m_tail.data);
        }

        void CheckMem() const
        {
                _listnode<T> *np = m_head.next;
                while ( np != &m_tail )
                {
                        DEBUG_NOTE_MEM_ALLOCATION( np );
                        ValidateType( np->data );
                        np = np->next;
                }
                ValidateType(m_head.data);
                ValidateType(m_tail.data);
        }
#else
        inline void ValidateMem() const {}
        inline void CheckMem() const {}
#endif

protected:
        virtual RefCountPtr<IIterator<T> > IteratorPtr()
        {
                return RefCountPtr<IIterator<T> >(new Iterator(&m_head));
        }
};

REGISTER_TYPEOF( 300, List<char> );
REGISTER_TYPEOF( 301, List<byte> );
REGISTER_TYPEOF( 302, List<int16> );
REGISTER_TYPEOF( 303, List<uint16> );
REGISTER_TYPEOF( 304, List<int32> );
REGISTER_TYPEOF( 305, List<uint32> );
REGISTER_TYPEOF( 306, List<int64> );
REGISTER_TYPEOF( 307, List<uint64> );
REGISTER_TYPEOF( 308, List<float32> );
REGISTER_TYPEOF( 309, List<float64> );

REGISTER_TYPEOF( 310, List<BigInteger> );
REGISTER_TYPEOF( 311, List<Char> );
REGISTER_TYPEOF( 312, List<Date> );
REGISTER_TYPEOF( 313, List<DateTime> );
REGISTER_TYPEOF( 314, List<Decimal> );
REGISTER_TYPEOF( 315, List<Double> );
REGISTER_TYPEOF( 316, List<Int32> );
REGISTER_TYPEOF( 317, List<Int64> );
REGISTER_TYPEOF( 318, List<Null> );
REGISTER_TYPEOF( 319, List<String> );
REGISTER_TYPEOF( 320, List<StringPtr> );
REGISTER_TYPEOF( 321, List<UInt32> );
REGISTER_TYPEOF( 322, List<UInt64> );
REGISTER_TYPEOF( 323, List<Undefined> );

#endif