#pragma once

// メモ：
// 
// List テンプレートクラスは、簡単な双方向リストを実装する。
//
// ２つのバージョンの Clear() メソッドがある。
// ・Clear(void) は、内包するオブジェクトを解放せずにリストをクリアする。
// ・Clear(FN fn) は、オブジェクトを解放するための機能オブジェクトを使う。
//
// リストクラスは、列挙をサポートする。以下に例を挙げる。
//
// List<T>::POSIITON pos = list.GetFrontPosition();		// 先頭位置の取得
// while (pos != list.GetEndPosition())					// 列挙が終了するまで……
// {
//     T item;
//     hr = list.GetItemPos(&item);						// 現在位置のアイテムを取得（変数 pos は不要）
//     pos = list.Next(pos);							// 次の位置を取得
// }

namespace FDK
{
	template <class T>
	private class LinkList
	{

	protected:

		#pragma region [ リストノード構造体 Node の定義 ]
		//-----------------
		struct Node
		{
			Node *prev;
			Node *next;
			T    item;

			Node() : prev(NULL), next(NULL)
			{
			}
			Node( T item ) : prev(NULL), next(NULL)
			{
				this->item = item;
			}

			T Item() const
			{
				return item;
			}
		};
		//-----------------
		#pragma endregion

		#pragma region [ 典型的な Clear メソッド用クラスの定義（NoOp, ComAutoRelease, MemDelete）。]
		//-----------------
		class MemDelete
		{
		public: 
			void operator()( void *p )
			{
				if( p )
					delete p;
			}
		};
		template <class T> struct NoOp
		{
			void operator()(T& t)
			{
			}
		};
		class ComAutoRelease
		{
		public: 
			void operator()( IUnknown *p )
			{
				if( p )
					p->Release();
			}
		};
		//-----------------
		#pragma endregion

	public:

		#pragma region [ リストの列挙用内部クラス POSITION の定義 ]
		//-----------------
		class POSITION
		{
			friend class LinkList<T>;

		public:
			POSITION() : pNode(NULL)
			{
			}

			bool operator==(const POSITION &p) const
			{
				return pNode == p.pNode;
			}
			bool operator!=(const POSITION &p) const
			{
				return pNode != p.pNode;
			}

		private:
			const Node *pNode;
			POSITION(Node *p) : pNode(p) 
			{
			}
		};
		//-----------------
		#pragma endregion

	protected:

		Node    m_anchor;  // リストのアンカーノード。
		DWORD   m_count;   // リストのアイテム数（＝ノード数）。

		Node* Front() const
		{
			return m_anchor.next;
		}
		Node* Back() const
		{
			return m_anchor.prev;
		}

		virtual HRESULT InsertAfter( T item, Node *pBefore )
		{
			if( pBefore == NULL )
				return E_POINTER;

			Node *pNode = new Node( item );
            
			if( pNode == NULL )
				return E_OUTOFMEMORY;

			Node *pAfter = pBefore->next;
            
			pBefore->next = pNode;
			pAfter->prev = pNode;
			pNode->prev = pBefore;
			pNode->next = pAfter;

			m_count++;

			return S_OK;
		}
		virtual HRESULT GetItem( const Node *pNode, T *ppItem )
		{
			if( pNode == NULL || ppItem == NULL )
				return E_POINTER;

			*ppItem = pNode->item;
			return S_OK;
		}
		
		// ppItem が非 NULL なら、削除したアイテムをそこへ格納して返す。
		virtual HRESULT RemoveItem( Node *pNode, T *ppItem )
		{
			if( pNode == NULL )
				return E_POINTER;
			
			if( pNode == &m_anchor )	// アンカーノードは削除できない。
				return E_INVALIDARG;
			
			T item;
			
			pNode->next->prev = pNode->prev;
			pNode->prev->next = pNode->next;
			
			item = pNode->item;
			delete pNode;
			
			m_count--;
			
			if( ppItem )
				*ppItem = item;
			
			return S_OK;
		}
	
	public:
		
		LinkList()
		{
			m_anchor.next = &m_anchor;
			m_anchor.prev = &m_anchor;
			m_count = 0;
		}
		virtual ~LinkList()
		{
			this->Clear();
		}
		HRESULT InsertBack( T item )
		{
			return this->InsertAfter( item, m_anchor.prev );
		}
		HRESULT InsertFront( T item )
		{
			return this->InsertAfter( item, &m_anchor );
		}
		HRESULT RemoveBack( T *ppItem )
		{
			if( this->IsEmpty() )
			{
				return E_FAIL;
			}
			else
			{
				// ppItem が非 NULL なら、削除したアイテムをそこへ格納して返す。
				return this->RemoveItem( this->Back(), ppItem );
			}
		}
		HRESULT RemoveFront( T *ppItem )
		{
			if( this->IsEmpty() )
			{
				return E_FAIL;
			}
			else
			{
				// ppItem が非 NULL なら、削除したアイテムをそこへ格納して返す。
				return this->RemoveItem( this->Front(), ppItem );
			}
		}
		HRESULT GetBack( T *ppItem )
		{
			if( this->IsEmpty() )
			{
				return E_FAIL;
			}
			else
			{
				return this->GetItem( this->Back(), ppItem );
			}
		}
		HRESULT GetFront( T *ppItem )
		{
			if( this->IsEmpty() )
			{
				return E_FAIL;
			}
			else
			{
				return this->GetItem( this->Front(), ppItem );
			}
		}
		DWORD GetCount() const
		{
			return m_count;
		}
		bool IsEmpty() const
		{
			return ( GetCount() == 0 );
		}

		template <class FN>
		void Clear( FN& clear_fn )
		{
			// リスト上でオブジェクトを解放する operator() を持つオブジェクトを引数に取る。

			Node *n = m_anchor.next;
			
			// ノードを削除する。
			while( n != &m_anchor )
			{
				clear_fn( n->item );
				
				Node *tmp = n->next;
				delete n;
				n = tmp;
			}
			
			// アンカーを自分自身に設定する。
			m_anchor.next = &m_anchor;
			m_anchor.prev = &m_anchor;
			m_count = 0;
		}
		
		// リストアイテムの delete や release は行わない。
		virtual void Clear()
		{
			this->Clear<NoOp<T>>(NoOp<T>());
		}
		
		// 列挙関数
		
		POSITION FrontPosition()
		{
			if( this->IsEmpty() )
			{
				return POSITION( NULL );
			}
			else
			{
				return POSITION( this->Front() );
			}
		}
		POSITION EndPosition() const
		{
			return POSITION();
		}
		HRESULT GetItemPos( POSITION pos, T *ppItem )
		{   
			if( pos.pNode )
			{
				return this->GetItem( pos.pNode, ppItem );
			}
			else 
			{
				return E_FAIL;
			}
		}
		POSITION Next( const POSITION pos )
		{
			if( pos.pNode && ( pos.pNode->next != &m_anchor ) )
			{
				return POSITION( pos.pNode->next );
			}
			else
			{
				return POSITION( NULL );
			}
		}
		// ppItem が非 NULL なら、削除したアイテムをそこへ格納して返す。
		HRESULT Remove( POSITION& pos, T *ppItem )
		{
			if( pos.pNode )
			{
				Node *pNode = const_cast<Node*>( pos.pNode );

				pos = POSITION();
				return this->RemoveItem( pNode, ppItem );
			}
			else
			{
				return E_INVALIDARG;
			}
		}
	};
}
