//------------------------------------------------------------------------------
// emAvlTreeSet.h
//
// Copyright (C) 2016,2021 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 emAvlTreeSet_h
#define emAvlTreeSet_h
#ifndef emAvlTree_h
#include <emCore/emAvlTree.h>
#endif
//==============================================================================
//================================ emAvlTreeSet ================================
//==============================================================================
template <class OBJ> class emAvlTreeSet {
public:
// Template class for an AVL tree which holds a sorted set of unique
// elements. This class provides copy-on-write behavior and stable
// iterators. The template parameter OBJ describes the type of the
// elements. Elements are compared with the normal comparison operators
// (==, <=, >...).
emAvlTreeSet();
// Construct an empty set.
emAvlTreeSet(const emAvlTreeSet & src);
// Construct a copied set.
emAvlTreeSet(const OBJ & obj);
// Construct a set with one element.
~emAvlTreeSet();
// Destructor.
emAvlTreeSet & operator = (const emAvlTreeSet & set);
// Make this set a copy of the given set.
bool Contains(const OBJ & obj) const;
// Ask whether this set contains an element which equals the
// given object.
const OBJ * Get(const OBJ & obj) const;
// Get a pointer to the element which equals the given object.
// If there is no such element, NULL is returned. At least
// because of the copy-on-write feature, the pointer is valid
// only until calling any non-const method or operator on this
// set, or giving this set as a non-const argument to any call
// in the world.
const OBJ * GetFirst() const;
const OBJ * GetLast() const;
// Get the smallest or largest element. If the set is empty,
// NULL is returned. The rules for the validity of the
// pointer are the same as with Get(obj).
const OBJ * GetNearestGreater(const OBJ & obj) const;
const OBJ * GetNearestGreaterOrEqual(const OBJ & obj) const;
const OBJ * GetNearestLess(const OBJ & obj) const;
const OBJ * GetNearestLessOrEqual(const OBJ & obj) const;
// Get the nearest element which is greater, or greater or
// equal, or less, or less or equal to a given object. If no
// such element exists, NULL is returned. The rules for the
// validity of the pointer are the same as with Get(obj).
OBJ * GetWritable(const OBJ & obj, bool insertIfNew);
OBJ * GetWritable(const OBJ * elem);
// Get a non-const version of a pointer to an element of this
// set. If insertIfNew is true, the element is created if it is
// not found. The pointer may be used for modifying the object
// in a way that the order is not disturbed. The rules for the
// validity of the pointer are the same as with Get(obj), but:
// The pointer must not be used for modifying after doing
// something which could have made a shallow copy of this list.
void Insert(const OBJ & obj);
void Insert(const emAvlTreeSet & set);
// Insert one or more objects. Each objects is only inserted, if
// there is not already an equal element contained in the set.
void RemoveFirst();
void RemoveLast();
void Remove(const OBJ & obj);
void Remove(const OBJ * elem);
void Remove(const emAvlTreeSet & set);
// Remove (and delete) elements from this set.
void Intersect(const emAvlTreeSet & set);
// Remove (and delete) all elements from this set which are not
// contained in a given set.
void Clear();
// Remove (and delete) all elements of this set.
bool IsEmpty() const;
// Ask whether this set has no elements.
int GetCount() const;
// Compute the number of elements.
bool operator == (const emAvlTreeSet & set) const;
bool operator != (const emAvlTreeSet & set) const;
// Operators for comparing sets.
emAvlTreeSet & operator += (const OBJ & obj);
emAvlTreeSet & operator += (const emAvlTreeSet & set);
emAvlTreeSet operator + (const OBJ & obj) const;
emAvlTreeSet operator + (const emAvlTreeSet & set) const;
// Operators for uniting sets.
emAvlTreeSet & operator |= (const OBJ & obj);
emAvlTreeSet & operator |= (const emAvlTreeSet & set);
emAvlTreeSet operator | (const OBJ & obj) const;
emAvlTreeSet operator | (const emAvlTreeSet & set) const;
// Operators for uniting sets (same as +).
emAvlTreeSet & operator -= (const OBJ & obj);
emAvlTreeSet & operator -= (const emAvlTreeSet & set);
emAvlTreeSet operator - (const OBJ & obj) const;
emAvlTreeSet operator - (const emAvlTreeSet & set) const;
// Operators for subtracting sets.
emAvlTreeSet & operator &= (const OBJ & obj);
emAvlTreeSet & operator &= (const emAvlTreeSet & set);
emAvlTreeSet operator & (const OBJ & obj) const;
emAvlTreeSet operator & (const emAvlTreeSet & set) const;
// Operators for intersecting sets.
//friend emAvlTreeSet operator + (const OBJ & obj, const emAvlTreeSet & set);
//friend emAvlTreeSet operator | (const OBJ & obj, const emAvlTreeSet & set);
//friend emAvlTreeSet operator - (const OBJ & obj, const emAvlTreeSet & set);
//friend emAvlTreeSet operator & (const OBJ & obj, const emAvlTreeSet & set);
// These ones even exist and can be used.
// (Having the declaration here would not be portable)
unsigned int GetDataRefCount() const;
// Get number of references to the data behind this set.
void MakeNonShared();
// This must be called before handing the set to another thread.
// This method is not recursive. So if the object class
// even has such a method, you have to call that manually.
class Iterator {
public:
// Class for a stable pointer to an element of a set.
// "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 removed from a set, 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 set, all
// iterators which were pointing to elements of the set are
// set to NULL. This is even true if the set is assigned to
// itself.
// This kind of iterator needs little more than 500 bytes of
// memory, because it manages a stack of tree nodes for the
// current position (yes, the AVL nodes do not have parent
// pointers...).
// Modifying the set while an iterator is active slows down the
// iterator, because it has to find the tree position again on
// next increment or decrement.
// Note the auto-cast operator to a 'const OBJ *'. Wherever
// there is an argument 'const OBJ *' in the methods of
// emAvlTreeSet, 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 emAvlTreeSet<OBJ> & set, const OBJ * elem);
// Construct an iterator pointing to a particular
// element.
// Arguments:
// set - The set.
// elem - Pointer to an element of the set, 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 emAvlTreeSet<OBJ> & set, const OBJ * elem);
// Set this iterator to the given element of the given
// set and return the element pointer.
const OBJ * SetFirst(const emAvlTreeSet<OBJ> & set);
const OBJ * SetLast(const emAvlTreeSet<OBJ> & set);
// Set this iterator to the first or last element of the
// given set 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 emAvlTreeSet<OBJ> * GetSet() const;
// Get a pointer to the set this iterator is currently
// attached to. Returns NULL if not attached to any
// set. (See comments on Detach()).
void Detach();
// Detach this iterator from its set and point to NULL.
// Note: to care about the iterators, each emAvlTreeSet
// has a single linked list of its iterators. The
// mechanism is lazy, that means, an iterator may stay
// in the set 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 set is modified.
private:
friend class emAvlTreeSet<OBJ>;
void SetSet(const emAvlTreeSet<OBJ> * set);
const OBJ * SetPos(const OBJ & obj);
const OBJ * Pos;
emAvlIterator AvlIter;
bool AvlIterValid;
emAvlTreeSet<OBJ> * Ats;
Iterator * NextIter; // Undefined if Ats==NULL
};
private:
friend class Iterator;
struct Element {
OBJ Obj;
emAvlNode AvlNode;
inline Element(const OBJ & obj) : Obj(obj) {}
};
struct SharedData {
emAvlTree AvlTree;
bool IsStaticEmpty;
unsigned int RefCount;
};
void MakeWritable(const OBJ * * preserve=NULL);
void DeleteData();
emAvlNode * CloneTree(emAvlNode * tree, const OBJ * * preserve);
SharedData * Data;
Iterator * Iterators;
static SharedData EmptyData;
};
//==============================================================================
//============================== Implementations ===============================
//==============================================================================
template <class OBJ> inline emAvlTreeSet<OBJ>::emAvlTreeSet()
{
Iterators=NULL;
Data=&EmptyData;
}
template <class OBJ> inline emAvlTreeSet<OBJ>::emAvlTreeSet(
const emAvlTreeSet & src
)
{
Iterators=NULL;
Data=src.Data;
Data->RefCount++;
}
template <class OBJ> emAvlTreeSet<OBJ>::emAvlTreeSet(const OBJ & obj)
{
Iterators=NULL;
Data=&EmptyData;
Insert(obj);
}
template <class OBJ> emAvlTreeSet<OBJ>::~emAvlTreeSet()
{
Iterator * i;
for (i=Iterators; i; i=i->NextIter) { i->Pos=NULL; i->Ats=NULL; }
if (!--Data->RefCount) DeleteData();
}
template <class OBJ> emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator = (
const emAvlTreeSet & set
)
{
Iterator * i;
for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
set.Data->RefCount++;
if (!--Data->RefCount) DeleteData();
Data=set.Data;
return *this;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::Contains(
const OBJ & obj
) const
{
return Get(obj)!=NULL;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Get(const OBJ & obj) const
{
EM_AVL_SEARCH_VARS(Element)
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) EM_AVL_SEARCH_GO_LEFT
else if (obj>element->Obj) EM_AVL_SEARCH_GO_RIGHT
EM_AVL_SEARCH_END
return &element->Obj;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetFirst() const
{
EM_AVL_SEARCH_VARS(Element)
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
EM_AVL_SEARCH_GO_LEFT_OR_FOUND
EM_AVL_SEARCH_END
return &element->Obj;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetLast() const
{
EM_AVL_SEARCH_VARS(Element)
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
EM_AVL_SEARCH_GO_RIGHT_OR_FOUND
EM_AVL_SEARCH_END
return &element->Obj;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetNearestGreater(
const OBJ & obj
) const
{
EM_AVL_SEARCH_VARS(Element)
const OBJ * nearest;
nearest=NULL;
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) { nearest=&element->Obj; EM_AVL_SEARCH_GO_LEFT }
else EM_AVL_SEARCH_GO_RIGHT
EM_AVL_SEARCH_END
return nearest;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetNearestGreaterOrEqual(
const OBJ & obj
) const
{
EM_AVL_SEARCH_VARS(Element)
const OBJ * nearest;
nearest=NULL;
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) { nearest=&element->Obj; EM_AVL_SEARCH_GO_LEFT }
else if (obj>element->Obj) EM_AVL_SEARCH_GO_RIGHT
else nearest=&element->Obj;
EM_AVL_SEARCH_END
return nearest;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetNearestLess(
const OBJ & obj
) const
{
EM_AVL_SEARCH_VARS(Element)
const OBJ * nearest;
nearest=NULL;
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj>element->Obj) { nearest=&element->Obj; EM_AVL_SEARCH_GO_RIGHT }
else EM_AVL_SEARCH_GO_LEFT
EM_AVL_SEARCH_END
return nearest;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::GetNearestLessOrEqual(
const OBJ & obj
) const
{
EM_AVL_SEARCH_VARS(Element)
const OBJ * nearest;
nearest=NULL;
EM_AVL_SEARCH_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) EM_AVL_SEARCH_GO_LEFT
else if (obj>element->Obj) { nearest=&element->Obj; EM_AVL_SEARCH_GO_RIGHT }
else nearest=&element->Obj;
EM_AVL_SEARCH_END
return nearest;
}
template <class OBJ> OBJ * emAvlTreeSet<OBJ>::GetWritable(
const OBJ & obj, bool insertIfNew
)
{
if (insertIfNew) {
if (Data->RefCount>1 || Data->IsStaticEmpty) MakeWritable();
EM_AVL_INSERT_VARS(Element)
EM_AVL_INSERT_BEGIN_SEARCH(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) EM_AVL_INSERT_GO_LEFT
else if (obj>element->Obj) EM_AVL_INSERT_GO_RIGHT
else return &element->Obj;
EM_AVL_INSERT_END_SEARCH
element=new Element(obj);
Iterator * i;
for (i=Iterators; i; i=i->NextIter) {
i->AvlIterValid=false;
}
EM_AVL_INSERT_NOW(AvlNode)
return &element->Obj;
}
else {
const OBJ * elem = Get(obj);
if (!elem) return NULL;
if (Data->RefCount>1) MakeWritable(&elem);
return (OBJ*)elem;
}
}
template <class OBJ> OBJ * emAvlTreeSet<OBJ>::GetWritable(
const OBJ * elem
)
{
if (!elem) return NULL;
if (Data->RefCount>1) MakeWritable(&elem);
return (OBJ*)elem;
}
template <class OBJ> inline void emAvlTreeSet<OBJ>::Insert(const OBJ & obj)
{
GetWritable(obj,true);
}
template <class OBJ> void emAvlTreeSet<OBJ>::Insert(const emAvlTreeSet & set)
{
emAvlTreeSet::Iterator i;
for (i.SetFirst(set); i; ++i) {
Insert(*i.Get());
}
}
template <class OBJ> inline void emAvlTreeSet<OBJ>::RemoveFirst()
{
Remove(GetFirst());
}
template <class OBJ> inline void emAvlTreeSet<OBJ>::RemoveLast()
{
Remove(GetLast());
}
template <class OBJ> void emAvlTreeSet<OBJ>::Remove(const OBJ & obj)
{
EM_AVL_REMOVE_VARS(Element)
Iterator * i;
if (Data->RefCount>1 && !Data->IsStaticEmpty) MakeWritable();
EM_AVL_REMOVE_BEGIN(Element,AvlNode,Data->AvlTree)
if (obj<element->Obj) {
EM_AVL_REMOVE_GO_LEFT
}
else if (obj>element->Obj) {
EM_AVL_REMOVE_GO_RIGHT
}
else {
for (i=Iterators; i; i=i->NextIter) {
if (i->Pos==&element->Obj) i->SetNext();
i->AvlIterValid=false;
}
EM_AVL_REMOVE_NOW
delete element;
}
EM_AVL_REMOVE_END
}
template <class OBJ> void emAvlTreeSet<OBJ>::Remove(const OBJ * elem)
{
if (elem) Remove(*elem);
}
template <class OBJ> void emAvlTreeSet<OBJ>::Remove(const emAvlTreeSet & set)
{
emAvlTreeSet::Iterator i;
if (Data != set.Data) {
for (i.SetFirst(set); i; ++i) {
Remove(*i.Get());
}
}
else {
Clear();
}
}
template <class OBJ> void emAvlTreeSet<OBJ>::Intersect(const emAvlTreeSet & set)
{
emAvlTreeSet::Iterator i;
for (i.SetFirst(*this); i;) {
if (!set.Contains(*i.Get())) Remove(*i);
else ++i;
}
}
template <class OBJ> void emAvlTreeSet<OBJ>::Clear()
{
Iterator * i;
for (i=Iterators; i; i=i->NextIter) i->Pos=NULL;
if (!--Data->RefCount) DeleteData();
Data=&EmptyData;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::IsEmpty() const
{
return !Data->AvlTree;
}
template <class OBJ> int emAvlTreeSet<OBJ>::GetCount() const
{
EM_AVL_LOOP_VARS(Element)
int count;
count=0;
EM_AVL_LOOP_START(Element,AvlNode,Data->AvlTree)
count++;
EM_AVL_LOOP_END
return count;
}
template <class OBJ> bool emAvlTreeSet<OBJ>::operator == (
const emAvlTreeSet & set
) const
{
emAvlTreeSet::Iterator i,j;
if (Data != set.Data) {
for (i.SetFirst(*this), j.SetFirst(set); ; ++i, ++j) {
if (!i) {
if (j) return false;
break;
}
if (!j) {
if (i) return false;
break;
}
if (*i.Get() != *j.Get()) return false;
}
}
return true;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::operator != (
const emAvlTreeSet & set
) const
{
return !(*this == set);
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator += (
const OBJ & obj
)
{
Insert(obj);
return *this;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator += (
const emAvlTreeSet & set
)
{
Insert(set);
return *this;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator + (
const OBJ & obj
) const
{
emAvlTreeSet result(*this);
result += obj;
return result;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator + (
const emAvlTreeSet & set
) const
{
emAvlTreeSet result(*this);
result += set;
return result;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator |= (
const OBJ & obj
)
{
return *this += obj;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator |= (
const emAvlTreeSet & set
)
{
return *this += set;
}
template <class OBJ> inline emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator | (
const OBJ & obj
) const
{
return *this + obj;
}
template <class OBJ> inline emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator | (
const emAvlTreeSet & set
) const
{
return *this + set;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator -= (
const OBJ & obj
)
{
Remove(obj);
return *this;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator -= (
const emAvlTreeSet & set
)
{
Remove(set);
return *this;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator - (
const OBJ & obj
) const
{
emAvlTreeSet result(*this);
result -= obj;
return result;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator - (
const emAvlTreeSet & set
) const
{
emAvlTreeSet result(*this);
result -= set;
return result;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator &= (
const OBJ & obj
)
{
Intersect(emAvlTreeSet(obj));
return *this;
}
template <class OBJ> inline emAvlTreeSet<OBJ> & emAvlTreeSet<OBJ>::operator &= (
const emAvlTreeSet & set
)
{
Intersect(set);
return *this;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator & (
const OBJ & obj
) const
{
emAvlTreeSet result(*this);
result &= obj;
return result;
}
template <class OBJ> emAvlTreeSet<OBJ> emAvlTreeSet<OBJ>::operator & (
const emAvlTreeSet & set
) const
{
emAvlTreeSet result(*this);
result &= set;
return result;
}
template <class OBJ> inline emAvlTreeSet<OBJ> operator + (
const OBJ & obj, const emAvlTreeSet<OBJ> & set
)
{
return set + obj;
}
template <class OBJ> inline emAvlTreeSet<OBJ> operator | (
const OBJ & obj, const emAvlTreeSet<OBJ> & set
)
{
return set | obj;
}
template <class OBJ> emAvlTreeSet<OBJ> operator - (
const OBJ & obj, const emAvlTreeSet<OBJ> & set
)
{
if (!set.Contains(obj)) return emAvlTreeSet<OBJ>(obj);
else return emAvlTreeSet<OBJ>();
}
template <class OBJ> inline emAvlTreeSet<OBJ> operator & (
const OBJ & obj, const emAvlTreeSet<OBJ> & set
)
{
return set & obj;
}
template <class OBJ> unsigned int emAvlTreeSet<OBJ>::GetDataRefCount() const
{
return Data->IsStaticEmpty ? UINT_MAX/2 : Data->RefCount;
}
template <class OBJ> inline void emAvlTreeSet<OBJ>::MakeNonShared()
{
MakeWritable();
}
template <class OBJ> inline emAvlTreeSet<OBJ>::Iterator::Iterator()
{
Pos=NULL;
Ats=NULL;
}
template <class OBJ> emAvlTreeSet<OBJ>::Iterator::Iterator(
const typename emAvlTreeSet<OBJ>::Iterator & iter
)
{
Pos=NULL;
Ats=NULL;
Set(iter);
}
template <class OBJ> emAvlTreeSet<OBJ>::Iterator::Iterator(
const emAvlTreeSet<OBJ> & set,
const OBJ * elem
)
{
Pos=NULL;
Ats=NULL;
Set(set,elem);
}
template <class OBJ> emAvlTreeSet<OBJ>::Iterator::~Iterator()
{
Iterator * * pi;
if (Ats) {
for (pi=&Ats->Iterators; *pi!=this; pi=&(*pi)->NextIter);
*pi=NextIter;
}
}
template <class OBJ> inline
typename emAvlTreeSet<OBJ>::Iterator & emAvlTreeSet<OBJ>::Iterator::operator = (
const Iterator & iter
)
{
Set(iter);
return *this;
}
template <class OBJ> inline
emAvlTreeSet<OBJ>::Iterator::operator const OBJ * () const
{
return Pos;
}
template <class OBJ> inline
const OBJ * emAvlTreeSet<OBJ>::Iterator::operator * () const
{
return Pos;
}
template <class OBJ> inline
const OBJ * emAvlTreeSet<OBJ>::Iterator::operator -> () const
{
return Pos;
}
template <class OBJ> inline const OBJ * emAvlTreeSet<OBJ>::Iterator::Get() const
{
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::Set(
const Iterator & iter
)
{
SetSet(iter.Ats);
if (Pos!=iter.Pos) {
AvlIterValid=false;
Pos=iter.Pos;
}
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::Set(
const emAvlTreeSet<OBJ> & set, const OBJ * elem
)
{
SetSet(&set);
if (Pos!=elem) {
AvlIterValid=false;
Pos=elem;
}
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::SetFirst(
const emAvlTreeSet<OBJ> & set
)
{
EM_AVL_ITER_VARS(Element)
SetSet(&set);
EM_AVL_ITER_FIRST(Element,AvlNode,Ats->Data->AvlTree,AvlIter)
AvlIterValid=true;
Pos=(element ? &element->Obj : NULL);
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::SetLast(
const emAvlTreeSet<OBJ> & set
)
{
EM_AVL_ITER_VARS(Element)
SetSet(&set);
EM_AVL_ITER_LAST(Element,AvlNode,Ats->Data->AvlTree,AvlIter)
AvlIterValid=true;
Pos=(element ? &element->Obj : NULL);
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::SetNext()
{
EM_AVL_ITER_VARS(Element)
if (Pos) {
if (!AvlIterValid) SetPos(*Pos);
EM_AVL_ITER_NEXT(Element,AvlNode,AvlIter)
Pos=(element ? &element->Obj : NULL);
}
return Pos;
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::SetPrev()
{
EM_AVL_ITER_VARS(Element)
if (Pos) {
if (!AvlIterValid) SetPos(*Pos);
EM_AVL_ITER_PREV(Element,AvlNode,AvlIter)
Pos=(element ? &element->Obj : NULL);
}
return Pos;
}
template <class OBJ> inline const OBJ * emAvlTreeSet<OBJ>::Iterator::operator ++()
{
return SetNext();
}
template <class OBJ> inline const OBJ * emAvlTreeSet<OBJ>::Iterator::operator --()
{
return SetPrev();
}
template <class OBJ> inline const OBJ * emAvlTreeSet<OBJ>::Iterator::operator ++(int)
{
const OBJ * res=Pos;
SetNext();
return res;
}
template <class OBJ> inline const OBJ * emAvlTreeSet<OBJ>::Iterator::operator --(int)
{
const OBJ * res=Pos;
SetPrev();
return res;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::Iterator::operator == (
const Iterator & iter
) const
{
return Pos==iter.Pos;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::Iterator::operator != (
const Iterator & iter
) const
{
return Pos!=iter.Pos;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::Iterator::operator == (
const OBJ * elem
) const
{
return Pos==elem;
}
template <class OBJ> inline bool emAvlTreeSet<OBJ>::Iterator::operator != (
const OBJ * elem
) const
{
return Pos!=elem;
}
template <class OBJ> inline
const emAvlTreeSet<OBJ> * emAvlTreeSet<OBJ>::Iterator::GetSet() const
{
return Ats;
}
template <class OBJ> void emAvlTreeSet<OBJ>::Iterator::Detach()
{
Iterator * * pi;
if (Ats) {
for (pi=&Ats->Iterators; *pi!=this; pi=&(*pi)->NextIter);
*pi=NextIter;
Ats=NULL;
Pos=NULL;
}
}
template <class OBJ> void emAvlTreeSet<OBJ>::Iterator::SetSet(
const emAvlTreeSet<OBJ> * set
)
{
Iterator * * pi;
if (Ats!=set) {
if (Ats) {
for (pi=&Ats->Iterators; *pi!=this; pi=&(*pi)->NextIter);
*pi=NextIter;
}
Ats=(emAvlTreeSet<OBJ>*)set;
if (Ats) {
NextIter=Ats->Iterators;
Ats->Iterators=this;
}
}
}
template <class OBJ> const OBJ * emAvlTreeSet<OBJ>::Iterator::SetPos(
const OBJ & obj
)
{
EM_AVL_ITER_VARS(Element)
EM_AVL_ITER_START_ANY_BEGIN(Element,AvlNode,Ats->Data->AvlTree,AvlIter)
if (obj<element->Obj) EM_AVL_ITER_START_ANY_GO_LEFT(AvlIter)
else if (obj>element->Obj) EM_AVL_ITER_START_ANY_GO_RIGHT(AvlIter)
EM_AVL_ITER_START_ANY_END
AvlIterValid=true;
Pos=(element ? &element->Obj : NULL);
return Pos;
}
template <class OBJ> void emAvlTreeSet<OBJ>::MakeWritable(
const OBJ * * preserve
)
{
SharedData * d1, * d2;
d1=Data;
if (d1->RefCount>1 || Data->IsStaticEmpty) {
d2=new SharedData;
d2->AvlTree=NULL;
d2->IsStaticEmpty=false;
d2->RefCount=1;
d1->RefCount--;
Data=d2;
if (d1->AvlTree) {
d2->AvlTree=CloneTree(d1->AvlTree,preserve);
}
}
}
template <class OBJ> void emAvlTreeSet<OBJ>::DeleteData()
{
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) {
if (Data->AvlTree) {
EM_AVL_CLEAR_VARS(Element)
EM_AVL_CLEAR_BEGIN(Element,AvlNode,Data->AvlTree)
delete element;
EM_AVL_CLEAR_END
}
delete Data;
}
}
template <class OBJ> emAvlNode * emAvlTreeSet<OBJ>::CloneTree(
emAvlNode * tree, const OBJ * * preserve
)
{
Element * e1, * e2;
Iterator * i;
e1=EM_AVL_ELEMENT(Element,AvlNode,tree);
e2=new Element(e1->Obj);
e2->AvlNode=e1->AvlNode;
if (preserve && *preserve==&e1->Obj) *preserve=&e2->Obj;
for (i=Iterators; i; i=i->NextIter) {
if (i->Pos==&e1->Obj) {
i->Pos=&e2->Obj;
i->AvlIterValid=false;
}
}
if (e1->AvlNode.Left) {
e2->AvlNode.Left=CloneTree(e1->AvlNode.Left,preserve);
}
if (e1->AvlNode.Right) {
e2->AvlNode.Right=CloneTree(e1->AvlNode.Right,preserve);
}
return &e2->AvlNode;
}
template <class OBJ>
typename emAvlTreeSet<OBJ>::SharedData emAvlTreeSet<OBJ>::EmptyData=
{
NULL,true,UINT_MAX/2
};
#endif