/*---------------------------------------------------------------------------*
  Project:  NintendoWare
  File:     ut_LinkList.h
  
  Copyright (C)2009-2011 Nintendo/HAL Laboratory, Inc.  All rights reserved.
  
  These coded instructions, statements, and computer programs contain proprietary
  information of Nintendo and/or its licensed developers and are protected by
  national and international copyright laws. 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.
  
  The content herein is highly confidential and should be handled accordingly.
  
  $Revision: $
 *---------------------------------------------------------------------------*/

#ifndef NW_UT_LINKLIST_H_
#define NW_UT_LINKLIST_H_

#include <nw/types.h>
#include <nw/assert.h>
#include <nw/ut/ut_Inlines.h>
#include <nw/ut/ut_Iterator.h>
#include <nw/ut/ut_Preprocessor.h>

namespace nw {
namespace ut {

class LinkListNode;

namespace internal {

class LinkListImpl;

} // namespace internal

//--------------------------------------------------------------------------
//! @brief    双方向リンクリストノードです。
//---------------------------------------------------------------------------
class LinkListNode
{
private:
    NW_DISALLOW_COPY_AND_ASSIGN(LinkListNode);

public:
    
    typedef LinkListNode Self;  //!< @details :private
    
    //--------------------------------------------------------------------------
    //! @brief        コンストラクタです。
    //---------------------------------------------------------------------------
    /* ctor */ explicit LinkListNode() : m_pNext(NULL), m_pPrev(NULL) {}
    
    //--------------------------------------------------------------------------
    //! @brief        次のノードを取得します。
    //! 
    //! @return       次のノードのポインタを返します。
    //---------------------------------------------------------------------------
    Self* GetNext() const { return m_pNext; }
    
    //--------------------------------------------------------------------------
    //! @brief        １つ前のノードを取得します。
    //! 
    //! @return       １つ前のノードのポインタを返します。
    //---------------------------------------------------------------------------
    Self* GetPrev() const { return m_pPrev; }
    
    //--------------------------------------------------------------------------
    //! @brief        比較演算子のオーバーロードです。
    //! 
    //! @param[in]    &r1     １つ目の比較値です。
    //! @param[in]    &r2     ２つ目の比較値です。
    //! 
    //! @return       等しい場合には true、そうでない場合には false を返します。
    //---------------------------------------------------------------------------
    friend bool operator==(const Self &r1,const Self &r2) { return &r1 == &r2; }

    //--------------------------------------------------------------------------
    //! @brief        否定の比較演算子のオーバーロードです。
    //! 
    //! @param[in]    r1     １つ目の比較値です。
    //! @param[in]    r2     ２つ目の比較値です。
    //! 
    //! @return       等しい場合には false、そうでない場合には true を返します。
    //---------------------------------------------------------------------------
    friend bool operator!=(const Self &r1,const Self &r2) { return !(r1 == r2); }
    
private:
    Self* m_pNext;
    Self* m_pPrev;
    
    friend class internal::LinkListImpl;  // m_pNext, m_pPrevを使用するため。
};

namespace internal {

    //--------------------------------------------------------------------------
    //! @brief        双方向リンクリスト実装クラス
    //---------------------------------------------------------------------------
    class LinkListImpl
    {
    private:
        NW_DISALLOW_COPY_AND_ASSIGN(LinkListImpl);

    public:

        typedef LinkListImpl        Self;
        typedef u32                 size_type;
        typedef PtrDiff             difference_type;
        
        // リンクリストノードクラス。
        typedef LinkListNode        Node;
        typedef Node                value_type;
        typedef value_type*         pointer;
        typedef const value_type*   const_pointer;
        typedef value_type&         reference;
        typedef const value_type&   const_reference;
        typedef std::bidirectional_iterator_tag iterator_category;

        //===========================================================================
        // イテレータ
        //===========================================================================
        class iterator;
        class const_iterator;

        class iterator : public internal::iterator<iterator_category, value_type>
        {
        public:
            
