(std orderedset)

Reference

Overview

Persistent sorted set implemented as a B-tree in element order, with builder and transient.

(import (std orderedset))

(def s (list->orderedset (list 5 1 3 9)))
(orderedset->list s)                 ; (1 3 5 9)
(orderedset-min s)                   ; (Some 1)
(orderedset-successor s 3)           ; (Some 5)
(orderedset-successor s 4)           ; (Some 5), 4 need not be in set
(->list (orderedset-range s 2 6)) ; (3 5)

An (OrderedSet a) is an immutable, persistent sorted set. Updates return a new set sharing untouched nodes with the original. Implemented as a B-tree (OrderedSet.OrderedSet in the runtime). Lookup, insertion, and deletion operations run in O(log n) time.

Element ordering. Constructors (orderedset-empty, seq->orderedset, list->orderedset, vec->orderedset, orderedsetbuilder-empty, transientorderedset-empty, and the ordered-setting collector) require an Ord instance for element type %a. Elements are ordered according to compare. Elements considered equal by compare are deduplicated. Derived sets retain the source set’s ordering comparer.

Order guarantees. All traversals, conversions, and callbacks visit elements in ascending order. Provides efficient boundary operations (orderedset-min, orderedset-max, orderedset-successor, orderedset-predecessor) and range slices (orderedset-range, orderedset-from, orderedset-until). If element ordering is not required, use (std hashset), which requires only Eq.

Batch mutations and construction. An OrderedSetBuilder collects elements, sorts them, and constructs the tree in a single pass. A TransientOrderedSet mutates tree nodes in place and converts to a persistent set in O(1) time. Both outperform repeated calls to orderedset-add for bulk updates.

Traits. Implements Iterable, Collection, Refable (where (ref s x) tests membership), Addable, Eq, Written and Displayed. Two sets are = if they contain identical elements. Builders and transients implement Addable!, and transients implement Refable.

See also: OrderedSet, orderedset-empty, orderedset-add, orderedset-min, orderedset-range, orderedset-union, OrderedSetBuilder, TransientOrderedSet

Reference

Types

Functions

Types

OrderedSet

type alias ↑ Types

Persistent set sorted by element.

%a
The element type. Requires an Ord instance.
(def s (orderedset-add (orderedset-add (orderedset-empty) "b") "a"))
(orderedset->list s)   ; ("a" "b")
(ref s "c")            ; #f

See also: orderedset-empty, orderedset-add, orderedset-contains?, OrderedSetBuilder, TransientOrderedSet, OrderedSetting

OrderedSetBuilder

type alias ↑ Types

Mutable buffer for constructing an ordered set in a single pass.

%a
The element type.
(def b (orderedsetbuilder-empty))
(orderedsetbuilder-add! b 3)
(orderedsetbuilder-add! b 1)
(orderedsetbuilder-add! b 3)
(orderedsetbuilder-length b)           ; 3
(orderedsetbuilder->orderedset b)      ; #{1 3}

Appends elements to a flat buffer. Calling orderedsetbuilder->orderedset sorts elements and constructs the B-tree in a single pass. If elements arrive in sorted order, sorting is skipped. Duplicate elements are deduplicated. Builders do not support lookups or removals; use TransientOrderedSet for mutable set operations. Implements Addable!.

See also: orderedsetbuilder-empty, orderedsetbuilder-add!, orderedsetbuilder->orderedset, TransientOrderedSet

TransientOrderedSet

type alias ↑ Types

Mutable transient ordered set for batch in-place updates.

%a
The element type.
(def t (orderedset->transientorderedset s))
(transientorderedset-add! t 4)
(transientorderedset-remove! t 1)
(transientorderedset->orderedset t)

Provides in-place mutators mirroring persistent orderedset- functions. Mutates owned tree nodes in place without copying. Calling transientorderedset->orderedset yields a persistent set in O(1) time. The transient remains usable afterward; subsequent writes perform copy-on-write on shared nodes. Implements Addable! and Refable.

See also: orderedset->transientorderedset, transientorderedset->orderedset, transientorderedset-add!, OrderedSetBuilder

