virtualized_iterator.h

 
#pragma once
 
#include <iterator>
#include <utility>
#include <memory>
#include <system/diagnostics/debug.h>
#include <type_traits>
#include <cstring>
#include <limits>
 
#include <system/exceptions.h>
#include <system/smart_ptr.h>
#include <defines.h>
 
namespace System { namespace Collections { namespace Generic {
 
template <typename T> class IEnumerable;
 
}}} // namespace System::Collections::Generic
 
namespace System { namespace Details {
 
template <typename Element>
class VirtualizedIteratorBase
{
public:
    virtual ~VirtualizedIteratorBase() = default;
    virtual Element OffsetDereferenceIterator(std::ptrdiff_t offset) const
    {
        ASPOSE_UNUSED(offset);
        throw System::NotImplementedException(u"Iterator offset dereference");
    }
    virtual void OffsetDereferenceAssignIterator(std::ptrdiff_t offset, const Element &value) const
    {
        ASPOSE_UNUSED(offset);
        ASPOSE_UNUSED(value);
        throw System::NotImplementedException(u"Iterator offset assignment");
    }
    virtual void OffsetDereferenceAssignIterator(std::ptrdiff_t offset, Element &&value) const
    {
        ASPOSE_UNUSED(offset);
        ASPOSE_UNUSED(value);
        throw System::NotImplementedException(u"Iterator offset assignment");
    }
    virtual void IncrementIterator() = 0;
    virtual void DecrementIterator()
    {
        throw System::NotImplementedException(u"Iterator decrement");
    }
    virtual void ShiftIteratorBy(std::ptrdiff_t offset)
    {
        ASPOSE_UNUSED(offset);
        throw System::NotImplementedException(u"Iterator offset shift");
    }
    virtual bool IteratorEquals(VirtualizedIteratorBase *other) const = 0;
    virtual bool IteratorLess(VirtualizedIteratorBase *other) const
    {
        ASPOSE_UNUSED(other);
        throw System::NotImplementedException(u"Iterator less-comparison");
    }
    virtual std::ptrdiff_t DiffIterators(VirtualizedIteratorBase *other) const
    {
        ASPOSE_UNUSED(other);
        throw System::NotImplementedException(u"Iterator subtraction");
    }
    virtual VirtualizedIteratorBase* CloneIterator() const = 0;
 
    bool AssignsContainerValue() const
    {
        return m_points_to_container_element;
    }
    bool IsEndIterator() const
    {
        return m_is_end;
    }
    Element* GetElementPointer() const
    {
        return m_pointer;
    }
 
    VirtualizedIteratorBase(const VirtualizedIteratorBase&) = delete;
    VirtualizedIteratorBase(VirtualizedIteratorBase&&) = delete;
    VirtualizedIteratorBase& operator = (const VirtualizedIteratorBase&) = delete;
    VirtualizedIteratorBase& operator = (VirtualizedIteratorBase&&) = delete;
 
protected:
    VirtualizedIteratorBase(bool points_to_container_element, bool is_end_iterator)
        : m_points_to_container_element(points_to_container_element)
        , m_is_end(is_end_iterator)
    {}
 