            typedef iterator TIt;
            typedef internal::iterator<iterator_category, value_type> TBaseIt;
            
            /* ctor */ explicit iterator() : m_pPointer(NULL) {}

            reference operator*()   const { NW_NULL_ASSERT(m_pPointer); return *m_pPointer; }
            pointer   operator->()  const { return m_pPointer; }

            TIt &operator++()   { m_pPointer = m_pPointer->GetNext(); return *this; }
            TIt operator++(int) { const TIt it(*this); (void)++*this; return it;  }
            TIt &operator--()   { m_pPointer = m_pPointer->GetPrev(); return *this; }
            TIt operator--(int) { const TIt it(*this); (void)--*this; return it;  }

            friend bool operator==(TIt it1, TIt it2) { return it1.m_pPointer == it2.m_pPointer; }
            friend bool operator!=(TIt it1, TIt it2) { return !(it1 == it2); }

        private:

            explicit iterator(pointer p) : m_pPointer(p) {}

            pointer m_pPointer;

            friend class LinkListImpl;    // コンストラクタを使用するため。
            friend class const_iterator;  // m_pPointerを使用するため。
        };
        
        //! @details :private
        typedef iterator Iterator_alias_;  // const_iterator内部で使用。
        
        class const_iterator
            : public internal::iterator<iterator_category, value_type>
        {
        public:
            
            typedef const_iterator TIt;
            typedef internal::iterator<iterator_category, value_type> TBaseIt;
            typedef const_pointer pointer;
            typedef const_reference reference;
            
            explicit const_iterator() : m_pPointer(NULL) {}
            const_iterator(Iterator_alias_ it) : m_pPointer(it.m_pPointer) {}

            reference operator*()  const { NW_NULL_ASSERT(m_pPointer); return *m_pPointer;}
            pointer   operator->() const { return m_pPointer;}

            TIt &operator++()   { m_pPointer = m_pPointer->GetNext(); return *this; }
            TIt operator++(int) { const TIt it(*this); (void)++*this; return it; }
            TIt &operator--()   { m_pPointer = m_pPointer->GetPrev(); return *this; }
            TIt operator--(int) { const TIt it(*this); (void)--*this; return it; }

            friend bool operator==(TIt it1, TIt it2) {return it1.m_pPointer == it2.m_pPointer; }
            friend bool operator!=(TIt it1, TIt it2) {return !(it1 == it2);}
            
        private:

            explicit const_iterator(pointer p) : m_pPointer(p) {}
            
            pointer m_pPointer;
            
            friend class LinkListImpl;  // コンストラクタを使用するため。
        };
        
        typedef internal::reverse_iterator<iterator>       reverse_iterator;
        typedef internal::reverse_iterator<const_iterator> const_reverse_iterator;
        
        //----------------------------------------
        //! @name コンストラクタ/デストラクタ。
        //@{

        /* ctor */ explicit LinkListImpl() { Initialize_(); }
        /* dtor */ ~LinkListImpl() { clear(); }
        
        //@}
        
        //----------------------------------------
        //! @name 状態の問い合わせ、イテレータの取得
        //@{
        
        size_type       size() const { return m_Size; }
        bool            empty() const { return m_Size == 0; }
        
        iterator         begin()       { return iterator(m_BaseNode.GetNext()); }
        const_iterator   begin() const { return const_iterator(m_BaseNode.GetNext()); }
        iterator         end()         { return iterator(&m_BaseNode); }
        const_iterator   end()   const { return const_iterator(const_cast<Node*>(&m_BaseNode)); }
        
        reverse_iterator       rbegin()       { return reverse_iterator(end()); }
        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
        reverse_iterator       rend()         { return reverse_iterator(begin()); }
        const_reverse_iterator rend()   const { return const_reverse_iterator(begin()); }
        
