Index handler

Representation invariant

This abstract data structure is generic and parameterized by some value type [math]\displaystyle{ \mathcal{V} }[/math]. An object of an implementation of this abstract data structure is repesented by:

1. A positive integral number [math]\displaystyle{ N }[/math].
2. A subset [math]\displaystyle{ I }[/math] of [math]\displaystyle{ \{1,\ldots,N\} }[/math], the currently used indexes.
3. A mapping [math]\displaystyle{ I\rightarrow\mathcal{V} }[/math].

Remarks:

1. This abstract data structure may be viewed as a specific, quite restricted type of map.
2. The returned indexes have to be managed outside this data structure. For example, in Dijkstra and Prim, it might be a good option to make the index a node attribute,

Method

Name: reserve index

Input: A value [math]\displaystyle{ V\in\mathcal{V} }[/math].

Precondition: [math]\displaystyle{ |I|\lt N }[/math].

Return value: One of the indexes not in [math]\displaystyle{ I }[/math].

Postcondition: The returned index is inserted in [math]\displaystyle{ I }[/math] and associated with [math]\displaystyle{ V }[/math].

Method

Name: release index

Input: An integral number [math]\displaystyle{ i }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Postcondition: [math]\displaystyle{ i }[/math] is extracted from [math]\displaystyle{ I }[/math], and the associated value is dropped.

Method

Name: get value

Input: An integral number [math]\displaystyle{ i }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Return value: The value currently associated with [math]\displaystyle{ i }[/math].

Method

Name: change value

Input: An integral number [math]\displaystyle{ i }[/math] and a value [math]\displaystyle{ V\in\mathcal{V} }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Postcondition: The value currently associated with [math]\displaystyle{ i }[/math] is overwritten by [math]\displaystyle{ V }[/math].

Known implementations

1. Index handler with list of unused