OrderedSetCursor

type alias ↑ Types

Cursor for iterating over an ordered set.

%a
The element type.

Used by the Iterable implementation of OrderedSet to iterate in ascending element order. Immutable cursor value: advancing produces a new cursor without mutating the previous one.

See also: OrderedSet

OrderedSetting

union ↑ Types

Collector for gathering elements into an ordered set via loop.

%a
The element type. Requires an Ord instance.
ordered-setting
The collector constructor.
(loop (:for x (range 0 10))
      (:when (= 0 (% x 2)))
      (:acc s (ordered-setting x)))   ; #{0 2 4 6 8}

Collects elements through an OrderedSetBuilder.

See also: list->orderedset, OrderedSetBuilder

Functions

orderedset-empty

function ↑ Functions

(: orderedset-empty (-> (OrderedSet %a)))
(orderedset-empty)

Creates an empty ordered set.

returns
An empty set ordered by the element type's Ord instance.

See also: orderedset-clear, seq->orderedset, list->orderedset

orderedset-add

function ↑ Functions

(: orderedset-add (-> (OrderedSet %a) %a (OrderedSet %a)))

Returns a new set with an element added.

s
The source set (unmodified).
x
The element to add.
returns
A new set containing x. If x is already present, returns an equivalent set.

See also: orderedset-add-all, orderedset-remove, add

orderedset-add-all

function ↑ Functions

(: orderedset-add-all (-> (OrderedSet %a) (Seq %a) (OrderedSet %a)))

Returns a new set with all elements of a sequence added.

s
The source set (unmodified).
xs
Sequence of elements to add.
returns
A new set containing all elements from s and xs.

Executes through a transient, copying tree nodes once rather than once per element.

See also: orderedset-add, orderedset-union, transientorderedset-add-all!

orderedset-remove

function ↑ Functions

(: orderedset-remove (-> (OrderedSet %a) %a (OrderedSet %a)))

Returns a new set with an element removed.

s
The source set (unmodified).
x
The element to remove.
returns
A new set without x. If x was absent, returns s directly.

See also: orderedset-remove-all, orderedset-filter

orderedset-remove-all

function ↑ Functions

(: orderedset-remove-all (-> (OrderedSet %a) (Seq %a) (OrderedSet %a)))

Returns a new set with all specified elements removed.

s
The source set (unmodified).
xs
Sequence of elements to remove.
returns
A new set without those elements.

Executes through a transient, copying tree nodes once rather than once per element.

See also: orderedset-remove, orderedset-difference, transientorderedset-remove-all!

orderedset-contains?

function ↑ Functions

(: orderedset-contains? (-> (OrderedSet %a) %a bool))

Tests if an element is in the set.

s
The set to inspect.
x
The element to locate.
returns
#t if x is present, otherwise #f.

See also: ref, orderedset-find

orderedset-length

function ↑ Functions

(: orderedset-length (-> (OrderedSet %a) int))

Returns the number of elements in the set.

s
The set.
returns
The count of elements.

See also: orderedset-empty?, length

orderedset-empty?

function ↑ Functions

(: orderedset-empty? (-> (OrderedSet %a) bool))

Tests if the set contains no elements.

s
The set.
returns
#t if empty, otherwise #f.

See also: orderedset-length, empty?

orderedset-clear

function ↑ Functions

(: orderedset-clear (-> (OrderedSet %a) (OrderedSet %a)))

Returns an empty set retaining the element comparer of the source set.

s
The set whose order is preserved.
returns
An empty persistent set.

See also: orderedset-empty, orderedset-remove-all

orderedset-union

function ↑ Functions

(: orderedset-union (-> (OrderedSet %a) (OrderedSet %a) (OrderedSet %a)))

Returns the union of two sets.

s
The first set.
other
The second set.
returns
A new set containing elements from both sets.

Elements from other are added to s using a transient. If either set is empty, the other set is returned directly.

See also: orderedset-add-all, orderedset-intersection

orderedset-intersection

function ↑ Functions

(: orderedset-intersection (-> (OrderedSet %a) (OrderedSet %a) (OrderedSet %a)))

