//------------------------------------------------------------------------------
// emUcList.h
//
// Copyright (C) 2024 Oliver Hamann.
//
// Homepage: http://eaglemode.sourceforge.net/
//
// This program is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License version 3 as published by the
// Free Software Foundation.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU General Public License version 3 for
// more details.
//
// You should have received a copy of the GNU General Public License version 3
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//------------------------------------------------------------------------------

#ifndef emUcList_h
#define emUcList_h

#ifndef emList_h
#include <emCore/emList.h>
#endif


//==============================================================================
//================================== emUcList ==================================
//==============================================================================

template <class OBJ> class emUcList : public emUncopyable {

public:

        // Template class for a double-linked NULL-terminated uncopyable list.
        // This is similar to emList, but the list cannot be copied, and so the
        // elements do not have to be copyable.

        emUcList();
                // Construct an empty list.

        ~emUcList();
                // Destructor.

        const OBJ * GetFirst() const;
        OBJ * GetFirst();
        const OBJ * GetLast() const;
        OBJ * GetLast();
        const OBJ * GetNext(const OBJ * elem) const;
        OBJ * GetNext(const OBJ * elem);
        const OBJ * GetPrev(const OBJ * elem) const;
        OBJ * GetPrev(const OBJ * elem);
                // Get a pointer to the first or last element of this list, or
                // get a pointer to the next or previous element of an element
                // of this list.
                // Arguments:
                //   elem - A pointer to an element in this list, must never be
                //          NULL.
                // Returns:
                //   A pointer to the requested element in this list, or NULL if
                //   there is no such element.

        OBJ * InsertNewAtBeg();
        OBJ * InsertNewAtEnd();
        OBJ * InsertNewBefore(const OBJ * pos);
        OBJ * InsertNewAfter(const OBJ * pos);
                // Insert a new element at the beginning or end of this list, or
                // before or after an element of this list.
                // Arguments:
                //   pos   - An element in this list before which or after which
                //           the insertion has to take place. NULL is allowed
                //           here. InsertNewBefore(NULL) means to insert at the
                //           end, and InsertNewAfter(NULL) means to insert at
                //           the beginning.

        OBJ * AddNew();
                // Just another name for InsertNewAtEnd.

        void MoveToBeg(const OBJ * elem);
        void MoveToBeg(const OBJ * first, const OBJ * last);
        void MoveToBeg(emUcList * src);
        void MoveToBeg(emUcList * src, const OBJ * elem);
        void MoveToBeg(emUcList * src, const OBJ * first, const OBJ * last);
        void MoveToEnd(const OBJ * elem);
        void MoveToEnd(const OBJ * first, const OBJ * last);
        void MoveToEnd(emUcList * src);
        void MoveToEnd(emUcList * src, const OBJ * elem);
        void MoveToEnd(emUcList * src, const OBJ * first, const OBJ * last);
        void MoveBefore(const OBJ * pos, const OBJ * elem);
        void MoveBefore(const OBJ * pos, const OBJ * first, const OBJ * last);
        void MoveBefore(const OBJ * pos, emUcList * src);
        void MoveBefore(const OBJ * pos, emUcList * src, const OBJ * elem);
        void MoveBefore(const OBJ * pos, emUcList * src, const OBJ * first,
                        const OBJ * last);
        void MoveAfter(const OBJ * pos, const OBJ * elem);
        void MoveAfter(const OBJ * pos, const OBJ * first, const OBJ * last);
        void MoveAfter(const OBJ * pos, emUcList * src);
        void MoveAfter(const OBJ * pos, emUcList * src, const OBJ * elem);
        void MoveAfter(const OBJ * pos, emUcList * src, const OBJ * first,
                       const OBJ * last);
                // Move elements from a source list to the beginning or end of
                // this list, or before or after an element of this list.
                // Arguments:
                //   pos   - An element in this list before which or after which
                //           the elements are to be moved. It must not be a
                //           member of the moved elements! NULL is allowed here.
                //           MoveBefore(NULL,...) means to move to the end, and
                //           MoveAfter(NULL,...) means to move to the beginning.
                //   src   - Pointer to the source list. If NULL or not given,
                //           this list itself is the source list.
                //   elem  - An element of the source list, which shall be
                //           moved. If NULL, nothing is moved.
                //   first - An element of the source list. It is the first one
                //           of a range of elements to be moved. If NULL,
                //           nothing is moved.
                //   last  - An element of the source list, not before 'first'.
                //           It is the last one of the range of elements to be
                //           moved. If NULL, nothing is moved.

        void RemoveFirst();
        void RemoveLast();
        void Remove(const OBJ * elem);
        void Remove(const OBJ * first, const OBJ * last);
                // Remove (and delete) the first element, the last element, a
                // given element or a range of elements from this list.
                // Arguments:
                //   elem  - An element of this list, which shall be removed.
                //           If NULL, nothing is removed.
                //   first - An element of this list. It is the first one of a
                //           range of elements to be removed. If NULL, nothing
                //           is removed.
                //   last  - An element of this list, not before 'first'. It is
                //           the last one of the range of elements to be
                //           removed. If NULL, nothing is removed.

        void Clear();
                // Remove (and delete) all elements of this list.

        bool IsEmpty() const;
                // Ask whether this list has no elements.

        bool Sort(
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL
        );
                // Sort this list. The order of equal elements is preserved.
                // Arguments:
                //   compare - Function for comparing two elements. If you want
                //             the elements to be compared via the operators '<'
                //             and '>', say:
                //               emStdComparer<OBJ>::Compare
                //             with OBJ replaced by the real type of the
                //             elements. The context argument is ignored then.
                //             Arguments:
                //               obj1    - Pointer to first element.
                //               obj2    - Pointer to second element.
                //               context - See below.
                //             Returns: Zero if the elements are equal, a value
                //               greater than zero if the first element is
                //               greater than the second one, and a value less
                //               than zero if the first element is less than the
                //               second one.
                //   context - Any pointer to be forwarded to the compare
                //             function.
                // Returns: Whether there was a change.

        int GetCount() const;
                // Compute the number of elements.

        const OBJ * GetAtIndex(int index) const;
                // Search the element at the given index. Returns NULL if the
                // index is out of range. The rules for the validity of the
                // pointer are the same as with the GetFirst() method.

        int GetIndexOf(const OBJ * elem) const;
                // Search the given element and return its index. Returns -1
                // if it is not an element of this list.

private:

        struct Element {
                OBJ Obj;
                OBJ * Next;
                OBJ * Prev;
        };

        OBJ * First;
        OBJ * Last;
};


