//------------------------------------------------------------------------------
// emList.h
//
// Copyright (C) 2005-2010,2014-2015 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 emList_h
#define emList_h

#ifndef emStd1_h
#include <emCore/emStd1.h>
#endif


//==============================================================================
//=========================== Linked-list functions ============================
//==============================================================================

bool emSortSingleLinkedList(
        void * * pFirst, int nextOffset,
        int(*compare)(void * ptr1, void * ptr2, void * context),
        void * context=NULL
);
        // Sort a single-linked NULL-terminated list. The order of equal
        // elements is preserved. It is a merge-sort algorithm.
        // Arguments:
        //   pFirst     - Pointer to pointer to first element. On return,
        //                *pFirst will be set to the new first element.
        //   nextOffset - Offset where the pointer to the next element is stored
        //                within an element: If e points to an element, then
        //                *((void**)(((char*)e)+nextOffset)) points to the next
        //                element.
        //   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:
        //                  ptr1    - Pointer to first element.
        //                  ptr2    - 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: true if the order has changed, false otherwise.

bool emSortDoubleLinkedList(
        void * * pFirst, void * * pLast, int nextOffset, int prevOffset,
        int(*compare)(void * ptr1, void * ptr2, void * context),
        void * context=NULL
);
        // Sort a double-linked NULL-terminated list. The order of equal
        // elements is preserved. It is a merge-sort algorithm.
        // Arguments:
        //   pFirst     - Pointer to pointer to first element. On return,
        //                *pFirst will be set to the new first element.
        //   pLast      - Pointer to pointer to last element. On return, *pLast
        //                will be set to the new last element.
        //   nextOffset - Offset where the pointer to the next element is stored
        //                within an element: If e points to an element, then
        //                *((void**)(((char*)e)+nextOffset)) points to the next
        //                element.
        //   prevOffset - Offset where the pointer to the previous element is
        //                stored within an element: If e points to an element,
        //                then *((void**)(((char*)e)+prevOffset)) points to
        //                the previous element.
        //   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:
        //                  ptr1    - Pointer to first element.
        //                  ptr2    - 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: true if the order has changed, false otherwise.


//==============================================================================
//=================================== emList ===================================
//==============================================================================

