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\} }[/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. Extract minimum: The minimum keys are found at position [math]\displaystyle{ P }[/math]. If the set at position [math]\displaystyle{ P }[/math] is empty after extracting one minimum element, the current position [math]\displaystyle{ P }[/math] is increased by 1 modulo [math]\displaystyle{ S }[/math],
2. Insert: A key [math]\displaystyle{ K }[/math] is inserted at index [math]\displaystyle{ (S+K-P)\bmod S }[/math].
3. Decrease key: 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]. The set element is retrieved from the index handler.

Remark

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