//==============================================================================
//============================== Implementations ===============================
//==============================================================================

template <class OBJ> inline emUcList<OBJ>::emUcList()
        : First(NULL),
        Last(NULL)
{
}

template <class OBJ> emUcList<OBJ>::~emUcList()
{
        Clear();
}

template <class OBJ> inline const OBJ * emUcList<OBJ>::GetFirst() const
{
        return First;
}

template <class OBJ> inline OBJ * emUcList<OBJ>::GetFirst()
{
        return First;
}

template <class OBJ> inline const OBJ * emUcList<OBJ>::GetLast() const
{
        return Last;
}

template <class OBJ> inline OBJ * emUcList<OBJ>::GetLast()
{
        return Last;
}

template <class OBJ> inline const OBJ * emUcList<OBJ>::GetNext(
        const OBJ * elem
) const
{
        return EM_LSTIMP_NEXT(elem);
}

template <class OBJ> inline OBJ * emUcList<OBJ>::GetNext(const OBJ * elem)
{
        return EM_LSTIMP_NEXT(elem);
}

template <class OBJ> inline const OBJ * emUcList<OBJ>::GetPrev(
        const OBJ * elem
) const
{
        return EM_LSTIMP_PREV(elem);
}

template <class OBJ> inline OBJ * emUcList<OBJ>::GetPrev(const OBJ * elem)
{
        return EM_LSTIMP_PREV(elem);
}

