F:/My Projects/LSEngine/Modules/LSTL/Src/LinkedList/LSTLLinkedList.h

#ifndef __LSTL_LINKEDLIST_H__
#define __LSTL_LINKEDLIST_H__

#include "../LSTLib.h"
#include "LSTLLinkedListBase.h"
#include <new>

namespace lstl {

        template <typename _tType>
        class CLinkedList : protected CLinkedListBase {
        public :
                // == Various constructors.
                LSE_CALL                                                                CLinkedList() :
                        m_lpllnHead( NULL ),
                        m_lpllnTail( NULL ),
                        m_paOurAllocator( &Parent::m_aAllocator ) {
                }
                LSE_CALL                                                                ~CLinkedList() {
                        Reset();
                }


                // == Types.
                typedef struct LSTL_LINKED_LIST_NODE {
                        _tType                                                          tLinkedListObject;

                        LSTL_LINKED_LIST_NODE *                         pllnLinkedListNext;

                        LSTL_LINKED_LIST_NODE *                         pllnLinkedListPrev;
                } * LPLSTL_LINKED_LIST_NODE, * const LPCLSTL_LINKED_LIST_NODE;


                // == Functions.
                LSVOID LSE_CALL                                                 SetAllocator( CAllocator * _paAllocator ) {
                        Reset();
                        m_paOurAllocator = _paAllocator;
                        if ( !m_paOurAllocator ) {
                                m_paOurAllocator = &Parent::m_aAllocator;
                        }
                }

                CAllocator * LSE_CALL                                   GetAllocator() {
                        return m_paOurAllocator;
                }

                LSVOID LSE_CALL                                                 Reset() {
                        LPLSTL_LINKED_LIST_NODE lpllnNext = NULL;
                        for ( LPLSTL_LINKED_LIST_NODE lpllnThis = m_lpllnHead;
                                lpllnThis; lpllnThis = lpllnNext ) {
                                lpllnNext = lpllnThis->pllnLinkedListNext;
                                Destroy( (*lpllnThis) );
                                m_paOurAllocator->Free( lpllnThis );
                        }

                        m_lpllnHead = m_lpllnTail = NULL;
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                InsertAfter( const _tType &_tNew, LPLSTL_LINKED_LIST_NODE _lpllnNode ) {
                        LPLSTL_LINKED_LIST_NODE lpllnNew = NewNode();
                        if ( !lpllnNew ) { return NULL; }
                        Construct( (*lpllnNew) );
                        lpllnNew->tLinkedListObject = _tNew;

                        if ( !_lpllnNode ) {
                                // Insert at the head.
                                if ( m_lpllnHead ) {
                                        lpllnNew->pllnLinkedListNext = m_lpllnHead;
                                }
                        }
                        else {
                                // Otherwise it goes after some item or another.
                                lpllnNew->pllnLinkedListNext = _lpllnNode->pllnLinkedListNext;
                                lpllnNew->pllnLinkedListPrev = _lpllnNode;
                        }

                        // Fix the links in the objects surrounding this one.
                        if ( lpllnNew->pllnLinkedListNext ) {
                                lpllnNew->pllnLinkedListNext->pllnLinkedListPrev = lpllnNew;
                        }
                        else {
                                // At the tail.
                                m_lpllnTail = lpllnNew;
                        }

                        if ( lpllnNew->pllnLinkedListPrev ) {
                                lpllnNew->pllnLinkedListPrev->pllnLinkedListNext = lpllnNew;
                        }
                        else {
                                // At the head.
                                m_lpllnHead = lpllnNew;
                        }

                        return lpllnNew;
                }

                LSVOID LSE_CALL                                                 RemoveItem( LPLSTL_LINKED_LIST_NODE _lpllnNode ) {
                        if ( !_lpllnNode ) { return; }
                        // Unlink the object.
                        if ( _lpllnNode->pllnLinkedListPrev ) {
                                _lpllnNode->pllnLinkedListPrev->pllnLinkedListNext = _lpllnNode->pllnLinkedListNext;
                        }
                        else {
                                // At the head.
                                m_lpllnHead = _lpllnNode->pllnLinkedListNext;
                        }

                        if ( _lpllnNode->pllnLinkedListNext ) {
                                _lpllnNode->pllnLinkedListNext->pllnLinkedListPrev = _lpllnNode->pllnLinkedListPrev;
                        }
                        else {
                                // At the tail.
                                m_lpllnTail = _lpllnNode->pllnLinkedListPrev;
                        }

                        Destroy( (*_lpllnNode) );
                        m_paOurAllocator->Free( _lpllnNode );
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                Head() {
                        return m_lpllnHead;
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                Tail() {
                        return m_lpllnTail;
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                PushFront( const _tType &_tNew ) {
                        return InsertAfter( _tNew, NULL );
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                PushBack( const _tType &_tNew ) {
                        return InsertAfter( _tNew, m_lpllnTail );
                }

                LSUINT32 LSE_CALL                                               Length() {
                        LSUINT32 ui32Len = 0UL;
                        for ( LPLSTL_LINKED_LIST_NODE lpllnThis = m_lpllnHead;
                                lpllnThis; lpllnThis = lpllnThis->pllnLinkedListNext ) {
                                ++ui32Len;
                        }
                        return ui32Len;
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                Find( const _tType &_tValue ) {
                        for ( LPLSTL_LINKED_LIST_NODE lpllnThis = m_lpllnHead;
                                lpllnThis; lpllnThis = lpllnThis->pllnLinkedListNext ) {
                                if ( lpllnThis->tLinkedListObject == _tValue ) {
                                        return lpllnThis;
                                }
                        }
                        return NULL;
                }


        protected :
                // == Members.
                LPLSTL_LINKED_LIST_NODE                                 m_lpllnHead;

                LPLSTL_LINKED_LIST_NODE                                 m_lpllnTail;

                CAllocator *                                                    m_paOurAllocator;

                
                // == Functions.
                LSVOID LSE_CALL                                                 Construct( LSTL_LINKED_LIST_NODE &_llnNode ) {
                        _llnNode.pllnLinkedListNext = _llnNode.pllnLinkedListPrev = NULL;
                        new( &_llnNode.tLinkedListObject ) _tType;
                }
                LSVOID LSE_CALL                                                 Destroy( const LSTL_LINKED_LIST_NODE &_llnNode ) {
                        // This gives warning C4100 when this class is created with types that have no destructor,
                        //      claiming _llnNode is unreferenced.
                        // Erase this warning with some do-nothing code.
                        static_cast<LSTL_LINKED_LIST_NODE>(_llnNode);
                        _llnNode.tLinkedListObject.~_tType();
                }

                LPLSTL_LINKED_LIST_NODE LSE_CALL                NewNode() {
                        return static_cast<LPLSTL_LINKED_LIST_NODE>(m_paOurAllocator->Alloc( sizeof( LSTL_LINKED_LIST_NODE ) ));
                }

        private :
                typedef CLinkedListBase                                 Parent;
        };

}       // namespace lstl

#endif  // __LSTL_LINKEDLIST_H__