Linear Orders

Many data types, such as dictionaries, priority queues, and sorted sequences require linearly ordered parameter types. Whenever a type T is used in such a situation, e.g. in dictionary<T,...>the function

int   compare(const T&, const T&)

must be declared and must define a linear order on the data type T.

A binary relation rel on a set T is called a linear order on T if for all x,y,z in T:

1) x rel x
2) x rel y and y rel z implies x rel z
3) x rel y or y rel x
4) x rel y and y rel x implies x = y

A function int compare(const T&, const T&) defines the linear order rel on T if

$$\mathrm{compare}(x,y)\ \ \cases{ < 0, &if $x$ {\it rel} $y$ ... ... 0, &if $x = y$\cr > 0, &if $y$ {\it rel} $x$ and $x \ne y$}$$

For each of the data types char, short, int, long, float, double, integer, rational, bigfloat, real, string, and point a function compare is predefined and defines the so-called default ordering on that type. The default ordering is the usual $\le$ - order for the built-in numerical types, the lexicographic ordering for string, and for point the lexicographic ordering of the cartesian coordinates. For all other types T there is no default ordering, and the user has to provide a compare function whenever a linear order on T is required.

Example: Suppose pairs of real numbers shall be used as keys in a dictionary with the lexicographic order of their components. First we declare class pair as the type of pairs of real numbers, then we define the I/O operations operator>>and operator<<and the lexicographic order on pair by writing an appropriate compare function.

class pair {
  double  x;
  double  y;

public:
 pair() { x = y = 0; }
 pair(const pair& p) { x = p.x; y = p.y; }


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

 friend int compare(const pair&, const pair&);

};

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

Now we can use dictionaries with key type pair, e.g.,

dictionary<pair,int> D;

Sometimes, a user may need additional linear orders on a data type T which are different from the order defined by compare. In The following example a user wants to order points in the plane by the lexicographic ordering of their cartesian coordinates and by their polar coordinates. The former ordering is the default ordering for points. The user can introduce an alternative ordering on the data type point (cf. section Basic Data Types for Two-Dimensional Geometry) by defining an appropriate comparing function

int   pol_cmp(const point& x, const point& y)
{ /* lexicographic ordering on polar coordinates */ }

Now he has two possibilities:

1.

First he can call the macro

DEFINE_LINEAR_ORDER(point, pol_cmp, pol_point)

After this call pol_point is a new data type which is equivalent to the data type point, with the only exception that if pol_point is used as an actual parameter e.g. in dictionary<pol_point,...>, the resulting data type is based on the linear order defined by pol_cmp. Now, dictionaries based on either ordering can be used.

dictionary<point,int>     D0; // default ordering
dictionary<pol_point,int> D1; // polar ordering

In general the macro call

DEFINE_LINEAR_ORDER(T, cmp, T1)

introduces a new type T1 equivalent to type T with the linear order defined by the compare function cmp.

2.

As a new feature all order based data types like dictionaries, priority queues, and sorted sequences offer a constructor which allows a user to set the internally used ordering at construction time.

dictionary<point,int> D0;          // default ordering
dictionary<point,int> D1(pol_cmp); // polar ordering

This alternative handles the cases where two or more different orderings are needed more elegantly.