Range modifications

From Rosetta Code
Revision as of 15:47, 23 October 2020 by PureFox (talk | contribs) (Added Wren)
Range modifications is a 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.

The increasing range of all integers from a lower to an upper bound, including each boundary, is shown by the lower-boundary separated from the higher-boundary by a single dash. So 64-1234 is the range of all integers from 64 to 1234, (including both 64 and 1234). 10-10 is the range covering the single integer 10.

A sequence of ranges is shown by successive integer ranges that do not overlap, and which have increasing lower bounds. Each range is separated by a single comma. So 13-14,22-22,100999999-101000001 is a sequence of ranges that contain the integers 13 14 22 100999999 101000000 and 101000001.
Empty ranges are removed. An empty sequence has an empty string representation.

Task

Given an initial sequence of ranges write programs to add or remove an integer from the sequence and display the resultant sequence.
Note:

  • The initial sequence may be empty.
  • Adding an int that is already covered should not change the sequence.
  • removing an int that is not in the sequence should not change the sequence.
  • The add and remove operations should print their result in the standard form mentioned.
  • Solutions must work by modifying range boundaries, splitting and joining, as well as creating and deleting ranges.
    Do not use algorithms that create and modify arrays of all the integer values within ranges.

Show the results, (including intermediate results), of performing the following steps

Ex0
   Start with ""
       add 77
       add 79
       add 78
       remove 77
       remove 78
       remove 79
Ex1
   Start with "1-3,5-5"
       add 1
       remove 4
       add 7
       add 8
       add 6
       remove 7
Ex2
   Start with "1-5,10-25,27-30"
       add 26
       add 9
       add 7
       remove 26
       remove 9
       remove 7

Phix

<lang Phix>requires("0.8.2") -- (uses latest apply() functionality)

function consolidate(sequence ranges) 

   for i=1 to length(ranges)-1 do
       integer {lo,hi} = ranges[i],
               {nl,nh} = ranges[i+1]
       if hi+1>=nl then
           ranges[i..i+1] = Template:Lo,nh
           exit
       end if
   end for         
   return ranges

end function

function add(sequence ranges, integer v) 

   integer l = length(ranges)
   for i=1 to l+1 do
       if i>l then       ranges &= Template:V,v         exit end if
       integer {lo,hi} = ranges[i]
       if v>=lo and v<=hi then                     exit
       elsif v=lo-1 then ranges[i][1] = v          exit
       elsif v=hi+1 then ranges[i][2] = v          exit
       elsif v<lo then   ranges[i..i-1] = Template:V,v  exit
       end if
   end for
   return consolidate(ranges)

end function

function del(sequence ranges, integer v) 

   for i=1 to length(ranges) do
       integer {lo,hi} = ranges[i]
       if v>=lo and v<=hi then
           if v=lo then
               if v<hi then    ranges[i][1] = lo+1
               else            ranges[i..i] = {}   end if
           elsif v=hi then
               if lo<v then    ranges[i][2] = hi-1
               else            ranges[i..i] = {}   end if
           else
                               ranges[i..i] = {{lo,v-1},{v+1,hi}}
           end if
           exit
       elsif v<hi then
           exit
       end if
   end for
   return ranges

end function

function action(string range, integer op, v) 

   sequence ranges = split(range,",")
   ranges = vslice(apply(true,scanf,{ranges,{"%d-%d"}}),1)
   ranges = op(ranges,v)
   ranges = apply(true,sprintf,{{"%d-%d"},ranges})
   range = join(ranges,",")
   return range

end function

constant tests = split(""" Start with "" 

   add 77
   add 79
   add 78
   remove 77
   remove 78
   remove 79

Start with "1-3,5-5" 

   add 1
   remove 4
   add 7
   add 8
   add 6
   remove 7

Start with "1-5,10-25,27-30" 

   add 26
   add 9
   add 7
   remove 26
   remove 9
   remove 7

""","\n",no_empty:=true)

string range = "" for i=1 to length(tests) do 

   string ti = tests[i]
   if match("Start with",ti) then
       Template:Range = scanf(ti,"Start with \"%s\"")
       printf(1,"\nNew start range: \"%s\"\n",{range})
   else
       Template:String op, integer v = scanf(trim(ti),"%s %d")
       range = action(range,routine_id(substitute(op,"remove","del")),v)
       printf(1," %9s %2d -> \"%s\"\n",{op,v,range})
   end if

