/**
 *  @file   vecmap.h
 *  @brief  vector を map に似た仕様にする.
 *  @author tenk*
 *  @note
 *  -   Public Domain Software
 */
#ifndef VECMAP_H
#define VECMAP_H

#include <vector>
#include <memory>
#include <functional>
#include <algorithm>

#if defined __WATCOMC__ //|| defined __DMC__
#define VECMAP_NO_MEMBER_TEMPLATES      // メンバーテンプレート未サポートなら定義.
#endif


template< typename K, typename T, class C=std::less<K> , class V = std::vector< std::pair< K, T > > >
class vecmap : protected V, protected C {
public:
    typedef K                                       key_type;
    typedef T                                       value_type;
    typedef std::pair<K,T>                          pair_type;
    typedef V                                       base_type;
    typedef typename base_type::size_type           size_type;
    typedef typename base_type::difference_type     difference_type;
    typedef typename base_type::reference           reference;
    typedef typename base_type::const_reference     const_reference;
    typedef typename base_type::pointer             pointer;
    typedef typename base_type::const_pointer       const_pointer;
    typedef typename base_type::iterator            iterator;
    typedef typename base_type::const_iterator      const_iterator;
    typedef std::reverse_iterator<iterator>         reverse_iterator;
    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;

    T&              operator[](const K& k)       { return find_ins(k)->second; }
    const T&        operator[](const K& k) const { return find_ins(k)->second; }

    bool            empty()    const { return base().empty(); }
    size_type       size()     const { return base().size(); }
    size_type       max_size() const { return base().max_size(); }
    size_type       capacity() const { return base().capacity(); }
    void            reserve(std::size_t sz) { base().reserve((sz+31) & ~31); }
    void            clear()        { base().clear(); }

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

    reverse_iterator       rbegin()        { return base().rbegin(); }
    const_reverse_iterator rbegin()  const { return base().rbegin(); }
    const_reverse_iterator crbegin() const { return base().rbegin(); }
    reverse_iterator       rend()          { return base().rend(); }
    const_reverse_iterator rend()    const { return base().rend(); }
    const_reverse_iterator crend()   const { return base().rend(); }

    size_type       count(const K& k) const { return const_cast<vecmap*>(this)->find(k) != const_cast<vecmap*>(this)->end(); }

    void            swap(vecmap& r) { base().swap(r.base()); }

    void            erase(iterator pos)           { base().erase(pos); }
    void            erase(iterator b, iterator e) { base().erase(b, e); }
    size_type       erase(const K& k);

    iterator        find(const K& k);
    const_iterator  find(const K& k) const { return const_cast<vecmap*>(this)->find(k); }

  #ifndef VECMAP_NO_MEMBER_TEMPLATES
    template<typename Ite> void insert(Ite b, Ite e);
  #else
    void insert(iterator b, iterator e);
  #endif
    std::pair<iterator, bool>   insert( const pair_type& v );
    iterator                    insert( iterator pos, const pair_type& v ); // { return insert(v).first; }

    typename V::allocator_type& get_allocator() { return base().get_allocator(); }

    C&               key_comp()       { return *dynamic_cast<C*>(this); }
    const C&         key_comp() const { return *dynamic_cast<const C*>(this); }
    iterator         lower_bound(const K& k) { return std::lower_bound(begin(), end(), k, key_comp()); }
    iterator         upper_bound(const K& k) { return std::upper_bound(begin(), end(), k, key_comp()); }

    bool operator==(const vecmap& r) const { return base() == r.base(); }
    bool operator!=(const vecmap& r) const { return !(*this == r); }
    bool operator< (const vecmap& r) const { return base() < r.base(); }
    bool operator<=(const vecmap& r) const { return !(r < *this); }
    bool operator> (const vecmap& r) const { return  (r < *this); }
    bool operator>=(const vecmap& r) const { return !(*this < r); }

public:
    base_type&       base()       { return *(base_type*)this; }
    const base_type& base() const { return *(base_type*)this; }

private:
    iterator         find_ins(const K& k, const T* t=0, bool* pSw=0);
};



template<typename K, typename T, class C, class V>
typename vecmap<K,T,C,V>::size_type
vecmap<K,T,C,V>::erase(const K& k) {
    iterator it = find(k);
    bool     rc = (it != end());
    if (rc)
        erase(it);
    return size_type(rc);
}


template<typename K, typename T, class C, class V>
typename vecmap<K,T,C,V>::iterator
vecmap<K,T,C,V>::find(const K& k) {
    typedef char     check_pair_type_cc[ (pair_type*)0 == (typename V::value_type*)0 ? 1: -1 ];
    enum             { check_pair_type = sizeof(check_pair_type_cc) };
    size_type   mid = 0;
    size_type   hi  = base().size();
    if (hi == 0) {
        base().reserve(1);
    } else {
        size_type   low = 0;
        while (low < hi) {
            mid = (low + hi - 1) / 2;
            const K& mt = base()[mid].first;
            if (key_comp()(k, mt)) {
                hi = mid;
            } else if (key_comp()(mt, k)) {
                ++mid;
                low = mid;
            } else {
                return begin() + mid;
            }
        }
    }
    return end();
}


template<typename K, typename T, class C, class V>
typename vecmap<K,T,C,V>::iterator
vecmap<K,T,C,V>::find_ins(const K& k, const T* t, bool* pSw) {
    unsigned    mid = 0;
    unsigned    hi  = base().size();
    if (hi == 0) {
        base().reserve(1);
    } else {
        unsigned    low = 0;
        while (low < hi) {
            mid = (low + hi - 1) / 2;
            const K& mt = base()[mid].first;
            if (key_comp()(k, mt)) {
                hi = mid;
            } else if (key_comp()(mt, k)) {
                ++mid;
                low = mid;
            } else {
                return begin() + mid;
            }
        }
    }
    base().insert( begin()+mid, pair_type(k, t ? *t : value_type()) );
    if (pSw)
        *pSw = 1;
    return begin() + mid;
}



template<typename K, typename T, class C, class V> inline
typename vecmap<K,T,C,V>::iterator
vecmap<K,T,C,V>::insert( typename vecmap<K,T,C,V>::iterator pos, const std::pair<K,T>& v ) {
    pos;
  #if 0 //TODO: pos を利用した挿入
  #endif
    return insert(v).first;
}



template<typename K, typename T, class C, class V>
std::pair< typename vecmap<K,T,C,V>::iterator, bool >
vecmap<K,T,C,V>::insert( const std::pair<K,T>& v ) {
    bool     b = 0;
    iterator i = find_ins(v.first, &v.second, &b);
    return std::pair< iterator, bool >(i, b);
}



#ifndef VECMAP_NO_MEMBER_TEMPLATES
template<typename K, typename T, class C, class V>
template<typename Ite>
void vecmap<K,T,C,V>::insert(Ite b, Ite e)
#else
template<typename K, typename T, class C, class V>
void vecmap<K,T,C,V>::insert(iterator b, iterator e)
#endif
{
    while (b != e) {
        find_ins(b->first, &b->second);
        ++b;
    }
}


#ifdef __WATCOMC__
template<typename K, typename T, class C, class V>
void swap(vecmap<K,T,C,V>& l, vecmap<K,T,C,V>& r) { l.swap(r); }
#else
namespace std {
    template<typename K, typename T, class C, class V>
    void swap(vecmap<K,T,C,V>& l, vecmap<K,T,C,V>& r) { l.swap(r); }
}
#endif


#endif  // VECMAP_H