Index handler

Abstract view

Representation invariant:

1. There is a positive natural number [math]\displaystyle{ N }[/math].
2. For each object, there is a specific, dynamically changing partition of [math]\displaystyle{ \{1,\ldots,N\} }[/math] into used and unused indexes.
3. For each used index, a value is stored.

Implementation invariant:

1. There is an array [math]\displaystyle{ Indexes }[/math] with index range [math]\displaystyle{ 1,...,N_\text{max} }[/math] and integral components from [math]\displaystyle{ \{1,...,N_\text{max}\} }[/math].
2. There is a set [math]\displaystyle{ U }[/math] (for unused) of natural numbers, which has length [math]\displaystyle{ N_\text{max}-N }[/math] and stores pairwise different numbers from [math]\displaystyle{ \{1,...,N_\text{max}\} }[/math].
3. For each [math]\displaystyle{ i\in\{1,...,N_\text{max}\} }[/math] not in [math]\displaystyle{ Unused }[/math]:
   1. [math]\displaystyle{ Positions[i] }[/math] is the position of one of the [math]\displaystyle{ N }[/math] heap items in [math]\displaystyle{ TheHeap }[/math]. As long as this heap item is stored, [math]\displaystyle{ i }[/math] is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers [math]\displaystyle{ i }[/math] is one-to-one.

Methods

1. If an index is requested, [math]\displaystyle{ U\neq\emptyset }[/math] is a precondition. Then one index is extracted from [math]\displaystyle{ U }[/math] and returned.

1. If an index is given back, it is inserted in [math]\displaystyle{ U }[/math].