1.11 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.11.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 (inclusive-bound 3) (exclusive-bound 7) #<comparator:real<=>>)
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 (inclusive-bound 3) #<unbounded> #<comparator:real<=>>)
> (range unbounded (exclusive-bound 7)) (range #<unbounded> (exclusive-bound 7) #<comparator:real<=>>)
> (range unbounded unbounded) (range #<unbounded> #<unbounded> #<comparator: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"
(strict-cond
((unbounded? lower-bound) #t)
((unbounded? upper-bound) #t)
(else
(define lower
(range-bound-endpoint lower-bound))
(define upper
(range-bound-endpoint upper-bound))
(not (equal? ... greater))))
#: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/private/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/private/range.rkt:18.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 (inclusive-bound 5) (inclusive-bound 5) #<comparator:real<=>>)
> (range (inclusive-bound 18) (exclusive-bound 18)) (range (inclusive-bound 18) (exclusive-bound 18) #<comparator:real<=>>)
> (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"
(strict-cond
((unbounded? lower-bound) #t)
((unbounded? upper-bound) #t)
(else
(define lower
(range-bound-endpoint lower-bound))
(define upper
(range-bound-endpoint upper-bound))
(not (equal? ... greater))))
#: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/private/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/private/range.rkt:18.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 #<unbounded> (exclusive-bound 14)
#<comparator:real<=>>)
in: the 1st argument of
(-> bounded-below-range? any/c)
contract from:
<pkgs>/rebellion/private/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/private/range.rkt:144.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 (inclusive-bound 1) #<unbounded>
#<comparator:real<=>>)
in: the 1st argument of
(-> bounded-above-range? any/c)
contract from:
<pkgs>/rebellion/private/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/private/range.rkt:145.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.11.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)) #t
> (nonempty-range? (open-closed-range 3 3)) #t
1.11.1.2 Range Bounds
procedure
(range-bound? v) → boolean?
v : any/c
procedure
(range-bound endpoint type) → range-bound?
endpoint : any/c type : range-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) → range-bound-type?
bound : range-bound?
> (range-bound-type (inclusive-bound 5)) #<range-bound-type:inclusive>
> (range-bound-type (exclusive-bound "banana")) #<range-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) #<range-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) #<range-bound-type:exclusive>
procedure
(range-bound-type? v) → boolean?
v : any/c
value
value
procedure
(unbounded? v) → boolean?
v : any/c
value
1.11.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 (inclusive-bound 14) #<unbounded> #<comparator:real<=>>)
> (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 #<unbounded> (inclusive-bound 14) #<comparator:real<=>>)
> (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 (exclusive-bound 14) #<unbounded> #<comparator:real<=>>)
> (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 #<unbounded> (exclusive-bound 14) #<comparator:real<=>>)
> (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 (inclusive-bound 42) (inclusive-bound 42) #<comparator:real<=>>)
> (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 #<unbounded> #<unbounded> #<comparator: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 (inclusive-bound 5) #<unbounded> #<comparator:real<=>>)
> (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 #<unbounded> (exclusive-bound 5) #<comparator:real<=>>)
> (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.11.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
range: (range (exclusive-bound 2) #<unbounded>
#<comparator:real<=>>)
other-range: (range (exclusive-bound "apple")
#<unbounded> #<comparator:string<=>>)
in: (->i
((range range?) (other-range range?))
#:pre/name
(range other-range)
"both ranges must use the same comparator"
(equal?
(range-comparator range)
(range-comparator other-range))
(_ boolean?))
contract from:
<pkgs>/rebellion/private/range.rkt
blaming: top-level
(assuming the contract is correct)
at: <pkgs>/rebellion/private/range.rkt:112.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
1.11.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 (inclusive-bound 2) (exclusive-bound 9) #<comparator:real<=>>)
> (range-span (less-than-range 4) (singleton-range 6)) (range #<unbounded> (inclusive-bound 6) #<comparator:real<=>>)
> (range-span (open-range 2 8) (at-most-range 5)) (range #<unbounded> (exclusive-bound 8) #<comparator:real<=>>)