Learning objectives
Linearly ordered types 
The function compare() 
The LEDA rule “Requirements for linearly ordered types” 
If we closely look at the output of the programs for the output of the unique IPaddresses and the marriage bureau, we notice that the strings are listed in lexicographic order. Is this by chance or is there a reason for this order?
Although we said that the elements, so to speak,
“float around freely in a set without having any inner
order”, the implementation of the class
set
arranges all elements in order into
a search tree to be
able to search as fast as possible for a certain
element. Figure 2.26 shows such a
search tree for the customer file
Customers01.txt
.
Elements can be found particularly fast in such a tree. To every node the following applies: All descendants in the left partial tree are “smaller”, all nodes in the right partial tree “larger”. To find an element x in the tree, the search starts in the root and compares x to the root. If x equals the root, the search ends immediately. If x is smaller, the search branches into the left partial tree, if x is larger, into the right one. So the search in the tree descends to below until it either finds x or stops in a leaf (thereby recognizing x as not belonging to the set). The search is particularly fast because such a tree always has a depth of approximately log(n) with n elements stored if, in addition, it is balanced, that is, if it satisfies the condition that just as many nodes lie in every left subtree of a node as in every right subtree.
It is an indispensable prerequisite for the construction of such a search tree that each two elements can be compared with regard to their “size”. So there must be an order on the elements.
A linear order of a set means that all elements can be compared in pairs by a certain order relation “<=”. For all elements x, y, and z of the set the following must hold:
In LEDA, a function
int f(const T&, const T&);
realizes a linear order on a type T
if there is a linear
order <= on T so that for all x
and
y
in the domain of T
the following holds:
f(x,y)<0
, if x < y
f(x,y)==0
, if x
and y
are equivalentf(x,y)>0
, if x > y
The class set
requires a
socalled linearly
ordered type as type parameter. In accordance with
the LEDA rule “Requirements for linearly ordered types” this is a type
for which a function
int compare(const T&, const T&);
is defined (with exactly this name!) that realizes a linear order in
the above sense. In other words: There is a function
compare()
with which each two objects of type
T
can be compared and put into an order relation.
If compare(x,y)
returns a 0 for two
objects x
and y
, these
objects are called compareequivalent or
simply equivalent.
The implementation of the class
set
needs this function
compare()
to be able to arrange the
values of the type T
handed over to it in order
into a search tree. This makes clear why the output of the
previous programs was ordered: The elements were output in
accordance with their order in the search tree; a simple,
recursive function suffices to traverse the search
tree.
Some data structures of LEDA can store only such
linearly ordered types. Examples of such data structures,
besides set
, are the classes dictionary
,
d_array
,
p_queue
and sortseq
.
Until now, we have held only strings and integer numbers
in set
. Fortunately, for the class
string
, LEDA already has a
corresponding function
int compare(const string&, const string&);
predefined. Likewise, for each of the types char
,
short
, int
, long
,
float
, double
,
integer
, rational
,
bigfloat
, real
and
point
a function compare()
is already predefined realizing the socalled default order. The
default order is the ordinary <= relation for the numeric types, the
lexicographical order for strings, and for points the lexicographical
order of the Cartesian coordinates. There is no predefined default
order for all other types, however.
What if we want to build a data type
T
of our own and store objects of this type in a
set
? We then must write a function
compare(const T&,const T&)
of our
own that realizes a linear order on T
.
To give an example: Let us suppose that our data consist
of a compound type pair
of points in
the plane (with integral coordinates), which we want to manage
in a set
. So we need a function
int compare(const pair&, const pair&);
fulfilling the following requirements:
Important  

The function If 
Furthermore we need the 5 functions that we have got to know in Section 2.3.5; in accordance with the rule “Requirements for type parameters”, these functions are needed by every type parameter.
#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; } };
Here we define a function compare(const
pair&, const pair&)
providing a linear
order on the points. For that purpose, it compares the x and
ycoordinates of the points (the Cartesian
coordinates), in which priority is given to the
xcoordinates. So a point (a, b) comes before a point (c,d) in
the order, if a < b holds or if a = b and c < d. To
be able to access the private members of the class pair, the
function uses the get
methods of that
class.
We can define a set of such points now:
set<pair> S;
Tip  

If a LEDA program crashes apparently without an
obvious reason in a method of a container type like for example
It may be for example that 
To show an application of such a class, we implement the TORWAT algorithm for creating fractal sets. It is described in [10] and returns figures like Figure 2.27.
The algorithm works as follows:
Insert the point (0.0) into the set.
As long as the set does not consist of 2000 points yet, do the following:
Create a random point (with integral coordinates) on the edge of the circle with the center (0.0) and radius 100.
Make a random walk with the point until either it leaves the circle or becomes a neighbor of a point of the set. Insert the point into the set in the second case. In every step, the random walk moves the point by 1 to the left, to the right, up, or down.
To manage the set, we use a
set<pair>
as just defined. Since
we test very often here whether a certain point belongs to the
set and since the set, however, does not often change and all
in all remains small, set
is the
structure of choice to manage the points.
#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_x1,cur_y))  FractalSet.member(pair(cur_x+1,cur_y))  FractalSet.member(pair(cur_x,cur_y1))  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 }
Here we have sourced out the code for the graphical user
interface and for the drawing of individual points into the
functions init_window_system()
,
set_pixel()
, and
clean_up_window_system()
because it is
not of interest. However, it shall be said that we have used
the graphic system of LEDA for creating the figure.
To create a random point on the edge of the circle, we
calculate a random angle in the radian measure. For this we
first create a random double
value between 0 and
1. Every random_source
creates such a
number if the second argument of the operator
>>
is a variable of type
double
, independently from the mode and the
precision of the interval range set. We therefore get by on
only one random_source
in this
program. We then change the polar coordinates, consisting of
the angle created and the radius 100, into Cartesian
coordinates by means of sin()
and
cos()
.
In some situations it is useful to have more than only
one linear order on a type T
. We could want to
manage two sets S1
and
S2
with type parameter
pair
, for example; in
S1
the pairs shall be ordered according to
the representation of the points in Cartesian coordinates, in
S2
according to the representation in polar
coordinates (see also Exercise 20). We can define
S1
like above by
set<pair> S1;
But how can we define S2
? After all, we are bound
to the syntactic convention that the function that defines the linear
order must bear the name compare()
!
There are two solutions for
this.^{[30]}
Let us suppose that the function
polar_compare()
compares objects of the type
pair
with regard to the representation in polar
coordinates. This function then can be passed to the constructor of
set
as an additional argument:
set<pair> S2(polar_compare);
This possibility exists for every container type that expects a linearly ordered type parameter (for the type of the elements or of the key).
Note  

This statement is incorrect for the current
version 6.2 of LEDA. Not yet every such container type has
such a constructor, neither has the class

The second possibility consists in defining a type
equivalent to pair
with a different
linear order. The sequence of statements
DEFINE_LINEAR_ORDER(pair, polar_compare, polar_pair); set <polar_pair> S2;
first defines a type polar_pair
by the macro
DEFINE_LINEAR_ORDER
; a type that is equivalent to
the type pair
, whose linear order is, however,
given by the function polar_compare()
. Every
polar_pair
can be assigned to a
pair
and viceversa. After these statements
have been executed, the type polar_pair
can be used as a
type parameter of a set
.
More information about linearly ordered types and linear orders can be found on the corresponding manual page.
^{[30] }Actually, there are three solutions since
one can also derive a class polar_pair
from pair
and define
compare()
appropriately on that
class.