Obwohl wir gesagt haben, dass die Elemente in einer Menge sozusagen „ohne innere Ordnung frei herumliegen“, ordnet die Implementierung der Klasse set alle Elemente in einen Suchbaum ein, um ein bestimmtes Element möglichst schnell suchen zu können. Abbildung 2.26 zeigt einen solchen Suchbaum für die Kundendatei Customers01.txt.

Abbildung 2.26. Ein Suchbaum

In einem solchen Baum können Elemente besonders schnell gefunden werden. Für jeden Knoten gilt nämlich: Alle Nachfahren im linken Teilbaum sind „kleiner“, alle im rechten Teilbaum „größer“. Um ein Element x im Baum zu finden, startet die Suche in der Wurzel und vergleicht x mit der Wurzel. Ist x gleich der Wurzel, so endet die Suche. Ist x kleiner, verzweigt die Suche in den linken Teilbaum, ist x größer, in den rechten. So steigt die Suche im Baum nach unten, bis sie entweder x findet, oder in einem Blatt stehen bleibt (und x als nicht zur Menge gehörig erkennt). Die Suche ist deswegen besonders schnell, weil ein solcher Baum bei n gespeicherten Elemente immer einer Tiefe von ungefähr log(n) hat, wenn er zusätzlich noch balanciert ist, d. h., wenn er die Bedingung erfüllt, dass in jedem linken Unterbaum eines Knotens genauso viele Knoten liegen wie in jedem rechten Unterbaum.

Eine unabdingbare Voraussetzung für den Aufbau eines solchen Suchbaums ist, dass je zwei Elemente hinsichtlich ihrer „Größe“ verglichen werden können. Es muss also eine Ordnung auf den Elementen geben.

Dabei bedeutet lineare Ordnung einer Menge, dass alle Elemente paarweise mit einer bestimmten Ordnungsrelation „<=“ verglichen werden können. Dabei muss für alle Elemente x, y und z der Menge gelten:

In LEDA realisiert eine Funktion

int f(const T&, const T&);

eine lineare Ordnung auf einem Typ T, wenn es eine eine lineare Ordnung <= auf T gibt, so dass für alle x und y im Wertebereich von T gilt:

Die Klasse set verlangt als Typparameter einen so genannten linear geordneten Typ. Gemäß der LEDA-Regel „Anforderungen an linear geordnete Typen“ ist das ein Typ, für den eine Funktion

int compare(const T&, const T&);

definiert ist (mit genau diesem Namen!), die eine lineare Ordnung im obigen Sinne realisiert. Mit anderen Worten: Es gibt eine Funktion compare(), mit der jeweils zwei Objekte vom Typ T verglichen und in eine Ordnungsrelation gebracht werden können.

Wenn compare(x,y) für zwei Objekte x und y eine 0 zurückliefert, so heißen diese Objekte vergleichs-äquivalent oder einfach äquivalent.

Die Implementierung der Klasse set benötigt diese Funktion compare(), um die ihr ausgehändigten Werte des Typs T in einen Suchbaum einordnen zu können. Das macht klar, warum die Ausgabe der vorigen Programme geordnet war: Die Elemente wurden gemäß ihrer Ordnung im Suchbaum ausgegeben; eine einfache, rekursive Funktion genügt, um den Suchbaum zu durchwandern.

Einige Datenstrukturen von LEDA können nur solche linear geordnete Typen speichern. Beispiele solcher Datenstrukturen sind neben set die Klassen dictionary, d_array, p_queue und sortseq.

Bisher haben wir in set nur Strings und ganze Zahlen verwaltet. Glücklicherweise hat LEDA für die Klasse string schon eine entsprechende Funktion

int compare(const string&, const string&);

vordefiniert. Ebenso ist für jeden der Typen char, short, int, long, float, double, integer, rational, bigfloat, real und point eine Funktion compare() bereits vordefiniert, die die so genannte Default-Ordnung realisiert. Die Default-Ordnung ist für die numerischen Typen die gewöhnliche <=-Beziehung, für Strings die lexikographische Ordnung und für Punkte die lexikographische Ordnung der Kartesischen Koordinaten. Für alle anderen Typen gibt es jedoch keine vordefinierte Default-Ordnung.

Was nun, wenn wir uns einen eigenen Datentyp T bauen und Objekte davon in einem set abspeichern wollen? Dann müssen wir uns eine eigene Funktion compare(const T&,const T&) schreiben, die eine lineare Ordnung auf T realisiert.

Dazu ein Beispiel: Angenommen, unsere Daten bestehen aus einem Verbundtyp pair von Punkten in der Ebene (mit ganzzahligen Koordinaten), die wir in einem set verwalten wollen. Wir benötigen also eine Funktion