    const bool m_points_to_container_element;
    bool m_is_end;
    Element *m_pointer;
};
 
 
template <typename Iterator>
struct UnderlyingIteratorExtractor
{
    using type = Iterator;
};
template <typename Iterator>
struct UnderlyingIteratorExtractor<std::reverse_iterator<Iterator>>
{
    using type = Iterator;
};
template <typename Iterator>
using UnderlyingIteratorType = typename UnderlyingIteratorExtractor<typename std::remove_cv<typename std::remove_reference<Iterator>::type>::type>::type;
 
 
template <typename Iterator, typename Value, typename = void>
struct IteratorOffsetDereferencer
{
    static Value get(const Iterator&, std::ptrdiff_t)
    {
        throw System::NotSupportedException(u"Iterator offset dereference");
    }
};
template <typename Iterator, typename Value>
struct IteratorOffsetDereferencer<Iterator, Value, decltype(std::declval<const UnderlyingIteratorType<Iterator>>()[std::declval<std::ptrdiff_t>()], (void)0)>
{
    static Value get(const Iterator &iterator, std::ptrdiff_t offset)
    {
        return iterator[offset];
    }
};
 
template <typename Iterator, typename Value, typename = void>
struct IteratorOffsetAssigner
{
    static void assign(const Iterator&, std::ptrdiff_t, const Value&)
    {
        throw System::NotSupportedException(u"Iterator offset assignment");
    }
};
template <typename Iterator, typename Value>
struct IteratorOffsetAssigner<Iterator, Value, decltype((void)(std::declval<const UnderlyingIteratorType<Iterator>>()[std::declval<std::ptrdiff_t>()] = std::declval<Value>()))>
{
    static void assign(const Iterator &iterator, std::ptrdiff_t offset, const Value &value)
    {
        iterator[offset] = value;
    }
    static void assign(const Iterator &iterator, std::ptrdiff_t offset, Value &&value)
    {
        iterator[offset] = std::move(value);
    }
};
 
template <typename Iterator, typename = void>
struct IteratorDecrementer
{
    static void decrement(Iterator&)
    {
        throw System::NotSupportedException(u"Iterator decrement");
    }
};
template <typename Iterator>
struct IteratorDecrementer<Iterator, decltype(--std::declval<UnderlyingIteratorType<Iterator>>(), (void)0)>
{
    static void decrement(Iterator &iterator)
    {
        --iterator;
    }
};
 
template <typename Iterator, typename = void>
struct IteratorShifter
{
    static void shift(Iterator&, std::ptrdiff_t)
    {
        throw System::NotSupportedException(u"Iterator decrement");
    }
};
template <typename Iterator>
struct IteratorShifter<Iterator, decltype(std::declval<UnderlyingIteratorType<Iterator>>() += std::declval<std::ptrdiff_t>(), (void)0)>
{
    static void shift(Iterator &iterator, std::ptrdiff_t offset)
    {
        iterator += offset;
    }
};
 
template <typename Iterator, typename = void>
struct IteratorDiffer
{
    static std::ptrdiff_t diff(const Iterator&, const Iterator&)
    {
        throw System::NotSupportedException(u"Iterator difference");
    }
};
template <typename Iterator>
struct IteratorDiffer<Iterator, decltype(std::declval<UnderlyingIteratorType<Iterator>>() - std::declval<UnderlyingIteratorType<Iterator>>(), (void)0)>
{
    static std::ptrdiff_t diff(const Iterator &lhs, const Iterator &rhs)
    {
        return lhs - rhs;
    }
};
 
template <typename Iterator, typename = void>
struct IteratorLessComparer
{
    static bool less(const Iterator&, const Iterator&)
    {
        throw System::NotSupportedException(u"Iterator less-comparison");
    }
};
template <typename Iterator>
struct IteratorLessComparer<Iterator, decltype(std::declval<UnderlyingIteratorType<Iterator>>() < std::declval<UnderlyingIteratorType<Iterator>>(), (void)0)>
{
    static bool less(const Iterator &lhs, const Iterator &rhs)
    {
        return lhs < rhs;
    }
};
 
 
template <typename Element, bool iterator_provides_direct_reference,
    bool = std::is_arithmetic<Element>::value || std::is_enum<Element>::value || IsSmartPtr<Element>::value || System::detail::is_a<Element, System::ExceptionWrapper>::value>
struct IteratorPointerUpdater
{
    void InitializeIteratorPointer(Element*&)
    {}
    void UpdateIteratorPointer(Element *&pointer, Element &value)
    {
        pointer = &value;
    }
    void UpdateIteratorPointer(Element *&pointer, const Element &value)
    {
        // This is to make const iterators compatible with VirtualizedIteratorBase interface and to avoid having separate VirtualizedConstIteratorBase one.
        // Actually, this pointer will never be used as a non-const for const iterators.
        pointer = const_cast<Element*>(&value);
    }
};
 
template <typename Element>
struct IteratorPointerUpdater<Element, false, true>
{
    void InitializeIteratorPointer(Element *&pointer)
    {
        pointer = &m_cache;
    }
    void UpdateIteratorPointer(Element*&, const Element &value)
    {
        m_cache = value;
    }
    void UpdateIteratorPointer(Element*&, Element &&value)
    {
        m_cache = std::move(value);
    }
 
    Element* HoldTemporaryObject(Element &&value)
    {
        m_cache = std::move(value);
        return &m_cache;
    }
    Element* HoldTemporaryObject(const Element &value)
    {
        m_cache = value;
        return &m_cache;
    }
    Element* HoldIfTemporary(Element &&value)
    {
        m_cache = std::move(value);
        return &m_cache;
    }
    Element* HoldIfTemporary(const Element &value)
    {
        m_cache = value;
        return &m_cache;
    }
    Element* HoldIfTemporary(Element &value)
    {
        return &value;
    }
 
