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.

Figure 2.26. A search tree

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 sub-tree of a node as in every right sub-tree.

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:

The class set requires a so-called 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 compare-equivalent 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 so-called 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 compare() must always be in the namespace leda. If y is the copy of a value x of the type T, then compare(x, y) == 0 must hold.

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 y-coordinates of the points (the Cartesian coordinates), in which priority is given to the x-coordinates. 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 d_array, this often is due to the fact that this container type manages a user defined type T whose compare()-function is faulty because it does not really realize a linear order. The type T then is not really linearly ordered and therefore cannot be used as a type parameter! It may be for example that compare() values, for some objects x and y, both x < y and y < x (violation of anti-symmetry), or that it orders the objects x, y, and z as x < y, y < z, z < x (violation of transitivity). See also Exercise 19.

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.

Figure 2.27. A fractal set

This set was created by the TORWAT algorithm. The name consists of the German words for “staggers” (“torkelt”) and “grows” (“wächst”).

The algorithm works as follows:

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

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 set. However, this shall change in one of the next versions; all these constructors then will be available.

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 vice-versa. 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.