nw/ut/ut_MoveArray.h

/*---------------------------------------------------------------------------*
  Project:  NintendoWare
  File:     ut_MoveArray.h

  Copyright (C)2009-2010 Nintendo Co., Ltd./HAL Laboratory, Inc.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

  $Revision: 28041 $
 *---------------------------------------------------------------------------*/

#ifndef NW_UT_MOVEARRAY_H_
#define NW_UT_MOVEARRAY_H_

#include <nw/ut/ut_Config.h>

#include <nw/ut/ut_Preprocessor.h>
#include <nw/ut/ut_TypeTraits.h>
#include <nw/ut/ut_Flag.h>
#include <nw/os/os_Memory.h>

#include <iterator>
#include <algorithm>

namespace nw
{

namespace ut
{

namespace detail
{

template<typename From, typename To>
struct is_convertible
{
    static char test(To*);
    static int  test(...);
    static const bool value = sizeof( test( static_cast<From*>(NULL) ) ) == 1;
};

}

//---------------------------------------------------------------------------
//! @brief        配列の種類です。
//---------------------------------------------------------------------------
enum ArrayKind
{
    ARRAY_WRAPPER, //!< 配列をラップするだけの、サイズ変更できない種類です。
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
    ARRAY_VARIABILITY, //!< ヒープからメモリを確保し、サイズ変更できる種類です。
#endif
    ARRAY_FIXED, //!< ヒープからメモリ確保しない、サイズ変更できない種類です。

    NW_FLAG_VALUE_DECLARE(ARRAY_KIND, 30, 2)
};

//---------------------------------------------------------------------------
//! @brief        配列をラッピングして、STL の vector のように使用できるクラスです。
//!
//! 配列を安全に使用することを目的としています。
//! このクラスはムーブセマンティクスを実現するような
//! 実装になっており、コピーや代入が特殊な実装になっています。
//! 管理するリソースをコピーせず、所有権を移動します。
//!
//! 生成時に、以下の３つのいずれかの動作方式になります。
//!
//! 1. サイズを変更できない固定長配列@n
//! 2. push_back 時などに自動でサイズ拡張する可変長配列@n
//! 3. 配列を持たない無効な状態@n
//!
//! 所有権の移動元のインスタンスは、移動後に上記の 3 の状態になっています。
//! デフォルトコンストラクタで生成したインスタンスも 3 の状態になっています。
//! この状態のインスタンスを if の条件文して記述すると false が返るようになっています。
//! 1 または 2 の状態では、条件文に記述すると true が返るようになっています。
//!
//! "nw/ut/ut_Config.h"の"NW_MOVE_ARRAY_VARIABILITY_ENABLED"の定義を無効にして
//! ライブラリをビルドしなおすことで、上記 2 の機能を無効化することができます。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @sa nw::ut::ArrayKind
//---------------------------------------------------------------------------
template<typename TElement>
class MoveArray
{
    NW_STATIC_ASSERT(!IsArray<TElement>::value);

public:
#ifdef NW_MOVE_ARRAY_CACHE_LINE_ALIGNMENT_ENABLED
    static const size_t MEMORY_ALIGNMENT = os::IAllocator::CACHE_LINE_ALIGNMENT;
#endif

    typedef TElement&                                       reference; //!< 要素の参照です。
    typedef TElement                                        difference_type; //!< 要素の差です。
    typedef TElement                                        value_type; //!< 要素の型です。
    typedef TElement*                                       iterator; //!< 要素のイテレータの型です。
    typedef const TElement*                                 const_iterator; //!< 要素の const イテレータの型です。

#if defined(_MSC_VER) && _MSC_VER <= 1201
    typedef std::reverse_iterator<iterator, TElement>       reverse_iterator; //!< 要素のリバースイテレータの型です。
    typedef std::reverse_iterator<const_iterator, TElement> const_reverse_iterator; //!< 要素の const リバースイテレータの型です。
#else
    typedef std::reverse_iterator<iterator>             reverse_iterator; //!< 要素のリバースイテレータの型です。
    typedef std::reverse_iterator<const_iterator>       const_reverse_iterator; //!< 要素の const リバースイテレータの型です。
#endif

public:
    //! @brief        コンストラクタです。
    //!
    //! デフォルトコンストラクタです。
    //! サイズ０の固定長配列として動作します。
    //! このコンストラクタで作ったインスタンスを if 文等の条件に入れると false が
    //! 返ります。
    //!
    MoveArray()
    : m_Allocator(NULL),
      m_Elements(NULL),
      m_End(NULL)
    {
        SetCapacity(0);
        SetArrayKind(ARRAY_WRAPPER);
    }

