LinkedList.hpp

[詳解]

// ----------------------------------------------------------------------------
 
#pragma once
 
#include "WindowsLibrary.h"
 
namespace alt
{
    namespace skeleton
    {
        template<class T>
        class LinkedListNode
        {
        public:
            LinkedListNode<T> ()
            {
                _prev = nullptr;
                _next = nullptr;
                _value = nullptr;
            };
 
            LinkedListNode<T> (T& value)
                :LinkedListNode<T> ()
            {
                _value = new T (value);
            };
 
            APIENTRY ~LinkedListNode<T> ()
            {
                delete _value;
            };
 
            LinkedListNode<T>* _prev;
 
            LinkedListNode<T>* _next;
 
            T* _value;
        };
 
        template<class T>
        class LinkedListIterator
        {
        public:
            LinkedListIterator<T> (LinkedListNode<T>* node)
            {
                _node = node;
            };
 
            APIENTRY ~LinkedListIterator<T> ()
            {
                _node = nullptr;
            };
 
            T& APIENTRY operator * ()
            {
                return *(_node->_value);
            };
 
            LinkedListIterator<T>& APIENTRY operator ++ ()
            {
                _node = _node->_next;
                return *this;
            };
 
            bool APIENTRY operator != (const LinkedListIterator<T>& comp)
            {
                return _node != comp._node;
            };
 
        private:
            LinkedListIterator<T> () = delete;
            LinkedListNode<T>* _node;
        };
 
        template<class T>
        class LinkedList
        {
        public:
            LinkedList<T> ()
            {
                _node = new LinkedListNode<T> ();
                _size = 0;
            };
 
            LinkedList<T> (const LinkedList<T>& base)
                : LinkedList<T> ()
            {
                operator =(base);
            };
 
            virtual APIENTRY ~LinkedList<T> ()
            {
                Clear ();
                delete _node;
            };
 
            VOID APIENTRY AddFirst (T& item)
            {
                LinkedListNode<T>* newNode = new LinkedListNode<T> (item);
 
                if (_size == 0)
                {
                    _node->_prev = newNode;
                    _node->_next = newNode;
                }
                else
                {
                    LinkedListNode<T>* next = _node->_next;
                    _node->_next = newNode;
                    newNode->_next = next;
                    next->_prev = newNode;
                }
 
                _size++;
            };
 
            VOID APIENTRY AddLast (T& item)
            {
                LinkedListNode<T>* newNode = new LinkedListNode<T> (item);
 
                if (_size == 0)
                {
                    _node->_prev = newNode;
                    _node->_next = newNode;
                }
                else
                {
                    LinkedListNode<T>* prev = _node->_prev;
                    _node->_prev = newNode;
                    newNode->_prev = prev;
                    prev->_next = newNode;
                }
 
                _size += 1;
            };
 
            T* APIENTRY Get (SIZE_T index) const
            {
                LinkedListNode<T>* current = _node->_next;
 
                for (INT i = 0; i < index; i++)
                {
                    if (current == nullptr)
                    {
                        break;
                    }
                    current = current->_next;
                }
 
                return current != nullptr ? current->_value : nullptr;
            };
 
            T* APIENTRY operator[](SIZE_T index) const
            {
                return Get (index);
            };
 
            VOID APIENTRY operator = (const LinkedList<T>& base)
            {
                Clear ();
 
                for (auto& itr : base)
                {
                    AddLast (itr);
                }
            }
 
            VOID APIENTRY RemoveFirst ()
            {
                if (_size == 0) return;
 
                LinkedListNode<T>* node1 = _node->_next;
                LinkedListNode<T>* node2 = node1->_next;
                delete node1;
                _node->_next = node2;
 
                _size--;
            };
 
            VOID APIENTRY RemoveLast ()
            {
                if (_size == 0) return;
 
                LinkedListNode<T>* node1 = _node->_prev;
                LinkedListNode<T>* node2 = node1->_prev;
                delete node1;
                _node->_prev = node2;
 
                _size--;
            };
 
            VOID APIENTRY Remove (T& item)
            {
                LinkedListNode<T>* current = _node->_next;
                LinkedListNode<T>* before = _node;
                LinkedListNode<T>* after = current->_next;
 
                for (INT i = 0; i < _size; i++)
                {
                    if (*(current->_value) == item)
                    {
                        break;
                    }
 
                    current = current->_next;
                    if (current == nullptr)
                    {
                        break;
                    }
                    before = current->_prev;
                    after = current->_next;
                }
 
                if (current != nullptr)
                {
                    if (before != nullptr && before->_next != nullptr)
                        before->_next = after;
                    if (after != nullptr && after->_prev != nullptr)
                        after->_prev = before;
 
                    delete current;
                    _size--;
                }
            };
 
            VOID APIENTRY Enqueue (T& item)
            {
                AddLast (item);
            };
 
            bool APIENTRY Dequeue (T& item)
            {
                bool ret = true;
                T* value = Get (0);
 
                if (value != nullptr) item = *value;
                else ret = false;
 
                RemoveFirst ();
 
                return ret;
            };
 
            SIZE_T APIENTRY Size () const
            {
                return _size;
            };
 
            VOID APIENTRY Clear ()
            {
                while (_size > 0)
                {
                    LinkedListNode<T>* node = _node->_next;
                    delete _node;
                    _node = node;
                    _size--;
                }
            };
 
            LinkedListIterator<T> APIENTRY begin () const
            {
                return LinkedListIterator<T> (_node->_next);
            };
 
            LinkedListIterator<T> APIENTRY end () const
            {
                return LinkedListIterator<T> (nullptr);
            };
 
            friend LinkedListIterator<T>;
 
        private:
            LinkedListNode<T>* _node;
            SIZE_T _size;
        };
    }
}