Sorted sequence: Difference between revisions
(→Find) |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| 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. | |||
== 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 | '''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 | '''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]] | ||
Latest revision as of 13:06, 21 May 2015
General Information
Representation invariant:
- The abstract data structure sorted sequence implements sorted sequences as defined here.
- This abstract data structure is generic and parameterized by a fixed key type [math]\displaystyle{ \mathcal{K} }[/math] and a fixed comparison [math]\displaystyle{ c }[/math] defined on [math]\displaystyle{ \mathcal{K} }[/math].
Constructor
Gets a comparison [math]\displaystyle{ c }[/math] to maintain and initializes the sequence so as to be empty.
Insert
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output: None.
Precondition: None.
Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted at an appropriate position in sorting order, so the sorting order is maintained.
Traverse
Input: None.
Output: A linear list structure [math]\displaystyle{ L }[/math] containing all elements of the sorted sequence in ascending order.
Precondition: None.
Postcondition: None.
Find
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output: A Boolean value, which is true if, and only if, at least one occurrence of [math]\displaystyle{ K }[/math] is currently contained in the sequence.
Precondition: None.
Postcondition: None.
Remove
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output: A Boolean value, which is true if, and only if, at least one occurrence of [math]\displaystyle{ K }[/math] is currently contained in the sequence.
Precondition: None.
Postcondition: If the output is true, exactly one occurrence of [math]\displaystyle{ K }[/math] is removed. The choice of the occurrence to be removed is unspecified.