/**
 *  @file   vecque.h
 *  @brief  内部でポインタのvectorで管理するdeque風vector.
 *  @author tenk*
 *  @note
 *  -   ポインタのvectorとして実装し、個々の要素を1つ１つアロケート.
 *  -   なので、要素間のアドレスは連続しない.
 *  -   resize等で内部のvectorでメモリー再確保がおきると、
 *      vecqueのイテレータは無効になる.
 *      が、要素のメモリ自体はそのままなので、要素へのポインタは変動しない.
 *  -   vectorで実装してるので、挿入/削除系を多様する用途には向かない.
 *      (dequeの代用にはあまりならない)
 *      が移動するのはポインタなので、実体が大きい場合は、量を扱える、とも.
 *  -   reserveできるのは、ポインタのvectorの部分のみ.
 *  -   現状、実装に気合が入っていないので、要素のallocate/deallocateは
 *      使いまわし等せず、そのつどダイレクトに行う.
 *      ※ 必要ならばアロケータ側で工夫ということに.
 *  -   Public Domain Software
 */
#ifndef VECQUE_H_INCLUDED
#define VECQUE_H_INCLUDED

#include <cstddef>
#include <iterator>
#include <algorithm>
#include <functional>
#include <new>
#include <memory>
#include <vector>
#ifndef assert
#include <cassert>
#endif
#ifndef UNUSE_THROW
#include <stdexcept>
#endif

#if defined _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4100)
#endif

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




// ============================================================================

namespace vecque_detail {

template<typename T, class A, class V >
class vecque_iterator : public std::iterator< std::random_access_iterator_tag, T > {
    typedef typename V::iterator        raw_iterator;
    typedef typename V::const_iterator  c_raw_iterator;

public:
    vecque_iterator(raw_iterator r=raw_iterator()) : ptr_(r) {}
    vecque_iterator(const vecque_iterator& r) : ptr_(r.ptr_) {}
    // ~vecque_iterator(){}

    T&       operator*()       { return **ptr_; }
    const T& operator*() const { return **ptr_; }

    T*       operator->()       { return *ptr_; }
    const T* operator->() const { return *ptr_; }

    vecque_iterator& operator=(const vecque_iterator& r) { ptr_  = r.ptr_; return *this; }
    vecque_iterator& operator+=(std::ptrdiff_t n) { ptr_ += n; return *this; }
    vecque_iterator& operator-=(std::ptrdiff_t n) { ptr_ -= n; return *this; }
    vecque_iterator& operator++() { ++ptr_; return *this; }
    vecque_iterator& operator--() { --ptr_; return *this; }
    vecque_iterator  operator++(int) { vecque_iterator p(ptr_); ++ptr_; return p; }
    vecque_iterator  operator--(int) { vecque_iterator p(ptr_); --ptr_; return p; }

    friend ptrdiff_t operator-(vecque_iterator l, vecque_iterator r) { return l.ptr_ - r.ptr_; }

    bool operator!=(const vecque_iterator& r) const { return ptr_ != r.ptr_; }
    bool operator==(const vecque_iterator& r) const { return ptr_ == r.ptr_; }
    bool operator< (const vecque_iterator& r) const { return ptr_ <  r.ptr_; }
    bool operator<=(const vecque_iterator& r) const { return ptr_ <= r.ptr_; }
    bool operator> (const vecque_iterator& r) const { return ptr_ >  r.ptr_; }
    bool operator>=(const vecque_iterator& r) const { return ptr_ >= r.ptr_; }

    raw_iterator    get_raw_ptr()       { return ptr_; }
    c_raw_iterator  get_raw_ptr() const { return ptr_; }

private:
    raw_iterator    ptr_;
};

template<typename T, class A, class V > inline
vecque_iterator<T,A,V> operator+(const vecque_iterator<T,A,V>& l, std::ptrdiff_t n) { return vecque_iterator<T,A,V>(l) += n; }

template<typename T, class A, class V > inline
vecque_iterator<T,A,V> operator-(const vecque_iterator<T,A,V>& l, std::ptrdiff_t n) { return vecque_iterator<T,A,V>(l) -= n; }

template<typename T, class A, class V > inline
vecque_iterator<T,A,V> operator+(std::ptrdiff_t n, const vecque_iterator<T,A,V>& r) { return vecque_iterator<T,A,V>(r) += n; }


struct vecque_sort_cmp_ptr_less {
    template<typename ITE>
    bool operator()(ITE l, ITE r) const {
        return *l < *r;
    }
};


}


// ============================================================================

