#ifndef NNTREE_HH

#define NNTREE_HH

#include <qpdf/QPDF.hh>

#include <qpdf/QPDFObjectHandle_private.hh>

#include <iterator>

#include <list>

#include <memory>

class NNTreeImpl;

class NNTreeIterator final

{

    friend class NNTreeImpl;

  public:

    typedef std::pair<QPDFObjectHandle, QPDFObjectHandle> T;

    using iterator_category = std::bidirectional_iterator_tag;

    using value_type = T;

    using difference_type = long;

    using pointer = T*;

    using reference = T&;

    ~NNTreeIterator() = default;

    // iterator can be incremented or decremented, or dereferenced. This does not imply that it

    // points to a valid item.

    bool

    valid() const

    {

        return item_number >= 0;

    }

    NNTreeIterator&

    operator++()

    {

        increment(false);

        return *this;

    }

    NNTreeIterator

    operator++(int)

    {

        NNTreeIterator t = *this;

        ++(*this);

        return t;

    }

    NNTreeIterator&

    operator--()

    {

        increment(true);

        return *this;

    }

    NNTreeIterator

    operator--(int)

    {

        NNTreeIterator t = *this;

        --(*this);

        return t;

    }

    reference

    operator*()

    {

        updateIValue(false);

        return ivalue;

    }

    pointer

    operator->()

    {

        updateIValue(false);

        return &ivalue;

    }

    bool operator==(NNTreeIterator const& other) const;

    bool

    operator!=(NNTreeIterator const& other) const

    {

        return !operator==(other);

    }

    void insertAfter(QPDFObjectHandle const& key, QPDFObjectHandle const& value);

    void remove();

  private:

    class PathElement

    {

      public:

        PathElement(qpdf::Dictionary const& node, int kid_number) :

            node(node),

            kid_number(kid_number)

        {

        }

        qpdf::Dictionary node;

        int kid_number;

    };

    NNTreeIterator(NNTreeImpl& impl) :

        impl(impl)

    {

    }

    void updateIValue(bool allow_invalid = true);

    bool deepen(qpdf::Dictionary node, bool first, bool allow_empty);

    void

    setItemNumber(QPDFObjectHandle const& a_node, int n)

    {

        node = a_node;

        item_number = n;

        updateIValue();

    }

    void

    addPathElement(QPDFObjectHandle const& a_node, int kid_number)

    {

        path.emplace_back(a_node, kid_number);

    }

    qpdf::Dictionary getNextKid(PathElement& element, bool backward);

    void increment(bool backward);

    void resetLimits(qpdf::Dictionary node, std::list<PathElement>::iterator parent);

    void split(qpdf::Dictionary to_split, std::list<PathElement>::iterator parent);

    std::list<PathElement>::iterator lastPathElement();

    NNTreeImpl& impl;

    std::list<PathElement> path;

    qpdf::Dictionary node;

    int item_number{-1};

    value_type ivalue;

};

class NNTreeImpl final

{

    friend class NNTreeIterator;

  public:

    typedef NNTreeIterator iterator;

    NNTreeImpl(

        QPDF& qpdf,

        qpdf::Dictionary tree_root,

        qpdf_object_type_e key_type,

        std::function<bool(QPDFObjectHandle const&)> value_validator,

        bool auto_repair) :

        qpdf(qpdf),

        tree_root(std::move(tree_root)),

        key_type(key_type),

        items_key(key_type == ::ot_string ? "/Names" : "/Nums"),

        value_valid(value_validator),

        auto_repair(auto_repair)

    {

    }

    iterator begin();

    iterator

    end()

    {

        return {*this};

    }

    iterator last();

    iterator find(QPDFObjectHandle const& key, bool return_prev_if_not_found = false);

    iterator insertFirst(QPDFObjectHandle const& key, QPDFObjectHandle const& value);

    iterator insert(QPDFObjectHandle const& key, QPDFObjectHandle const& value);

    bool remove(QPDFObjectHandle const& key, QPDFObjectHandle* value = nullptr);

    bool validate(bool repair = true);

    // Change the split threshold for easier testing. There's no real reason to expose this to

    // downstream tree helpers, but it has to be public so we can call it from the test suite.

    void

    setSplitThreshold(int threshold)

    {

        split_threshold = threshold;

    }

  private:

    void repair();

    iterator findInternal(QPDFObjectHandle const& key, bool return_prev_if_not_found = false);

    int binarySearch(

        QPDFObjectHandle const& key,

        qpdf::Array const& items,

        size_t num_items,

        bool return_prev_if_not_found,

        bool search_kids) const;

    int compareKeyItem(QPDFObjectHandle const& key, qpdf::Array const& items, int idx) const;

    int compareKeyKid(QPDFObjectHandle const& key, qpdf::Array const& items, int idx) const;

    void warn(QPDFObjectHandle const& node, std::string const& msg);

    void error(QPDFObjectHandle const& node, std::string const& msg) const;

    std::string const&

    itemsKey() const

    {

        return items_key;

    }

    bool

    keyValid(QPDFObjectHandle o) const

    {

        return o.resolved_type_code() == key_type;

    }

    int compareKeys(QPDFObjectHandle a, QPDFObjectHandle b) const;

    QPDF& qpdf;

    int split_threshold{32};

    qpdf::Dictionary tree_root;

    const qpdf_object_type_e key_type;

    const std::string items_key;

    const std::function<bool(QPDFObjectHandle const&)> value_valid;

    bool auto_repair{true};

    size_t error_count{0};

};

#endif // NNTREE_HH