Dial implementation

From Algowiki
Revision as of 08:33, 7 October 2014 by Weihe (talk | contribs)
Jump to navigation Jump to search

General information

Abstract Data Structure: Bounded monotonous priority queue where [math]\displaystyle{ \mathcal{K} }[/math] is an integral type and addition is defined on [math]\displaystyle{ \mathcal{K} }[/math]

Implementation Invariant:

  1. For each object of "Dial implementation", there is
    1. a specific maximum span of keys [math]\displaystyle{ S_\text{max}\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 [math]\displaystyle{ P\in\mathbb{N}_{0} }[/math], which is dynamically changing,

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 $i$ is larger than the value of the keys at index [math]\displaystyle{ P }[/math] by exactly [math]\displaystyle{ (S+i-P)\bmod S }[/math]. In particular, the minimum keys are at index $P$

Remark

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

References