template<typename T, class A=std::allocator<T>, class V=std::vector<T*> >
class vecque : private A {
public:
    typedef T                                           value_type;
    typedef A                                           allocator_type;
    typedef typename A::size_type                       size_type;
    typedef typename A::difference_type                 difference_type;
    typedef typename A::reference                       reference;
    typedef typename A::const_reference                 const_reference;
    typedef typename A::pointer                         pointer;
    typedef typename A::const_pointer                   const_pointer;
    typedef vecque_detail::vecque_iterator<T,A,V>       iterator;
    typedef vecque_detail::vecque_iterator<const T,A,V> const_iterator;
    typedef std::reverse_iterator<iterator>             reverse_iterator;
    typedef std::reverse_iterator<const_iterator>       const_reverse_iterator;

    vecque() { assert((T*)0 == (typename V::value_type)0); }
    ~vecque() { clear(); }

    vecque(const vecque& r);
    explicit vecque(size_type sz);
    vecque(size_type sz, const T& t);

    vecque& operator=(const vecque& x);

    void            assign(size_type n, const T &t);

    size_type       size()          const { return vec_.size();}
    size_type       max_size()      const { return vec_.max_size();}
    size_type       capacity()      const { return vec_.capacity();}
    bool            empty()         const { return vec_.empty();}

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

    reverse_iterator       rbegin()       { return reverse_iterator( end() );}
    const_reverse_iterator rbegin() const { return const_reverse_iterator( end() );}
    const_reverse_iterator crbegin()const { return const_reverse_iterator( end() );}
    reverse_iterator       rend()         { return reverse_iterator( begin() ); }
    const_reverse_iterator rend()   const { return const_reverse_iterator( begin() );}
    const_reverse_iterator crend()  const { return const_reverse_iterator( begin() );}

    reference       front()               { return *vec_.front(); }
    const_reference front()         const { return *vec_.front(); }
    reference       back()                { return *vec_.back(); }
    const_reference back()          const { return *vec_.back(); }

    reference       operator[](size_type n)       { assert(n < vec_.size()); return *vec_[n]; }
    const_reference operator[](size_type n) const { assert(n < vec_.size()); return *vec_[n]; }
    reference       at(size_type n)       { return *vec_.at(n); }
    const_reference at(size_type n) const { return *vec_.at(n); }

    void            clear();
    void            resize( size_type sz);
    void            reserve(size_type sz) { vec_.reserve(sz); }
    void            push_back(const T& t);
    void            pop_back();
    void            push_front(const T& t);
    void            pop_front();

    iterator        erase(iterator pos);
    iterator        erase(iterator first, iterator last);
    iterator        insert(iterator pos, const T& t);
    iterator        insert(iterator pos, size_type n, const T& t);

    bool operator==(const vecque& r) const;
    bool operator!=(const vecque& r) const { return !(*this == r); }
    bool operator< (const vecque& r) const;
    bool operator>=(const vecque& r) const { return !(*this < r); }
    bool operator> (const vecque& r) const { return r < *this ; }
    bool operator<=(const vecque& r) const { return ! (r < *this); }
    void            swap(vecque& r) { vec_.swap(r.vec_); }

    A&          get_allocator() { return *(A*)this; }

    void            sort();

  #ifndef VECQUE_NO_MEMBER_TEMPLATES    // メンバーテンプレートサポートの場合.
    template<typename InpIte> vecque(InpIte bgn, InpIte end);
    template<typename InpIte>  void     assign(InpIte bgn, InpIte end);
    template <typename InpIte> iterator insert(iterator pos, InpIte a, InpIte b);
    //template<class Comp>     void     sort(Comp comp);
  #else                                 // メンバーテンプレート未サポートの場合.
    vecque(iterator bgn, iterator end);
    void            assign(iterator bgn, iterator end);
    iterator        insert(iterator pos, iterator a, iterator b);
  #endif


private:
    T*              alloc1(const T& t);
    void            dealloc1(const T* t);

    typedef typename V::iterator            v_iterator;
    typedef typename V::const_iterator      v_c_iterator;
    v_iterator      ite_to_v_ite(iterator i) { return i.get_raw_ptr(); }

private:
    V               vec_;
};


// ----------------------------------------------------------------------------


template<typename T, class A, class V >
inline T* vecque<T,A,V>::alloc1(const T& t) {
    T*  a = A::allocate(1);
    if (a)
        A::construct(a, t);
  #if 0 //def UNUSE_THROW
    else
        notEnoughMemory();
  #endif
    return a;
}



