PPL6-Icon Patrick's Programming Library Version 6.4.21 - Dokumentation
ppl6::CAVLTree Klassenreferenz

AVL-Bäume mit nichtypisierten Elementen. Mehr ...

Klassen

class  Walker
 

Öffentliche Methoden

 CAVLTree ()
 Konstruktor. Mehr ...
 
virtual ~CAVLTree ()
 Destruktor. Mehr ...
 
int Add (const void *value)
 Element hinzufügen. Mehr ...
 
void AllowDupes (bool allow)
 Duplikate erlauben. Mehr ...
 
void Clear ()
 Baum leeren. Mehr ...
 
virtual int Compare (const void *value1, const void *value2) const
 Zwei Elemente des Baums vergleichen. Mehr ...
 
int Delete (const void *value)
 Element anhand eines Wertes löschen. Mehr ...
 
virtual int DestroyValue (void *item) const
 Datenelement löschen. Mehr ...
 
void * Find (const void *value) const
 Element im Baum finden. Mehr ...
 
TREEITEMFindNode (const void *value) const
 Wert im Baum finden. Mehr ...
 
void * FindOrAdd (const void *item)
 
void * GetCurrent ()
 Aktuelles Element des Baums. Mehr ...
 
void * GetCurrent (Walker &walk) const
 
void * GetFirst ()
 Erstes Element aus dem Baum. Mehr ...
 
void * GetFirst (Walker &walk) const
 
void * GetLast ()
 Letztes Element aus dem Baum. Mehr ...
 
void * GetLast (Walker &walk) const
 
void * GetNext ()
 Nächstes Element aus dem Baum. Mehr ...
 
void * GetNext (Walker &walk) const
 
void * GetPrevious ()
 Vorheriges Element aus dem Baum. Mehr ...
 
void * GetPrevious (Walker &walk) const
 
virtual int GetValue (const void *item, CString &buffer) const
 Daten als String ausgeben. Mehr ...
 
int Num () const
 Anzahl Elemente im Baum. Mehr ...
 
void PrintNodes (const TREEITEM *node=NULL) const
 
int Remove (const void *value)
 Element aus dem AVL-Baum entfernen. Mehr ...
 
void Reset ()
 Internen Pointer für Walk-Funktionen zurücksetzen. Mehr ...
 
void Reset (Walker &walk) const
 
void SetTreeController (CTreeController *c)
 Kontrollklasse festlegen. Mehr ...
 

Private Methoden

int DeleteNode (TREEITEM *item)
 Interne Funktion, die das tatsächliche Löschen vornimmt. Mehr ...
 
TREEITEMRotate (TREEITEM *kn)
 
void SwapNodes (TREEITEM *item1, TREEITEM *item2)
 
void UpDelete (TREEITEM *node)
 
void UpInsert (TREEITEM *node)
 

Private Attribute

CTreeControllercontroller
 Externes von CTreeController abgeleitetes Steuermodul. Mehr ...
 
size_t count
 Anzahl Knoten im Baum. Mehr ...
 
TREEITEMcurrent
 Aktueller Knoten beim Durchwandern des Baums. Mehr ...
 
bool dupes
 
TREEITEMroot
 Pointer auf die Wurzel des Baums. Mehr ...
 
TREEITEMstack [AVL_MAX_HEIGHT]
 Alle Knoten oberhalb von current. Mehr ...
 
size_t stack_height
 Anzahl Knoten im Stack. Mehr ...
 

Ausführliche Beschreibung

Beschreibung:
Diese Klasse kann zur Verwaltung beliebiger Elemente in einem sortierten AVL-Baum verwendet werden. Die Elemente sind dabei beliebig und werden nur durch ihren Pointer referenziert. Im Gegensatz zu CTree werden die zur Baumstruktur benötigten Daten von der Klasse selbst verwaltet und sind nicht Bestandteil der einzelnen Elemente.
Dafür kann die Klasse aber nicht direkt verwendet werden, es muss zunächst eine Ableitung erstellt werden, in der mindestens die virtuelle Funktion CAVLTree::Compare implementiert werden muss. Optional können auch noch CAVLTree::DestroyValue und CAVLTree::GetValue implementiert werden.
Als Alternative kann auch eine Klasse von CTreeController abgeleitet werden, in der die genannten Funktionen implementiert werden. Diese wird über CAVLTree::SetTreeController der AVL-Klasse mitgeteilt, wodurch fortan deren Methoden verwendet werden.
Achtung
Die Klasse verwaltet keinen eigenen Mutex und ist somit nicht Thread-sicher. Die Aufrufende Anwendung muss selbst sicherstellen, dass die Klasse nicht gleichzeitig von mehreren Threads verwendet wird.

