/*---------------------------------------------------------------------------*
  Project:  Horizon
  File:     fnd_LinkedList.h

  Copyright (C)2009 Nintendo Co., Ltd.  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.

  $Rev: 21468 $
 *---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*
  Project:  NW4R - SystemLib - include - nw4r - ut
  File:     LinkedList.h

  Copyright (C)2005-2008 Nintendo  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: 1.13 #$
 *---------------------------------------------------------------------------*/

/* @file
  @brief 双方向リンクリストを扱うクラステンプレートです。

*/

#ifndef NN_FND_FND_LINKEDLIST_H_
#define NN_FND_FND_LINKEDLIST_H_

#ifdef __cplusplus

#include <nn/assert.h>
#include <nn/util/util_NonCopyable.h>
#include <nn/fnd/fnd_Result.h>

namespace nn { namespace fnd {

// 使用例
//
// class Hoge : public IntrusiveLinkedList<Hoge>::Item { ... };
// tyepdef IntrusiveLinkedList<Hoge> HogeList;
//
// Hoge a, b, c;
// {
//      HogeList list;
//      list.PushFront(&a);
//      list.PushBack(&b);
//      list.PushFront(&a); // PANIC: 二重にリストに入れることはできない。
//      if (Hoge* p = list.PopBack())
//      {
//          // *p を使った処理
//      }
//      list.Erase(&a); // 要素を指定して削除
//      list.Clear();
//  } // デストラクタで自動 Clear()

// TODO: 未テスト
// NEED_DOCUMENT
// NEED_TEST

/*
    @brief 双方向リンクリストのためのクラステンプレートです。
*/
template <typename T, typename Tag = void>
class IntrusiveLinkedList : private nn::util::NonCopyable<IntrusiveLinkedList<T, Tag> >
{
public:

    class Item;   //!< ノードクラス
    
    /*
        @brief コンストラクタです。
    */
    IntrusiveLinkedList() : m_Head(0) {}

    /*
        @brief デストラクタです。
    */
    ~IntrusiveLinkedList() { Clear(); }
    
    /*
        @brief リストが空かどうかを取得します。

        @return リストが空であれば true を返します。そうでなければ false を返します。
    */
    bool IsEmpty() const { return !m_Head; }

    /*
        @brief リストの末尾に要素を追加します。

        @param[in] p 追加する要素
    */
    void PushBack(T* p);

    /*
        @brief リストの先頭に要素を追加します。

        @param[in] p 追加する要素
    */
    void PushFront(T* p);

    /*
        @brief リストの先頭の要素へのポインタを取得します。

        @return 先頭の要素へのポインタを返します。
    */
    T* GetFront() const;

    /*
        @brief リストの末尾の要素へのポインタを取得します。

        @return 末尾の要素へのポインタを返します。
    */
    T* GetBack() const;

    /*
        @brief リストの先頭の要素をリストから取り出します。

               リストの先頭のノードを削除し、要素へのポインタを返します。

        @return 先頭の要素へのポインタを返します。
    */
    T* PopFront();

    /*
        @brief リストの末尾の要素をリストから取り出します。

               リストの末尾のノードを削除し、要素へのポインタを返します。

        @return 末尾の要素へのポインタを返します。
    */
    T* PopBack();

    /*
        @brief 次の要素へのポインタを取得します。

        @param[in] 基準となる要素の位置

        @return 次の要素へのポインタを返します。
    */
    T* GetNext(T* p) const;

    /*
        @brief 前の要素へのポインタを取得します。

        @param[in] 基準となる要素の位置

        @return 前の要素へのポインタを返します。
    */
    T* GetPrevious(T* p) const;

    /*
        @brief 要素をリストに挿入します。

               position で指定したノードの直前に inserted が挿入されます。

        @param[in] position 基準となる要素の位置
        @param[in] inserted 挿入する要素
    */
    void Insert(T* position, T* inserted);

    /*
        @brief 要素をリストから削除します。

        @parma[in] p 削除する要素
    */
    void Erase(T* p);

    /*
        @brief リストから全要素を削除します。
    */
    void Clear();
    
private:
    
    Item* m_Head;  //!< 先頭のノード
    
    /*
        :private

        @brief 指定したノードのリンクをクリアします。

        @param[in] p リンクをクリアする対象のノード
    */
    static void ClearLinks(Item* p);