        reference front()
        {
            NW_ASSERT(!empty());
            return *begin();
        }
        const_reference front() const
        {
            NW_ASSERT(!empty());
            return *begin();
        }
        reference back()
        {
            NW_ASSERT(!empty());
            return *--end();
        }
        const_reference back() const
        {
            NW_ASSERT(!empty());
            return *--end();
        }
        
        //@}
        
        //----------------------------------------
        //! @name 要素の挿入/削除。
        //@{

        void push_front(pointer p) { (void)insert( begin(), p ); }
        void push_back(pointer p)  { (void)insert( end(), p ); }
        void pop_front()           { (void)erase( begin() ); }
        void pop_back()            { (void)erase( --end() ); }
        
        iterator insert(iterator it,pointer p);
        
        iterator erase(pointer p);
        iterator erase(iterator it);
        iterator erase(iterator itFirst,iterator itLast);
        
        void clear() { (void)this->erase(begin(), end()); }
        
        //@}
        
        //----------------------------------------
        //! @name 要素の順序の変更
        //@{
        
        void reverse();
        
        //@}
        
        //----------------------------------------
        //! @name 要素とノードとの変換
        //@{
        
        static iterator GetIteratorFromPointer(pointer p)
        {
            NW_NULL_ASSERT(p);
            return iterator(p);
        }
        
        static const_iterator GetIteratorFromPointer(const_pointer p)
        {
            NW_NULL_ASSERT(p);
            return const_iterator(p);
        }
        //@}
        
    protected:
        Node* GetBaseNode() { return &m_BaseNode; }
        const Node* GetBaseNode() const { return &m_BaseNode; }
    
    private:
        
        void Initialize_()
        {
            m_Size=0;
            m_BaseNode.m_pNext = &m_BaseNode;
            m_BaseNode.m_pPrev = &m_BaseNode;
        }
        
        
        size_type   m_Size;      // 現在の要素数。
        Node        m_BaseNode;  // ノードリンクリストの[先端 - 1]兼[終端]。
    };

} // namespace internal


//--------------------------------------------------------------------------
//! @brief        リンクリストクラスです。
//!
//! @tparam T        リストの要素となるクラスの型です。
//! @tparam TNOffset 要素 T の型の中での LinkListNode へのオフセットです。
//---------------------------------------------------------------------------
template < typename T, PtrDiff TNOffset >
class LinkList : private internal::LinkListImpl
{
private:

    typedef internal::LinkListImpl Base;
    
public:
    
    typedef LinkList  Self;    //!< @details :private
    using Base::Node;
    
    using Base::size_type;
    using Base::difference_type;
    
    typedef T                  value_type;      //!< @details :private
    typedef value_type*        pointer;         //!< @details :private
    typedef const value_type*  const_pointer;   //!< @details :private
    typedef value_type&        reference;       //!< @details :private
    typedef const value_type&  const_reference; //!< @details :private
    typedef std::bidirectional_iterator_tag iterator_category; //!< @details :private
    
private:
    
    typedef Base::iterator      TIt_base_;
    typedef Base::const_iterator TItC_base_;
    
public:
    
    //===========================================================================
    // イテレータ
    //===========================================================================

    class iterator;
    class const_iterator;
    
    //--------------------------------------------------------------------------
    //! @brief   リンクリストのイテレータです。
    //---------------------------------------------------------------------------
    class iterator : public internal::iterator<iterator_category, value_type>
    {
    public:
        
        typedef iterator TIt;                                               //!< @details :private
        typedef internal::iterator<iterator_category, value_type> TBaseIt;  //!< @details :private
        
        //--------------------------------------------------------------------------
        //! @brief        コンストラクタです。
        //---------------------------------------------------------------------------
        /* ctro */ explicit iterator() {}
        
