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

AVL-Bäume mit CTreeItem. Mehr ...

Öffentliche Methoden

 CTree ()
 Konstruktor. Mehr ...
 
virtual ~CTree ()
 Destruktor. Mehr ...
 
int Add (CTreeItem *item)
 Element hinzufügen. Mehr ...
 
void Clear (bool deleteitems=false)
 Baum leeren. Mehr ...
 
int Delete (CTreeItem *item)
 Element löschen. Mehr ...
 
int Delete (void *value)
 Element anhand eines Wertes löschen. Mehr ...
 
CTreeItemFind (void *value) const
 Wert im Baum finden. Mehr ...
 
CTreeItemFind (CTreeItem *item) const
 Element im Baum finden. Mehr ...
 
CTreeItemFindOrAdd (CTreeItem *item)
 Element im Baum finden oder hinzufügen. Mehr ...
 
CTreeItemGetCurrent (CTreeWalker &walk) const
 Aktuelles Element des Baums. Mehr ...
 
CTreeItemGetCurrent () const
 Aktuelles Element des Baums. Mehr ...
 
CTreeItemGetFirst ()
 Erstes Element aus dem Baum. Mehr ...
 
CTreeItemGetFirst (CTreeWalker &walk) const
 
CTreeItemGetLast ()
 Letztes Element aus dem Baum. Mehr ...
 
CTreeItemGetLast (CTreeWalker &walk) const
 Letztes Element aus dem Baum. Mehr ...
 
CTreeItemGetNext ()
 Nächstes Element aus dem Baum. Mehr ...
 
CTreeItemGetNext (CTreeWalker &walk) const
 
CTreeItemGetPrevious ()
 Vorheriges Element aus dem Baum. Mehr ...
 
CTreeItemGetPrevious (CTreeWalker &walk) const
 Vorheriges Element aus dem Baum. Mehr ...
 
CTreeItemGetRootNode () const
 Pointer auf Root-Knoten holen. Mehr ...
 
void Graphviz (CString &s, CTreeItem *node=NULL) const
 Baumdarstellung mit Graphviz. Mehr ...
 
int ListNodes (CCallback *callback) const
 Elemente des Baums sortiert an eine Callback-Funktion geben. Mehr ...
 
int Num () const
 Anzahl Elemente im Baum. Mehr ...
 
void PrintNodes (CTreeItem *node=NULL) const
 
void Reset ()
 Internen Pointer für Walk-Funktionen zurücksetzen. Mehr ...
 
void Reset (CTreeWalker &walk) const
 CTreeWalker für Walk-Funktionen zurücksetzen. Mehr ...
 
int Validate ()
 Baum überprüfen. Mehr ...
 

Private Methoden

void Graphviz (CString &s, CTreeItem *node, int tiefe) const
 Baumdarstellung mit Graphviz. Mehr ...
 
void ListNodes (CCallback *callback, CTreeItem *node) const
 Interne Funktion zum Auflisten des Baums. Mehr ...
 
CTreeItemRotate (CTreeItem *kn)
 
void SwapNodes (CTreeItem *item1, CTreeItem *item2)
 
void UpDelete (CTreeItem *node)
 
void UpInsert (CTreeItem *node)
 

Private Attribute

size_t count
 Anzahl Knoten im Baum. Mehr ...
 
CTreeItemcurrent
 Aktueller Knoten beim Durchwandern des Baums. Mehr ...
 
CTreeItemroot
 Pointer auf die Wurzel des Baums. Mehr ...
 
