2.8.3. Linear geordnete Typen

Lernziele

Linear geordnete Typen
Die Funktion compare()
LEDA-Regel 15

Wenn wir uns die Ausgabe der Programme zur eindeutigen Ausgabe der IP-Adressen und der Heiratsvermittlung genau ansehen, stellen wir fest, dass die Strings lexikographisch geordnet aufgelistet sind. Ist das ein Zufall, oder gibt es einen Grund für diese Ordnung?

Balancierte Suchbäume

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

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.

Lineare Ordnungen

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:

  • x <= x (Reflexivität)
  • x <= y und y <= z impliziert x <= z (Transitivität)
  • x <= y oder y <= x (Anti-Symmetrie). Wenn beides gleichzeitig zutrifft, heißen x und y äquivalent. Wenn dagegen nicht y <= x gilt, heißt x echt kleiner als y und man schreibt dafür x < y.

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:

  • f(x,y) < 0, wenn x < y
  • f(x,y) == 0, wenn x und y äquivalent sind
  • f(x,y) > 0, wenn x > y

Linear geordnete Typen

Die Klasse set verlangt als Typparameter einen so genannten linear geordneten Typ. Nach LEDA-Regel 15 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.

Einen eigenen Typ linear geordnet machen

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.

[Important] Wichtig

Die Funktion compare() muss immer in den Namensraum leda eingeordnet sein.

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&);

Des Weiteren benötigen wir die 5 Funktionen, die wir in Abschnitt 2.3.5 kennen gelernt haben; diese werden gemäß LEDA-Regel 14 von jedem Typparameter benötigt.

Filename: pair.h
#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;
[Tip] 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

Ein Beispiel: Fraktale Mengen erzeugen

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

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:

  1. Nimm den Punkt (0,0) in die Menge auf.

  2. Solange die Menge noch nicht aus 2000 Punkten besteht, mache Folgendes:

    1. Erzeuge einen zufälligen Punkt (mit ganzzahligen Koordinaten) auf dem Rand des Kreises mit dem Mittelpunkt (0,0) und Radius 100.

    2. Mache mit dem Punkt einen Zufälligen Spaziergang (Random Walk), bis er entweder den Kreis verlässt oder Nachbar eines Punktes der Menge ist. Im zweiten Fall nimm den Punkt in die Menge auf. Der Random Walk führt in jedem Schritt um 1 nach links, rechts, oben oder unten.

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.

Filename: TORWAT.C
#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.

Mehrere lineare Ordnungen auf einem Typ

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).

[Note] Anmerkung

Diese Aussage ist für die augenblickliche 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.

Weitere Informationen

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

Übungen

Übung 18.

Warum realisiert folgende Funktion compare() keine lineare Ordnung auf dem Typ pair und macht diesen daher nicht zu einem linear geordneten Typ?

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

Eine andere Möglichkeit, eine lineare Ordnung auf der Menge der Punkte der Ebene zu definieren, geht von deren Darstellung mittels Polarkoordinaten aus: Jeder Punkt p wird durch ein Paar (r,φ) dargestellt, wobei r der Abstand zum Ursprung O und φ der Winkel zwischen dem Liniensegment [O,p] und der x-Achse ist. Punkte werden folgerndermaßen miteinander verglichen:

  • Der Ursprung O ist kleiner als jeder andere Punkt.
  • Ein Punkt p=(r,φ) ist kleiner als ein Punkt q=(s,χ), wenn r < s ist, oder wenn r = s und φ < χ ist.
  • p und q sind gleich, wenn r = s und φ = χ ist.

Schreiben Sie eine Funktion compare(), die auf obiger Klasse pair eine lineare Ordnung gemäß der durch diese Regeln gegebenen Ordnungsrelation realisiert.

Übung 20.

Die für string vordefinierte Funktion compare() zieht beim lexikographischen Vergleich nicht die Sortierregeln für die Sonderzeichen der deutschen Sprache in Betracht: Ein „ä“ wird wie „ae“ gewertet, „ö“ wie „oe“, „ü“ wie „ue“ und „ß“ wie „ss“.

Schreiben Sie eine Funktion german_compare(), die diese Regeln beim Vergleich zweier Strings berücksichtigt, und verwalten Sie einige Strings mit deutschen Sonderzeichen in einem set, geordnet gemäß der Funktion german_compare().

Übung 21.

Der oben vorgestellte TORWAT-Algorithmus ist extrem uneffizient. Viel sinnvoller ist es, die Menge „von innen“ wachsen zu lassen, d. h., in jeder Iteration einen Punkt der Menge zufällig auszuwählen und an diesen Punkt einen anderen Punkt an einer der 8 benachbarten Positionen „anzubauen“, falls dies noch möglich ist. Implementieren Sie dieses effizientere Verfahren.

Die Methode choose() der Klasse set ist dafür leider nicht geeignet, da sie nicht garantiert, dass ein Element zufällig aus der Menge ausgewählt wird. Sie benötigen hier eine weitere Datenstruktur, in der die Punkte zusätzlich gespeichert werden, und aus der ein Punkt zufällig ausgewählt werden kann. Welche bietet sich hier an?



[29] Eigentlich drei, denn man kann ja auch eine Klasse polar_pair von pair ableiten und auf dieser compare() geeignet definieren.