////////////////////////////////////////////////////////////////////////////
//
// Copyright 2015 Realm Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
////////////////////////////////////////////////////////////////////////////

#ifndef REALM_INDEX_SET_HPP
#define REALM_INDEX_SET_HPP

#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

namespace realm {
namespace _impl {
template<typename OuterIterator>
class MutableChunkedRangeVectorIterator;

// An iterator for ChunkedRangeVector, templated on the vector iterator/const_iterator
template<typename OuterIterator>
class ChunkedRangeVectorIterator {
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = typename std::remove_reference<decltype(*OuterIterator()->data.begin())>::type;
    using difference_type = ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;

    ChunkedRangeVectorIterator(OuterIterator outer, OuterIterator end, value_type* inner)
    : m_outer(outer), m_end(end), m_inner(inner) { }

    reference operator*() const noexcept { return *m_inner; }
    pointer operator->() const noexcept { return m_inner; }

    template<typename Other> bool operator==(Other const& it) const noexcept;
    template<typename Other> bool operator!=(Other const& it) const noexcept;

    ChunkedRangeVectorIterator& operator++() noexcept;
    ChunkedRangeVectorIterator operator++(int) noexcept;

    ChunkedRangeVectorIterator& operator--() noexcept;
    ChunkedRangeVectorIterator operator--(int) noexcept;

    // Advance directly to the next outer block
    void next_chunk() noexcept;

    OuterIterator outer() const noexcept { return m_outer; }
    size_t offset() const noexcept { return m_inner - &m_outer->data[0]; }

private:
    OuterIterator m_outer;
    OuterIterator m_end;
    value_type* m_inner;
    friend struct ChunkedRangeVector;
    friend class MutableChunkedRangeVectorIterator<OuterIterator>;
};

// A mutable iterator that adds some invariant-preserving mutation methods
template<typename OuterIterator>
class MutableChunkedRangeVectorIterator : public ChunkedRangeVectorIterator<OuterIterator> {
public:
    using ChunkedRangeVectorIterator<OuterIterator>::ChunkedRangeVectorIterator;

    // Set this iterator to the given range and update the parent if needed
    void set(size_t begin, size_t end);
    // Adjust the begin and end of this iterator by the given amounts and
    // update the parent if needed
    void adjust(ptrdiff_t front, ptrdiff_t back);
    // Shift this iterator by the given amount and update the parent if needed
    void shift(ptrdiff_t distance);
};

// A vector which stores ranges in chunks with a maximum size
struct ChunkedRangeVector {
    struct Chunk {
        std::vector<std::pair<size_t, size_t>> data;
        size_t begin;
        size_t end;
        size_t count;
    };
    std::vector<Chunk> m_data;

    using value_type = std::pair<size_t, size_t>;
    using iterator = MutableChunkedRangeVectorIterator<typename decltype(m_data)::iterator>;
    using const_iterator = ChunkedRangeVectorIterator<typename decltype(m_data)::const_iterator>;

#ifdef REALM_DEBUG
    static const size_t max_size = 4;
#else
    static const size_t max_size = 4096 / sizeof(std::pair<size_t, size_t>);
#endif

    iterator begin() noexcept { return empty() ? end() : iterator(m_data.begin(), m_data.end(), &m_data[0].data[0]); }
    iterator end() noexcept { return iterator(m_data.end(), m_data.end(), nullptr); }
    const_iterator begin() const noexcept { return cbegin(); }
    const_iterator end() const noexcept { return cend(); }
    const_iterator cbegin() const noexcept { return empty() ? cend() : const_iterator(m_data.cbegin(), m_data.end(), &m_data[0].data[0]); }
    const_iterator cend() const noexcept { return const_iterator(m_data.end(), m_data.end(), nullptr); }

    bool empty() const noexcept { return m_data.empty(); }

    iterator insert(iterator pos, value_type value);
    iterator erase(iterator pos) noexcept;
    void push_back(value_type value);
    iterator ensure_space(iterator pos);

    void verify() const noexcept;
};
} // namespace _impl

class IndexSet : private _impl::ChunkedRangeVector {
public:
    static const size_t npos = -1;

    using ChunkedRangeVector::value_type;
    using ChunkedRangeVector::iterator;
    using ChunkedRangeVector::const_iterator;
    using ChunkedRangeVector::begin;
    using ChunkedRangeVector::end;
    using ChunkedRangeVector::empty;
    using ChunkedRangeVector::verify;

    IndexSet() = default;
    IndexSet(std::initializer_list<size_t>);

    // Check if the index set contains the given index
    bool contains(size_t index) const noexcept;

    // Counts the number of indices in the set in the given range
    size_t count(size_t start_index=0, size_t end_index=-1) const noexcept;

    // Add an index to the set, doing nothing if it's already present
    void add(size_t index);
    void add(IndexSet const& is);

    // Add an index which has had all of the ranges in the set before it removed
    // Returns the unshifted index
    size_t add_shifted(size_t index);
    // Add indexes which have had the ranges in `shifted_by` added and the ranges
    // in the current set removed
    void add_shifted_by(IndexSet const& shifted_by, IndexSet const& values);