CTreeItemstack [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 müssen dabei von der Basisklasse ppl6::CTreeItem abgeleitet sein.
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::CTree::CTree ( )
Beschreibung:
Im Konstruktor wird der Baum mit NULL initialisiert.
ppl6::CTree::~CTree ( )
virtual
Beschreibung:
Der Destruktor ruft die CTree::Clear Funktion auf.

Dokumentation der Elementfunktionen

int ppl6::CTree::Add ( CTreeItem item)
Beschreibung:
Diese Funktion fügt ein neues Element in den Baum ein. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
Parameter
[in]itemPointer auf das hinzuzufügende Element
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::CTree::Clear ( bool  deleteitems = false)
Beschreibung:
Mit dieser Funktion wird der Inhalt des Baums gelöscht.
Parameter
[in]deleteitemsWird der optionale Parameter auf "true" gesetzt, wird der Destruktur jedes Baumelements aufgerufen.
int ppl6::CTree::Delete ( CTreeItem item)
Beschreibung:
Diese Funktion prüft 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.
Parameter
[in]itemPointer auf das zu löschende Element
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::CTree::Delete ( 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.
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,
CTreeItem * ppl6::CTree::Find ( void *  value) const
Beschreibung:
Mit dieser Funktion wird ein beliebiger Wert innerhalb des Baums gesucht. Dazu wird die Funktion CTreeItem::CompareValue verwendet.
Parameter
[in]valueBeliebiger Pointer auf einen Wert
Rückgabe
Wird der Wert im Baum gefunden, gibt die Funktion einen Pointer auf das Baum-Element zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
CTreeItem * ppl6::CTree::Find ( CTreeItem item) const
Beschreibung:
Mit dieser Funktion wird ein Element innerhalb des Baums gesucht. Dazu wird die Funktion CTree::CompareItems verwendet.
Parameter
[in]itemPointer auf ein CTreeItem Element
Rückgabe
Wird das Element im Baum gefunden, gibt die Funktion einen Pointer auf das Baum-Element zurück. Falls nicht, wird NULL zurückgegeben und der Fehlercode 421 gesetzt.
CTreeItem * ppl6::CTree::FindOrAdd ( CTreeItem item)
Beschreibung:
Mit dieser Funktion wird ein Element innerhalb des Baums gesucht. Dazu wird die Funktion CTree::CompareItems verwendet. Wird es gefunden, wird der Pointer auf das Element zurückgeliefert. Wird es nicht gefunden, wird automatisch ein neues Element angelegt und dessen Pointer zurückgeliefert.
Parameter
[in]itemPointer auf ein CTreeItem Element
Rückgabe
Pointer auf das gefundene oder neu angelegte Element, oder NULL, wenn ein Fehler aufgetreten ist.
CTreeItem * ppl6::CTree::GetCurrent ( CTreeWalker walk) const
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.
CTreeItem * ppl6::CTree::GetCurrent ( ) const
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.
CTreeItem * ppl6::CTree::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
CTreeItem * ppl6::CTree::GetFirst ( CTreeWalker walk) const
CTreeItem * ppl6::CTree::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
CTreeItem * ppl6::CTree::GetLast ( CTreeWalker walk) const
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
CTreeItem * ppl6::CTree::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.
CTreeItem * ppl6::CTree::GetNext ( CTreeWalker walk) const
CTreeItem * ppl6::CTree::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.
CTreeItem * ppl6::CTree::GetPrevious ( CTreeWalker walk) const
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.
CTreeItem * ppl6::CTree::GetRootNode ( ) const
Beschreibung:
Diese Funktion liefert einen Pointer auf den obersten Knoten des Baums.
Rückgabe
CTreeItem Pointer auf Root-Knoten. Ist der Baum leer, wird NULL zurückgegeben und der Fehlercode 347 gesetzt.
void ppl6::CTree::Graphviz ( CString s,
CTreeItem node,
int  tiefe 
) const
private

Diese Funktion wird intern rekursiv aufgerufen, um einen Graphen zu erstellen, der mit Hilfe von graphviz (dot) grafisch dargestellt werden kann.

Parameter
[in]sString, in dem der Code gespeichert werden soll
[in]nodeDer Knoten, bei dem begonnen werden soll.
[in]tiefeDie Tiefe des Baums
Seit
Eingeführt mit PPL 6.2.6
void ppl6::CTree::Graphviz ( CString s,
CTreeItem node = NULL 
) const

Diese Funktion erzeugt einen textuellen graphen, der mit Hilfe von graphviz (dot) grafisch dargestellt werden kann.

Parameter
[in]sString, in dem der Code gespeichert werden soll
[in]nodeDer Knoten, bei dem begonnen werden soll. Bei Angabe von NULL (Default) wird mit dem root-Knoten begonnen.
Seit
Eingeführt mit PPL 6.2.6
void ppl6::CTree::ListNodes ( CCallback callback,
CTreeItem node 
) const
private
int ppl6::CTree::ListNodes ( CCallback callback) const
Beschreibung:
Parameter
callbackPointer auf eine von CpplCallback abgeleitete Klasse
Rückgabe
Die Funktion gibt im Erfolgsfall true (1) zurück, im Fehlerfall false (0). Ein Fehler kann nur auftreten, wenn der Paramater auf NULL zeigt oder der Baum leer ist.
Bemerkungen
Die Callbackfunktion bekommt das aktuelle Element als void* übergeben
int ppl6::CTree::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::CTree::PrintNodes ( CTreeItem node = NULL) const
void ppl6::CTree::Reset ( )
Beschreibung:
Mit dieser Funktion wird der interne Pointer zurückgesetzt, der für die Walk-Funktionen GetNext und GetPrevious verwendet wird.
void ppl6::CTree::Reset ( CTreeWalker walk) const
Beschreibung:
Mit dieser Funktion wird der CTreeWalker zurückgesetzt, der für die Walk-Funktionen GetNext und GetPrevious verwendet wird.
CTreeItem * ppl6::CTree::Rotate ( CTreeItem kn)
private
void ppl6::CTree::SwapNodes ( CTreeItem item1,
CTreeItem item2 
)
private
void ppl6::CTree::UpDelete ( CTreeItem node)
private
void ppl6::CTree::UpInsert ( CTreeItem node)
private
int ppl6::CTree::Validate ( )
Beschreibung:
Diese Funktion kann aufgerufen werden, um die Integrität des Baumes zu überprüfen. Sie hangelt sich durch den kompletten Baum und überprüft für jeden Knoten, ob die Verbindungen (left, right, parent) sowie die Balance in Ordnung sind. Außerdem wird die tatsächliche Anzahl Knoten ermittelt, die mit dem Sollwert übereinstimmen muß.
Rückgabe
Wird ein Fehler festgestellt, wird eine Beschreibung auf STDOUT ausgegeben und die Funktion gibt false (0) zurück. Wird kein Fehler festgestellt, gibt die Funktion true (1) zurück.
Seit
Die Funktion wurde in Version 6.2.0 eingeführt.

Dokumentation der Datenelemente

ppl6::CTree::count
private
ppl6::CTree::current
private
ppl6::CTree::root
private
ppl6::CTree::stack
private
ppl6::CTree::stack_height
private

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