sorted_list.h

 
#pragma once
 
#include "system/object.h"
#include "system/collections/ilist.h"
#include "system/collections/icomparer.h"
#include "system/collections/base_dictionary.h"
#include "system/collections/keyvalue_list.h"
#include "system/exceptions.h"
#include "system/cycles_detection.h"
 
#include <vector>
#include <utility>
#include <algorithm>
 
namespace System { namespace Collections { namespace Generic {
 
namespace Detail {
    template <typename Key, typename Mapped, typename Comparer>
    class ASPOSECPP_SHARED_CLASS FlatMap
    {
    public:
        typedef Key key_type;
        typedef Mapped mapped_type;
        typedef std::pair<key_type, mapped_type> value_type;
        typedef Comparer comparer_type;
        typedef ASPOSE_VECTOR_ALLOCATOR_TYPE(key_type, mapped_type) allocator_type;
        typedef std::vector<value_type, allocator_type> vector_type;
        typedef typename vector_type::iterator iterator;
        typedef typename vector_type::const_iterator const_iterator;
        typedef typename vector_type::reverse_iterator reverse_iterator;
        typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
        typedef typename vector_type::size_type size_type;
 
        FlatMap(const allocator_type &allocator = allocator_type()) : m_data(allocator) {}
        FlatMap(const comparer_type &cmp, const allocator_type &allocator = allocator_type()) : m_data(allocator), m_comparer(cmp) {}
        FlatMap(const FlatMap &map, const allocator_type &allocator) : m_data(map.m_data, allocator) {}
 
        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(); }
 
        mapped_type& operator [] (const key_type &key)
        {
            const iterator position = std::lower_bound(begin(), end(), key, m_comparer);
            if (position != end() && !m_comparer(key, position->first))
                return position->second;
 
            return m_data.insert(position, value_type(key, mapped_type()))->second;
        }
 
        iterator erase(const_iterator position) 
        { 
            return m_data.erase(position); 
        }
        std::pair<iterator, bool> insert(const value_type &pair)
        {
            const iterator position = std::lower_bound(begin(), end(), pair, m_comparer);
            if (position != end() && !m_comparer(pair.first, position->first))
                return std::make_pair(position, false);
 
            return std::make_pair(m_data.insert(position, pair), true);
        }
        iterator find(const key_type &key)
        {
            const iterator position = std::lower_bound(begin(), end(), key, m_comparer);
            if (position == end() || m_comparer(key, position->first))
                return end();
            else
                return position;
        }
        const_iterator find(const key_type &key) const
        {
            const const_iterator position = std::lower_bound(begin(), end(), key, m_comparer);
            if (position == end() || m_comparer(key, position->first))
                return end();
            else
                return position;
        }
        size_type count(const key_type &key) const
        {
            const const_iterator position = std::lower_bound(begin(), end(), key, m_comparer);
            if (position == end() || m_comparer(key, position->first))
                return 0;
            else
                return 1;
        }
 
        void clear()
        {
            m_data.clear();
        }
        size_type size() const
        {
            return m_data.size();
        }
 
        void reserve(size_type cnt)
        {
            m_data.reserve(cnt);
        }
        bool operator == (const FlatMap &other) const
        {
            return size() == other.size() && std::equal(begin(), end(), other.begin());
        }
 
        vector_type& data() noexcept
        {
            return m_data;
        }
 
        vector_type const& data() const noexcept
        {
            return m_data;
        }
 
        allocator_type get_allocator() const
        {
            return m_data.allocator_type();
        }
 
        size_type capacity() const
        {
            return m_data.capacity();
        }
    private:
        class value_type_comparer {
        public:
            inline value_type_comparer() {}
            inline value_type_comparer(const comparer_type &cmp) : m_comparer(cmp) {}
            template <class P, class Q>
            inline bool operator () (const P &a, const Q &b) const
            {
                return m_comparer(getKey(a), getKey(b));
            }
        private:
            static inline const key_type& getKey(const key_type &key) { return key; }
            static inline const key_type& getKey(const value_type &pair) { return pair.first; }
            comparer_type m_comparer;
        };
 
