4.14 Range Sets

8.16.0.2

4.14 Range Sets🔗ℹ

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

A range set is a sorted collection of nonempty, disconnected ranges. All ranges in the same range set must use the same comparator. Two immutable range sets are equal? if they contain the same ranges. Two mutable range sets are equal? if they will always contain the same ranges, meaning that they share the same mutable state. This is not necessarily the same as being eq?, as some range sets may be views of others.

All range sets are sequences. When iterated, a range set traverses its ranges in ascending order as defined by the comparator shared by those ranges. To traverse a range set in descending order, use in-range-set with #:descending? set to true.

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

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

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

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

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

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

4.14.1 Constructing Range Sets🔗ℹ

procedure
(range-set range
...
#:comparator comparator) → immutable-range-set?
  range : nonempty-range?
  comparator : comparator?
(range-set first-range
range ...
[ #:comparator comparator]) → immutable-range-set?
  first-range : nonempty-range?
  range : nonempty-range?
  comparator : comparator? = (range-comparator first-range)

Constructs an immutable range set containing the given ranges. If at least one range is provided, comparator may be omitted and defaults to the comparator of the first range. Overlapping ranges are disallowed, but adjacent ranges are accepted and are merged together. All ranges must use comparator as their endpoint comparators or a contract exception is raised.

Examples:

> (range-set (closed-open-range 2 5))
(immutable-range-set #<range:real<=> [2, 5)>)
> (range-set (closed-open-range 4 8) (closed-open-range 0 4))
(immutable-range-set #<range:real<=> [0, 8)>)
> (range-set (greater-than-range 20) (less-than-range 5) (closed-range 10 15))
(immutable-range-set
  #<range:real<=> [-∞, 5)>
  #<range:real<=> [10, 15]>
  #<range:real<=> (20, ∞]>)
> (range-set (closed-open-range 2 5) #:comparator real<=>)
(immutable-range-set #<range:real<=> [2, 5)>)

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

Constructs a new mutable range set containing initial-ranges (which defaults to the empty list). All ranges must use comparator as their endpoint comparators or a contract exception is raised. As in the range-set constructor, overlapping ranges are disallowed.

Examples:

> (make-mutable-range-set #:comparator real<=>)
(mutable-range-set
> (make-mutable-range-set (list (closed-range 2 5) (open-range 10 20))
#:comparator real<=>)
(mutable-range-set #<range:real<=> [2, 5]> #<range:real<=> (10, 20)>)

procedure
(sequence->range-set ranges
#:comparator comparator)
→ immutable-range-set?
ranges : (sequence/c nonempty-range?)
comparator : comparator?

Constructs an immutable range set from the given ranges (which must use comparator.) As in the range-set consturctor, overlapping ranges are disallowed.

Example:

> (sequence->range-set
   (list (closed-range 1 3) (closed-range 10 12) (closed-range 5 6))
   #:comparator real<=>)
(immutable-range-set
  #<range:real<=> [1, 3]>
  #<range:real<=> [5, 6]>
  #<range:real<=> [10, 12]>)

syntax
(for/range-set #:comparator comparator (for-clause ...)
body-or-break ...
body)

Like for, but collects the iterated ranges into an immutable range set.

Example:

> (for/range-set #:comparator real<=> ([char (in-string "abcxyz")])
(define codepoint (char->integer char))
(closed-open-range codepoint (add1 codepoint)))
(immutable-range-set #<range:real<=> [97, 100)> #<range:real<=> [120, 123)>)

syntax
(for*/range-set #:comparator comparator (for-clause ...)
body-or-break ...
body)

Like for*, but collects the iterated ranges into an immutable range set.

Example:

> (for*/range-set #:comparator real<=>
    ([str (in-list (list "abc" "tuv" "xyz" "qrs"))]
     [char (in-string str)])
    (define codepoint (char->integer char))
    (closed-open-range codepoint (add1 codepoint)))
(immutable-range-set
  #<range:real<=> [97, 100)>
  #<range:real<=> [113, 119)>
  #<range:real<=> [120, 123)>)

procedure
(into-range-set comparator)
→ (reducer/c nonempty-range? immutable-range-set?)
comparator : comparator?

Constructs a reducer that reduces a sequence of nonempty ranges (which must use comparator) into a range set. As in the range-set constructor, overlapping ranges are disallowed.

Example:

> (transduce (list (closed-range 1 3) (closed-range 10 12) (closed-range 5 6))
             #:into (into-range-set real<=>))
(immutable-range-set
  #<range:real<=> [1, 3]>
  #<range:real<=> [5, 6]>
  #<range:real<=> [10, 12]>)

4.14.2 Iterating Range Sets🔗ℹ

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

Returns a sequence iterating through the ranges in range-set in ascending order. Note that range sets are already sequences, but this form may yield better performance when used directly within a for clause.

Examples:

(define ranges (range-set (closed-range 1 3) (closed-range 10 12) (closed-range 5 6)))

> (for ([r (in-range-set ranges)])
(displayln r))
#<range:real<=> [1, 3]>
#<range:real<=> [5, 6]>
#<range:real<=> [10, 12]>
> (for ([r (in-range-set ranges #:descending? #true)])
(displayln r))
#<range:real<=> [10, 12]>
#<range:real<=> [5, 6]>
#<range:real<=> [1, 3]>

4.14.3 Querying Range Sets🔗ℹ

procedure
(range-set-size ranges) → natural?
ranges : range-set?

Returns the number of ranges in ranges

Example:

> (range-set-size (range-set (closed-range 3 5) (closed-range 8 14)))
2

procedure
(range-set-comparator ranges) → comparator?
ranges : range-set?

Returns the comparator that ranges uses to compare elements to its contained ranges.

procedure
(range-set-empty? ranges) → boolean?
ranges : range-set?

Returns true if ranges is empty, returns false otherwise.

procedure
(range-set-contains? ranges element) → boolean?
ranges : range-set?
element : any/c

Determines if any range in ranges contains element.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-contains? ranges 2)
#t
> (range-set-contains? ranges 7)
#f
> (range-set-contains? ranges 10)
#t

procedure
(range-set-contains-all? ranges elements) → boolean?
ranges : range-set?
elements : (sequence/c any/c)

Determines if ranges contains every value in vs. If elements is empty, returns true.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-contains-all? ranges (list 2 3 4 5 9 10))
#t
> (range-set-contains-all? ranges (list 4 7))
#f
> (range-set-contains-all? ranges (list))
#t

procedure
(range-set-encloses? ranges other-range) → boolean?
ranges : range-set?
other-range : range?

Determines if any range in ranges encloses other-range.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-encloses? ranges (closed-range 3 4))
#t
> (range-set-encloses? ranges (closed-range 4 10))
#f
> (range-set-encloses? ranges (open-range 9 10))
#t

procedure
(range-set-encloses-all? ranges
other-ranges) → boolean?
ranges : range-set?
other-ranges : (sequence/c range?)

Determines if ranges encloses every range in other-ranges. If other-ranges is empty, returns true.

Example:

> (range-set-encloses-all? (range-set (closed-range 2 5) (closed-range 7 10))
(range-set (closed-range 3 4) (closed-range 8 9)))
#t

procedure
(range-set-overlaps? ranges other-range) → boolean?
ranges : range-set?
other-range : range?

Determines if any range in ranges overlaps with other-range.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-overlaps? ranges (closed-range 4 8))
#t
> (range-set-overlaps? ranges (closed-range 6 8))
#f

procedure
(range-set-range-containing ranges
element
[ failure-result]) → any/c
  ranges : range-set?
  element : any/c
  failure-result : failure-result/c = (λ () (raise ...))

Returns the range in ranges that contains element. If no range contains element, 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 ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-range-containing ranges 4)
#<range:real<=> [2, 5]>
> (range-set-range-containing ranges 9)
#<range:real<=> [9, 10]>
> (range-set-range-containing ranges 7)
range-set-range-containing: no range containing value;
ranges: (immutable-range-set #<range:real<=> [2, 5]>
#<range:real<=> [9, 10]>) value: 7
> (range-set-range-containing ranges 7 #false)
#f

procedure
(range-set-range-containing-or-absent ranges
element)
→ (option/c range?)
ranges : range-set?
element : any/c

Returns the range in ranges that contains element, wrapped in a present option. If no range contains element, then absent is returned.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 9 10)))

> (range-set-range-containing-or-absent ranges 4)
(present #<range:real<=> [2, 5]>)
> (range-set-range-containing-or-absent ranges 9)
(present #<range:real<=> [9, 10]>)
> (range-set-range-containing-or-absent ranges 7)
#<absent>

procedure
(range-set-span ranges [empty-result]) → any/c
ranges : range-set?
empty-result : failure-result/c = (λ () (raise ...))

Returns the span of ranges, which is the smallest range that encloses every range in the set. If ranges is empty, then empty-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:

> (range-set-span (range-set (closed-range 2 5) (open-range 9 10)))
#<range:real<=> [2, 10)>
> (range-set-span (range-set #:comparator real<=>))
range-set-span: range set is empty and has no span
> (range-set-span (range-set #:comparator real<=>) "empty range set!")
"empty range set!"

procedure
(range-set-span-or-absent ranges) → (option/c range?)
ranges : range-set?

Returns the span of ranges, which is the smallest range that encloses every range in the set. The returned span is wrapped in a present option. If ranges is empty, then absent is returned.

Examples:

> (range-set-span-or-absent (range-set (closed-range 2 5) (open-range 9 10)))
(present #<range:real<=> [2, 10)>)
> (range-set-span-or-absent (range-set #:comparator real<=>))
#<absent>

4.14.4 Range Set Views🔗ℹ

procedure
(range-subset ranges subset-range) → range-set?
ranges : range-set?
subset-range : range?

Returns a range set containing the ranges in ranges that are enclosed by subset-range.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 7 10)))

> (range-subset ranges (less-than-range 4))
(immutable-range-set #<range:real<=> [2, 4)>)

procedure
(range-set-complement ranges) → range-set?
ranges : range-set?

Returns a range set that is the complement of ranges, meaning it contains exactly the ranges that are not contained by ranges. The returned set is a collection view of ranges. The returned set is immutable if ranges is immutable, and if ranges is mutable then the returned set is a write-through view. Adding a range to the returned complement set removes that range from the underlying set, and vice-versa for removing ranges from the complement set.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 7 10)))

> (range-set-complement ranges)
(immutable-range-set
  #<range:real<=> [-∞, 2)>
  #<range:real<=> (5, 7)>
  #<range:real<=> (10, ∞]>)

4.14.5 Modifying Range Sets🔗ℹ

procedure
(range-set-add ranges new-range) → immutable-range-set?
ranges : immutable-range-set?
new-range : range?

Functionally adds new-range to ranges by returning a new range set containing all of the ranges in ranges and new-range. Overlapping and adjacent ranges are coalesced. The input range set is not modified.

Examples:

(define ranges (range-set (closed-range 2 5) (closed-range 7 10)))

> (range-set-add ranges (closed-range 0 3))
(immutable-range-set #<range:real<=> [0, 5]> #<range:real<=> [7, 10]>)
> (range-set-add ranges (closed-range 6 12))
(immutable-range-set #<range:real<=> [2, 5]> #<range:real<=> [6, 12]>)
> (range-set-add ranges (closed-range 4 8))
(immutable-range-set #<range:real<=> [2, 10]>)

procedure
(range-set-add! ranges new-range) → void?
ranges : mutable-range-set?
new-range : range?

Adds new-range to ranges. Overlapping and adjacent ranges are coalesced.

Examples:

(define ranges (make-mutable-range-set #:comparator real<=>))
(range-set-add! ranges (closed-range 2 5))
(range-set-add! ranges (closed-range 7 10))

> ranges
(mutable-range-set #<range:real<=> [2, 5]> #<range:real<=> [7, 10]>)

(range-set-add! ranges (closed-range 4 8))

> ranges
(mutable-range-set #<range:real<=> [2, 10]>)

procedure
(range-set-add-all ranges new-ranges) → immutable-range-set?
ranges : immutable-range-set?
new-ranges : (sequence/c range?)

Functionally adds every range in new-ranges to ranges by returning a new range set containing all of the ranges in ranges and all of the ranges in new-ranges. Overlapping and adjacent ranges are coalesced. The input range set is not modified. This function is equivalent to looping over new-ranges with range-set-add.

Example:

> (range-set-add-all (range-set (closed-range 2 5) (open-range 10 12))
                     (range-set (open-range 3 8) (closed-range 15 20)))
(immutable-range-set
  #<range:real<=> [2, 8)>
  #<range:real<=> (10, 12)>
  #<range:real<=> [15, 20]>)

procedure
(range-set-add-all! ranges new-ranges) → void?
ranges : mutable-range-set?
new-ranges : (sequence/c range?)

Adds every range in new-ranges to ranges. Overlapping and adjacent ranges are coalesced. This function is equivalent to looping over new-ranges with range-set-add!.

Examples:

(define ranges (make-mutable-range-set #:comparator real<=>))

(range-set-add-all! ranges (list (closed-range 2 5) (open-range 10 12)))
(range-set-add-all! ranges (list (open-range 3 8) (closed-range 15 20)))

> ranges
(mutable-range-set
  #<range:real<=> [2, 8)>
  #<range:real<=> (10, 12)>
  #<range:real<=> [15, 20]>)

procedure
(range-set-remove ranges range-to-remove) → immutable-range-set?
ranges : immutable-range-set?
range-to-remove : range?

Functionally removes range-to-remove from ranges by returning a new range set containing all of the ranges in ranges except any ranges enclosed by range-to-remove. If a range only partially intersects range-to-remove, only the intersecting portion is removed in the returned range set. The input range set is not modified.

Example:

> (range-set-remove (range-set (closed-range 1 5) (closed-range 8 10))
(closed-range 3 12))
(immutable-range-set #<range:real<=> [1, 3)>)

procedure
(range-set-remove! ranges range-to-remove) → void?
ranges : mutable-range-set?
range-to-remove : range?

Removes range-to-remove from ranges by removing all of the ranges in ranges that are enclosed by range-to-remove. If a range only partially intersects range-to-remove, only the intersecting portion is removed from the range set.

Examples:

(define ranges (make-mutable-range-set #:comparator real<=>))
(range-set-add-all! ranges (list (closed-range 1 5) (closed-range 8 10)))

> ranges
(mutable-range-set #<range:real<=> [1, 5]> #<range:real<=> [8, 10]>)

(range-set-remove! ranges (closed-range 3 12))

> ranges
(mutable-range-set #<range:real<=> [1, 3)>)

procedure
(range-set-remove-all ranges
ranges-to-remove) → immutable-range-set?
ranges : immutable-range-set?
ranges-to-remove : (sequence/c range?)

Functionally removes every range in ranges-to-remove from ranges by returning a new range set containing all of the ranges in ranges except any ranges enclosed by a range in ranges-to-remove. If a range only partially intersects range-to-remove, only the intersecting portion is removed in the returned range set. The input range set is not modified. This function is equivalent to looping over ranges-to-remove with range-set-remove.

Example:

> (range-set-remove-all (range-set (closed-range 1 5) (closed-range 8 10))
(range-set (open-range 3 7) (closed-range 9 15)))
(immutable-range-set #<range:real<=> [1, 3]> #<range:real<=> [8, 9)>)

procedure
(range-set-remove-all! ranges
ranges-to-remove) → void?
ranges : mutable-range-set?
ranges-to-remove : (sequence/c range?)

Removes every range in ranges-to-remove from ranges by removing all of the ranges in ranges that are enclosed by any range in ranges-to-remove. If a range only partially intersects a range in ranges-to-remove, only the intersecting portion is removed from the range set. This function is equivalent to looping over ranges-to-remove with range-set-remove!.

Examples:

(define ranges (make-mutable-range-set #:comparator real<=>))
(range-set-add-all! ranges (list (closed-range 1 5) (closed-range 8 10)))

> ranges
(mutable-range-set #<range:real<=> [1, 5]> #<range:real<=> [8, 10]>)

(range-set-remove-all! ranges (list (open-range 3 7) (closed-range 9 15)))

> ranges
(mutable-range-set #<range:real<=> [1, 3]> #<range:real<=> [8, 9)>)

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

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.14.1	Constructing Range Sets
4.14.2	Iterating Range Sets
4.14.3	Querying Range Sets
4.14.4	Range Set Views
4.14.5	Modifying Range Sets