4.13 Sorted Maps

8.12

4.13 Sorted Maps🔗ℹ

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

A sorted map is a collection of key-value mappings whose keys are unique and sorted according to some comparator. Sorted maps may be mutable, immutable, or unmodifiable. Two immutable sorted maps are equal? if they contain the same entries and use equal? comparators. Two mutable sorted maps are equal? if they will always contain the same entries and use equal? comparators, meaning that they share the same mutable state. This is not necessarily the same as being eq?, as some sorted maps may be views of others.

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

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

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

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

A predicate for mutable sorted maps. Implies sorted-map?.

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

A predicate for immutable sorted maps. Implies sorted-map?.

4.13.1 Constructing Sorted Maps🔗ℹ

procedure
(sorted-map key
value ...
...
#:key-comparator key-comparator)
→ immutable-sorted-map?
  key : any/c
  value : any/c
  key-comparator : comparator?

Constructs an immutable sorted map mapping each key to the corresponding value, where keys are sorted by key-comparator. The input keys may be given in any order. Duplicate keys (as in, keys that key-comparator considers equivalent) are disallowed and result in a contract error.

Example:

> (sorted-map 3 'c 1 'a 4 'd 2 'b 5 'e #:key-comparator natural<=>)
(immutable-sorted-map 1 'a 2 'b 3 'c 4 'd 5 'e)

procedure
(make-mutable-sorted-map [ initial-entries]
#:key-comparator key-comparator)
→ mutable-sorted-map?
initial-entries : (sequence/c entry?) = '()
key-comparator : comparator?

Constructs a new mutable sorted map containing initial-entries (which defaults to the empty list) sorted by key according to key-comparator. Duplicate keys (as in, keys that key-comparator considers equivalent) are disallowed and result in a contract error.

Examples:

> (make-mutable-sorted-map #:key-comparator natural<=>)
(mutable-sorted-map
> (make-mutable-sorted-map
(in-hash-entries (hash 3 'c 1 'a 4 'd 2 'b))
#:key-comparator natural<=>)
(mutable-sorted-map 1 'a 2 'b 3 'c 4 'd)

procedure
(entry-sequence->sorted-map entries
#:key-comparator key-comparator)
→ immutable-sorted-map?
entries : (sequence/c entry?)
key-comparator : comparator?

Constructs an immutable sorted map containing each mapping in entries, with keys sorted by key-comparator. The input entries may be given in any order. Duplicate keys (as in, keys that key-comparator considers equivalent) are disallowed and result in a contract error.

Examples:

(define h (hash 3 'c 1 'a 4 'd 2 'b 5 'e))

> (entry-sequence->sorted-map (in-hash-entries h) #:key-comparator natural<=>)
(immutable-sorted-map 1 'a 2 'b 3 'c 4 'd 5 'e)

procedure
(into-sorted-map key-comparator)
→ (reducer/c entry? immutable-sorted-map?)
key-comparator : comparator?

Returns a reducer that reduces a sequence of entries into an immutable sorted map, where keys are sorted by key-comparator. Duplicate keys (as in, keys that key-comparator considers equivalent) are disallowed and result in a contract error.

Examples:

(define h (hash 3 'c 1 'a 4 'd 2 'b 5 'e))

> (transduce (in-hash-entries h) #:into (into-sorted-map natural<=>))
(immutable-sorted-map 1 'a 2 'b 3 'c 4 'd 5 'e)

syntax
(for/sorted-map #:key-comparator key-comparator (for-clause ...)
  body-or-break ... body)

   key-comparator : comparator?
   body : entry?

Like for, but collects the iterated entries into a sorted map.

Example:

> (for/sorted-map #:key-comparator char<=>
    ([char (in-string "cat")]
     [i (in-naturals)])
    (entry char i))
(immutable-sorted-map #\a 1 #\c 0 #\t 2)

syntax
(for*/sorted-map #:key-comparator key-comparator (for-clause ...)
  body-or-break ... body)

   key-comparator : comparator?
   body : entry?

Like for*, but collects the iterated entries into a sorted map.

Example:

> (for*/sorted-map #:key-comparator char<=>
    ([str (in-list (list "abc" "tuv" "xyz"))]
     [char (in-string str)])
    (entry char str))
(immutable-sorted-map
  #\a "abc"
  #\b "abc"
  #\c "abc"
  #\t "tuv"
  #\u "tuv"
  #\v "tuv"
  #\x "xyz"
  #\y "xyz"
  #\z "xyz")

4.13.2 Iterating Sorted Maps🔗ℹ

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sequence->list (in-sorted-map map))
(list (entry 1 'a) (entry 2 'b) (entry 3 'c))

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sequence->list (in-sorted-map-keys map))
'(1 2 3)

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

Returns a sequence that iterates through the values of map in ascending order by key. If descending? is true, the sequence iterates in descending order instead.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sequence->list (in-sorted-map-values map))
'(a b c)

4.13.3 Querying Sorted Maps🔗ℹ

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-empty? map)
#f
> (sorted-map-empty? (sorted-submap map (less-than-range 1 #:comparator natural<=>)))
#t

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-size map)
3
> (sorted-map-size (sorted-submap map (at-least-range 2 #:comparator natural<=>)))
2

procedure
(sorted-map-key-comparator map) → comparator?
map : sorted-map?

Returns the comparator used by map to sort keys.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-key-comparator map)
#<comparator:natural<=>>

procedure
(sorted-map-contains-key? map key) → boolean?
map : sorted-map?
key : any/c

Returns true if map contains an entry for key, returns false otherwise.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-contains-key? map 2)
#t
> (sorted-map-contains-key? map 4)
#f

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

Returns true if map maps at least one key to value, returns false otherwise.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-contains-value? map 'b)
#t
> (sorted-map-contains-value? map 'z)
#f

procedure
(sorted-map-contains-entry? map entry) → boolean?
map : sorted-map?
entry : entry?

Returns true if map contains entry.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-contains-entry? map (entry 1 'a))
#t
> (sorted-map-contains-entry? map (entry 2 'b))
#t
> (sorted-map-contains-entry? map (entry 1 'b))
#f

procedure
(sorted-map-get map key [failure-result]) → any/c
  map : sorted-map?
  key : any/c
  failure-result : failure-result/c = (λ () (raise ...))

Returns the value mapped by key in map. If no value exists for key, then failure-result determines the result: if it’s a procedure it’s called with no arguments to produce the result, if it’s not a procedure it’s returned directly.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-get map 2)
'b
> (sorted-map-get map 4)
sorted-map-get: no value for key;
key: 4
map: (immutable-sorted-map 1 'a 2 'b 3 'c)
> (sorted-map-get map 4 'missing)
'missing

procedure
(sorted-map-get-option map key) → option?
map : sorted-map?
key : any/c

Returns the value mapped by key in map, or absent if no value exists for key.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-get-option map 2)
(present 'b)
> (sorted-map-get-option map 4)
#<absent>

procedure
(sorted-map-get-entry map
key
[ failure-result]) → entry?
  map : sorted-map?
  key : any/c
  failure-result : failure-result/c = (λ () (raise ...))

Returns the entry for key in map. If no value exists for key, then failure-result determines the resulting entry’s value: if it’s a procedure it’s called with no arguments to produce the value, if it’s not a procedure it’s used directly as the resulting entry’s value.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-get-entry map 2)
(entry 2 'b)
> (sorted-map-get-entry map 4)
sorted-map-get-entry: no value for key;
key: 4
map: (immutable-sorted-map 1 'a 2 'b 3 'c)
> (sorted-map-get-entry map 4 'missing)
(entry 4 'missing)

procedure
(sorted-map-least-key map) → option?
map : sorted-map?

Returns the first and smallest key in map, or absent if map is empty.

Examples:

> (sorted-map-least-key (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(present 1)
> (sorted-map-least-key (sorted-map #:key-comparator natural<=>))
#<absent>

procedure
(sorted-map-greatest-key map) → option?
map : sorted-map?

Returns the last and largest key in map, or absent if map is empty.

Examples:

> (sorted-map-greatest-key (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(present 3)
> (sorted-map-greatest-key (sorted-map #:key-comparator natural<=>))
#<absent>

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-key-less-than map 2)
(present 1)
> (sorted-map-key-less-than map 1)
#<absent>

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-key-greater-than map 2)
(present 3)
> (sorted-map-key-greater-than map 3)
#<absent>

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-key-at-most map 5)
(present 3)
> (sorted-map-key-at-most map 0)
#<absent>

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-key-at-least map 0)
(present 1)
> (sorted-map-key-at-least map 5)
#<absent>

procedure
(sorted-map-least-entry map) → (option/c entry?)
map : sorted-map?

Returns the entry for the first and smallest key in map, or absent if map is empty.

Examples:

> (sorted-map-least-entry (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(present (entry 1 'a))
> (sorted-map-least-entry (sorted-map #:key-comparator natural<=>))
#<absent>

procedure
(sorted-map-greatest-entry map) → (option/c entry?)
map : sorted-map?

Returns the entry for the last and largest key in map, or absent if map is empty.

Examples:

> (sorted-map-greatest-entry (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(present (entry 3 'c))
> (sorted-map-greatest-entry (sorted-map #:key-comparator natural<=>))
#<absent>

procedure
(sorted-map-entry-less-than map
upper-key-bound)
→ (option/c entry?)
map : sorted-map?
upper-key-bound : any/c

Returns the entry for the largest key in map less than upper-key-bound, or absent if no such key exists.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-entry-less-than map 2)
(present (entry 1 'a))
> (sorted-map-entry-less-than map 1)
#<absent>

procedure
(sorted-map-entry-greater-than map
lower-key-bound)
→ (option/c entry?)
map : sorted-map?
lower-key-bound : any/c

Returns the entry for the smallest key in map greater than lower-key-bound, or absent if no such key exists.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-entry-greater-than map 2)
(present (entry 3 'c))
> (sorted-map-entry-greater-than map 3)
#<absent>

procedure
(sorted-map-entry-at-most map
upper-key-bound) → (option/c entry?)
map : sorted-map?
upper-key-bound : any/c

Returns the entry for the largest key in map less than or equivalent to upper-key-bound, or absent if no such key exists.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-entry-at-most map 5)
(present (entry 3 'c))
> (sorted-map-entry-at-most map 0)
#<absent>

procedure
(sorted-map-entry-at-least map
lower-key-bound) → (option/c entry?)
map : sorted-map?
lower-key-bound : any/c

Returns the entry for the smallest key in map greater than or equivalent to lower-key-bound, or absent if no such key exists.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-entry-at-least map 0)
(present (entry 1 'a))
> (sorted-map-entry-at-least map 5)
#<absent>

4.13.4 Sorted Map Views🔗ℹ

procedure
(sorted-submap map key-range) → sorted-map?
map : sorted-map?
key-range : range?

Returns a view of the entries in map with keys that fall within key-range. The returned submap is not a copy! It is a read-through view of map, and any modifications to map will be reflected in the returned view. The returned view is an immutable-sorted-map? if map is immutable, and similarly it is a mutable-sorted-map? if map is mutable.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-submap map (at-most-range 2 #:comparator natural<=>))
(immutable-sorted-map 1 'a 2 'b)

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

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

(define map<=2
  (sorted-submap map (at-most-range 2 #:comparator natural<=>)))

> map<=2
(mutable-sorted-map 1 'a 2 'b)
> (sorted-map-remove! map<=2 1)
> map<=2
(mutable-sorted-map 2 'b)
> map
(mutable-sorted-map 2 'b 3 'c)

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

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

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

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-reverse map)
(immutable-sorted-map 3 'c 2 'b 1 'a)

procedure
(sorted-map-keys map) → sorted-set?
map : sorted-map?

Returns a view of the keys in map. The returned set is not a copy! It is a read-through view of map, and modifications to map will be reflected in the returned view. The returned view is an immutable-sorted-set? if map is immutable, and similarly it is a mutable-sorted-set? if map is mutable.

Example:

> (sorted-map-keys (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(immutable-sorted-set 1 2 3)

When used on mutable sorted maps, the returned set is also a write-through view — mutating the returned key set will mutate the original, underlying map. The returned key set only supports set removal operations and cannot be used to insert new entries into map.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-set-remove! (sorted-map-keys map) 2)
> map
(mutable-sorted-map 1 'a 3 'c)
> (sorted-set-add! (sorted-map-keys map) 5)
sorted-set-add!: sorted map key sets do not support
insertion
  key set: (sorted-set 1 3)
  element: 5

procedure
(sorted-map-entries map) → sorted-set?
map : sorted-map?

Returns a view of the entries in map. The returned set is not a copy! It is a read-through view of map, and modifications to map will be reflected in the returned view. The returned view is an immutable-sorted-set? if map is immutable, and similarly it is a mutable-sorted-set? if map is mutable. The returned set uses a comparator on entries that ignores the entry’s value and compares its keys using the same comparator as map.

Example:

> (sorted-map-entries (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))
(sorted-set (entry 1 'a) (entry 2 'b) (entry 3 'c))

When used on mutable sorted maps, the returned set is also a write-through view — mutating the returned entry set will mutate the original, underlying map. The returned set supports all of the same operations as ordinary mutable sorted sets. Note that because it uses a comparator that ignores entry values, it cannot be used to insert entries with duplicate keys.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-set-remove! (sorted-map-entries map) (entry 2 'b))
> map
(mutable-sorted-map 1 'a 3 'c)
> (sorted-set-add! (sorted-map-entries map) (entry 5 'b))
> map
(mutable-sorted-map 1 'a 3 'c 5 'b)

4.13.5 Modifying Sorted Maps🔗ℹ

procedure
(sorted-map-get! map key failure-result) → any/c
  map : mutable-sorted-map?
  key : any/c
  failure-result : failure-result/c

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-map-get! map 2 'missing)
'b
> (sorted-map-get! map 5 'missing)
'missing
> map
(mutable-sorted-map 1 'a 2 'b 3 'c 5 'missing)

procedure
(sorted-map-get-entry! map
key
failure-result) → entry?
  map : sorted-map?
  key : any/c
  failure-result : failure-result/c

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-map-get-entry! map 2 'missing)
(entry 2 'b)
> (sorted-map-get-entry! map 5 'missing)
(entry 5 'missing)
> map
(mutable-sorted-map 1 'a 2 'b 3 'c 5 'missing)

procedure
(sorted-map-put map key value) → immutable-sorted-map?
  map : immutable-sorted-map?
  key : any/c
  value : any/c

Functionally inserts a mapping from key to value into map by returning a new immutable sorted map containing all of the entries of map and the additional inserted mapping from key to value. The input map is not modified.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-put map 4 'd)
(immutable-sorted-map 1 'a 2 'b 3 'c 4 'd)
> (sorted-map-put map 2 'x)
(immutable-sorted-map 1 'a 2 'x 3 'c)

procedure
(sorted-map-put! map key value) → void?
  map : mutable-sorted-map?
  key : any/c
  value : any/c

Inserts a mapping from key to value into map, overwriting any existing mapping for key in map.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-map-put! map 2 'x)
> map
(mutable-sorted-map 1 'a 2 'x 3 'c)
> (sorted-map-put! map 4 'd)
> map
(mutable-sorted-map 1 'a 2 'x 3 'c 4 'd)

procedure
(sorted-map-put-all map entries) → immutable-sorted-map?
map : immutable-sorted-map?
entries : (sequence/c entry?)

Functionally inserts a mapping for each key-value entry in entries into map by returning a new immutable sorted map containing all of the entries of map and the additional inserted mappings. If any entries have duplicate keys, a contract error is raised.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-put-all map (in-hash-entries (hash 2 'x 3 'x 4 'x)))
(immutable-sorted-map 1 'a 2 'x 3 'x 4 'x)

procedure
(sorted-map-put-all! map entries) → void?
map : mutable-sorted-map?
entries : (sequence/c entry?)

Inserts a mapping for each key-value entry in entries into map. If any entries have duplicate keys, a contract error is raised.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-map-put-all! map (in-hash-entries (hash 2 'x 3 'x 4 'x)))
> map
(mutable-sorted-map 1 'a 2 'x 3 'x 4 'x)

procedure
(sorted-map-put-if-absent map key value)
→ (result/c immutable-sorted-map? any/c)
  map : immutable-sorted-map?
  key : any/c
  value : any/c

Functionally inserts a mapping from key to value into map if map does not already contain a mapping for key. If map already contains key, a failure containing the preexisting value is returned. Otherwise, returns a success value of a new immutable sorted map containing all of the entries of map and the additional inserted mapping from key to value. The input map is not modified.

Examples:

(define map (sorted-map 1 'a 2 'b 3 'c #:key-comparator natural<=>))

> (sorted-map-put-if-absent map 4 'd)
(success (immutable-sorted-map 1 'a 2 'b 3 'c 4 'd))
> (sorted-map-put-if-absent map 2 'x)
(failure 'b)

procedure
(sorted-map-put-if-absent! map key value) → option?
  map : mutable-sorted-map?
  key : any/c
  value : any/c

Inserts a mapping from key to value into map if map does not already contain a mapping for key. If map already contains key, the map is not modified and the preexisting value is returned.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 1 'a) (entry 2 'b) (entry 3 'c))
   #:key-comparator natural<=>))

> (sorted-map-put-if-absent! map 4 'd)
#<absent>
> map
(mutable-sorted-map 1 'a 2 'b 3 'c 4 'd)
> (sorted-map-put-if-absent! map 2 'x)
(present 'b)
> map
(mutable-sorted-map 1 'a 2 'b 3 'c 4 'd)

procedure
(sorted-map-update map
key
updater
[ failure-result]) → immutable-sorted-map?
  map : immutable-sorted-map?
  key : any/c
  updater : (-> any/c any/c)
  failure-result : failure-result/c = (λ () (raise ...))

Functionally updates the value for key in map by applying updater to the value and returning a new immutable sorted map containing all the entries of map along with a mapping from key to the value returned by updater. If no value exists for key, then failure-result determines the value passed to updater: if it’s a procedure it’s called with no arguments to produce the value, if it’s not a procedure it’s passed to updater directly. The input map is not modified.

Examples:

(define map (sorted-map 'a 1 'b 1 'c 1 #:key-comparator symbol<=>))

> (sorted-map-update map 'b add1)
(immutable-sorted-map 'a 1 'b 2 'c 1)
> (sorted-map-update map 'd add1)
sorted-map-update: no value for key;
key: 'd
map: (immutable-sorted-map 'a 1 'b 1 'c 1)
> (sorted-map-update map 'd add1 0)
(immutable-sorted-map 'a 1 'b 1 'c 1 'd 1)

procedure
(sorted-map-update! map
key
updater
[ failure-result]) → void?
  map : mutable-sorted-map?
  key : any/c
  updater : (-> any/c any/c)
  failure-result : failure-result/c = (λ () (raise ...))

Updates the value for key in map by applying updater to the value and using the returned value as the new value for key. If no value exists for key, then failure-result determines the value passed to updater: if it’s a procedure it’s called with no arguments to produce the value, if it’s not a procedure it’s passed to updater directly.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 'a 1) (entry 'b 1) (entry 'c 1))
   #:key-comparator symbol<=>))

> (sorted-map-update! map 'b add1)
> map
(mutable-sorted-map 'a 1 'b 2 'c 1)
> (sorted-map-update! map 'd add1)
sorted-map-update!: no value for key;
  key: 'd
  map: (mutable-sorted-map 'a 1 'b 2 'c 1)
> (sorted-map-update! map 'd add1 0)
> map
(mutable-sorted-map 'a 1 'b 2 'c 1 'd 1)

procedure
(sorted-map-remove map key) → immutable-sorted-map?
map : immutable-sorted-map?
key : any/c

Functionally removes the mapping for key from map by returning a new immutable sorted map with all of the entries in map except for the entry for key. The input map is not modified.

Examples:

(define map (sorted-map 'a 1 'b 1 'c 1 #:key-comparator symbol<=>))

> (sorted-map-remove map 'b)
(immutable-sorted-map 'a 1 'c 1)

procedure
(sorted-map-remove! map key) → void?
map : mutable-sorted-map?
key : any/c

Removes the mapping for key from map.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 'a 1) (entry 'b 1) (entry 'c 1))
   #:key-comparator symbol<=>))

> (sorted-map-remove! map 'b)
> map
(mutable-sorted-map 'a 1 'c 1)

procedure
(sorted-map-remove-all map keys) → immutable-sorted-map?
map : immutable-sorted-map?
keys : (sequence/c any/c)

Functionally removes the mappings for keys from map by returning a new immutable sorted map with all of the entries in map except for the entries for keys. The input map is not modified. Duplicate keys are ignored.

Examples:

(define map (sorted-map 'a 1 'b 1 'c 1 #:key-comparator symbol<=>))

> (sorted-map-remove-all map (list 'b 'c 'd))
(immutable-sorted-map 'a 1)

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

Removes the mappings for keys from map. Duplicate keys are ignored.

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 'a 1) (entry 'b 1) (entry 'c 1))
   #:key-comparator symbol<=>))

> (sorted-map-remove-all! map (list 'b 'c 'd))
> map
(mutable-sorted-map 'a 1)

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

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

Examples:

(define map
  (make-mutable-sorted-map
   (list (entry 'a 1) (entry 'b 1) (entry 'c 1))
   #:key-comparator symbol<=>))

> (sorted-map-clear!
   (sorted-submap map (less-than-range 'c #:comparator symbol<=>)))
> map
(mutable-sorted-map 'c 1)

4.13.6 Sorted Map Builders🔗ℹ

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

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

A predicate for sorted map builders.

procedure
(make-sorted-map-builder key-comparator) → sorted-map-builder?
key-comparator : comparator?

Creates a new sorted map builder that builds maps sorted by key-comparator.

procedure
(sorted-map-builder-put builder key value) → sorted-map-builder?
  builder : sorted-map-builder?
  key : any/c
  value : any/c

Adds an entry mapping key to value in the built map, 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 keys are not allowed, and will cause build-sorted-map to fail.

Examples:

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

> (sorted-map-builder-put builder 7 'c)
#<sorted-map-builder>
> (sorted-map-builder-put builder 2 'a)
#<sorted-map-builder>
> (sorted-map-builder-put builder 5 'b)
#<sorted-map-builder>
> (build-sorted-map builder)
(immutable-sorted-map 2 'a 5 'b 7 'c)

procedure
(sorted-map-builder-put-all builder
entries) → sorted-map-builder?
builder : sorted-map-builder?
entries : (sequence/c entry?)

Adds entries 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 keys are not allowed, and will cause build-sorted-map to fail.

Examples:

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

> (sorted-map-builder-put-all builder (list (entry 1 'a) (entry 3 'c) (entry 2 'b)))
#<sorted-map-builder>
> (build-sorted-map builder)
(immutable-sorted-map 1 'a 2 'b 3 'c)

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

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

Examples:

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

> (for/fold ([builder (make-sorted-map-builder natural<=>)]
             #:result (build-sorted-map builder))
            ([char (in-string "hello")]
             [i (in-naturals)])
    (sorted-map-builder-put builder i char))
(immutable-sorted-map 0 #\h 1 #\e 2 #\l 3 #\l 4 #\o)

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.13.1	Constructing Sorted Maps
4.13.2	Iterating Sorted Maps
4.13.3	Querying Sorted Maps
4.13.4	Sorted Map Views
4.13.5	Modifying Sorted Maps
4.13.6	Sorted Map Builders