Beschreibung der Konstruktoren und Destruktoren

ppl6::CAVLTree::CAVLTree ( )
Beschreibung:
Im Konstruktor wird der Baum mit NULL initialisiert und ein gemeinsamer Heap-Speicher für die Verwaltung der Knoten-Elemente wird eingerichtet.
ppl6::CAVLTree::~CAVLTree ( )
virtual
Beschreibung:
Der Destruktor ruft die CTree::Clear Funktion auf.
Achtung
Bei einer abgeleiteten Klasse muss der Destruktor ebenfalls implementiert werden und die Funktion CAVLTree::Clear aufrufen, um sicherzustellen, dass alle Elemente gelöscht werden.

Dokumentation der Elementfunktionen

int ppl6::CAVLTree::Add ( const void *  value)
Beschreibung:
Diese Funktion fügt ein neues Element in den Baum ein. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist. Im Gegensatz zu CTree erlaub CAVLTree auch mehrere Elemente mit dem gleichen Schlüssel. Dieses Feature muss jedoch explizit durch Aufruf der Funktion CAVLTree::AllowDupes aktiviert werden.
Parameter
[in]valuePointer auf den hinzuzufügenden Wert
Rückgabe
Wurde das Element erfolgreich hinzugefügt, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt,
void ppl6::CAVLTree::AllowDupes ( bool  allow)
Beschreibung:
Mit dieser Funktion kann festgelegt werden, ob Elemente mit gleichem Schlüssel im Baum erlaubt sind. Normalerweise ist dies nicht der Fall. Dabei gilt zu beachten, dass einige Funktionen möglicherweise unerwartet funktionieren. So wird CAVLTree::Find immer nur das erste Element finden können, ebenso CAVLTree::Delete oder CAVLTree::Remove.
Parameter
allowMit true werden Duplikate erlaubt, mit false nicht. Werden bei einem bereits gefüllten Baum nachträglich Duplikate verboten, hat dies keine Auswirkung auf bereits vorhandene Duplikate.
void ppl6::CAVLTree::Clear ( )
Beschreibung:
Mit dieser Funktion wird der Inhalt des Baums gelöscht und sämtlicher durch die Elemente belegter Speicher wieder freigegeben. Dazu wird für jedes Element zunächst CAVLTree::DeleteNode und dann die virtuelle Funktion CAVLTree::DestroyValue aufgerufen. Zuletzt wiird noch der duch den Knoten selbst belegte Speicher wieder freigegeben.
Achtung
Bei einer abgeleiteten Klasse muss diese Funktion durch den Destruktor aufgerufen werden, um sicherzustellen, dass alle Elemente gelöscht werden.
int ppl6::CAVLTree::Compare ( const void *  value1,
const void *  value2 
) const
virtual
Beschreibung:
Damit Elemente sortiert in den Baum eingehangen werden können, muss eine Möglichkeit bestehen zwei Elemente zu vergleichen. Dies wird mit dieser Methode realisiert. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden.
Parameter
[in]value1Pointer auf das erste Element. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens.
[in]value2Pointer auf das zweite Element. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens.
Rückgabe
Die Funktion muss einen der folgenden 4 Werte zurückliefern:
  • 0: Ist der Wert in value2 identisch mit value1, muss 0 zurückgegeben werden.
  • +1: Ist der Wert in value2 größer als der Wert in value1, muss +1 zurückgegeben werden
  • -1: Ist der Wert in value2 kleiner als der Wert in value1, muss -1 zurückgegeben werden
  • -2: Dieser Wert wird im Fehlerfall zurückgegeben und es wird ein Fehlercode gesetzt. Die Tree-Operation muss dann ebenfalls mit einem Fehler abbrechen und diesen Fehlercode zurückgeben.
Achtung
Beim Vergleich zweier Strings kann die Funktion strcmp nicht direkt verwendet werden, da sie laut Definition Werte kleiner oder größer 0 liefert, aber nicht exakt -1 oder +1.
Beispiel:
Beispiel für eine Implementierung:
class MyItem
{
public:
MyItem(const char *name) {
Name=name;
}
};
class MyTree : public ppl6::CAVLTree
{
public:
~MyTree() {
Clear();
}
virtual int Compare(const void *value1, const void *value2) {
MyItem *i1=(MyItem*)value1;
MyItem *i2=(MyItem*)value2;
int ret=i2->Name.StrCmp(i1->Name);
if (ret<0) return -1;
if (ret>0) return 1;
return 0;
}
}