template <class OBJ> inline OBJ * emUcList<OBJ>::InsertNewAtBeg()
{
        return InsertNewAfter(NULL);
}

template <class OBJ> inline OBJ * emUcList<OBJ>::InsertNewAtEnd()
{
        return InsertNewBefore(NULL);
}

template <class OBJ> OBJ * emUcList<OBJ>::InsertNewBefore(const OBJ * pos)
{
        OBJ * e;

        e=&(new Element())->Obj;
        if ((EM_LSTIMP_NEXT(e)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_PREV(e)=Last)==NULL) First=e;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                Last=e;
        }
        else {
                if ((EM_LSTIMP_PREV(e)=EM_LSTIMP_PREV(pos))==NULL) First=e;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                EM_LSTIMP_PREV(pos)=e;
        }
        return e;
}

template <class OBJ> OBJ * emUcList<OBJ>::InsertNewAfter(const OBJ * pos)
{
        OBJ * e;

        e=&(new Element())->Obj;
        if ((EM_LSTIMP_PREV(e)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_NEXT(e)=First)==NULL) Last=e;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                First=e;
        }
        else {
                if ((EM_LSTIMP_NEXT(e)=EM_LSTIMP_NEXT(pos))==NULL) Last=e;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                EM_LSTIMP_NEXT(pos)=e;
        }
        return e;
}

