The ORDSET signature

« 210 Library Documentation

Overview

The ORDSET interface specifies an ordered collection of items. These sets do not contain duplicates, and are not polymorphic: the type of their elements is given by the Key substructure.

This interface is nearly identical to SET except for the following:

Interface

structure Key : ORDKEY
structure Seq : SEQUENCE

type t
type set = t

exception Order

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 : ('a * Key.t → 'a) → 'a → set → 'a

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, which are totally ordered according to the provided comparison function.
structure Seq : SEQUENCE
The Seq substructure defines a sequence type for use with toSeq and fromSeq.

Types

type t

type set = t
The abstract set type. The alias set is for readability in the signature.

Exceptions

exception Order
Order is raised when the ordering invariant would be violated.

Values

val size : set → int
size x evaluates to $|x|$, the number of elements in the set $x$.
val toString : set → string
Evaluates to a string representation of the set. Each element is converted to a string via Key.toString.
val toSeq : set → Key.t Seq.t
Return the sequence containing all keys in a set. The ordering of the elements in the returned sequence is implementation-defined.
val empty : unit → set
Construct the empty set.
val singleton : Key.t → set
Construct the singleton set containing only the provided key.
val fromSeq : Key.t Seq.t → set
Return the set of 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 : ('a * Key.t → 'a) → 'a → set → 'a
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 (s, k) evaluates to $(l, m, r)$, where $l = \{ k' \in s\ |\ k' < k \}$, $r = \{ k' \in s\ |\ k' > k \}$, and $m$ indicates whether or not $k$ is a member of $s$.
val join : set * set → set
For sets $a$ and $b$ where every element in $a$ is strictly less than every element in $b$, (join (a, b)) evaluates to $a \cup b$. Otherwise it raises Order.
val getRange : set → Key.t * Key.t → set
(getRange s (x, y)) evaluates to $\{ k \in s\ |\ x \leq k \leq y \}$.
val rank : set * Key.t → int
(rank (s, k)) evaluates to $\big|\{ k' \in s\ |\ k' < k \}\big|$, the number of elements in $s$ which are strictly smaller than $k$.
val select : set * int → Key.t option
(select (s, i)) returns the $i^\text{th}$ smallest element in $s$, or NONE if either $i < 0$ or $i \geq |s|$.
val splitRank : set * int → set * set
(splitRank (s, i)) evaluates to $(l, r)$, where $l$ is the set of the $i$ smallest elements of $s$, and $r$ is the set of the $|s| - i$ largest elements of $s$.

Raises Fail if $i < 0$ or $i \geq |s|$.