Returns the intersection of two sets.

s
The first set.
other
The second set.
returns
A new set containing only elements present in both sets, ordered as s is.

Traverses both sorted sets in parallel in O(n + m) time. Assumes both sets share identical ordering.

See also: orderedset-union, orderedset-difference

orderedset-difference

function ↑ Functions

(: orderedset-difference (-> (OrderedSet %a) (OrderedSet %a) (OrderedSet %a)))

Returns the set difference of two sets.

s
The base set.
other
Elements to exclude.
returns
A new set containing elements of s that are absent from other.

Traverses both sorted sets in parallel in O(n + m) time. Assumes both sets share identical ordering.

See also: orderedset-remove-all, orderedset-symmetric-difference

orderedset-symmetric-difference

function ↑ Functions

(: orderedset-symmetric-difference (-> (OrderedSet %a) (OrderedSet %a) (OrderedSet %a)))

Returns elements present in either set, but not both.

s
The first set.
other
The second set.
returns
A new set containing elements in s or other, but not both.

Traverses both sorted sets in parallel in O(n + m) time. Assumes both sets share identical ordering.

See also: orderedset-difference, orderedset-intersection

orderedset-min

function ↑ Functions

(: orderedset-min (-> (OrderedSet %a) (out %a) (Option %a)))

Returns the smallest element of a set, or None if empty.

s
The set.
returns
(Some x) for the smallest element, or None if empty.

See also: orderedset-max, orderedset-successor, transientorderedset-min

orderedset-max

function ↑ Functions

(: orderedset-max (-> (OrderedSet %a) (out %a) (Option %a)))

Returns the largest element of a set, or None if empty.

s
The set.
returns
(Some x) for the largest element, or None if empty.

See also: orderedset-min, orderedset-predecessor, transientorderedset-max

orderedset-successor

function ↑ Functions

(: orderedset-successor (-> (OrderedSet %a) %a (out %a) (Option %a)))

Returns the smallest element strictly greater than a value, or None.

s
The set.
x
Search value (need not exist in set).
returns
(Some y) for the next greater element, or None.
(def s (list->orderedset (list 10 20 30)))
(orderedset-successor s 20)   ; (Some 30)
(orderedset-successor s 25)   ; (Some 30)
(orderedset-successor s 30)   ; None

See also: orderedset-predecessor, orderedset-from

orderedset-predecessor

function ↑ Functions

(: orderedset-predecessor (-> (OrderedSet %a) %a (out %a) (Option %a)))

Returns the largest element strictly less than a value, or None.

s
The set.
x
Search value (need not exist in set).
returns
(Some y) for the next smaller element, or None.

See also: orderedset-successor, orderedset-until

orderedset-range

function ↑ Functions

(: orderedset-range (-> (OrderedSet %a) %a %a (Seq %a)))

Returns a sequence of elements in [lo, hi] in ascending order.

s
The set.
lo
Lower bound value (inclusive). Need not exist in set.
hi
Upper bound value (inclusive). Need not exist in set.
returns
A lazy sequence of elements in ascending order.
(->list (orderedset-range (list->orderedset (list 1 3 5 7)) 2 5))   ; (3 5)

Lazy: descends the B-tree to lo once and advances sequentially, so slicing a subset runs in time proportional to the range slice size.

See also: orderedset-from, orderedset-until

orderedset-from

function ↑ Functions

(: orderedset-from (-> (OrderedSet %a) %a (Seq %a)))

Returns a sequence of elements >= lo in ascending order.

s
The set.
lo
Lower bound value (inclusive). Need not exist in set.
returns
A lazy sequence of elements >= lo in ascending order.

Lazy, matching orderedset-range.

See also: orderedset-range, orderedset-until, orderedset-successor

orderedset-until

function ↑ Functions

(: orderedset-until (-> (OrderedSet %a) %a (Seq %a)))

Returns a sequence of elements <= hi in ascending order.

s
The set.
hi
Upper bound value (inclusive). Need not exist in set.
returns
A lazy sequence of elements <= hi in ascending order.

