Dial implementation

General information

Abstract Data Structure: Bounded monotonous priority queue.

Implementation Invariant: An object of "Dial implementation" comprises:

1. A specific maximum span of keys [math]\displaystyle{ S\in\mathbb{N} }[/math],
2. An array [math]\displaystyle{ A }[/math] with index set [math]\displaystyle{ \{0,\ldots,S-1\} }[/math] and sets of keys as components,
3. A current position of the minimum [math]\displaystyle{ P }[/math], which is dynamically changing,
4. An index handler, whose value type is a pointer to an element in a set

of keys All keys at an index of [math]\displaystyle{ A }[/math] are equal. For [math]\displaystyle{ i\in\{0,\ldots,S-1\}\setminus\{P\} }[/math], the value of the keys at position [math]\displaystyle{ i }[/math] is larger than the value of the keys at index [math]\displaystyle{ P }[/math] by exactly [math]\displaystyle{ (S+i-P)\bmod S }[/math].

For each key currently stored in [math]\displaystyle{ A }[/math], the index handler contains a pointer to the corresponding set element.

Methods

1. The minimum keys are found at position [math]\displaystyle{ P }[/math]. The position is increased in the minimum extraction method by 1 modulo [math]\displaystyle{ S }[/math], when the set at position [math]\displaystyle{ P }[/math] becomes empty.
2. A key [math]\displaystyle{ K }[/math] is inserted at index [math]\displaystyle{ (S+K-P)\bmod S }[/math].
3. Decreasing a key value [math]\displaystyle{ K }[/math] to value [math]\displaystyle{ K' }[/math] amounts to removing the key from the set at index [math]\displaystyle{ (S+K-P)\bmod S }[/math] and re-insert it at index [math]\displaystyle{ (S+K'-P)\bmod S }[/math].

Remark

The implementations of the methods Bounded priority queue: number and Bounded priority queue: find minimum are trivial and, hence, left out here.