template<typename T, class A, class V >
inline void vecque<T,A,V>::dealloc1(const T* t) {
    if (t) {
        A::destroy((T*)t);
        A::deallocate((T*)t, 1);
    }
}



// ----------------------------------------------------------------------------

template<typename T, class A, class V >
vecque<T,A,V>::vecque(typename vecque<T,A,V>::size_type sz)
    : vec_(sz)
{
    for (size_type i = 0; i < sz; ++i)
        vec_[i] = alloc1(T());
}



template<typename T, class A, class V >
vecque<T,A,V>::vecque(typename vecque<T,A,V>::size_type sz, const T& t)
    : vec_(sz)
{
    for (size_type i = 0; i < sz; ++i)
        vec_[i] = alloc1(t);
}



#ifndef VECQUE_NO_MEMBER_TEMPLATES  // メンバーテンプレートサポートの場合.
template<typename T, class A, class V >
template<typename InpIte>
vecque<T,A,V>::vecque(InpIte bgn, InpIte end)
#else                                   // 未サポートの場合.
template<typename T, class A, class V >
vecque<T,A,V>::vecque(typename vecque<T,A,V>::iterator bgn, typename vecque<T,A,V>::iterator end)
#endif
{
    size_type   sz  = std::distance(bgn, end);
    vec_.resize(sz);
    for (size_type i = 0; i < sz; ++i) {
        vec_[i] = alloc1(*bgn);
        ++bgn;
    }
}



template<typename T, class A, class V >
vecque<T,A,V>::vecque(const vecque<T,A,V>& r)
    : vec_(r.size())
{
    size_type   sz   = r.size();
    for (size_type i = 0; i < sz; ++i) {
        vec_[i] = alloc1(r[i]);
    }
}



// ----------------------------------------------------------------------------

template<typename T, class A, class V >
vecque<T,A,V>& vecque<T,A,V>::operator=(const vecque<T,A,V>& r)
{
    clear();
    size_type   sz   = r.size();
    resize(sz);
    for (size_type i = 0; i < sz; ++i)
        vec_[i] = alloc1( r[i] );
    return *this;
}



template<typename T, class A, class V >
void vecque<T,A,V>::assign(typename vecque<T,A,V>::size_type sz, const T& t)
{
    clear();
    resize(sz);
    for (size_type i = 0; i < sz; ++i)
        vec_[i] = alloc1(t);
}



#ifndef VECQUE_NO_MEMBER_TEMPLATES  // メンバーテンプレートサポートの場合.
template<typename T, class A, class V >
template<typename InpIte>
void vecque<T,A,V>::assign(InpIte bgn, InpIte end)
#else                                   // 未サポートの場合.
template<typename T, class A, class V >
void vecque<T,A,V>::assign(typename vecque<T,A,V>::iterator bgn, typename vecque<T,A,V>::iterator end)
#endif
{
    clear();
    size_type   sz  = std::distance(bgn, end);
    resize(sz);
    for (size_type i = 0; i < sz; ++i) {
        vec_[i] = alloc1(*bgn);
        ++bgn;
    }
}



// ----------------------------------------------------------------------------

template<typename T, class A, class V >
void vecque<T,A,V>::clear() {
    size_type   sz = vec_.size();
    for (size_type i = 0; i < sz; ++i)
        dealloc1(vec_[i]);
    vec_.clear();
}



template<typename T, class A, class V >
void vecque<T,A,V>::resize( typename vecque<T,A,V>::size_type sz )
{
    size_type   size = vec_.size();
    if (sz < size) {
        for (size_type i = sz; i < size; ++i)
            dealloc1(vec_[i]);
        vec_.resize(sz);
    } else if (sz > size) {
        vec_.resize(sz);
        for (size_type i = size; i < sz; ++i)
            vec_[i] = alloc1(T());
    }
}



template<typename T, class A, class V >
void vecque<T,A,V>::push_back( const T& t ) {
    T* a = alloc1(t);
    vec_.push_back( a );
}



template<typename T, class A, class V >
void vecque<T,A,V>::pop_back()
{
    if (!vec_.empty()) {
        T* a = vec_.back();
        dealloc1(a);
        vec_.pop_back();
    }
}



template<typename T, class A, class V >
void vecque<T,A,V>::push_front( const T& t ) {
    vec_.insert( vec_.begin() , NULL );
    vec_[0] = alloc1(t);
}



template<typename T, class A, class V >
void vecque<T,A,V>::pop_front()
{
    if (!vec_.empty()) {
        T* t = vec_.front();
        dealloc1(t);
        vec_.erase( vec_.begin() );
    }
}