Lazy, matching orderedset-range.

See also: orderedset-range, orderedset-from, orderedset-predecessor

orderedset-map

function ↑ Functions

(: orderedset-map (-> (-?-> %a %b) (OrderedSet %a) (OrderedSet %b)))
(orderedset-map f s)

Transforms all elements using a function, returning a new set.

f
Transformation function called as (f x), in ascending order.
s
The source set.
returns
A new ordered set of transformed elements using the result type's Ord instance.

Duplicate transformed values are consolidated, so the resulting set may have fewer elements than s.

See also: orderedset-filter, orderedset-fold

orderedset-filter

function ↑ Functions

(: orderedset-filter (-> (-?-> %a bool) (OrderedSet %a) (OrderedSet %a)))
(orderedset-filter keep? s)

Returns a new set containing only elements satisfying a predicate.

keep?
Predicate function called as (keep? x); #t keeps element.
s
The source set.
returns
A new set of retained elements in ascending order.

See also: orderedset-remove-all, transientorderedset-filter!, orderedset-find

orderedset-fold

function ↑ Functions

(: orderedset-fold (-> (-?-> %a %s %s) %s (OrderedSet %a) %s))
(orderedset-fold f init s)

Folds over all elements in ascending order.

f
Accumulator function called as (f element acc), returning next acc.
init
Initial accumulator value.
s
The set to fold.
returns
The final accumulator value, or init if empty.
(orderedset-fold (fun (x acc) (+ (* acc 10) x)) 0
                 (list->orderedset (list 2 1 3)))   ; 123

See also: orderedset-for-each, fold

orderedset-for-each

function ↑ Functions

(: orderedset-for-each (-> (-?-> %a void) (OrderedSet %a) void))
(orderedset-for-each f s)

Applies a function to each element in ascending order.

f
Callback function called as (f x).
s
The set to iterate over.

See also: orderedset-iter, orderedset-fold

orderedset-iter

function ↑ Functions

(: orderedset-iter (-> (-?-> %a bool) (OrderedSet %a) bool))
(orderedset-iter f s)

Iterates over elements in ascending order until f returns #f.

f
Callback function called as (f x); #f stops iteration.
s
The set to iterate over.
returns
#t if all elements were visited; #f if stopped early by f.

See also: orderedset-for-each, orderedset-any?, orderedset-find

orderedset-any?

function ↑ Functions

(: orderedset-any? (-> (-> %a bool) (OrderedSet %a) bool))

Tests if any element satisfies a predicate.

pred
Predicate function called as (pred x).
s
The set to inspect.
returns
#t on the first element satisfying pred; #f if none match.

See also: orderedset-find, orderedset-iter

orderedset-find

function ↑ Functions

(: orderedset-find (-> (-> %a bool) (OrderedSet %a) (out %a) (Option %a)))

Returns the first element satisfying a predicate in ascending order.

pred
Predicate function called as (pred x).
s
The set to search.
returns
(Some x) for the first match, or None.

See also: orderedset-any?, orderedset-filter

list->orderedset

function ↑ Functions

(: list->orderedset (-> (List %a) (OrderedSet %a)))
(list->orderedset xs)

Constructs an ordered set from a list.

xs
Source list. Duplicate elements are added once.
returns
A new ordered set sorted by element.

Constructed through a builder in a single pass.

See also: orderedset->list, vec->orderedset, seq->orderedset, OrderedSetting

orderedset->list

function ↑ Functions

(: orderedset->list (-> (OrderedSet %a) (List %a)))
(orderedset->list s)

Converts set elements to a list in ascending order.

s
The source set.
returns
A list of elements in ascending order.

See also: list->orderedset, orderedset->vec, orderedset->seq

vec->orderedset

function ↑ Functions

(: vec->orderedset (-> (Vec %a) (OrderedSet %a)))
(vec->orderedset v)

Constructs an ordered set from a vector.

v
Source vector. Duplicate elements are added once.
returns
A new ordered set sorted by element.

Constructed through a builder in a single pass.

See also: orderedset->vec, list->orderedset, seq->orderedset

