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. A typical requirement is that a comparison as defined below is given for that type.

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-commutativity), 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 pairs of elements may be incomparable.