►Rebellion
▼4 Collections
►4.14 Range Sets
On this page:
range-set?
range-set
empty-range-set?
empty-range-set
nonempty-range-set?
4.14.1 Querying Range Sets
range-set-size
range-set-comparator
range-set-contains?
range-set-encloses?
range-set-encloses-all?
range-subset
4.14.2 Range Set Iterations and Comprehensions
in-range-set
into-range-set
sequence->range-set
for/  range-set
for*/  range-set
8.6
  top  contents  ← prev  up  next → 

4.14 Range Sets

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

A range set is a sorted set of nonempty, disconnected ranges. All ranges in the same range set must use the same comparator. Range sets are sequences, and when used as a sequence the set’s ranges are iterated in ascending order.

procedure

(range-set? v) → boolean?

  v : any/c
A predicate for range sets.

procedure

(range-set range    
  ...    
  #:comparator comparator) → range-set?
  range : nonempty-range?
  comparator : comparator?
(range-set first-range    
  range ...    
  [#:comparator comparator]) → range-set?
  first-range : nonempty-range?
  range : nonempty-range?
  comparator : comparator? = (range-comparator first-range)
Constructs a 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))

(range-set

 (range (inclusive-bound 2) (exclusive-bound 5) #<comparator:real<=>>))

> (range-set (closed-open-range 4 8) (closed-open-range 0 4))

(range-set

 (range (inclusive-bound 0) (exclusive-bound 8) #<comparator:real<=>>))

> (range-set (greater-than-range 20) (less-than-range 5) (closed-range 10 15))

(range-set

 (range #<unbounded> (exclusive-bound 5) #<comparator:real<=>>)

 (range (inclusive-bound 10) (inclusive-bound 15) #<comparator:real<=>>)

 (range (exclusive-bound 20) #<unbounded> #<comparator:real<=>>))

> (range-set (closed-open-range 2 5) #:comparator real<=>)

(range-set

 (range (inclusive-bound 2) (exclusive-bound 5) #<comparator:real<=>>))

procedure

(empty-range-set? v) → boolean?

  v : any/c
A predicate for empty range sets. Implies range-set?.

value

empty-range-set : empty-range-set?

The empty range set, which contains no ranges.

procedure

(nonempty-range-set? v) → boolean?

  v : any/c
A predicate for nonempty range sets. Implies range-set?.

4.14.1 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-contains? ranges value) → boolean?

  ranges : range-set?
  value : any/c
Determines if any range in ranges contains value.

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-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.

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-subset range-set subset-range) → range-set?

  range-set : range-set?
  subset-range : range?
Returns a range set containing the ranges in range-set 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))

(range-set

 (range (inclusive-bound 2) (exclusive-bound 4) #<comparator:real<=>>))

4.14.2 Range Set Iterations and Comprehensions

procedure

(in-range-set range-set) → (sequence/c nonempty-range?)

  range-set : range-set?
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.

procedure

(into-range-set comparator)

 → (reducer/c nonempty-range? 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<=>))

(range-set

 (range (inclusive-bound 1) (inclusive-bound 3) #<comparator:real<=>>)

 (range (inclusive-bound 5) (inclusive-bound 6) #<comparator:real<=>>)

 (range (inclusive-bound 10) (inclusive-bound 12) #<comparator:real<=>>))

procedure

(sequence->range-set ranges    
  #:comparator comparator) → range-set?
  ranges : (sequence/c nonempty-range?)
  comparator : comparator?
Constructs a 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<=>)

(range-set

 (range (inclusive-bound 1) (inclusive-bound 3) #<comparator:real<=>>)

 (range (inclusive-bound 5) (inclusive-bound 6) #<comparator:real<=>>)

 (range (inclusive-bound 10) (inclusive-bound 12) #<comparator:real<=>>))

syntax

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

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

Example:
> (for/range-set #:comparator real<=> ([char (in-string "abcxyz")])
    (define codepoint (char->integer char))
    (closed-open-range codepoint (add1 codepoint)))

(range-set

 (range (inclusive-bound 97) (exclusive-bound 100) #<comparator:real<=>>)

 (range (inclusive-bound 120) (exclusive-bound 123) #<comparator:real<=>>))

syntax

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

Like for*, but collects the iterated ranges into a 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)))

(range-set

 (range (inclusive-bound 97) (exclusive-bound 100) #<comparator:real<=>>)

 (range (inclusive-bound 113) (exclusive-bound 119) #<comparator:real<=>>)

 (range (inclusive-bound 120) (exclusive-bound 123) #<comparator:real<=>>))

  top  contents  ← prev  up  next →