orderedset->vec

function ↑ Functions

(: orderedset->vec (-> (OrderedSet %a) (Vec %a)))
(orderedset->vec s)

Converts set elements to a vector in ascending order.

s
The source set.
returns
A vector of elements in ascending order.

See also: vec->orderedset, orderedset->list, orderedset->seq

seq->orderedset

function ↑ Functions

(: seq->orderedset (-> (Seq %a) (OrderedSet %a)))
(seq->orderedset xs)

Constructs an ordered set from a sequence.

xs
Source sequence. Duplicate elements are added once.
returns
A new ordered set sorted by element.

Constructed through a builder in a single pass.

See also: orderedset->seq, list->orderedset, vec->orderedset

orderedset->seq

function ↑ Functions

(: orderedset->seq (-> (OrderedSet %a) (Seq %a)))

Views set elements as a sequence in ascending order.

s
The source set.
returns
A sequence of elements in ascending order.

See also: seq->orderedset, orderedset-range, orderedset->list

orderedset->str

function ↑ Functions

(: orderedset->str (-> (OrderedSet %a) string))
(orderedset->str s)

Deprecated: use displayed. Formats an ordered set as text in the form #{…}.

s
The set to format.
returns
String with elements in ascending order inside #{...}, separated by spaces.
(displayed (list->orderedset (list 3 1 2)))   ; #{1 2 3}

The same text as displayed gives for an ordered set. Elements appear in ascending order. No reader macro reads this text back into an ordered set.

See also: orderedset->list

orderedsetbuilder-empty

function ↑ Functions

(: orderedsetbuilder-empty (-> (OrderedSetBuilder %a)))
(orderedsetbuilder-empty)

Creates an empty ordered set builder.

returns
A new builder using the element type's Ord instance.

See also: orderedset->orderedsetbuilder, orderedsetbuilder-add!, OrderedSetBuilder

orderedset->orderedsetbuilder

function ↑ Functions

(: orderedset->orderedsetbuilder (-> (OrderedSet %a) (OrderedSetBuilder %a)))

Creates an ordered set builder initialized with elements from a set.

s
The source set (unmodified).
returns
A new builder containing s's elements.

Traverses the set to populate the buffer in O(n) time. To mutate an existing set in place, use orderedset->transientorderedset in O(1).

See also: orderedsetbuilder-empty, orderedset->transientorderedset

orderedsetbuilder-add!

function ↑ Functions

(: orderedsetbuilder-add! (-> (OrderedSetBuilder %a) %a void))

Appends an element to an ordered set builder buffer.

b
The builder.
x
The element to append.

See also: orderedsetbuilder-add-all!, orderedsetbuilder->orderedset, add!

orderedsetbuilder-add-all!

function ↑ Functions

(: orderedsetbuilder-add-all! (-> (OrderedSetBuilder %a) (Seq %a) void))

Appends all elements of a sequence to an ordered set builder buffer.

b
The builder.
xs
Sequence of elements to append.

See also: orderedsetbuilder-add!

orderedsetbuilder-length

function ↑ Functions

(: orderedsetbuilder-length (-> (OrderedSetBuilder %a) int))

Returns the number of elements appended to the builder buffer.

b
The builder.
returns
The count of elements appended, including duplicates.

Duplicate entries are resolved when the set is built, so this represents an upper bound on final set size.

See also: orderedsetbuilder->orderedset

orderedsetbuilder->orderedset

function ↑ Functions

(: orderedsetbuilder->orderedset (-> (OrderedSetBuilder %a) (OrderedSet %a)))

Constructs a persistent ordered set from the builder buffer.

b
The builder.
returns
A new persistent ordered set containing the appended elements.

See also: orderedsetbuilder-empty, OrderedSetBuilder

transientorderedset-empty

function ↑ Functions

(: transientorderedset-empty (-> (TransientOrderedSet %a)))
(transientorderedset-empty)

Creates an empty transient ordered set.

returns
A new transient ordered set using the element type's Ord instance.

See also: orderedset->transientorderedset, TransientOrderedSet

orderedset->transientorderedset

