Create a classic set for strings.

Create a classic set for strings.

I got sick of the map[string]bool fluffing around when wanting a set of
strings, so I wrote one.

https://code.launchpad.net/~thumper/juju-core/string-set/+merge/158530

(do not edit description out of merge proposal)

[thumper, 2013-04-12 05:20:37]

Please take a look.

[rog, 2013-04-12 06:27:12]

i think this the general idea is reasonable, but I have some suggestions below.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go
File utils/set/stringset.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode1
utils/set/stringset.go:1: package set
you actually haven't created a "utils" package, just a directory; i think that's
a good thing.

keeping the juju-core root name space uncluttered seems like a reasonable idea
though.

i suggest moving trivial to utils/trivial if we have set though.

other possible candidates for moving include cloudinit, upstart, schema, cert
and thirdparty (basically those packages which have no juju dependencies and
could be considered independent functionality)

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode9
utils/set/stringset.go:9: type StringSet struct {
if the package is "set", then "Strings" would be a better name, so you use
"set.Strings".

also, i'd prefer

type Strings map[string] bool

so to use it you'd do:

s := make(set.Strings)
etc


this means that the map-like nature of the set
is not hidden; then you can do all the normal map operations
on it, while adding others.

then i'd delete Size, Add, Remove and Contains.

i'll make the rest of my comments assuming the above changes.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode15
utils/set/stringset.go:15: func MakeStringSet(initial ...string) StringSet {
s/MakeStringSet/New/

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode24
utils/set/stringset.go:24: func (s *StringSet) Size() int {
d

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode29
utils/set/stringset.go:29: func (s *StringSet) Add(value string) {
d

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode38
utils/set/stringset.go:38: func (s *StringSet) Remove(value string) {
d

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode46
utils/set/stringset.go:46: func (s *StringSet) Contains(value string) bool {
d (and the if is redundant anyway)

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode76
utils/set/stringset.go:76: // Use the internal map rather than going through the
friendlier functions
i don't think these comments are particular useful.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode78
utils/set/stringset.go:78: for value, _ := range s.values {
s/, _//

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode81
utils/set/stringset.go:81: for value, _ := range other.values {
s/, _//

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode89
utils/set/stringset.go:89: func (s *StringSet) Intersection(other StringSet)
StringSet {
s/Intersection/Intersect/

?

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode103
utils/set/stringset.go:103: func (s *StringSet) Difference(other StringSet)
StringSet {
Difference sounds like a symmetric operation.
Without? Sub/Subtract? Minus?

[rog, 2013-04-12 06:53:28]

a few more comments

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go
File utils/set/stringset.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode15
utils/set/stringset.go:15: func MakeStringSet(initial ...string) StringSet {
On 2013/04/12 06:27:12, rog wrote:
> s/MakeStringSet/New/

actually, perhaps NewStrings would be better. we might add more set types to
this package.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode29
utils/set/stringset.go:29: func (s *StringSet) Add(value string) {
On 2013/04/12 06:27:12, rog wrote:
> d

seeing the way you've used it in the other CL, perhaps this should stay, even if
we're using a map type directly.

// Add puts a value into the set. It may
// be used even when the set is nil.
func (s *StringSet) Add(value string) {
    if s == nil {
         *s = make(StringSet)
    }
    s[value] = true
}

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode38
utils/set/stringset.go:38: func (s *StringSet) Remove(value string) {
On 2013/04/12 06:27:12, rog wrote:
> d

or (given that in go1.0.3 you can't delete from
a nil map):

// Remove removes a value from the set. If the value
// was not in the set to start with, it silently
// succeeds. It may be used even when the set is nil.
func (s Strings) Remove(value string) {
    if s == nil {
        return
    }
    delete(s, value)
}

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode55
utils/set/stringset.go:55: func (s *StringSet) Values() []string {
func (s Strings) Values() []string

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode58
utils/set/stringset.go:58: for key, _ := range s.values {
s/, _//

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode74
utils/set/stringset.go:74: func (s *StringSet) Union(other StringSet) StringSet
{
func (s Strings) Union(other Strings) Strings

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode89
utils/set/stringset.go:89: func (s *StringSet) Intersection(other StringSet)
StringSet {
func (s Strings) Intersect(other Strings) Strings

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go
File utils/set/stringset_test.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go#new...
utils/set/stringset_test.go:27: c.Assert(values, DeepEquals, expected)
i'd put
c.Assert(s.SortedValues(), DeepEquals, expected)

here and lose the AssertSortedValues method below.

[TheMue, 2013-04-12 07:09:39]

+1 one on most of Rogers comments, even if I would keep Add() etc if it is a map
as base type. 

Additionally I would like a Do(func (string)) and a Filter(fund (string) bool)
StringSet.

[rog, 2013-04-12 09:13:56]

On 12 April 2013 08:09, <themue@gmail.com> wrote:
>
> +1 one on most of Rogers comments, even if I would keep Add() etc if it
> is a map as base type.
>
> Additionally I would like a Do(func (string)) and a Filter(fund (string)
> bool) StringSet.

Do is:

for k := range myset { }

(except you can't break out of a Do)

Filter is:

for k := myset {
     if something {
         delete(myset, k)
    }
}

neither Do or Filter are worth it IMHO.

let's not layer our own stuff on top of things that the
language already does well.

[TheMue, 2013-04-12 09:25:02]

> Do is:
> 
> for k := range myset { }
> 
> (except you can't break out of a Do)
> 
> Filter is:
> 
> for k := myset {
>      if something {
>          delete(myset, k)
>     }
> }
> 
> neither Do or Filter are worth it IMHO.
> 
> let's not layer our own stuff on top of things that the
> language already does well.

Sure there are many ways, some are more, some are less elegant. But YMMW. Your
filter implementation wouldn't by the way mine working on the set itself. I had
a more functional approach in mind creating a new set based on the filtered
values. Also when those operations are defined in an interface the
implementation may vary, e.g. to sets (or other structures) larger than memory,
e.g. in database.

But right now you're right, YAGNI, so lets throw away those thoughts. ;)

[fwereade, 2013-04-12 15:12:39]

This LGTM. I'm not sure what we get out of inventing our own quasi-set -- rog,
would you expand on your objections please?

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go
File utils/set/stringset.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode9
utils/set/stringset.go:9: type StringSet struct {
On 2013/04/12 06:27:12, rog wrote:
> this means that the map-like nature of the set
> is not hidden; then you can do all the normal map operations
> on it, while adding others.
> 
> then i'd delete Size, Add, Remove and Contains.

...and what you end up with is not a set, but a kinda half-map with
magnificently leaky abstractions. If there are serious conceptual problems with
the standard set abstraction, let's hear 'em; but most of these suggestions seem
like change for its own sake...

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode15
utils/set/stringset.go:15: func MakeStringSet(initial ...string) StringSet {
On 2013/04/12 06:27:12, rog wrote:
> s/MakeStringSet/New/

Make echoes the referenciness quite well, I think.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode76
utils/set/stringset.go:76: // Use the internal map rather than going through the
friendlier functions
On 2013/04/12 06:27:12, rog wrote:
> i don't think these comments are particular useful.

They methods stand pretty well on their own; but the comments offer a clear
explanation of why a not-necessarily-obvious choice was made. I'd prefer to keep
them, I think.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode89
utils/set/stringset.go:89: func (s *StringSet) Intersection(other StringSet)
StringSet {
On 2013/04/12 06:53:28, rog wrote:
> func (s Strings) Intersect(other Strings) Strings

Why change the common vocabulary?

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode103
utils/set/stringset.go:103: func (s *StringSet) Difference(other StringSet)
StringSet {
On 2013/04/12 06:27:12, rog wrote:
> Difference sounds like a symmetric operation.
> Without? Sub/Subtract? Minus?

Difference is a perfectly cromulent set operation.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go
File utils/set/stringset_test.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go#new...
utils/set/stringset_test.go:88: func (stringSetSuite) TestRemoveNonExistant(c
*C) {
Existent

[rog, 2013-04-12 16:10:33]

On 12 April 2013 16:12,  <fwereade@gmail.com> wrote:
> This LGTM. I'm not sure what we get out of inventing our own quasi-set
> -- rog, would you expand on your objections please?

I think that we gain more from adding a few useful operations
on top of an existing type with good existing primitives
than by hiding everything away as if we might change
the representation some day (it's not hard even if we do).

I'm thinking of http://golang.org/pkg/net/url/#Values when I say
this. It works well, and to be honest, I don't think the abstractions
are that leaky - a map[string] bool is a very reasonable representation
of a set.

I much prefer to be able to use the language built-in operations
when reasonable. The value added from this package comes IMHO
from the actual set operations - the rest is unnecessary abstraction.

The other nice thing about defining it directly as a map is it becomes
compatible with other places that happen to use a map[string]bool.

Also iteration by copying the whole set or by requiring a function-based
iterator seems like a step backwards.

[rog, 2013-04-12 16:26:28]

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go
File utils/set/stringset.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode15
utils/set/stringset.go:15: func MakeStringSet(initial ...string) StringSet {
On 2013/04/12 15:12:39, fwereade wrote:
> On 2013/04/12 06:27:12, rog wrote:
> > s/MakeStringSet/New/
> 
> Make echoes the referenciness quite well, I think.

NewX is a standard name for a constructor of an X. I don't see how this is any
different.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode29
utils/set/stringset.go:29: func (s *StringSet) Add(value string) {
On 2013/04/12 06:53:28, rog wrote:
> On 2013/04/12 06:27:12, rog wrote:
> > d
> 
> seeing the way you've used it in the other CL, perhaps this should stay, even
if
> we're using a map type directly.
> 
> // Add puts a value into the set. It may
> // be used even when the set is nil.
> func (s *StringSet) Add(value string) {
>     if s == nil {

this is of course bogus.
i meant if *s == nil.

>          *s = make(StringSet)
>     }
>     s[value] = true
> }

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode76
utils/set/stringset.go:76: // Use the internal map rather than going through the
friendlier functions
On 2013/04/12 15:12:39, fwereade wrote:
> On 2013/04/12 06:27:12, rog wrote:
> > i don't think these comments are particular useful.
> 
> They methods stand pretty well on their own; but the comments offer a clear
> explanation of why a not-necessarily-obvious choice was made. I'd prefer to
keep
> them, I think.

they also show why it's an abstraction too far. why should we deny normal code
the ability to iterate quickly over a set without producing garbage?

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode103
utils/set/stringset.go:103: func (s *StringSet) Difference(other StringSet)
StringSet {
On 2013/04/12 15:12:39, fwereade wrote:
> On 2013/04/12 06:27:12, rog wrote:
> > Difference sounds like a symmetric operation.
> > Without? Sub/Subtract? Minus?
> 
> Difference is a perfectly cromulent set operation.

it's a fine operation, but to me it sounds like
"what's the difference between a and b?" in the
sense of diff(1)) not "what does a have that b does not?".

[dave_cheney.net, 2013-04-12 23:43:09]

not lgtm.

The only thing worse than having 1 utils package (trivial) is having two, the
latter heavily namespaced.

I have no objection to stringset or its friends, just make one package,
launchpad.net/juju-core/utils and move it in there, and trivial/*.go for good
measure.

[thumper, 2013-04-14 22:08:24]

On 2013/04/12 23:43:09, dfc wrote:
> not lgtm.
> 
> The only thing worse than having 1 utils package (trivial) is having two, the
> latter heavily namespaced.
> 
> I have no objection to stringset or its friends, just make one package,
> launchpad.net/juju-core/utils and move it in there, and trivial/*.go for good
> measure.

I'm proposing a separate branch that just does the trivial -> utils change.

[thumper, 2013-04-14 22:45:28]

Please take a look.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go
File utils/set/stringset.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode9
utils/set/stringset.go:9: type StringSet struct {
On 2013/04/12 06:27:12, rog wrote:
> if the package is "set", then "Strings" would be a better name, so you use
> "set.Strings".
> 
> also, i'd prefer
> 
> type Strings map[string] bool
> 
> so to use it you'd do:
> 
> s := make(set.Strings)
> etc
> 
> 
> this means that the map-like nature of the set
> is not hidden; then you can do all the normal map operations
> on it, while adding others.
> 
> then i'd delete Size, Add, Remove and Contains.
> 
> i'll make the rest of my comments assuming the above changes.

Actually I did briefly consider this and discarded it.  The purpose of the
opaque type is to hide the data, not make it available.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode76
utils/set/stringset.go:76: // Use the internal map rather than going through the
friendlier functions
On 2013/04/12 16:26:29, rog wrote:
> On 2013/04/12 15:12:39, fwereade wrote:
> > On 2013/04/12 06:27:12, rog wrote:
> > > i don't think these comments are particular useful.
> > 
> > They methods stand pretty well on their own; but the comments offer a clear
> > explanation of why a not-necessarily-obvious choice was made. I'd prefer to
> keep
> > them, I think.
> 
> they also show why it's an abstraction too far. why should we deny normal code
> the ability to iterate quickly over a set without producing garbage?

What it shows is that the internal representation is currently a map, but it may
as well be something else, like a red/black tree, but for speed, I just
implemented it using the map.  Not ideal, but faster.  Given the information
hiding though, it would be possible to swap out the implementation without
impacting anyone.  Yet another reason to use an opaque type and not a map type.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset.go#newcode89
utils/set/stringset.go:89: func (s *StringSet) Intersection(other StringSet)
StringSet {
On 2013/04/12 15:12:39, fwereade wrote:
> On 2013/04/12 06:53:28, rog wrote:
> > func (s Strings) Intersect(other Strings) Strings
> 
> Why change the common vocabulary?

union, intersection, and difference are all well know, and understood, set
operations.  Python sets have these exact method names as well, and this adds
consistency and familiarity around dealing with sets.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go
File utils/set/stringset_test.go (right):

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go#new...
utils/set/stringset_test.go:27: c.Assert(values, DeepEquals, expected)
On 2013/04/12 06:53:28, rog wrote:
> i'd put
> c.Assert(s.SortedValues(), DeepEquals, expected)
> 
> here and lose the AssertSortedValues method below.

Done.

https://codereview.appspot.com/8672044/diff/1/utils/set/stringset_test.go#new...
utils/set/stringset_test.go:88: func (stringSetSuite) TestRemoveNonExistant(c
*C) {
On 2013/04/12 15:12:39, fwereade wrote:
> Existent

Done.

[dave_cheney.net, 2013-04-14 23:14:39]

On 2013/04/14 22:08:24, thumper wrote:
> On 2013/04/12 23:43:09, dfc wrote:
> > not lgtm.
> > 
> > The only thing worse than having 1 utils package (trivial) is having two,
the
> > latter heavily namespaced.
> > 
> > I have no objection to stringset or its friends, just make one package,
> > launchpad.net/juju-core/utils and move it in there, and trivial/*.go for
good
> > measure.
> 
> I'm proposing a separate branch that just does the trivial -> utils change.

Ok, but you have placed this code in utils/set. I would like to see it in
launchpad.net/juju-core/utils.

[dave_cheney.net, 2013-04-14 23:42:13]

LGTM. I can't give a crap about namespace bikeshedding.

[thumper, 2013-04-14 23:49:46]

*** Submitted:

Create a classic set for strings.

I got sick of the map[string]bool fluffing around when wanting a set of
strings, so I wrote one.

R=rog, TheMue, fwereade, dfc
CC=
https://codereview.appspot.com/8672044

[rog, 2013-04-15 10:42:50]

On 14 April 2013 23:45,  <tim.penhey@canonical.com> wrote:
> Actually I did briefly consider this and discarded it.  The purpose of
> the opaque type is to hide the data, not make it available.

YAGNI. a map is already an opaque type - there's all kinds of magic
buried beneath.
i don't believe there's any value in making this an opaque type.

BTW we should really have a way of iterating over this type without
copying all its items into a new slice.