linkedlist.h

 
#pragma once
 
#include <system/object.h>
#include <system/string.h>
#include <system/type_info.h>
#include <system/shared_ptr.h>
#include <system/exceptions.h>
#include <system/collections/ienumerator.h>
#include <system/collections/ienumerable.h>
#include <system/collections/icollection.h>
#include <system/collections/invalidatable.h>
#include <system/array.h>
 
#include <system/diagnostics/debug.h>
#include <list>
#include <unordered_map>
 
#include <type_traits>
 
namespace System { namespace Collections { namespace Generic {
 
template <typename T>
class LinkedList;
 
template <typename T>
class ASPOSECPP_SHARED_CLASS LinkedListNode final : public Object
{
    RTTI_INFO_TEMPLATE_CLASS(LinkedListNode<T>, System::BaseTypesInfo<System::Object>)
    friend class LinkedList<T>;
    typedef typename LinkedList<T>::iterator iterator;
 
    LinkedListNode(const SharedPtr<LinkedList<T>>& list, const iterator& it) : m_value(*it)
    {
        Bind(list, it);
    }
    MEMBER_FUNCTION_MAKE_OBJECT(LinkedListNode, CODEPORTING_ARGS(const SharedPtr<LinkedList<T>>& list, const iterator& it), CODEPORTING_ARGS(list, it));
 
    void Bind(const SharedPtr<LinkedList<T>>& list, const iterator& it)
    {
        list->m_ptr_node_map[&*it] = this;
        m_list = list;
        m_it = it;
    }
 
    void Unbind()
    {
        if (m_list != nullptr)
        {
            m_list->m_ptr_node_map.erase(&*m_it);
            m_list = nullptr;
            m_it = iterator();
        }
    }
 
    void UnbindNode()
    {
        if (m_list != nullptr)
        {
            m_list = nullptr;
            m_it = iterator();
        }
    }
 
    iterator CopyIterator() const
    {
        return m_it;
    }
 
public:
    LinkedListNode(const T &value) : m_value(value)
    {}
 
    SharedPtr<LinkedList<T>> get_List() const
    {
        return m_list;
    }
 
    SharedPtr<LinkedListNode<T>> get_Next() const
    {
        if (m_list != nullptr)
        {
            auto next_it = ++CopyIterator();
            if (next_it == m_list->m_data.end())
                return nullptr;
 
            return m_list->MakeSharedLinkedListNode(next_it);
        }
        else
            return nullptr;
    }
 
    SharedPtr<LinkedListNode<T>> get_Previous() const
    {
        if (m_list != nullptr && m_it != m_list->m_data.begin())
            return m_list->MakeSharedLinkedListNode(--CopyIterator());
        else
            return nullptr;
    }
 
    T get_Value() const
    {
        return m_value;
    }
 
    void set_Value(const T &value)
    {
        m_value = value;
        if (m_list != nullptr)
        {
            *m_it = value;
        }
    }
 
protected:
    ~LinkedListNode() override
    {
        if (m_list != nullptr)
        {
            m_list->m_ptr_node_map.erase(&*m_it);
        }
    }
 
#ifdef ASPOSE_GET_SHARED_MEMBERS
    void GetSharedMembers(System::Object::shared_members_type& result) const override
    {
        System::Object::GetSharedMembers(result);
 
        result.Add("System::Collections::Generic::LinkedListNode::m_list", this->m_list);
    }
#endif
 
private:
    T m_value;
    SharedPtr<LinkedList<T>> m_list;
    iterator m_it;
};
 
template <typename T>
class ASPOSECPP_SHARED_CLASS LinkedList : virtual public Object, public ICollection<T>, private Invalidatable
{
    typedef BaseTypesInfo<Object, ICollection<T>> ThisTypeBaseTypesInfo;
    RTTI_INFO_TEMPLATE_CLASS(LinkedList<T>, ThisTypeBaseTypesInfo);
    friend class LinkedListNode<T>;
    
    using Invalidatable::Invalidate;
 
    ASPOSE_COLLECTION_POINTER_MODE_CONTROL(T)
 
public:
    typedef std::list<T, typename pointer_mode_t::allocator_type> list_t;
    
