2.8.3. Linearly ordered types

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 IP-addresses 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?

Balanced search trees

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

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.

Linear orders

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:

  • x <= x (reflexivity)
  • x <= y and y <= z implies x <= z (transitivity)
  • x <= y or y <= x (anti-symmetry). If both relations hold, x and y are called equivalent. If, however, y <= x does not hold, x is called strictly smaller than y and one writes x < y for that.

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 equivalent
  • f(x,y)>0, if x > y

Linearly ordered types

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.

Making a type of our own linearly ordered

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

Filename: pair.h
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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]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.

An example: Creating fractal sets

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

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:

  1. Insert the point (0.0) into the set.

  2. As long as the set does not consist of 2000 points yet, do the following:

    1. Create a random point (with integral coordinates) on the edge of the circle with the center (0.0) and radius 100.

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

Filename: TORWAT.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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().

Several linear orders on a type

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

Further information

More information about linearly ordered types and linear orders can be found on the corresponding manual page.

Exercises

Exercise 19.

Why does the following function compare() not realize a linear order on the type pair and therefore does not make it a linearly ordered type?

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

Exercise 20.

Another possibility for defining a linear order on the set of the points of the plane is based on the representation by means of polar coordinates: Every point p is represented by a pair (r,φ), in which r is the distance to the origin O and φ the angle between the line segment [O,p] and the x-axis. Points are compared with each other as follows:

  • The origin O is smaller than every other point.
  • A point p=(r,φ) is smaller than a point q=(s,χ), if r < s, or if r = s and φ < χ.
  • p and q are equal if r = s and φ = χ.

Write a function compare() that realizes a linear order on the above class pair in accordance with the order relation given by these rules.

Exercise 21.

When performing a lexicographical comparison, the function compare(), as it is predefined for string, does not take the sorting rules for the special characters of the German language into consideration: “ä” shall be valued as “ae”, “ö” as “oe”, “ü” as “ue”, and “ß” as “ss”.

Write a function german_compare() that takes into account these rules in the comparison of two strings, and insert some strings with German special characters into a set, ordered in accordance with the function german_compare().

Exercise 22.

The TORWAT algorithm introduced above is extremely inefficient. It is much more sensible to let the set grow “from inside”, that is, to select a point of the set in every iteration at random and to “attach” another point to this point at one of the 8 adjacent positions if this is still possible. Implement this more efficient procedure.

Unfortunately, the method choose() of the class set is not suitable for this since it does not guarantee that an element is selected from the set at random. You need an additional data structure here in which the points are stored and from which a point can be selected at random. Which one offers great services here?



[30] Actually, there are three solutions since one can also derive a class polar_pair from pair and define compare() appropriately on that class.




Imprint-Dataprotection