#ifndef __GBLIBCPP_SET__
#define __GBLIBCPP_SET__

#include <bits/iter_ops>

#include <bits/rbtree>
#include <functional>
#include <initializer_list>
#include <memory>
#include <cstddef>

namespace std {

template <typename Key,
    typename Compare = std::less<Key>,
    typename Allocator = std::allocator<Key>>
class set {
private:
    using rbtree_type = impl::rbtree<Key, Compare, Allocator>;
    using node_allocator = typename rbtree_type::node_allocator;

private:
    rbtree_type tree;

public:
    using key_type = Key;
    using value_type = Key;
    using size_type = std::size_t;
    using allocator_type = Allocator;
    using iterator = typename rbtree_type::iterator;
    using const_iterator = typename rbtree_type::const_iterator;

public:
    __GBLIBCPP_CONSTEXPR
    iterator end(void) noexcept { return tree.end(); }
    __GBLIBCPP_CONSTEXPR
    const_iterator end(void) const noexcept { return tree.cend(); }
    __GBLIBCPP_CONSTEXPR
    const_iterator cend(void) const noexcept { return tree.cend(); }

    __GBLIBCPP_CONSTEXPR
    iterator begin(void) noexcept { return tree.begin(); }
    __GBLIBCPP_CONSTEXPR
    const_iterator begin(void) const noexcept { return tree.cbegin(); }
    __GBLIBCPP_CONSTEXPR
    const_iterator cbegin(void) const noexcept { return tree.cbegin(); }

    explicit __GBLIBCPP_CONSTEXPR
    set(const Compare& comp,
        const Allocator& alloc = Allocator())
        : tree(comp, alloc) {}
    
    explicit __GBLIBCPP_CONSTEXPR
    set(const Allocator& alloc)
        : set(Compare(), alloc) {}

    __GBLIBCPP_CONSTEXPR
    set() : set(Compare()) {}

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    set(InputIter first, InputIter last,
        const Compare& comp = Compare(),
        const Allocator& alloc = Allocator())
        : set(comp, alloc)
    {
        insert(first, last);
    }

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    set(InputIter first, InputIter last,
        const Allocator& alloc = Allocator())
        : set(first, last, Compare(), alloc) {}

    __GBLIBCPP_CONSTEXPR
    set(const set& other) : tree(other.tree) {}
    __GBLIBCPP_CONSTEXPR
    set(const set& other, const Allocator& alloc)
        : tree(other.tree, alloc) { }

    __GBLIBCPP_CONSTEXPR
    set(set&& other) : tree(std::move(other.tree)) {}
    __GBLIBCPP_CONSTEXPR
    set(set&& other, const Allocator& alloc)
        : tree(std::move(other.tree), alloc) {}

    __GBLIBCPP_CONSTEXPR
    set(std::initializer_list<Key> ilist,
        const Compare& comp = Compare(),
        const Allocator& alloc = Allocator())
        : set(comp, alloc)
    { insert(ilist.begin(), ilist.end()); }
    
    __GBLIBCPP_CONSTEXPR
    set(std::initializer_list<Key> ilist,
        const Allocator& alloc)
        : set(ilist, Compare(), alloc) {}
    
    __GBLIBCPP_CONSTEXPR
    ~set() { clear(); }
    
    __GBLIBCPP_CONSTEXPR
    set& operator=(const set& other) = default;
    __GBLIBCPP_CONSTEXPR
    set& operator=(set&& other) = default;
    __GBLIBCPP_CONSTEXPR
    set& operator=(std::initializer_list<Key> ilist)
    {
        clear();
        insert(ilist.begin(), ilist.end());
        return *this;
    }

    __GBLIBCPP_CONSTEXPR
    iterator find(const Key& key) { return tree.find(key); }
    __GBLIBCPP_CONSTEXPR
    const_iterator find(const Key& key) const { return tree.find(key); }
    template <typename K>
    __GBLIBCPP_CONSTEXPR
    iterator find(const K& key) { return tree.find(key); }
    template <typename K>
    __GBLIBCPP_CONSTEXPR
    const_iterator find(const K& key) const { return tree.find(key); }