        //----------------------------------------
        //! @name 演算子オーバーロード
        //@{
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの指している要素の値を取得するポインタ演算子です。
        //! 
        //! @return       要素の参照を返します。
        //---------------------------------------------------------------------------
        reference operator*()  const { pointer p = operator->(); NW_NULL_ASSERT(p); return *p;}
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの指している要素のアドレスを取得するアロー演算子です。
        //! 
        //! @return       要素のポインタを返します。
        //---------------------------------------------------------------------------
        pointer   operator->() const { return GetPointerFromNode(it_.operator->());}
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの前置のインクリメント演算子です。
        //! 
        //! @return       インクリメントされたイテレータを返します。
        //---------------------------------------------------------------------------
        TIt &operator++()   { (void)++it_; return *this; }
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの後置のインクリメント演算子です。
        //! 
        //! @return       インクリメント前のイテレータを返します。
        //---------------------------------------------------------------------------
        TIt operator++(int) { const TIt it(*this); (void)++*this; return it; }
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの前置のデクリメント演算子です。
        //! 
        //! @return       デクリメントされたイテレータを返します。
        //---------------------------------------------------------------------------
        TIt &operator--()   { (void)--it_; return *this; }
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの後置のデクリメント演算子です。
        //! 
        //! @return       デクリメント前のイテレータを返します。
        //---------------------------------------------------------------------------
        TIt operator--(int) { const TIt it(*this); (void)--*this; return it; }
        
        //--------------------------------------------------------------------------
        //! @brief        比較演算子です。
        //! 
        //! @param[in]    it1     比較対象の１つ目のイテレータです。
        //! @param[in]    it2     比較対象の２つ目のイテレータです。
        //! 
        //! @return       等しい場合には true, そうでない場合には false を返します。
        //---------------------------------------------------------------------------
        friend bool operator == (TIt it1, TIt it2) { return it1.it_== it2.it_; }
        
        //--------------------------------------------------------------------------
        //! @brief        否定の比較演算子です。
        //! 
        //! @param[in]    it1_     比較対象の１つ目のイテレータです。
        //! @param[in]    it2_     比較対象の２つ目のイテレータです。
        //! 
        //! @return       等しい場合には false, そうでない場合には true を返します。
        //---------------------------------------------------------------------------
        friend bool operator != (TIt it1_, TIt it2_) { return !(it1_ == it2_); }  // it1, it2 にすると何故かコンパイラに警告される。
        
        //@}
        
    private:
        
        /* ctor */ explicit iterator(TIt_base_ it) : it_(it) {}
        TIt_base_ it_;
        
    #ifdef NW_PLATFORM_CTR
        friend class LinkList;
    #else
        friend class Self;  // コンストラクタを使用するため。
    #endif
        friend class const_iterator;  // it_を使用するため。
    };

    typedef iterator Iterator_alias_;  // const_iterator内部で使用。
    
