# The ORDSET signature

## Overview

Ordered sets are sets along with an ordering on their elements. This interface is nearly identical to SET except for the ordered set functions starting with first, and Key now ascribing to ORDKEY.

## Interface

structure Key : ORDKEY
structure Seq : SEQUENCE

type t
type set = t

val size : set → int
val toString : set → string
val toSeq : set → Key.t Seq.t

val empty : unit → set
val singleton : Key.t → set
val fromSeq : Key.t Seq.t → set

val find : set → Key.t → bool
val insert : set * Key.t → set
val delete : set * Key.t → set

val filterKey : (Key.t → bool) → set → set

val reduceKey : (Key.t * Key.t → Key.t) → Key.t → set → Key.t
val iterateKey : (α * Key.t → α) → α → set → α

val union : set * set → set
val intersection : set * set → set
val difference : set * set → set

val $: Key.t → set val first : set → Key.t option val last : set → Key.t option val prev : set * Key.t → Key.t option val next : set * Key.t → Key.t option val split : set * Key.t → set * bool * set val join : set * set → set val getRange : set → Key.t * Key.t → set val rank : set * Key.t → int val select : set * int → Key.t option val splitRank : set * int → set * set ## Substructures structure Key : ORDKEY The Key substructure defines the type of elements in a set, providing comparison and other useful functions. structure Seq : SEQUENCE The Seq substructure defines the underlying sequence type to and from which sets can be converted. ## Types type t The abstract set type. type set = t An alias for t, for readability. ## Values val size : set → int (size x) evaluates to$|x|$, the number of elements in the set$x$. val toString : set → string (toString x) evaluates to a string representation of$x$. Each element of$x$is converted to a string by Key.toString. For example, the set$\{1,2,3\}$would be represented by the string “{1,2,3}”. val toSeq : set → Key.t Seq.t Return the sequence containing all elements of a set in sorted order. val empty : unit → set Construct the empty set,$\{\}$. val singleton : Key.t → set (singleton x) evaluates to$\{x\}$, the singleton set containing only the element$x$. val fromSeq : Key.t Seq.t → set Return the set containing all elements of a sequence. val find : set → Key.t → bool (find x k) returns whether or not$k$is a member of the set$x$. val insert : set * Key.t → set (insert (x, k)) evaluates to the set$x \cup \{k\}$. val delete : set * Key.t → set (delete (x, k)) evaluates to the set$x \setminus \{k\}$. val filterKey : (Key.t → bool) → set → set (filterKey p x) evaluates to the subset of$x$containing every key$k$which satisfies$p(k)$. val reduceKey : (Key.t * Key.t → Key.t) → Key.t → set → Key.t (reduceKey f b x) is logically equivalent to (Seq.reduce f b (toSeq x)). val iterateKey : (α * Key.t → α) → α → set → α (iterateKey f b x) is logically equivalent to (Seq.iterate f b (toSeq x)). val union : set * set → set (union (x, y)) evaluates to the set$x \cup y$. val intersection : set * set → set (intersection (x, y)) evaluates to the set$x \cap y$. val difference : set * set → set (difference (x, y)) evaluates to the set$x \setminus y$. val$ : Key.t → set
An alias for singleton.
val first : set → Key.t option
Return the least element of a set, or NONE if the set is empty.
val last : set → Key.t option
Return the greatest element of a set, or NONE if the set is empty.
val prev : set * Key.t → Key.t option
(prev (x, k)) evaluates to $\max \{ k' \in x\ |\ k' < k \}$, or NONE if there is no such element.
val next : set * Key.t → Key.t option
(next (x, k)) evaluates to $\min \{ k' \in x\ |\ k' > k \}$, or NONE if there is no such element.
val split : set * Key.t → set * bool * set
(split (x, k)) evaluates to $(l, b, r)$, where $l = \{ k' \in x\ |\ k' < k \}$, $r = \{ k' \in x\ |\ k' > k \}$, and $b$ indicates whether or not $k \in x$.
val join : set * set → set
Given sets $x$ and $y$ where every element in $x$ is strictly less than every element in $y$, (join (x, y)) evaluates to $x \cup y$.
val getRange : set → Key.t * Key.t → set
(getRange x (a, b)) evaluates to $\{ k \in x\ |\ a \leq k \leq b \}$.
val rank : set * Key.t → int
(rank (x, k)) evaluates to $\big|\{ k' \in x\ |\ k' < k \}\big|$.
val select : set * int → Key.t option
(select (x, i)) evaluates to the $i^\text{th}$ smallest element in $x$, or NONE if either $i < 0$ or $i \geq |x|$.
val splitRank : set * int → set * set
(splitRank (x, i)) evaluates to $(l, r)$ such that $|l| = i$, $|r| = |x| - i$, every key in $l$ is strictly less than every key in $r$, and their union is $x$. Raises Fail if $i < 0$ or $i \geq |x|$.