Ordered sequence: Difference between revisions
No edit summary |
|||
| Line 8: | Line 8: | ||
== Insert at position == | == Insert at position == | ||
'''Input:''' A key <math>K \in \ | '''Input:''' A key <math>K \in \mathcal{K}</math> and a nonnegative integral position <math>p</math>. | ||
'''Output:''' a Boolean value, which is '''true''' if, and only if, <math>p\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list. | '''Output:''' a Boolean value, which is '''true''' if, and only if, <math>p\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list. | ||
| Line 17: | Line 17: | ||
== 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 26: | Line 26: | ||
== 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:24, 17 May 2015
General Information
Representation invariant:
- The abstract data structure ordered 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].
Insert at position
Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math] and a nonnegative integral position [math]\displaystyle{ p }[/math].
Output: a Boolean value, which is true if, and only if, [math]\displaystyle{ p\in\{0,\ldots,n\} }[/math], where [math]\displaystyle{ n }[/math] is the length of the list.
Precondition:
Postcondition: If the output ist true, a new element with the key [math]\displaystyle{ K }[/math] is inserted at position [math]\displaystyle{ p }[/math].
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.