# Category:Jq/RealSet.jq

```module {
"name": "RealSet",
"description": "Real intervals and finite unions thereof",
"version": "0.0.2",
"homepage": "https://rosettacode.org/w/index.php?title=Category:Jq/RealSet.jq",
"license": "MIT",
"author": "pkoppstein at gmail dot com",
};

# A RealSet is a jq array consisting of numbers and/or two-element arrays
# [a,b], where a and b are numbers with a < b, where:
# * each number represents the closed interval containing that number;
# * each array [a,b] represents the open interval from a to b exclusive;
# * the items in the outer array are sorted in ascending order in the obvious way.

# Examples:
#   [] representes the empty RealSet.
#   [1,2] represents the union of the closed intervals containing 1 and 2.
#   [[1,2]] represents the open interval from 1 to 2 exclusive.
#   [1, [1,2], 2] represents the closed interval from 1 to 2 inclusive.
#   [-infinite, 0] represents the open interval consisting of the finite negative numbers.
#   [infinite] represents the closed interval whose only element is positive inifinity.

# To compute the RealSet corresponding to a finite union of real
# intervals, the RealSet filter defined below can be used.

# Unless otherwise specified, the filters defined here assume the input is a RealSet.

def isRealSet:
if length == 0 then true
else . as \$in
| .[0]
| type as \$t
| (\$t == "number" or (\$t == "array" and length == 2 and all(.[]; type == "number") and .[0] < .[1] ))
and (\$in[1:] | isRealSet)
end;

# Input should be canonical except possibly for triplets such as [0,1],1,[1,2]
def canonicalize:
if length < 3 then .
elif (.[0]|type) == "array" and (.[1]|type) == "number" and (.[2]|type) == "array"
and .[0][1] == .[1] and .[1] == .[2][0]
then [[.[0][0], .[2][1]]] + .[3:] | canonicalize
else [.[0]] + ( .[1:] | canonicalize )
end;

def containsNumber(\$r):
def _containsNumber:
if length == 0 then false
else .[0] as \$first
| if \$first|type == "number"
then if \$r == \$first then true
elif \$r > \$first then .[1:] | _containsNumber
else false
end
else # it must be an array
((\$first[0] < \$r) and (\$r < \$first[1])) or (.[1:] | _containsNumber)
end
end;
_containsNumber;

def containsOpenInterval(\$a; \$b):
def coi:
if length == 0 then false
else .[0] as \$first
| if \$first|type == "number" then .[1:] | coi
elif \$first[0] <= \$a and \$first[1] >= \$b then true
elif \$first[1] > \$a then false
else .[1:] | coi
end
end;
coi ;

# \$rs should be a RealSet in canonical form
def contains( \$rs ):
if \$rs | length == 0 then true
elif \$rs[0] | type == "number" then containsNumber(\$rs[0]) and contains(\$rs[1:])
else (containsOpenInterval(\$rs[0][0]; \$rs[0][1]) and contains(\$rs[1:]))
end;

# Input: a RealSet
# Add the open interval (\$A,\$B) to the input
def add( \$A; \$B ):
reduce .[] as \$x ({ ans: [], min: \$A, max: \$B};
if \$x | type == "number"
then if .min
then if \$x <= .min then .ans += [\$x]
elif \$x >= .max
then .ans += [[.min,.max], \$x] | .min = null | .max = null
elif .min < \$x and \$x < .max then .
else .ans += [\$x]
end
else .ans += [\$x]
end
else \$x as [\$a, \$b]
| if .min
then if   \$b <= .min then .ans += [\$x]
elif \$a >= .max
then .ans += [[.min,.max], \$x] | .min = null | .max = null
else .min = ([\$a, .min]|min)
|    .max = ([\$b, .max]|max)
end
else
.ans += [\$x]
end
end)
| if .min then .ans + [[.min, .max]] else .ans end
| canonicalize ;

# Input: a RealSet
# Add the number \$r to the input
def addNumber( \$r ):

# addNumberHelper assumes \$r is NOT in the input RealSet
# and that it has no pair [_,\$r], [\$r,_]
def addNumberHelper:
. as \$in
| (first( range(0;length) as \$i
| (if (\$in[\$i]|type)  == "number" then \$in[\$i] else \$in[\$i][1] end) as \$v
| if \$v > \$r then \$i else empty end ) // false) as \$ix
| if \$ix == false then . + [\$r]
else .[:\$ix]  + [\$r] + .[\$ix:]
end;

if length==0 then [\$r]
elif containsNumber(\$r) then .
else . as \$in
# watch out for the sequence: [_, \$r], [\$r, _]
| (first( range(0;length - 1) as \$i
| if   (\$in[\$i]|type)  == "number" and \$in[\$i] > \$r then false
elif (\$in[\$i]|type)   == "array" and \$in[\$i][0] > \$r then false
elif (\$in[\$i]|type)   == "array" and \$in[\$i][1]  ==\$r and
(\$in[\$i+1]|type) == "array" and \$in[\$i+1][0]==\$r
then \$i
else empty
end ) // false) as \$ix
| if \$ix != false
then \$in[:\$ix] + [[ \$in[\$ix][0], \$in[\$ix+1][1]] ] + \$in[\$ix+2:]
else addNumberHelper
end
end ;

# add two RealSets naively
# Actually \$rs need not be canonical.
def add(\$rs):
reduce \$rs[] as \$x (.;
if \$x|type == "number" then addNumber(\$x)
else add(\$x[0]; \$x[1])
end);

# Return a RealSet
def intersectionNumber(\$r):
first(.[]
| if type == "number"
then if . == \$r then [\$r]
elif . > \$r then []
else empty
end
else . as [\$a, \$b]
| if \$a < \$r and \$r < \$b then [\$r]
elif \$b > \$r then []
else empty
end
end) // [] ;

# Return a RealSet
def intersectionInterval(\$a; \$b):
reduce .[] as \$x ({ans: [], done: false };
if .done then .
else
if \$x|type == "number"
then if \$a < \$x and \$x < \$b then .ans += [\$x]
else .
end
else \$x as [\$A, \$B]
| if \$A > \$b then .done = true
elif \$B < \$a then .
else [ ([\$a,\$A])|max, ([\$b,\$B]|min) ] as \$y
| if \$y[0] < \$y[1] then .ans += [\$y]
else .
end
end
end
end)
| .ans;

def intersection(\$rs):
. as \$in
| reduce \$rs[] as \$x ([];
if \$x|type == "number" then . + (\$in|intersectionNumber(\$x))
else \$x as [\$a, \$b]
| . + (\$in|intersectionInterval(\$a;\$b))
end);

# \$r should be a number
def minusNumber(\$r):
if \$r == -infinite  then intersection( [[-infinite, \$r], [\$r, infinite], infinite] )
elif \$r == infinite then intersection( [-infinite, [-infinite, \$r], [\$r, infinite]] )
else intersection( [-infinite, [-infinite, \$r], [\$r, infinite], infinite] )
end;

# \$a and \$b should be numbers with \$a < \$b
def minusInterval(\$a; \$b):
intersection(
{left:   (if \$a == -infinite then null else [[-infinite, \$a]] end),
right:  (if \$b ==  infinite then null else [[\$b,  infinite]] end) }
| .left + [\$a, \$b] + .right
);

def minus(\$rs):
. as \$in
| reduce \$rs[] as \$x (\$in;
if \$x | type == "number" then minusNumber(\$x)
else minusInterval(\$x[0]; \$x[1])
end);

# The length of the empty RealSet is 0
def RealSetLength:
if any(.[] | select(type=="array") | .[]; isinfinite) then infinite
else map( select(type=="array") | .[1] - .[0] ) | add // 0
end;

# Given an array consisting of open intervals represented by [a,b]
# with a<b, and singleton intervals represented by the singleton
# value, compute the corresponding RealSet
def RealSet:
. as \$in
| [] | add(\$in) ;
```

This category currently contains no pages or media.