StringMap.hpp

#ifndef LIB_STRING_MAP_H
#define LIB_STRING_MAP_H

#include <string>
#include <utility>
#include <iterator>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
#include <limits>
#include <stdexcept>

namespace lib
{

    namespace detail
    {
        struct range
        {
            constexpr range(std::size_t sz) : b(0), e(sz) {}
            constexpr range(std::size_t b, std::size_t e) : b(b), e(e) {}
            struct iterator
            {
                iterator& operator++() { ++i; return *this; }
                iterator operator++(int) { auto tmp = *this; ++i; return tmp; }
                iterator& operator--() { --i; return *this; }
                iterator operator--(int) { auto tmp = *this; --i; return tmp; }
                bool operator==(iterator other) const { return i==other.i; }
                bool operator!=(iterator other) const { return i!=other.i; }
                std::size_t operator*() const { return i; };
                std::size_t i;
            };
            std::size_t b, e;
            iterator begin() const { return {b}; }
            iterator end()   const { return {e}; }
        };
        static int ival(char c)
        {
            union X {
                unsigned char uc;
                char c;
            } x;
            x.c = c;
            return x.uc;
        }
    }

    static constexpr detail::range knodes = detail::range(1,256); // key nodes
    static constexpr detail::range anodes = detail::range(0,256); // all nodes

    template<
        typename T,                               // this is the mapped type
        typename Alloc = std::allocator<T>        // allocator, need to implement rebind
    >
    class StringMap
    {
        struct TreeElem;
    public:
        StringMap() noexcept;
        StringMap(const StringMap&);
        StringMap(StringMap&&) noexcept;
        StringMap& operator=(const StringMap&);
        StringMap& operator=(StringMap&&) noexcept;
        ~StringMap();

        void swap(StringMap&) noexcept;
        void swap(StringMap&&) noexcept;

        struct iterator;
        struct const_iterator;

        typedef std::string key_type;
        typedef T mapped_type;
        typedef T& reference;
        typedef T* pointer;

    private:
        struct iter_core
        {
            std::string key() const;
            void nxt();
            TreeElem* node;
            bool eq(const iter_core& other) const;
        };

    public:

        struct const_iterator :
            std::iterator<std::forward_iterator_tag,const_iterator>,
            private iter_core
        {
            std::string key() const; // O(log(n))
            const T& value() const; // O(1)
            const_iterator() { this->node = nullptr; }
            const_iterator& operator++() { this->nxt(); return *this; }
            const const_iterator operator*() { return *this; }
            const const_iterator* operator->() { return this; }
            const_iterator operator++(int) { const_iterator tmp = *this; this->nxt(); return tmp; }
            bool operator==(const const_iterator& other) const { return this->eq(other); }
            bool operator!=(const const_iterator& other) const { return ! this->eq(other); }
        private:
            const_iterator(TreeElem* p) { this->node = p; }
        friend
            class StringMap;
        friend
            struct iterator;
        };

        struct iterator :
            std::iterator<std::forward_iterator_tag,iterator>,
            private iter_core
        {
            std::string key() const; // O(log(n))
            T& value() const; // O(1)
            iterator() { this->node = nullptr; }
            iterator& operator++() { this->nxt(); return *this; }
            iterator operator*() { return *this; }
            iterator* operator->() { return this; }
            iterator operator++(int) { iterator tmp = *this; this->nxt(); return tmp; }
            bool operator==(const iterator& other) const { return this->eq(other); }
            bool operator!=(const iterator& other) const { return ! this->eq(other); }
            operator const_iterator() { return {this->node}; }
        private:
            iterator(TreeElem* p) { this->node = p; }
        friend
            class StringMap;
        };

        typedef iterator value_type;
        typedef const_iterator const_value_type;

        iterator begin();
        iterator end();

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

        T& operator[](const std::string&);

        T& at(const std::string&);
        const T& at(const std::string&) const;

        iterator find(const std::string&);
        const_iterator find(const std::string&) const;

        std::size_t count(const std::string&) const;

        iterator lower_bound(const std::string& key);
        const_iterator lower_bound(const std::string& key) const;

        iterator upper_bound(const std::string& key);
        const_iterator upper_bound(const std::string& key) const;

