1.12 Ranges
(require rebellion/base/range) | package: rebellion |
A range, also called an interval, is a continuous set of ordered values. Ranges have at most two bounds: an upper bound and a lower bound. Either bound may be absent, in which case the range is unbounded. If a bound is present, it contains an endpoint value and an indication of whether the bound is inclusive or exclusive.
1.12.1 Range Data Model
procedure
(range lower-bound upper-bound [ #:comparator comparator]) → range? lower-bound : (or/c range-bound? unbounded?) upper-bound : (or/c range-bound? unbounded?) comparator : comparator? = real<=>
> (range (inclusive-bound 3) (exclusive-bound 7)) #<range:real<=> [3, 7)>
Either lower-bound or upper-bound may be the special unbounded constant, indicating that the range is unbounded on that end. A range may be unbounded on both ends, in which case the range encompasses all possible values (as long as they would be accepted by comparator).
> (range (inclusive-bound 3) unbounded) #<range:real<=> [3, ∞]>
> (range unbounded (exclusive-bound 7)) #<range:real<=> [-∞, 7)>
> (range unbounded unbounded) #<range:real<=> [-∞, ∞]>
If the range is not unbounded, then lower-bound must not be greater than upper-bound when compared with comparator.
> (range (inclusive-bound 42) (exclusive-bound 17)) range: contract violation;
lower endpoint must be less than or equal to upper endpoint
lower-bound: (inclusive-bound 42)
upper-bound: (exclusive-bound 17)
cmp: #<unsupplied-arg>
in: (->i
((lower-bound
(or/c range-bound? unbounded?))
(upper-bound
(or/c range-bound? unbounded?)))
(#:comparator (cmp comparator?))
#:pre/name
(lower-bound upper-bound cmp)
"lower endpoint must be less than or equal to upper
endpoint"
(guarded-block
(guard
(not (unbounded? lower-bound))
#:else
#t)
(guard
(not (unbounded? upper-bound))
#:else
#t)
(define lower
(range-bound-endpoint lower-bound))
...)
#:pre/name
(lower-bound upper-bound)
"equal endpoints cannot both be exclusive"
(not
(and (exclusive-bound? lower-bound)
(exclusive-bound? upper-bound)
(equal?
(exclusive-bound-endpoint
lower-bound)
(exclusive-bound-endpoint
upper-bound))))
(_ range?))
contract from:
<pkgs>/rebellion/base/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/base/range.rkt:20:3
However, lower-bound may be equal to upper-bound, as long as at least one of the two bounds is inclusive. If both bounds are equal and inclusive, this constructs a singleton range which contains only one value. If one of the bounds is exclusive, the constructed range is an empty range that contains no values. If both bounds are exclusive, a contract violation is raised.
> (range (inclusive-bound 5) (inclusive-bound 5)) #<range:real<=> [5, 5]>
> (range (inclusive-bound 18) (exclusive-bound 18)) #<range:real<=> [18, 18)>
> (range (exclusive-bound 42) (exclusive-bound 42)) range: contract violation;
equal endpoints cannot both be exclusive
lower-bound: (exclusive-bound 42)
upper-bound: (exclusive-bound 42)
in: (->i
((lower-bound
(or/c range-bound? unbounded?))
(upper-bound
(or/c range-bound? unbounded?)))
(#:comparator (cmp comparator?))
#:pre/name
(lower-bound upper-bound cmp)
"lower endpoint must be less than or equal to upper
endpoint"
(guarded-block
(guard
(not (unbounded? lower-bound))
#:else
#t)
(guard
(not (unbounded? upper-bound))
#:else
#t)
(define lower
(range-bound-endpoint lower-bound))
...)
#:pre/name
(lower-bound upper-bound)
"equal endpoints cannot both be exclusive"
(not
(and (exclusive-bound? lower-bound)
(exclusive-bound? upper-bound)
(equal?
(exclusive-bound-endpoint
lower-bound)
(exclusive-bound-endpoint
upper-bound))))
(_ range?))
contract from:
<pkgs>/rebellion/base/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/base/range.rkt:20:3
procedure
(range-lower-bound rng) → (or/c range-bound? unbounded?)
rng : range?
> (range-lower-bound (closed-range 3 7)) (inclusive-bound 3)
> (range-lower-bound (open-closed-range 3 7)) (exclusive-bound 3)
> (range-lower-bound (at-least-range 5)) (inclusive-bound 5)
> (range-lower-bound (less-than-range 14)) #<unbounded>
procedure
(range-lower-endpoint rng) → any/c
rng : bounded-below-range?
> (range-lower-endpoint (closed-range 3 7)) 3
> (range-lower-endpoint (at-least-range 5)) 5
> (range-lower-endpoint (less-than-range 14)) range-lower-endpoint: contract violation
expected: bounded-below-range?
given: #<range:real<=> [-∞, 14)>
in: the 1st argument of
(-> bounded-below-range? any/c)
contract from:
<pkgs>/rebellion/base/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/base/range.rkt:122:3
procedure
(range-upper-bound rng) → (or/c range-bound? unbounded?)
rng : range?
> (range-upper-bound (closed-range 3 7)) (inclusive-bound 7)
> (range-upper-bound (open-closed-range 3 7)) (inclusive-bound 7)
> (range-upper-bound (at-least-range 5)) #<unbounded>
> (range-upper-bound (less-than-range 14)) (exclusive-bound 14)
procedure
(range-upper-endpoint rng) → any/c
rng : bounded-above-range?
> (range-upper-endpoint (closed-range 3 7)) 7
> (range-upper-endpoint (less-than-range 8)) 8
> (range-upper-endpoint (at-least-range 1)) range-upper-endpoint: contract violation
expected: bounded-above-range?
given: #<range:real<=> [1, ∞]>
in: the 1st argument of
(-> bounded-above-range? any/c)
contract from:
<pkgs>/rebellion/base/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/base/range.rkt:123:3
procedure
(range-comparator rng) → comparator?
rng : range?
> (range-comparator (closed-range 3 7)) #<comparator:real<=>>
> (range-comparator (open-range "apple" "orange" #:comparator string<=>)) #<comparator:string<=>>
1.12.1.1 Types of Ranges
procedure
(bounded-range? v) → boolean?
v : any/c
> (bounded-range? (closed-range 2 7)) #t
> (bounded-range? (open-range 3 5)) #t
> (bounded-range? (less-than-range 6)) #f
procedure
(bounded-above-range? v) → boolean?
v : any/c
> (bounded-above-range? (closed-range 2 7)) #t
> (bounded-above-range? (greater-than-range 3)) #f
> (bounded-above-range? (less-than-range 6)) #t
procedure
(bounded-below-range? v) → boolean?
v : any/c
> (bounded-below-range? (closed-range 2 7)) #t
> (bounded-below-range? (greater-than-range 3)) #t
> (bounded-below-range? (less-than-range 6)) #f
procedure
(unbounded-range? v) → boolean?
v : any/c
> (unbounded-range? (closed-range 2 7)) #f
> (unbounded-range? (greater-than-range 3)) #t
> (unbounded-range? (less-than-range 6)) #t
procedure
v : any/c
> (unbounded-above-range? (closed-range 2 7)) #f
> (unbounded-above-range? (greater-than-range 3)) #t
> (unbounded-above-range? (less-than-range 6)) #f
procedure
v : any/c
> (unbounded-below-range? (closed-range 2 7)) #f
> (unbounded-below-range? (greater-than-range 3)) #f
> (unbounded-below-range? (less-than-range 6)) #t
procedure
(singleton-range? v) → boolean?
v : any/c
> (singleton-range? (singleton-range 3)) #t
> (singleton-range? (closed-range 3 3)) #t
> (singleton-range? (closed-open-range 3 3)) #f
procedure
(empty-range? v) → boolean?
v : any/c
> (empty-range? (closed-range 3 3)) #f
> (empty-range? (closed-open-range 3 3)) #t
> (empty-range? (open-closed-range 3 3)) #t
procedure
(nonempty-range? v) → boolean?
v : any/c
> (nonempty-range? (closed-range 3 3)) #t
> (nonempty-range? (closed-open-range 3 3)) #f
> (nonempty-range? (open-closed-range 3 3)) #f
1.12.1.2 Range Bounds
procedure
(range-bound? v) → boolean?
v : any/c
procedure
(range-bound endpoint type) → range-bound?
endpoint : any/c type : bound-type?
> (range-bound 5 inclusive) (inclusive-bound 5)
> (range-bound "banana" exclusive) (exclusive-bound "banana")
procedure
(range-bound-endpoint bound) → any/c
bound : range-bound?
> (range-bound-endpoint (inclusive-bound 5)) 5
> (range-bound-endpoint (exclusive-bound "banana")) "banana"
procedure
(range-bound-type bound) → bound-type?
bound : range-bound?
> (range-bound-type (inclusive-bound 5)) #<bound-type:inclusive>
> (range-bound-type (exclusive-bound "banana")) #<bound-type:exclusive>
procedure
(inclusive-bound endpoint) → range-bound?
endpoint : any/c
> (define bound (inclusive-bound 5)) > (range-bound-endpoint bound) 5
> (range-bound-type bound) #<bound-type:inclusive>
procedure
(exclusive-bound endpoint) → range-bound?
endpoint : any/c
> (define bound (exclusive-bound "banana")) > (range-bound-endpoint bound) "banana"
> (range-bound-type bound) #<bound-type:exclusive>
procedure
(bound-type? v) → boolean?
v : any/c
value
value
procedure
(unbounded? v) → boolean?
v : any/c
value
1.12.2 Range Constructors
procedure
(closed-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range? lower-endpoint : any/c upper-endpoint : any/c comparator : comparator? = real<=>
procedure
(open-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range? lower-endpoint : any/c upper-endpoint : any/c comparator : comparator? = real<=>
procedure
(closed-open-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range? lower-endpoint : any/c upper-endpoint : any/c comparator : comparator? = real<=>
procedure
(open-closed-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range? lower-endpoint : any/c upper-endpoint : any/c comparator : comparator? = real<=>
procedure
(at-least-range lower-endpoint [ #:comparator comparator]) → (and/c unbounded-above-range? bounded-below-range?) lower-endpoint : any/c comparator : comparator? = real<=>
> (at-least-range 14) #<range:real<=> [14, ∞]>
> (range-contains? (at-least-range 14) 5) #f
> (range-contains? (at-least-range 14) 14) #t
> (range-contains? (at-least-range 14) 87) #t
procedure
(at-most-range upper-endpoint [ #:comparator comparator]) → (and/c unbounded-below-range? bounded-above-range?) upper-endpoint : any/c comparator : comparator? = real<=>
> (at-most-range 14) #<range:real<=> [-∞, 14]>
> (range-contains? (at-most-range 14) 5) #t
> (range-contains? (at-most-range 14) 14) #t
> (range-contains? (at-most-range 14) 87) #f
procedure
(greater-than-range lower-endpoint [ #:comparator comparator]) → (and/c unbounded-above-range? bounded-below-range?) lower-endpoint : any/c comparator : comparator? = real<=>
> (greater-than-range 14) #<range:real<=> (14, ∞]>
> (range-contains? (greater-than-range 14) 5) #f
> (range-contains? (greater-than-range 14) 14) #f
> (range-contains? (greater-than-range 14) 87) #t
procedure
(less-than-range upper-endpoint [ #:comparator comparator]) → (and/c unbounded-below-range? bounded-above-range?) upper-endpoint : any/c comparator : comparator? = real<=>
> (less-than-range 14) #<range:real<=> [-∞, 14)>
> (range-contains? (less-than-range 14) 5) #t
> (range-contains? (less-than-range 14) 14) #f
> (range-contains? (less-than-range 14) 87) #f
procedure
(singleton-range endpoint [ #:comparator comparator]) → singleton-range? endpoint : any/c comparator : comparator? = real<=>
> (singleton-range 42) #<range:real<=> [42, 42]>
> (range-contains? (singleton-range 42) 42) #t
> (range-contains? (singleton-range 42) 41) #f
> (range-contains? (singleton-range 42) 43) #f
procedure
(unbounded-range [#:comparator comparator]) → unbounded-range?
comparator : comparator? = real<=>
> (unbounded-range #:comparator string<=>) #<range:string<=> [-∞, ∞]>
> (range-contains? (unbounded-range #:comparator string<=>) "apple") #t
> (range-contains? (unbounded-range #:comparator string<=>) "zebra") #t
procedure
(unbounded-above-range lower-bound [ #:comparator comparator]) → unbounded-above-range? lower-bound : range-bound? comparator : comparator? = real<=>
> (unbounded-above-range (inclusive-bound 5)) #<range:real<=> [5, ∞]>
> (range-contains? (unbounded-above-range (inclusive-bound 5)) 3) #f
> (range-contains? (unbounded-above-range (inclusive-bound 5)) 5) #t
> (range-contains? (unbounded-above-range (inclusive-bound 5)) 8) #t
procedure
(unbounded-below-range lower-bound [ #:comparator comparator]) → unbounded-below-range? lower-bound : range-bound? comparator : comparator? = real<=>
> (unbounded-below-range (exclusive-bound 5)) #<range:real<=> [-∞, 5)>
> (range-contains? (unbounded-below-range (exclusive-bound 5)) 3) #t
> (range-contains? (unbounded-below-range (exclusive-bound 5)) 5) #f
> (range-contains? (unbounded-below-range (exclusive-bound 5)) 8) #f
1.12.3 Querying Ranges
procedure
(range-contains? range v) → boolean?
range : range? v : any/c
> (range-contains? (closed-range 3 7) 5) #t
> (range-contains? (closed-range 3 7) 7) #t
> (range-contains? (closed-range 3 7) 10) #f
> (range-contains? (greater-than-range "apple" #:comparator string<=>) "banana") #t
> (range-contains? (greater-than-range "apple" #:comparator string<=>) "aardvark") #f
procedure
(range-encloses? range other-range) → boolean?
range : range? other-range : range?
> (range-encloses? (open-range 2 8) (closed-range 4 6)) #t
> (range-encloses? (open-range 2 8) (closed-range 2 6)) #f
> (range-encloses? (open-range 2 8) (at-least-range 5)) #f
> (range-encloses? (greater-than-range 2) (at-least-range 5)) #t
> (range-encloses? (greater-than-range 2) (greater-than-range "apple" #:comparator string<=>)) range-encloses?: contract violation;
both ranges must use the same comparator
range1: #<range:real<=> (2, ∞]>
range2: #<range:string<=> ("apple", ∞]>
in: (->i
((range1 range?) (range2 range?))
#:pre/name
(range1 range2)
"both ranges must use the same comparator"
(equal?
(range-comparator range1)
(range-comparator range2))
(_ boolean?))
contract from:
<pkgs>/rebellion/base/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/base/range.rkt:114:3
procedure
(range-connected? range1 range2) → boolean?
range1 : range? range2 : range?
> (range-connected? (closed-range 2 7) (open-range 3 8)) #t
> (range-connected? (closed-range 2 5) (open-range 5 8)) #t
> (range-connected? (open-range 2 5) (open-range 5 8)) #f
procedure
(range-overlaps? range1 range2) → boolean?
range1 : range? range2 : range?
> (range-overlaps? (closed-range 2 7) (open-range 3 8)) #t
> (range-overlaps? (closed-range 2 5) (closed-range 5 8)) #t
> (range-overlaps? (closed-range 2 5) (open-range 5 8)) #f
value
Ranges only compare equivalent if they’re equal. That is, the range<=> comparator is consistent with equality. Note that this means that some ranges are not equivalent even though they contain the same set of values. Specifically, any two empty ranges with always contain the same set of values (the empty set) but the ranges only compare equivalent if they have the same endpoints. This is only possible with empty ranges; two nonempty ranges that contain the same set of values are always equal and thus always compare equivalent.
> (compare range<=> (singleton-range 4) (singleton-range 8)) #<lesser>
> (compare range<=> (closed-range 0 5) (closed-range 3 10)) #<lesser>
> (compare range<=> (closed-range 0 5) (closed-range 0 3)) #<greater>
> (compare range<=> (closed-range 0 5) (closed-range 2 5)) #<lesser>
1.12.4 Operations on Ranges
procedure
(range-span range1 range2) → range?
range1 : range? range2 : range?
> (range-span (closed-range 2 5) (open-range 8 9)) #<range:real<=> [2, 9)>
> (range-span (less-than-range 4) (singleton-range 6)) #<range:real<=> [-∞, 6]>
> (range-span (open-range 2 8) (at-most-range 5)) #<range:real<=> [-∞, 8)>
> (range-gap (closed-range 2 5) (closed-range 8 9)) #<range:real<=> (5, 8)>
> (range-gap (less-than-range 4) (singleton-range 6)) #<range:real<=> [4, 6)>
> (range-gap (open-range 2 8) (closed-range 8 10)) #<range:real<=> [8, 8)>
> (range-gap (closed-range 2 8) (closed-range 8 10)) range-gap: expected non-overlapping ranges
range1: #<range:real<=> [2, 8]>
range2: #<range:real<=> [8, 10]>
procedure
(range-intersection range1 range2) → range?
range1 : range? range2 : range?
> (range-intersection (closed-range 2 8) (open-range 4 16)) #<range:real<=> (4, 8]>
> (range-intersection (greater-than-range 4) (less-than-range 6)) #<range:real<=> (4, 6)>
> (range-intersection (open-range 2 8) (at-most-range 5)) #<range:real<=> (2, 5]>
> (range-intersection (less-than-range 4) (singleton-range 4)) #<range:real<=> [4, 4)>