brick-compact

// -*- mode: C++; indent-tabs-mode: nil; c-basic-offset: 4 -*-

/*
 * (c) 2019 Petr Ročkai <code@fixp.eu>
 * (c) 2017 Jan Mrázek <email@honzamrazek.cz>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#pragma once

#include <vector>
#include <algorithm>
#include <functional>
#include <stdexcept>

#include "brick-assert"
#include "brick-order"

namespace brq
{
    struct less_map
    {
        template< typename T >
        auto operator()( const T &a, const T &b ) const -> decltype( a.first < b.first )
        {
            return a.first < b.first;
        }

        template< typename T, typename K >
        auto operator()( const T &a, const K &b ) const -> decltype( a.first < b )
        {
            return a.first < b;
        }

        template< typename T, typename K >
        auto operator()( const K &a, const T &b ) const -> decltype( a < b.first )
        {
            return a < b.first;
        }
    };

    template< typename cmp_ = std::less<> >
    struct std_sort
    {
        using cmp = cmp_;

        template< typename it >
        static void sort( it begin, it end )
        {
            std::sort( begin, end, cmp() );
        }

        template< typename It, typename K >
        static It lower_bound( It begin, It end, const K &v )
        {
            return std::lower_bound( begin, end, v, cmp() );
        }
    };

    template< typename cmp_ = std::less<> >
    struct insert_sort
    {
        using cmp = cmp_;

        template< typename It, typename K >
        static It lower_bound( It begin, It end, const K &v )
        {
            if ( begin == end )
                return begin;
            auto pivot = begin + ( end - begin ) / 2;
            if ( cmp()( *pivot, v ) )
                return lower_bound( pivot + 1, end, v );
            else
                return lower_bound( begin, pivot, v );
        }

        template< typename It >
        static void sort( It begin, It end )
        {
            int i = 1;
            while ( i < end - begin )
            {
                int j = i;
                while ( j > 0 && cmp()( begin[ j ], begin[ j - 1 ] ) )
                {
                    std::swap( begin[ j ], begin[ j - 1 ] );
                    -- j;
                }
                ++ i;
            }
        }
    };

    template< typename key_t, typename sort = std_sort<>, typename container = std::vector< key_t > >
    struct array_set : derive_eq, derive_ord
    {
        using cmp = typename sort::cmp;
        using key_type = key_t;
        using value_type = key_t;

        using size_type = typename container::size_type;
        using iterator = typename container::iterator;
        using const_iterator = typename container::const_iterator;
        using reference = value_type&;
        using const_reference = const value_type&;

        container _container;

        auto begin() { return _container.begin(); }
        auto begin() const { return _container.cbegin(); }
        auto cbegin() const { return _container.cbegin(); }
        auto end() { return _container.end(); }
        auto end() const { return _container.cend(); }
        auto cend() const { return _container.cend(); }

        auto empty() const { return _container.empty(); }
        auto size() const { return _container.size(); }

        void clear() noexcept { _container.clear(); }

        array_set() = default;
        array_set( std::initializer_list< value_type > il ) : _container( il )
        {
            sort::sort( begin(), end() );
        }

        std::pair< iterator, bool > insert( const_reference value )
        {
            auto it = find( value.first );
            if ( it != cend() )
                return { it, false };
            _container.push_back( value );
            sort::sort( begin(), end() );
            return { find( value.first ), true };
        }

        template< class... Args >
        std::pair< iterator, bool > emplace( Args&&... args )
        {
            _container.emplace_back( std::forward< Args >( args )... );
            auto it = sort::lower_bound( begin(), end() - 1, _container.back() );
            if ( it == end() - 1 || !eq( *it, _container.back() ) )
            {
                sort::sort( begin(), end() );
                return { it, true };
            }
            else
            {
                _container.pop_back();
                return { it, false };
            }
        }

        void erase( iterator pos )
        {
            using std::swap;
            swap( *pos, _container.back() );
            _container.pop_back();
        }

        template< typename K >
        auto erase( const K& key ) -> decltype( cmp()( key, *begin() ), size_type() )
        {
            auto it = find( key );
            if ( it == end() )
                return 0;
            erase( it );
            return 1;
        }

        void swap( array_set &other )
        {
            using std::swap;
            swap( _container, other._container );
        }

        template< typename K >
        static bool eq( const key_t &a, const K &b )
        {
            return !cmp()( a, b ) && !cmp()( b, a );
        }

        template< typename K >
        size_type count( const K &key ) const
        {
            return find( key ) == cend() ? 0 : 1;
        }

        template< typename K >
        iterator find( const K &key )
        {
            auto elem = sort::lower_bound( begin(), end(), key );
            return elem != end() && eq( *elem, key ) ? elem : end();
        }

        template< typename K >
        const_iterator find( const K& key ) const
        {
            auto elem = sort::lower_bound( cbegin(), cend(), key );
            return elem != cend() && eq( *elem, key ) ? elem : cend();
        }

        bool operator<( const array_set &o ) const { return _container < o._container; }
        bool operator==( const array_set &o ) const { return _container == o._container; }
    };

    template< typename key_t, typename val_t, typename sort = std_sort< less_map >,
              typename container = std::vector< std::pair< key_t, val_t > > >
    struct array_map : array_set< std::pair< key_t, val_t >, sort, container >
    {
        using key_type = key_t;
        using mapped_type = val_t;
        using value_type = std::pair< key_t, val_t >;
        using reference = value_type &;
        using const_reference = const value_type &;

        val_t &operator[]( const key_t& key )
        {
            auto it = this->find( key );
            if ( it != this->end() )
                return it->second;
            return this->emplace( key, val_t() ).first->second;
        }

        template< typename K >
        val_t &at( const K& key )
        {
            auto it = this->find( key );
            if ( it == this->end() )
                throw std::out_of_range( "ArrayMap::at" );
            return it->second;
        }

        template< typename K >
        const val_t &at( const K& key ) const
        {
            auto it = this->find( key );
            if ( it == this->cend() )
                throw std::out_of_range( "ArrayMap::at" );
            return it->second;
        }
    };

    template< typename key_t, typename val_t, typename container = std::vector< val_t > >
    struct dense_map : derive_eq, derive_ord
    {
        using key_type = key_t;
        using mapped_type = val_t;
        using value_type = std::pair< key_t, val_t >;

        using size_type = typename container::size_type;
        using reference = std::pair< key_t, val_t & >;
        using const_reference = std::pair< key_t, const val_t & >;
        using base_iterator = typename container::iterator;
        using base_const_iterator = typename container::const_iterator;

        container _container;

        template< typename ref_t >
        struct proxy
        {
            ref_t ref;
            ref_t *operator->() { return &ref; }
            proxy( key_t i, typename ref_t::second_type v ) : ref( i, v ) {}
        };

        template< typename base, typename ref >
        struct iterator_t : derive_eq, derive_ord
        {
            base _iter;
            key_t _index;
            iterator_t( key_t idx, base it ) : _iter( it ), _index( idx ) {}

            ref operator*() { return { _index, *_iter }; }
            proxy< ref > operator->() { return { _index, *_iter }; }
            bool operator<( iterator_t o ) const { return _iter < o._iter; }
            bool operator==( iterator_t o ) const { return _iter == o._iter; }
            iterator_t operator+( key_t k ) const { return iterator_t( _index + k, _iter + k ); }
            iterator_t &operator++() { ++_iter; ++_index; return *this; }
            iterator_t operator++(int) { auto rv = *this; ++*this; return rv; }
        };

        using const_iterator = iterator_t< typename container::const_iterator, const_reference >;
        using iterator       = iterator_t< typename container::iterator, reference >;

        auto begin() { return iterator( 0, _container.begin() ); }
        auto begin() const { return cbegin(); }
        auto cbegin() const { return const_iterator( 0, _container.cbegin() ); }
        auto end() { return iterator( size(), _container.end() ); }
        auto end() const { return cend(); }
        auto cend() const { return const_iterator( size(), _container.cend() ); }

        auto empty() const { return _container.empty(); }
        auto size() const { return _container.size(); }

        void clear() noexcept { _container.clear(); }

        bool _bump( key_t k )
        {
            if ( size_t( k ) < _container.size() )
                return false;
            else
                return _container.resize( k + 1 ), true;
        }

        dense_map() = default;

        val_t &operator[]( key_t k ) { _bump( k ); return _container[ k ]; }

        std::pair< iterator, bool > insert( const_reference value )
        {
            key_t idx = value.first;
            bool is_new = _bump( value.first );
            if ( is_new || _container[ idx ] == val_t() )
                _container[ idx ] = value.second;
            return { iterator( idx, _container.begin() + idx ), is_new };
        }

        std::pair< iterator, bool > emplace( key_t idx, val_t val )
        {
            return insert( std::make_pair( idx, val ) );
        }

        void erase( iterator pos ) { pos->second = val_t(); }
        void erase( key_t key ) { _container[ key ] = val_t(); }

        size_type count( key_t key ) const
        {
            return size_t( key ) < size() && _container[ key ] != val_t();
        }

        iterator find( key_t k ) { return count( k ) ? begin() + k : end(); }
        const_iterator find( key_t k ) const { return count( k ) ? cbegin() + k : end(); }

        bool operator<( const dense_map &o ) const { return _container < o._container; }
        bool operator==( const dense_map &o ) const { return _container == o._container; }
    };

}