int compare(const pair&, const pair&);

	Wichtig
	Die Funktion compare() muss immer in den Namensraum leda eingeordnet sein. Ist y die Kopie eines Wertes x vom Typ T, so muss compare(x, y) == 0 gelten.

Des Weiteren benötigen wir die 5 Funktionen, die wir in Abschnitt 2.3.5 kennen gelernt haben; diese werden gemäß der Regel „Anforderungen an Typparameter“ von jedem Typparameter benötigt.

#include <istream>

class pair {
private:
  int  x;
  int  y;

public:
 pair() { x = y = 0; }
 pair(const pair& p) { x = p.x; y = p.y; }
 pair& operator=(const pair& p) {
       if(this != &p) { x = p.x; y = p.y; }
       return *this;
       }
 friend std::istream& operator>> (std::istream& is, pair& p) 
   { is >> p.x >> p.y; return is; }
 friend std::ostream& operator<< (std::ostream& os, const pair& p) 
   { os << p.x << " " << p.y; return os; }
 
 pair(int a, int b) { x = a;  y = b; }

 int get_x() const { return x; }
 int get_y() const { return y; }
};

namespace leda {
int compare(const pair& p, const pair& q)
{
  if (p.get_x() < q.get_x()) return  -1;
  if (p.get_x() > q.get_x()) return   1; 
  if (p.get_y() < q.get_y()) return  -1;
  if (p.get_y() > q.get_y()) return   1;
  return 0;
}
};

Wir definieren uns hier eine Funktion compare(const pair&, const pair&), die eine lineare Ordnung auf den Punkten bereitstellt. Sie vergleicht dazu die x- und y-Koordinaten der Punkte (die Kartesischen Koordinaten), wobei den x-Koordinaten Vorrang eingeräumt wird. Ein Punkt (a,b) liegt also in der Ordnung vor einem Punkt (c,d), wenn a < b gilt, oder wenn a = b ist und c < d. Um auf die privaten Member der Klasse pair zugreifen zu können, benutzt sie deren get-Methoden.

Jetzt können wir eine Menge von solchen Punkten definieren:

set<pair> S;

Tipp

Wenn ein LEDA-Programm scheinbar ohne einen ersichtlichen Grund in einer Methode eines Containertyps wie z. B. d_array abstürzt, so liegt das oft daran, dass dieser Containertyp einen benutzer-definierten Typ T verwaltet, dessen compare()-Funktion fehlerhaft ist, weil sie nicht wirklich eine lineare Ordnung realisiert. Der Typ T ist dann nicht wirklich linear geordnet und kann somit nicht als Typparameter verwendet werden! Es kann z. B. sein, dass compare() für manche Objekte x und y sowohl x < y, als auch y < x wertet (Verletzung der Anti-Symmetrie) oder die Objekte x, y und z als x < y, y < z, z < x anordnet (Verletzung der Transitivität). Siehe hierzu auch Übung 18

Um eine Verwendung einer solchen Klasse aufzuzeigen, implementieren wir den TORWAT-Algorithmus zum Erzeugen fraktaler Mengen. Er ist in [10] beschrieben und liefert Abbildungen wie Abbildung 2.27.

Abbildung 2.27. Eine fraktale Menge

Diese Menge wurde durch den TORWAT-Algorithmus erzeugt. Der Name setzt sich zusammen aus „Torkeln“ und „fraktalem Wachstum“.

Der Algorithmus arbeitet wie folgt:

Um die Menge zu verwalten, benutzen wir ein set<pair> wie eben definiert. Da wir hier sehr oft testen, ob ein bestimmter Punkt zur Menge gehört, die Menge selbst sich aber nicht oft ändert und insgesamt klein bleibt, ist set die Struktur der Wahl, um die Punkte zu verwalten.

#include <LEDA/set.h>
#include <LEDA/random_source.h>
#include <cmath>
#include "pair.h"
#include "TORWAT_window_system_code.h"

using leda::set;
using leda::random_source;

enum direction { LEFT, RIGHT, UP, DOWN };

random_source Totter(LEFT,DOWN);


// create a random point on circle C(0,100)
void new_start_point(int *x, int *y) {
  double angle;
  Totter >> angle; // use the source to create a random double
  angle *= 2*3.1415729;
  *x = int(std::cos(angle) * 100);
  *y = int(std::sin(angle) * 100);
}


// do random step in one of the 4 directions
void move(int *x, int *y) {
  int dir;
  Totter >> dir; // use the source to create a random direction

  switch(dir) {
  case LEFT:  (*x)--; break;    
  case RIGHT: (*x)++; break;    
  case  UP:   (*y)++; break;    
  case DOWN:  (*y)--; break;    
  }             
}


