Dial implementation - Revision history

BB91: /* Methods */

2015-02-26T09:57:47Z

Methods

← Older revision		Revision as of 09:57, 26 February 2015
Line 18:		Line 18:

	# '''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>,		# '''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>,
	# '''Insert:''' A key <math>K</math> is inserted at index <math>(S+K-A[P])\bmod S</math>.		# '''Insert:''' A key <math>K</math> is inserted at index <math>(K-A[P]+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>(S+K-A[P])\bmod S</math> and re-insert it at index <math>(S+K'-A[P])\bmod S</math>. The set element is retrieved from the index handler.		# '''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==

BB91: /* Methods */

2014-11-03T11:14:03Z

Methods

← Older revision		Revision as of 11:14, 3 November 2014
Line 18:		Line 18:

	# '''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>,		# '''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>,
	# '''Insert:''' 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>(S+K-A[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>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>. The set element is retrieved from the index handler.		# '''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>(S+K-A[P])\bmod S</math> and re-insert it at index <math>(S+K'-A[P])\bmod S</math>. The set element is retrieved from the index handler.

	==Remark==		==Remark==

Weihe: /* Methods */

2014-10-20T14:27:38Z

Methods

← Older revision		Revision as of 14:27, 20 October 2014
Line 19:		Line 19:
	# '''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>,		# '''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>,
	# '''Insert:''' 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>(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>(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>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>. The set element is retrieved from the index handler.

	==Remark==		==Remark==

Weihe: /* General information */

2014-10-20T14:25:45Z

General information

← Older revision		Revision as of 14:25, 20 October 2014
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>.

Weihe: /* Methods */

2014-10-17T14:27:51Z

Methods

← Older revision		Revision as of 14:27, 17 October 2014
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>(S+K-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>(S+K-P)\bmod S</math> and re-insert it at index <math>(S+K'-P)\bmod S</math>.

	==Remark==		==Remark==

Weihe: /* General information */

2014-10-17T14:25:28Z

General information

← Older revision		Revision as of 14:25, 17 October 2014
Line 6:		Line 6:
	'''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 <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>.		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.

Weihe: /* General information */

2014-10-14T10:43:52Z

General information

← Older revision		Revision as of 10:43, 14 October 2014
Line 11:		Line 11:
	# 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\}\setminus\{P\}</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.

Weihe: /* General information */

2014-10-14T05:00:19Z

General information

← Older revision		Revision as of 05:00, 14 October 2014
Line 8:		Line 8:
	# 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~~\in\mathbb{N}_{0}~~</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

Weihe at 09:18, 10 October 2014

2014-10-10T09:18:16Z

← Older revision		Revision as of 09:18, 10 October 2014
Line 9:		Line 9:
	# 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\in\mathbb{N}_{0}</math>, which is dynamically changing,		# A '''current position of the minimum''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing,
	# An [[Index ~~hander~~\|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\}\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>.

	For each key currently stored in <math>A</math>, the index handler contains a o 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.

	== Methods ==		== Methods ==

Weihe: /* General information */

2014-10-10T09:15:12Z

General information

← Older revision		Revision as of 09:15, 10 October 2014
Line 9:		Line 9:
	# 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\in\mathbb{N}_{0}</math>, which is dynamically changing,		# A '''current position of the minimum''' <math>P\in\mathbb{N}_{0}</math>, which is dynamically changing,
	# ~~'''ToDo:''' extract the positions array and the list of unused orm Heap as array~~, ~~make it~~ a ~~separate data structure~~ and ~~integrate~~ an ~~object~~ of ~~that data structure here for~~ the ~~decrease key method~~.		# An [[Index hander\|index handler]], whose value type is a pointer to an element in a [[Sets and sequences\|set]]
			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\}\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>~~.		For each key currently stored in <math>A</math>, the index handler contains a o pointer to the corresponding set element.

	== Methods ==		== Methods ==