//-----------------------------------------------------------------------------
// File: Linklist.h
// Desc: Linked list class.
//
// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
// PARTICULAR PURPOSE.
//
//  Copyright (C) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------

#pragma once

// Notes:
// 
// The List class template implements a simple double-linked list. 
// It uses STL's copy semantics. 

// There are two versions of the Clear() method:
//  Clear(void) clears the list w/out cleaning up the object.
//  Clear(FN fn) takes a functor object that releases the objects, if they need cleanup.

// The List class supports enumeration. Example of usage:
//
// List<T>::POSIITON pos = list.GetFrontPosition();
// while (pos != list.GetEndPosition())
// {
//     T item;
//     hr = list.GetItemPos(&item);
//     pos = list.Next(pos);
// }

// The ComPtrList class template derives from List<> and implements a list of COM pointers.

namespace MediaFoundationSamples
{


    template <class T>
    struct NoOp
    {
        void operator()(T& t)
        {
        }
    };

    template <class T>
    class List
    {
    protected:

        // Nodes in the linked list
        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; }
        };

    public:

        // Object for enumerating the list.
        class POSITION
        {
            friend class List<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) 
            {
            }
        };

    protected:
        Node    m_anchor;  // Anchor node for the linked list.
        DWORD   m_count;   // Number of items in the list.

        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;
        }

        // RemoveItem:
        // Removes a node and optionally returns the item.
        // ppItem can be NULL.
        virtual HRESULT RemoveItem(Node *pNode, T *ppItem)
        {
            if (pNode == NULL)
            {
                return E_POINTER;
            }

            assert(pNode != &m_anchor); // We should never try to remove the anchor node.
            if (pNode == &m_anchor)
            {
                return E_INVALIDARG;
            }


            T item;

            // The next node's previous is this node's previous.
            pNode->next->prev = pNode->prev;

            // The previous node's next is this node's next.
            pNode->prev->next = pNode->next;

            item = pNode->item;
            delete pNode;

            m_count--;

            if (ppItem)
            {
                *ppItem = item;
            }

            return S_OK;
        }

    public:

        List()
        {
            m_anchor.next = &m_anchor;
            m_anchor.prev = &m_anchor;

            m_count = 0;
        }

        virtual ~List()
        {
            Clear();
        }

        // Insertion functions
        HRESULT InsertBack(T item)
        {
            return InsertAfter(item, m_anchor.prev);
        }


        HRESULT InsertFront(T item)
        {
            return InsertAfter(item, &m_anchor);
        }

        // RemoveBack: Removes the tail of the list and returns the value.
        // ppItem can be NULL if you don't want the item back. (But the method does not release the item.)
        HRESULT RemoveBack(T *ppItem)
        {
            if (IsEmpty())
            {
                return E_FAIL;
            }
            else
            {
                return RemoveItem(Back(), ppItem);
            }
        }

        // RemoveFront: Removes the head of the list and returns the value.
        // ppItem can be NULL if you don't want the item back. (But the method does not release the item.)
        HRESULT RemoveFront(T *ppItem)
        {
            if (IsEmpty())
            {
                return E_FAIL;
            }
            else
            {
                return RemoveItem(Front(), ppItem);
            }
        }

        // GetBack: Gets the tail item.
        HRESULT GetBack(T *ppItem)
        {
            if (IsEmpty())
            {
                return E_FAIL;
            }
            else
            {
                return GetItem(Back(), ppItem);
            }
        }

        // GetFront: Gets the front item.
        HRESULT GetFront(T *ppItem)
        {
            if (IsEmpty())
            {
                return E_FAIL;
            }
            else
            {
                return GetItem(Front(), ppItem);
            }
        }


        // GetCount: Returns the number of items in the list.
        DWORD GetCount() const { return m_count; }

        bool IsEmpty() const
        {
            return (GetCount() == 0);
        }

        // Clear: Takes a functor object whose operator()
        // frees the object on the list.
        template <class FN>
        void Clear(FN& clear_fn)
        {
            Node *n = m_anchor.next;

            // Delete the nodes
            while (n != &m_anchor)
            {
                clear_fn(n->item);

                Node *tmp = n->next;
                delete n;
                n = tmp;
            }

            // Reset the anchor to point at itself
            m_anchor.next = &m_anchor;
            m_anchor.prev = &m_anchor;

            m_count = 0;
        }

        // Clear: Clears the list. (Does not delete or release the list items.)
        virtual void Clear()
        {
            Clear<NoOp<T>>(NoOp<T>());
        }


        // Enumerator functions

        POSITION FrontPosition()
        {
            if (IsEmpty())
            {
                return POSITION(NULL);
            }
            else
            {
                return POSITION(Front());
            }
        }

        POSITION EndPosition() const
        {
            return POSITION();
        }

        HRESULT GetItemPos(POSITION pos, T *ppItem)
        {   
            if (pos.pNode)
            {
                return 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);
            }
        }

        // Remove an item at a position. 
        // The item is returns in ppItem, unless ppItem is NULL.
        // NOTE: This method invalidates the POSITION object.
        HRESULT Remove(POSITION& pos, T *ppItem)
        {
            if (pos.pNode)
            {
                // Remove const-ness temporarily...
                Node *pNode = const_cast<Node*>(pos.pNode);

                pos = POSITION();

                return RemoveItem(pNode, ppItem);
            }
            else
            {
                return E_INVALIDARG;
            }
        }

    };



    // Typical functors for Clear method.

    // ComAutoRelease: Releases COM pointers.
    // MemDelete: Deletes pointers to new'd memory.

    class ComAutoRelease
    {
    public: 
        void operator()(IUnknown *p)
        {
            if (p)
            {
                p->Release();
            }
        }
    };
        
    class MemDelete
    {
    public: 
        void operator()(void *p)
        {
            if (p)
            {
                delete p;
            }
        }
    };


    // ComPtrList class
    // Derived class that makes it safer to store COM pointers in the List<> class.
    // It automatically AddRef's the pointers that are inserted onto the list
    // (unless the insertion method fails). 
    //
    // T must be a COM interface type. 
    // example: ComPtrList<IUnknown>
    //
    // NULLABLE: If true, client can insert NULL pointers. This means GetItem can
    // succeed but return a NULL pointer. By default, the list does not allow NULL
    // pointers.

    template <class T, bool NULLABLE = FALSE>
    class ComPtrList : public List<T*>
    {
    public:

        typedef T* Ptr;

        void Clear()
        {
            List<Ptr>::Clear(ComAutoRelease());
        }

        ~ComPtrList()
        {
            Clear();
        }

    protected:
        HRESULT InsertAfter(Ptr item, Node *pBefore)
        {
            // Do not allow NULL item pointers unless NULLABLE is true.
            if (!item && !NULLABLE)
            {
                return E_POINTER;
            }

            if (item)
            {
                item->AddRef();
            }

            HRESULT hr = List<Ptr>::InsertAfter(item, pBefore);
            if (FAILED(hr))
            {
                SAFE_RELEASE(item);
            }
            return hr;
        }

        HRESULT GetItem(const Node *pNode, Ptr* ppItem)
        {
            Ptr pItem = NULL;

            // The base class gives us the pointer without AddRef'ing it.
            // If we return the pointer to the caller, we must AddRef().
            HRESULT hr = List<Ptr>::GetItem(pNode, &pItem);
            if (SUCCEEDED(hr))
            {
                assert(pItem || NULLABLE);
                if (pItem)
                {
                    *ppItem = pItem;
                    (*ppItem)->AddRef();
                }
            }
            return hr;
        }

        HRESULT RemoveItem(Node *pNode, Ptr *ppItem)
        {
            // ppItem can be NULL, but we need to get the
            // item so that we can release it. 

            // If ppItem is not NULL, we will AddRef it on the way out.

            Ptr pItem = NULL;

            HRESULT hr = List<Ptr>::RemoveItem(pNode, &pItem);

            if (SUCCEEDED(hr))
            {
                assert(pItem || NULLABLE);
                if (ppItem && pItem)
                {
                    *ppItem = pItem;
                    (*ppItem)->AddRef();
                }

                SAFE_RELEASE(pItem);
            }

            return hr;
        }
    };

};  // namespace MediaFoundationSamples

