# Range consolidation

*is a*

**Range consolidation****draft**programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Define a range of numbers `R`

, with bounds `b0`

and `b1`

covering all numbers between and including both bounds. That range can be shown as:

`[b0, b1]`

or equally as:

`[b1, b0]`

.

Given two ranges, the act of consolidation between them compares the two ranges:

- If one range covers all of the other then the result is that encompassing range.
- If the ranges touch or intersect then the result is
*one*new single range covering the overlapping ranges. - Otherwise the act of consolidation is to return the two non-touching ranges.

Given N ranges where N>2 then the result is the same as repeatedly replacing all combinations of two ranges by their consolidation until no further consolidation between range pairs is possible. If N<2 then range consolidation has no strict meaning and the input can be returned.

**Example 1:**- Given the two ranges
`[1, 2.5]`and`[3, 4.2]`then there is no - common element between the ranges and the result is the same as the input.
**Example 2:**- Given the two ranges
`[1, 2.5]`and`[1.8, 4.7]`then there is - an overlap
`[2.5, 1.8]`between the ranges and the result is the single - range
`[1, 4.7]`. Note that order of bounds in a range is not, (yet), stated. **Example 3:**- Given the two ranges
`[6.1, 7.2]`and`[7.2, 8.3]`then they - touch at
`7.2`and the result is the single range`[6.1, 8.3]`. **Example 4:**- Given the three ranges
`[1, 2]`and`[4, 8]`and`[2, 5]` - then there is no intersection of the ranges
`[1, 2]`and`[4, 8]` - but the ranges
`[1, 2]`and`[2, 5]`overlap and consolidate to - produce the range
`[1, 5]`. This range, in turn, overlaps the other range `[4, 8]`, and so consolidates to the final output of the single range`[1, 8]`

**Task:**

Let a normalized range display show the smaller bound to the left; and show the range with the smaller lower bound to the left of other ranges when showing multiple ranges.

Output the *normalised* result of applying consolidation to these five sets of ranges:

[1.1, 2.2] [6.1, 7.2], [7.2, 8.3] [4, 3], [2, 1] [4, 3], [2, 1], [-1, -2], [3.9, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]

Show output here.

## Go

<lang go>package main

import (

"fmt" "math" "sort"

)

type Range struct{ Lower, Upper float64 }

func (r Range) Norm() Range {

if r.Lower > r.Upper { return Range{r.Upper, r.Lower} } return r

}

func (r Range) String() string {

return fmt.Sprintf("[%g, %g]", r.Lower, r.Upper)

}

func (r1 Range) Union(r2 Range) []Range {

if r1.Upper < r2.Lower { return []Range{r1, r2} } r := Range{r1.Lower, math.Max(r1.Upper, r2.Upper)} return []Range{r}

}

func consolidate(rs []Range) []Range {

for i := range rs { rs[i] = rs[i].Norm() } le := len(rs) if le < 2 { return rs } sort.Slice(rs, func(i, j int) bool { return rs[i].Lower < rs[j].Lower }) if le == 2 { return rs[0].Union(rs[1]) } for i := 0; i < le-1; i++ { for j := i + 1; j < le; j++ { ru := rs[i].Union(rs[j]) if len(ru) == 1 { rs[i] = ru[0] copy(rs[j:], rs[j+1:]) rs = rs[:le-1] le-- i-- break } } } return rs

}

func main() {

rss := [][]Range{ Template:1.1, 2.2, {{6.1, 7.2}, {7.2, 8.3}}, {{4, 3}, {2, 1}}, {{4, 3}, {2, 1}, {-1, -2}, {3.9, 10}}, {{1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6}}, } for _, rs := range rss { s := fmt.Sprintf("%v", rs) fmt.Printf("%40s => ", s[1:len(s)-1]) rs2 := consolidate(rs) s = fmt.Sprintf("%v", rs2) fmt.Println(s[1 : len(s)-1]) }

}</lang>

- Output:

[1.1, 2.2] => [1.1, 2.2] [6.1, 7.2] [7.2, 8.3] => [6.1, 8.3] [4, 3] [2, 1] => [1, 2] [3, 4] [4, 3] [2, 1] [-1, -2] [3.9, 10] => [-2, -1] [1, 2] [3, 10] [1, 3] [-6, -1] [-4, -5] [8, 2] [-6, -6] => [-6, -1] [1, 8]

## Perl 6

In Perl 6, a Range is a first class object with its own specialized notation. Perl 6 Ranges allow for exclusion of the boundary numbers. This example doesn't allow for excluded boundaries since that wasn't a requirement in this task. Much of the logic is lifted from Set_of_real_numbers with simplified logic for the much simpler requirements.

Note: the output is in standard Perl 6 notation for Ranges.

<lang perl6># Union sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,$b.max) }

- Intersection