    //--------------------------------------------------------------------------
    //! @brief   リンクリストのコンストイテレータです。
    //---------------------------------------------------------------------------
    class const_iterator
        : public internal::iterator<iterator_category, value_type>
    {
    public:

        typedef const_iterator TIt;                                         //!< @details :private
        typedef internal::iterator<iterator_category, value_type> TBaseIt;  //!< @details :private
        typedef const_pointer pointer;                                      //!< @details :private
        typedef const_reference reference;                                  //!< @details :private

        //--------------------------------------------------------------------------
        //! @brief        コンストラクタです。
        //---------------------------------------------------------------------------
        /* ctor */ explicit const_iterator() {}

        //--------------------------------------------------------------------------
        //! @brief        コピーコンストラクタです。
        //---------------------------------------------------------------------------
        /* ctor */ const_iterator(Iterator_alias_ it) : it_(it.it_) {}

        //----------------------------------------
        //! @name 演算子オーバーロード
        //@{
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの指している要素の値を取得するポインタ演算子です。
        //! 
        //! @return       要素の参照を返します。
        //---------------------------------------------------------------------------
        reference operator*()  const { pointer p = operator->(); NW_NULL_ASSERT(p); return *p; }

        //--------------------------------------------------------------------------
        //! @brief        イテレータの指している要素のアドレスを取得するアロー演算子です。
        //! 
        //! @return       要素のポインタを返します。
        //---------------------------------------------------------------------------
        pointer   operator->() const { return GetPointerFromNode(it_.operator->());}
        
        //--------------------------------------------------------------------------
        //! @brief        イテレータの前置のインクリメント演算子です。
        //! 
        //! @return       インクリメントされたイテレータを返します。
        //---------------------------------------------------------------------------
        TIt &operator++()   { (void)++it_; return *this; }

        //--------------------------------------------------------------------------
        //! @brief        イテレータの後置のインクリメント演算子です。
        //! 
        //! @return       インクリメント前のイテレータを返します。
        //---------------------------------------------------------------------------
        TIt operator++(int) { const TIt it(*this); (void)++*this; return it; }

        //--------------------------------------------------------------------------
        //! @brief        イテレータの前置のデクリメント演算子です。
        //! 
        //! @return       デクリメントされたイテレータを返します。
        //---------------------------------------------------------------------------
        TIt &operator--()   { (void)--it_; return *this;}

        //--------------------------------------------------------------------------
        //! @brief        イテレータの後置のデクリメント演算子です。
        //! 
        //! @return       デクリメント前のイテレータを返します。
        //---------------------------------------------------------------------------
        TIt operator--(int) { const TIt it(*this); (void)--*this; return it; }
        
        //--------------------------------------------------------------------------
        //! @brief        比較演算子です。
        //! 
        //! @param[in]    it1     比較対象の１つ目のイテレータです。
        //! @param[in]    it2     比較対象の２つ目のイテレータです。
        //! 
        //! @return       等しい場合には true, そうでない場合には false を返します。
        //---------------------------------------------------------------------------
        friend bool operator == (TIt it1, TIt it2) { return it1.it_== it2.it_; }

        //--------------------------------------------------------------------------
        //! @brief        否定の比較演算子です。
        //! 
        //! @param[in]    it1_     比較対象の１つ目のイテレータです。
        //! @param[in]    it2_     比較対象の２つ目のイテレータです。
        //! 
        //! @return       等しい場合には false, そうでない場合には true を返します。
        //---------------------------------------------------------------------------
        friend bool operator != (TIt it1_, TIt it2_) { return !(it1_ == it2_); }
        
        //@}
        
    protected:
        
        /* ctor */ explicit const_iterator(TItC_base_ it) : it_(it) {}
        
        TItC_base_ it_;
        
        
    #if defined(NW_PLATFORM_CTR)
        friend class LinkList;  // コンストラクタを使用するため。
    #else
        friend class Self;  // コンストラクタを使用するため。
    #endif
    };

    typedef internal::reverse_iterator<iterator> reverse_iterator;              //!< @details :private
    typedef internal::reverse_iterator<const_iterator> const_reverse_iterator;  //!< @details :private
    
    //----------------------------------------
    //! @name コンストラクタ/デストラクタ。
    //@{
    
    //--------------------------------------------------------------------------
    //! @brief   コンストラクタです。
    //---------------------------------------------------------------------------
    /* ctor */ explicit LinkList() {}
    
    //@}
    
    //----------------------------------------
    //! @name 状態の問い合わせ、イテレータの取得
    //@{
    
    //--------------------------------------------------------------------------
    //! @fn          u32  LinkList::size()
    //! 
    //! @brief        リストのサイズを取得します。
    //! 
    //! @return       リストのサイズを返します。
    //---------------------------------------------------------------------------
    using Base::size;

    //--------------------------------------------------------------------------
    //! @fn           bool LinkList::empty()
    //! 
    //! @brief        リストが空であるかどうかを取得します。
    //! 
    //! @return       リストが空の場合には true, 要素が存在する場合には false を返します。
    //---------------------------------------------------------------------------
    using Base::empty;
    
    //--------------------------------------------------------------------------
    //! @brief        先頭の要素へのイテレータを取得します。
    //! 
    //! @return       先頭の要素へのイテレータを返します。
    //---------------------------------------------------------------------------
    iterator        begin()       { return iterator(Base::begin()); }
    const_iterator  begin() const { return const_iterator(const_cast<Self*>(this)->begin()); }
    