    typedef typename list_t::iterator iterator;
    typedef typename list_t::const_iterator const_iterator;
    typedef typename list_t::reverse_iterator reverse_iterator;
    typedef typename list_t::const_reverse_iterator const_reverse_iterator;
 
    class Enumerator : virtual public Object, public IEnumerator<T>
    {
        typedef BaseTypesInfo<Object, IEnumerator<T>> ThisTypeBaseTypesInfo;
        RTTI_INFO_TEMPLATE_CLASS(LinkedList<T>, ThisTypeBaseTypesInfo);
        typedef typename LinkedList<T>::iterator iterator;
 
        iterator m_current;
        SharedPtr<LinkedList<T>> m_list;
        bool m_was_first_move;
        bool m_was_not_reached_end;
        InvalidatableTracker m_tracker;
 
    public:
        Enumerator(const SharedPtr<LinkedList<T>>& list) : m_list(list)
            , m_was_first_move(false)
            , m_was_not_reached_end(true), m_tracker(list.get())
        {}
 
        MakeConstRef_t<T> get_Current() const override
        {
            return *m_current;
        }
 
        bool MoveNext() override
        {
            if (!m_tracker.CheckValidity())
                throw InvalidOperationException(u"Collection was modified after the enumerator was instantiated.");
            else if (!m_was_first_move)
            {
                m_was_first_move = true;
 
                if ((m_current = m_list->begin()) != m_list->end())
                    return true;
                else
                {
                    m_was_not_reached_end = false;
                    return false;
                }
            }
            else if (m_was_not_reached_end)
            {
                if (++m_current != m_list->end())
                    return true;
                else
                {
                    m_was_not_reached_end = false;
                    return false;
                }
            }
            else
                return false;
        }
 
    protected:
        ~Enumerator() override
        {}
 
#ifdef ASPOSE_GET_SHARED_MEMBERS
        void GetSharedMembers(System::Object::shared_members_type& result) const override
        {
            System::Object::GetSharedMembers(result);
 
            result.Add("System::Collections::Generic::LinkedList::Enumerator::m_list", this->m_list);
        }
#endif
    };
 
    LinkedList() : ASPOSE_COLLECTION_INIT_ALLOCATOR(){}
 
