# Sorted sequence

## Contents

## 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]\mathcal{K}[/math] and a fixed comparison [math]c[/math] defined on [math]\mathcal{K}[/math].

## Constructor

Gets a comparison [math]c[/math] to maintain and initializes the sequence so as to be empty.

## Insert

**Input:** A key [math]K \in \mathcal{K}[/math].

**Output:** None.

**Precondition:** None.

**Postcondition:** A new element with the key [math]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]L[/math] containing all elements of the sorted sequence in ascending order.

**Precondition:** None.

**Postcondition:** None.

## Find

**Input:** A key [math]K \in \mathcal{K} [/math].

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

**Precondition:** None.

**Postcondition:** None.

## Remove

**Input:** A key [math]K \in \mathcal{K}[/math].

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

**Precondition:** None.

**Postcondition:** If the output is **true**, exactly one occurrence of [math]K[/math] is removed. The choice of the occurrence to be removed is unspecified.