AnySet.h

#ifndef ANY_SET_H
#define ANY_SET_H

#ifdef _MSC_VER
# include <iso646.h>
#endif 

#include <functional>
#include <cstddef>
#include <cmath>
#include "AnyList.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <type_traits>
#include <bitset>
#include "AnyHash.h"
#include "CompressedPair.h"


namespace te {

namespace detail {

template <typename T, typename = void>
struct is_iterator
{
    static constexpr const bool value = false;
};

template <typename T>
struct is_iterator<T, std::enable_if_t<!std::is_same_v<typename std::iterator_traits<T>::value_type, void>>>
{
    static constexpr const bool value = true;
};

template <class T>
inline constexpr const bool is_iterator_v = is_iterator<T>::value;

} /* namespace detail */

template <
    class HashFn = AnyHash,
    class KeyEqual = std::equal_to<>,
    class Allocator = std::allocator<AnyValue<HashFn, KeyEqual>>
>
struct AnySet:
    private CompressedPair<HashFn, KeyEqual>
{
private:
    using self_type = AnySet<HashFn, KeyEqual, Allocator>;
    using list_type = detail::AnyList<HashFn, KeyEqual>;
    using list_iterator = typename list_type::iterator;
    using const_list_iterator = typename list_type::const_iterator;

public:
    struct iterator:
        public list_iterator
    {
        using value_type        = typename AnySet::value_type;
        using reference         = typename AnySet::reference;
        using pointer           = typename AnySet::pointer;
        using difference_type   = typename AnySet::difference_type;
        using iterator_category = std::forward_iterator_tag;

        using list_iterator::list_iterator;
        using list_iterator::operator=;

        iterator(const list_iterator& it):
            list_iterator(it)
        {
            
        }
    private:
        
        iterator to_non_const() const
        { 
            return iterator(
                static_cast<const list_iterator&>(*this).to_non_const()
            ); 
        }
        friend struct AnySet;
    };

    struct const_iterator:
        public const_list_iterator
    {
        using value_type        = typename AnySet::value_type;
        using reference         = typename AnySet::const_reference;
        using pointer           = typename AnySet::const_pointer;
        using difference_type   = typename AnySet::difference_type;
        using iterator_category = std::forward_iterator_tag;

        const_iterator(const const_list_iterator& it):
            const_list_iterator(it)
        {
            
        }

        const_iterator(const list_iterator& it):
            const_list_iterator(it)
        {
            
        }

        const_iterator& operator=(const iterator& other)
        {
            return *this = const_iterator(other);
        }

        using const_list_iterator::const_list_iterator;
        using const_list_iterator::operator=;
    private:

        iterator to_non_const() const
        { 
            return iterator(
                static_cast<const const_list_iterator&>(*this).to_non_const()
            ); 
        }
        friend struct AnySet;
    };

private:
    using table_allocator = typename std::allocator_traits<Allocator>::template rebind_alloc<iterator>;
    using vector_type = std::vector<iterator, table_allocator>;
    using pair_type = CompressedPair<HashFn, KeyEqual>;
    using vector_iterator = typename vector_type::iterator;
    using const_vector_iterator = typename vector_type::const_iterator;

    template <class T>
    struct KeyInfo {
        const T& value;
        const std::size_t hash;
        std::size_t bucket;
    };

public:
    using value_type = AnyValue<HashFn, KeyEqual>;
    using size_type = typename vector_type::size_type;
    using difference_type = typename vector_type::difference_type;
    using key_equal = KeyEqual;
    using hasher = HashFn;
    using allocator_type = Allocator;
    using key_type = value_type;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using node_handle = std::unique_ptr<value_type>;

private:
    static size_type next_highest_pow2(size_type n)
    {
        size_type i = 1;
        while(i <= n)
        {
            assert(i * 2 > i);
            i *= 2;
        }
        return i;
    }

    allocator_type alloc_socca() const
    {
        return std::allocator_traits<allocator_type>::select_on_container_copy_construction(
            get_allocator()
        );
    }

    template <bool IsConst> 
    struct BucketIterator:
        private std::conditional_t<IsConst, const_iterator, iterator>
    {
    private:
        using self_type = BucketIterator<IsConst>;
        using base_type = std::conditional_t<IsConst, const_iterator, iterator>;
    public:
        using value_type        = typename base_type::value_type;
        using reference         = typename base_type::reference;
        using pointer           = typename base_type::pointer;
        using difference_type   = typename base_type::difference_type;
        using iterator_category = typename base_type::iterator_category;

        BucketIterator() = default;

        friend bool operator==(const BucketIterator<IsConst>& left, const BucketIterator<IsConst>& right)
        {
            if((left.bucket_ != right.bucket_) or (left.mask_ != right.mask_))
            {
                // Different buckets or different masks.
                return false;
            }
            if(
                (left.get_pos().is_null() or left.is_past_the_end()) 
                and (right.get_pos().is_null() or right.is_past_the_end())
            )
            {
                return true;
            }
            return left.get_pos() == right.get_pos();
        }

        friend bool operator!=(const BucketIterator<IsConst>& left, const BucketIterator<IsConst>& right)
        { return not (left == right); }

        self_type& operator++()
        {
            ++get_pos();
            return *this;
        }

        self_type operator++() const
        {
            auto cpy = *this;
            ++*this;
            return cpy;
        }

        using base_type::operator->;
        using base_type::operator*;

    private:
        BucketIterator(base_type pos, std::size_t bucket, std::size_t table_size):
            base_type(pos), bucket_(bucket), mask_(table_size - 1u)
        {
            
        }

        bool is_past_the_end() const
        {
            assert(not get_pos().is_null());
            // Returns true if 'pos_' is past-the-end for the whole list or the element pointed to by
            // 'pos_' has a hash in a different bucket (past-the-end for this bucket).
            return get_pos().is_end() or ((get_pos()->hash & mask_) != bucket_);
        }

        BucketIterator<false> to_non_const() const
        {
            return BucketIterator<false>(
                get_pos().to_non_const(), bucket_, mask_ + 1
            );
        }

        const base_type& get_pos() const
        { return static_cast<const base_type&>(*this); }

        base_type& get_pos()
        { return static_cast<base_type&>(*this); }

        std::size_t bucket_{0};
        std::size_t mask_{0};
        template <class, class, class>
        friend struct AnySet;
    };
    
public:
    using local_iterator = BucketIterator<false>;
    using const_local_iterator = BucketIterator<true>;

    void _assert_invariants(bool check_load_factor = false) const
    {
        list_._assert_invariants();
        assert(table_size() > 0u);
        assert(((table_size() & (table_size() - 1)) == 0u) and "Table size not a power of two.");
        assert(max_load_factor_ > 0.0);
        auto iter_dist = std::distance(cbegin(), cend());
        assert(iter_dist >= 0);
        assert(static_cast<size_type>(iter_dist) == size());
        assert(std::all_of(table_.begin(), table_.end(), [](const auto& v){ return v.is_null() or not v.is_end();}));
        for(size_type i = 0; i < bucket_count(); ++i)
        {
            // each bucket is sorted WRT hash values of the nodes in the bucket
            assert(std::is_sorted(
                this->begin(i),
                this->end(i),
                [](const auto& l, const auto& r){ return l.hash < r.hash; }
            ));
            assert(std::all_of(begin(i), end(i), [&](const auto& v){ return bucket_index(v.hash) == i; }));
        }
        // the load factor is allowed to be not satisfied if the user changed the max_load_factor().
        // we only do this assertion when asked to
        if(check_load_factor)
            assert(load_factor_satisfied());
    }

    ~AnySet() = default;


    AnySet(): AnySet(size_type(0)) { }

    explicit AnySet(
        size_type bucket_count,
        const HashFn& hash = HashFn(),
        const KeyEqual& equal = KeyEqual(),
        const Allocator& alloc = Allocator()
    ):
        pair_type(hash, equal),
        table_(next_highest_pow2(bucket_count), iterator(), allocator_type(alloc))
    {
        
    }

    AnySet(size_type bucket_count, const Allocator& alloc):
        AnySet(bucket_count, HashFn(), KeyEqual(), alloc) 
    {
        
    }
    
    AnySet(size_type bucket_count, const HashFn& hash, const Allocator& alloc):
        AnySet(bucket_count, hash, KeyEqual(), alloc)
    {
        
    }

    template <class InputIt>
    AnySet(
        InputIt first, 
        InputIt last,
        size_type bucket_count = 0,
        const HashFn& hash = HashFn(),
        const KeyEqual& equal = KeyEqual(),
        const Allocator& alloc = Allocator()
    ):
        AnySet(bucket_count, hash, equal, alloc)
    {
        insert(first, last);
    }

    template <class InputIt>
    AnySet(
        InputIt first, 
        InputIt last,
        size_type bucket_count,
        const Allocator& alloc
    ):
        AnySet(first, last, bucket_count, HashFn(), KeyEqual(), alloc)
    {
        
    }

    template <class InputIt>
    AnySet(
        InputIt first, 
        InputIt last,
        size_type bucket_count,
        const HashFn& hash,
        const Allocator& alloc
    ):
        AnySet(first, last, bucket_count, hash, KeyEqual(), alloc)
    {
        
    }

    AnySet(const AnySet& other, const Allocator& alloc):
        pair_type(other.as_pair()),
        list_(other.list_),
        table_(0, alloc),
        max_load_factor_(other.max_load_factor_)
    {
        table_.assign(other.table_.size(), iterator());
        list_type tmp(std::move(list_));
        assert(size() == 0u);
        node_handle node{nullptr};
        while(not tmp.empty())
        {
            node = std::move(tmp.pop(tmp.begin()).first);
            node = std::move(push(std::move(node)));
            assert(not static_cast<bool>(node));
        }
        assert(tmp.empty());
    }

    AnySet(const AnySet& other):
        pair_type(other.as_pair()),
        list_(other.list_, list_type::make_copy),
        table_(0, other.alloc_socca()),
        max_load_factor_(other.max_load_factor_)
    {
        table_.resize(other.table_.size());
        list_type tmp(std::move(list_));
        assert(size() == 0u);
        node_handle node{nullptr};
        while(not tmp.empty())
        {
            node = std::move(tmp.pop(tmp.begin()).first);
            node = std::move(push(std::move(node)).second);
            assert(not static_cast<bool>(node));
        }
        assert(tmp.empty());
    }

    AnySet(AnySet&& other, const Allocator& alloc):
        pair_type(std::move(other.as_pair())),
        list_(std::move(other.list_)),
        table_(std::move(other.table_), alloc),
        max_load_factor_(other.max_load_factor_)
    {
        fix_table_after_move();
        assert(other.empty());
        if(other.table_.size() == 0u)
            other.table_.assign(1u, iterator());
    }

    AnySet(AnySet&& other):
        pair_type(std::move(other.as_pair())),
        list_(std::move(other.list_)),
        table_(std::move(other.table_)),
        max_load_factor_(other.max_load_factor_)
    {
        fix_table_after_move();
        assert(other.empty());
        if(other.table_.size() == 0u)
            other.table_.assign(1u, iterator());
    }

    template <class T>
    AnySet(
        std::initializer_list<T> ilist,
        size_type bucket_count = 0,
        const HashFn& hash = HashFn(),
        const KeyEqual& equal = KeyEqual(),
        const Allocator& alloc = Allocator()
    ):
        AnySet(ilist.begin(), ilist.end(), bucket_count, hash, equal, alloc)
    {
        
    }

    template <class T>
    AnySet(
        std::initializer_list<T> ilist,
        size_type bucket_count,
        const Allocator& alloc
    ):
        AnySet(ilist, bucket_count, HashFn(), KeyEqual(), alloc)
    {
        
    }

    template <class T>
    AnySet(
        std::initializer_list<T> ilist,
        size_type bucket_count,
        const HashFn& hash,
        const Allocator& alloc
    ):
        AnySet(ilist, bucket_count, hash, KeyEqual(), alloc)
    {
        
    }

    template <class ... T>
    AnySet(
        std::tuple<T ...>&& tup,
        size_type bucket_count = 2 * (sizeof...(T)),
        const HashFn& hash = HashFn(),
        const KeyEqual& equal = KeyEqual(),
        const Allocator& alloc = Allocator()
    ):
        AnySet(bucket_count, hash, equal, alloc)
    {
        std::apply(
            [&](auto&& ... args) { 
                this->arg_insert(std::forward<decltype(args)>(args)...); 
            },
            std::move(tup)
        );
        
    }

    template <class ... T>
    AnySet(
        std::tuple<T ...>&& tup,
        size_type bucket_count,
        const Allocator& alloc
    ):
        AnySet(std::move(tup), bucket_count, HashFn(), KeyEqual(), alloc)
    {
        
    }

    template <class ... T>
    AnySet(
        std::tuple<T ...>&& tup,
        size_type bucket_count,
        const HashFn& hash,
        const Allocator& alloc
    ):
        AnySet(std::move(tup), bucket_count, hash, KeyEqual(), alloc)
    {
        
    }



    AnySet& operator=(const AnySet& other)
    { return *this = std::move(self_type(other)); }

    AnySet& operator=(AnySet&& other) noexcept(std::is_nothrow_move_assignable_v<vector_type>)
    {
        as_pair() = std::move(other.as_pair());
        list_ = std::move(other.list_);
        table_ = std::move(other.table_);
        max_load_factor_ = std::move(other.max_load_factor_);
        fix_table_after_move();
        assert(other.empty());
        if(other.table_.size() == 0u)
            other.table_.assign(1u, iterator());
        return *this;
    }

    template <class T>
    AnySet& operator=(std::initializer_list<T> ilist)
    { return *this = self_type(ilist); }



    const_iterator cbegin() const
    { return list_.cbegin(); }

    const_iterator begin() const
    { return cbegin(); }

    iterator begin() 
    { return list_.begin(); }

    const_iterator cend() const
    { return list_.cend(); }

    const_iterator end() const
    { return cend(); }

    iterator end()
    { return list_.end(); }



    [[nodiscard]]
    bool empty() const noexcept
    { return not static_cast<bool>(size()); }

    size_type size() const noexcept
    { return list_.size(); }

    size_type max_size() const noexcept
    { return std::numeric_limits<typename list_type::size_type>::max(); }



    void clear() noexcept
    {
        list_.clear();
        std::fill(table_.begin(), table_.end(), iterator());
    }
    
    template <class T, class ... Args>
    std::pair<iterator, bool> emplace(Args&& ... args)
    {
        static_assert(
            std::is_same_v<T, std::decay_t<T>>,
            "Cannot emplace references, arrays, or functions into an AnySet."
        );
        auto node(make_any_value<T, HashFn, KeyEqual>(get_hasher(), std::forward<Args>(args)...));
        auto hash_v = node->hash;
        KeyInfo<T> ki{unsafe_cast<const T&>(*node), hash_v, bucket_index(hash_v)};
        return insert_impl<true>(ki.value, ki, std::move(node));
    }
    
    template <class T, class ... Args>
    std::pair<iterator, bool> emplace_hint([[maybe_unused]] const_iterator hint, Args&& ... args)
    { return emplace<T>(std::forward<Args>(args)...); }

    template <class T>
    std::pair<iterator, bool> insert(T&& value)
    {
        return insert_impl<true>(std::forward<T>(value), make_key_info(value));
    }

    template <class T>
    std::pair<iterator, bool> insert([[maybe_unused]] const_iterator hint, T&& value)
    { return insert(std::forward<T>(value)); }

    template <
        class It, 
        class = std::enable_if_t<
            std::is_copy_constructible_v<typename std::iterator_traits<It>::value_type>
            or std::is_rvalue_reference_v<decltype(*std::declval<It>())>
        >
    >
    size_type insert(It first, It last)
    {
        using iter_cat = typename std::iterator_traits<It>::iterator_category;
        return range_insert(first, last, iter_cat{});
    }

    template <
        class T, 
        class U, 
        class ... V,
        class = std::enable_if_t<
            (not (std::is_same_v<std::decay_t<T>, std::decay_t<U>> and detail::is_iterator_v<std::decay_t<T>>))
            and (not std::is_same_v<std::decay_t<T>, const_iterator>)
            and (not std::is_same_v<std::decay_t<T>, iterator>)
        >
    >
    std::bitset<2ull + sizeof...(V)> insert(T&& first, U&& second, V&& ... args)
    {
        return arg_insert(
            std::forward<T>(first),
            std::forward<U>(second),
            std::forward<V>(args) ...
        );
    }
    
    template <class T, class = std::enable_if_t<std::is_copy_constructible_v<T>>>
    size_type insert(std::initializer_list<T> ilist)
    {
        return insert(ilist.begin(), ilist.end());
    }

    iterator erase(const_iterator pos)
    {
        return pop(pos).second;
    }

    iterator erase(const_iterator first, const_iterator last)
    {
        iterator pos = first.to_non_const();
        if(first == last)
            return pos;
        bool done = false;
        do {
            // hop over 'pos' and check if we've reached the end
            auto nxt = std::next(first);
            done = (nxt == last);
            pos = erase(pos);
        } while(not done);
        return pos.to_non_const();
    }

    template <class T, class = std::enable_if_t<not (std::is_same_v<const_iterator, T> or std::is_same_v<iterator, T>)>>
    size_type erase(const T& value)
    {
        auto [pos, found] = find_position(make_key_info(value));
        if(found)
            erase(pos);
        return static_cast<size_type>(found);
    }

    void swap(AnySet& other) 
        noexcept(std::is_nothrow_swappable_v<vector_type> and std::is_nothrow_swappable_v<pair_type>)
    {
        using std::swap;
        swap(as_pair(), other.as_pair());
        swap(list_, other.list_);
        swap(table_, other.table_);
        swap(max_load_factor_, other.max_load_factor_);
        this->fix_table_after_move();
        other.fix_table_after_move();
    }

    AnySet& update(const AnySet& other)
    {
        preemptive_reserve(other.size());
        for(const auto& any_v: other)
        {
            auto [pos, found] = find_position(make_key_info(any_v));
            if(found)
            {
                continue;
            }
            else
            {
                unsafe_splice_at(pos, any_v.clone());
            }
        }
        assert(load_factor_satisfied());
        return *this;
    }

    AnySet& update(AnySet&& other)
    {
        preemptive_reserve(other.size());
        for(auto pos = other.begin(); pos != other.end(); )
        {
            auto [ins_pos, found] = find_position(make_key_info(*pos));
            if(found)
            {
                ++pos;
            }
            else
            {
                node_handle node;
                std::tie(node, pos) = other.pop(pos);
                unsafe_splice_at(ins_pos, std::move(node));
            }
        }
        return *this;
    }



    template <class T>
    size_type count(const T& value) const
    {
        return static_cast<size_type>(
            find_position(make_key_info(value)).second
        );
    }

    template <class T>
    const_iterator find(const T& value) const
    {
        auto [pos, found] = find_position(make_key_info(value));
        if(found)
            return pos;
        else
            return cend();
    }

    template <class T>
    iterator find(const T& value)
    {
        return static_cast<const self_type*>(this)->find(value).to_non_const();
    }

    template <class T>
    std::pair<const_iterator, const_iterator> equal_range(const T& value) const
    {
        auto pos = find(value);
        if(pos != cend())
            return std::make_pair(pos, std::next(pos));
        else
            return std::make_pair(cend(), cend());
    }

    template <class T>
    std::pair<iterator, iterator> equal_range(const T& value)
    {
        auto [first, last] = static_cast<const self_type*>(this)->equal_range(value);
        return std::make_pair(
            first.to_non_const(),
            last.to_non_const()
        );
    }

    bool contains_value(const value_type& any_v) const
    {
        return contains(any_v);
    }

    bool contains_value_eq(const value_type& any_v) const
    { return find_matching_value(any_v) != cend(); }

    template <class T>
    bool contains(const T& value) const
    {
        return count(value);
    }
    
    template <class T>
    bool contains_eq(const T& value) const
    { return find_matching_value(value) != cend(); }
    


    const_local_iterator cbegin(size_type buck) const
    {
        assert(buck < bucket_count());
        return const_local_iterator(table_[buck], buck, table_size());
    }

    const_local_iterator begin(size_type buck) const
    { return cbegin(buck); }

    local_iterator begin(size_type buck)
    { return cbegin(buck).to_non_const(); }

    const_local_iterator cend(size_type buck) const
    {
        assert(buck < bucket_count());
        return const_local_iterator(const_iterator(), buck, table_size());
    }

    const_local_iterator end(size_type buck) const
    { return cend(buck); }

    local_iterator end(size_type buck)
    { return cend(buck).to_non_const(); }

    size_type bucket_count() const noexcept
    { return table_size(); }

    size_type max_bucket_count() const noexcept
    { 
        size_type maxm = ~((~size_type(0)) >> 1);
        while(maxm > table_.max_size())
            maxm >>= 1;
        return maxm;
    }

    size_type bucket_size(size_type buck) const
    {
        assert(buck < bucket_count());
        return static_cast<size_type>(
            std::distance(cbegin(buck), cend(buck))
        );
    }

    template <class T>
    size_type bucket(const T& value) const
    { return bucket_index(get_hasher()(value)); }



    void max_load_factor(float f)
    {
        assert(f > 0.0);
        max_load_factor_ = f;
    }
    
    float max_load_factor() const noexcept
    { return max_load_factor_; }

    float load_factor() const noexcept
    { return static_cast<double>(size()) / table_size(); }
    
    void rehash(size_type nbuckets)
    {
        size_type bcount = bucket_count();
        assert(bcount > 0u);
        auto load_factor_good = [&]() {
            return (static_cast<double>(size()) / bcount) <= max_load_factor_;
        };
        if(nbuckets < bcount)
        {
            if(nbuckets == 0u)
                nbuckets = 1u;
            while(nbuckets < bcount and load_factor_good())
                bcount /= 2;
            if((bcount == bucket_count()) and load_factor_good())
                return;
            
        }
        else if(nbuckets > bcount)
        {
            assert(max_bucket_count() >= nbuckets);
            while(nbuckets > bcount)
            {
                assert(bcount > 0u);
                bcount *= 2;
            }
        }
        while(not load_factor_good())
            bcount *= 2;
        if(bcount > bucket_count())
            grow_table(bcount);
        else if(bcount < bucket_count())
            shrink_table(bcount);
    }

    void reserve(size_type count)
    {
        rehash(static_cast<size_type>(std::ceil(count / max_load_factor())));
    }



    hasher hash_function() const
    { return get_hasher(); }

    key_equal key_eq() const
    { return get_key_equal(); }

    allocator_type get_allocator() const
    { return table_.get_allocator(); }



    friend void swap(AnySet& left, AnySet& right)
    { return left.swap(right); }

    friend bool operator==(const AnySet& left, const AnySet& right)
    {
        if(left.size() != right.size())
            return false;
        // iterate over the set with the smaller table.
        const auto& iter_set = (left.table_size() > right.table_size()) ? right : left;
        // search through the set with the larger table
        const auto& search_set = (&left == &iter_set) ? right : left;
        for(const auto& item: iter_set)
        {
            auto pos = search_set.find_matching_value(item);
            if(pos.is_end())
            {
                return false;
            }
        }
        return true;
    }

    friend bool operator!=(const AnySet& left, const AnySet& right)
    { return not (left == right); }



    std::pair<node_handle, iterator> pop(const_iterator pos_)
    {
        assert(not pos_.is_end());
        assert(not pos_.is_null());

        iterator pos = pos_.to_non_const();
        size_type buck_idx = iter_bucket_index(pos);
        iterator bucket_head = table_[buck_idx];

        assert(not bucket_head.is_null());
        assert(not bucket_head.is_end());

        if(bucket_head == pos)
        {
            // 'pos' is the first item in its bucket.
            auto [node, next] = std::move(list_.pop(pos));
            if(next.is_end())
            {
                // 'pos' was the last item in 'list_'.  The bucket is now empty.
                table_[buck_idx] = iterator();
                return std::make_pair(std::move(node), end());
            }

            if(size_type next_idx = iter_bucket_index(next); next_idx != buck_idx)
            {
                // The const_iterator after 'bucket_head' is in a different bucket.
                // 'pos' was the last item in its bucket and the bucket is now empty.
                // Since we just invalidated all iterators to the element following
                // 'pos', we need to fix iterator in the bucket whose first element
                // was pointed to by next(pos).
                table_[buck_idx] = iterator();
                // Fix the iterator we invalidated.
                table_[next_idx] = next;
            }
            else
            {
                // 'pos' was *not* the last element in its bucket.  The iterator
                // stored in the bucket should automagically point to the next
                // item.  Nothing to fix.
                assert(table_[buck_idx] == next);
            }
            return std::make_pair(std::move(node), next); 
        }
        else
        {
            // 'pos' is *not* the first item in its bucket.
            auto [node, next] = std::move(list_.pop(pos));
            if(next.is_end())
            {
                // 'pos' was the last item in the whole list.  Nothing to fix.
                return std::make_pair(std::move(node), end());
            }

            if(size_type next_idx = iter_bucket_index(next); next_idx != buck_idx)
            {
                // 'pos' was the last item in its bucket.  
                // Since we just invalidated all iterators to the element following
                // 'pos', we need to fix iterator in the bucket whose first element
                // was pointed to by next(pos).
                table_[next_idx] = next;
            }
            else
            {
                // 'pos' was *not* the last element in its bucket.  The iterator
                // stored in the bucket should automagically point to the next
                // item.  Nothing to fix.
                assert(table_[buck_idx] == next);
            }
            return std::make_pair(std::move(node), next); 
        }
    }

    node_handle dup(const_iterator pos) const
    { return pos->clone(); }

    std::pair<iterator, node_handle> push(node_handle&& node)
    {
        auto [pos, found] = find_position(make_key_info(*node));
        if(found)
            return std::make_pair(pos.to_non_const(), std::move(node));
        iterator ins_pos = safely_splice_at(pos, std::move(node));
        return std::make_pair(ins_pos, node_handle(nullptr));
    }

    
    std::tuple<iterator, iterator, bool> splice(AnySet& other, const_iterator pos)
    { return splice_or_copy(std::move(other), pos); }

    std::pair<iterator, iterator> splice(AnySet& other, const_iterator first, const_iterator last)
    { return splice_or_copy(std::move(other), first, last); }

    template <class T, class = std::enable_if_t<std::is_same_v<std::decay_t<T>, self_type>>>
    auto splice_or_copy(T&& other, const_iterator first, const_iterator last)
        -> std::pair<decltype(other.begin()), decltype(other.begin())> 
    {
        if(first == last)
            return std::make_pair(first.to_non_const(), last.to_non_const());
        preemptive_reserve(std::distance(first, last));
        auto pos = first;
        bool done = false;
        do {
            done = (std::next(pos) == last);
            std::tie(std::ignore, pos, std::ignore) = splice_or_copy(std::forward<T>(other), pos);
        } while(not done);
        return std::make_pair(first.to_non_const(), pos.to_non_const());
    }

    template <class T, class = std::enable_if_t<std::is_same_v<std::decay_t<T>, self_type>>>
    auto splice_or_copy(T&& other, const_iterator pos)
        -> std::tuple<iterator, decltype(other.begin()), bool>
    {
        using tuple_t = std::tuple<iterator, decltype(other.begin()), bool>;
        assert(not pos.is_end());
        auto ki = make_key_info(*pos);
        auto [ins_pos_, found] = find_position(ki);
        auto ins_pos = ins_pos_.to_non_const();
        if(found)
            return tuple_t(ins_pos, std::next(pos).to_non_const(), false);
        if constexpr(
            std::is_rvalue_reference_v<decltype(other)>
            and not std::is_const_v<std::remove_reference_t<decltype(other)>>
        )
        {
            auto [node, next] = other.pop(pos);
            try
            {
                assert(load_factor_satisfied());
                return tuple_t(
                    safely_splice_at(ins_pos, ki, std::move(node)), next.to_non_const(), true
                );
            }
            catch(...)
            {
                // put back the node if didn't make it in
                if(node)
                    other.unsafe_splice_at(pos, std::move(node));
                throw;
            }
        }
        else
        {
            assert(load_factor_satisfied());
            return tuple_t(
                safely_splice_at(ins_pos, ki, other.dup(pos)), 
                std::next(pos).to_non_const(), 
                true
            );
        }
    }


private:

    void fix_table_after_move()
    {
        if(size() > 0u)
            table_[iter_bucket_index(begin())] = begin();
    }

    float load_factor(size_type extra) const noexcept
    { return static_cast<double>(size() + extra) / table_size(); }
    
    bool load_factor_satisfied(size_type extra = 0) const
    { return load_factor(extra) <= max_load_factor(); }

    iterator safely_splice_at(const_iterator pos, node_handle&& node)
    {
        return safely_splice_at(pos, make_key_info(*node), std::move(node));
    }

    template <class Value>
    iterator safely_splice_at(const_iterator pos, const KeyInfo<Value>& ki, node_handle&& node)
    {
        // Insert the node, *then* check if a rehash is needed.  This optimizes for the case
        // where we don't rehash (which is almost certainly the common case) and doing it this 
        // way results in simpler code.
        iterator ins_pos = unsafe_splice_at(pos, ki, std::move(node));

        if(not load_factor_satisfied()) 
        {
            // However, we want rollback semantics if resizing the bucket table throws an exception.
            // Use the scope guard pattern instead of a try-catch-rethrow.  This lets the compiler possibly
            // optimize the guard out entirely if callers don't have an exception handler (many 
            // implementations only propagate exceptions when there's a handler beneath the throw).
            struct RollbackScopeGuard {
                self_type& self; // *this
                const_iterator pos; // iterator to erase 
                bool good = false; // whether we
                
                ~RollbackScopeGuard()
                {
                    // If growing failed, erase the value we just inserted.
                    // This gives us rollback/commit semantics and only pessimizes
                    // the uncommon case.
                    if(not good) 
                        // Control flow only reach here if an exception is thrown by 'grow_table'.
                        self.erase(pos);
                }
            } guard{*this, pos, false};

            // Before we grow the table, save the address of the inserted node, we'll need it
            // to find the node again after rehashing.
            const value_type* addr_save = std::addressof(*ins_pos);

            grow_table(2 * table_size());

            // No exceptions thrown.
            guard.good = true;

            // the key landed somewhere else now, go find it to give the caller their iterator.
            auto buck_idx = bucket_index(ki.hash);
            auto buck_pos = table_[buck_idx];
            assert(not buck_pos.is_null());
            assert(not buck_pos.is_end());
            while(std::addressof(*buck_pos) != addr_save)
            {
                ++buck_pos;
                assert(iter_bucket_index(buck_pos) == buck_idx);
            }
            return buck_pos.to_non_const();
        }
        else
        {
            // No rehash, just return ins_pos.
            return ins_pos;
        }
    }

    template <class Value>
    iterator initialize_bucket(const KeyInfo<Value>& ki, node_handle&& node)
    {
        assert(table_[ki.bucket].is_null());
        return table_[ki.bucket] = list_.push_back(std::move(node));
    }

    iterator unsafe_splice_at(const_iterator pos, node_handle&& node)
    {
        return unsafe_splice_at(pos, make_key_info(*node), std::move(node));
    }

    template <class Value>
    iterator unsafe_splice_at(const_iterator pos, const KeyInfo<Value>& ki, node_handle&& node)
    {
        if(pos.is_null())
            return initialize_bucket(ki, std::move(node));
        else if(pos.is_end())
            return list_.splice(pos, std::move(node));

        size_type buck_idx = iter_bucket_index(pos);
        iterator ins_pos = list_.splice(pos, std::move(node));
        if(buck_idx != ki.bucket)
        {
            // The iterator that we just inserted changed the value of an iterator 
            // in another bucket.  The iterator whose value changed should now point 
            // to the 'next' of the node we just inserted.  Make it so.
            auto next_pos = std::next(ins_pos);
            assert(iter_bucket_index(next_pos) == buck_idx);
            table_[buck_idx] = next_pos;
        }
        return ins_pos;
    }

    template <class Value>
    bool insertion_compare(const Value& value, const value_type& any_v) const
    { return compare(value, any_v, get_key_equal()); }

    template <class Value>
    bool insertion_compare(const value_type& any_v, const Value& value) const
    { return compare(any_v, value, get_key_equal()); }

    template <class Value>
    std::size_t get_hash_value(const Value& value) const
    {
        if constexpr(std::is_same_v<Value, value_type>)
            return value.hash;
        else
            return get_hasher()(value);
    }
    
    size_type iter_bucket_index(const_iterator pos) const
    {
        assert(not pos.is_end());
        return bucket_index(pos->hash);
    }

    template <class Value>
    KeyInfo<Value> make_key_info(const Value& val) const
    {
        return make_key_info(val, get_hash_value(val));
    }

    template <class Value>
    KeyInfo<Value> make_key_info(const Value& val, std::size_t hash_v) const
    {
        return KeyInfo<Value>{val, hash_v, bucket_index(hash_v)};
    }

    template <class Value>
    const_iterator find_matching_value(const Value& value) const
    {
        auto ki = make_key_info(value);
        auto [pos, last] = get_bucket_start(ki);
        if(pos.is_null() or (not last.is_null()))
            return cend();

        while((not pos.is_end()) and (pos->hash == ki.hash))
        {
            if(*pos == value)
                return const_iterator(pos);
            ++pos;
        }
        return cend();
    }

    template <class ... T>
    std::bitset<sizeof...(T)> arg_insert(T&& ... args)
    {
        std::bitset<sizeof...(T)> bs;
        std::size_t pos = 0;
        preemptive_reserve(sizeof...(args));

        // set the ith bit if the ith arg was inserted
        (bs.set(pos++, insert_impl<false>(std::forward<T>(args)).second) , ...);

        assert(load_factor() <= max_load_factor());
        return bs;
    }

    template <class It>
    size_type range_insert(It first, It last, std::input_iterator_tag)
    {
        size_type count = 0;
        while(first != last)
            count += static_cast<size_type>(insert_impl<true>(*first++).second);
        return count;
    }

    template <class It, class = std::enable_if_t<std::is_copy_constructible_v<typename std::iterator_traits<It>::value_type>>>
    size_type range_insert(It first, It last, std::forward_iterator_tag)
    {
        size_type count = 0;
        preemptive_reserve(std::distance(first, last));
        while(first != last)
            count += static_cast<size_type>(insert_impl<false>(*first++).second);
        assert(load_factor() <= max_load_factor());
        return count;
    }

    void preemptive_reserve(std::size_t ins_count)
    {
        auto new_count = size() + ins_count;
        size_type new_table_size = table_size();
        assert(new_table_size > 0u);
        auto compute_new_load_factor = [&](){
            return (static_cast<double>(new_count) / new_table_size);
        };
        while(compute_new_load_factor() > max_load_factor())
            new_table_size *= 2;
        if(new_table_size > table_size())
            grow_table(new_table_size);
    }

    template <bool CheckLoadFactor, class T>
    std::pair<iterator, bool> insert_impl(T&& value)
    {
        return insert_impl<CheckLoadFactor>(
            std::forward<T>(value), make_key_info(value), nullptr
        );
    }
    
    template <bool CheckLoadFactor, class T>
    std::pair<iterator, bool> insert_impl(
        T&& value,
        const KeyInfo<std::decay_t<T>>& ki,
        node_handle existing = nullptr
    )
    {
        using ValueType = std::decay_t<T>;
        iterator ins_pos;
        auto [pos, found] = find_position(ki);
        
        if(not found)
        {
            // if constexpr(std::is_copy_constructible_v<ValueType>)
            if constexpr(std::is_constructible_v<ValueType, decltype(value)>)
            {
                if(not existing)
                {
                    existing = make_any_value<std::decay_t<T>, HashFn, KeyEqual>(
                        ki.hash, std::forward<T>(value)
                    );
                }
            }
            else
            {
                assert(existing);
            }

            if constexpr(CheckLoadFactor)
                ins_pos = safely_splice_at(pos, ki, std::move(existing));
            else
                ins_pos = unsafe_splice_at(pos, ki, std::move(existing));
            assert(not ins_pos.is_null());
            assert(not ins_pos.is_end());
        }
        else
        {
            ins_pos = pos.to_non_const();
        }
        return std::make_pair(ins_pos, not found);
    }

    void shrink_table(size_type new_size) noexcept
    {
        assert(new_size < table_size());
        // new size must always be a power of two
        assert((new_size & (new_size - 1)) == 0u);

        table_.assign(new_size, iterator());

        list_type tmp = std::move(list_);
        assert(size() == 0u);
        node_handle node{nullptr};
        while(not tmp.empty())
        {
            node = std::move(tmp.pop(tmp.begin()).first);
            node = std::move(push(std::move(node)).second);
            assert(not static_cast<bool>(node));
        }
        assert(tmp.empty());
    }

    void grow_table(size_type new_size)
    {
        assert(new_size > table_size());
        // new size must always be a power of two
        assert((new_size & (new_size - 1)) == 0u);
        table_.assign(new_size, iterator());
        list_type tmp = std::move(list_);
        assert(size() == 0u);
        node_handle node{nullptr};
        while(not tmp.empty())
        {
            node = std::move(tmp.pop(tmp.begin()).first);
            node = std::move(push(std::move(node)).second);
            assert(not static_cast<bool>(node));
        }
        assert(tmp.empty());
    }

    template <class Value>
    std::pair<const_iterator, bool> find_position(const KeyInfo<Value>& ki) const
    { return find_position(ki, get_key_equal()); }

    template <class Value, class Comp>
    std::pair<const_iterator, bool> find_position(const KeyInfo<Value>& ki, Comp comp) const
    {
        if(auto [pos, last] = get_bucket_start(ki); pos.is_null() and last.is_null())
        {
            // Bucket is empty, return null iterator.
            return std::make_pair(const_iterator(), false);
        }
        else if(last.is_null())
        {
            assert(pos->hash >= ki.hash);
            for(; (not pos.is_end()) and pos->hash == ki.hash; ++pos)
            {
                if(compare(ki.value, *pos, comp))
                    // found a match
                    return std::make_pair(pos, true);
            }
            // No match, return const_iterator to first element whose hash is
            // greater than ki's hash, or the end of the list, which ever comes
            // first.
            return std::make_pair(pos, false);
        }
        else
        {
            assert(not pos.is_null());
            assert(last == cend() or iter_bucket_index(last) != ki.bucket);
            // No match, return end of the bucket.
            return std::make_pair(last, false);
        }
    }

    template <class Value>
    std::pair<const_iterator, const_iterator> get_bucket_start(const KeyInfo<Value>& ki) const
    {
        auto first = table_[ki.bucket];
        if(first.is_null())
            // two 'null' const_iterators
            return std::make_pair(const_iterator(), const_iterator()); 
        assert(not first.is_end());
        auto pos = first;
        std::size_t pos_hash = pos->hash;
        do {
            if(pos_hash >= ki.hash)
                return std::make_pair(pos, const_iterator());
            ++pos;
            if(pos.is_end())
                break;
            pos_hash = pos->hash;
        } while(bucket_index(pos_hash) == ki.bucket);
        return std::make_pair(first, pos);
    }

    size_type table_size() const
    { return table_.size(); }

    size_type get_mask() const
    { return table_size() - 1; }

    size_type bucket_index(std::size_t hash) const
    { return hash & get_mask(); }

    bool equal_values(const value_type& left, const value_type& right) const
    { return left.compare_to(right, get_key_equal()); }

    // functions to access the hasher and comparator
    pair_type& as_pair() &
    { return static_cast<pair_type&>(*this); }

    pair_type&& as_pair() &&
    { return static_cast<pair_type&&>(*this); }

    const pair_type& as_pair() const &
    { return static_cast<const pair_type&>(*this); }

    const pair_type&& as_pair() const &&
    { return static_cast<const pair_type&&>(*this); }

    HashFn& get_hasher() &
    { return as_pair().first(); }

    HashFn&& get_hasher() &&
    { return std::move(std::move(as_pair()).first()); }

    const HashFn& get_hasher() const &
    { return as_pair().first(); }

    const HashFn&& get_hasher() const &&
    { return std::move(std::move(as_pair()).first()); }

    KeyEqual& get_key_equal() &
    { return as_pair().second(); }

    KeyEqual&& get_key_equal() &&
    { return std::move(std::move(as_pair()).second()); }

    const KeyEqual& get_key_equal() const &
    { return as_pair().second(); }

    const KeyEqual&& get_key_equal() const &&
    { return std::move(std::move(as_pair()).second()); }

    list_type list_;
    vector_type table_;
    float max_load_factor_{1.0};
};

template <
    class HashFn = te::AnyHash,
    class KeyEqual = std::equal_to<>,
    class Allocator = std::allocator<te::AnyValue<HashFn, KeyEqual>>,
    class ... Elements
>
te::AnySet<HashFn, KeyEqual, Allocator> make_anyset(Elements&& ... elements)
{
    return te::AnySet<HashFn, KeyEqual, Allocator>(
        std::forward_as_tuple(std::forward<Elements>(elements)...)
    );
}


} /* namespace te */    

#endif /* ANY_SET_H */