    //--------------------------------------------------------------------------
    //! @brief        イテレータの終端を取得します。
    //! 
    //! @return       イテレータの終端を返します。
    //---------------------------------------------------------------------------
    iterator        end()         { return iterator(Base::end()); }
    const_iterator  end()   const { return const_iterator(const_cast<Self*>(this)->end()); }
    
    //--------------------------------------------------------------------------
    //! @brief        末尾の要素へのリバースイテレータを取得します。
    //! 
    //! @return       末尾の要素へのリバースイテレータを返します。
    //---------------------------------------------------------------------------
    reverse_iterator        rbegin()       { return reverse_iterator(end()); }
    const_reverse_iterator  rbegin() const { return const_reverse_iterator(end()); }
    
    //--------------------------------------------------------------------------
    //! @brief        リバースイテレータの終端を取得します。
    //! 
    //! @return       リバースイテレータの終端を返します。
    //---------------------------------------------------------------------------
    reverse_iterator        rend()         { return reverse_iterator(begin()); }
    const_reverse_iterator  rend()   const { return const_reverse_iterator(begin()); }
    
    //--------------------------------------------------------------------------
    //! @brief        先頭の要素の参照を取得します。
    //! 
    //! @return       先頭の要素の参照を返します。
    //---------------------------------------------------------------------------
    reference       front()       { NW_ASSERT(!empty()); return *begin(); }
    const_reference front() const { NW_ASSERT(!empty()); return *begin(); }
    
    //--------------------------------------------------------------------------
    //! @brief        末尾の要素の参照を取得します。
    //! 
    //! @return       末尾の要素の参照を返します。
    //---------------------------------------------------------------------------
    reference       back()        { NW_ASSERT(!empty()); return *--end(); }
    const_reference back() const  { NW_ASSERT(!empty()); return *--end(); }
    
    //@}
    
    //----------------------------------------
    //! @name 挿入/削除
    //@{
    
    //--------------------------------------------------------------------------
    //! @brief        リストに要素を挿入します。
    //! 
    //! @param[in]    it      要素を挿入位置のイテレータです。 it の直前に要素が挿入されます。
    //! @param[in]    p       挿入する要素のポインタです。
    //! 
    //! @return       追加された要素のイテレータを返します。
    //---------------------------------------------------------------------------
    iterator insert(iterator it, pointer p) { return iterator(Base::insert(it.it_,GetNodeFromPointer(p)));}

    //--------------------------------------------------------------------------
    //! @brief        リストにの先頭に要素を追加します。
    //! 
    //! @param[in]    p       挿入する要素のポインタです。
    //---------------------------------------------------------------------------
    void     push_front(pointer p)          { (void)insert(begin(),p);}

    //--------------------------------------------------------------------------
    //! @brief        リストにの末尾に要素を追加します。
    //! 
    //! @param[in]    p       挿入する要素のポインタです。
    //---------------------------------------------------------------------------
    void     push_back(pointer p)           { (void)insert(end(),p);}
    
    using Base::pop_front;
    using Base::pop_back;
    
    //--------------------------------------------------------------------------
    //! @brief        指定されたメンバを削除します。
    //! 
    //! @param[in]    it      削除する要素のイテレータです。
    //! 
    //! @return       削除した要素の次のノードへのイテレータを返します。
    //---------------------------------------------------------------------------
    iterator erase(iterator it)                      { return iterator(Base::erase(it.it_)); }

    //--------------------------------------------------------------------------
    //! @brief        指定されたメンバを削除します。
    //! 
    //!
    //!               終了位置に指定された要素は削除されません。
    //!
    //! @param[in]    itFirst 削除開始位置を示すイテレータです。
    //! @param[in]    itLast  削除終了位置を示すイテレータです。
    //! 
    //! @return       削除した要素の次のノードへのイテレータを返します。
    //---------------------------------------------------------------------------
    iterator erase(iterator itFirst,iterator itLast) { return iterator(Base::erase(itFirst.it_, itLast.it_)); }