    const Element& HoldAndGetReference(Element &&value) const
    {
        m_cache = std::move(value);
        return m_cache;
    }
    const Element& HoldAndGetReference(const Element &value) const
    {
        m_cache = value;
        return m_cache;
    }
    const Element& HoldIfTemporaryAndGetReference(Element &&value) const
    {
        m_cache = std::move(value);
        return m_cache;
    }
    const Element& HoldIfTemporaryAndGetReference(const Element &value) const
    {
        return value;
    }
 
private:
    mutable Element m_cache;
};
 
template <typename Element>
struct IteratorPointerUpdater<Element, false, false>
{
    IteratorPointerUpdater() = default;
    IteratorPointerUpdater(const IteratorPointerUpdater &)
        : m_allocated(false)
    {}
    ~IteratorPointerUpdater()
    {
        if (m_allocated)
            reinterpret_cast<Element&>(m_cache).~Element();
    }
    void InitializeIteratorPointer(Element *&pointer)
    {
        pointer = reinterpret_cast<Element*>(&m_cache);
    }
    void UpdateIteratorPointer(Element*&, const Element &value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(value);
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = value;
        }
    }
    void UpdateIteratorPointer(Element*&, Element &&value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(std::move(value));
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = std::move(value);
        }
    }
 
    Element* HoldTemporaryObject(Element &&value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(std::move(value));
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = std::move(value);
        }
        return reinterpret_cast<Element*>(&m_cache);
    }
    Element* HoldTemporaryObject(const Element &value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(value);
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = value;
        }
        return reinterpret_cast<Element*>(&m_cache);
    }
    Element* HoldIfTemporary(Element &&value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(std::move(value));
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = std::move(value);
        }
        return reinterpret_cast<Element*>(&m_cache);
    }
    Element* HoldIfTemporary(const Element &value)
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(value);
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = value;
        }
        return reinterpret_cast<Element*>(&m_cache);
    }
    Element* HoldIfTemporary(Element &value)
    {
        return &value;
    }
 
    const Element& HoldAndGetReference(Element &&value) const
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(std::move(value));
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = std::move(value);
        }
        return *reinterpret_cast<Element*>(&m_cache);
    }
    const Element& HoldAndGetReference(const Element &value) const
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(value);
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = value;
        }
        return *reinterpret_cast<Element*>(&m_cache);
    }
    const Element& HoldIfTemporaryAndGetReference(Element &&value) const
    {
        if (!m_allocated)
        {
            new (reinterpret_cast<Element*>(&m_cache)) Element(std::move(value));
            m_allocated = true;
        }
        else
        {
            reinterpret_cast<Element&>(m_cache) = std::move(value);
        }
        return *reinterpret_cast<Element*>(&m_cache);
    }
    const Element& HoldIfTemporaryAndGetReference(const Element &value) const
    {
        return value;
    }
 
private:
    mutable bool m_allocated = false;
    mutable typename std::aligned_storage<sizeof(Element), alignof(Element)>::type m_cache;
};
 
 
template <typename Element, typename Iterator>
class NativeIteratorWrapperBase : public VirtualizedIteratorBase<Element>
{
    static constexpr bool is_pointer_assignable = std::is_same<decltype(*std::declval<Iterator>()), Element&>::value;
 
public:
    NativeIteratorWrapperBase(const Iterator &iterator, const Iterator &end)
        : VirtualizedIteratorBase<Element>(is_pointer_assignable, iterator == end)
        , m_iterator(iterator)
        , m_end(end)
    {}
    NativeIteratorWrapperBase(Iterator &&iterator, Iterator &&end) noexcept
        : VirtualizedIteratorBase<Element>(is_pointer_assignable, iterator == end)
        , m_iterator(std::forward<Iterator>(iterator))
        , m_end(std::forward<Iterator>(end))
    {}
    virtual ~NativeIteratorWrapperBase() = default;
    bool IteratorEquals(VirtualizedIteratorBase<Element> *other) const override
    {
        CODEPORTING_DEBUG_ASSERT(dynamic_cast<NativeIteratorWrapperBase*>(other) != nullptr);
        return m_iterator == static_cast<NativeIteratorWrapperBase*>(other)->m_iterator;
    }
    bool IteratorLess(VirtualizedIteratorBase<Element> *other) const override
    {
        CODEPORTING_DEBUG_ASSERT(dynamic_cast<NativeIteratorWrapperBase*>(other) != nullptr);
        return IteratorLessComparer<Iterator>::less(m_iterator, static_cast<NativeIteratorWrapperBase*>(other)->m_iterator);
    }
    std::ptrdiff_t DiffIterators(VirtualizedIteratorBase<Element> *other) const override
    {
        CODEPORTING_DEBUG_ASSERT(dynamic_cast<NativeIteratorWrapperBase*>(other) != nullptr);
        return IteratorDiffer<Iterator>::diff(m_iterator, static_cast<NativeIteratorWrapperBase*>(other)->m_iterator);
    }
 
