/**
 *  @file   ya_vector.h
 *  @brief  std::vectorの別実装.
 *  @author tenk*
 *  @date   2003-2010
 *  @note
 *  -   オーソドックスな vector.
 *  -   デバッグ時に値が見やすいよう(ポインタでなく)個数をメンバー変数にもつ.
 *      逆にend()等がポインタ計算になってしまう.
 *  -   UNUSE_THROW マクロが定義されていた場合、例外を投げず、assertで処理する.
 *  -   Public Domain Software
 */
#ifndef YA_VECTOR_H_INCLUDED
#define YA_VECTOR_H_INCLUDED

#include <cstddef>
#include <iterator>
#include <algorithm>
#include <functional>
#include <new>
#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 YA_VECTOR_NO_MEMBER_TEMPLATES       // メンバーテンプレート未サポートなら定義.
#endif



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

#ifndef YA_ALLOCATOR_INCLUDED
#define YA_ALLOCATOR_INCLUDED
template< typename T >
class ya_allocator {
public:
    typedef T               value_type;
    typedef T*              pointer;
    typedef const T*        const_pointer;
    typedef T&              reference;
    typedef const T&        const_reference;
    typedef std::size_t     size_type;
    //typedef unsigned      size_type;
    typedef std::ptrdiff_t  difference_type;
    template <class U> struct rebind { typedef class ya_allocator<U> other; };

    ya_allocator() {}
    ya_allocator(const ya_allocator&) {}
  #ifndef YA_VECTOR_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<class U> ya_allocator(const ya_allocator<U>&) {}
  #endif
    ~ya_allocator() throw() {}

    static pointer          address(reference       x) {return &x;}
    static const_pointer    address(const_reference x) {return &x;}

    static pointer allocate(size_type n)              {return (pointer)::operator new(sizeof(T)*n);}
    static pointer allocate(size_type n,const void *) {return allocate(n);}

    static void deallocate(pointer p)               {::operator delete(p);}
    static void deallocate(pointer p, size_type)    {deallocate(p);}

    static void construct(pointer p, const T& val)  {new((void*)p) T(val);}
    static void construct(pointer p)                {new((void*)p) T;}
    static void destroy(pointer p)                  {p->~T();}

    static size_type max_size() throw() {return ~0; }

  #ifndef YA_VECTOR_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<class U> bool operator ==(const ya_allocator<U>& r) const {return true;}
    template<class U> bool operator !=(const ya_allocator<U>& r) const {return !(*this == r);}
  #else                                 // メンバーテンプレート未サポートの場合.
    bool operator ==(const ya_allocator& r) const {return true;}
    bool operator !=(const ya_allocator& r) const {return !(*this == r);}
  #endif
};
#endif  // YA_ALLOCATOR_INCLUDED



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

template< typename T, class ALC = ya_allocator<T> >
class ya_vector : protected ALC {
public:
    typedef T                                       value_type;
    typedef typename ALC::size_type                 size_type;
    typedef typename ALC::difference_type           difference_type;
    typedef typename ALC::reference                 reference;
    typedef typename ALC::const_reference           const_reference;
    typedef typename ALC::pointer                   pointer;
    typedef typename ALC::const_pointer             const_pointer;
    typedef pointer                                 iterator;
    typedef const_pointer                           const_iterator;
    typedef std::reverse_iterator<iterator>         reverse_iterator;
    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
    typedef ALC                                     allocator_type;

    ya_vector() : ptr_(0), size_(0), capa_(0) {;}
    ~ya_vector() { clear(); }

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

    ya_vector&  operator=(const ya_vector& x);

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

    size_type       size()          const { return size_;}
    size_type       max_size()      const { return capa_;}
    size_type       capacity()      const { return capa_;}
    bool            empty()         const { return size_ == 0;}