    // Remove all indexes from the set and then add a single range starting from
    // zero with the given length
    void set(size_t len);

    // Insert an index at the given position, shifting existing indexes at or
    // after that point back by one
    void insert_at(size_t index, size_t count=1);
    void insert_at(IndexSet const&);

    // Shift indexes at or after the given point back by one
    void shift_for_insert_at(size_t index, size_t count=1);
    void shift_for_insert_at(IndexSet const&);

    // Delete an index at the given position, shifting indexes after that point
    // forward by one
    void erase_at(size_t index);
    void erase_at(IndexSet const&);

    // If the given index is in the set remove it and return npos; otherwise unshift() it
    size_t erase_or_unshift(size_t index);

    // Remove the indexes at the given index from the set, without shifting
    void remove(size_t index, size_t count=1);
    void remove(IndexSet const&);

    // Shift an index by inserting each of the indexes in this set
    size_t shift(size_t index) const noexcept;
    // Shift an index by deleting each of the indexes in this set
    size_t unshift(size_t index) const noexcept;

    // Remove all indexes from the set
    void clear() noexcept;

    // An iterator over the individual indices in the set rather than the ranges
    class IndexIterator : public std::iterator<std::forward_iterator_tag, size_t> {
    public:
        IndexIterator(IndexSet::const_iterator it) : m_iterator(it) { }
        size_t operator*() const noexcept { return m_iterator->first + m_offset; }
        bool operator==(IndexIterator const& it) const noexcept { return m_iterator == it.m_iterator; }
        bool operator!=(IndexIterator const& it) const noexcept { return m_iterator != it.m_iterator; }

        IndexIterator& operator++() noexcept
        {
            ++m_offset;
            if (m_iterator->first + m_offset == m_iterator->second) {
                ++m_iterator;
                m_offset = 0;
            }
            return *this;
        }

        IndexIterator operator++(int) noexcept
        {
            auto value = *this;
            ++*this;
            return value;
        }

    private:
        IndexSet::const_iterator m_iterator;
        size_t m_offset = 0;
    };

    class IndexIteratableAdaptor {
    public:
        using value_type = size_t;
        using iterator = IndexIterator;
        using const_iterator = iterator;

        const_iterator begin() const noexcept { return m_index_set.begin(); }
        const_iterator end() const noexcept { return m_index_set.end(); }

        IndexIteratableAdaptor(IndexSet const& is) : m_index_set(is) { }
    private:
        IndexSet const& m_index_set;
    };

    IndexIteratableAdaptor as_indexes() const noexcept { return *this; }

private:
    // Find the range which contains the index, or the first one after it if
    // none do
    iterator find(size_t index) noexcept;
    iterator find(size_t index, iterator it) noexcept;
    // Insert the index before the given position, combining existing ranges as
    // applicable
    // returns inserted position
    iterator do_add(iterator pos, size_t index);
    void do_erase(iterator it, size_t index);
    iterator do_remove(iterator it, size_t index, size_t count);

    void shift_until_end_by(iterator begin, ptrdiff_t shift);
};

namespace util {
// This was added in C++14 but is missing from libstdc++ 4.9
template<typename Iterator>
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it) noexcept
{
    return std::reverse_iterator<Iterator>(it);
}
} // namespace util


namespace _impl {
template<typename T>
template<typename OtherIterator>
inline bool ChunkedRangeVectorIterator<T>::operator==(OtherIterator const& it) const noexcept
{
    return m_outer == it.outer() && m_inner == it.operator->();
}

template<typename T>
template<typename OtherIterator>
inline bool ChunkedRangeVectorIterator<T>::operator!=(OtherIterator const& it) const noexcept
{
    return !(*this == it);
}

template<typename T>
inline ChunkedRangeVectorIterator<T>& ChunkedRangeVectorIterator<T>::operator++() noexcept
{
    ++m_inner;
    if (offset() == m_outer->data.size())
        next_chunk();
    return *this;
}

template<typename T>
inline ChunkedRangeVectorIterator<T> ChunkedRangeVectorIterator<T>::operator++(int) noexcept
{
    auto value = *this;
    ++*this;
    return value;
}

template<typename T>
inline ChunkedRangeVectorIterator<T>& ChunkedRangeVectorIterator<T>::operator--() noexcept
{
    if (!m_inner || m_inner == &m_outer->data.front()) {
        --m_outer;
        m_inner = &m_outer->data.back();
    }
    else {
        --m_inner;
    }
    return *this;
}

template<typename T>
inline ChunkedRangeVectorIterator<T> ChunkedRangeVectorIterator<T>::operator--(int) noexcept
{
    auto value = *this;
    --*this;
    return value;
}

template<typename T>
inline void ChunkedRangeVectorIterator<T>::next_chunk() noexcept
{
    ++m_outer;
    m_inner = m_outer != m_end ? &m_outer->data[0] : nullptr;
}
} // namespace _impl

} // namespace realm

#endif // REALM_INDEX_SET_HPP