#include <boost/intrusive/set.hpp>
#include <boost/intrusive/detail/tree_iterator.hpp>
#include <boost/iterator/iterator_adaptor.hpp>

// from: https__raw_githubusercontent_com/boostorg/intrusive/master/test/bounded_pointer.hpp
#include "bounded_pointer.hpp"

namespace bi = boost::intrusive;

template < typename Value_Traits, bool Is_Const >
class my_iterator
    : public boost::iterator_adaptor< my_iterator< Value_Traits, Is_Const >,
                                      bi::tree_iterator< Value_Traits, Is_Const >,
                                      boost::use_default,
                                      boost::forward_traversal_tag >
{
public:
    typedef bi::tree_iterator< Value_Traits, Is_Const > base_iterator;

    my_iterator()
        : my_iterator::iterator_adaptor_() {}
    explicit my_iterator(const base_iterator& other)
        : my_iterator::iterator_adaptor_(other) {}
    my_iterator(const my_iterator< Value_Traits, false >& other)
        : my_iterator::iterator_adaptor_(other) {}

    typedef typename base_iterator::pointer pointer; // WHY ???
    base_iterator operator -> () const { return this->base(); } // WHY ???

private:
    friend class boost::iterator_core_access;
    typedef bi::bstree_algorithms< typename Value_Traits::node_traits > node_algorithms;

    void increment()
    {
        ++this->base_reference();
        if (not node_algorithms::is_header(this->base().pointed_node()))
        {
            ++this->base_reference();
        }
    }
}; // class my_iterator

struct A;

typedef bounded_allocator< A > alloc_type;
typedef bounded_pointer< A > ptr_type;
typedef bounded_pointer< const A > const_ptr_type;
typedef bounded_reference< A > ref_type;
typedef bounded_reference< const A > const_ref_type;

struct A
{
    A(int val = 42) : _val(val) {}

    friend bool operator == (const A& lhs, const A& rhs) { return lhs._val == rhs._val; }
    friend bool operator != (const A& lhs, const A& rhs) { return not (lhs == rhs); }
    friend bool operator <  (const A& lhs, const A& rhs) { return lhs._val < rhs._val; }
    friend bool operator <= (const A& lhs, const A& rhs) { return lhs < rhs or lhs == rhs; }
    friend bool operator >  (const A& lhs, const A& rhs) { return not (lhs <= rhs); }
    friend bool operator >= (const A& lhs, const A& rhs) { return not (lhs < rhs); }

    int _val;
    ptr_type _parent;
    ptr_type _l_child;
    ptr_type _r_child;
    int _col;
}; // struct A

struct A_Set_Node_Traits
{
    typedef A node;
    typedef bounded_pointer< A > node_ptr;
    typedef bounded_pointer< const A > const_node_ptr;
    typedef int color;

    static node_ptr get_parent(const_node_ptr n) { return n->_parent; }
    static void set_parent(node_ptr n, node_ptr ptr) { n->_parent = ptr; }
    static node_ptr get_left(const_node_ptr n) { return n->_l_child; }
    static void set_left(node_ptr n, node_ptr ptr) { n->_l_child = ptr; }
    static node_ptr get_right(const_node_ptr n) { return n->_r_child; }
    static void set_right(node_ptr n, node_ptr ptr) { n->_r_child = ptr; }
    static color get_color(const_node_ptr n) { return n->_col; }
    static void set_color(node_ptr n, color c) { n->_col = c ; }
    static color black() { return 0; }
    static color red() { return 1; }
}; // struct A_Set_Node_Traits

struct A_Set_Value_Traits
{
    typedef A value_type;
    typedef A_Set_Node_Traits node_traits;
    typedef node_traits::node_ptr node_ptr;
    typedef node_traits::const_node_ptr const_node_ptr;
    typedef node_ptr pointer;
    typedef const_node_ptr const_pointer;
    typedef bounded_reference< A > reference;
    typedef bounded_reference< const A > const_reference;
    typedef A_Set_Value_Traits* value_traits_ptr;

    static const bi::link_mode_type link_mode = bi::safe_link;

    static node_ptr to_node_ptr (reference value) { return &value; }
    static const_node_ptr to_node_ptr (const_reference value) { return &value; }
    static pointer to_value_ptr(node_ptr n) { return n; }
    static const_pointer to_value_ptr(const_node_ptr n) { return n; }
}; // struct A_Set_Value_Traits

typedef bi::set<
    A,
    bi::value_traits< A_Set_Value_Traits >,
    bi::header_holder_type< bounded_pointer_holder< A > >
    > set_type;

typedef bi::tree_iterator< A_Set_Value_Traits, false > reg_iterator_type;
typedef my_iterator< A_Set_Value_Traits, false > my_iterator_type;

// check iterator inner types
// reg_iterator_type
static_assert(std::is_same< reg_iterator_type::value_type, A >::value, "reg_iterator_type::value_type != A");
static_assert(std::is_same< reg_iterator_type::reference, ref_type >::value, "reg_iterator_type::value_type != ref_type");
static_assert(std::is_same< reg_iterator_type::pointer, ptr_type >::value, "reg_iterator_type::value_type != ptr_type");
// my_iterator_type
static_assert(std::is_same< my_iterator_type::value_type, A >::value, "my_iterator_type::value_type != A");
static_assert(std::is_same< my_iterator_type::reference, ref_type >::value, "my_iterator_type::value_type != ref_type");
static_assert(std::is_same< my_iterator_type::pointer, ptr_type >::value, "my_iterator_type::value_type != ptr_type");

template < typename Iterator >
void print_set(std::ostream& os, set_type& s, const std::string& tag)
{
    os << "set using " << tag << ":";
    Iterator it(s.begin());
    Iterator it_end(s.end());
    while (it != it_end)
    {
        os << " " << it->_val;
        ++it;
    }
    os << std::endl;
}

int main()
{
    alloc_type a;
    a.init();
    ptr_type p;
    {
        set_type s;
        for (size_t i = 0; i < 10; ++i)
        {
            p = a.allocate(1);
            new (p.raw()) A(i);
            s.insert(*p);
        }
        print_set< reg_iterator_type >(std::cout, s, "reg_iterator");
        print_set< my_iterator_type >(std::cout, s, "my_iterator");
        s.clear_and_dispose([&a] (ptr_type p) { a.deallocate(p, 1); });
    }
    assert(a.is_clear());
    a.destroy();
}