Genericity

Definition

An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is generic if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.

Remark: Typically, there are requirements on the open types. This means an open type must offer some methods with prescribed syntax and semantics. Quite different concepts to formulate and ensure syntactical requirements are implemented in the various programming languages that support genericity.

Comparison

A comparison on a finite or infinite set [math]\displaystyle{ S }[/math] is a binary relation [math]\displaystyle{ c:S\times S \rightarrow \{ -1,0,+1\} }[/math] with the following properties:

• [math]\displaystyle{ c(x,x) = 0 }[/math] for all [math]\displaystyle{ x \in S }[/math] (reflexivity),
• [math]\displaystyle{ c(x,y)=-c(y,x) }[/math] for all [math]\displaystyle{ x,y \in S }[/math] (anti-symmetry), and
• [math]\displaystyle{ (c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1 }[/math] for all [math]\displaystyle{ x,y,z \in S }[/math] (transitivity).

For convenience, we write [math]\displaystyle{ x\lt y }[/math] in case [math]\displaystyle{ c(x,y)=1 }[/math], [math]\displaystyle{ x\le y }[/math] in case [math]\displaystyle{ c(x,y)\ge 0 }[/math], and so on.

Remark

Note that [math]\displaystyle{ c(x,y)=0 }[/math] does not imply [math]\displaystyle{ x=y }[/math]. If [math]\displaystyle{ c(x,y)=0 }[/math] actually implies [math]\displaystyle{ x=y }[/math] for all [math]\displaystyle{ x,y }[/math], such a binary relation is usually called a total or linear order - as opposed to partial orders, in which [math]\displaystyle{ c(x,y)=0 }[/math] is possible for [math]\displaystyle{ x\neq y }[/math]. In the last case, we say [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are incomparable.