Dial implementation: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(6 intermediate revisions by 2 users not shown)
Line 2: Line 2:
[[Category:Data Structures]]
[[Category:Data Structures]]
==General information==
==General information==
'''Abstract Data Structure:''' [[Bounded monotonous priority queue]].
'''Abstract data structure:''' [[Bounded monotonous priority queue]].


'''Implementation Invariant:'''
'''Implementation invariant:'''
An object of "Dial implementation" comprises:
An object of "Dial implementation" comprises:
# A specific '''maximum span of keys''' <math>S\in\mathbb{N}</math>,
# A specific '''maximum span of keys''' <math>S\in\mathbb{N}</math>.
# An array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> and [[Sets and sequences|sets]] of keys as components,
# An array <math>A</math> with index set <math>\{0,\ldots,S-1\}</math> and [[Sets and sequences|sets]] of keys as components,
# A '''current position of the minimum''' <math>P</math>, which is dynamically changing,
# A '''current position of the minimum''' <math>P</math>, which is dynamically changing.
# An [[Index handler|index handler]], whose value type is a pointer to an element in a [[Sets and sequences|set]]
# An [[Index handler|index handler]], whose value type is a pointer to an element in a [[Sets and sequences|set]] of keys.
of keys
 
All keys at an index of <math>A</math> are equal. For <math>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>P</math> by exactly <math>(S+i-P)\bmod S</math>.
All keys at an index of <math>A</math> are equal. For <math>i\in\{0,\ldots,S-1\}</math>, the value of the keys at position <math>i</math> is larger than the value of the keys at index <math>P</math> by exactly <math>(S+i-P)\bmod S</math>.


For each key currently stored in <math>A</math>, the index handler contains a pointer to the corresponding set element.
For each key currently stored in <math>A</math>, the index handler contains a pointer to the corresponding set element.
Line 17: Line 17:
== Methods ==
== Methods ==


# The minimum keys are found at position <math>P</math>. The position is increased in the minimum extraction method by 1 modulo <math>S</math>, when the set at position <math>P</math> becomes empty.
# '''Extract minimum:''' The minimum keys are found at position <math>P</math>. If the set at position <math>P</math> is empty after extracting one minimum element, the current position <math>P</math> is increased by 1 modulo <math>S</math>,
# A key <math>K</math> is inserted at index <math>(S+K-P)\bmod S</math>.
# '''Insert:''' A key <math>K</math> is inserted at index <math>(K-A[P]+P)\bmod S</math>.
# Decreasing a key value <math>K</math> to value <math>K'</math> amounts to removing the key from the set at index <math>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>.  
# '''Decrease key:''' Decreasing a key value <math>K</math> to value <math>K'</math> amounts to removing the key from the set at index <math>(K-A[P]+P)\bmod S</math> and re-insert it at index <math>(K'-A[P]+P)\bmod S</math>. The set element is retrieved from the index handler.


==Remark==
==Remark==

Latest revision as of 09:57, 26 February 2015

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{ (K-A[P]+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{ (K-A[P]+P)\bmod S }[/math] and re-insert it at index [math]\displaystyle{ (K'-A[P]+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.

References