tiny.h

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; eval: (progn (c-set-style "stroustrup") (c-set-offset 'innamespace 0)); -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2015, The TPIE development team
// 
// This file is part of TPIE.
// 
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
// 
// TPIE is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
// License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE.  If not, see <http://www.gnu.org/licenses/>
#ifndef __TPIE_TINY_H__
#define __TPIE_TINY_H__

#include <algorithm>
#include <stdexcept>
#include <tpie/config.h>

namespace tpie {
namespace tiny {

template <typename T, typename Comp>
void sort(T start, T end, Comp comp=Comp()) {
    for (T i = start; i != end; ++i)
        std::rotate(std::upper_bound(start, i, *i, comp), i, std::next(i));
}

template <typename T>
void sort(T start, T end) {
    for (T i = start; i != end; ++i)
        std::rotate(std::upper_bound(start, i, *i), i, std::next(i));
}

namespace bits {
class IdentityExtract {
public:
    template <typename T>
    const T & operator()(const T & x) const {return x;}
};

template <typename A, typename B>
class PairExtract {
public:
    template <typename T>
    const T & operator()(const T & x) const {return x;}
    const A & operator()(const std::pair<A, B> & x) const {return x.first;}
};

struct SingleInsertHelp {
    template <typename Inner>
    struct type {
        static const bool multi=false;
        typedef typename Inner::iterator iterator;
        typedef std::pair<iterator, bool> result;

        template <typename Comp>
        static result handle(Inner & inner, const Comp & comp) {
            iterator fend=std::prev(inner.end());
            iterator i=std::lower_bound(inner.begin(), fend, *fend, comp);
            if (i != fend && !comp(*fend, *i)) {
                inner.pop_back();
                return std::make_pair(i, false);
            }
            std::rotate(i, fend, std::next(fend));
            return std::make_pair(i, true);
        }
    };
};

struct MultiInsertHelp {
    template <typename Inner>
    struct type {
        static const bool multi=true;
        typedef typename Inner::iterator iterator;
        typedef iterator result;
        
        template <typename Comp>
        static result handle(Inner & inner, const Comp &) {
            iterator y=std::upper_bound(inner.begin(), inner.end()-1, inner.back());
            std::rotate(y, inner.end()-1, inner.end());
            return y;
        }
    };
};

} //namespace bits
template <typename T,
          typename Key,
          typename KeyExtract,
          typename Comp,
          typename Alloc,
          typename InsertHelp>
class set_impl {
protected:
    typedef std::vector<T, Alloc> Inner;
    typedef typename InsertHelp::template type<Inner> IH;
public:
    typedef T value_type;
    typedef Key key_type;
    typedef typename Inner::iterator iterator;
    typedef typename Inner::const_iterator const_iterator;
    typedef typename Inner::reverse_iterator reverse_iterator;
    typedef typename Inner::const_reverse_iterator const_reverse_iterator;
    typedef Comp key_compare;
    typedef Alloc allocator_type;
    typedef typename IH::result insert_result;
    
    struct value_compare {
        template <typename L, typename R>
        bool operator()(const L & l, const R & r) const {
            return comp(extract(l), extract(r));
        }
        Comp comp;
        KeyExtract extract;
        value_compare(Comp comp): comp(comp) {}
    };

    set_impl(): comp(Comp()) {}
    
    explicit set_impl(const Comp & comp, const Alloc & alloc=Alloc()): comp(comp), inner(alloc) {}

    explicit set_impl(const Alloc & alloc): inner(alloc) {}

    set_impl(const set_impl & other): comp(other.comp), inner(other.inner) {}

    set_impl(const set_impl & other, const Alloc & alloc): comp(other.comp), inner(other.inner, alloc) {}

    set_impl(set_impl && other): comp(std::move(other.comp)), inner(std::move(other.inner)) {}

    set_impl(set_impl && other, const Alloc & alloc): comp(std::move(other.comp)), inner(std::move(other.inner), alloc) {}

    template< class InputIterator >
    set_impl(InputIterator first, InputIterator last,
             const Comp& comp = Comp(),
             const Alloc& alloc = Alloc()): comp(comp), inner(alloc) {
        insert(first, last);
    }

    set_impl( std::initializer_list<value_type> init,
                    const Comp& comp = Comp(),
                    const Alloc& alloc = Alloc() ): comp(comp), inner(alloc) {
        insert(init);
    }
    
    iterator begin() noexcept {return inner.begin();}

    const_iterator begin() const noexcept {return inner.cbegin();}

    const_iterator cbegin() const noexcept {return inner.cbegin();}

    reverse_iterator rbegin() noexcept {return inner.rbegin();}

    const_reverse_iterator rbegin() const noexcept {return inner.rbegin();}

    const_reverse_iterator crbegin() const noexcept {return inner.rbegin();}

    iterator end() noexcept {return inner.end();}

    const_iterator end() const noexcept {return inner.cend();}

    const_iterator cend() const noexcept {return inner.cend();}

    reverse_iterator rend() noexcept {return inner.rend();}

    const_reverse_iterator rend() const noexcept {return inner.rend();}

    const_reverse_iterator crend() const noexcept {return inner.rend();}

    bool empty() const noexcept {return inner.empty();}

    size_t size() const noexcept {return inner.size();}

    size_t max_size() const noexcept {return inner.max_size();}

    void clear() {inner.clear(); }

    iterator erase(iterator pos) {
        std::rotate(pos, std::next(pos), inner.end());
        inner.pop_back();
        return pos;
    }

    iterator erase(iterator first, iterator last) {
        std::rotate(first, last, inner.end());
        inner.resize(size() - (last-first));
        return begin();
    }

    size_t erase(const Key & key) {
        auto x=equal_range(key);
        erase(x.first, x.second);
        return x.second - x.first;
    }

    void swap(set_impl & o) {
        std::swap(comp, o.comp);
        std::swap(inner, o.inner);
    }

    iterator find(const Key & key) noexcept {
        iterator x=lower_bound(key);
        if (x == end() || comp(key, *x)) return end();
        return x;
    }

    const_iterator find(const Key & key) const noexcept {
        const_iterator x=lower_bound(key);
        if (x == end() || comp(key, *x)) return end();
        return x;
    }

    std::pair<iterator, iterator> equal_range(const Key & key) noexcept {
        return std::equal_range(inner.begin(), inner.end(), key, comp);
    }

    std::pair<const_iterator, const_iterator> equal_range(const Key & key) const noexcept {
        return std::equal_range(inner.begin(), inner.end(), key, comp);
    }

    iterator lower_bound(const Key & key) noexcept {
        return std::lower_bound(inner.begin(), inner.end(), key, comp);
    }

    const_iterator lower_bound(const Key & key) const noexcept {
        return std::lower_bound(inner.begin(), inner.end(), key, comp);
    }

    iterator upper_bound(const Key & key) noexcept {
        return std::upper_bound(inner.begin(), inner.end(), key, comp);
    }

    const_iterator upper_bound(const Key & key) const noexcept {
        return std::upper_bound(inner.begin(), inner.end(), key, comp);
    }

    key_compare key_comp() const noexcept {
        return comp.comp;
    }

    value_compare value_comp() const noexcept {
        return comp;
    }

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

    set_impl & operator=(const set_impl& other ) {
        inner = other.inner;
        comp = other.comp;
        return *this;
    }

    set_impl & operator=(set_impl&& other ) {
        inner = std::move(other.inner);
        comp = std::move(other.comp);
        return *this;
    }

    set_impl& operator=(std::initializer_list<value_type> ilist) {
        clear();
        insert(ilist);
        return *this;
    }
    
    friend bool operator==(const set_impl & lhs, const set_impl & rhs) {
        return lhs.inner == rhs.inner;
    }

    friend bool operator!=(const set_impl & lhs, const set_impl & rhs) {
        return lhs.inner != rhs.inner;
    }

    friend bool operator<(const set_impl & lhs, const set_impl & rhs) {
        return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), lhs.comp);
    }

    friend bool operator<=(const set_impl & lhs, const set_impl & rhs) {
        return !std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
        
    }

    friend bool operator>(const set_impl & lhs, const set_impl & rhs) {
        return std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
    }

    friend bool operator>=(const set_impl & lhs, const set_impl & rhs) {
        return !std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), lhs.comp);
    }

    friend void swap(set_impl & lhs, set_impl & rhs) {lhs.swap(rhs);}

    
    size_t count(const Key k) const noexcept {
        if (IH::multi) {
            auto x=equal_range(k);
            return x.second - x.first;
        } else {
            auto x=lower_bound(k);
            if (x == end() || comp(k, *x)) return 0;
            return 1;
        }
    }

    insert_result insert(const T & t) {
        inner.push_back(t);
        return IH::handle(inner, comp);
    }

    template <typename TT>
    insert_result insert(TT && t) {
        return emplace(std::forward<TT>(t));
    }

    insert_result insert(const_iterator /*hint*/, const T & t) {
        return insert(t);
    }

    template <typename TT>
    insert_result insert(const_iterator /*hint*/, TT && t) {
        return insert(std::forward<TT>(t));
    }

    template <class InputIt>
    void insert(InputIt first, InputIt last) {
        inner.reserve(size() + last-first);
        for (InputIt i=first; i != last; ++i)
            insert(*i);
    }

    void insert(std::initializer_list<value_type> list) {
        insert(list.begin(), list.end());
    }
                
    template <class... Args>
    insert_result emplace(Args &&... args) {
        inner.emplace_back(std::forward<Args>(args)...);
        return IH::handle(inner, comp);
    }

    template <class... Args>
    insert_result emplace_hint(const_iterator /*hint*/, Args &&... args) {
        return emplace(std::forward<Args>(args)...);
    }

    void reserve(size_t new_cap) {inner.reserve(new_cap);}

    void shrink_to_fit() {inner.shrink_to_fit();}

    size_t capacity() const noexcept {return inner.capacity();}
protected:  
    value_compare comp;
    std::vector<value_type, Alloc> inner;
};

