►Rebellion
▼4 Collections
►4.14 Range Sets
On this page:
range-set?
immutable-range-set?
mutable-range-set?
4.14.1 Constructing Range Sets
range-set
sequence->range-set
for/  range-set
for*/  range-set
into-range-set
4.14.2 Iterating Range Sets
in-range-set
4.14.3 Querying Range Sets
range-set-size
range-set-comparator
range-set-empty?
range-set-contains?
range-set-contains-all?
range-set-encloses?
range-set-encloses-all?
range-set-intersects?
range-set-range-containing
range-set-range-containing-or-absent
range-set-span
range-set-span-or-absent
4.14.4 Range Set Views
range-subset
4.14.5 Modifying Range Sets
range-set-add
range-set-add!
range-set-add-all
range-set-add-all!
range-set-remove
range-set-remove!
range-set-remove-all
range-set-remove-all!
range-set-clear!
8.12
  top  contents    up   

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

(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-intersects? ranges other-range) → boolean?

  ranges : range-set?
  other-range : range?
Determines if any range in ranges intersects with other-range.

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

 

> (range-set-intersects? ranges (closed-range 4 8))

#t

> (range-set-intersects? 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)>)

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?

procedure

(range-set-add-all ranges new-ranges) → immutable-range-set?

  ranges : immutable-range-set?
  new-ranges : (sequence/c range?)

procedure

(range-set-add-all! ranges new-ranges) → void?

  ranges : mutable-range-set?
  new-ranges : (sequence/c range?)

procedure

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

  ranges : immutable-range-set?
  range-to-remove : range?

procedure

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

  ranges : mutable-range-set?
  range-to-remove : range?

procedure

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

procedure

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

procedure

(range-set-clear! ranges) → void?

  ranges : mutable-range-set?
  top  contents    up