    LinkedList(const SharedPtr<IEnumerable<T>>& collection) : ASPOSE_COLLECTION_INIT_ALLOCATOR()
    {
        if (collection == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: collection");
 
        for (auto enumerator = collection->GetEnumerator(); enumerator->MoveNext();)
        {
            m_data.emplace_back(enumerator->get_Current());
        }
    }
 
    SharedPtr<LinkedListNode<T>> get_First() const
    {
        if (m_data.empty())
            return nullptr;
        else
            return MakeSharedLinkedListNode(m_data.begin());
    }
 
    SharedPtr<LinkedListNode<T>> get_Last() const
    {
        if (m_data.empty())
            return nullptr;
        else
            return MakeSharedLinkedListNode(--m_data.end());
    }
 
    int get_Count() const override
    {
        return ASPOSECPP_CHECKED_CAST(int, m_data.size());
    }
 
    SharedPtr<LinkedListNode<T>> AddAfter(const SharedPtr<LinkedListNode<T>>& node, const T& element)
    {
        if (node == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: node");
 
        if (node->get_List().get() != this)
            throw InvalidOperationException(u"The LinkedList node does not belong to current LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(++node->CopyIterator(), element);
        return LinkedListNode<T>::MakeObject(MakeSharedPtr(this), it);
    }
 
    void AddAfter(const SharedPtr<LinkedListNode<T>>& node, const SharedPtr<LinkedListNode<T>>& newNode)
    {
        if (node == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: node");
 
        if (newNode == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: newNode");
        
        if (node->m_list.get() != this)
            throw InvalidOperationException(u"The LinkedList node does not belong to current LinkedList.");
 
        if (newNode->m_list != nullptr)
            throw InvalidOperationException(u"The LinkedList node already belongs to a LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(++node->CopyIterator(), newNode->m_value);
        newNode->Bind(MakeSharedPtr(this), it);
    }
 
    SharedPtr<LinkedListNode<T>> AddBefore(const SharedPtr<LinkedListNode<T>>& node, const T& element)
    {
        if (node == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: node");
 
        if (node->get_List().get() != this)
            throw InvalidOperationException(u"The LinkedList node does not belong to current LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(node->m_it, element);
        return LinkedListNode<T>::MakeObject(MakeSharedPtr(this), it);
    }
 
    void AddBefore(const SharedPtr<LinkedListNode<T>>& node, const SharedPtr<LinkedListNode<T>>& newNode)
    {
        if (node == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: node");
 
        if (newNode == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: newNode");
 
        if (node->m_list.get() != this)
            throw InvalidOperationException(u"The LinkedList node does not belong to current LinkedList.");
 
        if (newNode->m_list != nullptr)
            throw InvalidOperationException(u"The LinkedList node already belongs to a LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(node->m_it, newNode->m_value);
        newNode->Bind(MakeSharedPtr(this), it);
    }
 
    SharedPtr<LinkedListNode<T>> AddFirst(const T& element)
    {
        Invalidate();
 
        auto it = m_data.emplace(m_data.begin(), element);
        return LinkedListNode<T>::MakeObject(MakeSharedPtr(this), it);
    }
 
    void AddFirst(const SharedPtr<LinkedListNode<T>>& newNode)
    {
        if (newNode == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: newNode");
 
        if (newNode->m_list != nullptr)
            throw InvalidOperationException(u"The LinkedList node already belongs to a LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(m_data.begin(), newNode->m_value);
        newNode->Bind(MakeSharedPtr(this), it);
    }
 
    SharedPtr<LinkedListNode<T>> AddLast(const T& element)
    {
        Invalidate();
 
        auto it = m_data.emplace(m_data.end(), element);
        return LinkedListNode<T>::MakeObject(MakeSharedPtr(this), it);
    }
 
    void AddLast(const SharedPtr<LinkedListNode<T>>& newNode)
    {
        if (newNode == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: newNode");
 
        if (newNode->m_list != nullptr)
            throw InvalidOperationException(u"The LinkedList node already belongs to a LinkedList.");
 
        Invalidate();
 
        auto it = m_data.emplace(m_data.end(), newNode->m_value);
        newNode->Bind(MakeSharedPtr(this), it);
    }
 
    void Add(const T& element) override
    {
        AddLast(element);
    }
 
    void Clear() override
    {
        Invalidate();
 
        std::for_each(m_ptr_node_map.begin(), m_ptr_node_map.end(),
                      [](const std::pair<const T*, LinkedListNode<T>*>& it_node_pair) {
                          it_node_pair.second->UnbindNode();
                      });
        m_ptr_node_map.clear();
        m_data.clear();
    }
 
    bool Contains(const T& element) const override
    {
        return std::find(m_data.begin(), m_data.end(), element) != m_data.end();
    }
 
    void CopyTo(ArrayPtr<T> array, int index) override
    {
        if (array == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: array");
 
        if (index < 0)
            throw ArgumentOutOfRangeException(u"Index is out of range. Parameter name: index");
 
        if (array->get_Count() - index < get_Count())
            throw ArgumentException(u"Insufficient space in the target location to copy the information.");
 
        std::copy(m_data.begin(), m_data.end(), array.begin() + index);
    }
 
    SharedPtr<LinkedListNode<T>> Find(const T& element) const
    {
        auto it = std::find(m_data.begin(), m_data.end(), element);
        if (it == m_data.end())
            return nullptr;
        else
            return MakeSharedLinkedListNode(it);
    }
 
    SharedPtr<LinkedListNode<T>> FindLast(const T& element) const
    {
        auto rit = std::find(m_data.rbegin(), m_data.rend(), element);
        if (rit == m_data.rend())
            return nullptr;
        else
            return MakeSharedLinkedListNode(--rit.base());
    }
 
    SharedPtr<IEnumerator<T>> GetEnumerator() override
    {
        return MakeObject<Enumerator>(MakeSharedPtr(this));
    }
 
    bool Remove(const T& element) override
    {
        auto it = std::find(m_data.begin(), m_data.end(), element);
        if (it == m_data.end())
            return false;
        else
        {
            Invalidate();
 
            auto ptr_node_it = m_ptr_node_map.find(&*it);
            if (ptr_node_it != m_ptr_node_map.end())
            {
                ptr_node_it->second->Unbind();
            }
 
            m_data.erase(it);
            return true;
        }
    }
 
    void Remove(const SharedPtr<LinkedListNode<T>>& node)
    {
        if (node == nullptr)
            throw ArgumentNullException(u"Value cannot be null. Parameter name: node");
 
        if (node->m_list.get() != this)
            throw InvalidOperationException(u"The LinkedList node does not belong to current LinkedList.");
 
        Invalidate();
 
        auto it = node->m_it;
        node->Unbind();
        m_data.erase(it);
    }
 
    void RemoveFirst()
    {
        if (m_data.empty())
            throw InvalidOperationException(u"The LinkedList is empty.");
 
        Invalidate();
 
        auto ptr_node_it = m_ptr_node_map.find(&*m_data.begin());
        if (ptr_node_it != m_ptr_node_map.end())
        {
            ptr_node_it->second->Unbind();
        }
 
        m_data.pop_front();
    }
 
    void RemoveLast()
    {
        if (m_data.empty())
            throw InvalidOperationException(u"The LinkedList is empty.");
        
        Invalidate();
 
        auto ptr_node_it = m_ptr_node_map.find(&*--m_data.end());
        if (ptr_node_it != m_ptr_node_map.end())
        {
            ptr_node_it->second->Unbind();
        }
 
        m_data.pop_back();
    }
 
    iterator begin() noexcept
    {
        return m_data.begin();
    }
    iterator end() noexcept
    {
        return m_data.end();
    }
 
    const_iterator begin() const noexcept
    {
        return m_data.begin();
    }
    const_iterator end() const noexcept
    {
        return m_data.end();
    }
 
    const_iterator cbegin() const noexcept
    {
        return m_data.cbegin();
    }
    const_iterator cend() const noexcept
    {
        return m_data.cend();
    }
 
    reverse_iterator rbegin() noexcept
    {
        return m_data.rbegin();
    }
    reverse_iterator rend() noexcept
    {
        return m_data.rend();
    }
 
    const_reverse_iterator rbegin() const noexcept
    {
        return m_data.rbegin();
    }
    const_reverse_iterator rend() const noexcept
    {
        return m_data.rend();
    }
 
    const_reverse_iterator crbegin() const noexcept
    {
        return m_data.crbegin();
    }
    const_reverse_iterator crend() const noexcept
    {
        return m_data.crend();
    }
 
    System::Details::VirtualizedIteratorBase<T>* virtualizeBeginIterator() override
    {
        return new System::Details::NativeIteratorWrapper<T, iterator>(begin(), end());
    }
    System::Details::VirtualizedIteratorBase<T>* virtualizeEndIterator() override
    {
        return new System::Details::NativeIteratorWrapper<T, iterator>(end(), end());
    }
    System::Details::VirtualizedIteratorBase<T>* virtualizeBeginConstIterator() const override
    {
        return new System::Details::NativeConstIteratorWrapper<T, const_iterator>(begin(), end());
    }
    System::Details::VirtualizedIteratorBase<T>* virtualizeEndConstIterator() const override
    {
        return new System::Details::NativeConstIteratorWrapper<T, const_iterator>(end(), end());
    }
 
#ifdef __DBG_FOR_EACH_MEMBER
    void DBG_for_each_member(DBG::for_each_member_visitor& visitor) const override
    {
        visitor.add_self(this);
        DBG::for_each_of_Object(this, m_data, visitor);
    }
 
    const char* DBG_class_name() const override { return "LinkedList<T>"; }
#endif
 
protected:
    ~LinkedList() override
    {}
 
#ifdef ASPOSE_GET_SHARED_MEMBERS
    DEFINE_GET_SHARED_MEMBERS(m_data)
#endif
 
private:
    SharedPtr<LinkedListNode<T>> MakeSharedLinkedListNode(iterator it) const
    {
        auto ptr_node_it = m_ptr_node_map.find(&*it);
        if (ptr_node_it != m_ptr_node_map.end())
            return MakeSharedPtr(ptr_node_it->second);
        else
            return LinkedListNode<T>::MakeObject(MakeSharedPtr(this), it);
    }
 
    mutable list_t m_data;
    std::unordered_map<const T*, LinkedListNode<T>*> m_ptr_node_map;
};
 
}}} // namespace System::Collections::Generic