    __GBLIBCPP_CONSTEXPR
    std::pair<iterator, bool> insert(const value_type& value)
    { return tree.insert(value); }
    __GBLIBCPP_CONSTEXPR
    std::pair<iterator, bool> insert(value_type&& value)
    { return tree.insert(std::move(value)); }

    template <typename InputIter>
    __GBLIBCPP_CONSTEXPR
    void insert(InputIter first, InputIter last)
    {
        for ( ; first != last; ++first)
            insert(*first);
    }

    template <typename... Args>
    __GBLIBCPP_CONSTEXPR
    std::pair<iterator, bool> emplace(Args&&... args)
    { return tree.emplace(std::forward<Args>(args)...); }

    __GBLIBCPP_CONSTEXPR
    iterator erase(iterator pos) noexcept { return tree.erase(pos); }
    __GBLIBCPP_CONSTEXPR
    iterator erase(const_iterator pos) noexcept { return tree.erase(pos); }
    __GBLIBCPP_CONSTEXPR
    iterator erase(const_iterator first, const_iterator last) noexcept
    {
        while (first != last)
            first = erase(first);
        return first;
    }

    __GBLIBCPP_CONSTEXPR
    size_type erase(const Key& key)
    {
        auto iter = find(key);
        if (!iter)
            return 0;
        erase(iter);
        return 1;
    }

    __GBLIBCPP_CONSTEXPR
    void clear() noexcept { tree.destroy(); }

    __GBLIBCPP_CONSTEXPR
    bool empty() const noexcept { return tree.empty(); }

    __GBLIBCPP_CONSTEXPR
    size_type size() const noexcept { return tree.size(); }

    __GBLIBCPP_CONSTEXPR
    void swap(set& other) { tree.swap(other.tree); }

    __GBLIBCPP_CONSTEXPR
    size_type count(const Key& key) const
    { return find(key) ? 1 : 0; }

    __GBLIBCPP_CONSTEXPR
    bool contains(const Key& key) const { return count(key) != 0; }

    __GBLIBCPP_CONSTEXPR
    iterator upper_bound(const Key& key)
    { return tree.upper_bound(key); }
    __GBLIBCPP_CONSTEXPR
    const_iterator upper_bound(const Key& key) const
    { return tree.upper_bound(key); }

    __GBLIBCPP_CONSTEXPR
    iterator lower_bound(const Key& key)
    { return tree.lower_bound(key); }
    __GBLIBCPP_CONSTEXPR
    const_iterator lower_bound(const Key& key) const
    { return tree.lower_bound(key); }
};

template <typename Key, typename Compare, typename Allocator>
void swap(std::set<Key, Compare, Allocator>& lhs,
    std::set<Key, Compare, Allocator>& rhs)
{ lhs.swap(rhs); }

template <typename Key, typename Compare,
    typename Allocator, typename Pred>
typename std::set<Key, Compare, Allocator>::size_type
erase_if(std::set<Key, Compare, Allocator>& set, Pred pred)
{
    auto iter = set.begin();
    typename std::set<Key, Compare, Allocator>::size_type count = 0;
    while (iter != set.end()) {
        if (pred(*iter)) {
            iter = set.erase(iter);
            ++count;
        } else {
            ++iter;
        }
    }
    return count;
}

template <typename Key,
    typename Compare = std::less<Key>,
    typename Allocator = std::allocator<Key>>
set(std::initializer_list<Key>, Compare = Compare(),
    Allocator = Allocator()) -> set<Key, Compare, Allocator>;

template <typename Key, typename Allocator>
set(std::initializer_list<Key>, Allocator)
    -> set<Key, std::less<Key>, Allocator>;

} // namespace std

#endif