    //! @brief        コンストラクタです。
    //!
    //! 渡されたメモリをデストラクタで開放してくれるコンストラクタです。
    //! kind を ARRAY_VARIABILITY にすると、サイズを自動拡張する機能が ON になります。
    //! サイズが自動拡張されるときには内部でメモリを確保します。
    //! 内部でメモリを確保するのが適切ではない場合、kind は ARRAY_WRAPPER にしてください。
    //! また、allocator を 0 にすると、デストラクタでメモリを解放しません。
    //!
    //! @param[in]    elements 要素格納用に確保されたメモリです。
    //! @param[in]    capacity キャパシティ要素数です。
    //! @param[in]    allocator アロケータです。
    //! @param[in]    kind メモリ拡張方法の種類です。
    //!
    template <typename TTElemet>
    MoveArray(
        TTElemet* elements,
        size_t capacity,
        os::IAllocator* allocator = NULL,
        ArrayKind kind = ARRAY_WRAPPER
        )
    : m_Allocator(allocator),
      m_Elements(reinterpret_cast<TElement*>(elements)),
      m_End(reinterpret_cast<TElement*>(elements))
    {
        // 引数の順番を間違いやすかったので、最初の引数に os::IAllocator 型のポインタ
        // を渡している場合は、コンパイル時にアサートになるようにしました。
        NW_STATIC_ASSERT((!detail::is_convertible<TTElemet, os::IAllocator>::value));
        SetCapacity(capacity);
        SetArrayKind(kind);
    }

    //! @brief        コンストラクタです。
    //!
    //! 指定したサイズのメモリをアロケータから確保してくれるコンストラクタです。
    //! kind を ARRAY_VARIABILITY にすると、サイズを自動拡張する機能が ON になります。
    //! サイズが自動拡張されるときには内部でメモリを確保します。
    //! 内部でメモリを確保するのが適切ではない場合、kind は ARRAY_WRAPPER にしてください。
    //!
    //! @param[in]    capacity キャパシティ要素数です。
    //! @param[in]    allocator アロケータです。
    //! @param[in]    kind メモリ拡張方法の種類です。
    //!
    MoveArray(
        size_t capacity,
        os::IAllocator* allocator,
        ArrayKind kind = ARRAY_WRAPPER
        )
    : m_Allocator(allocator)
    {
        NW_NULL_ASSERT(allocator);
        if (0 < capacity)
        {
#ifdef NW_MOVE_ARRAY_CACHE_LINE_ALIGNMENT_ENABLED
            m_Elements = static_cast<TElement*>(allocator->Alloc(sizeof(TElement) * capacity, MEMORY_ALIGNMENT));
#else
            m_Elements = static_cast<TElement*>(allocator->Alloc(sizeof(TElement) * capacity));
#endif
            NW_NULL_ASSERT(m_Elements);
        }
        else
        {
            m_Elements = NULL;
        }
        m_End = m_Elements;
        SetCapacity(capacity);
        SetArrayKind(kind);
    }

    //! @brief        コンストラクタです。
    //!
    //! メモリのサイズを自動拡張する MoveArray のコンストラクタです。
    //! サイズが自動拡張されるときには内部でメモリを確保します。
    //!
    //! @param[in]    allocator アロケータです。
    //!
    MoveArray(os::IAllocator* allocator)
    : m_Allocator(allocator),
      m_Elements(NULL),
      m_End(NULL)
    {
        NW_NULL_ASSERT(allocator);
        SetCapacity(0);
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
        SetArrayKind(ARRAY_VARIABILITY);
#endif
    }