end for</lang>

Output:
New start range: ""
       add 77 -> "77-77"
       add 79 -> "77-77,79-79"
       add 78 -> "77-79"
    remove 77 -> "78-79"
    remove 78 -> "79-79"
    remove 79 -> ""

New start range: "1-3,5-5"
       add  1 -> "1-3,5-5"
    remove  4 -> "1-3,5-5"
       add  7 -> "1-3,5-5,7-7"
       add  8 -> "1-3,5-5,7-8"
       add  6 -> "1-3,5-8"
    remove  7 -> "1-3,5-6,8-8"

New start range: "1-5,10-25,27-30"
       add 26 -> "1-5,10-30"
       add  9 -> "1-5,9-30"
       add  7 -> "1-5,7-7,9-30"
    remove 26 -> "1-5,7-7,9-25,27-30"
    remove  9 -> "1-5,7-7,10-25,27-30"
    remove  7 -> "1-5,10-25,27-30"

Python

<lang python>class Sequence(): 

   def __init__(self, sequence_string):
       self.ranges = self.to_ranges(sequence_string)
       assert self.ranges == sorted(self.ranges), "Sequence order error"
       
   def to_ranges(self, txt):
       return [[int(x) for x in r.strip().split('-')]
               for r in txt.strip().split(',') if r]
   
   def remove(self, rem):
       ranges = self.ranges
       for i, r in enumerate(ranges):
           if r[0] <= rem <= r[1]:
               if r[0] == rem:     # range min
                   if r[1] > rem:
                       r[0] += 1
                   else:
                       del ranges[i]
               elif r[1] == rem:   # range max
                   if r[0] < rem:
                       r[1] -= 1
                   else:
                       del ranges[i]
               else:               # inside, range extremes.
                   r[1], splitrange = rem - 1, [rem + 1, r[1]]
                   ranges.insert(i + 1, splitrange)
               break
           if r[0] > rem:  # Not in sorted list
               break
       return self
           
   def add(self, add):
       ranges = self.ranges
       for i, r in enumerate(ranges):
           if r[0] <= add <= r[1]:     # already included
               break
           elif r[0] - 1 == add:      # rough extend to here
               r[0] = add
               break
           elif r[1] + 1 == add:      # rough extend to here
               r[1] = add
               break
           elif r[0] > add:      # rough insert here
               ranges.insert(i, [add, add])
               break
       else:
           ranges.append([add, add])
           return self
       return self.consolidate()
   
   def consolidate(self):
       "Combine overlapping ranges"
       ranges = self.ranges
       for this, that in zip(ranges, ranges[1:]):
           if this[1] + 1 >= that[0]:  # Ranges interract
               if this[1] >= that[1]:  # this covers that
                   this[:], that[:] = [], this
               else:   # that extends this
                   this[:], that[:] = [], [this[0], that[1]]
       ranges[:] = [r for r in ranges if r]
       return self
   def __repr__(self):
       rr = self.ranges
       return ",".join(f"{r[0]}-{r[1]}" for r in rr)

def demo(opp_txt): 

   by_line = opp_txt.strip().split('\n')
   start = by_line.pop(0)
   ex = Sequence(start.strip().split()[-1][1:-1])    # Sequence("1-3,5-5")
   lines = [line.strip().split() for line in by_line]
   opps = [((ex.add if word[0] == "add" else ex.remove), int(word[1]))
           for word in lines]
   print(f"Start: \"{ex}\"")
   for op, val in opps:
       print(f"    {op.__name__:>6} {val:2} => {op(val)}")
   print()

if __name__ == '__main__': 

   demo("""
       Start with ""
           add 77
           add 79
           add 78
           remove 77
           remove 78
           remove 79
        """)
   demo("""
       Start with "1-3,5-5"
           add 1
           remove 4
           add 7
           add 8
           add 6
           remove 7
        """)
   demo("""
       Start with "1-5,10-25,27-30"
           add 26
           add 9
           add 7
           remove 26
           remove 9
           remove 7
       """)

</lang>

Output:
Start: ""
       add 77 => 77-77
       add 79 => 77-77,79-79
       add 78 => 77-79
    remove 77 => 78-79
    remove 78 => 79-79
    remove 79 => 