        vector_type m_data;
        value_type_comparer m_comparer;
    };
 
} // namespace Detail
 
template<typename TKey, typename TValue>
class ASPOSECPP_SHARED_CLASS SortedListHelper
{
public:
    SharedPtr<IList<TKey>> get_Keys() const
    {
        return get_KeysImpl();
    }
    SharedPtr<IList<TValue>> get_Values() const
    {
        return get_ValuesImpl();
    }
protected:
    virtual SharedPtr<IList<TKey>> get_KeysImpl() const = 0;
    virtual SharedPtr<IList<TValue>> get_ValuesImpl() const = 0;
};
 
 
template<typename TKey, typename TValue>
class ASPOSECPP_SHARED_CLASS SortedList
    : public SortedListHelper<TKey, TValue>, public BaseDictionary<Detail::FlatMap<TKey, TValue, ComparerAdapter<TKey> > >
{
    typedef SortedList<TKey, TValue> _ThisType;
    typedef SortedListHelper<TKey, TValue> _HelperType;
    typedef BaseDictionary<Detail::FlatMap<TKey, TValue, ComparerAdapter<TKey> > > _BaseType;
    RTTI_INFO_TEMPLATE_CLASS(_ThisType, System::BaseTypesInfo<_BaseType>);
 
protected:
    using _BaseType::m_map;
 
public:
    typedef ICollection<TKey>   KeyCollection;
    typedef ICollection<TValue> ValueCollection;
    typedef Detail::FlatMap<TKey, TValue, ComparerAdapter<TKey> > map_t;
    typedef SortedList<TKey, TValue> this_t;
    typedef SharedPtr<this_t> Ptr;
    typedef KeyValuePair<TKey, TValue> KVPair;
    typedef SharedPtr< IEnumerable<KVPair> > IEnumerablePtr;
    typedef SharedPtr< IEnumerator<KVPair> > IEnumeratorPtr;
 
    typedef typename _BaseType::iterator iterator;
    typedef typename _BaseType::const_iterator const_iterator;
    typedef typename map_t::reverse_iterator reverse_iterator;
    typedef typename map_t::const_reverse_iterator const_reverse_iterator;
 
    SortedList()
        : _BaseType(0, ComparerAdapter<TKey>(GetDefaultComparer<TKey>()))
    {}
    SortedList(const SharedPtr<IComparer<TKey> >& comparer)
        : _BaseType(0, ComparerAdapter<TKey>(comparer)) // use forwarding ctor
    {}
    SortedList(const SharedPtr<IDictionary<TKey, TValue> >& src)
        : _BaseType(src.get())
    {}
    SortedList(const map_t& map)
        : _BaseType(0, map) // 0 - use forwarding ctor
    {}
    SortedList(int capacity)
    {
        this->m_map.reserve(static_cast<typename map_t::size_type>(capacity));
    }
    int get_Capacity() const
    {
        return static_cast<int>(this->m_map.capacity());
    }
    void set_Capacity(int capacity)
    {
        this->m_map.reserve(capacity);
    }
 
    void RemoveAt(int index)
    {
        this->m_map.erase(this->m_map.begin() + index);
    }
    int IndexOfKey(TKey key) const
    {
        auto iter = this->m_map.find(key);
        if (iter == this->m_map.end())
            return -1;
        return ASPOSECPP_CHECKED_CAST(int, std::distance(this->m_map.begin(), iter));
    }
    int IndexOfValue(TValue value) const
    {
        for (auto iter = this->m_map.begin(); iter != this->m_map.end(); ++iter)
        {
            if (iter->second == value)
            {
                return ASPOSECPP_CHECKED_CAST(int, std::distance(this->m_map.begin(), iter));
            }
        }
        return -1;
    }
 
    class Enumerator : public SimpleEnumerator<map_t, KVPair>
    {
    public:
        Enumerator(const Ptr& dict) : SimpleEnumerator<map_t, KVPair>(dict, dict->m_map) { }
        typedef typename SortedList<TKey, TValue>::Enumerator EnumeratorType;
        RTTI_INFO_TEMPLATE_CLASS(EnumeratorType, System::BaseTypesInfo<System::Object>);
    };
    IEnumeratorPtr GetEnumerator() override
    {
        return MakeObject<Enumerator>(MakeSharedPtr(this));
    }
 
    reverse_iterator rbegin() noexcept
    {
        return m_map.rbegin();
    }
    reverse_iterator rend() noexcept
    {
        return m_map.rend();
    }
 
    const_reverse_iterator rbegin() const noexcept
    {
        return m_map.rbegin();
    }
    const_reverse_iterator rend() const noexcept
    {
        return m_map.rend();
    }
 
    const_reverse_iterator crbegin() const noexcept
    {
        return rbegin();
    }
    const_reverse_iterator crend() const noexcept
    {
        return rend();
    }
 
protected:
    ~SortedList() override {}
 
    virtual SharedPtr<KeyCollection> get_KeysInternal() const override
    {
        return get_Keys();
    }
    virtual SharedPtr<ValueCollection> get_ValuesInternal() const override
    {
        return get_Values();
    }
#ifdef ASPOSE_GET_SHARED_MEMBERS
    DEFINE_GET_SHARED_MEMBERS(_BaseType::m_map)
#endif
public:
    using _HelperType::get_Values;
    using _HelperType::get_Keys;
protected:
    SharedPtr<IList<TKey>> get_KeysImpl() const override
    {
        return MakeObject<_KeyList<SortedList<TKey, TValue>>>(MakeSharedPtr(this));
    }
    SharedPtr<IList<TValue>> get_ValuesImpl() const override
    {
        return MakeObject<_ValueList<SortedList<TKey, TValue>>>(MakeSharedPtr(this));
    }
 
private:
    template<typename T>
    class DefaultComparer : public IComparer<T>
    {
    public:
#ifdef ASPOSE_COMPARE_BY_REF
        typedef const T& args_type;
#else
        typedef T args_type;
#endif
    };
 
    template<typename T>
    class DefaultClassComparer : public DefaultComparer<T>
    {
        using args_type = typename DefaultComparer<T>::args_type;
    public:
        int32_t Compare(args_type c1, args_type c2) const override
        {
            return c1->CompareTo(c2);
        }
    };
 
    template<typename T>
    class DefaultStructComparer : public DefaultComparer<T>
    {
        using args_type = typename DefaultComparer<T>::args_type;
    public:
        int32_t Compare(args_type c1, args_type c2) const override
        {
            return c1.CompareTo(c2);
        }
    };
 
    template<typename T>
    typename std::enable_if<
        detail::has_method_compareto_via_arrow<T>::value,
        SharedPtr<IComparer<T>>
    >::type GetDefaultComparer()
    {
        return MakeObject<DefaultClassComparer<T>>();
    }
    template<typename T>
    typename std::enable_if<
        detail::has_method_compareto_via_dot<T>::value,
        SharedPtr<IComparer<T>>
    >::type GetDefaultComparer()
    {
        return MakeObject<DefaultStructComparer<T>>();
    }
    template<typename T>
    typename std::enable_if<
        !detail::has_method_compareto_via_arrow<T>::value && !detail::has_method_compareto_via_dot<T>::value,
        SharedPtr<IComparer<T>>
    >::type GetDefaultComparer()
    {
        return SharedPtr<IComparer<T> >();
    }
};
 
}}} // namespace System::Collections::Generic