Implementiert ppl6::CTreeController.

Erneute Implementation in ppl6::db::PoolTree.

int ppl6::CAVLTree::Delete ( const void *  value)
Beschreibung:
Diese Funktion sucht zunächst ob der angegebene Wert im Baum enthalten ist und löscht anschließend das gefundene Element. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
Beim Löschen des Elements wird auch die virtuelle Funktion CAVLTree::DestroyValue aufgerufen. Diese muss sicherstellen, dass der durch das Element belegte Speicher ebenfalls freigegeben wird.
Falls das Element nur aus dem Baum entfernt werden, aber der durch das Element
belegte Speicher erhalten bleiben soll, kann stattdessen die Funktion CAVLTree::Remove aufgerufen werden.
Parameter
[in]valuePointer auf den zu löschenden Wert
Rückgabe
Wurde das Element erfolgreich gelöscht, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt.
int ppl6::CAVLTree::DeleteNode ( TREEITEM item)
private

Dies ist eine interne Funktion, die den tatsächlichen Löschvorgang aus dem AVL-Baum vornimmt. Der Inhalt des Knotens item und auch der Knoten selbst werden dabei nicht gelöscht, dies muss die Aufrufende Funktion vornehmen. Sie wird von CAVLTree::Delete aufgerufen.

Parameter
[in]itemPointer auf die Verwaltungsstruktur des Baumelements
Rückgabe
Wurde das Element erfolgreich gelöscht, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt,
int ppl6::CAVLTree::DestroyValue ( void *  item) const
virtual
Beschreibung:
Diese Funktion wird aufgerufen, wenn ein Wert aus dem Baum gelöscht werden soll, bzw. wenn der komplette Baum gelöscht wird. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden.
Parameter
itemPointer auf die zu löschenden Daten. Der Pointer zeigt direkt auf die Daten des Knotens, nicht auf die Verwaltungsdaten des Knotens.
Rückgabe
Die Funktion sollte 1 bei erfolgreichem Löschen zurückgeben, im Fehlerfall 0. Allerdings wird der Rückgabewert gegenwärtig nicht geprüft, so dass gegebenenfalls unbemerkt ein Memory-Leak entstehen kann.

Implementiert ppl6::CTreeController.

Erneute Implementation in ppl6::db::PoolTree.

void * ppl6::CAVLTree::Find ( const void *  value) const
Beschreibung:
Mit dieser Funktion wird ein Element innerhalb des Baums gesucht. Dazu wird die Funktion CTree::CompareItems verwendet.
Parameter
[in]valueDer zu suchende Wert
Rückgabe
Wird das Element im Baum gefunden, gibt die Funktion einen Pointer auf den Wert des Baum-Elements zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
TREEITEM * ppl6::CAVLTree::FindNode ( const void *  value) const
Beschreibung:
Mit dieser Funktion wird der Wert value innerhalb des Baums gesucht und dessen Baumelement (TREEITEM) zurückgegeben.
Parameter
[in]valueDer zu suchende Wert
Rückgabe
Wird der Wert im Baum gefunden, gibt die Funktion einen Pointer auf den Wert des Baum-Elements zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
void* ppl6::CAVLTree::FindOrAdd ( const void *  item)
void * ppl6::CAVLTree::GetCurrent ( )
Beschreibung:
Mit dieser Funktion wird ein Pointer auf das aktuelle Element des Baums zurückgeliefert. Dabei wird der Pointer nicht verändert.
Rückgabe
Pointer auf das aktuelle Element des Baums oder NULL, wenn kein Element mehr vorhanden ist. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetCurrent ( Walker walk) const
void * ppl6::CAVLTree::GetFirst ( )
Beschreibung:
Mit dieser Funktion wird ein Pointer auf das erste Element des Baums zurückgeliefert.
Rückgabe
Pointer auf das erste Element des Baums oder NULL, wenn der Baum leer ist
void * ppl6::CAVLTree::GetFirst ( Walker walk) const
void * ppl6::CAVLTree::GetLast ( )
Beschreibung:
Mit dieser Funktion wird ein Pointer auf das letzte Element des Baums zurückgeliefert.
Rückgabe
Pointer auf das letzte Element des Baums oder NULL, wenn der Baum leer ist
void * ppl6::CAVLTree::GetLast ( Walker walk) const
void * ppl6::CAVLTree::GetNext ( )
Beschreibung:
Mit dieser Funktion wird ein Pointer auf das nächste Element des Baums zurückgeliefert. Somit kann der Baum sortiert vorwärts durchwandert werden.
Rückgabe
Pointer auf das nächste Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetNext ( Walker walk) const
void * ppl6::CAVLTree::GetPrevious ( )
Beschreibung:
Mit dieser Funktion wird ein Pointer auf das vorherige Element des Baums zurückgeliefert. Somit kann der Baum sortiert rückwärts durchwandert werden.
Rückgabe
Pointer auf das vorherige Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind. In diesesm Fall wird ausserdem der Fehlercode 422 gesetzt.
void * ppl6::CAVLTree::GetPrevious ( Walker walk) const
int ppl6::CAVLTree::GetValue ( const void *  item,
CString buffer 
) const
virtual

