/**
 *  @file   a_vector.h
 *  @brief  動的メモリ確保を行わず、メンバーにバッファを持つvector.
 *  @author tenk*
 *  @date   2003-2010
 *  @note
 *      - std::arrayの vector 版のようなもの.
 *      - コンストラクタ、デストラクタの都合、クラス内メモリは
 *        基本型の配列で確保.
 *      - このため、アライメント不具合を起こす可能性あり.
 *      - デバッガで不便なので、A_VECTOR_USE_DBG_PTR を定義すると
 *        buf_を指すT*型のポインタ dbgPtr_ をメンバーに加える.
 *        (a_vectorのサイズが変動しても問題ない場合用)
 *      - メンバーテンプレートがあるので、watcomとかはdmcはたぶん不可.
 *      - Public Domain Software
 */
#ifndef A_VECTOR_H
#define A_VECTOR_H

#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 0 //ndef NDEBUG // デバッガでの表示を楽にするためのポインタを付加する場合.
#define A_VECTOR_USE_DBG_PTR
#endif

#ifdef  A_VECTOR_USE_DBG_PTR    // デバッガでの表示用のポインタを追加する場合.
#define A_VECTOR_SET_DBG_PTR()      (dbgPtr_ = (T*)buf_)
#else
#define A_VECTOR_SET_DBG_PTR()
#endif


template< typename T, unsigned N >
class a_vector {
public:
    typedef T                   value_type;
    typedef std::size_t         size_type;
    typedef std::ptrdiff_t      difference_type;
    typedef T&                  reference;
    typedef const T&            const_reference;
    typedef T*                  pointer;
    typedef const T*            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;

    a_vector() : size_(0) { A_VECTOR_SET_DBG_PTR(); }
    ~a_vector() { clear(); }

    explicit a_vector(size_type sz);
    a_vector(size_type sz, const T& t);
    template<typename InpIte>   a_vector(InpIte bgn, InpIte end);
    template<unsigned N2>       a_vector(const a_vector<T,N2>& r);

    a_vector&       operator=(const a_vector& x);

    void            assign(size_type n, const T &t);
    template<typename InpIte>
    void            assign(InpIte bgn, InpIte end);

    size_type       size()          const { return size_;}
    size_type       max_size()      const { return N;}
    size_type       capacity()      const { return N;}
    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) { size; assert(size <= N); }
    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) { return insert(pos, 1U, t); }
    iterator        insert(iterator pos, size_type n, const T& t);
    template <typename InpIte>
    iterator        insert(iterator pos, InpIte a, InpIte b);

    void            swap(a_vector& x) { std::swap(x, *this); }      // 効率悪いので注意！

    bool operator==(const a_vector& r) const { return (size_ == r.size_) && std::equal(begin(), end(), r.begin()); }
    bool operator!=(const a_vector& r) const { return !(*this == r); }
    bool operator< (const a_vector& r) const { return std::lexicographical_compare(begin(), end(), r.begin(), r.end()); }
    bool operator>=(const a_vector& r) const { return !(*this <  r); }
    bool operator> (const a_vector& r) const { return   r <  *this ; }
    bool operator<=(const a_vector& r) const { return !(r <  *this); }

private:
    static void construct(T* a, const T& t) { new(reinterpret_cast<void*>(a)) T(t); }
    static void set_construct(T* a, const T& t, size_type sz);
    template<typename InpIte>
    static void copy_construct(T* ary, InpIte bgn, InpIte end);

    static void destroy(T* a) { a->~T(); }
    static void destruct(T* ary, size_type n);

    T*       ptr()       { return reinterpret_cast<T*>(buf_); }
    const T* ptr() const { return reinterpret_cast<const T*>(buf_); }

  #ifdef UNUSE_THROW
    void outOfRng() { assert(n < size_ && "invalid a_vector subscript"); }
  #else
    void outOfRng() { throw std::out_of_range("invalid a_vector subscript"); }
  #endif

private:
    typedef double  aln_t;      //typedef void* aln_t;
    aln_t           buf_[ (N * sizeof(T) + sizeof(aln_t)-1) / sizeof(aln_t) ];
    size_type       size_;
 #ifdef A_VECTOR_USE_DBG_PTR
    T*              dbgPtr_;
 #endif
};




template< typename T, unsigned N > inline
void a_vector<T,N>::set_construct(T* a, const T& t, typename a_vector<T,N>::size_type sz) {
    if (sz) {
        assert(a != 0);
        do {
            construct(a, t);
            ++a;
        } while (--sz);
    }
}


template< typename T, unsigned N >
template<typename InpIte> inline
void a_vector<T,N>::copy_construct(T* d, InpIte s, InpIte e) {
    assert(d != 0);
    while (s != e) {
        construct(d++, *s);
        ++s;
    }
}


template< typename T, unsigned N > inline
void a_vector<T,N>::destruct(T* a, typename a_vector<T,N>::size_type sz) {
    assert(sz > 0);
    if (sz) {
        assert(a != 0);
        do {
            destroy(a);
            ++a;
        } while (--sz);
    }
}