template <typename T,
          typename Comp=std::less<T>,
          typename Alloc=std::allocator<T> >
using set = set_impl<T, T, bits::IdentityExtract, Comp, Alloc, bits::SingleInsertHelp>;

template <typename T,
          typename Comp=std::less<T>,
          typename Alloc=std::allocator<T> >
using multiset = set_impl<T, T, bits::IdentityExtract, Comp, Alloc, bits::MultiInsertHelp>;

template <typename Key,
          typename T,
          typename Comp=std::less<Key>,
          typename Alloc=std::allocator<std::pair<Key, T> > >
using multimap = set_impl<std::pair<Key, T>, T, bits::PairExtract<Key, T>, Comp, Alloc, bits::MultiInsertHelp>;

template <typename Key,
          typename T,
          typename Comp=std::less<Key>,
          typename Alloc=std::allocator<std::pair<Key, T> >
          > class map: public set_impl<std::pair<Key, T>, T, bits::PairExtract<Key, T>, Comp, Alloc, bits::SingleInsertHelp> {
private:
    typedef set_impl<std::pair<Key, T>, T, bits::PairExtract<Key, T>, Comp, Alloc, bits::SingleInsertHelp> P;
public:

    map() {}
    explicit map(const Comp & comp, const Alloc & alloc = Alloc()) : P(comp, alloc) {}
    explicit map(const Alloc & alloc) : P(alloc) {}
    map(const map & other) : P(other) {}
    map(const map & other, const Alloc & alloc) : P(other, alloc) {}
    map(map && other) : P(other) {}
    map(map && other, const Alloc & alloc) : P(std::move(other), alloc) {}
    template< class InputIterator >
    map(InputIterator first, InputIterator last,
        const Comp& comp = Comp(),
        const Alloc& alloc = Alloc()) : P(first, last, comp, alloc) {}
    map(std::initializer_list<typename P::value_type> init,
        const Comp& comp = Comp(),
        const Alloc& alloc = Alloc()) : P(init, comp, alloc) {}

    //using P::P; we must explicity copy the constructors until VS supports this
        
    T & operator[](const Key & key) {
        return this->emplace(key, T()).first->second;
    }

    T & operator[](Key && key) {
        return this->emplace(std::move(key), T()).first->second;
    }

    T& at( const Key& key ) {
        typename P::iterator x=P::lower_bound(key);
        if (x == P::end() || P::comp(key, *x)) throw std::out_of_range("tiny::map::at");
        return x->second;
    }

    const T& at( const Key& key ) const {
        typename P::const_iterator x=P::lower_bound(key);
        if (x == P::end() || P::comp(key, *x)) throw std::out_of_range("tiny::map::at");
        return x->second;
    }
};

} //namespace tiny
} //namespace tpie;

#endif //__TPIE_TINY_H__