template <class OBJ> inline OBJ * emUcList<OBJ>::AddNew()
{
        return InsertNewBefore(NULL);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(const OBJ * elem)
{
        MoveAfter(NULL,this,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
        const OBJ * first, const OBJ * last
)
{
        MoveAfter(NULL,this,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(emUcList * src)
{
        if (src) MoveAfter(NULL,src,src->First,src->Last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
        emUcList * src, const OBJ * elem
)
{
        MoveAfter(NULL,src,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
        emUcList * src, const OBJ * first, const OBJ * last
)
{
        MoveAfter(NULL,src,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(const OBJ * elem)
{
        MoveBefore(NULL,this,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
        const OBJ * first, const OBJ * last
)
{
        MoveBefore(NULL,this,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(emUcList * src)
{
        if (src) MoveBefore(NULL,src,src->First,src->Last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
        emUcList * src, const OBJ * elem
)
{
        MoveBefore(NULL,src,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
        emUcList * src, const OBJ * first, const OBJ * last
)
{
        MoveBefore(NULL,src,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
        const OBJ * pos, const OBJ * elem
)
{
        MoveBefore(pos,this,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
        const OBJ * pos, const OBJ * first, const OBJ * last
)
{
        MoveBefore(pos,this,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
        const OBJ * pos, emUcList * src
)
{
        if (src) MoveBefore(pos,src,src->First,src->Last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
        const OBJ * pos, emUcList * src, const OBJ * elem
)
{
        MoveBefore(pos,src,elem,elem);
}

template <class OBJ> void emUcList<OBJ>::MoveBefore(
        const OBJ * pos, emUcList * src, const OBJ * first, const OBJ * last
)
{
        if (!first || !last) return;
        if (!src) src=this;
        if (!EM_LSTIMP_PREV(first)) src->First=EM_LSTIMP_NEXT(last);
        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
        if (!EM_LSTIMP_NEXT(last)) src->Last=EM_LSTIMP_PREV(first);
        else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
        if ((EM_LSTIMP_NEXT(last)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_PREV(first)=Last)==NULL) First=(OBJ*)first;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
                Last=(OBJ*)last;
        }
        else {
                if ((EM_LSTIMP_PREV(first)=EM_LSTIMP_PREV(pos))==NULL) {
                        First=(OBJ*)first;
                }
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
                EM_LSTIMP_PREV(pos)=(OBJ*)last;
        }
}

template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
        const OBJ * pos, const OBJ * elem
)
{
        MoveAfter(pos,this,elem,elem);
}

template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
        const OBJ * pos, const OBJ * first, const OBJ * last
)
{
        MoveAfter(pos,this,first,last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
        const OBJ * pos, emUcList * src
)
{
        if (src) MoveAfter(pos,src,src->First,src->Last);
}

template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
        const OBJ * pos, emUcList * src, const OBJ * elem
)
{
        MoveAfter(pos,src,elem,elem);
}

template <class OBJ> void emUcList<OBJ>::MoveAfter(
        const OBJ * pos, emUcList * src, const OBJ * first, const OBJ * last
)
{
        if (!first || !last) return;
        if (!src) src=this;
        if (!EM_LSTIMP_PREV(first)) src->First=EM_LSTIMP_NEXT(last);
        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
        if (!EM_LSTIMP_NEXT(last)) src->Last=EM_LSTIMP_PREV(first);
        else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
        if ((EM_LSTIMP_PREV(first)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_NEXT(last)=First)==NULL) Last=(OBJ*)last;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
                First=(OBJ*)first;
        }
        else {
                if ((EM_LSTIMP_NEXT(last)=EM_LSTIMP_NEXT(pos))==NULL) {
                        Last=(OBJ*)last;
                }
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
                EM_LSTIMP_NEXT(pos)=(OBJ*)first;
        }
}

template <class OBJ> inline void emUcList<OBJ>::RemoveFirst()
{
        Remove(First,First);
}

template <class OBJ> inline void emUcList<OBJ>::RemoveLast()
{
        Remove(Last,Last);
}

template <class OBJ> inline void emUcList<OBJ>::Remove(const OBJ * elem)
{
        Remove(elem,elem);
}

template <class OBJ> void emUcList<OBJ>::Remove(
        const OBJ * first, const OBJ * last
)
{
        const OBJ * e;

        if (!first || !last) return;
        if (!EM_LSTIMP_PREV(first)) First=EM_LSTIMP_NEXT(last);
        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
        if (!EM_LSTIMP_NEXT(last)) Last=EM_LSTIMP_PREV(first);
        else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
        do {
                e=first;
                first=EM_LSTIMP_NEXT(first);
                delete EM_LSTIMP_ELEM(e);
        } while (e!=last);
}

template <class OBJ> void emUcList<OBJ>::Clear()
{
        OBJ * e1, * e2;

        for (e1=First; e1; e1=e2) {
                e2=EM_LSTIMP_NEXT(e1);
                delete EM_LSTIMP_ELEM(e1);
        }
        First=NULL;
        Last=NULL;
}

template <class OBJ> inline bool emUcList<OBJ>::IsEmpty() const
{
        return !First;
}

template <class OBJ> bool emUcList<OBJ>::Sort(
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context
)
{
        if (First==Last) return false;
        return emSortDoubleLinkedList(
                (void**)(void*)&First,
                (void**)(void*)&Last,
                offsetof(Element,Next)-offsetof(Element,Obj),
                offsetof(Element,Prev)-offsetof(Element,Obj),
                (int(*)(void*,void*,void*))compare,
                context
        );
}

template <class OBJ> int emUcList<OBJ>::GetCount() const
{
        const OBJ * e;
        int cnt;

        for (cnt=0, e=First; e; cnt++, e=EM_LSTIMP_NEXT(e));
        return cnt;
}

template <class OBJ> const OBJ * emUcList<OBJ>::GetAtIndex(int index) const
{
        const OBJ * e;

        if (index<0) e=NULL;
        else for (e=First; e && --index>=0; e=EM_LSTIMP_NEXT(e));
        return e;
}

template <class OBJ> int emUcList<OBJ>::GetIndexOf(const OBJ * elem) const
{
        const OBJ * e;
        int i;

        for (i=0, e=First; e; i++, e=EM_LSTIMP_NEXT(e)) {
                if (e==elem) return i;
        }
        return -1;
}


#endif