# Sorted sequence

## General Information

Representation invariant:

1. The abstract data structure sorted sequence implements sorted sequences as defined here.
2. This abstract data structure is generic and parameterized by a fixed key type $\mathcal{K}$ and a fixed comparison $c$ defined on $\mathcal{K}$.

## Constructor

Gets a comparison $c$ to maintain and initializes the sequence so as to be empty.

## Insert

Input: A key $K \in \mathcal{K}$.

Output: None.

Precondition: None.

Postcondition: A new element with the key $K$ is inserted at an appropriate position in sorting order, so the sorting order is maintained.

## Traverse

Input: None.

Output: A linear list structure $L$ containing all elements of the sorted sequence in ascending order.

Precondition: None.

Postcondition: None.

## Find

Input: A key $K \in \mathcal{K}$.

Output: A Boolean value, which is true if, and only if, at least one occurrence of $K$ is currently contained in the sequence.

Precondition: None.

Postcondition: None.

## Remove

Input: A key $K \in \mathcal{K}$.

Output: A Boolean value, which is true if, and only if, at least one occurrence of $K$ is currently contained in the sequence.

Precondition: None.

Postcondition: If the output is true, exactly one occurrence of $K$ is removed. The choice of the occurrence to be removed is unspecified.