        std::pair< iterator, iterator > equal_range( const std::string& key );
        std::pair< const_iterator, const_iterator > equal_range( const std::string& key ) const;

        std::size_t size() const { return sz; }
        bool empty() const { return !sz; }

        static std::size_t max_size() noexcept { return std::numeric_limits<std::size_t>::max(); }

        typedef std::pair<iterator,bool> insert_result_type;

        insert_result_type insert(const std::string&, const T&);
        insert_result_type insert(const std::string&, T&&);

        template<typename... Args>
        insert_result_type emplace(const std::string&, Args&&...);

        template<typename... Args>
        insert_result_type try_emplace(const std::string& key, Args&&... args)
            { return emplace(key,std::forward<Args>(args)...); } // emplace already works like that for StringMap

        insert_result_type insert_or_assign(const std::string&, const T&);
        insert_result_type insert_or_assign(const std::string&, T&&);

        iterator erase(iterator);
        bool erase(const std::string&);
        iterator erase(iterator,iterator);

        void clear();

        void debugprint(std::ostream&) const;

        int compare(const StringMap&) const;

    private:

        struct TreeElem
        {
            T* leaf;
            TreeElem* nodes[256];
            TreeElem* nxt();
        };

        Alloc val_alloc;
        mutable typename Alloc::template rebind<TreeElem>::other node_alloc;

        std::size_t sz;

        mutable TreeElem sentinel;

        void recursive_clear_nodes( TreeElem* );

        TreeElem* make_node( bool clear=true ) const;
        template<typename... Args>
        void make_val( TreeElem*, Args&&... );
        void del_val( TreeElem* );
        void del_node( TreeElem* );

        TreeElem* lookup(const std::string&) const;
        TreeElem* create(const std::string&) const;

    };

    template<typename T,typename Alloc>
    StringMap<T,Alloc>::StringMap() noexcept
    {
        for( auto i : anodes )
            sentinel.nodes[i] = nullptr;
        sentinel.leaf = nullptr;
        sz = 0;
    }

    template<typename T,typename Alloc>
    StringMap<T,Alloc>::StringMap(const StringMap& other)
        : StringMap()
    {
        (*this) = other;
    }