// is point inside circle C(0,100)?
bool in_circle(int x, int y) {
  int square_dist = x * x  +  y * y;
  if(square_dist > 10001) return false;
  return true;
}


int main() {

  init_window_system(); // code left out here

  set<pair> FractalSet;

  FractalSet.insert(pair(0,0));

  set_pixel(0,0);  // code left out here

  int points_in_set = 0;

  while(points_in_set < 2000) {
    int cur_x, cur_y; // coordinates of current point

    new_start_point(&cur_x,&cur_y);

    while(in_circle(cur_x,cur_y)) {

      move(&cur_x,&cur_y);

      if(FractalSet.member(pair(cur_x-1,cur_y))
         || FractalSet.member(pair(cur_x+1,cur_y))
         || FractalSet.member(pair(cur_x,cur_y-1))
         || FractalSet.member(pair(cur_x,cur_y+1))) 
        {
          // current point is a neighbour point of the set
          FractalSet.insert(pair(cur_x,cur_y));
          set_pixel(cur_x,cur_y);
          points_in_set++;
          std::cout << "Points in set:" << points_in_set << std::endl;
          break;
        }
    }
  }
  clean_up_window_system(); // code left out here
}

Den Code für die grafische Oberfläche und das Zeichnen einzelner Punkt haben wir hier in die Funktionen init_window_system(), set_pixel() und clean_up_window_system() ausgelagert, weil er nicht von Interesse ist. Es sei aber gesagt, dass wir das Grafiksystem von LEDA zum Erzeugen der Abbildung benutzt haben.

Um einen zufälligen Punkt auf dem Kreisrand zu erzeugen, berechnen wir einen zufälligen Winkel im Bogenmaß. Dazu erzeugen wir zunächst einen zufälligen double-Wert zwischen 0 und 1. Jede random_source erzeugt eine solche Zahl, wenn das zweite Argument des Operators >> eine Variable vom Typ double ist, unabhängig vom Modus und der eingestellten Präzision oder Intervallbreite. Daher kommen wir in diesem Programm mit nur einer random_source aus. Die Polarkoordinaten aus erzeugtem Winkel und Radius 100 wandeln wir dann mittels sin() und cos() in Kartesische Koordinaten um.

In manchen Situationen ist es nützlich, mehr als nur eine lineare Ordnung auf einem Typ T zu besitzen. Beispielsweise könnten wir zwei Mengen S1 und S2 mit Typparameter pair verwalten wollen; in S1 sollen die Paare nach der Darstellung der Punkte in Kartesischen Koordinaten geordnet sein, in S2 aber nach der Darstellung in Polarkoordinaten (s. hierzu auch Übung 19). S1 können wir wie oben durch

set<pair> S1;

definieren, aber wie können wir S2 definieren? Schließlich sind wir ja an die syntaktische Konvention gebunden, dass die Funktion, die die lineare Ordnung definiert, den Namen compare() trägt!

Hierfür gibt es zwei Lösungen.^[29] Angenommen, die Funktion polar_compare() vergleicht Objekte vom Typ pair hinsichtlich deren Darstellung in Polarkoordinaten. Dann kann diese Funktion dem Konstruktor von set als zusätzliches Argument übergeben werden:

set<pair> S2(polar_compare);

Diese Möglichkeit besteht für jeden Containertyp, der einen linear geordneten Typparameter erwartet (für den Typ der Elemente bzw. des Schlüssels).

	Anmerkung
	Diese Aussage ist für die Version 4.4 von LEDA unzutreffend. Noch nicht jeder solche Containertyp besitzt einen solchen Konstruktor, auch die Klasse set noch nicht. Dies soll sich aber in einer der nächsten Versionen ändern; dann werden alle diese Konstruktoren zur Verfügung stehen.

Die zweite Möglichkeit besteht darin, einen zu pair äquivalenten Typ mit einer anderen linearen Ordnung zu definieren. Die Anweisungsfolge

DEFINE_LINEAR_ORDER(pair, polar_compare, polar_pair);
set <polar_pair> S2;

definiert zuerst durch das Makro DEFINE_LINEAR_ORDER einen Typ polar_pair, der zum Typ pair äquivalent ist, dessen lineare Ordnung aber durch die Funktion polar_compare() gegeben ist; jedes polar_pair kann einem pair zugewiesen werden und umgekehrt. Danach kann der Typ polar_pair als Typparamter eines set verwendet werden.

Mehr Informationen zu linear geordneten Typen und linearen Ordnungen findet man auf der entsprechenden Manualseite.