    //! @brief        コピー元から要素を移動します。
    //!
    //! @param[in]    array コピー元の MoveArray オブジェクトです。
    //!
    MoveArray(const MoveArray& array)
    : m_Allocator(array.m_Allocator),
      m_Elements(array.m_Elements),
      m_End(array.m_End),
      m_Capacity(array.m_Capacity)
    {
        const_cast<MoveArray&>(array).release();
    }

    //! @brief デストラクタです。
    ~MoveArray()
    {
        clear();

        if (m_Allocator && m_Elements)
        {
            m_Allocator->Free(m_Elements);
        }
    }

public:
    //! @details :private
    struct SafeBoolHelper { int x; };
    typedef int SafeBoolHelper::* SafeBool; //!< @details :private

    //! @brief 有効な配列を所有する場合に true を返します。
    //!
    //! 望まない式評価を行われないような安全な真偽評価を行います。
    operator SafeBool() const
    {
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
        return (capacity() == 0 && GetArrayKind() != ARRAY_VARIABILITY)
#else
        return (capacity() == 0)
#endif
            ? 0
            : &SafeBoolHelper::x;
    }

    //! @brief 代入演算子の定義です。
    MoveArray& operator=(MoveArray rhs)
    {
        rhs.swap(*this);
        return *this;
    }

    //! @brief 配列の読み取り専用外部公開用アクセッサです。
    const TElement* Elements() const { return m_Elements; }

    //! @brief 添え字演算子の定義です。
    TElement& operator[](int index)
    {
        NW_MINMAXLT_ASSERT(index, 0, size());
        return m_Elements[index];
    }

    //! @brief 添え字演算子の定義です。
    const TElement& operator[](int index) const
    {
        NW_MINMAXLT_ASSERT(index, 0, size());
        return m_Elements[index];
    }

    //! @brief 内部の配列メモリの所有権を手放します。
    TElement* release()
    {
        NW_ASSERT(GetArrayKind() != ARRAY_FIXED);
        TElement* result = m_Elements;
        m_Elements = 0;
        m_End = 0;
        SetCapacity(0);
        return result;
    }

    //! @brief        MoveArray の管理する配列を再設定します。
    //!
    //! 渡されたメモリはデストラクタで開放されます。
    //! kind を ARRAY_VARIABILITY にすると、サイズを自動拡張する機能が ON になります。
    //! サイズが自動拡張されるときには内部でメモリを確保します。
    //! 内部でメモリを確保するのが適切ではない場合、kind は ARRAY_WRAPPER にしてください。
    //! また、allocator を 0 にすると、デストラクタでメモリを解放しません。
    //!
    //! 再設定以前に管理していたメモリはデストラクタが呼ばれ、
    //! 設定時にアロケータが渡されていればメモリの解放も行います。
    //!
    //! @param[in]    elements 要素格納用に確保されたメモリです。
    //! @param[in]    size 要素数です。
    //! @param[in]    allocator アロケータです。
    //! @param[in]    kind メモリ拡張方法の種類です。
    void Reset(
        void* elements,
        size_t size,
        os::IAllocator* allocator = NULL,
        ArrayKind kind = ARRAY_WRAPPER
    )
    {
        clear();

        if (m_Allocator && m_Elements)
        {
            m_Allocator->Free(m_Elements);
        }

        release();

        m_Allocator = allocator;
        m_Elements = static_cast<TElement*>(elements);
        m_End = static_cast<TElement*>(elements);

        SetCapacity(size);
        SetArrayKind(kind);
    }

    //! @brief 配列のサイズを取得します。
    int size() const { return m_End - m_Elements; }

    //! @brief 先頭要素へのイテレータを取得します。
    iterator begin() { return m_Elements; }

    //! @brief 先頭要素へのイテレータを取得します。
    const_iterator begin() const { return m_Elements; }

    //! @brief 最後尾要素へのイテレータを取得します。
    iterator end() { return m_End; }

    //! @brief 最後尾要素へのイテレータを取得します。
    const_iterator end() const { return m_End; }

    //! @brief 先頭要素へのリバースイテレータを取得します。
    reverse_iterator rbegin() { return reverse_iterator(end()); }

    //! @brief 先頭要素へのリバースイテレータを取得します。
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }

