Range modifications
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.
Note: There are NO internal spaces in the sequence format.
- 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
Requires Gdip Library
11l
<lang 11l>T Sequence
[(Int, Int)] ranges
F (sequence_string)
I sequence_string != ‘’
L(r) sequence_string.split(‘,’)
V (b, e) = r.split(‘-’).map(x -> Int(x))
.ranges [+]= (b, e)
assert(.ranges == sorted(.ranges), ‘Sequence order error’)
F remove(rem)
L(&r) .ranges
V i = L.index
I rem C r[0] .. r[1]
I r[0] == rem
I r[1] > rem
r[0]++
E
.ranges.pop(i)
E I r[1] == rem
I r[0] < rem
r[1]--
E
.ranges.pop(i)
E
V (r1, splitrange) = (rem - 1, (rem + 1, r[1]))
r[1] = r1
.ranges.insert(i + 1, splitrange)
L.break
I r[0] > rem
L.break
F add(add)
L(&r) .ranges
V i = L.index
I add C r[0] .. r[1]
L.break
E I r[0] - 1 == add
r[0] = add
L.break
E I r[1] + 1 == add
r[1] = add
L.break
E I r[0] > add
.ranges.insert(i, (add, add))
L.break
L.was_no_break
.ranges.append((add, add))
.consolidate()
F consolidate()
‘Combine overlapping ranges’
L(i) 0 .< .ranges.len - 1
V this = i
V that = i + 1
I .ranges[this][1] + 1 >= .ranges[that][0]
I .ranges[this][1] >= .ranges[that][1]
.ranges[that] = .ranges[this]
.ranges[this] = (-1, -1)
E
.ranges[that] = (.ranges[this][0], .ranges[that][1])
.ranges[this] = (-1, -1)
.ranges = .ranges.filter(r -> r != (-1, -1))
F String()
R .ranges.map(r -> r[0]‘-’r[1]).join(‘,’)
F demo(opp_txt)
V by_line = opp_txt.split("\n")
V start = by_line.pop(0)
V ex = Sequence(start.split(‘ ’).last[1 .< (len)-1])
V lines = by_line.map(line -> line.ltrim(‘ ’).split(‘ ’))
V opps = lines.map(word -> (word[0], Int(word[1])))
print(‘Start: "’ex‘"’)
L(op, val) opps
I op == ‘add’
ex.add(val)
E
assert(op == ‘remove’)
ex.remove(val)
print(‘ #6 #2 => #.’.format(op, val, ex))
print()
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
Action!
<lang Action!>DEFINE PTR="CARD" TYPE Range=[BYTE low,high] TYPE Ranges=[
PTR data INT count]
PROC InitRanges(Ranges POINTER rs PTR d)
rs.data=d rs.count=0
RETURN
PROC CheckIndex(Ranges POINTER rs INT index)
IF index<0 OR index>=rs.count THEN Break() FI
RETURN
PTR FUNC GetItemPtr(Ranges POINTER rs INT index)
CheckIndex(rs,index)
RETURN (rs.data+2*index)
PROC PrintRanges(Ranges POINTER rs)
Range POINTER r INT i
IF rs.count=0 THEN
Print("empty")
ELSE
FOR i=0 TO rs.count-1
DO
IF i>0 THEN Print(",") FI
r=GetItemPtr(rs,i)
PrintF("%B-%B",r.low,r.high)
OD
FI
RETURN
PROC AppendRange(Ranges POINTER rs BYTE l,h)
Range POINTER r
rs.count==+1 r=GetItemPtr(rs,rs.count-1) r.low=l r.high=h
RETURN
PROC InsertRange(Ranges POINTER rs INT index BYTE l,h)
Range POINTER r1,r2 INT i
IF index=rs.count THEN AppendRange(rs,l,h) RETURN FI
CheckIndex(rs,index) rs.count==+1 i=rs.count-1 WHILE i>index DO r1=GetItemPtr(rs,i-1) r2=GetItemPtr(rs,i) r2.low=r1.low r2.high=r1.high i==-1 OD r1=GetItemPtr(rs,index) r1.low=l r1.high=h
RETURN
PROC DeleteRange(Ranges POINTER rs INT index)
Range POINTER r1,r2 INT i
CheckIndex(rs,index) FOR i=index TO rs.count-2 DO r1=GetItemPtr(rs,i+1) r2=GetItemPtr(rs,i) r2.low=r1.low r2.high=r1.high OD rs.count==-1
RETURN
BYTE FUNC InRange(Range POINTER r BYTE n)
IF r.low<=n AND n<=r.high THEN RETURN (1) FI
RETURN (0)
INT FUNC FindRange(Ranges POINTER rs BYTE n)
Range POINTER r INT i
FOR i=0 TO rs.count-1
DO
r=GetItemPtr(rs,i)
IF n<=r.high THEN
RETURN (i)
FI
OD
RETURN (rs.count)
PROC Add(Ranges POINTER rs BYTE n)
Range POINTER r,r2 INT i
IF rs.count=0 THEN
AppendRange(rs,n,n) RETURN
FI
FOR i=0 TO rs.count-1
DO
r=GetItemPtr(rs,i)
IF n<r.low-1 THEN
InsertRange(rs,i,n,n) RETURN
ELSEIF n=r.low-1 THEN
r.low=n RETURN
ELSEIF n<=r.high THEN
RETURN
ELSEIF n=r.high+1 THEN
r.high=n
IF i<rs.count-1 THEN
r2=GetItemPtr(rs,i+1)
IF n=r2.low OR n+1=r2.low THEN
r.high=r2.high
DeleteRange(rs,i+1)
FI
FI
RETURN
ELSEIF i=rs.count-1 THEN
AppendRange(rs,n,n)
RETURN
FI
OD
RETURN
PROC Remove(Ranges POINTER rs BYTE n)
Range POINTER r BYTE h INT i
IF rs.count=0 THEN
RETURN
FI
FOR i=0 TO rs.count-1
DO
r=GetItemPtr(rs,i)
IF n<=r.low-1 THEN
RETURN
ELSEIF n=r.low THEN
r.low=n+1
IF r.low>r.high THEN
DeleteRange(rs,i)
FI
RETURN
ELSEIF n<r.high THEN
h=r.high
r.high=n-1
InsertRange(rs,i+1,n+1,h)
RETURN
ELSEIF n=r.high THEN
r.high=n-1
RETURN
FI
OD
RETURN
PROC TestAdd(Ranges POINTER rs BYTE n)
PrintF("%E Add %B -> ",n)
Add(rs,n)
PrintRanges(rs)
RETURN
PROC TestRemove(Ranges POINTER rs BYTE n)
PrintF("%E Remove %B -> ",n)
Remove(rs,n)
PrintRanges(rs)
RETURN
PROC Main()
CARD ARRAY d(20) Ranges rs
InitRanges(rs,d) PrintRanges(rs) TestAdd(rs,77) TestAdd(rs,79) TestAdd(rs,78) TestRemove(rs,77) TestRemove(rs,78) TestRemove(rs,79)
PutE() PutE() InitRanges(rs,d) AppendRange(rs,1,3) AppendRange(rs,5,5) PrintRanges(rs) TestAdd(rs,1) TestRemove(rs,4) TestAdd(rs,7) TestAdd(rs,8) TestAdd(rs,6) TestRemove(rs,7)
PutE() PutE() InitRanges(rs,d) AppendRange(rs,1,5) AppendRange(rs,10,25) AppendRange(rs,27,30) PrintRanges(rs) TestAdd(rs,26) TestAdd(rs,9) TestAdd(rs,7) TestRemove(rs,26) TestRemove(rs,9) TestRemove(rs,7)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
empty Add 77 -> 77-77 Add 79 -> 77-77,79-79 Add 78 -> 77-79 Remove 77 -> 78-79 Remove 78 -> 79-79 Remove 79 -> empty 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 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
AutoHotkey
<lang AutoHotkey>RangeModifications(arr, Modify, v){ global steps ; optional line to track examples steps if (Modify = "add") arr.push([v, v]) if (Modify = "remove") for i, obj in arr if (v >= (start := obj.1)) && (v <= (stop := obj.2)) { arr.RemoveAt(i) if (start = v) && (v = stop) continue arr.push(start < v ? [start, v-1] : [v+1, v+1]) arr.push(v < stop ? [v+1, stop] : [v-1, v-1]) } result := RangeConsolidation(arr) steps .= Modify "`t" v "`t:`t" obj2string(result) "`n" ; optional line to track examples steps return result } RangeConsolidation(arr){ ;-) borrowed my own function from http://www.rosettacode.org/wiki/Range_consolidation#AutoHotkey arr1 := [], arr2 := [], result := []
for i, obj in arr arr1[i,1] := min(arr[i]*), arr1[i,2] := max(arr[i]*) ; sort each range individually
for i, obj in arr1 if (obj.2 > arr2[obj.1]) arr2[obj.1] := obj.2 ; creates helper array sorted by range
i := 1 for start, stop in arr2 if (i = 1) || (start > result[i-1, 2] + 1) ; first or non overlapping range result[i, 1] := start, result[i, 2] := stop, i++ else ; overlapping range result[i-1, 2] := stop > result[i-1, 2] ? stop : result[i-1, 2] return result } obj2string(arr){ for i, obj in arr str .= obj.1 "-" obj.2 "," return Trim(str, ",") } string2obj(str){ arr := [] for i, v in StrSplit(str, ",") x := StrSplit(v, "-"), arr.push([x.1, x.2]) return arr }</lang> Examples:<lang AutoHotkey>arr := string2obj("") steps .= "start with`t:`t" obj2string(arr) "`n" arr := RangeModifications(arr, "Add", 77) arr := RangeModifications(arr, "Add", 79) arr := RangeModifications(arr, "Add", 78) arr := RangeModifications(arr, "Remove", 77) arr := RangeModifications(arr, "Remove", 78) arr := RangeModifications(arr, "Remove", 79) MsgBox % steps
steps := "" arr := string2obj("1-3,5-5") steps .= "start with`t:`t" obj2string(arr) "`n" arr := RangeModifications(arr, "Add", 1) arr := RangeModifications(arr, "Remove", 4) arr := RangeModifications(arr, "Add", 7) arr := RangeModifications(arr, "Add", 8) arr := RangeModifications(arr, "add", 6) arr := RangeModifications(arr, "Remove", 7) MsgBox % steps
steps := "" arr := string2obj("1-5,10-25,27-30") steps .= "start with`t:`t" obj2string(arr) "`n" arr := RangeModifications(arr, "Add", 26) arr := RangeModifications(arr, "Add", 9) arr := RangeModifications(arr, "Add", 7) arr := RangeModifications(arr, "Remove", 26) arr := RangeModifications(arr, "Remove", 9) arr := RangeModifications(arr, "Remove", 7) MsgBox % steps return</lang>
- Output:
start with : 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 with : 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 with : 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
C++
<lang cpp>#include <algorithm>
- include <iomanip>
- include <iostream>
- include <list>
struct range {
range(int lo, int hi) : low(lo), high(hi) {}
int low;
int high;
};
std::ostream& operator<<(std::ostream& out, const range& r) {
return out << r.low << '-' << r.high;
}
class ranges { public:
ranges() {}
explicit ranges(std::initializer_list<range> init) : ranges_(init) {}
void add(int n);
void remove(int n);
bool empty() const { return ranges_.empty(); }
private:
friend std::ostream& operator<<(std::ostream& out, const ranges& r); std::list<range> ranges_;
};
void ranges::add(int n) {
for (auto i = ranges_.begin(); i != ranges_.end(); ++i) {
if (n + 1 < i->low) {
ranges_.emplace(i, n, n);
return;
}
if (n > i->high + 1)
continue;
if (n + 1 == i->low)
i->low = n;
else if (n == i->high + 1)
i->high = n;
else
return;
if (i != ranges_.begin()) {
auto prev = std::prev(i);
if (prev->high + 1 == i->low) {
i->low = prev->low;
ranges_.erase(prev);
}
}
auto next = std::next(i);
if (next != ranges_.end() && next->low - 1 == i->high) {
i->high = next->high;
ranges_.erase(next);
}
return;
}
ranges_.emplace_back(n, n);
}
void ranges::remove(int n) {
for (auto i = ranges_.begin(); i != ranges_.end(); ++i) {
if (n < i->low)
return;
if (n == i->low) {
if (++i->low > i->high)
ranges_.erase(i);
return;
}
if (n == i->high) {
if (--i->high < i->low)
ranges_.erase(i);
return;
}
if (n > i->low & n < i->high) {
int low = i->low;
i->low = n + 1;
ranges_.emplace(i, low, n - 1);
return;
}
}
}
std::ostream& operator<<(std::ostream& out, const ranges& r) {
if (!r.empty()) {
auto i = r.ranges_.begin();
out << *i++;
for (; i != r.ranges_.end(); ++i)
out << ',' << *i;
}
return out;
}
void test_add(ranges& r, int n) {
r.add(n); std::cout << " add " << std::setw(2) << n << " => " << r << '\n';
}
void test_remove(ranges& r, int n) {
r.remove(n); std::cout << " remove " << std::setw(2) << n << " => " << r << '\n';
}
void test1() {
ranges r; std::cout << "Start: \"" << r << "\"\n"; test_add(r, 77); test_add(r, 79); test_add(r, 78); test_remove(r, 77); test_remove(r, 78); test_remove(r, 79);
}
void test2() {
ranges r{{1,3}, {5,5}};
std::cout << "Start: \"" << r << "\"\n";
test_add(r, 1);
test_remove(r, 4);
test_add(r, 7);
test_add(r, 8);
test_add(r, 6);
test_remove(r, 7);
}
void test3() {
ranges r{{1,5}, {10,25}, {27,30}};
std::cout << "Start: \"" << r << "\"\n";
test_add(r, 26);
test_add(r, 9);
test_add(r, 7);
test_remove(r, 26);
test_remove(r, 9);
test_remove(r, 7);
}
int main() {
test1(); std::cout << '\n'; test2(); std::cout << '\n'; test3(); return 0;
}</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
Go
<lang go>package main
import (
"fmt" "strings"
)
type rng struct{ from, to int }
type fn func(rngs *[]rng, n int)
func (r rng) String() string { return fmt.Sprintf("%d-%d", r.from, r.to) }
func rangesAdd(rngs []rng, n int) []rng {
if len(rngs) == 0 {
rngs = append(rngs, rng{n, n})
return rngs
}
for i, r := range rngs {
if n < r.from-1 {
rngs = append(rngs, rng{})
copy(rngs[i+1:], rngs[i:])
rngs[i] = rng{n, n}
return rngs
} else if n == r.from-1 {
rngs[i] = rng{n, r.to}
return rngs
} else if n <= r.to {
return rngs
} else if n == r.to+1 {
rngs[i] = rng{r.from, n}
if i < len(rngs)-1 && (n == rngs[i+1].from || n+1 == rngs[i+1].from) {
rngs[i] = rng{r.from, rngs[i+1].to}
copy(rngs[i+1:], rngs[i+2:])
rngs[len(rngs)-1] = rng{}
rngs = rngs[:len(rngs)-1]
}
return rngs
} else if i == len(rngs)-1 {
rngs = append(rngs, rng{n, n})
return rngs
}
}
return rngs
}
func rangesRemove(rngs []rng, n int) []rng {
if len(rngs) == 0 {
return rngs
}
for i, r := range rngs {
if n <= r.from-1 {
return rngs
} else if n == r.from && n == r.to {
copy(rngs[i:], rngs[i+1:])
rngs[len(rngs)-1] = rng{}
rngs = rngs[:len(rngs)-1]
return rngs
} else if n == r.from {
rngs[i] = rng{n + 1, r.to}
return rngs
} else if n < r.to {
rngs[i] = rng{r.from, n - 1}
rngs = append(rngs, rng{})
copy(rngs[i+2:], rngs[i+1:])
rngs[i+1] = rng{n + 1, r.to}
return rngs
} else if n == r.to {
rngs[i] = rng{r.from, n - 1}
return rngs
}
}
return rngs
}
func standard(rngs []rng) string {
if len(rngs) == 0 {
return ""
}
var sb strings.Builder
for _, r := range rngs {
sb.WriteString(fmt.Sprintf("%s,", r))
}
s := sb.String()
return s[:len(s)-1]
}
func main() {
const add = 0
const remove = 1
fns := []fn{
func(prngs *[]rng, n int) {
*prngs = rangesAdd(*prngs, n)
fmt.Printf(" add %2d => %s\n", n, standard(*prngs))
},
func(prngs *[]rng, n int) {
*prngs = rangesRemove(*prngs, n)
fmt.Printf(" remove %2d => %s\n", n, standard(*prngs))
},
}
var rngs []rng
ops := [][2]int{{add, 77}, {add, 79}, {add, 78}, {remove, 77}, {remove, 78}, {remove, 79}}
fmt.Printf("Start: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, op[1])
}
rngs = []rng{{1, 3}, {5, 5}}
ops = [][2]int{{add, 1}, {remove, 4}, {add, 7}, {add, 8}, {add, 6}, {remove, 7}}
fmt.Printf("\nStart: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, op[1])
}
rngs = []rng{{1, 5}, {10, 25}, {27, 30}}
ops = [][2]int{{add, 26}, {add, 9}, {add, 7}, {remove, 26}, {remove, 9}, {remove, 7}}
fmt.Printf("\nStart: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, 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
Julia
Julia has iterator classes called a type of Range, such as integer UnitRanges, that are like the "10-10" of the task but are stated as 10:10, with a colon not a minus sign. This implementation uses Julia's UnitRange class internally. <lang julia>import Base.parse, Base.print, Base.reduce
const RangeSequence = Array{UnitRange, 1}
function combine!(seq::RangeSequence, r::UnitRange)
isempty(seq) && return push!(seq, r)
if r.start < seq[end].start
reduce!(push!(seq, r))
elseif r.stop > seq[end].stop
if r.start <= seq[end].stop + 1
seq[end] = seq[end].start:r.stop
else
push!(seq, r)
end
end
return seq
end
function parse(::Type{RangeSequence}, s)
seq = UnitRange[]
entries = sort!(split(s, r"\s*,\s*"))
for e in entries
startstop = split(e, r"\:|\-")
if length(startstop) == 2
start, stop = tryparse(Int, startstop[1]), tryparse(Int, startstop[2])
start, stop = start <= stop ? (start, stop) : (stop, start)
start != nothing && stop != nothing && push!(seq, start:stop)
elseif (n = tryparse(Int, startstop[1])) != nothing
push!(seq, n:n)
end
end
return reduce!(seq)
end
reduce!(a::RangeSequence) = (s = sort(a); empty!(a); for r in s combine!(a, r) end; a) reduce(a::RangeSequence) = (seq = UnitRange[]; for r in sort(a) combine!(seq, r) end; seq)
insertinteger!(seq::RangeSequence, n::Integer) = begin push!(seq, n:n); reduce!(seq) end
insertintegerprint!(seq, n) = println(" added $n => ", insertinteger!(seq, n)) removeintegerprint!(seq, n) = println(" removed $n => ", removeinteger!(seq, n))
function removeinteger!(seq::RangeSequence, n::Integer)
for (pos, r) in enumerate(seq)
if n in r
start, stop = r.start, r.stop
if start == stop == n
deleteat!(seq, pos:pos)
elseif stop == n
seq[pos] = start:stop-1
elseif start == n
seq[pos] = start+1:stop
elseif start < n < stop
seq[pos] = n+1:stop
insert!(seq, pos, start:n-1)
end
break
end
end
return seq
end
function print(io::IO, seq::RangeSequence)
return print(io, "\"" * join(map(r -> "$(r.start)-$(r.stop)", reduce(seq)), ",") * "\"")
end
const seq = parse(RangeSequence, "") println("Start: $seq") insertintegerprint!(seq, 77) insertintegerprint!(seq, 79) insertintegerprint!(seq, 78) removeintegerprint!(seq, 77) removeintegerprint!(seq, 78) removeintegerprint!(seq, 79)
const seq2 = parse(RangeSequence, "1-3, 5-5") println("Start: $seq2") insertintegerprint!(seq2, 1) removeintegerprint!(seq2, 4) insertintegerprint!(seq2, 7) insertintegerprint!(seq2, 8) insertintegerprint!(seq2, 6) removeintegerprint!(seq2, 7)
const seq3 = parse(RangeSequence, "1-5, 10-25, 27-30") println("Start: $seq3") insertintegerprint!(seq3, 26) insertintegerprint!(seq3, 9) insertintegerprint!(seq3, 7) removeintegerprint!(seq3, 26) removeintegerprint!(seq3, 9) removeintegerprint!(seq3, 7)
println("Parse \"10-25, 1-5, 27-30\" => ", parse(RangeSequence, "10-25, 1-5, 27-30")) println("Parse \"3-1,15-5,25-10,30-27\" => ", parse(RangeSequence, "3-1,15-5,25-10,30-27"))
</lang>
- Output:
Start: ""
added 77 => 77-77
added 79 => 77-77,79-79
added 78 => 77-79
removed 77 => 78-79
removed 78 => 79-79
removed 79 =>
Start: 1-3,5-5
added 1 => 1-3,5-5
removed 4 => 1-3,5-5
added 7 => 1-3,5-5,7-7
added 8 => 1-3,5-5,7-8
added 6 => 1-3,5-8
removed 7 => 1-3,5-6,8-8
Start: 1-5,10-25,27-30
added 26 => 1-5,10-30
added 9 => 1-5,9-30
added 7 => 1-5,7-7,9-30
removed 26 => 1-5,7-7,9-25,27-30
removed 9 => 1-5,7-7,10-25,27-30
removed 7 => 1-5,10-25,27-30
Parse "10-25, 1-5, 27-30" => 1-5,10-25,27-30
Parse "3-1,15-5,25-10,30-27" => 1-3,5-25,27-30
Nim
<lang Nim>import algorithm, sequtils, strscans, strutils
type
Range = tuple[low, high: int] Ranges = seq[Range]
func `$`(ranges: Ranges): string =
## Return the string representation of a list of ranges.
result.add '"'
for r in ranges:
result.addSep(",", 1)
result.add "$1-$2".format(r.low, r.high)
result.add '"'
proc initRanges(ranges: varargs[Range]): seq[Range] =
## Create a list of ranges with the given (potentially empty) ranges.
stdout.write "Start with "
var ranges = ranges.filterIt(it.low <= it.high)
if ranges.len <= 1:
echo ranges
return ranges
ranges.sort()
result = @[ranges[0]]
for newRange in ranges[1..^1]:
if newRange.low <= result[^1].high:
# Intersection is not empty.
if newRange.high > result[^1].low: result[^1].high = newRange.high
else:
# New range.
result.add newRange
echo result
proc initRanges(rangeString: string): seq[Range] =
## Create a list fo ranges from a string representation.
if rangeString.len == 0: return
var ranges: seq[Range]
for field in rangeString.split(','):
var r: Range
if field.scanf("$i-$i$.", r.low, r.high):
ranges.add r
else:
raise newException(ValueError, "Wrong range specification: " & field)
result = initRanges(ranges)
func contains(r: Range; val: int): bool =
## Return true if a range contains a value. ## Used by "in" operator. val >= r.low and val <= r.high
proc add(ranges: var Ranges; val: int) =
## Add a value to a list of ranges.
stdout.write "add ", ($val).alignLeft(2), " → "
if ranges.len == 0:
ranges.add (val, val)
echo ranges
return
# Search the range immediately following the value.
var idx = -1
for i, r in ranges:
if val in r:
# Already in a range: no changes.
echo ranges
return
if val < r.low:
idx = i
break
if idx < 0:
# Not found, so to add at the end.
if ranges[^1].high == val - 1: ranges[^1].high = val # Extend last range.
else: ranges.add (val, val) # Add a range.
elif ranges[idx].low == val + 1:
# Just before a range.
ranges[idx].low = val
if idx > 0:
if ranges[idx-1].high >= val - 1:
# Merge two ranges.
ranges[idx].low = ranges[idx-1].low
ranges.delete(idx - 1)
elif idx > 0:
# Between two ranges.
if ranges[idx-1].high == val - 1: ranges[idx-1].high = val # Extend previous range.
else: ranges.insert((val, val), idx) # Insert a range.
else:
# At the beginning.
ranges.insert((val, val), 0)
echo ranges
proc remove(ranges: var Ranges; val: int) =
## remove a value from a list of ranges.
stdout.write "remove ", ($val).alignLeft(2), " → "
# Search the range containing the value.
var idx = - 1
for i, r in ranges:
if val in r:
idx = i
break
if val < r.low: break
if idx < 0:
# Not found.
echo ranges
return
let r = ranges[idx]
if r.low == val:
if r.high == val:
# Delete the range.
ranges.delete(idx)
else:
# Update the low value.
ranges[idx].low = val + 1
elif r.high == val:
# Update the high value.
ranges[idx].high = val - 1
else:
# Split the range.
ranges.insert(r, idx + 1)
ranges[idx].high = val - 1
ranges[idx+1].low = val + 1
echo ranges
var r = initRanges("")
r.add 77
r.add 79
r.add 78
r.remove 77
r.remove 78
r.remove 79
echo()
r = initRanges("1-3,5-5") r.add 1 r.remove 4 r.add 7 r.add 8 r.add 6 r.remove 7 echo()
r = initRanges("1-5,10-25,27-30") r.add 26 r.add 9 r.add 7 r.remove 26 r.remove 9 r.remove 7</lang>
- Output:
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 with "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 with "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"
Perl
<lang perl>#!/usr/bin/perl
use strict; use warnings;
my $ranges;
while( )
{
my ($cmd) = /(\S.*\S)/ or print "\n";
$ranges = /Start with "(.*)"/ ? $1 :
/add (\d+)/ ? add($1) :
/remove (\d+)/ ? remove($1) :
$ranges;
$cmd and printf qq(%35s -> "%s"\n), $cmd, $ranges;
}
sub add
{
my $n = shift;
s/^$/$n-$n/ # empty
or s/-@{[$n-1]},@{[$n+1]}\b// # join 2 ranges
or s/\b@{[$n+1]}-/$n-/ # lower start
or s/-@{[$n-1]}\b/-$n/ # raise end
or s/^(?=(\d+)-(??{$n < $1 ? : 'X'}))/$n-$n,/ # add front
or s/-(\d+)\K$(??{$1 < $n ? : 'X'})/,$n-$n/ # add end
or s/\b(\d+),(\d+)\b(??{$1 < $n-1 && $n < $2+1 ? : 'X'
})/$1,$n-$n,$2/ # add middle
for $ranges;
$ranges;
}
sub remove
{
my $n = shift;
s/^$n-$n,?|,$n-$n\b// # single item
or s/\b$n(?=-)/$n+1/e # first from range
or s/-\K$n\b/$n-1/e # last from range
or s/\b(\d+)-(\d+)\b(??{$1 < $n && $n < $2 ? : 'X'
})/$1-@{[$n-1]},@{[$n+1]}-$2/ # split range
for $ranges;
$ranges;
}
__DATA__
Start with "1-3,5-5"
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</lang>
- Output:
Start with "1-3,5-5" -> "1-3,5-5"
add 77 -> "1-3,5-5,77-77"
add 79 -> "1-3,5-5,77-77,79-79"
add 78 -> "1-3,5-5,77-79"
remove 77 -> "1-3,5-5,78-79"
remove 78 -> "1-3,5-5,79-79"
remove 79 -> "1-3,5-5"
Start with "1-3,5-5" -> "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 with "1-5,10-25,27-30" -> "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"
Phix
with javascript_semantics function add(sequence ranges, atom v) -- -- eg {} + 9 --> {{9,9}} -- [1] -- {{3,5}} + 9 --> {{3,5},{9,9}} -- [1] -- {{3,5}} + 4 --> as-is -- [2] -- {{3,5}} + 2 --> {{2,5}} -- [3] -- {{3,5},{7,9}} + 6 --> {{3,9}} -- [4] -- {{3,5},{8,9}} + 6 --> {{3,6},{8,9}} -- [5] -- {{3,5},{8,9}} + 7 --> {{3,5},{7,9}} -- [3] -- {{3,5}} + 6 --> {{3,6}} -- [6] -- {{3,5}} + 1 --> {{1,1},{3,5}} -- [7] -- integer l = length(ranges) ranges = deep_copy(ranges) for i=1 to l+1 do if i>l then ranges &= {{v,v}} exit -- [1] end if atom nl,{lo,hi} = ranges[i] if v>=lo and v<=hi then exit -- [2] elsif v=lo-1 then ranges[i][1] = v exit -- [3] elsif v=hi+1 then if i<l then {nl,hi} = ranges[i+1] if nl=v+1 then ranges[i..i+1] = {{lo,hi}} exit -- [4] else ranges[i][2] = v exit -- [5] end if else ranges[i][2] = v exit -- [6] end if elsif v<lo then ranges[i..i-1] = {{v,v}} exit -- [7] end if end for return ranges end function function del(sequence ranges, atom v) -- -- eg {{1,2}} - 1 --> {{2,2}} -- [1] -- {{2,2}} - 2 --> {} -- [2] -- {{1,2}} - 2 --> {{1,1}} -- [3] -- {{1,3}} - 2 --> {{1,1},{3,3}} -- [4] -- {{2,3}} - 1 --> as-is -- [5] -- ranges = deep_copy(ranges) for i=1 to length(ranges) do atom {lo,hi} = ranges[i] if v>=lo and v<=hi then if v=lo then if v<hi then ranges[i][1] = lo+1 -- [1] else ranges[i..i] = {} end if -- [2] elsif v==hi then ranges[i][2] = hi-1 -- [3] else ranges[i..i] = {{lo,v-1},{v+1,hi}} -- [4] end if exit elsif v<hi then exit end if -- [5] end for return ranges 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 Start with "13-14,22-22,100000999999-100001000000,100001000003-999999999999" remove 22 remove 100000999999 remove 100001000000 add 100001000001 add 100001000002 remove 100001000002 remove 100001000001 ""","\n",no_empty:=true) string range = "" sequence ranges -- range internal form for i=1 to length(tests) do string ti = tests[i] if match("Start with",ti) then {range} = scanf(trim(ti),"Start with \"%s\"")[1] ranges = split(range,",") ranges = vslice(apply(true,scanf,{ranges,{"%d-%d"}}),1) printf(1,"\n Start with: \"%s\"\n",{range}) -- ^^ ^^ else {string op, atom v} = scanf(trim(ti),"%s %d")[1] integer rid = routine_id(substitute(op,"remove","del")) ranges = rid(ranges,v) range = join(apply(true,sprintf,{{"%d-%d"},ranges}),",") printf(1," %9s %-12d -> \"%s\"\n",{op,v,range}) -- ^^ ^^ end if end for
- Output:
(Note that all double-quotes in the output were deliberately added in the last two printf() statements, mainly to prove there are no unnecessary spaces, etc, and are (see ^^) obviously trivial to remove.)
Start with: ""
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 with: "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 with: "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"
Start with: "13-14,22-22,100000999999-100001000000,100001000003-999999999999"
remove 22 -> "13-14,100000999999-100001000000,100001000003-999999999999"
remove 100000999999 -> "13-14,100001000000-100001000000,100001000003-999999999999"
remove 100001000000 -> "13-14,100001000003-999999999999"
add 100001000001 -> "13-14,100001000001-100001000001,100001000003-999999999999"
add 100001000002 -> "13-14,100001000001-999999999999"
remove 100001000002 -> "13-14,100001000001-100001000001,100001000003-999999999999"
remove 100001000001 -> "13-14,100001000003-999999999999"
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
Raku
Quite a bit of this is just transforming syntax back and forth. Raku already has Ranges and Sequences as first class objects, though the syntax is different.
Demonstrate the task required examples: adding and removing integers, as well as an example adding and removing ranges to / from the sequence, in both native Raku syntax and the "Stringy" syntax required by the task.
Demo with some extremely large values / ranges. Capable of working with infinite ranges by default.
Won't handle negative numbers as written, mostly due the need to work around the syntax requirements for output.
<lang perl6>my @seq;
-> $op, $string { printf "%20s -> %s\n", $op, $string } for
'Start', to-string( @seq = canonicalize "" ), 'add 77', to-string( @seq .= &add(77) ), 'add 79', to-string( @seq .= &add(79) ), 'add 78', to-string( @seq .= &add(78) ), 'remove 77', to-string( @seq .= &remove(77) ), 'remove 78', to-string( @seq .= &remove(78) ), 'remove 79', to-string( @seq .= &remove(79) );
say ; -> $op, $string { printf "%20s -> %s\n", $op, $string } for
'Start', to-string( @seq = canonicalize "1-3,5-5" ), 'add 1', to-string( @seq .= &add(1) ), 'remove 4', to-string( @seq .= &remove(4) ), 'add 7', to-string( @seq .= &add(7) ), 'add 8', to-string( @seq .= &add(8) ), 'add 6', to-string( @seq .= &add(6) ), 'remove 7', to-string( @seq .= &remove(7) );
say ; -> $op, $string { printf "%20s -> %s\n", $op, $string } for
'Start', to-string( @seq = canonicalize "1-5,10-25,27-30" ), 'add 26', to-string( @seq .= &add(26) ), 'add 9', to-string( @seq .= &add(9) ), 'add 7', to-string( @seq .= &add(7) ), 'remove 26', to-string( @seq .= &remove(26) ), 'remove 9', to-string( @seq .= &remove(9) ), 'remove 7', to-string( @seq .= &remove(7) );
say ; -> $op, $string { printf "%30s -> %s\n", $op, $string } for
'Start', to-string( @seq = canonicalize "6-57,160-251,2700-7000000" ),
'add "2502-2698"', to-string( @seq .= &add("2502-2698") ),
'add 41..69', to-string( @seq .= &add(41..69) ),
'remove 17..30', to-string( @seq .= &remove(17..30) ),
'remove 4391..6527', to-string( @seq .= &remove("4391-6527") ),
'add 2699', to-string( @seq .= &add(2699) ),
'add 76', to-string( @seq .= &add(76) ),
'add 78', to-string( @seq .= &add(78) ),
'remove "70-165"', to-string( @seq .= &remove("70-165") ),
'remove 16..31', to-string( @seq .= &remove(16..31) ),
'add 1.417e16 .. 3.2e21', to-string( @seq .= &add(1.417e16.Int .. 3.2e21.Int) ),
'remove "4001-Inf"', to-string( @seq .= &remove("4001-Inf") );
sub canonicalize (Str $ranges) { sort consolidate |sort parse-range $ranges }
sub parse-range (Str $_) { .comb(/\d+|'Inf'/).map: { +$^α .. +$^ω } }
sub to-string (@ranges) { qq|"{ @ranges».minmax».join('-').join(',') }"| }
multi add (@ranges, Int $i) { samewith @ranges, $i .. $i } multi add (@ranges, Str $s) { samewith @ranges, |parse-range($s) } multi add (@ranges, Range $r) { @ranges > 0 ?? (sort consolidate |sort |@ranges, $r) !! $r }
multi remove (@ranges, Int $i) { samewith @ranges, $i .. $i } multi remove (@ranges, Str $s) { samewith @ranges, |parse-range($s) } multi remove (@ranges, Range $r) {
gather for |@ranges -> $this {
if $r.min <= $this.min {
if $r.max >= $this.min and $r.max < $this.max {
take $r.max + 1 .. $this.max
}
elsif $r.max < $this.min {
take $this
}
}
else {
if $r.max >= $this.max and $r.min <= $this.max {
take $this.min .. $r.min - 1
}
elsif $r.max < $this.max and $r.min > $this.min {
take $this.min .. $r.min - 1;
take $r.max + 1 .. $this.max
}
else {
take $this
}
}
}
}
multi consolidate() { () }
multi consolidate($this is copy, **@those) {
sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,max($a.max,$b.max)) }
sub infix:<∩> (Range $a, Range $b) { so $a.max >= $b.min }
my @ranges = sort gather {
for consolidate |@those -> $that {
next unless $that;
if $this ∩ $that { $this ∪= $that }
else { take $that }
}
take $this;
}
for reverse ^(@ranges - 1) {
if @ranges[$_].max == @ranges[$_ + 1].min - 1 {
@ranges[$_] = @ranges[$_].min .. @ranges[$_ + 1].max;
@ranges[$_ + 1]:delete
}
}
@ranges
}</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"
Start -> "6-57,160-251,2700-7000000"
add "2502-2698" -> "6-57,160-251,2502-2698,2700-7000000"
add 41..69 -> "6-69,160-251,2502-2698,2700-7000000"
remove 17..30 -> "6-16,31-69,160-251,2502-2698,2700-7000000"
remove 4391..6527 -> "6-16,31-69,160-251,2502-2698,2700-4390,6528-7000000"
add 2699 -> "6-16,31-69,160-251,2502-4390,6528-7000000"
add 76 -> "6-16,31-69,76-76,160-251,2502-4390,6528-7000000"
add 78 -> "6-16,31-69,76-76,78-78,160-251,2502-4390,6528-7000000"
remove "70-165" -> "6-16,31-69,166-251,2502-4390,6528-7000000"
remove 16..31 -> "6-15,32-69,166-251,2502-4390,6528-7000000"
add 1.417e16 .. 3.2e21 -> "6-15,32-69,166-251,2502-4390,6528-7000000,14170000000000000-3200000000000000000000"
remove "4001-Inf" -> "6-15,32-69,166-251,2502-4000"
Wren
<lang ecmascript>import "/fmt" for Fmt
var rangesAdd = Fn.new { |ranges, n|
if (ranges.count == 0) {
ranges.add(n..n)
return
}
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| Fmt.v("s", 0, ranges, 0, ",", "").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] ] Fmt.print("Start: $q", 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] ] Fmt.print("\nStart: $q", 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] ] Fmt.print("\nStart: $q", 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