Start: "1-3,5-5"
       add  1 => 1-3,5-5
    remove  4 => 1-3,5-5
       add  7 => 1-3,5-5,7-7
       add  8 => 1-3,5-5,7-8
       add  6 => 1-3,5-8
    remove  7 => 1-3,5-6,8-8

Start: "1-5,10-25,27-30"
       add 26 => 1-5,10-30
       add  9 => 1-5,9-30
       add  7 => 1-5,7-7,9-30
    remove 26 => 1-5,7-7,9-25,27-30
    remove  9 => 1-5,7-7,10-25,27-30
    remove  7 => 1-5,10-25,27-30

Wren

Library: Wren-fmt

<lang ecmascript>import "/fmt" for Fmt

var rangesAdd = Fn.new { |ranges, n| 

   if (ranges.count == 0) return ranges.add(n..n)
   for (i in 0...ranges.count) {
       var r = ranges[i]
       if (n < r.from - 1) {
           ranges.insert(i, n..n)
           return
       } else if (n == r.from-1) {
           ranges[i] = n..r.to
           return
       } else if (n <= r.to) {
           return
       } else if (n == r.to+1) {
           ranges[i] = r.from..n
           if (i < ranges.count - 1 && (n == ranges[i+1].from || n + 1 == ranges[i+1].from)) {
               ranges[i] = r.from..ranges[i+1].to
               ranges.removeAt(i+1)
               return
           }
       } else if (i == ranges.count - 1) {
           ranges.add(n..n)
           return
       }
   }

}

var rangesRemove = Fn.new { |ranges, n| 

   if (ranges.count == 0) return
   for (i in 0...ranges.count) {
       var r = ranges[i]
       if (n <= r.from - 1) {
           return
       } else if (n == r.from && n == r.to) {
           ranges.removeAt(i)
           return
       } else if (n == r.from) {
           ranges[i] = n+1..r.to
           return
       } else if (n < r.to) {
           ranges[i] = r.from..n-1
           ranges.insert(i+1, n+1..r.to)
           return
       } else if (n == r.to) {
           ranges[i] = r.from..n-1
           return
       }
   }

}

var standard = Fn.new { |ranges| ranges.toString.replace("..", "-") }

var add = 0 var remove = 1 var fns = [ 

   Fn.new { |ranges, n|
       rangesAdd.call(ranges, n)
       Fmt.print("       add $2d => $n", n, standard.call(ranges))
   },
   Fn.new { |ranges, n|
       rangesRemove.call(ranges, n)
       Fmt.print("    remove $2d => $n", n, standard.call(ranges))
   }

]

var ranges = [] var ops = [ [add, 77], [add, 79], [add, 78], [remove, 77], [remove, 78], [remove, 79] ] System.print("Start: %(standard.call(ranges))") for (op in ops) fns[op[0]].call(ranges, op[1])

ranges = [1..3, 5..5] ops = [ [add, 1], [remove, 4], [add, 7], [add, 8], [add, 6], [remove, 7] ] System.print("\nStart: %(standard.call(ranges))") for (op in ops) fns[op[0]].call(ranges, op[1])

ranges = [1..5, 10..25, 27..30] ops = [ [add, 26], [add, 9], [add, 7], [remove, 26], [remove, 9], [remove, 7] ] System.print("\nStart: %(standard.call(ranges))") for (op in ops) fns[op[0]].call(ranges, op[1])</lang>

Output:
Start: []
       add 77 => [77-77]
       add 79 => [77-77, 79-79]
       add 78 => [77-79]
    remove 77 => [78-79]
    remove 78 => [79-79]
    remove 79 => []

Start: [1-3, 5-5]
       add  1 => [1-3, 5-5]
    remove  4 => [1-3, 5-5]
       add  7 => [1-3, 5-5, 7-7]
       add  8 => [1-3, 5-5, 7-8]
       add  6 => [1-3, 5-8]
    remove  7 => [1-3, 5-6, 8-8]

Start: [1-5, 10-25, 27-30]
       add 26 => [1-5, 10-30]
       add  9 => [1-5, 9-30]
       add  7 => [1-5, 7-7, 9-30]
    remove 26 => [1-5, 7-7, 9-25, 27-30]
    remove  9 => [1-5, 7-7, 10-25, 27-30]
    remove  7 => [1-5, 10-25, 27-30]
Retrieved from "https://rosettacode.org/wiki/Range_modifications?oldid=303161"