    iterator        begin()               { return ptr_;}
    const_iterator  begin()         const { return ptr_;}
    const_iterator  cbegin()        const { return ptr_;}
    iterator        end()                 { return ptr_ + size_;}
    const_iterator  end()           const { return ptr_ + size_;}
    const_iterator  cend()          const { return ptr_ + size_;}

    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 *ptr_;}
    const_reference front()         const { return *ptr_;}
    reference       back()                { assert(size_ > 0); return *(end() - 1);}
    const_reference back()          const { assert(size_ > 0); return *(end() - 1);}

    reference       operator[](size_type n)       { assert(n < size_); return *(ptr_ + n); }
    const_reference operator[](size_type n) const { assert(n < size_); return *(ptr_ + n); }
    reference       at(size_type n)       { if (n >= size_) outOfRng(); return *(ptr_ + n); }
    const_reference at(size_type n) const { if (n >= size_) outOfRng(); return *(ptr_ + n); }

    void            clear();
    void            resize( size_type size);
    void            reserve(size_type size);
    void            push_back(const T& t);
    void            pop_back();

    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 ya_vector& r) const { return (size_ == r.size_) && std::equal(begin(), end(), r.begin()); }
    bool operator!=(const ya_vector& r) const { return !(*this == r); }
    bool operator< (const ya_vector& r) const; // { return std::lexicographical_compare(begin(), end(), r.begin(), r.end()); }
    bool operator>=(const ya_vector& r) const { return !(*this < r); }
    bool operator> (const ya_vector& r) const { return  r < *this ; }
    bool operator<=(const ya_vector& r) const { return ! (r < *this); }
    void            swap(ya_vector& r) { std::swap(ptr_,r.ptr_); std::swap(size_,r.size_); std::swap(capa_,r.capa_); }

    //ALC&          get_allocator() { return *dynamic_cast<ALC*>(this); }
    ALC&            get_allocator() { return *(ALC*)(this); }


  #ifndef YA_VECTOR_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<typename InpIte> ya_vector(InpIte bgn, InpIte end);
    template<typename InpIte> void      assign(InpIte bgn, InpIte end);
    template <typename InpIte> iterator insert(iterator pos, InpIte a, InpIte b);
  #else                                 // メンバーテンプレート未サポートの場合.
    ya_vector(const T* bgn, const T* end);
    void            assign(const T* bgn, const T* end);
    iterator        insert(iterator pos, const T* a, const T* b);
  #endif

private:
  #ifndef YA_VECTOR_NO_MEMBER_TEMPLATES // メンバーテンプレートサポートの場合.
    template<typename InpIte>
    void copy_construct(T* ary, InpIte bgn, InpIte end);
  #else                                 // メンバーテンプレート未サポートの場合.
    void copy_construct(T* ary, const T* bgn, const T* end);
  #endif
    void set_construct(T* a, const T& t, size_type sz);
    void destruct(T* ary, size_type n);

  #ifdef UNUSE_THROW    // 例外を使わない場合.
    void outOfRng() { assert(n < size_ && "invalid ya_vector subscript"); }
  #else                 // 例外を使う場合.
    void outOfRng() { throw std::out_of_range("invalid ya_vector subscript"); }
  #endif

private:
    T*              ptr_;
    size_type       size_;
    size_type       capa_;
};




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


template< typename T, class ALC > inline
void ya_vector<T,ALC>::set_construct(T* a, const T& t, typename ya_vector<T,ALC>::size_type sz) {
    if (sz) {
        assert(a != 0);
        T* e = a + sz;
        do {
            ALC::construct(a, t);
        } while (++a != e);
    }
}



#ifndef YA_VECTOR_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename T, class ALC >
template<typename InpIte> inline
void ya_vector<T,ALC>::copy_construct(T* d, InpIte s, InpIte e)
#else                                   // 未サポートの場合.
template< typename T, class ALC > inline
void ya_vector<T,ALC>::copy_construct(T* d, const T* s, const T* e)
#endif
{
    assert(d != 0);
    while (s != e) {
        ALC::construct(d++, *s);
        ++s;
    }
}



template< typename T, class ALC > inline
void ya_vector<T,ALC>::destruct(T* a, typename ya_vector<T,ALC>::size_type sz) {
    assert(sz > 0);
    if (sz) {
        assert(a != 0);
        T* e = a + sz;
        do {
            ALC::destroy(a);
        } while (++a != e);
    }
}



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

