Anhang B. Die goldenen LEDA-Regeln

Die folgenden Regeln müssen beim Programmieren mit LEDA eingehalten werden, um syntaktisch und semantisch korrekte und effiziente LEDA-Programme zu schreiben. Das Verständnis der meisten Regeln wird durch die Klassifikation der LEDA-Typen in Abbildung A.1 vereinfacht. Der darauf folgende Abschnitt zeigt für jede Regel ein oder mehrere Code-Beispiele auf.

Die LEDA-Regeln im Einzelnen

(Definition mit Initialisierung durch Kopieren) Definition mit Initialisierung durch Kopieren ist für jeden LEDA-Typ möglich. Sie initialisiert die definierte Variable mit einer Kopie des Argumentes der Definition. Was eine Kopie eines Wertes genau ist, legt die nächste Regel fest.
(Kopie eines Wertes) Zuweisungsoperator und Copy-Konstruktor von LEDA-Typen legen Kopien von Werten an. Diese Regel definiert rekursiv, was unter der Kopie eines Wertes zu verstehen ist.
1. Eine Kopie eines Wertes eines primitiven Typs (eingebauter Typ, Zeigertyp, Item-Typ) ist eine bitweise Kopie dieses Wertes.
2. Ein Wert x eines einfach-strukturierten Typs ist eine Menge bzw. Folge von Werten.
  Eine Kopie von x ist eine komponentenweise Kopie aller einzelnen Werte dieser Menge bzw. Folge.
3. Ein Wert x eines item-basierten, strukturierten Typs ist eine strukturierte Ansammlung von Werten.
  Eine Kopie von x ist eine Ansammlung von neuen Werten, von denen jeder einzelne die Kopie eines Wertes im Original x ist. Die kombinatorische Struktur, die den neuen Werten auferlegt wird, ist isomorph zur Struktur des Originals x.
(Gleichheit und Identität) Diese Regel legt fest, wann zwei Objekte x und y als gleich bzw. identisch gelten.
1. Für Objekte x und y von abhängigem Item-Typ meint das Gleichheitsprädikat x==y die Gleichheit zwischen den Werten dieser Objekte.
2. Für Objekte x und y von unabhängigem Item-Typ T ist das Gleichheitsprädikat x==y individuell für jeden solchen Item-Typ definiert. Meistens meint es Gleichheit zwischen den Werten von x und y, aber das ist nicht für jeden Typ garantiert.
  Sofern das Identitätsprädikat
```
bool identical(const T&, const T&);
```
  auf T definiert ist, meint es die Gleichheit zwischen den Werten dieser Objekte.
3. Für Objekte x und y von strukturiertem Typ meint das Gleichheitsprädikat x==y die Gleichheit zwischen den Werten dieser Objekte.
(Illegaler Zugriff über Item) Es ist illegal, über ein Item auf einen Container zuzugreifen, der zerstört wurde, oder über das Item nil auf einen Container zuzugreifen.
(Initialisierung von Attributen eines unabhängigen Item-Typs) Die Attribute eines unabhängigen Item-Typs sind immer definiert. Im Besonderen initialisiert eine Definition mit Default-Initialisierung alle Attribute. Ein solcher Typ kann die initialen Werte spezifizieren, muss es aber nicht.
(Spezifikation der zu durchlaufenden Struktur in forall-Makros) Das Argument in einem forall-Makro, das die Struktur spezifiziert, über die iteriert wird, sollte kein Funktionsaufruf sein, der die Struktur zurückliefert, sondern vielmehr ein Objekt selbst, das eine Struktur darstellt.
(Verändern von Objekten eines item-basierten Containertyps während einer Iteration darüber) Eine Iteration über ein Objekt x eines item-basiertem Containertyps darf keine neuen Elemente zu x hinzufügen. Sie darf das Element löschen, auf dem das Iterator-Item steht, aber kein anderes Element. Die Werte der Elemente können ohne Beschränkungen geändert werden.

(Anforderungen an Typparameter) Jeder Typparameter T muss die folgenden Funktionen implementieren

einen Default-Konstruktor	`T::T()`
einen Copy-Konstruktor	`T::T(const T&)`
einen Zuweisungs-Operator	`T& T::operator = (const T&)`
einen Eingabe-Operator	`istream& operator >> (istream&, T&)`
einen Ausgabe-Operator	`ostream& operator << (ostream&, const T&)`

(Anforderungen an linear geordnete Typen) Ein linear geordneter Typ muss über die Anforderungen an Typparameter hinaus implementieren
eine Vergleichsfunktion int compare(const T&, const T&)