Diese Funktion wird durch CAVLTree::PrintNodes aufgerufen, um den Inhalt des Baums anzeigen zu können. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden. Sie bekommt als Eingabe einen Pointer item auf die Daten des Knotens und einen String buffer, in dem eine textuelle Darstellung des Dateninhalts abgelegt werden soll.

Die Implementierung der Funktion ist optional.
Parameter
[in]itemPointer auf die Daten des Knotens
[out]bufferString, in dem die textuelle Darstellung der Daten erfolgen soll.
Rückgabe
Bei Erfolg soll die Funktion 1 zurückgeben, im Fehlerfall 0. Wird 0 zurückgegeben, wird der Knoten nicht ausgegeben.

Implementiert ppl6::CTreeController.

Erneute Implementation in ppl6::db::PoolTree.

int ppl6::CAVLTree::Num ( ) const
Beschreibung:
Diese Funktion liefert die Anzahl Elemente im Baum zurück.
Rückgabe
Anzahl Elemente oder 0, wenn der Baum leer ist. Bei einem leeren Baum wird ausserdem der Fehlercode 347 gesetzt.
void ppl6::CAVLTree::PrintNodes ( const TREEITEM node = NULL) const
int ppl6::CAVLTree::Remove ( const void *  value)
Beschreibung:
Diese Funktion sucht zunächst ob der angegebene Wert im Baum enthalten ist und löscht anschließend das gefundene Element aus dem Baum. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
Mit dieser Funktion wird das Element nur aus dem AVL-Baum entfernt, der durch das Element belegte Speicher wird jedoch nicht freigegeben. Falls dies gewünscht ist, kann stattdessen die Funktion CAVLTree::Delete aufgerufen werden.
Parameter
[in]valuePointer auf den zu entfernenden Wert
Rückgabe
Wurde das Element erfolgreich entfernt, gibt die Funktion true (1) zurück, sonst false (0) und ein entsprechender Fehlercode wird gesetzt.
void ppl6::CAVLTree::Reset ( )
Beschreibung:
Mit dieser Funktion wird der interne Pointer zurückgesetzt, der für die Walk-Funktionen GetNext und GetPrevious verwendet wird.
void ppl6::CAVLTree::Reset ( Walker walk) const
TREEITEM * ppl6::CAVLTree::Rotate ( TREEITEM kn)
private
void ppl6::CAVLTree::SetTreeController ( CTreeController c)
Beschreibung:
Bei Verwendung der CAVLTree-Klasse wird üblicherweise eine eigene Klasse davon abgeleitet und mindestens die virtuelle Funktion CAVLTree::Compare, optional auch CAVLTree::DestroyValue und CAVLTree::GetValue reimplementiert. Es gibt jedoch auch die Möglichkeit CAVLTree ohne Ableitung zu verwenden. Dazu muss die eigene Klasse von CTreeController abgeleitet werden und dessen Pointer mit dieser Funktion an die CAVLTree-Klasse übergeben werden.
Parameter
[in]cPointer auf eine von CTreeController abgeleitete Klasse, die mindestens die virtuelle Funktion CTreeController::Compare implementiert hat.
void ppl6::CAVLTree::SwapNodes ( TREEITEM item1,
TREEITEM item2 
)
private
void ppl6::CAVLTree::UpDelete ( TREEITEM node)
private
void ppl6::CAVLTree::UpInsert ( TREEITEM node)
private

Dokumentation der Datenelemente

ppl6::CAVLTree::controller
private
ppl6::CAVLTree::count
private
ppl6::CAVLTree::current
private
bool ppl6::CAVLTree::dupes
private
ppl6::CAVLTree::root
private
ppl6::CAVLTree::stack
private
ppl6::CAVLTree::stack_height
private

Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Dateien: