The SORTED_SET signature

Overview

The SORTED_SET interface specifies a persistent set of keys, kept in sorted order. Sets do not contain duplicates, and are not polymorphic: the type of their elements is given by the Key substructure.

A sorted set is a SORTED_DICT without values, and each operation means what the dictionary's does on keys alone. The operations that differ by more than dropping the value are described below. The rest are described on the SORTED_DICT page.

Interface

structure Key : ORDKEY
structure Seq : SEQUENCE

type t
type set = t

exception Order

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

val size : set → int
val contains : set → Key.t → bool
val insert : set * Key.t → set
val remove : set * Key.t → set

val union : set * set → set
val intersection : set * set → set
val difference : set * set → set
val filter : (Key.t → bool) → set → 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

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 the underlying sequence type, so that we may convert sets to and from sequences.

Types

type t

type set = t

The abstract set type. The type set is for readability in the signature.

Values

val fromSeq : Key.t Seq.t → set

Return the set of the keys in a sequence, which may be in any order and may contain duplicates.

val contains : set → Key.t → bool

contains s k returns whether $k \in s$.

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

filter p s returns the set of every $k \in s$ which satisfies $p(k)$.

val split : set * Key.t → set * bool * set

split (s, k) evaluates to $(l, b, r)$, where $l$ consists of all keys of $s$ strictly smaller than $k$, $r$ of all keys strictly greater than $k$, and $b$ is whether $k \in s$.