Sorted sequence: Difference between revisions
(→Remark) |
No edit summary |
||
| 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>\ | # 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 \ | '''Input:''' A key <math>K \in \mathcal{K}</math>. | ||
'''Output:''' | '''Output:''' | ||
| Line 29: | Line 29: | ||
== Find == | == Find == | ||
'''Input:''' A key <math>K \in \ | '''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 \ | '''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. | ||
Revision as of 09:25, 17 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] and initializes ths sequence so as to be empty.
Insert
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output:
Precondition:
Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted at the appropriate position in sorting order.
Traverse
Input:
Output: A linear list structure [math]\displaystyle{ L }[/math] containing all elements of the sorted sequence in ascending order.
Precondition:
Postcondition: All keys of the sorted sequence are appended to [math]\displaystyle{ L }[/math] in ascending order.
Find
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently contained in the sequence.
Precondition:
Postcondition:
Remove
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].
Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently stored in the sequence.
Precondition:
Postcondition: If the output is true, one occurrence of [math]\displaystyle{ K }[/math] is removed.