Für die Funktion compare() muss dabei gelten:
1. Sie muss in den Namensraum leda eingeordnet sein.
2. Sie muss eine lineare Ordnung auf T realisieren.
3. Ist y die Kopie eines Wertes x vom Typ T, so muss compare(x, y) == 0 gelten.
(Anforderungen an gehashte Typen) Ein gehashter Typ muss über die Anforderungen an Typparameter hinaus implementieren
eine Hash-Funktion int Hash(const T&)
einen Gleichheits-Operator bool operator == (const T&, const T&)

Für die Funktion Hash() muss dabei gelten:
1. Sie muss in den Namensraum leda eingeordnet sein.
2. Für alle Objekte x und y des Typs T: Wenn x == y ist, dann auch Hash(x) == Hash(y).
Für den Gleichheitsoperator operator==() muss dabei gelten:
1. Er definiert eine Äquivalenzrelation auf T.
2. Ist y die Kopie eines Wertes x vom Typ T, so muss x == y gelten.
(Anforderung an numerische Typen) Ein numerischer Typ muss über die Anforderungen an Typparameter hinaus die arithmetischen Operatoren operator+(), operator-() und operator*() sowie die Vergleichsoperatoren operator<(), operator<=(), operator>(), operator>=(), operator==() und operator!=() besitzen.

Code-Beispiele für die LEDA-Regeln

string s("Jumping Jack Flash");
string t(s);  // definition with initialization by copying
string u = s; // definition with initialization by copying

stack<int> S;
// ... fill S with some elements
stack<int> T(S); // definition with initialization by copying

1. ```
list_item it1, it2;
// ...
it2 = it1; // it2 now references the same container as it1
```
2. ```
array<int> A, B;
// ...fill A with some elements...
B = A;
```
  Jetzt enthält B dieselbe Anzahl von ganzen Zahlen wie A, in derselben Reihenfolge, mit den gleichen Werten.
  A und B enthalten aber nicht dieselben Objekte:
```
int* p = A[0];
int* q = B[0];
p == q; // false
```
  Die Objekte A und B sind verschieden:
```
A == B; // false
```
3. ```
list<int> L, M;
list_item it1, it2;
L.push(42);
L.push(666);
M = L;
```
  L und M enthalten nun beide die Zahlen 666 und 42. Es handelt sich dabei nicht um dieselben Objekte:
```
it1 = L.first();
it2 = M.first();
it1 == it2; // false
```
  Auch L und M sind verschiedene Objekte:
```
L == M; // false
```
Bei folgender Zuweisung werden die Regeln c, b und a rekursiv (in dieser Reihenfolge) angewendet:
```
list< array<int> > L, M;
// ...fill L with some array<int>s
// each of them filled with some elements...
M = L;
```

list_item it1, it2;
// ...
it2 = it1; // it2 now references the same container as it1
it1 == it2; // true

point p(2.0, 3.0);
point q(2.0, 3.0);
p == q; // true (as defined for class point)
identical(p, q); // false
point r;
r = p;
identical(p, r); // true

list<int> L, M;
// ...fill L with some elements...
M = L; 
L == M; // false

list_item it = L.first();
L.del_item(it);
L.contents(it); // illegal access
it = nil;
L.contents(it); // illegal access

point p(2.0, 3.0); // p has coordinates (2.0, 3.0)
point q; // q has coordinates but it is not known which

edge e;
forall(e, G.all_edges()) // dangerous!
  { ... } 

// do it like this
list<edge> E = G.all_edges();
forall(e, E) 
 { ... }

list_item it;
forall(it, L) {
  L.append(1); // illegal; results in infinite loop
  if(L[it] == 5 ) L.del(it); // legal
  if(L[it] == 6 ) L.del(L.succ(it)); // illegal
  L[it]++; // legal
}

class pair {
public:
 int x, y;

 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;
       }
};

std::istream& operator>> (std::istream& is, pair& p) 
   { is >> p.x >> p.y; return is; }
std::ostream& operator<< (std::ostream& os, const pair& p) 
   { os << p.x << " " << p.y; return os; }

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

namespace leda {
int Hash(const pair& p)
{
  return p.x ^ p.y;
}
};

bool operator == (const pair& p, const pair& q)
{
   return (p.x == q.x && p.y == q.y) ? true : false;
}

eine Hash-Funktion	`int Hash(const T&)`
einen Gleichheits-Operator	`bool operator == (const T&, const T&)`


Anhang A. Klassifizierung der LEDA-Datentypen		Literaturverzeichnis