//------------------------------------------------------------------------------
// emUcList.h
//
// Copyright (C) 2024 Oliver Hamann.
//
// Homepage: http://eaglemode.sourceforge.net/
//
// This program is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License version 3 as published by the
// Free Software Foundation.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU General Public License version 3 for
// more details.
//
// You should have received a copy of the GNU General Public License version 3
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//------------------------------------------------------------------------------
#ifndef emUcList_h
#define emUcList_h
#ifndef emList_h
#include <emCore/emList.h>
#endif
//==============================================================================
//================================== emUcList ==================================
//==============================================================================
template <class OBJ> class emUcList : public emUncopyable {
public:
// Template class for a double-linked NULL-terminated uncopyable list.
// This is similar to emList, but the list cannot be copied, and so the
// elements do not have to be copyable.
emUcList();
// Construct an empty list.
~emUcList();
// Destructor.
const OBJ * GetFirst() const;
OBJ * GetFirst();
const OBJ * GetLast() const;
OBJ * GetLast();
const OBJ * GetNext(const OBJ * elem) const;
OBJ * GetNext(const OBJ * elem);
const OBJ * GetPrev(const OBJ * elem) const;
OBJ * GetPrev(const OBJ * elem);
// Get a pointer to the first or last element of this list, or
// get a pointer to the next or previous element of an element
// of this list.
// Arguments:
// elem - A pointer to an element in this list, must never be
// NULL.
// Returns:
// A pointer to the requested element in this list, or NULL if
// there is no such element.
OBJ * InsertNewAtBeg();
OBJ * InsertNewAtEnd();
OBJ * InsertNewBefore(const OBJ * pos);
OBJ * InsertNewAfter(const OBJ * pos);
// Insert a new element at the beginning or end of this list, or
// before or after an element of this list.
// Arguments:
// pos - An element in this list before which or after which
// the insertion has to take place. NULL is allowed
// here. InsertNewBefore(NULL) means to insert at the
// end, and InsertNewAfter(NULL) means to insert at
// the beginning.
OBJ * AddNew();
// Just another name for InsertNewAtEnd.
void MoveToBeg(const OBJ * elem);
void MoveToBeg(const OBJ * first, const OBJ * last);
void MoveToBeg(emUcList * src);
void MoveToBeg(emUcList * src, const OBJ * elem);
void MoveToBeg(emUcList * src, const OBJ * first, const OBJ * last);
void MoveToEnd(const OBJ * elem);
void MoveToEnd(const OBJ * first, const OBJ * last);
void MoveToEnd(emUcList * src);
void MoveToEnd(emUcList * src, const OBJ * elem);
void MoveToEnd(emUcList * src, const OBJ * first, const OBJ * last);
void MoveBefore(const OBJ * pos, const OBJ * elem);
void MoveBefore(const OBJ * pos, const OBJ * first, const OBJ * last);
void MoveBefore(const OBJ * pos, emUcList * src);
void MoveBefore(const OBJ * pos, emUcList * src, const OBJ * elem);
void MoveBefore(const OBJ * pos, emUcList * src, const OBJ * first,
const OBJ * last);
void MoveAfter(const OBJ * pos, const OBJ * elem);
void MoveAfter(const OBJ * pos, const OBJ * first, const OBJ * last);
void MoveAfter(const OBJ * pos, emUcList * src);
void MoveAfter(const OBJ * pos, emUcList * src, const OBJ * elem);
void MoveAfter(const OBJ * pos, emUcList * src, const OBJ * first,
const OBJ * last);
// Move elements from a source list to the beginning or end of
// this list, or before or after an element of this list.
// Arguments:
// pos - An element in this list before which or after which
// the elements are to be moved. It must not be a
// member of the moved elements! NULL is allowed here.
// MoveBefore(NULL,...) means to move to the end, and
// MoveAfter(NULL,...) means to move to the beginning.
// src - Pointer to the source list. If NULL or not given,
// this list itself is the source list.
// elem - An element of the source list, which shall be
// moved. If NULL, nothing is moved.
// first - An element of the source list. It is the first one
// of a range of elements to be moved. If NULL,
// nothing is moved.
// last - An element of the source list, not before 'first'.
// It is the last one of the range of elements to be
// moved. If NULL, nothing is moved.
void RemoveFirst();
void RemoveLast();
void Remove(const OBJ * elem);
void Remove(const OBJ * first, const OBJ * last);
// Remove (and delete) the first element, the last element, a
// given element or a range of elements from this list.
// Arguments:
// elem - An element of this list, which shall be removed.
// If NULL, nothing is removed.
// first - An element of this list. It is the first one of a
// range of elements to be removed. If NULL, nothing
// is removed.
// last - An element of this list, not before 'first'. It is
// the last one of the range of elements to be
// removed. If NULL, nothing is removed.
void Clear();
// Remove (and delete) all elements of this list.
bool IsEmpty() const;
// Ask whether this list has no elements.
bool Sort(
int(*compare)(const OBJ * obj1, const OBJ * obj2,
void * context),
void * context=NULL
);
// Sort this list. The order of equal elements is preserved.
// Arguments:
// compare - Function for comparing two elements. If you want
// the elements to be compared via the operators '<'
// and '>', say:
// emStdComparer<OBJ>::Compare
// with OBJ replaced by the real type of the
// elements. The context argument is ignored then.
// Arguments:
// obj1 - Pointer to first element.
// obj2 - Pointer to second element.
// context - See below.
// Returns: Zero if the elements are equal, a value
// greater than zero if the first element is
// greater than the second one, and a value less
// than zero if the first element is less than the
// second one.
// context - Any pointer to be forwarded to the compare
// function.
// Returns: Whether there was a change.
int GetCount() const;
// Compute the number of elements.
const OBJ * GetAtIndex(int index) const;
// Search the element at the given index. Returns NULL if the
// index is out of range. The rules for the validity of the
// pointer are the same as with the GetFirst() method.
int GetIndexOf(const OBJ * elem) const;
// Search the given element and return its index. Returns -1
// if it is not an element of this list.
private:
struct Element {
OBJ Obj;
OBJ * Next;
OBJ * Prev;
};
OBJ * First;
OBJ * Last;
};
//==============================================================================
//============================== Implementations ===============================
//==============================================================================
template <class OBJ> inline emUcList<OBJ>::emUcList()
: First(NULL),
Last(NULL)
{
}
template <class OBJ> emUcList<OBJ>::~emUcList()
{
Clear();
}
template <class OBJ> inline const OBJ * emUcList<OBJ>::GetFirst() const
{
return First;
}
template <class OBJ> inline OBJ * emUcList<OBJ>::GetFirst()
{
return First;
}
template <class OBJ> inline const OBJ * emUcList<OBJ>::GetLast() const
{
return Last;
}
template <class OBJ> inline OBJ * emUcList<OBJ>::GetLast()
{
return Last;
}
template <class OBJ> inline const OBJ * emUcList<OBJ>::GetNext(
const OBJ * elem
) const
{
return EM_LSTIMP_NEXT(elem);
}
template <class OBJ> inline OBJ * emUcList<OBJ>::GetNext(const OBJ * elem)
{
return EM_LSTIMP_NEXT(elem);
}
template <class OBJ> inline const OBJ * emUcList<OBJ>::GetPrev(
const OBJ * elem
) const
{
return EM_LSTIMP_PREV(elem);
}
template <class OBJ> inline OBJ * emUcList<OBJ>::GetPrev(const OBJ * elem)
{
return EM_LSTIMP_PREV(elem);
}
template <class OBJ> inline OBJ * emUcList<OBJ>::InsertNewAtBeg()
{
return InsertNewAfter(NULL);
}
template <class OBJ> inline OBJ * emUcList<OBJ>::InsertNewAtEnd()
{
return InsertNewBefore(NULL);
}
template <class OBJ> OBJ * emUcList<OBJ>::InsertNewBefore(const OBJ * pos)
{
OBJ * e;
e=&(new Element())->Obj;
if ((EM_LSTIMP_NEXT(e)=(OBJ*)pos)==NULL) {
if ((EM_LSTIMP_PREV(e)=Last)==NULL) First=e;
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
Last=e;
}
else {
if ((EM_LSTIMP_PREV(e)=EM_LSTIMP_PREV(pos))==NULL) First=e;
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(e))=e;
EM_LSTIMP_PREV(pos)=e;
}
return e;
}
template <class OBJ> OBJ * emUcList<OBJ>::InsertNewAfter(const OBJ * pos)
{
OBJ * e;
e=&(new Element())->Obj;
if ((EM_LSTIMP_PREV(e)=(OBJ*)pos)==NULL) {
if ((EM_LSTIMP_NEXT(e)=First)==NULL) Last=e;
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
First=e;
}
else {
if ((EM_LSTIMP_NEXT(e)=EM_LSTIMP_NEXT(pos))==NULL) Last=e;
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(e))=e;
EM_LSTIMP_NEXT(pos)=e;
}
return e;
}
template <class OBJ> inline OBJ * emUcList<OBJ>::AddNew()
{
return InsertNewBefore(NULL);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(const OBJ * elem)
{
MoveAfter(NULL,this,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
const OBJ * first, const OBJ * last
)
{
MoveAfter(NULL,this,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(emUcList * src)
{
if (src) MoveAfter(NULL,src,src->First,src->Last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
emUcList * src, const OBJ * elem
)
{
MoveAfter(NULL,src,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToBeg(
emUcList * src, const OBJ * first, const OBJ * last
)
{
MoveAfter(NULL,src,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(const OBJ * elem)
{
MoveBefore(NULL,this,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
const OBJ * first, const OBJ * last
)
{
MoveBefore(NULL,this,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(emUcList * src)
{
if (src) MoveBefore(NULL,src,src->First,src->Last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
emUcList * src, const OBJ * elem
)
{
MoveBefore(NULL,src,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveToEnd(
emUcList * src, const OBJ * first, const OBJ * last
)
{
MoveBefore(NULL,src,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
const OBJ * pos, const OBJ * elem
)
{
MoveBefore(pos,this,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
const OBJ * pos, const OBJ * first, const OBJ * last
)
{
MoveBefore(pos,this,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
const OBJ * pos, emUcList * src
)
{
if (src) MoveBefore(pos,src,src->First,src->Last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveBefore(
const OBJ * pos, emUcList * src, const OBJ * elem
)
{
MoveBefore(pos,src,elem,elem);
}
template <class OBJ> void emUcList<OBJ>::MoveBefore(
const OBJ * pos, emUcList * src, const OBJ * first, const OBJ * last
)
{
if (!first || !last) return;
if (!src) src=this;
if (!EM_LSTIMP_PREV(first)) src->First=EM_LSTIMP_NEXT(last);
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
if (!EM_LSTIMP_NEXT(last)) src->Last=EM_LSTIMP_PREV(first);
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
if ((EM_LSTIMP_NEXT(last)=(OBJ*)pos)==NULL) {
if ((EM_LSTIMP_PREV(first)=Last)==NULL) First=(OBJ*)first;
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
Last=(OBJ*)last;
}
else {
if ((EM_LSTIMP_PREV(first)=EM_LSTIMP_PREV(pos))==NULL) {
First=(OBJ*)first;
}
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=(OBJ*)first;
EM_LSTIMP_PREV(pos)=(OBJ*)last;
}
}
template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
const OBJ * pos, const OBJ * elem
)
{
MoveAfter(pos,this,elem,elem);
}
template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
const OBJ * pos, const OBJ * first, const OBJ * last
)
{
MoveAfter(pos,this,first,last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
const OBJ * pos, emUcList * src
)
{
if (src) MoveAfter(pos,src,src->First,src->Last);
}
template <class OBJ> inline void emUcList<OBJ>::MoveAfter(
const OBJ * pos, emUcList * src, const OBJ * elem
)
{
MoveAfter(pos,src,elem,elem);
}
template <class OBJ> void emUcList<OBJ>::MoveAfter(
const OBJ * pos, emUcList * src, const OBJ * first, const OBJ * last
)
{
if (!first || !last) return;
if (!src) src=this;
if (!EM_LSTIMP_PREV(first)) src->First=EM_LSTIMP_NEXT(last);
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
if (!EM_LSTIMP_NEXT(last)) src->Last=EM_LSTIMP_PREV(first);
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
if ((EM_LSTIMP_PREV(first)=(OBJ*)pos)==NULL) {
if ((EM_LSTIMP_NEXT(last)=First)==NULL) Last=(OBJ*)last;
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
First=(OBJ*)first;
}
else {
if ((EM_LSTIMP_NEXT(last)=EM_LSTIMP_NEXT(pos))==NULL) {
Last=(OBJ*)last;
}
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=(OBJ*)last;
EM_LSTIMP_NEXT(pos)=(OBJ*)first;
}
}
template <class OBJ> inline void emUcList<OBJ>::RemoveFirst()
{
Remove(First,First);
}
template <class OBJ> inline void emUcList<OBJ>::RemoveLast()
{
Remove(Last,Last);
}
template <class OBJ> inline void emUcList<OBJ>::Remove(const OBJ * elem)
{
Remove(elem,elem);
}
template <class OBJ> void emUcList<OBJ>::Remove(
const OBJ * first, const OBJ * last
)
{
const OBJ * e;
if (!first || !last) return;
if (!EM_LSTIMP_PREV(first)) First=EM_LSTIMP_NEXT(last);
else EM_LSTIMP_NEXT(EM_LSTIMP_PREV(first))=EM_LSTIMP_NEXT(last);
if (!EM_LSTIMP_NEXT(last)) Last=EM_LSTIMP_PREV(first);
else EM_LSTIMP_PREV(EM_LSTIMP_NEXT(last))=EM_LSTIMP_PREV(first);
do {
e=first;
first=EM_LSTIMP_NEXT(first);
delete EM_LSTIMP_ELEM(e);
} while (e!=last);
}
template <class OBJ> void emUcList<OBJ>::Clear()
{
OBJ * e1, * e2;
for (e1=First; e1; e1=e2) {
e2=EM_LSTIMP_NEXT(e1);
delete EM_LSTIMP_ELEM(e1);
}
First=NULL;
Last=NULL;
}
template <class OBJ> inline bool emUcList<OBJ>::IsEmpty() const
{
return !First;
}
template <class OBJ> bool emUcList<OBJ>::Sort(
int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
void * context
)
{
if (First==Last) return false;
return emSortDoubleLinkedList(
(void**)(void*)&First,
(void**)(void*)&Last,
offsetof(Element,Next)-offsetof(Element,Obj),
offsetof(Element,Prev)-offsetof(Element,Obj),
(int(*)(void*,void*,void*))compare,
context
);
}
template <class OBJ> int emUcList<OBJ>::GetCount() const
{
const OBJ * e;
int cnt;
for (cnt=0, e=First; e; cnt++, e=EM_LSTIMP_NEXT(e));
return cnt;
}
template <class OBJ> const OBJ * emUcList<OBJ>::GetAtIndex(int index) const
{
const OBJ * e;
if (index<0) e=NULL;
else for (e=First; e && --index>=0; e=EM_LSTIMP_NEXT(e));
return e;
}
template <class OBJ> int emUcList<OBJ>::GetIndexOf(const OBJ * elem) const
{
const OBJ * e;
int i;
for (i=0, e=First; e; i++, e=EM_LSTIMP_NEXT(e)) {
if (e==elem) return i;
}
return -1;
}
#endif