    //! @brief 最後尾要素へのリバースイテレータを取得します。
    reverse_iterator rend() { return reverse_iterator(begin()); }

    //! @brief 最後尾要素へのリバースイテレータを取得します。
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    //! @brief 先頭要素の参照を取得します。
    TElement& front() { return *m_Elements; }

    //! @brief 先頭要素の参照を取得します。
    const TElement& front() const { return *m_Elements; }

    //! @brief 最後尾要素の参照を取得します。
    TElement& back() { return *(m_End - 1); }

    //! @brief 最後尾要素の参照を取得します。
    const TElement& back() const { return *(m_End - 1); }

    //! @brief 要素が一つもないかのフラグを取得します。確保メモリがないという意味ではありません。
    bool empty() const { return m_Elements == m_End; }

    //! @brief 確保されているメモリの要素数を取得します。
    int capacity() const { return GetCapacity(); }

    //! @brief 配列をコピーします。
    void CopyFrom(const MoveArray<TElement>& source)
    {
        clear();

        NW_MAX_ASSERT(source.size(), GetCapacity());
        this->resize(source.size());
        std::copy(source.begin(), source.end(),
                  NW_CHECKED_ARRAY_ITERATOR(this->begin(), this->size()));
    }

    //----------------------------------------
    //! @name 配列・メモリ操作
    //@{

    bool reserve(int reserveSize);

    bool push_back(const TElement& element);

    void pop_back();

    bool assign(int size, const TElement& element);

    void swap(MoveArray<TElement>& other);

    bool resize(int number);

    template <typename TIterator>
    TIterator erase(TIterator first);

    template <typename TIterator>
    TIterator erase(TIterator first, TIterator last);

    //! @brief 全ての要素のデストラクタを呼び、要素数を０にします。確保メモリの開放はしません。
    void clear() { erase(begin()); }

    //! @brief 引数と同じ値の要素を検索し、削除します。
    bool erase_find(const TElement& element)
    {
        iterator removed = std::remove(begin(), end(), element);
        bool IsErased = removed != end();
        erase(removed);
        return IsErased;
    }

    //! @brief 条件に当てはまる要素を検索し、削除します。
    template<typename Predicate>
    bool erase_if(Predicate predicate)
    {
        iterator removed = std::remove_if(begin(), end(), predicate);
        bool IsErased = removed != end();
        erase(removed);
        return IsErased;
    }

    //! @brief        現在の要素数に合わせて予約メモリを縮めます。
    //!
    //! GetArrayKind() が ARRAY_VARIABILITY の時だけに働きます。
    //!
    void ShrinkToFit()
    {
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
        if (GetArrayKind() == ARRAY_VARIABILITY)
        {
            MoveArray clone(size(), m_Allocator, GetArrayKind());
            clone.CopyFrom(*this);
            clone.swap(*this);
        }
#endif
    }

    //! @brief メモリ確保についての種類を取得します。
    ArrayKind GetArrayKind() const
    {
        return GetFlagValue<ArrayKind>(
            m_Capacity, FLAG_ARRAY_KIND_VALUE_SHIFT, FLAG_ARRAY_KIND_VALUE_MASK);
    }

    //! @brief アロケータを取得します。
    os::IAllocator& GetAllocator() { return *m_Allocator; }

    //@}

protected:
    os::IAllocator* m_Allocator;
    TElement* m_Elements;
    TElement* m_End;

    //! @brief 配列の種類を設定します。
    void SetArrayKind(ArrayKind kind)
    {
        m_Capacity =
            SetFlagValue(m_Capacity, FLAG_ARRAY_KIND_VALUE_SHIFT, FLAG_ARRAY_KIND_VALUE_MASK, kind);
    }

    //! @brief 確保数を設定します。
    void SetCapacity(int capacity)
    {
        // HACK: コンパイラを黙らせる static_cast<> を仮挿入。
        m_Capacity = (m_Capacity & static_cast<size_t>(FLAG_ARRAY_KIND_VALUE_MASK)) | static_cast<size_t>(capacity);
    }