function ↑ Functions

(: orderedset->transientorderedset (-> (OrderedSet %a) (TransientOrderedSet %a)))

Creates a transient ordered set from an existing persistent set.

s
The source set (unmodified).
returns
A mutable transient set that updates in place in O(1) time.

Shares nodes with s without copying. The transient performs copy-on-write on individual nodes as they are mutated.

See also: transientorderedset->orderedset, transientorderedset-empty

transientorderedset->orderedset

function ↑ Functions

(: transientorderedset->orderedset (-> (TransientOrderedSet %a) (OrderedSet %a)))

Converts a transient ordered set into a persistent set in O(1) time.

t
The transient ordered set (remains usable).
returns
A new immutable persistent ordered set.

Relinquishes ownership of current nodes to the persistent set. Subsequent writes to t perform copy-on-write without affecting the returned set.

See also: orderedset->transientorderedset

transientorderedset-add!

function ↑ Functions

(: transientorderedset-add! (-> (TransientOrderedSet %a) %a void))

Adds an element to a transient ordered set in place.

t
The transient set to modify.
x
The element to add.

See also: transientorderedset-add-all!, orderedset-add, add!

transientorderedset-add-all!

function ↑ Functions

(: transientorderedset-add-all! (-> (TransientOrderedSet %a) (Seq %a) void))

Adds all elements of a sequence to a transient ordered set in place.

t
The transient set to modify.
xs
Sequence of elements to add.

See also: transientorderedset-add!, orderedset-add-all

transientorderedset-remove!

function ↑ Functions

(: transientorderedset-remove! (-> (TransientOrderedSet %a) %a void))

Removes an element from a transient ordered set in place.

t
The transient set to modify.
x
The element to remove.

See also: transientorderedset-remove-all!, orderedset-remove

transientorderedset-remove-all!

function ↑ Functions

(: transientorderedset-remove-all! (-> (TransientOrderedSet %a) (Seq %a) void))

Removes all specified elements from a transient ordered set in place.

t
The transient set to modify.
xs
Sequence of elements to remove.

See also: transientorderedset-remove!, orderedset-remove-all

transientorderedset-filter!

function ↑ Functions

(: transientorderedset-filter! (-> (-> %a bool) (TransientOrderedSet %a) void))

Removes elements rejected by a predicate from a transient ordered set in place.

keep?
Predicate function called as (keep? x); #f removes element.
t
The transient set to modify.

Identifies all elements to remove before performing deletions, ensuring keep? observes the complete transient set state.

See also: orderedset-filter, transientorderedset-remove-all!

transientorderedset-contains?

function ↑ Functions

(: transientorderedset-contains? (-> (TransientOrderedSet %a) %a bool))

Tests if an element exists in the transient ordered set.

t
The transient set.
x
The element to locate.
returns
#t if present, otherwise #f.

See also: orderedset-contains?, ref

transientorderedset-length

function ↑ Functions

(: transientorderedset-length (-> (TransientOrderedSet %a) int))

Returns the number of elements in the transient ordered set.

t
The transient set.
returns
Current count of elements.

See also: transientorderedset-empty?, orderedset-length

transientorderedset-empty?

function ↑ Functions

(: transientorderedset-empty? (-> (TransientOrderedSet %a) bool))

Tests if the transient ordered set contains no elements.

t
The transient set.
returns
#t if empty, otherwise #f.

See also: transientorderedset-length, orderedset-empty?

transientorderedset-min

function ↑ Functions

(: transientorderedset-min (-> (TransientOrderedSet %a) (out %a) (Option %a)))

Returns the smallest element of a transient ordered set, or None if empty.

t
The transient set.
returns
(Some x) for the smallest element, or None if empty.

See also: transientorderedset-max, orderedset-min

transientorderedset-max

function ↑ Functions

(: transientorderedset-max (-> (TransientOrderedSet %a) (out %a) (Option %a)))

Returns the largest element of a transient ordered set, or None if empty.

t
The transient set.
returns
(Some x) for the largest element, or None if empty.

See also: transientorderedset-min, orderedset-max