    /*
        :private

        @brief ノード p の直前にノード p を挿入します。
    */
    static void InsertBefore(Item* p, Item* q);

};

// NEED_DOCUMENT
// NEED_TEST
/*
    :private

    @brief 双方向リンクリストのためのノードです。
*/
template <typename T, typename Tag>
class IntrusiveLinkedList<T, Tag>::Item : private nn::util::NonCopyable<IntrusiveLinkedList<T, Tag>::Item>
{
    friend class IntrusiveLinkedList;
protected:
    Item() : m_PreviousLink(0), m_NextLink(0) {}
    ~Item() { NN_TASSERT_(!m_PreviousLink && !m_NextLink); }
    T* GetPrevious() const { return static_cast<T*>(m_PreviousLink); }
    T* GetNext() const { return static_cast<T*>(m_NextLink); }
private:
    Item* m_PreviousLink;
    Item* m_NextLink;
};

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::ClearLinks(Item* p)
{
    p->m_PreviousLink = p->m_NextLink = 0;
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::InsertBefore(Item* p, Item* q)
{
    q->m_NextLink = p;
    p->m_PreviousLink->m_NextLink = q;
    q->m_PreviousLink = p->m_PreviousLink;
    p->m_PreviousLink = q;
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::PushBack(T* p)
{
    NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
    NN_TASSERT_(p);
    Item* pNode = static_cast<Item*>(p);
    NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
    NN_TASSERT_(!pNode->m_PreviousLink);
    NN_TASSERT_(!pNode->m_NextLink);
    if (IsEmpty())
    {
        p->m_PreviousLink = p->m_NextLink = p;
        this->m_Head = p;
    }
    else
    {
        InsertBefore(m_Head, pNode);
    }
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::PushFront(T* p)
{
    NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
    NN_TASSERT_(p);
    Item* pNode = static_cast<Item*>(p);
    NN_ASSERT_WITH_RESULT(!pNode->m_PreviousLink, MakeResultAlreadyListed());
    NN_TASSERT_(!pNode->m_PreviousLink);
    NN_TASSERT_(!pNode->m_NextLink);
    if (IsEmpty())
    {
        p->m_PreviousLink = p->m_NextLink = p;
    }
    else
    {
        InsertBefore(m_Head, pNode);
    }
    this->m_Head = p;
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::GetFront() const
{
    return static_cast<T*>(m_Head);
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::GetBack() const
{
    if (IsEmpty())
    {
        return 0;
    }
    else
    {
        return static_cast<T*>(m_Head->m_PreviousLink);
    }
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::PopFront()
{
    if (T* ret = GetFront())
    {
        this->Erase(ret);
        return ret;
    }
    else
    {
        return 0;
    }
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::PopBack()
{
    if (T* ret = GetBack())
    {
        this->Erase(ret);
        return ret;
    }
    else
    {
        return 0;
    }
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::GetPrevious(T* p) const
{
    NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
    NN_TASSERT_(p);
    Item* pNode = static_cast<Item*>(p);
    NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
    NN_TASSERT_(pNode->m_PreviousLink);
    NN_TASSERT_(pNode->m_NextLink);
    if (p == this->GetFront())
    {
        return 0;
    }
    return static_cast<T*>(pNode->m_PreviousLink);
}

template <typename T, typename Tag>
inline T* IntrusiveLinkedList<T, Tag>::GetNext(T* p) const
{
    NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
    NN_TASSERT_(p);
    Item* pNode = static_cast<Item*>(p);
    NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
    NN_TASSERT_(pNode->m_PreviousLink);
    NN_TASSERT_(pNode->m_NextLink);
    if (p == this->GetBack())
    {
        return 0;
    }
    return static_cast<T*>(pNode->m_NextLink);
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::Insert(T* position, T* inserted)
{
    NN_ASSERT_WITH_RESULT(inserted, MakeResultInvalidAddress());
    NN_TASSERT_(inserted);
    Item* pNodeInserted = static_cast<Item*>(inserted);
    Item* pNodePosition = static_cast<Item*>(position);
    NN_ASSERT_WITH_RESULT(!pNodeInserted->m_PreviousLink, MakeResultAlreadyListed());
    NN_TASSERT_(!pNodeInserted->m_PreviousLink);
    NN_TASSERT_(!pNodeInserted->m_NextLink);
    if (pNodePosition == m_Head)
    {
        PushFront(inserted);
    }
    else if (pNodePosition)
    {
        NN_ASSERT_WITH_RESULT(pNodePosition->m_PreviousLink, MakeResultInvalidNode());
        NN_TASSERT_(pNodePosition->m_PreviousLink);
        NN_TASSERT_(pNodePosition->m_NextLink);
        InsertBefore(pNodePosition, pNodeInserted);
    }
    else
    {
        PushBack(inserted);
    }
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::Erase(T* p)
{
    NN_ASSERT_WITH_RESULT(p, MakeResultInvalidAddress());
    NN_TASSERT_(p);
    Item* pNode = static_cast<Item*>(p);
    NN_ASSERT_WITH_RESULT(pNode->m_PreviousLink, MakeResultInvalidNode());
    NN_TASSERT_(pNode->m_PreviousLink);
    NN_TASSERT_(pNode->m_NextLink);
    if (pNode == pNode->m_PreviousLink)
    {
        this->m_Head = 0;
    }
    else
    {
        if (m_Head == pNode)
        {
            this->m_Head = m_Head->m_NextLink;
        }
        pNode->m_NextLink->m_PreviousLink = pNode->m_PreviousLink;
        pNode->m_PreviousLink->m_NextLink = pNode->m_NextLink;
    }
    ClearLinks(pNode);
}

template <typename T, typename Tag>
inline void IntrusiveLinkedList<T, Tag>::Clear()
{
    if (m_Head)
    {
        Item* p = m_Head;
        while (p)
        {
            Item* q = p;
            p = p->m_NextLink;
            ClearLinks(q);
        }
        this->m_Head = 0;
    }
}

}  // namespace util
}  // namespace nn

#endif // __cplusplus

#endif  /* NN_UTIL_LINKEDLIST_H_ */