4.12 Sorted Sets

8.12

4.12 Sorted Sets🔗ℹ

(require rebellion/collection/sorted-set)
	package: rebellion

A sorted set is a collection of distinct elements sorted according to some comparator. Sorted sets may be mutable, immutable, or unmodifiable. Two immutable sorted sets are equal? if and only if they contain the same elements and use equal? comparators. Two mutable sorted sets are equal? if and only if they will always contain the same elements and use equal? comparators, meaning that they share the same mutable state. This is not necessarily the same as being eq?, as some sorted sets may be views of others.

All sorted sets are sequences. When iterated, a sorted set traverses its elements in ascending order as defined by its comparator. To traverse a sorted set in descending order, either use in-sorted-set with #:descending? set to true, or reverse the sorted set with sorted-set-reverse. Note that sorted-set-reverse returns a view of the original set, not a copy, so it constructs the view in constant time regardless of the size of the original set.

procedure
(sorted-set? v) → boolean?
v : any/c

A predicate for sorted sets. Includes mutable, immutable, and unmodifiable sorted sets.

procedure
(mutable-sorted-set? v) → boolean?
v : any/c

A predicate for mutable sorted sets. Implies sorted-set?.

procedure
(immutable-sorted-set? v) → boolean?
v : any/c

A predicate for immutable sorted sets. Implies sorted-set?.

4.12.1 Constructing Sorted Sets🔗ℹ

