Ordered sequence
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{ \kappa }[/math].
Insert
Input: A key [math]\displaystyle{ K \in \kappa }[/math] and a nonnegative integral position <mth>p</math>.
Output: a Boolean value, which is true if, and only if, [math]\displaystyle{ p\\{0,\ldots,n\} }[/math], where
Precondition:
Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted . [math]\displaystyle{ K }[/math] has been inserted.
Find
Input: A key [math]\displaystyle{ K \in \kappa }[/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 \kappa }[/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.