convert range descriptions to lists of numbers

[ron minnich]

I have a simple need to turn things like this:
1-4,5,9-11
into
1 2 3 4 5 9 10 11

I've got the C code to do it, and it's not that complicated, but I
thought I'd ask as a new guy if there's a package or set of functions
written to do such a thing.

I'm thinking of just doing a Split on the , and then generating the
string from first '-' list, but at the same time ... if there's a
handy thing to do this, I'm lazy.

It's a long user-oriented story as to why this is not being done with regexp's.

ron

[fango]

A straightforward code comes into mind is:

package main

import (
"strings"
"strconv"
)

func main() {
s := "1-4,5,9-11"
a := strings.Split(s, ",", -1)
for _, a0 := range a {
b := strings.Split(a0, "-", -1)
j, _ := strconv.Atoi(b[0])
if len(b) == 2 {
j, _ = strconv.Atoi(b[1])
}
for i, _ := strconv.Atoi(b[0]); i <= j; i++ {
print(i, " ")
}
}
}

It would be nice to have a Set, that accepts "i-j,k" notation, then
reuse Set to many things like sort, count or other fancy map func,
same line as been discussed in Programming Peals.

Cheers,
Fango

[ron minnich]

On Mon, Aug 30, 2010 at 5:43 PM, fango <fan.h...@gmail.com> wrote:
> A straightforward code comes into mind is:

Yep, that's pretty much what I did.

I used the nice Trim function to clean up the string and also I
covered people making typos like two commas in a row etc. It's easier
to cover silly user typos than to sit on the phone arguing with people
about whether you should cover silly user typos :-)

What's fun is it took no time at all to do this thing that is just not
that fun in C :-)

ron

[fango]

Pretty true. I attribute this to the nice trade-off between 'machine'
space and 'man' time. GC mops the floor so nice that I feel like
living in a hotel rather than my apartment :)

Regards,
Fango

On Aug 31, 8:47 am, ron minnich <rminn...@gmail.com> wrote:

[fango]

Ok, Here goes what I mean a Set from Programming Pearls:

package main

import (
"fmt"
"strings"
"strconv"
)

const (
BitOfWord = 32
Shift = 5
Mask = 0x1F
)

type Set []uint32

func (x *Set) SetInt(i int, set bool) {
// print(i, " ")
y := []uint32(*x)
l := i >> Shift + 1
if l > cap(y) {
println("new set", i)
x0 := make(Set, l)
copy(x0, y)
*x = x0
y = []uint32(*x)
}
if set {
y[i>>Shift] |= 1 << (uint32(i) & Mask)
} else {
y[i>>Shift] &^= 1 << (uint32(i) & Mask)
}
}

func (x *Set) SetString(s string, set bool) {

a := strings.Split(s, ",", -1)

// going backwards as largest would be at the end
for k := len(a) - 1; k >= 0; k-- {
b := strings.Split(a[k], "-", -1)

i, _ := strconv.Atoi(b[0])

j := i

if len(b) == 2 {
j, _ = strconv.Atoi(b[1])
}

for ; j >= i; j-- {
x.SetInt(j, set)
}
}
}

func (x *Set) Set(s interface{}) {
switch i := s.(type) {
case int:
x.SetInt(i, true)
case string:
x.SetString(i, true)
default:
fmt.Printf("unknown type %T\n", i)
}
}

func (x *Set) Clear(s interface{}) {
switch i := s.(type) {
case int:
x.SetInt(i, false)
case string:
x.SetString(i, false)
}
}

func (x *Set) Do(f func(int)) {
for i, x0 := range *x {
for j := 0; j < BitOfWord; j++ {
if 1 << uint32(j) & x0 != 0 {
f( i << Shift + j)
}
}
}
}

func prn(i int){
print(i, ",")
}

func main() {
var x Set
x.Set(100) // int
x.Set("1-4,5,9-11") // range
x.Set(1<<30) // huge set
x.Set(1e6) // float not work
x.Do(prn)
}

Output:
new set 100
new set 1073741824
unknown type float
1,2,3,4,5,9,10,11,100,1073741824,

One thing I wish to remove is the clumsy uint32() conversion. Seems a
policy conflict here. On one hand is less typ(ing), on the other hand
is no implicit conversion. But Compiler knows exactly what to expect
for logic ops, why not treat it as is, without programmer explicit
telling it so? To me, too many times forget the conversion, and too
many time spent on coaxing Complier to accept what it knows already.
Can we do something here?

[Russ Cox]

