Appendix B. The golden LEDA rules

The following rules must be adhered to when programming with LEDA in order to write syntactically and semantically correct and efficient LEDA programs. The comprehension of most of the rules is eased by the categorization of the LEDA types given in Figure A.1.

Every rule is illustrated in Section “Code examples for the LEDA rules” by one or more code examples.

The LEDA rules in detail

(Definition with initialization by copying) Definition with initialization by copying is possible for every LEDA type. It initializes the defined variable with a copy of the argument of the definition. The next rule states precisely what a copy of a value is.
(Copy of a value) Assignment operator and copy constructor of LEDA types create copies of values. This rule defines recursively what is meant by the notion “copy of a value”.
1. A copy of a value of a primitive type (built-in type, pointer type, item type) is a bitwise copy of this value.
2. A value x of a simple-structured type is a set or a sequence of values, respectively.
  A copy of x is a componentwise copy of all constituent values of this set or this sequence, respectively.
3. A value x of an item-based, structured type is a structured collection of values.
  A copy of x is a collection of new values, each one of which is the copy of a value of x, the original. The combinatorical structure imposed to the new values is isomorphic to the structure of x, the original.
(Equality and identity) This rule defines when two objects x and y are considered as equal and identical, respectively.
1. For objects x and y of a dependent item type, the equality predicate x==y means equality between the values of these objects.
2. For objects x and y of an independent item type T, the equality predicate x==y is defined individually for each such item type. In the majority of cases it means equality between the values of x and y, but this is not guaranteed for every type.
  Provided that the identity predicate
```
bool identical(const T&, const T&);
```
  is defined on type T, it means equality between the values of these objects.
3. For objects x and y of a structured type the equality predicate x==y means equality between the values of these objects.
(Illegal access via an item) It is illegal to access a container that has been destroyed via an item, or to access a container via the item nil.
(Initialization of attributes of an independent item type) The attributes of an independent item type are always defined. In particular, a definition with default initialization initializes all attributes. Such a type may specify the initial values, but it need not.
(Specification of the structure to be traversed in forall-macros) The argument in a forall-macro that specifies the structure to be traversed should not be a function call that returns this structure, but rather an object by itself that represents this structure.
(Modification of objects of an item-based container type while iterating over them) An iteration over an object x of an item-based container type must not add new elements to x. It may delete the element that the iterator item points to, but no other element. The values of the elements may be modified without any restrictions.

(Requirements for type parameters) Every type parameter T must implement the following functions:

a default constructor	`T::T()`
a copy constructor	`T::T(const T&)`
an assigment operator	`T& T::operator = (const T&)`
an input operator	`istream& operator >> (istream&, T&)`
an output operator	`ostream& operator << (ostream&, const T&)`

(Requirements for linearly ordered types) In addition to the Requirements for type parameters a linearly ordered type must implement
a compare function int compare(const T&, const T&)

Here, for the function compare() the following must hold:
1. It must be put in the namespace leda.
2. It must realize a linear order on T.
3. If y is the copy of a value x of type T, then compare(x,y) == 0 must hold.
(Requirements for hashed types) In addition to the Requirements for type parameters a hashed type must implement
a hash function int Hash(const T&)
an equality operator bool operator == (const T&, const T&)

Here, for the function Hash() the following must hold:
1. It must be put in the namespace leda.
2. For all objects x and y of type T: If x == y holds, then so does Hash(x) == Hash(y).
For the equality operator operator==() the following must hold:
1. It defines an equivalence relation on T.
2. If y is a copy of a value x of type T, then x == y must hold.
(Requests for numerical types) In addition to the Requirements for type parameters a numerical type must offer the arithmetical operators operator+(), operator-(), and operator*(), as well as the comparison operators operator<(), operator<=(), operator>(), operator>=(), operator==(), and operator!=().

Code examples for the LEDA rules

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

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

```
array<int> A, B;
// ...fill A with some elements...
B = A;
```
Now B contains the same number of integers as A, in the same order, with the same values.
However, A and B do not contain the same objects:
```
int* p = A[0];
int* q = B[0];
p == q; // false
```
A and B are different objects:
```
A == B; // false
```
```
list<int> L, M;
list_item it1, it2;
L.push(42);
L.push(666);
M = L;
```
L and M now both contain the numbers 666 and 42. These numbers are not the same objects:
```
it1 = L.first();
it2 = M.first();
it1 == it2; // false
```
L and M are different objects as well:
```
L == M; // false
```

In the following assignment the rules c, b, and a are applied recursivley (in this order):

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

a hash function	`int Hash(const T&)`
an equality operator	`bool operator == (const T&, const T&)`


Appendix A. Categorization of the LEDA data types		Bibliography