    template<typename T,typename Alloc>
    StringMap<T,Alloc>::StringMap(StringMap&& other) noexcept
        : StringMap()
    {
        swap(other);
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::operator=(const StringMap& other) -> StringMap&
    {
        clear();

        std::function<void(const TreeElem*,TreeElem*)> cpy = [&](const TreeElem* src, TreeElem* dst) -> void
        {
            if( src->leaf )
            {
                make_val( dst, *src->leaf );
                ++sz;
            } else {
                dst->leaf = nullptr;
            }
            for( auto i : knodes )
            {
                if( src->nodes[i] )
                {
                    dst->nodes[i] = make_node(false);
                    dst->nodes[i]->nodes[0] = dst;
                    cpy( src->nodes[i], dst->nodes[i] );
                } else {
                    dst->nodes[i] = nullptr;
                }
            }
        };

        cpy( &other.sentinel, &sentinel );
        return *this;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::operator=(StringMap&& other) noexcept -> StringMap&
    {
        swap(other);
        return *this;
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::swap(StringMap& other) noexcept
    {
        using std::swap;
        swap( sentinel.leaf, other.sentinel.leaf );
        for( auto i : knodes )
        {
            swap( sentinel.nodes[i], other.sentinel.nodes[i] );
            if( sentinel.nodes[i] )
                sentinel.nodes[i]->nodes[0] = &sentinel;
            if( other.sentinel.nodes[i] )
                other.sentinel.nodes[i]->nodes[0] = &other.sentinel;
        }
        swap( val_alloc, other.val_alloc );
        swap( node_alloc, other.node_alloc );
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::swap(StringMap&& other) noexcept
    {
        swap(other);
    }

    template<typename T,typename Alloc>
    StringMap<T,Alloc>::~StringMap()
    {
        clear();
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::iter_core::key() const -> std::string
    {
        std::string res;
        TreeElem* p = node;
        while( true )
        {
            TreeElem* par = p->nodes[0];
            if(!par) break;
            for( auto i : knodes )
            {
                if( par->nodes[i] == p )
                {
                    res += (char) i;
                    break;
                }
            }
            p = par;
        }
        std::reverse( res.begin(), res.end() );
        return res;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::iterator::key() const -> std::string
    {
        return iter_core::key();
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::iterator::value() const -> T&
    {
        assert(this->node && this->node->leaf);
        return *this->node->leaf;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::const_iterator::key() const -> std::string
    {
        return iter_core::key();
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::const_iterator::value() const -> const T&
    {
        assert(this->node && this->node->leaf);
        return *this->node->leaf;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::TreeElem::nxt() -> TreeElem*
    {
        for( auto i : knodes )
        {
            if( nodes[i] )
                return nodes[i];
        }
        TreeElem* from = this;
        TreeElem* node = nodes[0];
        while(true)
        {
            if(!node) return nullptr;
            size_t i;
            for( i=knodes.b; i<knodes.e; ++i )
            {
                if( node->nodes[i] == from )
                    break;
            }
            if( i<256 )
            {
                for( ++i; i<knodes.e; ++i )
                {
                    if( node->nodes[i] )
                        return node->nodes[i];
                }
            }
            from = node;
            node = node->nodes[0];
        }
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::iter_core::nxt() -> void
    {
        if(node) while(true)
        {
            node = node->nxt();
            if(!node) break;
            if(node->leaf) break;
        }
    }

    template<typename T,typename Alloc>
    bool StringMap<T,Alloc>::iter_core::eq(const iter_core& other) const
    {
        return node == other.node;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::begin() -> iterator
    {
        TreeElem* p = &sentinel;
        while(true)
        {
            if(!p) break;
            if(p->leaf) break;
            p = p->nxt();
        }
        return {p};
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::end() -> iterator
    {
        return {nullptr};
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::begin() const -> const_iterator
    {
        TreeElem* p = (TreeElem*)&sentinel;
        while(true)
        {
            if(!p) break;
            if(p->leaf) break;
            p = p->nxt();
        }
        return {p};
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::end() const -> const_iterator
    {
        return {nullptr};
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::lookup(const std::string& key) const -> TreeElem*
    {
        int i,n = key.size();
        assert(n);
        const TreeElem* p = &sentinel;
        for(i=0;i<n;++i)
        {
            int c = detail::ival(key[i]);
            assert(c);
            if( p->nodes[c] )
            {
                p = p->nodes[c];
            } else {
                return nullptr;
            }
        }
        return (TreeElem*)p;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::create(const std::string& key) const -> TreeElem*
    {
        int i,n = key.size();
        assert(n);
        TreeElem* p = &sentinel;
        for(i=0;i<n;++i)
        {
            int c = detail::ival(key[i]);
            assert(c);
            if( p->nodes[c] )
            {
                p = p->nodes[c];
            } else {
                TreeElem* nn = make_node();
                nn->nodes[0] = p;
                p->nodes[c] = nn;
                p = nn;
            }
        }
        return p;
    }

    template<typename T,typename Alloc>
    T& StringMap<T,Alloc>::operator[](const std::string& key)
    {
        TreeElem* p = create(key);
        if( ! p->leaf )
        {
            make_val( p );
            ++sz;
        }
        return *p->leaf;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::at(const std::string& key) -> T&
    {
        TreeElem* p = lookup(key);
        if( p && p->leaf )
            return *p->leaf;
        else
            throw std::out_of_range("key not found");
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::at(const std::string& key) const -> const T&
    {
        TreeElem* p = lookup(key);
        if( p && p->leaf )
            return *p->leaf;
        else
            throw std::out_of_range("key not found");
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::find(const std::string& key) -> iterator
    {
        TreeElem* p = lookup(key);
        if( p && p->leaf )
            return {p};
        else
            return {nullptr};
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::find(const std::string& key) const -> const_iterator
    {
        TreeElem* p = lookup(key);
        if( p && p->leaf )
            return {p};
        else
            return {nullptr};
    }

    template<typename T,typename Alloc>
    std::size_t StringMap<T,Alloc>::count(const std::string& key) const
    {
        TreeElem* p = lookup(key);
        if( p && p->leaf )
            return 1;
        else
            return 0;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::lower_bound(const std::string& key) -> iterator
    {
        TreeElem* p = create(key);
        iterator i = {p};
        if(!p->leaf)
            ++i;
        return i;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::lower_bound(const std::string& key) const -> const_iterator
    {
        TreeElem* p = create(key);
        const_iterator i = {p};
        if(!p->leaf)
            ++i;
        return i;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::upper_bound(const std::string& key) -> iterator
    {
        TreeElem* p = create(key);
        iterator i = {p};
        ++i;
        return i;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::upper_bound(const std::string& key) const -> const_iterator
    {
        TreeElem* p = create(key);
        const_iterator i = {p};
        ++i;
        return i;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::equal_range( const std::string& key ) -> std::pair< iterator, iterator >
    {
        std::pair< iterator, iterator > result;
        TreeElem* p = create(key);
        iterator i = {p};
        if(p->leaf)
        {
            result.first  = i;
            result.second = ++i;
        } else {
            result.first  = ++i;
            result.second = i;
        }
        return result;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::equal_range( const std::string& key ) const
        -> std::pair< const_iterator, const_iterator >
    {
        std::pair< const_iterator, const_iterator > result;
        TreeElem* p = create(key);
        const_iterator i = {p};
        if(p->leaf)
        {
            result.first  = i;
            result.second = ++i;
        } else {
            result.first  = ++i;
            result.second = i;
        }
        return result;
    }


    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::insert(const std::string& key,const T& val) -> insert_result_type
    {
        TreeElem* p = create(key);
        if( p->leaf )
        {
            return make_pair( iterator{p}, false );
        } else {
            make_val( p, val );
            ++sz;
            return make_pair( iterator{p}, true );
        }
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::insert(const std::string& key,T&& val) -> insert_result_type
    {
        TreeElem* p = create(key);
        if( p->leaf )
        {
            return make_pair( iterator{p}, false );
        } else {
            make_val( p, std::move(val) );
            ++sz;
            return make_pair( iterator{p}, true );
        }
    }

    template<typename T,typename Alloc>
    template <class... Args>
    auto StringMap<T,Alloc>::emplace(const std::string& key,Args&&... args) -> insert_result_type
    {
        TreeElem* p = create(key);
        if( p->leaf )
        {
            return make_pair( iterator{p}, false );
        } else {
            make_val( p, std::forward<Args>(args)... );
            ++sz;
            return make_pair( iterator{p}, true );
        }
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::insert_or_assign(const std::string& key, const T& val) -> insert_result_type
    {
        TreeElem* p = create(key);
        if( p->leaf )
        {
            (*p->leaf) = val;
            return make_pair( iterator{p}, false );
        } else {
            make_val( p, val );
            ++sz;
            return make_pair( iterator{p}, true );
        }
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::insert_or_assign(const std::string& key, T&& val) -> insert_result_type
    {
        TreeElem* p = create(key);
        if( p->leaf )
        {
            (*p->leaf) = std::move(val);
            return make_pair( iterator{p}, false );
        } else {
            make_val( p, std::move(val) );
            ++sz;
            return make_pair( iterator{p}, true );
        }
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::erase(iterator iter) -> iterator
    {
        auto n = iter.node;
        if( n && n->leaf )
        {
            del_val( n );
            --sz;
        }
        return ++iter;
    }

    template<typename T,typename Alloc>
    bool StringMap<T,Alloc>::erase(const std::string& key)
    {
        auto i = find(key);
        if(i==end()) return false;
        erase(i);
        return true;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::erase(iterator b,iterator e) -> iterator
    {
        iterator i = b;
        while( i != e )
            i = erase(i);
        return i;
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::recursive_clear_nodes( TreeElem* p )
    {
        if(!p) return;
        if(p->leaf)
        {
            del_val(p);
        }
        for( auto i : knodes )
            recursive_clear_nodes(p->nodes[i]);
        del_node(p);
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::clear()
    {
        for( auto i : knodes )
        {
            auto& tep = sentinel.nodes[i];
            recursive_clear_nodes( tep );
            tep = nullptr;
        }
        if(sentinel.leaf)
        {
            del_val(&sentinel);
        }
        sz = 0;
    }

    template<typename T,typename Alloc>
    auto StringMap<T,Alloc>::make_node( bool clear ) const -> TreeElem*
    {
        TreeElem* tep = node_alloc.allocate(1);
        if(clear)
        {
            for( auto i : anodes )
                tep->nodes[i]=nullptr;
            tep->leaf = nullptr;
        }
        return tep;
    }

    template<typename T,typename Alloc>
    template<typename... Args>
    void StringMap<T,Alloc>::make_val( TreeElem* tep, Args&&... args )
    {
        tep->leaf = val_alloc.allocate(1);
        new (tep->leaf) T( std::forward<Args>(args)... );
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::del_val( TreeElem* tep )
    {
        if( tep->leaf )
        {
            tep->leaf->~T();
            val_alloc.deallocate(tep->leaf,1);
            tep->leaf = nullptr;
        }
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::del_node( TreeElem* tep )
    {
        node_alloc.deallocate(tep,1);
    }

    template<typename T,typename Alloc>
    void StringMap<T,Alloc>::debugprint(std::ostream& out) const
    {
        std::function<void(int,int,const TreeElem*)> rp;
        rp = [&](int ind, int c, const TreeElem* p) -> void
        {
            assert(p);
            for(int i=0;i<ind;++i)
                out << ' ';
            if(c) out << (char)c;
            if(p->leaf)
                out << " (" << *p->leaf << ")";
            out << "\n";
            for(auto i : knodes)
            {
                const TreeElem* pp = p->nodes[i];
                if(!pp) continue;
                assert( pp->nodes[0] == p );
                rp(ind+2,i,pp);
            }
        };

        rp( 0, 0, &sentinel );
    }

    namespace detail
    {

        template<typename T>
        struct has_compare_standalone
        {
            typedef char yes_type;
            typedef long no_type;

            template<typename U>
            static yes_type test( decltype( int{compare( std::declval<U>(), std::declval<U>() )} , void() )* );
            static no_type test(...);

            static const bool value = sizeof(test(0)) == sizeof(yes_type);
        };

        template<typename T>
        std::enable_if_t<has_compare_standalone<T>::value,int>
          cmp( const T& t1, const T& t2 )
        {
            return compare(t1,t2);
        }

        template<typename T>
        struct has_compare_member
        {
            typedef char yes_type;
            typedef long no_type;

            template<typename U>
            static yes_type test( decltype( int{ std::declval<const U&>().compare( std::declval<U>() )} , void() )* );
            static no_type test(...);

            static const bool value = sizeof(test(0)) == sizeof(yes_type);
        };

        template<typename T>
        std::enable_if_t<has_compare_member<T>::value && ! has_compare_standalone<T>::value,int>
          cmp( const T& t1, const T& t2 )
        {
            return t1.compare(t2);
        }

        template<typename T>
        std::enable_if_t< ! has_compare_member<T>::value && ! has_compare_standalone<T>::value,int>
          cmp( const T& t1, const T& t2 )
        {
            using std::less;
            if( less<T>()( t1, t2 ) )
                return -1;
            if( less<T>()( t2, t1 ) )
                return +1;
            return 0;
        }
    } // namespace detail

    template<typename T,typename Alloc>
    int StringMap<T,Alloc>::compare(const StringMap& other) const
    {
        auto mi = begin();
        auto oi = other.begin();
        while(true)
        {
            bool me = ( mi == end() );
            bool oe = ( oi == other.end() );
            if(me&&oe) return 0;
            if(me) return -1;
            if(oe) return +1;
            int i = detail::cmp<T>( mi->value(), oi->value() );
            if(i) return i;
            ++mi; ++oi;
        }
    }

    template<typename T,typename Alloc>
    bool operator < ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) < 0;
    }

    template<typename T,typename Alloc>
    bool operator <= ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) <= 0;
    }

    template<typename T,typename Alloc>
    bool operator == ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) == 0;
    }

    template<typename T,typename Alloc>
    bool operator > ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) > 0;
    }

    template<typename T,typename Alloc>
    bool operator >= ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) >= 0;
    }

    template<typename T,typename Alloc>
    bool operator != ( const StringMap<T,Alloc>& lhs, const StringMap<T,Alloc>& rhs )
    {
        return lhs.compare(rhs) != 0;
    }

} // namespace lib

#endif