Sorted sequence - Revision history

Weihe at 13:06, 21 May 2015

2015-05-21T13:06:13Z

← Older revision		Revision as of 13:06, 21 May 2015
Line 7:		Line 7:
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.

	~~'''~~Constructor~~:'''~~ Gets a [[Genericity#Comparison\|comparison]] <math>c</math> to maintain and initializes the sequence so as to be empty.		== Constructor ==

			Gets a [[Genericity#Comparison\|comparison]] <math>c</math> to maintain and initializes the sequence so as to be empty.


	== Insert ==		== Insert ==
	'''Input:''' A key <math>K \in \mathcal{K}</math>.		'''Input:''' A key <math>K \in \mathcal{K}</math>.

	'''Output:'''		'''Output:''' None.

	'''Precondition:'''		'''Precondition:''' None.

	'''Postcondition:''' A new element with the key <math>K</math> is inserted at an appropriate position in sorting order.		'''Postcondition:''' A new element with the key <math>K</math> is inserted at an appropriate position in sorting order, so the sorting order is maintained.

	== Traverse ==		== Traverse ==

	'''Input:'''		'''Input:''' None.

	'''Output:''' A linear list structure <math>L</math> containing all elements of the sorted sequence in ascending order.		'''Output:''' A linear list structure <math>L</math> containing all elements of the sorted sequence in ascending order.

	'''Precondition:'''		'''Precondition:''' None.

	'''Postcondition:'''		'''Postcondition:''' None.

	== Find ==		== Find ==
	'''Input:''' A key <math>K \in \mathcal{K} </math>.		'''Input:''' A key <math>K \in \mathcal{K} </math>.

	'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently contained in the sequence.		'''Output:''' A Boolean value, which is '''true''' if, and only if, at least one occurrence of <math>K</math> is currently contained in the sequence.

	'''Precondition:'''		'''Precondition:''' None.

	'''Postcondition:'''		'''Postcondition:''' None.

	== Remove ==		== Remove ==
	'''Input:''' A key <math>K \in \mathcal{K}</math>.		'''Input:''' A key <math>K \in \mathcal{K}</math>.

	'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently ~~stored~~ in the sequence.		'''Output:''' A Boolean value, which is '''true''' if, and only if, at least one occurrence of <math>K</math> is currently contained in the sequence.

	'''Precondition:'''		'''Precondition:''' None.

	'''Postcondition:''' If the output is '''true''', one occurrence of <math>K</math> is removed.		'''Postcondition:''' If the output is '''true''', exactly one occurrence of <math>K</math> is removed. The choice of the occurrence to be removed is unspecified.

	== Known Implementations ==		== Known Implementations ==
	# [[B-Trees]]		# [[B-Trees]]
	# [[Binary Search Tree]]		# [[Binary Search Tree]]

Weihe: /* Remove */

2015-05-18T07:08:11Z

Remove

← Older revision		Revision as of 07:08, 18 May 2015
Line 40:		Line 40:
	'''Input:''' A key <math>K \in \mathcal{K}</math>.		'''Input:''' A key <math>K \in \mathcal{K}</math>.

	'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently stored in the sequence.		'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently stored in the sequence.

	'''Precondition:'''		'''Precondition:'''

	'''Postcondition:''' If the output is '''''true''''', one occurrence of <math>K</math> is removed.		'''Postcondition:''' If the output is '''true''', one occurrence of <math>K</math> is removed.

	== Known Implementations ==		== Known Implementations ==
	# [[B-Trees]]		# [[B-Trees]]
	# [[Binary Search Tree]]		# [[Binary Search Tree]]

Weihe: /* Traverse */

2015-05-18T07:07:42Z

Traverse

← Older revision		Revision as of 07:07, 18 May 2015
Line 26:		Line 26:
	'''Precondition:'''		'''Precondition:'''

	'''Postcondition:''' ~~All keys of the sorted sequence are appended to <math>L</math> in ascending order.~~		'''Postcondition:'''

	== Find ==		== Find ==

Weihe: /* Find */

2015-05-18T07:07:11Z

Find

← Older revision		Revision as of 07:07, 18 May 2015
Line 31:		Line 31:
	'''Input:''' A key <math>K \in \mathcal{K} </math>.		'''Input:''' A key <math>K \in \mathcal{K} </math>.

	'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently contained in the sequence.		'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently contained in the sequence.

	'''Precondition:'''		'''Precondition:'''

Weihe: /* Insert */

2015-05-18T07:06:39Z

Insert

← Older revision		Revision as of 07:06, 18 May 2015
Line 16:		Line 16:
	'''Precondition:'''		'''Precondition:'''

	'''Postcondition:''' A new element with the key <math>K</math> is inserted at ~~the~~ appropriate position in sorting order.		'''Postcondition:''' A new element with the key <math>K</math> is inserted at an appropriate position in sorting order.

	== Traverse ==		== Traverse ==

Weihe: /* General Information */

2015-05-17T14:44:06Z

General Information

← Older revision		Revision as of 14:44, 17 May 2015
Line 7:		Line 7:
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.

	'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ~~ths~~ sequence so as to be empty.		'''Constructor:''' Gets a [[Genericity#Comparison\|comparison]] <math>c</math> to maintain and initializes the sequence so as to be empty.

	== Insert ==		== Insert ==

Weihe: /* General Information */

2015-05-17T14:43:28Z

General Information

← Older revision		Revision as of 14:43, 17 May 2015
Line 5:		Line 5:
	'''Representation invariant:'''		'''Representation invariant:'''
	# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences#Ordered and sorted sequences\|here]].		# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences#Ordered and sorted sequences\|here]].
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.

	'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.		'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.

Weihe: /* General Information */

2015-05-17T14:42:03Z

General Information

← Older revision		Revision as of 14:42, 17 May 2015
Line 4:		Line 4:
	== General Information ==		== General Information ==
	'''Representation invariant:'''		'''Representation invariant:'''
	# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences\|here]].		# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences#Ordered and sorted sequences\|here]].
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.

Weihe: /* General Information */

2015-05-17T09:25:53Z

General Information

← Older revision		Revision as of 09:25, 17 May 2015
Line 5:		Line 5:
	'''Representation invariant:'''		'''Representation invariant:'''
	# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences\|here]].		# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences\|here]].
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>mathcal{K}</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.

	'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.		'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.

Weihe at 09:25, 17 May 2015

2015-05-17T09:25:37Z

← Older revision		Revision as of 09:25, 17 May 2015
Line 5:		Line 5:
	'''Representation invariant:'''		'''Representation invariant:'''
	# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences\|here]].		# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences\|here]].
	# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\~~kappa~~</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>~~\kappa~~</math>.		# This abstract data structure is [[Genericity\|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity\|comparison]] <math>c</math> defined on <math>mathcal{K}</math>.

	'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.		'''Constructor:''' Gets a [[Genericity\|comparison]] <math>c</math> and initializes ths sequence so as to be empty.

	== Insert ==		== Insert ==
	'''Input:''' A key <math>K \in \~~kappa~~</math>.		'''Input:''' A key <math>K \in \mathcal{K}</math>.

	'''Output:'''		'''Output:'''
Line 29:		Line 29:

	== Find ==		== Find ==
	'''Input:''' A key <math>K \in \~~kappa~~ </math>.		'''Input:''' A key <math>K \in \mathcal{K} </math>.

	'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently contained in the sequence.		'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently contained in the sequence.
Line 38:		Line 38:

	== Remove ==		== Remove ==
	'''Input:''' A key <math>K \in \~~kappa~~</math>.		'''Input:''' A key <math>K \in \mathcal{K}</math>.

	'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently stored in the sequence.		'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently stored in the sequence.