7.5

#### 1.11Ranges

 (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.1Range Data Model

 procedure(range? v) → boolean? v : any/c
A predicate for ranges.

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<=>
Constructs a range encompassing all values between lower-bound and upper-bound, when ordered according to comparator.

Example:
 > (range (inclusive-bound 3) (exclusive-bound 7)) (range (inclusive-bound 3) (exclusive-bound 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).

Examples:
 > (range (inclusive-bound 3) unbounded) (range (inclusive-bound 3) # #>) > (range unbounded (exclusive-bound 7)) (range # (exclusive-bound 7) #>) > (range unbounded unbounded) (range # # #>)

If the range is not unbounded, then lower-bound must not be greater than upper-bound when compared with comparator.

Example:
 > (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: # 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: /rebellion/private/range.rkt blaming: top-level (assuming the contract is correct) at: /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.

Examples:
 > (range (inclusive-bound 5) (inclusive-bound 5)) (range (inclusive-bound 5) (inclusive-bound 5) #>) > (range (inclusive-bound 18) (exclusive-bound 18)) (range (inclusive-bound 18) (exclusive-bound 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" (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: /rebellion/private/range.rkt blaming: top-level (assuming the contract is correct) at: /rebellion/private/range.rkt:18.3

 procedure rng : range?
Returns the lower bound of rng, or unbounded if rng is unbounded below.

Examples:
 > (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)) #

 procedure rng : bounded-below-range?
Returns the lower endpoint of rng, which must be bounded below.

Examples:
 > (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 # (exclusive-bound 14) #>) in: the 1st argument of (-> bounded-below-range? any/c) contract from: /rebellion/private/range.rkt blaming: top-level (assuming the contract is correct) at: /rebellion/private/range.rkt:144.3

 procedure rng : range?
Returns the upper bound of rng, or unbounded if rng is unbounded above.

Examples:
 > (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)) # > (range-upper-bound (less-than-range 14)) (exclusive-bound 14)

 procedure rng : bounded-above-range?
Returns the upper endpoint of rng, which must be bounded above.

Examples:
 > (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) # #>) in: the 1st argument of (-> bounded-above-range? any/c) contract from: /rebellion/private/range.rkt blaming: top-level (assuming the contract is correct) at: /rebellion/private/range.rkt:145.3

 procedure rng : range?
Returns the comparator that rng uses to compare values to its bounds.

Examples:
 > (range-comparator (closed-range 3 7)) #> > (range-comparator (open-range "apple" "orange" #:comparator string<=>)) #>

##### 1.11.1.1Types of Ranges

 procedure v : any/c
A predicate for ranges that are bounded, meaning they have both an upper bound and a lower bound. Implies both bounded-above-range? and bounded-below-range?. Mutually exclusive with unbounded-range?.

Examples:
 > (bounded-range? (closed-range 2 7)) #t > (bounded-range? (open-range 3 5)) #t > (bounded-range? (less-than-range 6)) #f

 procedure v : any/c
A predicate for ranges that are bounded above, meaning they have an upper bound. Implies range?. Mutually exclusive with unbounded-above-range?.

Examples:
 > (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 v : any/c
A predicate for ranges that are bounded below, meaning they have a lower bound. Implies range?. Mutually exclusive with unbounded-below-range?.

Examples:
 > (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 v : any/c
A predicate for ranges that are unbounded, meaning they lack either an upper bound, a lower bound, or both. Implies range?. Mutually exclusive with bounded-range?.

Examples:
 > (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
A predicate for ranges that are unbounded above, meaning they lack an upper bound. Implies unbounded-range?. Mutually exclusive with bounded-above-range?.

Examples:
 > (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
A predicate for ranges that are unbounded below, meaning they lack a lower bound. Implies unbounded-range?. Mutually exclusive with bounded-below-range?.

Examples:
 > (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 v : any/c
A predicate for singleton ranges, which contain exactly one value. Singleton ranges must have equal inclusive endpoints. Implies bounded-range? and nonempty-range?.

Examples:
 > (singleton-range? (singleton-range 3)) #t > (singleton-range? (closed-range 3 3)) #t > (singleton-range? (closed-open-range 3 3)) #f

 procedure v : any/c
A predicate for empty ranges, which contain no values. Empty ranges must have equal endpoints, and exactly one endpoint must be exclusive. Implies bounded-range?. Mutually exclusive with nonempty-range?.

Examples:
 > (empty-range? (closed-range 3 3)) #f > (empty-range? (closed-open-range 3 3)) #t > (empty-range? (open-closed-range 3 3)) #t

 procedure v : any/c
A predicate for ranges that are not empty, meaning they contain at least one value. Implies range? and is mutually exclusive with empty-range?.

Examples:
 > (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.2Range Bounds

 procedure v : any/c
A predicate for range bounds, which contain an endpoint value and are either inclusive or exclusive.

 procedure(range-bound endpoint type) → range-bound? endpoint : any/c type : range-bound-type?
Constructs a range bound containing endpoint and of type type. See also the inclusive-bound and exclusive-bound constructors, which are shorthands for when the bound type is already known.

Examples:
 > (range-bound 5 inclusive) (inclusive-bound 5) > (range-bound "banana" exclusive) (exclusive-bound "banana")

 procedure(range-bound-endpoint bound) → any/c bound : range-bound?
Returns the endpoint value in bound.

Examples:
 > (range-bound-endpoint (inclusive-bound 5)) 5 > (range-bound-endpoint (exclusive-bound "banana")) "banana"

 procedure bound : range-bound?
Returns the type (inclusive or exclusive) of bound.

Examples:
 > (range-bound-type (inclusive-bound 5)) # > (range-bound-type (exclusive-bound "banana")) #

 procedure(inclusive-bound endpoint) → range-bound? endpoint : any/c
Constructs an inclusive range bound, which includes values equal to endpoint. An inclusive bound is also called a closed bound.

Examples:
 > (define bound (inclusive-bound 5)) > (range-bound-endpoint bound) 5 > (range-bound-type bound) #

 procedure(exclusive-bound endpoint) → range-bound? endpoint : any/c
Constructs an exclusive range bound, which does not include values equal to endpoint. An exclusive bound is also called an open bound.

Examples:
 > (define bound (exclusive-bound "banana")) > (range-bound-endpoint bound) "banana" > (range-bound-type bound) #

 procedure v : any/c
A predicate for the two constants inclusive and exclusive.

 value
 value
Constants for the two types of range bounds. An inclusive bound includes the endpoint value, an exclusive bound does not include the endpoint value.

 procedure v : any/c
A predicate for the unbounded range endpoint constant.

 value
A constant used with the range constructor to indicate that a range is unbounded on one or both ends.

##### 1.11.2Range Constructors

procedure

 (closed-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range?
lower-endpoint : any/c
upper-endpoint : any/c
comparator : comparator? = real<=>
Constructs a bounded range with inclusive lower and upper bounds of lower-endpoint and upper-endpoint. The constructed range contains all values between lower-endpoint and upper-endpoint, including both endpoints. Values are compared using comparator.

procedure

 (open-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range?
lower-endpoint : any/c
upper-endpoint : any/c
comparator : comparator? = real<=>
Constructs a bounded range with exclusive lower and upper bounds of lower-endpoint and upper-endpoint. The constructed range contains all values between lower-endpoint and upper-endpoint, but does not include either endpoint. Values are compared using comparator.

procedure

 (closed-open-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range?
lower-endpoint : any/c
upper-endpoint : any/c
comparator : comparator? = real<=>
Constructs a bounded range with an inclusive lower bound of lower-endpoint and an exclusive upper bound of upper-endpoint. Values are compared using comparator.

procedure

 (open-closed-range lower-endpoint upper-endpoint [ #:comparator comparator]) → bounded-range?
lower-endpoint : any/c
upper-endpoint : any/c
comparator : comparator? = real<=>
Constructs a bounded range with an exclusive lower bound of lower-endpoint and an inclusive upper bound of upper-endpoint. Values are compared using comparator.

procedure

 (at-least-range lower-endpoint [ #:comparator comparator])
(and/c unbounded-above-range? bounded-below-range?)
lower-endpoint : any/c
comparator : comparator? = real<=>
Constructs an unbounded above range with an inclusive lower bound of lower-endpoint. The constructed range includes every value that is greater than or equal to lower-endpoint according to comparator.

Examples:
 > (at-least-range 14) (range (inclusive-bound 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<=>
Constructs an unbounded below range with an inclusive upper bound of upper-endpoint. The constructed range includes every value that is less than or equal to upper-endpoint according to comparator.

Examples:
 > (at-most-range 14) (range # (inclusive-bound 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<=>
Constructs an unbounded above range with an exclusive lower bound of lower-endpoint. The constructed range includes every value that is greater than lower-endpoint according to comparator.

Examples:
 > (greater-than-range 14) (range (exclusive-bound 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<=>
Constructs an unbounded below range with an exclusive upper bound of upper-endpoint. The constructed range includes every value that is less than upper-endpoint according to comparator.

Examples:
 > (less-than-range 14) (range # (exclusive-bound 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<=>
Constructs a singleton range that contains only values that are equivalent to endpoint, according to comparator.

Examples:
 > (singleton-range 42) (range (inclusive-bound 42) (inclusive-bound 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<=>
Constructs an unbounded range that contains all values, provided they are acceptable inputs for comparator.

Examples:
 > (unbounded-range #:comparator string<=>) (range # # #>) > (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<=>
Constructs an unbounded above range that contains all values greater than lower-bound, according to comparator.

Examples:
 > (unbounded-above-range (inclusive-bound 5)) (range (inclusive-bound 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<=>
Constructs an unbounded below range that contains all values smaller than lower-bound, according to comparator.

Examples:
 > (unbounded-below-range (exclusive-bound 5)) (range # (exclusive-bound 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.11.3Querying Ranges

 procedure(range-contains? range v) → boolean? range : range? v : any/c
Determines whether or not v lies within range by comparing v to its bounds, using the range’s comparator.

Examples:
> (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?
Determines whether or not range encloses other-range. One range encloses another range when the first range contains every value contained by the second. Both ranges must use the same comparator, or else a contract violation is raised. Every range encloses itself, and empty ranges never enclose nonempty ranges.

Examples:
> (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?
Determines whether or not there exists a (possibly empty) range that is enclosed by both range1 and range2.

Examples:
 > (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.4Operations on Ranges

 procedure(range-span range1 range2) → range? range1 : range? range2 : range?
Returns the smallest range that encloses both range1 and range2. The ranges need not be connected, but they must use the same comparator. This operation is commutative, associative, and idempotent.

Examples:
 > (range-span (closed-range 2 5) (open-range 8 9)) (range (inclusive-bound 2) (exclusive-bound 9) #>) > (range-span (less-than-range 4) (singleton-range 6)) (range # (inclusive-bound 6) #>) > (range-span (open-range 2 8) (at-most-range 5)) (range # (exclusive-bound 8) #>)