Map.hpp

[詳解]

// ----------------------------------------------------------------------------
 
#pragma once
 
#include "Utility.h"
 
namespace alt
{
    namespace skeleton
    {
        template<class T>
        class MapNode
        {
        public:
            MapNode<T> ()
            {
                _prev = nullptr;
                _next = nullptr;
                _value = nullptr;
                ZeroMemory (_byMD5, sizeof (_byMD5));
            };
 
            MapNode<T> (T& value)
                :MapNode<T> ()
            {
                _value = new T (value);
                alt::Utility::CreateMD5 ((LPBYTE)_value, sizeof (T), _byMD5);
            };
 
            APIENTRY ~MapNode<T> ()
            {
                delete _value;
            };
 
            MapNode<T>* _prev;
 
            MapNode<T>* _next;
 
            T* _value;
 
            BYTE _byMD5[32];
        };
 
        template<class T>
        class MapIterator
        {
        public:
            MapIterator<T> (MapNode<T>* node)
            {
                _node = node;
            };
 
            APIENTRY ~MapIterator<T> ()
            {
                _node = nullptr;
            };
 
            T& APIENTRY operator * ()
            {
                return *(_node->_value);
            };
 
            MapIterator<T>& APIENTRY operator ++ ()
            {
                _node = _node->_next;
                return *this;
            };
 
            bool APIENTRY operator != (const MapIterator<T>& comp)
            {
                return _node != comp._node;
            };
 
        private:
            MapIterator<T> () = delete;
            MapNode<T>* _node;
        };
 
        template<class T>
        class Map
        {
        public:
            Map<T> ()
            {
                _node = new MapNode<T> ();
                _index = nullptr;
                _size = 0;
            };
 
            Map<T> (const Map<T>& base)
                : Map<T> ()
            {
                operator =(base);
            };
 
            virtual APIENTRY ~Map<T> ()
            {
                Clear ();
                delete _node;
            };
 
            VOID APIENTRY Add (T& item)
            {
                MapNode<T>* newNode = new MapNode<T> (item);
 
                if (_size == 0)
                {
                    _node->_prev = newNode;
                    _node->_next = newNode;
                }
                else
                {
                    MapNode<T>* current = _node;
 
                    while(current != NULL)
                    {
                        MapNode<T>* next = current->_next;
 
                        if (next == NULL || ::memcmp (newNode->_byMD5, next->_byMD5, 32) < 0)
                        {
                            if (next) next->_prev = newNode;
                            current->_next = newNode;
                            if (current) newNode->_prev = current;
                            if (next) newNode->_next = next;
                            break;
                        }
 
                        if (current->_next == NULL) break;
                        
                        current = current->_next;
                    }
                }
 
                _size += 1;
            };
 
            VOID APIENTRY Remove (T& item)
            {
                MapNode<T>* current = _node->_next;
 
                for (;current != NULL;)
                {
                    if (*(current->_value) == item)
                    {
                        break;
                    }
                    current = current->_next;
                }
 
                if (current != NULL)
                {
                    MapNode<T>* before = current->_prev;
                    MapNode<T>* after = current->_next;
                    if (before != NULL && before->_next != NULL) before->_next = after;
                    if (after != NULL && after->_prev != NULL) after->_prev = before;
 
                    delete current;
                    _size--;
                }
            };
 
            // for DEBUG
            MapNode<T>* GetNode (SIZE_T index)
            {
                MapNode<T>* current = _node->_next;
 
                for (INT i = 0; i < index; i++)
                {
                    if (current == nullptr)
                    {
                        break;
                    }
                    current = current->_next;
                }
 
                return current;
            };
 
            T* APIENTRY Get (SIZE_T index) const
            {
                MapNode<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 Map<T>& base)
            {
                Clear ();
 
                for (auto& itr : base)
                {
                    Add (itr);
                }
            }
 
            SIZE_T APIENTRY Size () const
            {
                return _size;
            };
 
            VOID APIENTRY Clear ()
            {
                while (_size > 0)
                {
                    MapNode<T>* node = _node->_next;
                    delete _node;
                    _node = node;
                    _size--;
                }
            };
 
            MapIterator<T> APIENTRY begin () const
            {
                return MapIterator<T> (_node->_next);
            };
 
            MapIterator<T> APIENTRY end () const
            {
                return MapIterator<T> (nullptr);
            };
 
            friend MapIterator<T>;
 
        private:
            void Balance (int left, int center, int right, MapNode<T> balance)
            {
 
            };
 
            void CreateIndex ()
            {
                SIZE_T center;
 
                if (_size % 2 == 0)
                {
                    // even
                    center = (_size + 1) / 2;
                }
                else
                {
                    // odd
                    center = _size / 2;
                }
 
                for (MapNode<T>* item = _node->_next; item != nullptr; _node = _node->_next)
                {
                    center--;
 
                    if (center == 0)
                    {
                        _index = item;
                        break;
                    }
                }
            };
 
            MapNode<T>* _node;
            MapNode<T>* _index;
            SIZE_T _size;
        };
    }
}