template< typename T, class ALC >
ya_vector<T,ALC>::ya_vector(typename ya_vector<T,ALC>::size_type sz) {
    ptr_        = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        set_construct(ptr_, T(), sz);
    }
}



template< typename T, class ALC >
ya_vector<T,ALC>::ya_vector(typename ya_vector<T,ALC>::size_type sz, const T& t) {
    ptr_        = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        set_construct(ptr_, t, sz);
    }
}



#ifndef YA_VECTOR_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename T, class ALC >
template<typename InpIte>
ya_vector<T,ALC>::ya_vector(InpIte bgn, InpIte end)
#else                                   // 未サポートの場合.
template< typename T, class ALC >
ya_vector<T,ALC>::ya_vector(const T* bgn, const T* end)
#endif
{
    size_type   sz  = std::distance(bgn, end);
    ptr_            = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_       = sz;
        capa_       = sz;
        copy_construct(ptr_, bgn, end);
    }
}



template< typename T, class ALC >
ya_vector<T,ALC>::ya_vector(const ya_vector<T,ALC>& r)
{
    size_type sz= r.size();
    ptr_        = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        copy_construct(begin(), r.begin(), r.end());
    }
}



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

template< typename T, class ALC >
ya_vector<T,ALC>& ya_vector<T,ALC>::operator=(const ya_vector<T,ALC>& r)
{
    clear();
    size_type sz= r.size();
    ptr_        = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        copy_construct(begin(), r.begin(), r.end());
    }
    return *this;
}



template< typename T, class ALC >
void ya_vector<T,ALC>::assign(typename ya_vector<T,ALC>::size_type sz, const T& t)
{
    clear();
    ptr_        = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        set_construct(begin(),t,sz);
    }
}



#ifndef YA_VECTOR_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename T, class ALC >
template<typename InpIte>
void ya_vector<T,ALC>::assign(InpIte bgn, InpIte end)
#else                                   // 未サポートの場合.
template< typename T, class ALC >
void ya_vector<T,ALC>::assign(const T* bgn, const T* end)
#endif
{
    clear();
    size_type   sz  = std::distance(bgn, end);
    ptr_            = ALC::allocate( sz );
    assert(ptr_ != 0);
    if (ptr_) {
        size_   = sz;
        capa_   = sz;
        copy_construct(begin(), bgn, end);
    }
}



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

template< typename T, class ALC > inline
void ya_vector<T,ALC>::clear() {
    if (size_ > 0) {
        destruct(begin(), size_);
        size_ = 0;
    }
}


template< typename T, class ALC >
void    ya_vector<T,ALC>::reserve(size_type sz) {
    if (sz > capa_) {
        T*  a = ALC::allocate( sz );
        assert(a != NULL);
        if (a) {
            if (ptr_) {
                std::uninitialized_copy(ptr_, ptr_+size_, a);
                ALC::deallocate( ptr_, 1 );
            }
            ptr_ = a;
        }
        capa_ = sz;
    }
}


template< typename T, class ALC >
void ya_vector<T,ALC>::resize( typename ya_vector<T,ALC>::size_type sz )
{
    size_type   size = size_;
    if (sz < size) {
        destruct(ptr_+sz, size - sz);
    } else if (sz > size) {
        if (sz > capa_) {
            reserve( sz );
        }
        set_construct(ptr_+size, T(), sz - size);
    }
    size_ = sz;
}



template< typename T, class ALC >
void ya_vector<T,ALC>::push_back( const T& t )
{
    size_type   sz = size_;
    if (sz >= capa_) {
        size_type l = sz + 1 + (sz+1) / 2;
        reserve( l );
    }
    size_ = sz + 1;
    ALC::construct(ptr_+sz, t);
}



template< typename T, class ALC >
void ya_vector<T,ALC>::pop_back()
{
    if (size_ > 0) {
        --size_;
        ALC::destroy(ptr_+size_);
    }
}