    NativeIteratorWrapperBase(const NativeIteratorWrapperBase&) = delete;
    NativeIteratorWrapperBase(NativeIteratorWrapperBase&&) = delete;
 
protected:
    Iterator m_iterator;
    const Iterator m_end;
 
    bool IteratorIncrementImplementation()
    {
        ++m_iterator;
        VirtualizedIteratorBase<Element>::m_is_end = m_iterator == m_end;
        if (VirtualizedIteratorBase<Element>::m_is_end)
            VirtualizedIteratorBase<Element>::m_pointer = nullptr;
        return !VirtualizedIteratorBase<Element>::m_is_end;
    }
    bool IteratorShiftImplementation(std::ptrdiff_t offset)
    {
        IteratorShifter<Iterator>::shift(m_iterator, offset);
        VirtualizedIteratorBase<Element>::m_is_end = m_iterator == m_end;
        if (VirtualizedIteratorBase<Element>::m_is_end)
            VirtualizedIteratorBase<Element>::m_pointer = nullptr;
        return !VirtualizedIteratorBase<Element>::m_is_end;
    }
};
 
 
template <typename Element, typename Iterator>
class NativeIteratorWrapper
    : public NativeIteratorWrapperBase<Element, Iterator>
    , private IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value>
{
    // Parent members to use.
    using NativeIteratorWrapperBase<Element, Iterator>::m_iterator;
    using NativeIteratorWrapperBase<Element, Iterator>::m_end;
    using VirtualizedIteratorBase<Element>::m_pointer;
    using IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value>::InitializeIteratorPointer;
    using IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value>::UpdateIteratorPointer;
 
public:
    NativeIteratorWrapper(const Iterator &iterator, const Iterator &end)
        : NativeIteratorWrapperBase<Element, Iterator>(iterator, end)
    {
        InitializeIteratorPointer(m_pointer);
        if (!VirtualizedIteratorBase<Element>::IsEndIterator())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    NativeIteratorWrapper(Iterator &&iterator, Iterator &&end) noexcept
        : NativeIteratorWrapperBase<Element, Iterator>(std::forward<Iterator>(iterator), std::forward<Iterator>(end))
    {
        InitializeIteratorPointer(m_pointer);
        if (!VirtualizedIteratorBase<Element>::IsEndIterator())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    virtual ~NativeIteratorWrapper() = default;
    void IncrementIterator() override
    {
        if (NativeIteratorWrapperBase<Element, Iterator>::IteratorIncrementImplementation())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    void DecrementIterator() override
    {
        IteratorDecrementer<Iterator>::decrement(m_iterator);
        VirtualizedIteratorBase<Element>::m_is_end = false;
        UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    void ShiftIteratorBy(std::ptrdiff_t offset) override
    {
        if (NativeIteratorWrapperBase<Element, Iterator>::IteratorShiftImplementation(offset))
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    Element OffsetDereferenceIterator(std::ptrdiff_t offset) const override
    {
        return IteratorOffsetDereferencer<Iterator, Element>::get(m_iterator, offset);
    }
    void OffsetDereferenceAssignIterator(std::ptrdiff_t offset, const Element &value) const override
    {
        IteratorOffsetAssigner<Iterator, Element>::assign(m_iterator, offset, value);
    }
    void OffsetDereferenceAssignIterator(std::ptrdiff_t offset, Element &&value) const override
    {
        IteratorOffsetAssigner<Iterator, Element>::assign(m_iterator, offset, std::move(value));
    }
    VirtualizedIteratorBase<Element>* CloneIterator() const override
    {
        return new NativeIteratorWrapper(m_iterator, m_end);
    }
 
    NativeIteratorWrapper(NativeIteratorWrapper&&) = delete;
 
private:
    NativeIteratorWrapper(const NativeIteratorWrapper &other)
        : NativeIteratorWrapper(other.m_iterator, other.VirtualizedIteratorBase<Element>::m_end)
    {}
};
 
template <typename Element, typename Iterator>
class NativeConstIteratorWrapper
    : public NativeIteratorWrapperBase<Element, Iterator>
    , private IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value || std::is_same<const Element&, decltype(*std::declval<Iterator>())>::value>
{
    // Parent members to use.
    using NativeIteratorWrapperBase<Element, Iterator>::m_iterator;
    using NativeIteratorWrapperBase<Element, Iterator>::m_end;
    using VirtualizedIteratorBase<Element>::m_pointer;
    using IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value || std::is_same<const Element&, decltype(*std::declval<Iterator>())>::value>
        ::InitializeIteratorPointer;
    using IteratorPointerUpdater<Element, std::is_same<Element&, decltype(*std::declval<Iterator>())>::value || std::is_same<const Element&, decltype(*std::declval<Iterator>())>::value>
        ::UpdateIteratorPointer;
 
public:
    NativeConstIteratorWrapper(const Iterator &iterator, const Iterator &end)
        : NativeIteratorWrapperBase<Element, Iterator>(iterator, end)
    {
        InitializeIteratorPointer(m_pointer);
        if (!VirtualizedIteratorBase<Element>::IsEndIterator())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    NativeConstIteratorWrapper(Iterator &&iterator, Iterator &&end) noexcept
        : NativeIteratorWrapperBase<Element, Iterator>(std::forward<Iterator>(iterator), std::forward<Iterator>(end))
    {
        InitializeIteratorPointer(m_pointer);
        if (!VirtualizedIteratorBase<Element>::IsEndIterator())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    virtual ~NativeConstIteratorWrapper() = default;
    void IncrementIterator() override
    {
        if (NativeIteratorWrapperBase<Element, Iterator>::IteratorIncrementImplementation())
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    void DecrementIterator() override
    {
        IteratorDecrementer<Iterator>::decrement(m_iterator);
        VirtualizedIteratorBase<Element>::m_is_end = false;
        UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    void ShiftIteratorBy(std::ptrdiff_t offset) override
    {
        if (NativeIteratorWrapperBase<Element, Iterator>::IteratorShiftImplementation(offset))
            UpdateIteratorPointer(m_pointer, *m_iterator);
    }
    Element OffsetDereferenceIterator(std::ptrdiff_t offset) const override
    {
        return IteratorOffsetDereferencer<Iterator, Element>::get(m_iterator, offset);
    }
    void OffsetDereferenceAssignIterator(std::ptrdiff_t, const Element&) const override
    {
        throw System::NotSupportedException(u"Assigning element through const iterator");
    }
    void OffsetDereferenceAssignIterator(std::ptrdiff_t, Element&&) const override
    {
        throw System::NotSupportedException(u"Assigning element through const iterator");
    }
    VirtualizedIteratorBase<Element>* CloneIterator() const override
    {
        return new NativeConstIteratorWrapper(m_iterator, m_end);
    }
 
    NativeConstIteratorWrapper(NativeConstIteratorWrapper&&) = delete;
 
private:
    NativeConstIteratorWrapper(const NativeConstIteratorWrapper& other)
        : NativeConstIteratorWrapper(other.m_iterator, other.VirtualizedIteratorBase<Element>::m_end)
    {}
};
 
 
template <typename Element>
class EnumeratorBasedIterator : public VirtualizedIteratorBase<Element>
{
public:
    virtual ~EnumeratorBasedIterator() = default;
 
    bool IteratorEquals(VirtualizedIteratorBase<Element> *other) const override
    {
        CODEPORTING_DEBUG_ASSERT(dynamic_cast<EnumeratorBasedIterator*>(other) != nullptr);
        return static_cast<EnumeratorBasedIterator*>(other)->m_offset == m_offset;
    }
    bool IteratorLess(VirtualizedIteratorBase<Element> *other) const override
    {
        CODEPORTING_DEBUG_ASSERT(dynamic_cast<EnumeratorBasedIterator*>(other) != nullptr);
        return static_cast<EnumeratorBasedIterator*>(other)->m_offset > m_offset;
    }
    virtual void InitializeIterator()
    {}
 
protected:
    EnumeratorBasedIterator()
        : VirtualizedIteratorBase<Element>(false, true)
        , m_offset(std::numeric_limits<std::ptrdiff_t>::max())
    {}
    EnumeratorBasedIterator(std::ptrdiff_t offset)
        : VirtualizedIteratorBase<Element>(false, offset == std::numeric_limits<std::ptrdiff_t>::max())
        , m_offset(offset)
    {}
    EnumeratorBasedIterator(const EnumeratorBasedIterator &other)
        : VirtualizedIteratorBase<Element>(false, other.m_offset == std::numeric_limits<std::ptrdiff_t>::max())
        , m_offset(other.m_offset)
    {}
 
    std::ptrdiff_t m_offset;
};
 
template <typename Element>
class EnumeratorBasedEndIterator : public EnumeratorBasedIterator<Element>
{
public:
    EnumeratorBasedEndIterator()
        : EnumeratorBasedIterator<Element>(std::numeric_limits<std::ptrdiff_t>::max())
    {}
    virtual ~EnumeratorBasedEndIterator() = default;
 
    void IncrementIterator() override
    {
        throw InvalidOperationException(u"Moving past the container's end");
    }
    System::Details::VirtualizedIteratorBase<Element>* CloneIterator() const override
    {
        return new EnumeratorBasedEndIterator();
    }
};
 
 
template <typename Element>
class VirtualizedIteratorOffsetPointer
{
public:
    VirtualizedIteratorOffsetPointer(VirtualizedIteratorBase<Element> *iterator, std::ptrdiff_t offset)
        : m_value(iterator->OffsetDereferenceIterator(offset))
    {}
    VirtualizedIteratorOffsetPointer(VirtualizedIteratorOffsetPointer &&other) noexcept
        : m_value(std::move(other.m_value))
    {}
 
    decltype(std::declval<Element>().operator ->()) operator -> () const
    {
        return m_value.operator ->();
    }
 
    VirtualizedIteratorOffsetPointer(const VirtualizedIteratorOffsetPointer&) = delete;
    VirtualizedIteratorOffsetPointer& operator = (const VirtualizedIteratorOffsetPointer&) = delete;
    VirtualizedIteratorOffsetPointer& operator = (VirtualizedIteratorOffsetPointer&&) = delete;
 
private:
    Element m_value;
};
 
template <typename Element>
class VirtualizedIteratorOffsetReference
{
public:
    VirtualizedIteratorOffsetReference(VirtualizedIteratorBase<Element> *iterator, std::ptrdiff_t offset)
        : m_iterator(iterator), m_offset(offset)
    {}
    VirtualizedIteratorOffsetReference(const VirtualizedIteratorOffsetReference&) = default;
    VirtualizedIteratorOffsetReference(VirtualizedIteratorOffsetReference&&) noexcept = default;
 
    operator Element () const
    {
        if (m_offset == 0)
            return *m_iterator->GetElementPointer();
        else
            return m_iterator->OffsetDereferenceIterator(m_offset);
    }
    VirtualizedIteratorOffsetReference& operator = (const Element &value)
    {
        m_iterator->OffsetDereferenceAssignIterator(m_offset, value);
        return *this;
    }
    VirtualizedIteratorOffsetReference& operator = (Element &&value)
    {
        m_iterator->OffsetDereferenceAssignIterator(m_offset, std::move(value));
        return *this;
    }
    VirtualizedIteratorOffsetPointer<Element> operator -> () const
    {
        return VirtualizedIteratorOffsetPointer<Element>(m_iterator, m_offset);
    }
 
    VirtualizedIteratorOffsetReference& operator = (const VirtualizedIteratorOffsetReference&) = delete;
    VirtualizedIteratorOffsetReference& operator = (VirtualizedIteratorOffsetReference&&) = delete;
 
private:
    VirtualizedIteratorBase<Element> *const m_iterator;
    const std::ptrdiff_t m_offset;
};
 
 
template <typename Element> class VirtualizedConstIterator;
 
template <typename Element>
class VirtualizedIterator : public BaseIterator<std::random_access_iterator_tag, Element, std::ptrdiff_t, Element*, Element&>
{
public:
    VirtualizedIterator() = default;
    VirtualizedIterator(const VirtualizedIterator &other)
        : m_iterator(other.m_iterator->CloneIterator())
    {}
    VirtualizedIterator(VirtualizedIterator &&other) noexcept
        : m_iterator(other.m_iterator.release())
    {}
    explicit VirtualizedIterator(VirtualizedIteratorBase<Element> *virtualizedIterator)
        : m_iterator(virtualizedIterator)
    {}
 
    VirtualizedIterator& operator = (const VirtualizedIterator &other)
    {
        m_iterator.reset(other.m_iterator->CloneIterator());
        return *this;
    }
    VirtualizedIterator& operator = (VirtualizedIterator &&other) noexcept
    {
        m_iterator = std::move(other.m_iterator);
        return *this;
    }
 
    VirtualizedIterator& operator ++ ()
    {
        m_iterator->IncrementIterator();
        return *this;
    }
    VirtualizedIterator& operator -- ()
    {
        m_iterator->DecrementIterator();
        return *this;
    }
    VirtualizedIterator operator ++ (int)
    {
        VirtualizedIterator copy(*this);
        operator++();
        return copy;
    }
    VirtualizedIterator operator -- (int)
    {
        VirtualizedIterator copy(*this);
        operator --();
        return copy;
    }
 
    VirtualizedIterator& operator += (std::ptrdiff_t offset)
    {
        m_iterator->ShiftIteratorBy(offset);
        return *this;
    }
    VirtualizedIterator& operator -= (std::ptrdiff_t offset)
    {
        m_iterator->ShiftIteratorBy(-offset);
        return *this;
    }
    VirtualizedIterator operator + (std::ptrdiff_t offset) const
    {
        VirtualizedIterator copy(*this);
        copy += offset;
        return copy;
    }
    VirtualizedIterator operator - (std::ptrdiff_t offset) const
    {
        VirtualizedIterator copy(*this);
        copy -= offset;
        return copy;
    }
    std::ptrdiff_t operator - (const VirtualizedIterator &other) const
    {
        return m_iterator->DiffIterators(other.m_iterator.get());
    }
 
    Element& operator * () const
    {
        return *m_iterator->GetElementPointer();
    }
    Element* operator -> () const
    {
        return m_iterator->GetElementPointer();
    }
    VirtualizedIteratorOffsetReference<Element> operator [] (std::ptrdiff_t offset) const
    {
        return VirtualizedIteratorOffsetReference<Element>(m_iterator.get(), offset);
    }
 
    bool operator == (const VirtualizedIterator &other) const
    {
        if (m_iterator->IsEndIterator() != other.m_iterator->IsEndIterator())
            return false;
        else if (m_iterator->IsEndIterator())
            return true;
        else
            return m_iterator->IteratorEquals(other.m_iterator.get());
    }
    bool operator != (const VirtualizedIterator &other) const
    {
        if (m_iterator->IsEndIterator() != other.m_iterator->IsEndIterator())
            return true;
        else if (m_iterator->IsEndIterator())
            return false;
        else
            return !m_iterator->IteratorEquals(other.m_iterator.get());
    }
    bool operator < (const VirtualizedIterator &other) const
    {
        if (other.m_iterator->IsEndIterator())
            return !m_iterator->IsEndIterator();
        else
            return m_iterator->IteratorLess(other.m_iterator.get());
    }
    bool operator >= (const VirtualizedIterator &other) const
    {
        return !(*this < other);
    }
    bool operator > (const VirtualizedIterator &other) const
    {
        return other < *this;
    }
    bool operator <= (const VirtualizedIterator &other) const
    {
        return !(other < *this);
    }
 
    void swap(VirtualizedIterator &other)
    {
        std::swap(m_iterator, other.m_iterator);
    }
 
private:
    std::unique_ptr<VirtualizedIteratorBase<std::remove_const_t<Element>>> m_iterator;
 
    friend class VirtualizedConstIterator<Element>;
};
 
template <typename Element>
class VirtualizedConstIterator : public BaseIterator<std::random_access_iterator_tag, Element, std::ptrdiff_t, const Element*, const Element&>
{
public:
    VirtualizedConstIterator()
        : m_iterator(nullptr)
    {}
    VirtualizedConstIterator(const VirtualizedConstIterator &other)
        : m_iterator(other.m_iterator->CloneIterator())
    {}
    VirtualizedConstIterator(VirtualizedConstIterator &&other) noexcept
        : m_iterator(other.m_iterator.release())
    {}
    VirtualizedConstIterator(const VirtualizedIterator<Element> &other)
        : m_iterator(other.m_iterator->CloneIterator())
    {}
    VirtualizedConstIterator(VirtualizedIterator<Element> &&other) noexcept
        : m_iterator(other.m_iterator.release())
    {}
    explicit VirtualizedConstIterator(VirtualizedIteratorBase<Element> *virtualizedIterator)
        : m_iterator(virtualizedIterator)
    {}
 
    VirtualizedConstIterator& operator = (const VirtualizedConstIterator &other)
    {
        m_iterator.reset(other.m_iterator->CloneIterator());
        return *this;
    }
    VirtualizedConstIterator& operator = (VirtualizedConstIterator &&other) noexcept
    {
        m_iterator = std::move(other.m_iterator);
        return *this;
    }
 
    VirtualizedConstIterator& operator ++ ()
    {
        m_iterator->IncrementIterator();
        return *this;
    }
    VirtualizedConstIterator& operator -- ()
    {
        m_iterator->DecrementIterator();
        return *this;
    }
    VirtualizedConstIterator operator ++ (int)
    {
        VirtualizedConstIterator copy(*this);
        operator++();
        return copy;
    }
    VirtualizedConstIterator operator -- (int)
    {
        VirtualizedConstIterator copy(*this);
        operator --();
        return copy;
    }
 
    VirtualizedConstIterator& operator += (std::ptrdiff_t offset)
    {
        m_iterator->ShiftIteratorBy(offset);
        return *this;
    }
    VirtualizedConstIterator& operator -= (std::ptrdiff_t offset)
    {
        m_iterator->ShiftIteratorBy(-offset);
        return *this;
    }
    VirtualizedConstIterator operator + (std::ptrdiff_t offset) const
    {
        VirtualizedConstIterator copy(*this);
        copy += offset;
        return copy;
    }
    VirtualizedConstIterator operator - (std::ptrdiff_t offset) const
    {
        VirtualizedConstIterator copy(*this);
        copy -= offset;
        return copy;
    }
    std::ptrdiff_t operator - (const VirtualizedConstIterator &other) const
    {
        return m_iterator->DiffIterators(other.m_iterator.get());
    }
 
    const Element& operator * () const
    {
        return *m_iterator->GetElementPointer();
    }
    const Element* operator -> () const
    {
        return m_iterator->GetElementPointer();
    }
    Element operator [] (std::ptrdiff_t offset) const
    {
        if (offset == 0)
            return *m_iterator->GetElementPointer();
        else
            return m_iterator->OffsetDereferenceIterator(offset);
    }
 
    bool operator == (const VirtualizedConstIterator &other) const
    {
        if (m_iterator->IsEndIterator() != other.m_iterator->IsEndIterator())
            return false;
        else if (m_iterator->IsEndIterator())
            return true;
        else
            return m_iterator->IteratorEquals(other.m_iterator.get());
    }
    bool operator != (const VirtualizedConstIterator &other) const
    {
        if (m_iterator->IsEndIterator() != other.m_iterator->IsEndIterator())
            return true;
        else if (m_iterator->IsEndIterator())
            return false;
        else
            return !m_iterator->IteratorEquals(other.m_iterator.get());
    }
    bool operator < (const VirtualizedConstIterator &other) const
    {
        if (other.m_iterator->IsEndIterator())
            return !m_iterator->IsEndIterator();
        else
            return m_iterator->IteratorLess(other.m_iterator.get());
    }
    bool operator >= (const VirtualizedConstIterator &other) const
    {
        return !(*this < other);
    }
    bool operator > (const VirtualizedConstIterator &other) const
    {
        return other < *this;
    }
    bool operator <= (const VirtualizedConstIterator &other) const
    {
        return !(other < *this);
    }
 
    void swap(VirtualizedConstIterator &other)
    {
        std::swap(m_iterator, other.m_iterator);
    }
 
private:
    std::unique_ptr<VirtualizedIteratorBase<std::remove_const_t<Element>>> m_iterator;
};
 
template <typename Element>
VirtualizedIterator<Element> operator + (std::ptrdiff_t offset, const VirtualizedIterator<Element> &iterator)
{
    return iterator + offset;
}
template <typename Element>
VirtualizedConstIterator<Element> operator + (std::ptrdiff_t offset, const VirtualizedConstIterator<Element> &iterator)
{
    return iterator + offset;
}
 
}} // namespace System::Details
 
using System::Details::operator +;
 
namespace std
{
 
template <typename Element>
void swap(System::Details::VirtualizedIterator<Element> &lhs, System::Details::VirtualizedIterator<Element> &rhs)
{
    lhs.swap(rhs);
}
template <typename Element>
void swap(System::Details::VirtualizedConstIterator<Element> &lhs, System::Details::VirtualizedConstIterator<Element> &rhs)
{
    lhs.swap(rhs);
}
 
}