    //! @brief 確保数を取得します。
    int GetCapacity() const
    {
        return m_Capacity & (~FLAG_ARRAY_KIND_VALUE_MASK);
    }

private:
    // m_Capacity は直接参照しないでください。必ず SetCapacity(), GetCapacity() を使用してください。
    size_t m_Capacity;

    //! 割当て済みの領域にコンストラクタを呼び出します。
    void construct(TElement* element, const TElement& value)
    {
        new(static_cast<void*>(element)) TElement(value);
    }
    //! 割当て済みの領域にコンストラクタを呼び出します。
    void construct(TElement* element)
    {
        new(static_cast<void*>(element)) TElement();
    }
    //! 初期化済みの領域のデストラクタを呼び出します。
    void destroy(TElement* element)
    {
        NW_UNUSED_VARIABLE(element); // プリミティブ型での警告を回避するため
        element->~TElement();
    }
    //! 要素を移動するためにコンストラクタを呼び出します。
    void move_construct(iterator dest, const TElement& source)
    {
        new(static_cast<void*>(dest)) TElement(source);
    }
    //! 初期化済みの領域のデストラクタをまとめて呼び出します。
    void destroy_range(iterator first, iterator last)
    {
        if (IsClass<TElement>::value)
        {
            for (; first != last; ++first)
            {
                destroy(first);
            }
        }
    }

public:
    //----------------------------------------
    //! @name NintendoWare のコーディングルール準拠のエイリアス。
    //@{

    //! @brief 配列のサイズを取得します。
    int                     Size() const { return this->size(); }
    //! @brief 先頭要素へのイテレータを取得します。
    iterator                Begin() { return this->begin(); }
    //! @brief 先頭要素へのイテレータを取得します。
    const_iterator          Begin() const { return this->begin(); }
    //! @brief 最後尾要素へのイテレータを取得します。
    iterator                End() { return this->end(); }
    //! @brief 最後尾要素へのイテレータを取得します。
    const_iterator          End() const { return this->end(); }
    //! @brief 先頭要素へのリバースイテレータを取得します。
    reverse_iterator        RBegin() { return this->rbegin(); }
    //! @brief 先頭要素へのリバースイテレータを取得します。
    const_reverse_iterator  RBegin() const { return this->rbegin(); }
    //! @brief 最後尾要素へのリバースイテレータを取得します。
    reverse_iterator        REnd() { return this->rend(); }
    //! @brief 最後尾要素へのリバースイテレータを取得します。
    const_reverse_iterator  REnd() const { return this->rend(); }
    //! @brief 配列のサイズを取得します。
    TElement&               Front() { return this->front(); }
    //! @brief 先頭要素の参照を取得します。
    const TElement&         Front() const { return this->front(); }
    //! @brief 最後尾要素の参照を取得します。
    TElement&               Back() { return this->back(); }
    //! @brief 最後尾要素の参照を取得します。
    const TElement&         Back() const { return this->back(); }
    //! @brief 要素が一つもないかのフラグを取得します。確保メモリがないという意味ではありません。
    bool                    Empty() const { return this->empty(); }
    //! @brief 確保されているメモリの要素数を取得します。
    int                     Capacity() const { return this->capacity(); }
    //! @brief 指定要素数分のメモリを予約します。
    bool                    Reserve(int reserveSize) { return this->reserve( reserveSize ); }
    //! @brief 末尾に要素を追加します。
    bool                    PushBack(const TElement& element) { return this->push_back( element ); }
    //! @brief 末尾の要素を破棄します。
    void                    PopBack() { this->pop_back(); }
    //! @brief 指定数の要素を引数 element で埋めます。
    bool                    Assign(int size, const TElement& element) { return this->assign(size, element); }
    //! @brief 配列の内容を入れ替えます。
    void                    Swap(MoveArray<TElement>& other) { this->swap(other); }
    //! @brief サイズを変更します。
    bool                    Resize(int number) { return this->resize( number ); }
    //! @brief 指定したイテレータ以降の要素を削除します。
    template <typename TIterator> TIterator Erase(TIterator first) { return this->erase( first ); }
    //! @brief 指定したイテレータ間の要素を削除します。
    template <typename TIterator> TIterator Erase(TIterator first, TIterator last) { return this->erase( first, last ); }
    //! @brief 全ての要素のデストラクタを呼び、要素数を０にします。確保メモリの開放はしません。
    void                    Clear() { this->clear(); }
    //! @brief 引数と同じ値の要素を検索し、削除します。
    void                    EraseFind(const TElement& element) { this->erase_find( element ); }
    //! @brief 条件に当てはまる要素を検索し、削除します。
    template<typename Predicate>  void EraseIf(Predicate predicate) { this->erase_if( predicate ); }