template< typename T, class ALC >
bool ya_vector<T,ALC>::operator< (const ya_vector<T,ALC>& rhs) const
{
    const T*  l   = begin();
    const T*  le  = end();
    const T*  r   = rhs.begin();
    const T*  re  = rhs.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 ALC >
typename ya_vector<T,ALC>::iterator ya_vector<T,ALC>::erase(typename ya_vector<T,ALC>::iterator pos)
{
    T*  b = ptr_;
    T*  e = b+size_;
    assert(b <= pos && pos < e);
    if (pos <  b || pos >= e)
        return e;
    --e;
    for (T* p = pos; p != e; ++p)
        *p = *(p+1);
    ALC::destroy(e);
    --size_;
    return pos;
}



template< typename T, class ALC >
typename ya_vector<T,ALC>::iterator ya_vector<T,ALC>::erase(
        typename ya_vector<T,ALC>::iterator first,
        typename ya_vector<T,ALC>::iterator last)
{
    T*  b = ptr_;
    T*  e = b+size_;
    assert(first < last && b <= first && last <= e);
    if (first >= last || first < b || last > e)
        return e;
    size_type l = last - first;
    e -= l;
    for (T* p = first; p != e; ++p)
        *p = *(p+l);
    destruct(e, l);
    size_ -= l;
    return first;
}



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

template< typename T, class ALC > inline
typename ya_vector<T,ALC>::iterator
ya_vector<T,ALC>::insert(typename ya_vector<T,ALC>::iterator pos, const T& t)
{
    return insert(pos, 1U, t);
}



template< typename T, class ALC >
typename ya_vector<T,ALC>::iterator
ya_vector<T,ALC>::insert(
        typename ya_vector<T,ALC>::iterator     pos,
        typename ya_vector<T,ALC>::size_type    n,
        const T&                                t)
{
    if (n == 0)
        return pos;

    T*  b = ptr_;
    if (size_ + n > capa_) {
        difference_type     diff = pos - b;
        reserve( size_ + n );
        b   = ptr_;
        pos = b + diff;
    }
    T*  e = b + size_;
    if (pos < b || pos > e) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (T* p = e; --p >= pos;) {
        ALC::construct(p+n, *p);
        ALC::destroy(p);
    }
    e = pos + n;
    while (pos < e)
        ALC::construct(pos++, t);
    return pos;
}



#ifndef YA_VECTOR_NO_MEMBER_TEMPLATES   // メンバーテンプレートサポートの場合.
template< typename T, class ALC >
template <typename InpIte>
typename ya_vector<T,ALC>::iterator
ya_vector<T,ALC>::insert(typename ya_vector<T,ALC>::iterator pos, InpIte first, InpIte last)
#else                                   // 未サポートの場合.
template< typename T, class ALC >
typename ya_vector<T,ALC>::iterator
ya_vector<T,ALC>::insert(typename ya_vector<T,ALC>::iterator pos, const T* first, const T* last)
#endif
{
    size_type n = std::distance(first, last);
    if (n == 0)
        return pos;
    T*  b = ptr_;
    if (size_ + n > capa_) {
        difference_type     diff = pos - b;
        reserve( size_ + n );
        b   = ptr_;
        pos = b + diff;
    }
    T*  e = b + size_;
    if (pos < b || pos > e) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (T* p = e; --p >= pos;) {
        ALC::construct(p+n, *p);
        ALC::destroy(p);
    }
    e = pos + n;
    while (pos < e) {
        ALC::construct(pos++, *first);
        ++first;
    }
    return pos;
}



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

#ifndef __WATCOMC__
namespace std {

template< typename T, class ALC > inline
void swap(ya_vector<T,ALC>& l, ya_vector<T,ALC>& r) {
    l.swap(r);
}

}
#else
template< typename T, class ALC > inline
void swap(ya_vector<T,ALC>& l, ya_vector<T,ALC>& r) {
    l.swap(r);
}
#endif



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

#if defined _MSC_VER
#pragma warning(pop)
#endif

#endif  // YA_VECTOR_H