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) ;