Sorted sequence
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.