sub infix:<∩> (Range $a, Range $b) { so $a.max >= $b.min }

multi consolidate() { () }

multi consolidate($this is copy, **@those) {

gather { for consolidate |@those -> $that { if $this ∩ $that { $this ∪= $that } else { take $that } } take $this; }

}

for [[1.1, 2.2],],

[[6.1, 7.2], [7.2, 8.3]], [[4, 3], [2, 1]], [[4, 3], [2, 1], [-1, -2], [3.9, 10]], [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]

-> @intervals {

printf "%46s => ", @intervals.perl; say reverse consolidate |@intervals».sort.sort({ [.[0], .[1]] }).map: { Range.new(.[0], .[1]) }

}</lang>

- Output:

[[1.1, 2.2],] => (1.1..2.2) [[6.1, 7.2], [7.2, 8.3]] => (6.1..8.3) [[4, 3], [2, 1]] => (1..2 3..4) [[4, 3], [2, 1], [-1, -2], [3.9, 10]] => (-2..-1 1..2 3..10) [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => (-6..-1 1..8)

## Python

<lang python>def normalize(s):

return sorted(sorted(bounds) for bounds in s if bounds)

def consolidate(ranges):

norm = normalize(ranges) for i, r1 in enumerate(norm): if r1: for r2 in norm[i+1:]: if r2 and r1[-1] >= r2[0]: # intersect? r1[:] = [r1[0], max(r1[-1], r2[-1])] r2.clear() return [rnge for rnge in norm if rnge]

if __name__ == '__main__':

for s in [ 1.1, 2.2, [[6.1, 7.2], [7.2, 8.3]], [[4, 3], [2, 1]], [[4, 3], [2, 1], [-1, -2], [3.9, 10]], [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]], ]: print(f"{str(s)[1:-1]} => {str(consolidate(s))[1:-1]}")

</lang>

- Output:

[1.1, 2.2] => [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] => [6.1, 8.3] [4, 3], [2, 1] => [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] => [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => [-6, -1], [1, 8]

### Functional

Defining consolidation as a fold over a list of tuples: <lang python>from functools import (reduce)

- consolidated :: [(Float, Float)] -> [(Float, Float)]

def consolidated(xs):

ys = sorted(map(tupleSort, xs), reverse=True) return reduce( lambda a, x: [(x[0], max(x[1], a[0][1]))] + a[1:] if ( x[1] >= a[0][0] ) else [x] + a, ys[1:], [ys[0]] )

- tupleSort :: (a, a) -> (a, a)

def tupleSort(ab): a, b = ab return ab if a <= b else (b, a)

if __name__ == '__main__':

tests = [ [(1.1, 2.2)], [(6.1, 7.2), (7.2, 8.3)], [(4, 3), (2, 1)], [(4, 3), (2, 1), (-1, -2), (3.9, 10)], [(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)] ] for x in tests: print ( str(x) + '\n\t-> ' + str(consolidated(x)) + '\n')</lang>

- Output:

[(1.1, 2.2)] -> [(1.1, 2.2)] [(6.1, 7.2), (7.2, 8.3)] -> [(6.1, 8.3)] [(4, 3), (2, 1)] -> [(1, 2), (3, 4)] [(4, 3), (2, 1), (-1, -2), (3.9, 10)] -> [(-2, -1), (1, 2), (3, 10)] [(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)] -> [(-6, -1), (1, 8)]

## zkl

<lang zkl>fcn consolidate(rs){

(s:=List()).append( normalize(rs).reduce('wrap(ab,cd){

if(ab[1]>=cd[0]) L(ab[0],ab[1].max(cd[1])); // consolidate else{ s.append(ab); cd } // no overlap

}) )

} fcn normalize(s){ s.apply("sort").sort(fcn(a,b){ a[0]<b[0] }) }</lang> <lang zkl>foreach rs in (L(

L(L(1.1, 2.2)), L(L(6.1, 7.2), L(7.2, 8.3)), L(L(4, 3), L(2, 1)), L(L(4.0, 3.0), L(2.0, 1.0), L(-1.0, -2.0), L(3.9, 10.0)), L(L(1, 3), L(-6, -1), L(-4, -5), L(8, 2), L(-6, -6)), )){ println(ppp(rs),"--> ",ppp(consolidate(rs))) }

fcn ppp(ll){ ll.pump(String,fcn(list){ list.concat(", ", "[", "] ") }) }</lang>

- Output:

[1.1, 2.2] --> [1.1, 2.2] [6.1, 7.2] [7.2, 8.3] --> [6.1, 8.3] [4, 3] [2, 1] --> [1, 2] [3, 4] [4, 3] [2, 1] [-1, -2] [3.9, 10] --> [-2, -1] [1, 2] [3, 10] [1, 3] [-6, -1] [-4, -5] [8, 2] [-6, -6] --> [-6, -1] [1, 8]