Processing math: 28%

The `ORDSET` signature

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:

The Key substructure now ascribes to ORDKEY.

There is additional functionality relying upon the ordering of keys, such as split, join, and getRange.
The toSeq function now specifies that it returns keys in sorted order.

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

The ORDSET signature