template<typename T, class A, class V >
bool vecque<T,A,V>::operator==(const vecque<T,A,V>& rhs) const
{
    size_type lsz  = vec_.size();
    size_type rsz  = rhs.vec_.size();
    if (lsz != rsz)
        return false;
    const T**  l   = (const T**)&vec_[0];
    const T**  le  = l + lsz;
    const T**  r   = (const T**)&rhs.vec_[0];
    //const T**  re  = (const T**)&*rhs.vec_.end();
    while (l != le) {
        if (**l != **r)
            return 0;
        ++l;
        ++r;
    }
    return 1;
}



template<typename T, class A, class V >
bool vecque<T,A,V>::operator< (const vecque<T,A,V>& rhs) const
{
    v_c_iterator  l   = vec_.begin();
    v_c_iterator  le  = vec_.end();
    v_c_iterator  r   = rhs.vec_.begin();
    v_c_iterator  re  = rhs.vec_.end();
    while (l != le) {
        if (r == re)
            return 0;
        if (**l < **r)
            return 1;
        if (**r < **l)
            return 0;
        ++l;
        ++r;
    }
    return (r != re);
}



// ----------------------------------------------------------------------------

template<typename T, class A, class V >
typename vecque<T,A,V>::iterator    vecque<T,A,V>::erase(typename vecque<T,A,V>::iterator pos)
{
    dealloc1( *pos.get_raw_ptr() );
    vec_.erase( ite_to_v_ite( pos ) );
    return pos;
}



template<typename T, class A, class V >
typename vecque<T,A,V>::iterator    vecque<T,A,V>::erase(
        typename vecque<T,A,V>::iterator first,
        typename vecque<T,A,V>::iterator last)
{
    // assert(first < last && begin() <= first && last <= end());
    for (iterator it = first; it != last; ++it)
        dealloc1(*it.get_raw_ptr());
    vec_.erase( ite_to_v_ite(first), ite_to_v_ite(last) );
    return first;
}



// ----------------------------------------------------------------------------

template<typename T, class A, class V >
typename vecque<T,A,V>::iterator
vecque<T,A,V>::insert(typename vecque<T,A,V>::iterator pos, const T& t)
{
    return insert(pos, 1U, t);
}



template<typename T, class A, class V > inline
typename vecque<T,A,V>::iterator
vecque<T,A,V>::insert(
        typename vecque<T,A,V>::iterator    pos,
        typename vecque<T,A,V>::size_type   n,
        const T&                            t)
{
    if (n == 0)
        return pos;
    v_iterator      p   = pos.get_raw_ptr();
    size_type       idx = p - vec_.begin();
    vec_.insert(p, n, (T*)NULL);
    p  = vec_.begin() + idx;
    do {
        *p = alloc1(t);
        ++p;
    } while (--n);
    return iterator(p);
}



#ifndef VECQUE_NO_MEMBER_TEMPLATES  // メンバーテンプレートサポートの場合.
template<typename T, class A, class V >
template <typename InpIte>
typename vecque<T,A,V>::iterator
vecque<T,A,V>::insert(typename vecque<T,A,V>::iterator pos, InpIte first, InpIte last)
#else                                   // 未サポートの場合.
template<typename T, class A, class V >
typename vecque<T,A,V>::iterator
vecque<T,A,V>::insert(typename vecque<T,A,V>::iterator pos
                    , typename vecque<T,A,V>::iterator first
                    , typename vecque<T,A,V>::iterator last)
#endif
{
    size_type n = std::distance(first, last);
    if (n == 0)
        return pos;
    v_iterator   p   = pos.get_raw_ptr();
    size_type    idx = p - vec_.begin();
    vec_.insert(p, n, (T*)NULL);
    p                = vec_.begin();
    p += idx;
    v_iterator   e   = p;
    e += n;
    do {
        *p = alloc1(*first);
        ++p;
        ++first;
    } while (p != e);
    return iterator(p);
}



template<typename T, class A, class V >
void vecque<T,A,V>::sort() {
    std::stable_sort(vec_.begin(), vec_.end(), vecque_detail::vecque_sort_cmp_ptr_less());
}



/*
#ifndef VECQUE_NO_MEMBER_TEMPLATES  // メンバーテンプレートサポートの場合.
template<typename T, class A, class V >
template<class Comp>
void vecque<T,A,V>::sort(Comp comp) {
    std::stable_sort(begin(), end(), comp);
}
#endif
*/



#endif // VECQUE_H_INCLUDED