procedure
(sorted-set element
...
#:comparator comparator) → immutable-sorted-set?
element : any/c
comparator : comparator?

Constructs an immutable sorted set containing elements sorted by comparator. The input elements may be given in any order, and duplicate elements (as in, elements that comparator considers equivalent) are ignored.

Example:

> (sorted-set 8 2 5 7 #:comparator natural<=>)
(immutable-sorted-set 2 5 7 8)

procedure
(sequence->sorted-set sequence
#:comparator comparator)
→ immutable-sorted-set?
sequence : (sequence/c any/c)
comparator : comparator?

Copies sequence into an immutable sorted set sorted by comparator. Duplicate elements of sequence (as in, elements that comparator considers equivalent) are ignored.

The sequence->sorted-set function makes an effort to avoid unnecessary copying if its input is already an immutable sorted set that’s sorted according to comparator. The precise details of this optimization are not guaranteed, but in general, converting a sequence to a sorted set and then converting it again takes the same amount of time as converting it once.

Examples:

> (sequence->sorted-set (list 4 8 2 1) #:comparator natural<=>)
(immutable-sorted-set 1 2 4 8)
> (sequence->sorted-set "hello world" #:comparator char<=>)
(immutable-sorted-set #\space #\d #\e #\h #\l #\o #\r #\w)

procedure
(sorted-set->immutable-sorted-set set) → immutable-sorted-set?
set : sorted-set?

Copies set into an immutable sorted set sorted by the same comparator. Like sequence->sorted-set, this function makes an effort to avoid unnecessary copying if its input is already an immutable sorted set.

Examples:

(define numbers
(make-mutable-sorted-set (list 1 2 3 4 5) #:comparator natural<=>))

> (sorted-set->immutable-sorted-set numbers)
(immutable-sorted-set 1 2 3 4 5)

procedure
(into-sorted-set comparator)
→ (reducer/c any/c immutable-sorted-set?)
comparator : comparator?

Constructs a reducer that reduces elements into an immutable sorted set sorted by comparator. Duplicate elements (as in, elements that comparator considers equivalent) are ignored.

Example:

> (transduce (list 4 8 2 1) #:into (into-sorted-set natural<=>))
(immutable-sorted-set 1 2 4 8)

procedure
(make-mutable-sorted-set [ initial-elements]
#:comparator comparator)
→ mutable-sorted-set?
initial-elements : (sequence/c any/c) = '()
comparator : comparator?

Constructs a new mutable sorted set containing initial-elements (which defaults to the empty list) sorted according to comparator. Duplicate elements in initial-elements (as in, elements that comparator considers equivalent) are ignored.

Examples:

> (make-mutable-sorted-set #:comparator natural<=>)
(mutable-sorted-set)
> (make-mutable-sorted-set (list 4 7 3 5) #:comparator natural<=>)
(mutable-sorted-set 3 4 5 7)

4.12.2 Querying Sorted Sets🔗ℹ

procedure
(in-sorted-set set
[ #:descending? descending?]) → (sequence/c any/c)
set : sorted-set?
descending? : boolean? = #false

Returns a sequence that iterates through the elements of set in ascending order. If descending? is true, the sequence iterates in descending order instead.

Examples:

(define fruits
  (sorted-set "apple" "orange" "grape" "banana"
              #:comparator string<=>))

> (transduce (in-sorted-set fruits)
             #:into (join-into-string ", "))
"apple, banana, grape, orange"
> (transduce (in-sorted-set fruits #:descending? #true)
             #:into (join-into-string ", "))
"orange, grape, banana, apple"

procedure
(sorted-set-empty? set) → boolean?
set : sorted-set?

Returns true if set contains no elements, returns false otherwise. Note that this operation can be combined with sorted-subset to efficiently determine if a range within a sorted set is empty.

Examples:

(define numbers (sorted-set 1 2 3 #:comparator real<=>))

> (sorted-set-empty? numbers)
#f
> (sorted-set-empty? (sorted-subset numbers (greater-than-range 5)))
#t

procedure
(sorted-set-size set) → natural?
set : sorted-set?

Returns the number of elements in set. Note that this operation can be combined with sorted-subset to efficiently determine how many elements are contained within a range of a sorted set.

Examples:

(define numbers
(sequence->sorted-set (in-range 5 15) #:comparator real<=>))

> (sorted-set-size numbers)
10
> (sorted-set-size (sorted-subset numbers (less-than-range 10)))
5

procedure
(sorted-set-comparator set) → comparator?
set : sorted-set?

Returns the comparator used by set to sort elements.

Example:

> (sorted-set-comparator (sorted-set 1 2 3 #:comparator natural<=>))
#<comparator:natural<=>>

procedure
(sorted-set-contains? set value) → boolean?
set : sorted-set?
value : any/c

Returns true if set contains value, returns false otherwise.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator natural<=>))

> (sorted-set-contains? numbers 2)
#t
> (sorted-set-contains? numbers 100)
#f

procedure
(sorted-set-contains-any? set sequence) → boolean?
set : sorted-set?
sequence : (sequence/c any/c)

Returns true if set contains at least one element in sequence, returns false otherwise.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator natural<=>))

> (sorted-set-contains-any? numbers (list 1 10 100))
#t
> (sorted-set-contains-any? numbers (vector 11 12 13))
#f
> (sorted-set-contains-any? numbers (list))
#f

procedure
(sorted-set-contains-all? set sequence) → boolean?
set : sorted-set?
sequence : (sequence/c any/c)

Returns true if set contains every element in sequence, returns false otherwise. If sequence is empty, then by the principle of vacuous truth the result is true.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator natural<=>))

> (sorted-set-contains-all? numbers (list 1 2 3))
#t
> (sorted-set-contains-all? numbers (vector 1 10 100))
#f
> (sorted-set-contains-all? numbers (list))
#t

procedure
(sorted-set-contains-none? set sequence) → boolean?
set : sorted-set?
sequence : (sequence/c any/c)

Returns true if set does not contain any element in sequence, returns false otherwise. If sequence is empty, then by the principle of vacuous truth the result is true.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator natural<=>))

> (sorted-set-contains-none? numbers (list 11 12 13))
#t
> (sorted-set-contains-none? numbers (vector 1 10 100))
#f
> (sorted-set-contains-none? numbers (list))
#t

procedure
(sorted-set-least-element set) → option?
set : sorted-set?

Returns the first and smallest element in set, or absent if set is empty.

Examples:

> (sorted-set-least-element (sorted-set 5 2 6 #:comparator natural<=>))
(present 2)
> (sorted-set-least-element (sorted-set #:comparator natural<=>))
#<absent>

procedure
(sorted-set-greatest-element set) → option?
set : sorted-set?

Returns the last and largest element in set, or absent if set is empty.

Examples:

> (sorted-set-greatest-element (sorted-set 5 2 6 #:comparator natural<=>))
(present 6)
> (sorted-set-greatest-element (sorted-set #:comparator natural<=>))
#<absent>

procedure
(sorted-set-element-less-than set
upper-bound) → option?
set : sorted-set?
upper-bound : any/c

Returns the largest element in set less than upper-bound, or absent if no such element exists.

Examples:

(define numbers
(sorted-set 5 10 20 #:comparator natural<=>))

> (sorted-set-element-less-than numbers 12)
(present 10)
> (sorted-set-element-less-than numbers 2)
#<absent>

procedure
(sorted-set-element-greater-than set
lower-bound) → option?
set : sorted-set?
lower-bound : any/c

Returns the smallest element in set greater than lower-bound, or absent if no such element exists.

Examples:

(define numbers
(sorted-set 5 10 20 #:comparator natural<=>))

> (sorted-set-element-greater-than numbers 7)
(present 10)
> (sorted-set-element-greater-than numbers 20)
#<absent>

procedure
(sorted-set-element-at-most set
upper-bound) → option?
set : sorted-set?
upper-bound : any/c

Returns the largest element in set less than or equivalent to upper-bound, or absent if no such element exists.

Examples:

(define numbers
(sorted-set 5 10 20 #:comparator natural<=>))

> (sorted-set-element-at-most numbers 12)
(present 10)
> (sorted-set-element-at-most numbers 10)
(present 10)
> (sorted-set-element-at-most numbers 2)
#<absent>

procedure
(sorted-set-element-at-least set
lower-bound) → option?
set : sorted-set?
lower-bound : any/c

Returns the smallest element in set greater than or equivalent to lower-bound, or absent if no such element exists.

Examples:

(define numbers
(sorted-set 5 10 20 #:comparator natural<=>))

> (sorted-set-element-at-least numbers 7)
(present 10)
> (sorted-set-element-at-least numbers 5)
(present 5)
> (sorted-set-element-at-least numbers 30)
#<absent>

4.12.3 Sorted Set Views🔗ℹ

procedure
(sorted-subset set element-range) → sorted-set?
set : sorted-set?
element-range : range?

Returns a view of the elements in set that fall within element-range. The returned subset is not a copy! It is a read-through view of set, and any modifications to set will be reflected in the returned view. The returned view is an immutable-sorted-set? if set is immutable, and similarly it is a mutable-sorted-set? if set is mutable.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator real<=>))

> (sorted-subset numbers (closed-range 2 4))
(immutable-sorted-set 2 3 4)

When used on mutable sorted sets, the returned set is also a write-through view — mutating the returned subset will mutate the original, underlying set. The returned subset supports all of the same operations as ordinary mutable sorted sets, with the exception that inserting elements outside element-range is disallowed. Additionally, note that calling sorted-set-remove! on the subset view with an element outside element-range will have no effect on either the subset view or the original set, as sorted-set-remove! does nothing on sets that do not contain the element being removed.

Examples:

(define numbers
(make-mutable-sorted-set (list 1 2 3 4 5) #:comparator real<=>))
(define numbers>3
(sorted-subset numbers (greater-than-range 3)))

> numbers>3
(mutable-sorted-set 4 5)
> (sorted-set-remove! numbers>3 4)
> numbers>3
(mutable-sorted-set 5)
> numbers
(mutable-sorted-set 1 2 3 5)

procedure
(sorted-set-reverse set) → sorted-set?
set : sorted-set?

Returns a view of set that sorts elements in the opposite order. The returned set is not a copy! It is a read-through view of set, and any modifications to set will be reflected in the returned view. The returned view is an immutable-sorted-set? if set is immutable, and similarly it is a mutable-sorted-set? if set is mutable. Note that calling sorted-set-comparator on the returned view returns a reversed version of the comparator on set.

When used on mutable sorted sets, the returned set is also a write-through view — mutating the returned set will mutate the original, underlying set. The returned set supports all of the same operations as ordinary mutable sorted sets.

Examples:

(define numbers
(sorted-set 1 2 3 4 5 #:comparator natural<=>))

> (sorted-set-reverse numbers)
(immutable-sorted-set 5 4 3 2 1)

procedure
(unmodifiable-sorted-set set)
→ (and/c sorted-set? (not/c mutable-sorted-set?))
set : sorted-set?

Returns an unmodifiable view of set. If set is not mutable, it is returned directly instead.

Examples:

(define mutable-numbers
  (make-mutable-sorted-set (list 1 2 3 4 5) #:comparator natural<=>))
(define numbers (unmodifiable-sorted-set mutable-numbers))

> (sorted-set-add! numbers 6)
sorted-set-add!: contract violation
  expected: mutable-sorted-set?
  given: (sorted-set 1 2 3 4 5)
  in: the 1st argument of
      (-> mutable-sorted-set? any/c void?)
  contract from:
      <pkgs>/rebellion/collection/private/sorted-set-interfa
ce.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/collection/private/sorted-set-interfa
ce.rkt:27:3

4.12.3.1 Synchronized Sorted Sets🔗ℹ

procedure
(synchronized-sorted-set? v) → boolean?
v : any/c

A predicate for synchronized views of sorted sets. Implies mutable-sorted-set?.

procedure
(synchronized-sorted-set set) → synchronized-sorted-set?
set : mutable-sorted-set?

Returns a synchronized view of set. The returned view is thread-safe provided that set is not accessed directly except by the view. To ensure this, consider calling synchronized-sorted-set on the result of make-mutable-sorted-set immediately, without storing the underlying set in a variable.

Examples:

(define numbers
(synchronized-sorted-set (make-mutable-sorted-set #:comparator natural<=>)))

> (for ([x (in-range 0 10)])
(thread (λ () (sorted-set-add! numbers x))))
> (sorted-set-size numbers)
10

Warning: the returned view is not thread-safe when iterated over as a sequence or when using in-sorted-set. All iteration over the returned view must be guarded by the synchronized view’s lock to ensure thread safety and atomicity. The lock can be acquired explicitly by using synchronized-sorted-set-lock.

Examples:

> (lock!
   (read-write-lock-write-lock (synchronized-sorted-set-lock numbers))
   (λ ()
     (define sum
       (for/sum ([x (in-sorted-set numbers)])
         x))
     (sorted-set-add! numbers sum)))
> numbers
(mutable-sorted-set 0 1 2 3 4 5 6 7 8 9 45)

procedure
(synchronized-sorted-set-lock set) → read-write-lock?
set : synchronized-sorted-set?

Returns the read-write lock that guards access to set. The returned lock is reentrant.

4.12.4 Modifying Sorted Sets🔗ℹ

procedure
(sorted-set-add set element) → immutable-sorted-set?
set : immutable-sorted-set?
element : any/c

Functionally inserts element into set by returning a new immutable sorted set containing all of the elements of set and element, if it did not already contain element. The input set is not modified.

Examples:

(define numbers
(sorted-set 10 20 30 #:comparator natural<=>))

> (sorted-set-add numbers 14)
(immutable-sorted-set 10 14 20 30)

procedure
(sorted-set-add! set element) → void?
set : mutable-sorted-set?
element : any/c

Inserts element into set if it does not already contain element.

Examples:

(define numbers
(make-mutable-sorted-set (list 10 20 30) #:comparator natural<=>))

> (sorted-set-add! numbers 14)
> numbers
(mutable-sorted-set 10 14 20 30)

procedure
(sorted-set-add-all set elements) → immutable-sorted-set?
set : immutable-sorted-set?
elements : (sequence/c any/c)

Functionally inserts each element of elements into set by returning a new immutable sorted set containing all of the elements of set and elements. There is no requirement that elements is sorted, and duplicates in elements are ignored. The input set is not modified. When given two sorted sets, this is the union operation on immutable sorted sets.

Examples:

(define numbers
(sorted-set 10 20 30 #:comparator natural<=>))

> (sorted-set-add-all numbers (list 25 5 35 15))
(immutable-sorted-set 5 10 15 20 25 30 35)

procedure
(sorted-set-add-all! set elements) → void?
set : mutable-sorted-set?
elements : (sequence/c any/c)

Inserts each element of elements into set. There is no requirement that elements is sorted, and duplicates in elements are ignored. When given two sorted sets, this is the union operation on mutable sorted sets.

Examples:

(define numbers
(make-mutable-sorted-set (list 10 20 30) #:comparator natural<=>))

> (sorted-set-add-all! numbers (list 25 5 35 15))
> numbers
(mutable-sorted-set 5 10 15 20 25 30 35)

procedure
(sorted-set-remove set element) → immutable-sorted-set?
set : immutable-sorted-set?
element : any/c

Functionally removes element from set by returning a new immutable sorted set containing all of the elements of set except for element. The input set is not modified.

Examples:

(define numbers
(sorted-set 10 20 30 #:comparator natural<=>))

> (sorted-set-remove numbers 20)
(immutable-sorted-set 10 30)

procedure
(sorted-set-remove! set element) → void?
set : mutable-sorted-set?
element : any/c

Removes element from set.

Examples:

(define numbers
(make-mutable-sorted-set (list 10 20 30) #:comparator natural<=>))

> (sorted-set-remove! numbers 20)
> numbers
(mutable-sorted-set 10 30)

procedure
(sorted-set-remove-all set elements) → immutable-sorted-set?
set : immutable-sorted-set?
elements : (sequence/c any/c)

Functionally removes each element of elements from set by returning a new immutable sorted set containing all of the elements of set except those in elements. There is no requirement that elements is sorted, and duplicates in elements are ignored. The input set is not modified. When given two sorted sets, this is the complement operation on immutable sorted sets.

Examples:

(define numbers
(sorted-set 10 20 30 #:comparator natural<=>))

> (sorted-set-remove-all numbers (list 20 30 40))
(immutable-sorted-set 10)

procedure
(sorted-set-remove-all! set elements) → void?
set : mutable-sorted-set?
elements : (sequence/c any/c)

Removes each element of elements from set. There is no requirement that elements is sorted, and duplicates in elements are ignored. When given two sorted sets, this is the complement operation on mutable sorted sets.

Examples:

(define numbers
(make-mutable-sorted-set (list 10 20 30) #:comparator natural<=>))

> (sorted-set-remove-all! numbers (list 20 30 40))
> numbers
(mutable-sorted-set 10)

procedure
(sorted-set-clear! set) → void?
set : mutable-sorted-set?

Removes all elements from set. On its own this operation isn’t all that useful, but it can be composed with sorted-subset to delete a range within a sorted set.

Examples:

(define numbers
(make-mutable-sorted-set (list 10 20 30) #:comparator real<=>))
(define numbers>15
(sorted-subset numbers (greater-than-range 15)))

> numbers>15
(mutable-sorted-set 20 30)
> (sorted-set-clear! numbers>15)
> numbers
(mutable-sorted-set 10)

4.12.5 Sorted Set Builders🔗ℹ

A sorted set builder is a mutable object that can create sorted sets. Values can be added to a builder incrementally with sorted-set-builder-add, and immutable sorted sets can be built from a builder with build-sorted-set. Builders can be reused — a single builder can build many sorted sets, and elements can be added to the builder after its already built sets. Each built set is a superset of the sets built before it. Creating a sorted set with a builder will usually lead to faster performance than creating an empty sorted set and repeatedly insesrting elements into it.

procedure
(sorted-set-builder? v) → boolean?
v : any/c

A predicate for sorted set builders.

procedure
(make-sorted-set-builder element-comparator)
→ sorted-set-builder?
element-comparator : comparator?

Creates a new sorted set builder that builds sets sorted by element-comparator.

procedure
(sorted-set-builder-add builder
element ...+) → sorted-set-builder?
builder : sorted-set-builder?
element : any/c

Adds each element to builder, then returns builder. This mutates the builder! The builder is returned as a convenience to the caller when used with operations like for/fold. Duplicate elements are ignored.

Examples:

(define builder (make-sorted-set-builder natural<=>))

> (sorted-set-builder-add builder 7 2 5 2)
#<sorted-set-builder>
> (build-sorted-set builder)
(immutable-sorted-set 2 5 7)

procedure
(sorted-set-builder-add-all builder
elements) → sorted-set-builder?
builder : sorted-set-builder?
elements : (sequence/c any/c)

Adds elements to builder, then returns builder. This mutates the builder! The builder is returned as a convenience to the caller when used with operations like for/fold. Duplicate elements are ignored.

Examples:

(define builder (make-sorted-set-builder natural<=>))

> (sorted-set-builder-add-all builder (in-range 0 5))
#<sorted-set-builder>
> (build-sorted-set builder)
(immutable-sorted-set 0 1 2 3 4)

procedure
(build-sorted-set builder) → immutable-sorted-set?
builder : sorted-set-builder?

Builds an immutable sorted set from the contents of builder, sorted according to the comparator used by builder. Does not mutate builder in any way, and builder can still be used to build additional sorted sets afterwards.

Examples:

(define builder (make-sorted-set-builder natural<=>))

> (build-sorted-set (sorted-set-builder-add-all builder (in-range 0 5)))
(immutable-sorted-set 0 1 2 3 4)
> (build-sorted-set (sorted-set-builder-add-all builder (in-range 10 15)))
(immutable-sorted-set 0 1 2 3 4 10 11 12 13 14)
> (build-sorted-set (sorted-set-builder-add builder 8 24))
(immutable-sorted-set 0 1 2 3 4 8 10 11 12 13 14 24)

1	Base Libraries
2	Data Types
3	Streaming Computations
4	Collections
5	Concurrency
6	Binary Data
7	Module Utilities
8	Other Libraries

4.1	Choosing Collections
4.2	Entries
4.3	Lists
4.4	Vectors
4.5	Vector Builders
4.6	Immutable Vectors
4.7	Sets
4.8	Hash Tables
4.9	Multisets
4.10	Multidicts
4.11	Association Lists
4.12	Sorted Sets
4.13	Sorted Maps
4.14	Range Sets
4.15	Keysets
4.16	Records
4.17	Tables

4.12.1	Constructing Sorted Sets
4.12.2	Querying Sorted Sets
4.12.3	Sorted Set Views
4.12.4	Modifying Sorted Sets
4.12.5	Sorted Set Builders