# 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]S[/math] is a binary relation [math]c:S\times S \rightarrow \{ -1,0,+1\}[/math] with the following properties:

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

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

### Remark

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