    //@}

    //----------------------------------------
    //! @name 最適化用
    //@{

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    template<typename TArg0>
    void PushBackFast(TArg0 arg0)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1>
    void PushBackFast(TArg0 arg0, TArg1 arg1)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    //! @param[in] arg5 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4, typename TArg5>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4, arg5);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    //! @param[in] arg5 配列要素のコンストラクタの引数です。
    //! @param[in] arg6 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4, typename TArg5, typename TArg6>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5, TArg6 arg6)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4, arg5, arg6);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    //! @param[in] arg5 配列要素のコンストラクタの引数です。
    //! @param[in] arg6 配列要素のコンストラクタの引数です。
    //! @param[in] arg7 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4, typename TArg5, typename TArg6, typename TArg7>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5, TArg6 arg6, TArg7 arg7)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4, arg5, arg6, arg7);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    //! @param[in] arg5 配列要素のコンストラクタの引数です。
    //! @param[in] arg6 配列要素のコンストラクタの引数です。
    //! @param[in] arg7 配列要素のコンストラクタの引数です。
    //! @param[in] arg8 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4, typename TArg5, typename TArg6, typename TArg7, typename TArg8>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5, TArg6 arg6, TArg7 arg7, TArg8 arg8)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8);
    }

    //! @brief 高速版の push_back です。
    //!
    //! 範囲チェックは Assert のみ、キャパシティの自動拡張機能は働きません。
    //! 初期化時など、明示的に reserve して配列要素を生成したいケースなどに利用してください。
    //!
    //! @param[in] arg0 配列要素のコンストラクタの引数です。
    //! @param[in] arg1 配列要素のコンストラクタの引数です。
    //! @param[in] arg2 配列要素のコンストラクタの引数です。
    //! @param[in] arg3 配列要素のコンストラクタの引数です。
    //! @param[in] arg4 配列要素のコンストラクタの引数です。
    //! @param[in] arg5 配列要素のコンストラクタの引数です。
    //! @param[in] arg6 配列要素のコンストラクタの引数です。
    //! @param[in] arg7 配列要素のコンストラクタの引数です。
    //! @param[in] arg8 配列要素のコンストラクタの引数です。
    //! @param[in] arg9 配列要素のコンストラクタの引数です。
    template<typename TArg0, typename TArg1, typename TArg2, typename TArg3, typename TArg4, typename TArg5, typename TArg6, typename TArg7, typename TArg8, typename TArg9>
    void PushBackFast(TArg0 arg0, TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5, TArg6 arg6, TArg7 arg7, TArg8 arg8, TArg9 arg9)
    {
        NW_MAX_ASSERT(size(), GetCapacity());
        new(m_End++) TElement(arg0, arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9);
    }

    //@}

};

//---------------------------------------------------------------------------
//! @brief        固定長の配列クラスです。内部でヒープメモリの確保は行いません。
//!
//! @tparam       TElement 配列要素の型です。
//! @tparam       TSize 配列の要素数です。
//---------------------------------------------------------------------------
template<typename TElement, size_t TSize>
class FixedSizeArray : public MoveArray<TElement>
{
private:
    NW_DISALLOW_COPY_AND_ASSIGN(FixedSizeArray);
    NW_STATIC_ASSERT(0 < TSize);
public:
    //! コンストラクタです。
    FixedSizeArray()
    : MoveArray<TElement>(reinterpret_cast<TElement*>(m_FixedSizeElements), TSize, 0, ARRAY_FIXED) {}

private:
    void swap(MoveArray<TElement>& array);
    TElement* release();

    u8 m_FixedSizeElements[sizeof(TElement) * TSize] NN_ATTRIBUTE_ALIGN(32);
};