On Tue, Aug 31, 2010 at 01:01, fango <fan.h...@gmail.com> wrote:
> One thing I wish to remove is the clumsy uint32() conversion. Seems a
> policy conflict here. On one hand is less typ(ing), on the other hand
> is no implicit conversion. But Compiler knows exactly what to expect
> for logic ops, why not treat it as is, without programmer explicit
> telling it so? To me, too many times forget the conversion, and too
> many time spent on coaxing Complier to accept what it knows already.
> Can we do something here?

Many of your conversions are not necessary. The program below
is still valid Go. The only required conversions here are the ones
that make the right operand of a shift unsigned. The compiler does
*not* know exactly what to expect for that case: did you mean
x<<-1 or x<<4294967295? Go forces you to make the operand
unsigned to avoid the ambiguity.

Russ

package main

import (
"fmt"
"strings"
"strconv"
)

const (
BitOfWord = 32
Shift = 5
Mask = 0x1F
)

type Set []uint32

func (x *Set) SetInt(i int, set bool) {

y := *x

l := i>>Shift + 1
if l > cap(y) {
println("new set", i)
x0 := make(Set, l)
copy(x0, y)
*x = x0

y = *x
}
if set {
y[i>>Shift] |= 1 << (uint(i) & Mask)
} else {
y[i>>Shift] &^= 1 << (uint(i) & Mask)
}
}

if x0&(1<<uint(j)) != 0 {
f(i<<Shift + j)

[fango]

--- 8x-----

The only required conversions here are the ones
that make the right operand of a shift unsigned. The compiler does
*not* know exactly what to expect for that case: did you mean
x<<-1 or x<<4294967295? Go forces you to make the operand
unsigned to avoid the ambiguity.

--- 8x-----

the uint32() of right shift is *exactly* the one I wish could be
removed.
From Spec: "The right operand in a shift operation must have unsigned
integer type or be an untyped constant that can be converted to
unsigned integer type."
So when i = -1 and <<unit32(i) does not help compiler to detect the
bug, does it?

On 8月31日, 下午7时53分, Russ Cox <r...@golang.org> wrote:

[Russ Cox]

> the uint32() of right shift is *exactly* the one I wish could be
> removed.
> From Spec: "The right operand in a shift operation must have unsigned
> integer type or be an untyped constant that can be converted to
> unsigned integer type."
> So when i = -1 and <<unit32(i) does not help compiler to detect the
> bug, does it?

no but it removes any doubt about whether it is a >>1.
the 32 is unnecessary: you can just say uint(i).

russ

[Eleanor McHugh]

Alternately Go could have a shift operator which determines direction automatically based upon the sign of the operand. That would be a little more natural when writing code that performs shifts at the expense of making the compiler work a little bit harder...

Ellie

Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
raise ArgumentError unless @reality.responds_to? :reason

[fango]

But to me uint for shift still feels like more typing...

I doubt any would write << -1 to mean >> 1

uint is inconvenient is because, for one, i := 0 is by default int,
not uint, so << i always need to bear the uint() shell. For two, the
right opr in a shift is such as small int, it cannot overflow and neg.
If it does overflow, it's a programmer's bug that compiler cannot help
even with uint() shell.

Limbo has no unsigned int or big and I think that won't cause much
problem.

Regards,
Fango

[ptolomy23]

Isn't the second operand of a shift necessarily a uint? The compiler isn't treating it as signed, so there is an implicit "uint()" there even if we don't put it there, so I'm happy to have to put it there to avoid secret casting and to remind me that negative values aren't going to go well for me. 

I think you're right that requiring a cast doesn't really help the compiler catch bugs, but I do think it helps me be more aware of  what the requirements are and helps me catch bugs. Others may be more careful and aware than me and not need such reminding.

[ptolomy23]

A slightly more complicated and perhaps more robust way of doing this

would be to use the "scanner" package. See http://ideone.com/wv6c8

However, I don't necessarily recommend this approach.

[fango]

A slightly optimization using big endian (msb first) so as to simply
test the sign bit, saving a & op. Also a early break of zero.

y[i>>Shift] |= 1 << (BitOfWord - 1 - (uint(i) & Mask))

and:

func (x *Set) Do(f func(int)) {
for i, x0 := range *x {
for j := 0; j < BitOfWord; j++ {

if x0 == 0 {
break
}
if int(x0) < 0 { // msb = 1

f( i << Shift + j)
}

x0 <<= 1
}
}
}

Now it's under http://ac-me.googlecode.com/files/set.go, served as an
example for type switch and conversion.

Thanks Russ for removing the unnecessary conversions.

Cheers,
Fango