The ORDSET signature

« 210 Library Documentation

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

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 : (α * 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.

Exceptions

exception Order
Order is raised whenever set operations would violate the ordering invariant.

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|$.