//---------------------------------------------------------------------------
//! @brief        指定要素数分のメモリを予約します。
//!               GetArrayKind() が ARRAY_VARIABILITY の時だけに働きます。
//!               要求されたサイズを予約できない場合、返り値に false を返します。
//!               reserve で予約メモリを縮めることはできません。
//!               その場合、shrink_to_fit を利用してください。
//!
//! @tparam       TElement 要素の型です。
//!
//! @param[in]    reserveSize 予約領域の容量(キャパシティ)です。
//!
//! @return       予約領域を拡張できなかった場合に false が返ります。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
MoveArray<TElement>::reserve(int reserveSize)
{
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
    if (reserveSize <= capacity())
    {
        return true;
    }

    if (m_Allocator == 0 || GetArrayKind() != ARRAY_VARIABILITY)
    {
        return false;
    }

#ifdef NW_MOVE_ARRAY_CACHE_LINE_ALIGNMENT_ENABLED
    TElement* elements =
        static_cast<TElement*>(m_Allocator->Alloc(sizeof(TElement) * reserveSize, MEMORY_ALIGNMENT));
#else
    TElement* elements =
        static_cast<TElement*>(m_Allocator->Alloc(sizeof(TElement) * reserveSize));
#endif
    NW_ASSERT(0 != elements);

    size_t elementsCount = 0;
    if (!empty())
    {
        std::copy(begin(), end(), NW_CHECKED_ARRAY_ITERATOR(elements, reserveSize));
        elementsCount = size();
    }

    if (0 != m_Elements)
    {
        NW_ASSERT(0 != m_Allocator);
        m_Allocator->Free(m_Elements);
    }

    m_Elements = elements;
    m_End = elements + elementsCount;
    SetCapacity(reserveSize);

    return true;
#else
    if (reserveSize <= capacity())
    {
        return true;
    }
    NW_FATAL_ERROR("Can't increase capacity.");
    return false;
#endif
}

//---------------------------------------------------------------------------
//! @brief        末尾に要素を追加します。
//!               要素が追加できなかった場合、返り値に false を返します。
//!
//! @tparam       TElement 要素の型です。
//!
//! @param[in]    element 追加する要素への参照です。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
MoveArray<TElement>::push_back(
    const TElement& element
)
{
    bool result = true;
    int capacity = GetCapacity();
    if (capacity <= size())
    {
#ifdef NW_MOVE_ARRAY_VARIABILITY_ENABLED
        int newCapacity = (capacity == 0) ? 1 : capacity * 2;
        result = reserve(newCapacity);
#else
        result = false;
#endif
    }

    if (result)
    {
        construct(m_End, element);
        ++m_End;
    }
    return result;
}

//---------------------------------------------------------------------------
//! @brief        末尾の要素を破棄します。
//!
//! @tparam       TElement 要素の型です。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE void
MoveArray<TElement>::pop_back()
{
    if (!empty())
    {
        destroy(m_End - 1);
        --m_End;
    }
}

//---------------------------------------------------------------------------
//! @brief        指定数の要素を引数 element で埋めます。
//!               全ての要素が追加できなかった場合、返り値に false を返します。
//!
//! @tparam       TElement 要素の型です。
//!
//! @param[in]    size 割り当てるサイズです。
//! @param[in]    element 要素を埋める値です。
//!
//! @return       指定通りの数分値を書き込めたら true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
MoveArray<TElement>::assign(
    int size,
    const TElement& element
)
{
    clear();
    bool result = reserve(size);
    if (!result)
    {
        size = capacity();
    }

    for (int i = 0; i < size; ++i)
    {
        push_back(element);
    }

    return result;
}

//---------------------------------------------------------------------------
//! @brief        配列の内容を入れ替えます。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    other 入れ替える対象となる配列です。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE void
MoveArray<TElement>::swap(
    MoveArray<TElement>& other
)
{
    if (&other == this)
    {
        return;
    }

    TElement* elements = m_Elements;
    TElement* end = m_End;
    size_t capacity = m_Capacity;
    os::IAllocator* allocator = m_Allocator;

    m_Elements = other.m_Elements;
    m_End = other.m_End;
    m_Capacity = other.m_Capacity;
    m_Allocator = other.m_Allocator;

    other.m_Elements = elements;
    other.m_End = end;
    other.m_Capacity = capacity;
    other.m_Allocator = allocator;
}

