xref: /dports/x11/eaglemode/eaglemode-0.95.0/include/emCore/emList.h

//------------------------------------------------------------------------------
// 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