template <class OBJ> class emList {

public:

        // Template class for a double-linked NULL-terminated list with
        // copy-on-write behavior and with support for stable iterators. The
        // template parameter OBJ describes the type of the elements.
        // Internally, emList extends the memory allocation for that type by the
        // next and prev pointers.
        //
        // There are two types of iterators. The very unstable one:
        // const OBJ * (please read the comments on GetFirst()), and the
        // stable one: the class Iterator, which can be found at the end of this
        // public declaration.
        //
        // If you wonder why a NULL in range arguments (first,last) of methods
        // means to cancel the operation, instead of taking the first/last
        // element of the whole list. It is because now one can say for example
        // l.Remove(l.GetNext(e),l.GetLast()) to remove all elements after the
        // element e, even when e is the last element.
        //
        // Here is a crazy example of printing "hello world\n":
        //
        // emList<emString> l;
        // emList<emString>::Iterator i;
        // const emString * j;
        // l="word";
        // l+="helo";
        // for (i.SetFirst(l); i; ++i) l.GetWritable(i)->Insert(3,'l');
        // l.Sort(emStdComparer<emString>::Compare);
        // for (i.SetLast(l); i; --i) l.InsertAfter(i," ");
        // *l.GetLastWritable()="\n";
        // // The following loop does not modify the list, so it is safe
        // // to do it with the unstable iterator j.
        // for (j=l.GetFirst(); j; j=l.GetNext(j)) printf("%s",j->Get());

        emList();
                // Construct an empty list.

        emList(const emList & src);
                // Construct a copied list.

        emList(const OBJ & obj);
                // Construct a list with one element copied from the given
                // object.

        emList(const emList & src1, const emList & src2);
        emList(const emList & src1, const OBJ & src2);
        emList(const OBJ & src1, const emList & src2);
        emList(const emList & src, const OBJ * first, const OBJ * last);
                // These constructors are designed mainly for internal use.

        ~emList();
                // Destructor.

        emList & operator = (const emList & list);
        emList & operator = (const OBJ & obj);
                // Make this list a copy of the given list or object.

        const OBJ * GetFirst() const;
        const OBJ * GetLast() const;
        const OBJ * GetNext(const OBJ * elem) const;
        const OBJ * GetPrev(const OBJ * elem) const;
                // 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. At least because of the copy-on-write feature,
                // the pointer is valid only until calling any non-const method
                // or operator on this list, or giving this list as a non-const
                // argument to any call in the world. If you need more stable
                // pointers, please refer to the class Iterator more below.
                // Hint: even methods like Add, Insert and GetSubList may make
                // shallow copies, like the copy operator and copy constructor
                // do.
                // 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 * GetWritable(const OBJ * elem);
                // Get a non-const version of a pointer to an element of this
                // list. The pointer may be used for modifying the element (but
                // not for deleting). The rules for validity of the pointer are
                // the same as with the GetFirst() method, but: The pointer must
                // not be used for modifying after doing something which could
                // have made a shallow copy of this list.
                // Arguments:
                //   elem - A pointer to an element of this list, or NULL.
                // Returns: Pointer for modifying, or NULL if elem is NULL.

        OBJ * GetFirstWritable();
        OBJ * GetLastWritable();
        OBJ * GetNextWritable(const OBJ * elem);
        OBJ * GetPrevWritable(const OBJ * elem);
                // Like GetWritable(GetFirst()) and so on.

        void Set(const OBJ * pos, const OBJ & obj);
                // Replace an element.
                // Arguments:
                //   pos - A pointer to an element of this list.
                //   obj - An object to be copied to the element.

        void InsertAtBeg(const OBJ & obj);
        void InsertAtBeg(const OBJ * elem);
        void InsertAtBeg(const OBJ * first, const OBJ * last);
        void InsertAtBeg(const emList & src);
        void InsertAtBeg(const emList & src, const OBJ * elem);
        void InsertAtBeg(const emList & src, const OBJ * first,
                         const OBJ * last);
        void InsertAtEnd(const OBJ & obj);
        void InsertAtEnd(const OBJ * elem);
        void InsertAtEnd(const OBJ * first, const OBJ * last);
        void InsertAtEnd(const emList & src);
        void InsertAtEnd(const emList & src, const OBJ * elem);
        void InsertAtEnd(const emList & src, const OBJ * first,
                         const OBJ * last);
        void InsertBefore(const OBJ * pos, const OBJ & obj);
        void InsertBefore(const OBJ * pos, const OBJ * elem);
        void InsertBefore(const OBJ * pos, const OBJ * first, const OBJ * last);
        void InsertBefore(const OBJ * pos, const emList & src);
        void InsertBefore(const OBJ * pos, const emList & src,
                          const OBJ * elem);
        void InsertBefore(const OBJ * pos, const emList & src,
                          const OBJ * first, const OBJ * last);
        void InsertAfter(const OBJ * pos, const OBJ & obj);
        void InsertAfter(const OBJ * pos, const OBJ * elem);
        void InsertAfter(const OBJ * pos, const OBJ * first, const OBJ * last);
        void InsertAfter(const OBJ * pos, const emList & src);
        void InsertAfter(const OBJ * pos, const emList & src, const OBJ * elem);
        void InsertAfter(const OBJ * pos, const emList & src, const OBJ * first,
                         const OBJ * last);
                // Insert elements at the beginning or end of this list, or
                // before or after an element of this list. It is even allowed
                // to insert a list into itself.
                // Arguments:
                //   pos   - An element in this list before which or after which
                //           the insertion has to take place. NULL is allowed
                //           here. InsertBefore(NULL,...) means to insert at the
                //           end, and InsertAfter(NULL,...) means to insert at
                //           the beginning.
                //   obj   - An object to be copied for inserting a single
                //           element.
                //   src   - A source list containing the element(s) to be
                //           copied for the insertion. If this argument is not
                //           given, this list itself is the source list.
                //   elem  - An element of the source list. The element is
                //           copied for inserting a single element. If NULL,
                //           nothing is inserted.
                //   first - An element of the source list. It is the first one
                //           of a range of elements to be copied for the
                //           insertion. If NULL, nothing is inserted.
                //   last  - An element of the source list, not before 'first'.
                //           It is the last one of the range of elements to be
                //           copied for the insertion. If NULL, nothing is
                //           inserted.

        void Add(const OBJ & obj);
        void Add(const OBJ * elem);
        void Add(const OBJ * first, const OBJ * last);
        void Add(const emList & src);
        void Add(const emList & src, const OBJ * elem);
        void Add(const emList & src, const OBJ * first, const OBJ * last);
                // Just another name for InsertAtEnd.

        emList & operator += (const emList & list);
        emList & operator += (const OBJ & obj);
        emList operator + (const emList & list) const;
        emList operator + (const OBJ & obj) const;
                // Similar to the Add methods...

        //friend emList operator + (const OBJ & obj, const emList & list);
                // This one even exists and can be used.
                // (Having the declaration here would not be portable)

        void MoveToBeg(const OBJ * elem);
        void MoveToBeg(const OBJ * first, const OBJ * last);
        void MoveToBeg(emList * src);
        void MoveToBeg(emList * src, const OBJ * elem);
        void MoveToBeg(emList * src, const OBJ * first, const OBJ * last);
        void MoveToEnd(const OBJ * elem);
        void MoveToEnd(const OBJ * first, const OBJ * last);
        void MoveToEnd(emList * src);
        void MoveToEnd(emList * src, const OBJ * elem);
        void MoveToEnd(emList * 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, emList * src);
        void MoveBefore(const OBJ * pos, emList * src, const OBJ * elem);
        void MoveBefore(const OBJ * pos, emList * 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, emList * src);
        void MoveAfter(const OBJ * pos, emList * src, const OBJ * elem);
        void MoveAfter(const OBJ * pos, emList * 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.

        emList GetSubListOfFirst() const;
        emList GetSubListOfLast() const;
        emList GetSubList(const OBJ * elem) const;
        emList GetSubList(const OBJ * first, const OBJ * last) const;
                // Like the Extract methods (see below), but the elements are
                // copied instead of removing them from this list.

        emList ExtractFirst();
        emList ExtractLast();
        emList Extract(const OBJ * elem);
        emList Extract(const OBJ * first, const OBJ * last);
                // Like the Remove methods (see below), but return a list of the
                // removed elements, instead of deleting them.

        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(bool compact=false);
                // Remove (and delete) all elements of this list.
                // Arguments:
                //   compact - true if you plan to keep this list empty for
                //             a long time. Otherwise a small block of memory
                //             may possibly not be freed for quick re-use.

        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.

        unsigned int GetDataRefCount() const;
                // Get number of references to the data behind this list.

        void MakeNonShared();
                // This must be called before handing the list to another
                // thread. This method is not recursive. So if the object class
                // even has such a method, you have to call it on every object
                // too.

        class Iterator {

        public:

                // Class for a stable pointer to an element of a list.
                // "stable" means:
                // * If the address of an element changes through the
                //   copy-on-write mechanism, iterators pointing to that element
                //   are adapted proper.
                // * If an element is moved to another list, iterators pointing
                //   to that element keep pointing to that element (and the list
                //   pointers of the iterators are adapted).
                // * If an element is removed or extracted from a list,
                //   iterators pointing to that element are set to the next
                //   element, or NULL if it was the last element.
                // * If the assignment operator '=' is called on a list, all
                //   iterators which were pointing to elements of the list are
                //   set to NULL. This is even true if the list is assigned to
                //   itself.
                // Note the auto-cast operator to a 'const OBJ *'. Wherever
                // there is an argument 'const OBJ *' in the methods of emList,
                // you can even give an instance of this class as the argument.

                Iterator();
                        // Construct a "NULL pointer".

                Iterator(const Iterator & iter);
                        // Construct a copied iterator.

                Iterator(const emList<OBJ> & list, const OBJ * elem);
                        // Construct an iterator pointing to a particular
                        // element.
                        // Arguments:
                        //   list - The list.
                        //   elem - Pointer to an element of the list, or NULL.

                ~Iterator();
                        // Destructor.

                Iterator & operator = (const Iterator & iter);
                        // Copy an iterator.

                operator const OBJ * () const;
                const OBJ * operator * () const;
                const OBJ * operator -> () const;
                const OBJ * Get() const;
                        // Get the element pointer. It is NULL if this iterator
                        // does not point to any element.

                const OBJ * Set(const Iterator & iter);
                        // Copy the given iterator and return the element
                        // pointer.

                const OBJ * Set(const emList<OBJ> & list, const OBJ * elem);
                        // Set this iterator to the given element of the given
                        // list and return the element pointer.

                const OBJ * SetFirst(const emList<OBJ> & list);
                const OBJ * SetLast(const emList<OBJ> & list);
                        // Set this iterator to the first or last element of the
                        // given list and return the element pointer.

                const OBJ * SetNext();
                const OBJ * SetPrev();
                const OBJ * operator ++();
                const OBJ * operator --();
                        // Set this iterator to the next or previous element and
                        // return the new element pointer. This must be called
                        // only if the old element pointer is not NULL.

                const OBJ * operator ++(int);
                const OBJ * operator --(int);
                        // Like above, but return the old element pointer.

                bool operator == (const Iterator & iter) const;
                bool operator != (const Iterator & iter) const;
                bool operator == (const OBJ * elem) const;
                bool operator != (const OBJ * elem) const;
                        // Ordinary compare operators.

                const emList<OBJ> * GetList() const;
                        // Get a pointer to the list this iterator is currently
                        // attached to. Returns NULL if not attached to any
                        // list. (See comments on Detach()).

                void Detach();
                        // Detach this iterator from its list and point to NULL.
                        // Note: to care about the iterators, each emList has a
                        // single linked list of its iterators. The mechanism is
                        // lazy, that means, an iterator may stay in the list
                        // even when not pointing to any element, just for quick
                        // re-use. On the other hand, such iterators are still
                        // costing a tiny number of CPU cycles whenever the list
                        // of elements is modified.

        private:
                friend class emList<OBJ>;
                const OBJ * Pos;
                emList<OBJ> * List;
                Iterator * NextIter; // Undefined if List==NULL
        };

private:
        friend class Iterator;

        struct Element {
                OBJ Obj;
                OBJ * Next;
                OBJ * Prev;
                inline Element(const OBJ & obj) : Obj(obj) {}
        };
        struct SharedData {
                OBJ * First;
                OBJ * Last;
                bool IsStaticEmpty;
                unsigned int RefCount;
        };

        SharedData * Data;
        Iterator * Iterators;
        static SharedData EmptyData;

        inline emList(SharedData * d) { Data=d; Iterators=NULL; }
        void MakeWritable();
        void MakeWritable(const OBJ * * preserve);
        void MakeWritable(const OBJ * * preserve1, const OBJ * * preserve2);
        void MakeWritable(const OBJ * * preserve1, const OBJ * * preserve2,
                          const OBJ * * preserve3);
        void DeleteData();
};


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

#define EM_LSTIMP_ELEM(objPtr) \
        ((Element*)(((char*)(objPtr))-offsetof(Element,Obj)))
#define EM_LSTIMP_PREV(objPtr) EM_LSTIMP_ELEM(objPtr)->Prev
#define EM_LSTIMP_NEXT(objPtr) EM_LSTIMP_ELEM(objPtr)->Next

template <class OBJ> inline emList<OBJ>::emList()
{
        Iterators=NULL;
        Data=&EmptyData;
}

template <class OBJ> inline emList<OBJ>::emList(const emList & src)
{
        Iterators=NULL;
        Data=src.Data;
        Data->RefCount++;
}

template <class OBJ> emList<OBJ>::emList(const OBJ & obj)
{
        Iterators=NULL;
        Data=&EmptyData;
        InsertBefore(NULL,obj);
}

template <class OBJ> emList<OBJ>::emList(
        const emList & src1, const emList & src2
)
{
        Iterators=NULL;
        Data=src1.Data;
        Data->RefCount++;
        InsertBefore(NULL,src2,src2.Data->First,src2.Data->Last);
}

template <class OBJ> emList<OBJ>::emList(
        const emList & src1, const OBJ & src2
)
{
        Iterators=NULL;
        Data=src1.Data;
        Data->RefCount++;
        InsertBefore(NULL,src2);
}

template <class OBJ> emList<OBJ>::emList(
        const OBJ & src1, const emList & src2
)
{
        Iterators=NULL;
        Data=src2.Data;
        Data->RefCount++;
        InsertAfter(NULL,src1);
}

template <class OBJ> emList<OBJ>::emList(
        const emList & src, const OBJ * first, const OBJ * last
)
{
        Iterators=NULL;
        Data=&EmptyData;
        InsertBefore(NULL,src,first,last);
}

template <class OBJ> emList<OBJ>::~emList()
{
        Iterator * i;

        for (i=Iterators; i; i=i->NextIter) { i->Pos=NULL; i->List=NULL; }
        if (!--Data->RefCount) DeleteData();
}

template <class OBJ> emList<OBJ> & emList<OBJ>::operator = (
        const emList & list
)
{
        Iterator * i;

        for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
        list.Data->RefCount++;
        if (!--Data->RefCount) DeleteData();
        Data=list.Data;
        return *this;
}

template <class OBJ> emList<OBJ> & emList<OBJ>::operator = (const OBJ & obj)
{
        Iterator * i;

        for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
        if (Data->RefCount>1) {
                Data->RefCount--;
                Data=&EmptyData;
        }
        InsertBefore(NULL,obj);
        if (EM_LSTIMP_PREV(Data->Last)) {
                Remove(Data->First,EM_LSTIMP_PREV(Data->Last));
        }
        return *this;
}

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

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

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

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

template <class OBJ> inline OBJ * emList<OBJ>::GetWritable(const OBJ * elem)
{
        if (Data->RefCount>1) MakeWritable(&elem);
        return (OBJ*)elem;
}

template <class OBJ> inline OBJ * emList<OBJ>::GetFirstWritable()
{
        if (Data->RefCount>1) MakeWritable();
        return Data->First;
}

template <class OBJ> inline OBJ * emList<OBJ>::GetLastWritable()
{
        if (Data->RefCount>1) MakeWritable();
        return Data->Last;
}

template <class OBJ> inline OBJ * emList<OBJ>::GetNextWritable(
        const OBJ * elem
)
{
        if (Data->RefCount>1) MakeWritable(&elem);
        return EM_LSTIMP_NEXT(elem);
}

template <class OBJ> inline OBJ * emList<OBJ>::GetPrevWritable(
        const OBJ * elem
)
{
        if (Data->RefCount>1) MakeWritable(&elem);
        return EM_LSTIMP_NEXT(elem);
}

template <class OBJ> inline void emList<OBJ>::Set(
        const OBJ * pos, const OBJ & obj
)
{
        if (Data->RefCount>1) MakeWritable(&pos);
        *((OBJ*)pos)=obj;
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(const OBJ & obj)
{
        InsertAfter(NULL,obj);
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(const OBJ * elem)
{
        InsertAfter(NULL,*this,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(
        const OBJ * first, const OBJ * last
)
{
        InsertAfter(NULL,*this,first,last);
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(
        const emList & src
)
{
        InsertAfter(NULL,src,src.Data->First,src.Data->Last);
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(
        const emList & src, const OBJ * elem
)
{
        InsertAfter(NULL,src,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::InsertAtBeg(
        const emList & src, const OBJ * first, const OBJ * last
)
{
        InsertAfter(NULL,src,first,last);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(const OBJ & obj)
{
        InsertBefore(NULL,obj);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(const OBJ * elem)
{
        InsertBefore(NULL,*this,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(
        const OBJ * first, const OBJ * last
)
{
        InsertBefore(NULL,*this,first,last);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(const emList & src)
{
        InsertBefore(NULL,src,src.Data->First,src.Data->Last);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(
        const emList & src, const OBJ * elem
)
{
        InsertBefore(NULL,src,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::InsertAtEnd(
        const emList & src, const OBJ * first, const OBJ * last
)
{
        InsertBefore(NULL,src,first,last);
}

template <class OBJ> void emList<OBJ>::InsertBefore(
        const OBJ * pos, const OBJ & obj
)
{
        OBJ * e;

        if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos);
        e=&(new Element(obj))->Obj;
        if ((EM_LSTIMP_NEXT(e)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_PREV(e)=Data->Last)==NULL) Data->First=e;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                Data->Last=e;
        }
        else {
                if ((EM_LSTIMP_PREV(e)=EM_LSTIMP_PREV(pos))==NULL) Data->First=e;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                EM_LSTIMP_PREV(pos)=e;
        }
}

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

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

template <class OBJ> inline void emList<OBJ>::InsertBefore(
        const OBJ * pos, const emList & src
)
{
        InsertBefore(pos,src,src.Data->First,src.Data->Last);
}

template <class OBJ> inline void emList<OBJ>::InsertBefore(
        const OBJ * pos, const emList & src, const OBJ * elem
)
{
        InsertBefore(pos,src,elem,elem);
}

template <class OBJ> void emList<OBJ>::InsertBefore(
        const OBJ * pos, const emList & src, const OBJ * first,
        const OBJ * last
)
{
        OBJ * p, * e;

        if (!first || !last) return;
        if (!Data->First && first==src.Data->First && last==src.Data->Last) {
                src.Data->RefCount++;
                if (!--Data->RefCount) DeleteData();
                Data=src.Data;
                return;
        }
        if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos,&first,&last);
        p=(OBJ*)pos;
        for (;;) {
                e=&(new Element(*last))->Obj;
                if ((EM_LSTIMP_NEXT(e)=p)==NULL) {
                        if ((EM_LSTIMP_PREV(e)=Data->Last)==NULL) Data->First=e;
                        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                        Data->Last=e;
                }
                else {
                        if ((EM_LSTIMP_PREV(e)=EM_LSTIMP_PREV(p))==NULL) Data->First=e;
                        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
                        EM_LSTIMP_PREV(p)=e;
                }
                if (last==first) break;
                p=e;
                if (last==pos) last=p;
                last=EM_LSTIMP_PREV(last);
        }
}

template <class OBJ> void emList<OBJ>::InsertAfter(
        const OBJ * pos, const OBJ & obj
)
{
        OBJ * e;

        if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos);
        e=&(new Element(obj))->Obj;
        if ((EM_LSTIMP_PREV(e)=(OBJ*)pos)==NULL) {
                if ((EM_LSTIMP_NEXT(e)=Data->First)==NULL) Data->Last=e;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                Data->First=e;
        }
        else {
                if ((EM_LSTIMP_NEXT(e)=EM_LSTIMP_NEXT(pos))==NULL) Data->Last=e;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                EM_LSTIMP_NEXT(pos)=e;
        }
}

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

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

template <class OBJ> inline void emList<OBJ>::InsertAfter(
        const OBJ * pos, const emList & src
)
{
        InsertAfter(pos,src,src.Data->First,src.Data->Last);
}

template <class OBJ> inline void emList<OBJ>::InsertAfter(
        const OBJ * pos, const emList & src, const OBJ * elem
)
{
        InsertAfter(pos,src,elem,elem);
}

template <class OBJ> void emList<OBJ>::InsertAfter(
        const OBJ * pos, const emList & src, const OBJ * first,
        const OBJ * last
)
{
        OBJ * p, * e;

        if (!first || !last) return;
        if (!Data->First && first==src.Data->First && last==src.Data->Last) {
                src.Data->RefCount++;
                if (!--Data->RefCount) DeleteData();
                Data=src.Data;
                return;
        }
        if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos,&first,&last);
        p=(OBJ*)pos;
        for (;;) {
                e=&(new Element(*first))->Obj;
                if ((EM_LSTIMP_PREV(e)=p)==NULL) {
                        if ((EM_LSTIMP_NEXT(e)=Data->First)==NULL) Data->Last=e;
                        else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                        Data->First=e;
                }
                else {
                        if ((EM_LSTIMP_NEXT(e)=EM_LSTIMP_NEXT(p))==NULL) Data->Last=e;
                        else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
                        EM_LSTIMP_NEXT(p)=e;
                }
                if (first==last) break;
                p=e;
                if (first==pos) first=p;
                first=EM_LSTIMP_NEXT(first);
        }
}

template <class OBJ> inline void emList<OBJ>::Add(const OBJ & obj)
{
        InsertBefore(NULL,obj);
}

template <class OBJ> inline void emList<OBJ>::Add(const OBJ * elem)
{
        InsertBefore(NULL,*this,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::Add(
        const OBJ * first, const OBJ * last
)
{
        InsertBefore(NULL,*this,first,last);
}

template <class OBJ> inline void emList<OBJ>::Add(const emList & src)
{
        InsertBefore(NULL,src,src.Data->First,src.Data->Last);
}

template <class OBJ> inline void emList<OBJ>::Add(
        const emList & src, const OBJ * elem
)
{
        InsertBefore(NULL,src,elem,elem);
}

template <class OBJ> inline void emList<OBJ>::Add(
        const emList & src, const OBJ * first, const OBJ * last
)
{
        InsertBefore(NULL,src,first,last);
}

template <class OBJ> inline emList<OBJ> & emList<OBJ>::operator += (
        const emList & list
)
{
        InsertBefore(NULL,list,list.Data->First,list.Data->Last);
        return *this;
}

template <class OBJ> inline emList<OBJ> & emList<OBJ>::operator += (
        const OBJ & obj
)
{
        InsertBefore(NULL,obj);
        return *this;
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::operator + (
        const emList & list
) const
{
        return emList<OBJ>(*this,list);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::operator + (
        const OBJ & obj
) const
{
        return emList<OBJ>(*this,obj);
}

template <class OBJ> inline emList<OBJ> operator + (
        const OBJ & obj, const emList<OBJ> & list
)
{
        return emList<OBJ>(obj,list);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template <class OBJ> void emList<OBJ>::MoveBefore(
        const OBJ * pos, emList * src, const OBJ * first, const OBJ * last
)
{
        Iterator * * pi;
        Iterator * i;
        const OBJ * e;

        if (!first || !last) return;
        if (!src) src=this;
        if (src!=this) {
                if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos);
                if (src->Data->RefCount>1) src->MakeWritable(&first,&last);
                for (pi=&src->Iterators, i=*pi; i; i=*pi) {
                        if (i->Pos!=last) {
                                if (!i->Pos) { pi=&i->NextIter; continue; }
                                for (e=first; i->Pos!=e && e!=last; e=EM_LSTIMP_NEXT(e));
                                if (e==last) { pi=&i->NextIter; continue; }
                        }
                        *pi=i->NextIter;
                        i->List=this;
                        i->NextIter=Iterators;
                        Iterators=i;
                }
        }
        else if (Data->RefCount>1) {
                if (EM_LSTIMP_NEXT(last)==pos) return;
                MakeWritable(&pos,&first,&last);
        }
        if (!EM_LSTIMP_PREV(first)) src->Data->First=EM_LSTIMP_NEXT(last);
        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
        if (!EM_LSTIMP_NEXT(last)) src->Data->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)=Data->Last)==NULL) Data->First=(OBJ*)first;
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
                Data->Last=(OBJ*)last;
        }
        else {
                if ((EM_LSTIMP_PREV(first)=EM_LSTIMP_PREV(pos))==NULL) {
                        Data->First=(OBJ*)first;
                }
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
                EM_LSTIMP_PREV(pos)=(OBJ*)last;
        }
}

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

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

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

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

template <class OBJ> void emList<OBJ>::MoveAfter(
        const OBJ * pos, emList * src, const OBJ * first, const OBJ * last
)
{
        Iterator * * pi;
        Iterator * i;
        const OBJ * e;

        if (!first || !last) return;
        if (!src) src=this;
        if (src!=this) {
                if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable(&pos);
                if (src->Data->RefCount>1) src->MakeWritable(&first,&last);
                for (pi=&src->Iterators, i=*pi; i; i=*pi) {
                        if (i->Pos!=last) {
                                if (!i->Pos) { pi=&i->NextIter; continue; }
                                for (e=first; i->Pos!=e && e!=last; e=EM_LSTIMP_NEXT(e));
                                if (e==last) { pi=&i->NextIter; continue; }
                        }
                        *pi=i->NextIter;
                        i->List=this;
                        i->NextIter=Iterators;
                        Iterators=i;
                }
        }
        else if (Data->RefCount>1) {
                if (EM_LSTIMP_PREV(first)==pos) return;
                MakeWritable(&pos,&first,&last);
        }
        if (!EM_LSTIMP_PREV(first)) src->Data->First=EM_LSTIMP_NEXT(last);
        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
        if (!EM_LSTIMP_NEXT(last)) src->Data->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)=Data->First)==NULL) Data->Last=(OBJ*)last;
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
                Data->First=(OBJ*)first;
        }
        else {
                if ((EM_LSTIMP_NEXT(last)=EM_LSTIMP_NEXT(pos))==NULL) {
                        Data->Last=(OBJ*)last;
                }
                else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
                EM_LSTIMP_NEXT(pos)=(OBJ*)first;
        }
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::GetSubListOfFirst() const
{
        return emList<OBJ>(*this,Data->First,Data->First);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::GetSubListOfLast() const
{
        return emList<OBJ>(*this,Data->Last,Data->Last);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::GetSubList(
        const OBJ * elem
) const
{
        return emList<OBJ>(*this,elem,elem);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::GetSubList(
        const OBJ * first, const OBJ * last
) const
{
        return emList<OBJ>(*this,first,last);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::ExtractFirst()
{
        return Extract(Data->First,Data->First);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::ExtractLast()
{
        return Extract(Data->Last,Data->Last);
}

template <class OBJ> inline emList<OBJ> emList<OBJ>::Extract(const OBJ * elem)
{
        return Extract(elem,elem);
}

template <class OBJ> emList<OBJ> emList<OBJ>::Extract(
        const OBJ * first, const OBJ * last
)
{
        SharedData * d;
        const OBJ * e;
        Iterator * i;

        if (!first || !last) {
                d=&EmptyData;
        }
        else if (first==Data->First && last==Data->Last) {
                for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
                d=Data;
                Data=&EmptyData;
        }
        else {
                if (Data->RefCount>1) MakeWritable(&first,&last);
                for (i=Iterators; i; i=i->NextIter) {
                        if (i->Pos!=last) {
                                if (!i->Pos) continue;
                                for (e=first; i->Pos!=e && e!=last; e=EM_LSTIMP_NEXT(e));
                                if (e==last) continue;
                        }
                        i->Pos=EM_LSTIMP_NEXT(last);
                }
                if (!EM_LSTIMP_PREV(first)) {
                        Data->First=EM_LSTIMP_NEXT(last);
                }
                else {
                        EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
                        EM_LSTIMP_PREV(first)=NULL;
                }
                if (!EM_LSTIMP_NEXT(last)) {
                        Data->Last=EM_LSTIMP_PREV(first);
                }
                else {
                        EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
                        EM_LSTIMP_NEXT(last)=NULL;
                }
                d=new SharedData;
                d->First=(OBJ*)first;
                d->Last=(OBJ*)last;
                d->IsStaticEmpty=false;
                d->RefCount=1;
        }
        return emList<OBJ>(d);
}

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

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

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

template <class OBJ> void emList<OBJ>::Remove(
        const OBJ * first, const OBJ * last
)
{
        const OBJ * e;
        OBJ * e2;
        Iterator * i;
        SharedData * d;

        if (!first || !last) return;
        if (first==Data->First && last==Data->Last) {
                for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
                if (Data->RefCount>1) {
                        Data->RefCount--;
                        Data=&EmptyData;
                        return;
                }
        }
        else {
                for (i=Iterators; i; i=i->NextIter) {
                        if (i->Pos!=last) {
                                if (!i->Pos) continue;
                                for (e=first; i->Pos!=e && e!=last; e=EM_LSTIMP_NEXT(e));
                                if (e==last) continue;
                        }
                        i->Pos=EM_LSTIMP_NEXT(last);
                }
        }
        if (Data->RefCount==1) {
                if (!EM_LSTIMP_PREV(first)) Data->First=EM_LSTIMP_NEXT(last);
                else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
                if (!EM_LSTIMP_NEXT(last)) Data->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);
        }
        else {
                d=new SharedData;
                d->First=NULL;
                d->Last=NULL;
                d->IsStaticEmpty=false;
                d->RefCount=1;
                for (e=Data->First; e; e=EM_LSTIMP_NEXT(e)) {
                        if (e==first) {
                                e=EM_LSTIMP_NEXT(last);
                                if (!e) break;
                        }
                        e2=&(new Element(*e))->Obj;
                        EM_LSTIMP_NEXT(e2)=NULL;
                        if ((EM_LSTIMP_PREV(e2)=d->Last)==NULL) d->First=e2;
                        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e2))=e2;
                        d->Last=e2;
                        for (i=Iterators; i; i=i->NextIter) {
                                if (i->Pos==e) i->Pos=e2;
                        }
                }
                Data->RefCount--;
                Data=d;
        }
}

template <class OBJ> void emList<OBJ>::Clear(bool compact)
{
        OBJ * e1, * e2;
        Iterator * i;

        for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
        if (Data->RefCount>1 || compact) {
                if (!--Data->RefCount) DeleteData();
                Data=&EmptyData;
        }
        else {
                for (e1=Data->First; e1; e1=e2) {
                        e2=EM_LSTIMP_NEXT(e1);
                        delete EM_LSTIMP_ELEM(e1);
                }
                Data->First=NULL;
                Data->Last=NULL;
        }
}

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

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

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

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

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

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

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

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

template <class OBJ> unsigned int emList<OBJ>::GetDataRefCount() const
{
        return Data->IsStaticEmpty ? UINT_MAX/2 : Data->RefCount;
}

template <class OBJ> inline void emList<OBJ>::MakeNonShared()
{
        MakeWritable();
}

template <class OBJ> inline emList<OBJ>::Iterator::Iterator()
{
        Pos=NULL;
        List=NULL;
}

template <class OBJ> emList<OBJ>::Iterator::Iterator(
        const typename emList<OBJ>::Iterator & iter
)
{
        Pos=iter.Pos;
        if ((List=iter.List)!=NULL) {
                NextIter=List->Iterators;
                List->Iterators=this;
        }
}

template <class OBJ> emList<OBJ>::Iterator::Iterator(
        const emList<OBJ> & list, const OBJ * elem
)
{
        Pos=elem;
        if ((List=(emList<OBJ>*)&list)!=NULL) {
                NextIter=List->Iterators;
                List->Iterators=this;
        }
}

template <class OBJ> emList<OBJ>::Iterator::~Iterator()
{
        Iterator * * pi;

        if (List) {
                for (pi=&List->Iterators; *pi!=this; pi=&(*pi)->NextIter);
                *pi=NextIter;
        }
}

template <class OBJ> inline typename emList<OBJ>::Iterator &
        emList<OBJ>::Iterator::operator = (const Iterator & iter)
{
        Set(iter);
        return *this;
}

template <class OBJ> inline
        emList<OBJ>::Iterator::operator const OBJ * () const
{
        return Pos;
}

template <class OBJ> inline
        const OBJ * emList<OBJ>::Iterator::operator * () const
{
        return Pos;
}

template <class OBJ> inline
        const OBJ * emList<OBJ>::Iterator::operator -> () const
{
        return Pos;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::Get() const
{
        return Pos;
}

template <class OBJ> const OBJ * emList<OBJ>::Iterator::Set(
        const Iterator & iter
)
{
        Iterator * * pi;

        if (List!=iter.List) {
                if (List) {
                        for (pi=&List->Iterators; *pi!=this; pi=&(*pi)->NextIter);
                        *pi=NextIter;
                }
                if ((List=iter.List)!=NULL) {
                        NextIter=List->Iterators;
                        List->Iterators=this;
                }
        }
        Pos=iter.Pos;
        return Pos;
}

template <class OBJ> const OBJ * emList<OBJ>::Iterator::Set(
        const emList<OBJ> & list, const OBJ * elem
)
{
        Iterator * * pi;

        if (List!=&list) {
                if (List) {
                        for (pi=&List->Iterators; *pi!=this; pi=&(*pi)->NextIter);
                        *pi=NextIter;
                }
                List=(emList<OBJ>*)&list;
                NextIter=List->Iterators;
                List->Iterators=this;
        }
        Pos=elem;
        return elem;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::SetFirst(
        const emList<OBJ> & list
)
{
        return Set(list,list.Data->First);
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::SetLast(
        const emList<OBJ> & list
)
{
        return Set(list,list.Data->Last);
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::SetNext()
{
        Pos=EM_LSTIMP_NEXT(Pos);
        return Pos;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::SetPrev()
{
        Pos=EM_LSTIMP_PREV(Pos);
        return Pos;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::operator ++()
{
        Pos=EM_LSTIMP_NEXT(Pos);
        return Pos;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::operator --()
{
        Pos=EM_LSTIMP_PREV(Pos);
        return Pos;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::operator ++(int)
{
        const OBJ * res=Pos;
        Pos=EM_LSTIMP_NEXT(Pos);
        return res;
}

template <class OBJ> inline const OBJ * emList<OBJ>::Iterator::operator --(int)
{
        const OBJ * res=Pos;
        Pos=EM_LSTIMP_PREV(Pos);
        return res;
}

template <class OBJ> inline bool emList<OBJ>::Iterator::operator == (
        const Iterator & iter
) const
{
        return Pos==iter.Pos;
}

template <class OBJ> inline bool emList<OBJ>::Iterator::operator != (
        const Iterator & iter
) const
{
        return Pos!=iter.Pos;
}

template <class OBJ> inline bool emList<OBJ>::Iterator::operator == (
        const OBJ * elem
) const
{
        return Pos==elem;
}

template <class OBJ> inline bool emList<OBJ>::Iterator::operator != (
        const OBJ * elem
) const
{
        return Pos!=elem;
}

template <class OBJ> inline
        const emList<OBJ> * emList<OBJ>::Iterator::GetList() const
{
        return List;
}

template <class OBJ> void emList<OBJ>::Iterator::Detach()
{
        Iterator * * pi;

        if (List) {
                for (pi=&List->Iterators; *pi!=this; pi=&(*pi)->NextIter);
                *pi=NextIter;
                List=NULL;
                Pos=NULL;
        }
}

template <class OBJ> typename emList<OBJ>::SharedData emList<OBJ>::EmptyData=
{
        NULL,NULL,true,UINT_MAX/2
};

template <class OBJ> void emList<OBJ>::MakeWritable()
{
        const OBJ * p1, * p2, * p3;

        p1=NULL; p2=NULL; p3=NULL;
        MakeWritable(&p1,&p2,&p3);
}

template <class OBJ> void emList<OBJ>::MakeWritable(const OBJ * * preserve)
{
        const OBJ * p2, * p3;

        p2=NULL; p3=NULL;
        MakeWritable(preserve,&p2,&p3);
}

template <class OBJ> void emList<OBJ>::MakeWritable(
        const OBJ * * preserve1, const OBJ * * preserve2
)
{
        const OBJ * p3;

        p3=NULL;
        MakeWritable(preserve1,preserve2,&p3);
}

template <class OBJ> void emList<OBJ>::MakeWritable(
        const OBJ * * preserve1, const OBJ * * preserve2,
        const OBJ * * preserve3
)
{
        SharedData * d1, * d2;
        OBJ * e1, * e2;
        Iterator * i;

        d1=Data;
        if (d1->RefCount>1 || Data->IsStaticEmpty) {
                d2=new SharedData;
                d2->First=NULL;
                d2->Last=NULL;
                d2->IsStaticEmpty=false;
                d2->RefCount=1;
                d1->RefCount--;
                Data=d2;
                for (e1=d1->First; e1; e1=EM_LSTIMP_NEXT(e1)) {
                        e2=&(new Element(*e1))->Obj;
                        EM_LSTIMP_NEXT(e2)=NULL;
                        if ((EM_LSTIMP_PREV(e2)=d2->Last)==NULL) d2->First=e2;
                        else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e2))=e2;
                        d2->Last=e2;
                        for (i=Iterators; i; i=i->NextIter) {
                                if (i->Pos==e1) i->Pos=e2;
                        }
                        if (*preserve1==e1) *preserve1=e2;
                        if (*preserve2==e1) *preserve2=e2;
                        if (*preserve3==e1) *preserve3=e2;
                }
        }
}

template <class OBJ> void emList<OBJ>::DeleteData()
{
        OBJ * e, * n;

        EmptyData.RefCount=UINT_MAX/2;

        // Never do a
        //  if (Data!=&EmptyData)...
        // instead of
        //  if (!Data->IsStaticEmpty)...
        // because static member variables of template classes could exist
        // multiple times for the same final type (e.g. with Windows DLLs).
        if (!Data->IsStaticEmpty) {
                for (e=Data->First; e; e=n) {
                        n=EM_LSTIMP_NEXT(e);
                        delete EM_LSTIMP_ELEM(e);
                }
                delete Data;
        }
}


#endif