//---------------------------------------------------------------------------
//! @brief        サイズを変更します。
//!               指定サイズにできなかった場合、返り値に false を返します。
//!
//! @tparam       TElement 要素の型です。
//!
//! @param[in]    number  格納可能な TElement の個数を指定します。
//!
//! @return       サイズが変更できた場合は true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
MoveArray<TElement>::resize(
    int number
)
{
    bool result = true;
    if (number < size())
    {
        int min = number;
        if (min < 0)
        {
            min = 0;
            result = false;
        }
        if (IsClass<TElement>::value)
        {
            for (int i = min; i < size(); ++i)
            {
                destroy(m_Elements + i);
            }
        }
        m_End = m_Elements + min;
    }
    else
    {
        int max = number;
        if (capacity() < max)
        {
            if (!reserve(max))
            {
                result = false;
                max = capacity();
            }
        }
        if (IsClass<TElement>::value)
        {
            for (int i = size(); i < max; ++i)
            {
                construct(m_Elements + i);
            }
        }
        m_End = m_Elements + max;
    }
    return result;
}

//---------------------------------------------------------------------------
//! @brief        指定したイテレータ以降の要素を削除します。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    first 削除を開始する要素のイテレータです。
//!
//! @return       first イテレータを返します。
//---------------------------------------------------------------------------
template<typename TElement> template <typename TIterator>
NW_INLINE TIterator
MoveArray<TElement>::erase(
    TIterator first
)
{
    destroy_range(first, end());
    m_End = first;
    return first;
}

//---------------------------------------------------------------------------
//! @brief        指定したイテレータ間の要素を削除します。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    first 削除を開始する要素のイテレータです。
//! @param[in]    last  削除を終了する要素のイテレータです。
//!
//! @return       first イテレータを返します。
//---------------------------------------------------------------------------
template<typename TElement> template <typename TIterator>
NW_INLINE TIterator
MoveArray<TElement>::erase(
    TIterator first,
    TIterator last
)
{
    TIterator dest = first;
    TIterator source = last;
    for (; dest != last && source != end(); ++dest, ++source)
    {
        destroy(dest);
        move_construct(dest, *source);
    }

    if (dest != last)
    {
        destroy_range(dest, last);
        destroy_range(last, end());
    }
    else
    {
        for (; source != end(); ++dest, ++source)
        {
            destroy(dest);
            move_construct(dest, *source);
        }
        destroy_range(dest, end());
    }

    m_End = dest;

    return first;
}

} // namespace ut
} // namespace nw

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士を比較する等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値と右辺値の内容が同じであれば true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator == (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    if (lhs.size() != rhs.size())
    {
        return false;
    }
    return std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士を比較する不等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値と右辺値の内容が同じでなければ true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator != (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    if (lhs.size() != rhs.size())
    {
        return false;
    }
    return !(lhs == rhs);
}

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士の左辺値のが小さいかを比較する不等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値が右辺値より小さい場合に true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator < (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士の左辺値のが大きいかを比較する不等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値が右辺値より大きい場合に true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator > (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    return rhs < lhs;
}

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士の左辺値のが小さいまたは等しいかを比較する不等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値が右辺値より小さいか等しい場合に true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator <= (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    return !(rhs < lhs);
}

//---------------------------------------------------------------------------
//! @brief        MoveArray 同士の左辺値のが大きいまたは等しいかを比較する不等価演算子です。
//!
//! @tparam       TElement 配列要素の型です。
//!
//! @param[in]    lhs 左辺値です。
//! @param[in]    rhs 右辺値です。
//!
//! @return       左辺値が右辺値より大きいか等しい場合に true を返します。
//---------------------------------------------------------------------------
template<typename TElement>
NW_INLINE bool
operator >= (
    const nw::ut::MoveArray<TElement>& lhs,
    const nw::ut::MoveArray<TElement>& rhs
)
{
    return !(lhs < rhs);
}

#endif // NW_UT_MOVEARRAY_H_