    //--------------------------------------------------------------------------
    //! @brief        指定されたメンバを削除します。
    //! 
    //! @param[in]    p       削除する要素のポインタです。
    //! 
    //! @return       削除した要素の次のノードへのイテレータを返します。
    //---------------------------------------------------------------------------
    iterator erase(pointer p)                        { return iterator(Base::erase(GetNodeFromPointer(p))); }
    
    //--------------------------------------------------------------------------
    //! @brief        一つ前の要素を取得します。
    //! 
    //! @param[in]    p       基点となる要素のポインタです。
    //! 
    //! @return       一つ前の要素を返します。 存在しない場合は NULL を返します。
    //---------------------------------------------------------------------------
    pointer GetPrev(pointer p) 
    {
        Node* baseNode = GetBaseNode();
        Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p );
        node = node->GetPrev();
        return ( node == baseNode )? NULL : GetPointerFromNode( node );
    }
    
    const_pointer GetPrev(const_pointer p) const 
    {
        const Node* baseNode = GetBaseNode();
        const Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p );
        node = node->GetPrev();
        return ( node == baseNode )? NULL : GetPointerFromNode( node );
    }
    
    //--------------------------------------------------------------------------
    //! @brief        一つ後の要素を取得します。
    //! 
    //! @param[in]    p       基点となる要素のポインタです。
    //! 
    //! @return       一つ後の要素を返します。 存在しない場合は NULL を返します。
    //---------------------------------------------------------------------------
    pointer GetNext(pointer p)
    {
        Node* baseNode = GetBaseNode();
        Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p );
        node = node->GetNext();
        return ( node == baseNode )? NULL : GetPointerFromNode( node );
    }
    
    const_pointer GetNext(const_pointer p) const 
    {
        const Node* baseNode = GetBaseNode();
        const Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p );
        node = node->GetNext();
        return ( node == baseNode )? NULL : GetPointerFromNode( node );
    }
    
    //--------------------------------------------------------------------------
    //! @fn           void nw::ut::LinkList::clear()
    //!
    //! @brief        リストを空にします。
    //---------------------------------------------------------------------------
    using Base::clear;
    
    //@}
    
    //----------------------------------------
    //! @name 順序の変更
    //@{

    //--------------------------------------------------------------------------
    //! @fn           void LinkList::reverse()
    //!
    //! @brief        リストの並びを反転します。
    //---------------------------------------------------------------------------
    using Base::reverse;
    
    //@}
    
    //----------------------------------------
    //! @name 要素とノードとの変換
    //@{
    
    //--------------------------------------------------------------------------
    //! @brief        ノードのポインタからイテレータを取得します。
    //! 
    //! @param[in]    p   ノードのポインタです。
    //! 
    //! @return       イテレータです。
    //---------------------------------------------------------------------------
    static iterator GetIteratorFromPointer(Node *p)
    {
        NW_NULL_ASSERT(p);
        return iterator(Base::GetIteratorFromPointer(p));
    }
    static const_iterator GetIteratorFromPointer(const Node *p)
    {
        NW_NULL_ASSERT(p);
        return const_iterator(Base::GetIteratorFromPointer(p));
    }

    //--------------------------------------------------------------------------
    //! @brief        要素のポインタからイテレータを取得します。
    //! 
    //! @param[in]    p   要素のポインタです。
    //! 
    //! @return       イテレータです。
    //---------------------------------------------------------------------------
    static iterator GetIteratorFromPointer(pointer p)
    {
        NW_NULL_ASSERT(p);
        return GetIteratorFromPointer(GetNodeFromPointer(p));
    }
    static const_iterator GetIteratorFromPointer(const_pointer p)
    {
        NW_NULL_ASSERT(p);
        return GetIteratorFromPointer(GetNodeFromPointer(p));
    }
    
    //--------------------------------------------------------------------------
    //! @brief        要素のポインタからノードのポインタを取得します。
    //! 
    //! @param[in]    p   要素のポインタです。
    //! 
    //! @return       ノードのポインタです。
    //---------------------------------------------------------------------------
    static Node* GetNodeFromPointer(pointer p)
    {
        NW_NULL_ASSERT(p);
        return reinterpret_cast<Node*>(reinterpret_cast<IntPtr>(p) + TNOffset);
    }
    static const Node* GetNodeFromPointer(const_pointer p)
    {
        NW_NULL_ASSERT(p);
        return reinterpret_cast<const Node*>(reinterpret_cast<IntPtr>(p) + TNOffset);
    }

    //--------------------------------------------------------------------------
    //! @brief        ノードのポインタから要素のポインタを取得します。
    //! 
    //! @param[in]    p   ノードのポインタです。
    //! 
    //! @return       要素のポインタです。
    //---------------------------------------------------------------------------
    static pointer GetPointerFromNode(Node* p)
    {
        NW_NULL_ASSERT(p);
        return reinterpret_cast<pointer>(reinterpret_cast<IntPtr>(p) - TNOffset);
    }
    static const_pointer GetPointerFromNode(const Node* p)
    {
        NW_NULL_ASSERT(p);
        return reinterpret_cast<const_pointer>( reinterpret_cast<IntPtr>(p) - TNOffset);
    }
    
    //@}
    
    //------------------------------------
    // NW4R 互換用のalias
    //------------------------------------
    typedef iterator                Iterator;               //!< @details :private
    typedef const_iterator          ConstIterator;          //!< @details :private
    typedef reverse_iterator        ReverseIterator;        //!< @details :private
    typedef const_reverse_iterator  ConstReverseIterator;   //!< @details :private
    
    size_type GetSize() const { return this->size(); }      //!< @details :private
    bool      IsEmpty() const { return this->empty(); }     //!< @details :private
    
    iterator        GetBeginIter()       { return this->begin(); }      //!< @details :private
    const_iterator  GetBeginIter() const { return this->begin();   }    //!< @details :private
    iterator        GetEndIter()         { return this->end();   }      //!< @details :private
    const_iterator  GetEndIter()   const { return this->end(); }        //!< @details :private
    
    reverse_iterator        GetBeginReverseIter()       { return this->rbegin(); }  //!< @details :private
    const_reverse_iterator  GetBeginReverseIter() const { return this->rbegin(); }  //!< @details :private
    reverse_iterator        GetEndReverseIter()         { return this->rend(); }    //!< @details :private
    const_reverse_iterator  GetEndReverseIter()   const { return this->rend(); }    //!< @details :private
    
    reference       GetFront()       { return this->front(); }  //!< @details :private
    const_reference GetFront() const { return this->front(); }  //!< @details :private
    reference       GetBack()        { return this->back(); }   //!< @details :private
    const_reference GetBack()  const { return this->back(); }   //!< @details :private

    iterator Insert(iterator it, pointer p) { return this->insert(it, p); } //!< @details :private
    void     PushFront(pointer p)           { this->push_front(p); }        //!< @details :private
    void     PushBack(pointer p)            { this->push_back(p); }         //!< @details :private
    
    void    PopFront() { this->pop_front(); }   //!< @details :private
    void    PopBack()  { this->pop_back();  }   //!< @details :private
    
    iterator Erase(iterator it)                      { return this->erase(it); }                //!< @details :private
    iterator Erase(iterator itFirst,iterator itLast) { return this->erase(itFirst, itLast); }   //!< @details :private
    iterator Erase(pointer p)                        { return this->erase(p); }                 //!< @details :private
    
    void     Clear() { this->clear(); }         //!< @details :private
    void     Reverse() { this->reverse(); }     //!< @details :private
};


}  // namespace ut
}  // namespace nw

#endif  /* NW_UT_LINKLIST_H_ */