/* 
 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
 * Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
 *
 * Distributed under the terms of the MIT License.
 */
#ifndef KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
#define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H


#include <util/DoublyLinkedList.h>


/*!
        A doubly linked queue is like a doubly linked list, but only has a pointer
        to the head of the list, none to its tail.
*/


#ifdef __cplusplus

// for convenience
#define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink>


template<typename Element,
        typename GetLink = DoublyLinkedListStandardGetLink<Element> >
class DoublyLinkedQueue {
private:
        typedef DoublyLinkedQueue<Element, GetLink>     Queue;
        typedef DoublyLinkedListLink<Element>           Link;

public:
        class Iterator {
                public:
                        Iterator(Queue *queue)
                                :
                                fQueue(queue)
                        {
                                Rewind();
                        }

                        Iterator(const Iterator &other)
                        {
                                *this = other;
                        }

                        bool HasNext() const
                        {
                                return fNext;
                        }

                        Element *Next()
                        {
                                fCurrent = fNext;
                                if (fNext)
                                        fNext = fQueue->GetNext(fNext);
                                return fCurrent;
                        }

                        Element *Remove()
                        {
                                Element *element = fCurrent;
                                if (fCurrent) {
                                        fQueue->Remove(fCurrent);
                                        fCurrent = NULL;
                                }
                                return element;
                        }

                        Iterator &operator=(const Iterator &other)
                        {
                                fQueue = other.fQueue;
                                fCurrent = other.fCurrent;
                                fNext = other.fNext;
                                return *this;
                        }

                        void Rewind()
                        {
                                fCurrent = NULL;
                                fNext = fQueue->First();
                        }

                private:
                        Queue   *fQueue;
                        Element *fCurrent;
                        Element *fNext;
        };

        class ConstIterator {
                public:
                        ConstIterator(const Queue *queue)
                                :
                                fQueue(queue)
                        {
                                Rewind();
                        }

                        ConstIterator(const ConstIterator &other)
                        {
                                *this = other;
                        }

                        bool HasNext() const
                        {
                                return fNext;
                        }

                        Element *Next()
                        {
                                Element *element = fNext;
                                if (fNext)
                                        fNext = fQueue->GetNext(fNext);
                                return element;
                        }

                        ConstIterator &operator=(const ConstIterator &other)
                        {
                                fQueue = other.fQueue;
                                fNext = other.fNext;
                                return *this;
                        }

                        void Rewind()
                        {
                                fNext = fQueue->First();
                        }

                private:
                        const Queue     *fQueue;
                        Element         *fNext;
        };

public:
        DoublyLinkedQueue() : fFirst(NULL) {}
        ~DoublyLinkedQueue() {}

        inline bool IsEmpty() const             { return (fFirst == NULL); }

        inline void Insert(Element *element);
        inline void InsertBefore(Element *before, Element *element);
        inline void Add(Element *element);
        inline void Remove(Element *element);

        inline void Swap(Element *a, Element *b);

        inline void TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList);

        inline void RemoveAll();
        inline void MakeEmpty()                 { RemoveAll(); }

        inline Element *First() const   { return fFirst; }
        inline Element *Head() const    { return fFirst; }

        inline Element *RemoveHead();

        inline Element *GetPrevious(Element *element) const;
        inline Element *GetNext(Element *element) const;

        inline int32 Size() const;
                // O(n)!

        inline Iterator GetIterator()                           { return Iterator(this); }
        inline ConstIterator GetIterator() const        { return ConstIterator(this); }

private:
        Element *fFirst;

        static GetLink  sGetLink;
};


// inline methods

// Insert
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element)
{
        if (element) {
                Link *elLink = sGetLink(element);
                elLink->previous = NULL;
                elLink->next = fFirst;
                if (fFirst)
                        sGetLink(fFirst)->previous = element;
                fFirst = element;
        }
}

// Insert
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::InsertBefore(Element *before, Element *element)
{
        if (before == NULL) {
                Insert(element);
                return;
        }
        if (element == NULL)
                return;

        Link *beforeLink = sGetLink(before);
        Link *link = sGetLink(element);

        link->next = before;
        link->previous = beforeLink->previous;
        if (link->previous != NULL)
                sGetLink(link->previous)->next = element;
        beforeLink->previous = element;

        if (fFirst == before)
                fFirst = element;
}

// Add
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element)
{
        Insert(element);
}

// Remove
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element)
{
        if (element == NULL)
                return;

#if DEBUG_DOUBLY_LINKED_LIST
        ASSERT_PRINT(fFirst != NULL,
                "queue: %p, element: %p\n", this, element);
#endif

        Link *elLink = sGetLink(element);
        if (element == fFirst)
                fFirst = elLink->next;
        else
                sGetLink(elLink->previous)->next = elLink->next;

        if (elLink->next)
                sGetLink(elLink->next)->previous = elLink->previous;

        elLink->next = elLink->previous = NULL;
}

// Swap
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b)
{
        if (a && b && a != b) {
                Link *aLink = sGetLink(a);
                Link *bLink = sGetLink(b);
                Element *aPrev = aLink->previous;
                Element *bPrev = bLink->previous;
                Element *aNext = aLink->next;
                Element *bNext = bLink->next;
                // place a
                if (bPrev)
                        sGetLink(bPrev)->next = a;
                else
                        fFirst = a;
                if (bNext)
                        sGetLink(bNext)->previous = a;

                aLink->previous = bPrev;
                aLink->next = bNext;
                // place b
                if (aPrev)
                        sGetLink(aPrev)->next = b;
                else
                        fFirst = b;
                if (aNext)
                        sGetLink(aNext)->previous = b;

                bLink->previous = aPrev;
                bLink->next = aNext;
        }
}

// TakeFrom
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList)
{
        if (fromList && fromList->fFirst) {
                if (fFirst) {
                        Element *element = fFirst;
                        Link *elLink;
                        while ((elLink = sGetLink(element))->next) {
                                element = elLink->next;
                        }
                        elLink->next = fromList->fFirst;
                } else {
                        fFirst = fromList->fFirst;
                }
                fromList->fFirst = NULL;
        }
}

// RemoveAll
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll()
{
        Element *element = fFirst;
        while (element) {
                Link *elLink = sGetLink(element);
                element = elLink->next;
                elLink->previous = NULL;
                elLink->next = NULL;
        }
        fFirst = NULL;
}

// RemoveHead
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead()
{
        Element *element = Head();
        Remove(element);
        return element;
}

// GetPrevious
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const
{
        Element *result = NULL;
        if (element)
                result = sGetLink(element)->previous;
        return result;
}

// GetNext
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const
{
        Element *result = NULL;
        if (element)
                result = sGetLink(element)->next;
        return result;
}

// Size
DOUBLY_LINKED_LIST_TEMPLATE_LIST
int32
DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const
{
        int32 count = 0;
        for (Element* element = First(); element; element = GetNext(element))
                count++;
        return count;
}

// sGetLink
DOUBLY_LINKED_LIST_TEMPLATE_LIST
GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink;

#endif  /* __cplusplus */

#endif  // _KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H