template< typename T, unsigned N >
a_vector<T,N>::a_vector(typename a_vector<T,N>::size_type sz) {
    A_VECTOR_SET_DBG_PTR();
    assert(sz <= N);
    if (sz > N)
        sz = N;
    size_ = sz;
    set_construct(ptr(), T(), sz);
}


template< typename T, unsigned N >
a_vector<T,N>::a_vector(typename a_vector<T,N>::size_type sz, const T& t) {
    A_VECTOR_SET_DBG_PTR();
    assert(sz <= N);
    if (sz > N)
        sz = N;
    size_ = sz;
    set_construct(ptr(), t, sz);
}


template< typename T, unsigned N >
template<typename InpIte>
a_vector<T,N>::a_vector(InpIte bgn, InpIte end) {
    A_VECTOR_SET_DBG_PTR();
    size_type   sz = std::distance(bgn, end);
    size_          = sz;
    assert(sz <= N);
    copy_construct(ptr(), bgn, end);
}


template< typename T, unsigned N >
template<unsigned N2>
a_vector<T,N>::a_vector(const a_vector<T,N2>& r) {
    A_VECTOR_SET_DBG_PTR();
    size_type   sz = r.size();
    size_          = sz;
    assert(sz <= N);
    if (sz > N)
        sz = N;
    copy_construct(ptr(), r.begin(), r.begin() + sz);
}




template< typename T, unsigned N >
a_vector<T,N>& a_vector<T,N>::operator=(const a_vector<T,N>& x) {
    assert(N >= x.size());
    clear();
    size_ = x.size();
    if (size_ > 0) {
        copy_construct(ptr(), x.begin(), x.end());
    }
    return *this;
}


template< typename T, unsigned N >
void a_vector<T,N>::assign(typename a_vector<T,N>::size_type n, const T& t) {
    assert(N >= n);
    clear();
    if (n > N)
        n = N;
    size_ = n;
    set_construct(ptr(),t,n);
}


template< typename T, unsigned N >
template<typename InpIte>
void a_vector<T,N>::assign(InpIte bgn, InpIte end) {
    size_type   n = std::distance(bgn, end);
    assert(N >= n);
    clear();
    if (n > N)
        n = N;
    size_ = n;
    copy_construct(ptr(),bgn,end);
}



template< typename T, unsigned N >
void a_vector<T,N>::clear() {
    if (size_ > 0) {
        destruct(ptr(), size_);
        size_ = 0;
    }
}



template< typename T, unsigned N >
void a_vector<T,N>::resize( typename a_vector<T,N>::size_type sz ) {
    if (sz > N) {
        assert(sz <= N);
        sz = N;
    }
    size_type   size = size_;
    if (sz < size) {
        destruct(ptr()+sz, size - sz);
    } else if (sz > size) {
        set_construct(ptr()+size, T(), sz - size);
    }
    size_ = sz;
}



template< typename T, unsigned N >
void a_vector<T,N>::push_back( const T& t ) {
    if (size_ < N) {
        construct(ptr()+size_, t);
        ++size_;
    } else {
        assert(size_ < N);
    }
}


template< typename T, unsigned N >
void a_vector<T,N>::pop_back() {
    if (size_ > 0) {
        --size_;
        destroy(ptr()+size_);
    } else {
        assert(size_ > 0);
    }
}




template< typename T, unsigned N >
T*  a_vector<T,N>::erase(typename a_vector<T,N>::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);
    destroy(e);
    --size_;
    return pos;
}


template< typename T, unsigned N >
T*  a_vector<T,N>::erase(
        typename a_vector<T,N>::iterator first,
        typename a_vector<T,N>::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, unsigned N >
T*  a_vector<T,N>::insert(
        typename a_vector<T,N>::iterator    pos,
        typename a_vector<T,N>::size_type   n,
        const T&                            t)
{
    if (n == 0)
        return pos;
    T*  b = ptr();
    T*  e = b + size_;
    if (pos < b || pos > e || size_+n > N) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (T* p = e; --p >= pos;) {
        construct(p+n, *p);
        destroy(p);
    }
    e = pos + n;
    while (pos < e)
        construct(pos++, t);
    return pos;
}


template< typename T, unsigned N >
template <typename InpIte>
T* a_vector<T,N>::insert(typename a_vector<T,N>::iterator pos, InpIte first, InpIte last) {
    size_type n = std::distance(first, last);
    if (n == 0)
        return pos;
    T*  b = ptr();
    T*  e = b + size_;
    if (pos < b || pos > e || size_+n > N) {
        outOfRng();
        return e;
    }
    size_ += n;
    for (T* p = e; --p >= pos;) {
        construct(p+n, *p);
        destroy(p);
    }
    e = pos + n;
    while (pos < e) {
        construct(pos++, *first);
        ++first;
    }
    return pos;
}


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

#endif  // AVECTOR_H