diff options
author | Taylor Gerring <taylor.gerring@gmail.com> | 2015-02-16 21:28:33 +0800 |
---|---|---|
committer | Taylor Gerring <taylor.gerring@gmail.com> | 2015-02-16 21:28:33 +0800 |
commit | 702218008ee2b6d708d6b2821cdef80736bb3224 (patch) | |
tree | d55ff7ce88187082378e7d8e4c2f3aad14d23b4e /Godeps/_workspace/src/gopkg.in/fatih | |
parent | 202362d9258335c695eb75f55f4be74a50a1af33 (diff) | |
download | go-tangerine-702218008ee2b6d708d6b2821cdef80736bb3224.tar.gz go-tangerine-702218008ee2b6d708d6b2821cdef80736bb3224.tar.zst go-tangerine-702218008ee2b6d708d6b2821cdef80736bb3224.zip |
Add versioned dependencies from godep
Diffstat (limited to 'Godeps/_workspace/src/gopkg.in/fatih')
9 files changed, 1575 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/.travis.yml b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/.travis.yml new file mode 100644 index 000000000..b05e4c53f --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/.travis.yml @@ -0,0 +1,3 @@ +language: go +go: 1.2 + diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/LICENSE.md b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/LICENSE.md new file mode 100644 index 000000000..25fdaf639 --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/LICENSE.md @@ -0,0 +1,20 @@ +The MIT License (MIT) + +Copyright (c) 2013 Fatih Arslan + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software is furnished to do so, +subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS +FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR +COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER +IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/README.md b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/README.md new file mode 100644 index 000000000..23afdd98d --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/README.md @@ -0,0 +1,245 @@ +# Set [![GoDoc](http://img.shields.io/badge/go-documentation-blue.svg?style=flat-square)](https://godoc.org/gopkg.in/fatih/set.v0) [![Build Status](http://img.shields.io/travis/fatih/set.svg?style=flat-square)](https://travis-ci.org/fatih/set) + +Set is a basic and simple, hash-based, **Set** data structure implementation +in Go (Golang). + +Set provides both threadsafe and non-threadsafe implementations of a generic +set data structure. The thread safety encompasses all operations on one set. +Operations on multiple sets are consistent in that the elements of each set +used was valid at exactly one point in time between the start and the end of +the operation. Because it's thread safe, you can use it concurrently with your +goroutines. + +For usage see examples below or click on the godoc badge. + +## Install and Usage + +Install the package with: + +```bash +go get gopkg.in/fatih/set.v0 +``` + +Import it with: + +```go +import "gopkg.in/fatih/set.v0" +``` + +and use `set` as the package name inside the code. + +## Examples + +#### Initialization of a new Set + +```go + +// create a set with zero items +s := set.New() +s := set.NewNonTS() // non thread-safe version + +// ... or with some initial values +s := set.New("istanbul", "frankfurt", 30.123, "san francisco", 1234) +s := set.NewNonTS("kenya", "ethiopia", "sumatra") + +``` + +#### Basic Operations + +```go +// add items +s.Add("istanbul") +s.Add("istanbul") // nothing happens if you add duplicate item + +// add multiple items +s.Add("ankara", "san francisco", 3.14) + +// remove item +s.Remove("frankfurt") +s.Remove("frankfurt") // nothing happes if you remove a nonexisting item + +// remove multiple items +s.Remove("barcelona", 3.14, "ankara") + +// removes an arbitary item and return it +item := s.Pop() + +// create a new copy +other := s.Copy() + +// remove all items +s.Clear() + +// number of items in the set +len := s.Size() + +// return a list of items +items := s.List() + +// string representation of set +fmt.Printf("set is %s", s.String()) + +``` + +#### Check Operations + +```go +// check for set emptiness, returns true if set is empty +s.IsEmpty() + +// check for a single item exist +s.Has("istanbul") + +// ... or for multiple items. This will return true if all of the items exist. +s.Has("istanbul", "san francisco", 3.14) + +// create two sets for the following checks... +s := s.New("1", "2", "3", "4", "5") +t := s.New("1", "2", "3") + + +// check if they are the same +if !s.IsEqual(t) { + fmt.Println("s is not equal to t") +} + +// if s contains all elements of t +if s.IsSubset(t) { + fmt.Println("t is a subset of s") +} + +// ... or if s is a superset of t +if t.IsSuperset(s) { + fmt.Println("s is a superset of t") +} + + +``` + +#### Set Operations + + +```go +// let us initialize two sets with some values +a := set.New("ankara", "berlin", "san francisco") +b := set.New("frankfurt", "berlin") + +// creates a new set with the items in a and b combined. +// [frankfurt, berlin, ankara, san francisco] +c := set.Union(a, b) + +// contains items which is in both a and b +// [berlin] +c := set.Intersection(a, b) + +// contains items which are in a but not in b +// [ankara, san francisco] +c := set.Difference(a, b) + +// contains items which are in one of either, but not in both. +// [frankfurt, ankara, san francisco] +c := set.SymmetricDifference(a, b) + +``` + +```go +// like Union but saves the result back into a. +a.Merge(b) + +// removes the set items which are in b from a and saves the result back into a. +a.Separate(b) + +``` + +#### Multiple Set Operations + +```go +a := set.New("1", "3", "4", "5") +b := set.New("2", "3", "4", "5") +c := set.New("4", "5", "6", "7") + +// creates a new set with items in a, b and c +// [1 2 3 4 5 6 7] +u := set.Union(a, b, c) + +// creates a new set with items in a but not in b and c +// [1] +u := set.Difference(a, b, c) + +// creates a new set with items that are common to a, b and c +// [5] +u := set.Intersection(a, b, c) +``` + +#### Helper methods + +The Slice functions below are a convenient way to extract or convert your Set data +into basic data types. + + +```go +// create a set of mixed types +s := set.New("ankara", "5", "8", "san francisco", 13, 21) + + +// convert s into a slice of strings (type is []string) +// [ankara 5 8 san francisco] +t := set.StringSlice(s) + + +// u contains a slice of ints (type is []int) +// [13, 21] +u := set.IntSlice(s) + +``` + +#### Concurrent safe usage + +Below is an example of a concurrent way that uses set. We call ten functions +concurrently and wait until they are finished. It basically creates a new +string for each goroutine and adds it to our set. + +```go +package main + +import ( + "fmt" + "github.com/fatih/set" + "strconv" + "sync" +) + +func main() { + var wg sync.WaitGroup // this is just for waiting until all goroutines finish + + // Initialize our thread safe Set + s := set.New() + + // Add items concurrently (item1, item2, and so on) + for i := 0; i < 10; i++ { + wg.Add(1) + go func(i int) { + item := "item" + strconv.Itoa(i) + fmt.Println("adding", item) + s.Add(item) + wg.Done() + }(i) + } + + // Wait until all concurrent calls finished and print our set + wg.Wait() + fmt.Println(s) +} +``` + +## Credits + + * [Fatih Arslan](https://github.com/fatih) + * [Arne Hormann](https://github.com/arnehormann) + * [Sam Boyer](https://github.com/sdboyer) + * [Ralph Loizzo](https://github.com/friartech) + +## License + +The MIT License (MIT) - see LICENSE.md for more details + diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set.go new file mode 100644 index 000000000..ac0240ce7 --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set.go @@ -0,0 +1,121 @@ +// Package set provides both threadsafe and non-threadsafe implementations of +// a generic set data structure. In the threadsafe set, safety encompasses all +// operations on one set. Operations on multiple sets are consistent in that +// the elements of each set used was valid at exactly one point in time +// between the start and the end of the operation. +package set + +// Interface is describing a Set. Sets are an unordered, unique list of values. +type Interface interface { + New(items ...interface{}) Interface + Add(items ...interface{}) + Remove(items ...interface{}) + Pop() interface{} + Has(items ...interface{}) bool + Size() int + Clear() + IsEmpty() bool + IsEqual(s Interface) bool + IsSubset(s Interface) bool + IsSuperset(s Interface) bool + Each(func(interface{}) bool) + String() string + List() []interface{} + Copy() Interface + Merge(s Interface) + Separate(s Interface) +} + +// helpful to not write everywhere struct{}{} +var keyExists = struct{}{} + +// Union is the merger of multiple sets. It returns a new set with all the +// elements present in all the sets that are passed. +// +// The dynamic type of the returned set is determined by the first passed set's +// implementation of the New() method. +func Union(set1, set2 Interface, sets ...Interface) Interface { + u := set1.Copy() + set2.Each(func(item interface{}) bool { + u.Add(item) + return true + }) + for _, set := range sets { + set.Each(func(item interface{}) bool { + u.Add(item) + return true + }) + } + + return u +} + +// Difference returns a new set which contains items which are in in the first +// set but not in the others. Unlike the Difference() method you can use this +// function separately with multiple sets. +func Difference(set1, set2 Interface, sets ...Interface) Interface { + s := set1.Copy() + s.Separate(set2) + for _, set := range sets { + s.Separate(set) // seperate is thread safe + } + return s +} + +// Intersection returns a new set which contains items that only exist in all given sets. +func Intersection(set1, set2 Interface, sets ...Interface) Interface { + all := Union(set1, set2, sets...) + result := Union(set1, set2, sets...) + + all.Each(func(item interface{}) bool { + if !set1.Has(item) || !set2.Has(item) { + result.Remove(item) + } + + for _, set := range sets { + if !set.Has(item) { + result.Remove(item) + } + } + return true + }) + return result +} + +// SymmetricDifference returns a new set which s is the difference of items which are in +// one of either, but not in both. +func SymmetricDifference(s Interface, t Interface) Interface { + u := Difference(s, t) + v := Difference(t, s) + return Union(u, v) +} + +// StringSlice is a helper function that returns a slice of strings of s. If +// the set contains mixed types of items only items of type string are returned. +func StringSlice(s Interface) []string { + slice := make([]string, 0) + for _, item := range s.List() { + v, ok := item.(string) + if !ok { + continue + } + + slice = append(slice, v) + } + return slice +} + +// IntSlice is a helper function that returns a slice of ints of s. If +// the set contains mixed types of items only items of type int are returned. +func IntSlice(s Interface) []int { + slice := make([]int, 0) + for _, item := range s.List() { + v, ok := item.(int) + if !ok { + continue + } + + slice = append(slice, v) + } + return slice +} diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots.go new file mode 100644 index 000000000..ec1ab2285 --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots.go @@ -0,0 +1,195 @@ +package set + +import ( + "fmt" + "strings" +) + +// Provides a common set baseline for both threadsafe and non-ts Sets. +type set struct { + m map[interface{}]struct{} // struct{} doesn't take up space +} + +// SetNonTS defines a non-thread safe set data structure. +type SetNonTS struct { + set +} + +// NewNonTS creates and initialize a new non-threadsafe Set. +// It accepts a variable number of arguments to populate the initial set. +// If nothing is passed a SetNonTS with zero size is created. +func NewNonTS(items ...interface{}) *SetNonTS { + s := &SetNonTS{} + s.m = make(map[interface{}]struct{}) + + // Ensure interface compliance + var _ Interface = s + + s.Add(items...) + return s +} + +// New creates and initalizes a new Set interface. It accepts a variable +// number of arguments to populate the initial set. If nothing is passed a +// zero size Set based on the struct is created. +func (s *set) New(items ...interface{}) Interface { + return NewNonTS(items...) +} + +// Add includes the specified items (one or more) to the set. The underlying +// Set s is modified. If passed nothing it silently returns. +func (s *set) Add(items ...interface{}) { + if len(items) == 0 { + return + } + + for _, item := range items { + s.m[item] = keyExists + } +} + +// Remove deletes the specified items from the set. The underlying Set s is +// modified. If passed nothing it silently returns. +func (s *set) Remove(items ...interface{}) { + if len(items) == 0 { + return + } + + for _, item := range items { + delete(s.m, item) + } +} + +// Pop deletes and return an item from the set. The underlying Set s is +// modified. If set is empty, nil is returned. +func (s *set) Pop() interface{} { + for item := range s.m { + delete(s.m, item) + return item + } + return nil +} + +// Has looks for the existence of items passed. It returns false if nothing is +// passed. For multiple items it returns true only if all of the items exist. +func (s *set) Has(items ...interface{}) bool { + // assume checked for empty item, which not exist + if len(items) == 0 { + return false + } + + has := true + for _, item := range items { + if _, has = s.m[item]; !has { + break + } + } + return has +} + +// Size returns the number of items in a set. +func (s *set) Size() int { + return len(s.m) +} + +// Clear removes all items from the set. +func (s *set) Clear() { + s.m = make(map[interface{}]struct{}) +} + +// IsEmpty reports whether the Set is empty. +func (s *set) IsEmpty() bool { + return s.Size() == 0 +} + +// IsEqual test whether s and t are the same in size and have the same items. +func (s *set) IsEqual(t Interface) bool { + // Force locking only if given set is threadsafe. + if conv, ok := t.(*Set); ok { + conv.l.RLock() + defer conv.l.RUnlock() + } + + // return false if they are no the same size + if sameSize := len(s.m) == t.Size(); !sameSize { + return false + } + + equal := true + t.Each(func(item interface{}) bool { + _, equal = s.m[item] + return equal // if false, Each() will end + }) + + return equal +} + +// IsSubset tests whether t is a subset of s. +func (s *set) IsSubset(t Interface) (subset bool) { + subset = true + + t.Each(func(item interface{}) bool { + _, subset = s.m[item] + return subset + }) + + return +} + +// IsSuperset tests whether t is a superset of s. +func (s *set) IsSuperset(t Interface) bool { + return t.IsSubset(s) +} + +// Each traverses the items in the Set, calling the provided function for each +// set member. Traversal will continue until all items in the Set have been +// visited, or if the closure returns false. +func (s *set) Each(f func(item interface{}) bool) { + for item := range s.m { + if !f(item) { + break + } + } +} + +// String returns a string representation of s +func (s *set) String() string { + t := make([]string, 0, len(s.List())) + for _, item := range s.List() { + t = append(t, fmt.Sprintf("%v", item)) + } + + return fmt.Sprintf("[%s]", strings.Join(t, ", ")) +} + +// List returns a slice of all items. There is also StringSlice() and +// IntSlice() methods for returning slices of type string or int. +func (s *set) List() []interface{} { + list := make([]interface{}, 0, len(s.m)) + + for item := range s.m { + list = append(list, item) + } + + return list +} + +// Copy returns a new Set with a copy of s. +func (s *set) Copy() Interface { + return NewNonTS(s.List()...) +} + +// Merge is like Union, however it modifies the current set it's applied on +// with the given t set. +func (s *set) Merge(t Interface) { + t.Each(func(item interface{}) bool { + s.m[item] = keyExists + return true + }) +} + +// it's not the opposite of Merge. +// Separate removes the set items containing in t from set s. Please aware that +func (s *set) Separate(t Interface) { + s.Remove(t.List()...) +} diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots_test.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots_test.go new file mode 100644 index 000000000..fd599699f --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_nots_test.go @@ -0,0 +1,282 @@ +package set + +import ( + "reflect" + "strings" + "testing" +) + +func TestSetNonTS_NewNonTS_parameters(t *testing.T) { + s := NewNonTS("string", "another_string", 1, 3.14) + + if s.Size() != 4 { + t.Error("NewNonTS: calling with parameters should create a set with size of four") + } +} + +func TestSetNonTS_Add(t *testing.T) { + s := NewNonTS() + s.Add(1) + s.Add(2) + s.Add(2) // duplicate + s.Add("fatih") + s.Add("zeynep") + s.Add("zeynep") // another duplicate + + if s.Size() != 4 { + t.Error("Add: items are not unique. The set size should be four") + } + + if !s.Has(1, 2, "fatih", "zeynep") { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSetNonTS_Add_multiple(t *testing.T) { + s := NewNonTS() + s.Add("ankara", "san francisco", 3.14) + + if s.Size() != 3 { + t.Error("Add: items are not unique. The set size should be three") + } + + if !s.Has("ankara", "san francisco", 3.14) { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSetNonTS_Remove(t *testing.T) { + s := NewNonTS() + s.Add(1) + s.Add(2) + s.Add("fatih") + + s.Remove(1) + if s.Size() != 2 { + t.Error("Remove: set size should be two after removing") + } + + s.Remove(1) + if s.Size() != 2 { + t.Error("Remove: set size should be not change after trying to remove a non-existing item") + } + + s.Remove(2) + s.Remove("fatih") + if s.Size() != 0 { + t.Error("Remove: set size should be zero") + } + + s.Remove("fatih") // try to remove something from a zero length set +} + +func TestSetNonTS_Remove_multiple(t *testing.T) { + s := NewNonTS() + s.Add("ankara", "san francisco", 3.14, "istanbul") + s.Remove("ankara", "san francisco", 3.14) + + if s.Size() != 1 { + t.Error("Remove: items are not unique. The set size should be four") + } + + if !s.Has("istanbul") { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSetNonTS_Pop(t *testing.T) { + s := NewNonTS() + s.Add(1) + s.Add(2) + s.Add("fatih") + + a := s.Pop() + if s.Size() != 2 { + t.Error("Pop: set size should be two after popping out") + } + + if s.Has(a) { + t.Error("Pop: returned item should not exist") + } + + s.Pop() + s.Pop() + b := s.Pop() + if b != nil { + t.Error("Pop: should return nil because set is empty") + } + + s.Pop() // try to remove something from a zero length set +} + +func TestSetNonTS_Has(t *testing.T) { + s := NewNonTS("1", "2", "3", "4") + + if !s.Has("1") { + t.Error("Has: the item 1 exist, but 'Has' is returning false") + } + + if !s.Has("1", "2", "3", "4") { + t.Error("Has: the items all exist, but 'Has' is returning false") + } +} + +func TestSetNonTS_Clear(t *testing.T) { + s := NewNonTS() + s.Add(1) + s.Add("istanbul") + s.Add("san francisco") + + s.Clear() + if s.Size() != 0 { + t.Error("Clear: set size should be zero") + } +} + +func TestSetNonTS_IsEmpty(t *testing.T) { + s := NewNonTS() + + empty := s.IsEmpty() + if !empty { + t.Error("IsEmpty: set is empty, it should be true") + } + + s.Add(2) + s.Add(3) + notEmpty := s.IsEmpty() + + if notEmpty { + t.Error("IsEmpty: set is filled, it should be false") + } +} + +func TestSetNonTS_IsEqual(t *testing.T) { + s := NewNonTS("1", "2", "3") + u := NewNonTS("1", "2", "3") + + ok := s.IsEqual(u) + if !ok { + t.Error("IsEqual: set s and t are equal. However it returns false") + } + + // same size, different content + a := NewNonTS("1", "2", "3") + b := NewNonTS("4", "5", "6") + + ok = a.IsEqual(b) + if ok { + t.Error("IsEqual: set a and b are now equal (1). However it returns true") + } + + // different size, similar content + a = NewNonTS("1", "2", "3") + b = NewNonTS("1", "2", "3", "4") + + ok = a.IsEqual(b) + if ok { + t.Error("IsEqual: set s and t are now equal (2). However it returns true") + } + +} + +func TestSetNonTS_IsSubset(t *testing.T) { + s := NewNonTS("1", "2", "3", "4") + u := NewNonTS("1", "2", "3") + + ok := s.IsSubset(u) + if !ok { + t.Error("IsSubset: u is a subset of s. However it returns false") + } + + ok = u.IsSubset(s) + if ok { + t.Error("IsSubset: s is not a subset of u. However it returns true") + } + +} + +func TestSetNonTS_IsSuperset(t *testing.T) { + s := NewNonTS("1", "2", "3", "4") + u := NewNonTS("1", "2", "3") + + ok := u.IsSuperset(s) + if !ok { + t.Error("IsSuperset: s is a superset of u. However it returns false") + } + + ok = s.IsSuperset(u) + if ok { + t.Error("IsSuperset: u is not a superset of u. However it returns true") + } + +} + +func TestSetNonTS_String(t *testing.T) { + s := NewNonTS() + if s.String() != "[]" { + t.Errorf("String: output is not what is excepted '%s'", s.String()) + } + + s.Add("1", "2", "3", "4") + if !strings.HasPrefix(s.String(), "[") { + t.Error("String: output should begin with a square bracket") + } + + if !strings.HasSuffix(s.String(), "]") { + t.Error("String: output should end with a square bracket") + } + +} + +func TestSetNonTS_List(t *testing.T) { + s := NewNonTS("1", "2", "3", "4") + + // this returns a slice of interface{} + if len(s.List()) != 4 { + t.Error("List: slice size should be four.") + } + + for _, item := range s.List() { + r := reflect.TypeOf(item) + if r.Kind().String() != "string" { + t.Error("List: slice item should be a string") + } + } +} + +func TestSetNonTS_Copy(t *testing.T) { + s := NewNonTS("1", "2", "3", "4") + r := s.Copy() + + if !s.IsEqual(r) { + t.Error("Copy: set s and r are not equal") + } +} + +func TestSetNonTS_Merge(t *testing.T) { + s := NewNonTS("1", "2", "3") + r := NewNonTS("3", "4", "5") + s.Merge(r) + + if s.Size() != 5 { + t.Error("Merge: the set doesn't have all items in it.") + } + + if !s.Has("1", "2", "3", "4", "5") { + t.Error("Merge: merged items are not availabile in the set.") + } +} + +func TestSetNonTS_Separate(t *testing.T) { + s := NewNonTS("1", "2", "3") + r := NewNonTS("3", "5") + s.Separate(r) + + if s.Size() != 2 { + t.Error("Separate: the set doesn't have all items in it.") + } + + if !s.Has("1", "2") { + t.Error("Separate: items after separation are not availabile in the set.") + } +} diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_test.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_test.go new file mode 100644 index 000000000..83dd5806d --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_test.go @@ -0,0 +1,188 @@ +package set + +import ( + "reflect" + "testing" +) + +func Test_Union(t *testing.T) { + s := New("1", "2", "3") + r := New("3", "4", "5") + x := NewNonTS("5", "6", "7") + + u := Union(s, r, x) + if settype := reflect.TypeOf(u).String(); settype != "*set.Set" { + t.Error("Union should derive its set type from the first passed set, got", settype) + } + if u.Size() != 7 { + t.Error("Union: the merged set doesn't have all items in it.") + } + + if !u.Has("1", "2", "3", "4", "5", "6", "7") { + t.Error("Union: merged items are not availabile in the set.") + } + + z := Union(x, r) + if z.Size() != 5 { + t.Error("Union: Union of 2 sets doesn't have the proper number of items.") + } + if settype := reflect.TypeOf(z).String(); settype != "*set.SetNonTS" { + t.Error("Union should derive its set type from the first passed set, got", settype) + } + +} + +func Test_Difference(t *testing.T) { + s := New("1", "2", "3") + r := New("3", "4", "5") + x := New("5", "6", "7") + u := Difference(s, r, x) + + if u.Size() != 2 { + t.Error("Difference: the set doesn't have all items in it.") + } + + if !u.Has("1", "2") { + t.Error("Difference: items are not availabile in the set.") + } + + y := Difference(r, r) + if y.Size() != 0 { + t.Error("Difference: size should be zero") + } + +} + +func Test_Intersection(t *testing.T) { + s1 := New("1", "3", "4", "5") + s2 := New("2", "3", "5", "6") + s3 := New("4", "5", "6", "7") + u := Intersection(s1, s2, s3) + + if u.Size() != 1 { + t.Error("Intersection: the set doesn't have all items in it.") + } + + if !u.Has("5") { + t.Error("Intersection: items after intersection are not availabile in the set.") + } +} + +func Test_SymmetricDifference(t *testing.T) { + s := New("1", "2", "3") + r := New("3", "4", "5") + u := SymmetricDifference(s, r) + + if u.Size() != 4 { + t.Error("SymmetricDifference: the set doesn't have all items in it.") + } + + if !u.Has("1", "2", "4", "5") { + t.Error("SymmetricDifference: items are not availabile in the set.") + } +} + +func Test_StringSlice(t *testing.T) { + s := New("san francisco", "istanbul", 3.14, 1321, "ankara") + u := StringSlice(s) + + if len(u) != 3 { + t.Error("StringSlice: slice should only have three items") + } + + for _, item := range u { + r := reflect.TypeOf(item) + if r.Kind().String() != "string" { + t.Error("StringSlice: slice item should be a string") + } + } +} + +func Test_IntSlice(t *testing.T) { + s := New("san francisco", "istanbul", 3.14, 1321, "ankara", 8876) + u := IntSlice(s) + + if len(u) != 2 { + t.Error("IntSlice: slice should only have two items") + } + + for _, item := range u { + r := reflect.TypeOf(item) + if r.Kind().String() != "int" { + t.Error("Intslice: slice item should be a int") + } + } +} + +func BenchmarkSetEquality(b *testing.B) { + s := New() + u := New() + + for i := 0; i < b.N; i++ { + s.Add(i) + u.Add(i) + } + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + s.IsEqual(u) + } +} + +func BenchmarkSubset(b *testing.B) { + s := New() + u := New() + + for i := 0; i < b.N; i++ { + s.Add(i) + u.Add(i) + } + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + s.IsSubset(u) + } +} + +func benchmarkIntersection(b *testing.B, numberOfItems int) { + s1 := New() + s2 := New() + + for i := 0; i < numberOfItems/2; i++ { + s1.Add(i) + } + for i := 0; i < numberOfItems; i++ { + s2.Add(i) + } + + b.ResetTimer() + for i := 0; i < b.N; i++ { + Intersection(s1, s2) + } +} + +func BenchmarkIntersection10(b *testing.B) { + benchmarkIntersection(b, 10) +} + +func BenchmarkIntersection100(b *testing.B) { + benchmarkIntersection(b, 100) +} + +func BenchmarkIntersection1000(b *testing.B) { + benchmarkIntersection(b, 1000) +} + +func BenchmarkIntersection10000(b *testing.B) { + benchmarkIntersection(b, 10000) +} + +func BenchmarkIntersection100000(b *testing.B) { + benchmarkIntersection(b, 100000) +} + +func BenchmarkIntersection1000000(b *testing.B) { + benchmarkIntersection(b, 1000000) +} diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts.go new file mode 100644 index 000000000..50f532565 --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts.go @@ -0,0 +1,200 @@ +package set + +import ( + "sync" +) + +// Set defines a thread safe set data structure. +type Set struct { + set + l sync.RWMutex // we name it because we don't want to expose it +} + +// New creates and initialize a new Set. It's accept a variable number of +// arguments to populate the initial set. If nothing passed a Set with zero +// size is created. +func New(items ...interface{}) *Set { + s := &Set{} + s.m = make(map[interface{}]struct{}) + + // Ensure interface compliance + var _ Interface = s + + s.Add(items...) + return s +} + +// New creates and initalizes a new Set interface. It accepts a variable +// number of arguments to populate the initial set. If nothing is passed a +// zero size Set based on the struct is created. +func (s *Set) New(items ...interface{}) Interface { + return New(items...) +} + +// Add includes the specified items (one or more) to the set. The underlying +// Set s is modified. If passed nothing it silently returns. +func (s *Set) Add(items ...interface{}) { + if len(items) == 0 { + return + } + + s.l.Lock() + defer s.l.Unlock() + + for _, item := range items { + s.m[item] = keyExists + } +} + +// Remove deletes the specified items from the set. The underlying Set s is +// modified. If passed nothing it silently returns. +func (s *Set) Remove(items ...interface{}) { + if len(items) == 0 { + return + } + + s.l.Lock() + defer s.l.Unlock() + + for _, item := range items { + delete(s.m, item) + } +} + +// Pop deletes and return an item from the set. The underlying Set s is +// modified. If set is empty, nil is returned. +func (s *Set) Pop() interface{} { + s.l.RLock() + for item := range s.m { + s.l.RUnlock() + s.l.Lock() + delete(s.m, item) + s.l.Unlock() + return item + } + s.l.RUnlock() + return nil +} + +// Has looks for the existence of items passed. It returns false if nothing is +// passed. For multiple items it returns true only if all of the items exist. +func (s *Set) Has(items ...interface{}) bool { + // assume checked for empty item, which not exist + if len(items) == 0 { + return false + } + + s.l.RLock() + defer s.l.RUnlock() + + has := true + for _, item := range items { + if _, has = s.m[item]; !has { + break + } + } + return has +} + +// Size returns the number of items in a set. +func (s *Set) Size() int { + s.l.RLock() + defer s.l.RUnlock() + + l := len(s.m) + return l +} + +// Clear removes all items from the set. +func (s *Set) Clear() { + s.l.Lock() + defer s.l.Unlock() + + s.m = make(map[interface{}]struct{}) +} + +// IsEqual test whether s and t are the same in size and have the same items. +func (s *Set) IsEqual(t Interface) bool { + s.l.RLock() + defer s.l.RUnlock() + + // Force locking only if given set is threadsafe. + if conv, ok := t.(*Set); ok { + conv.l.RLock() + defer conv.l.RUnlock() + } + + // return false if they are no the same size + if sameSize := len(s.m) == t.Size(); !sameSize { + return false + } + + equal := true + t.Each(func(item interface{}) bool { + _, equal = s.m[item] + return equal // if false, Each() will end + }) + + return equal +} + +// IsSubset tests whether t is a subset of s. +func (s *Set) IsSubset(t Interface) (subset bool) { + s.l.RLock() + defer s.l.RUnlock() + + subset = true + + t.Each(func(item interface{}) bool { + _, subset = s.m[item] + return subset + }) + + return +} + +// Each traverses the items in the Set, calling the provided function for each +// set member. Traversal will continue until all items in the Set have been +// visited, or if the closure returns false. +func (s *Set) Each(f func(item interface{}) bool) { + s.l.RLock() + defer s.l.RUnlock() + + for item := range s.m { + if !f(item) { + break + } + } +} + +// List returns a slice of all items. There is also StringSlice() and +// IntSlice() methods for returning slices of type string or int. +func (s *Set) List() []interface{} { + s.l.RLock() + defer s.l.RUnlock() + + list := make([]interface{}, 0, len(s.m)) + + for item := range s.m { + list = append(list, item) + } + + return list +} + +// Copy returns a new Set with a copy of s. +func (s *Set) Copy() Interface { + return New(s.List()...) +} + +// Merge is like Union, however it modifies the current set it's applied on +// with the given t set. +func (s *Set) Merge(t Interface) { + s.l.Lock() + defer s.l.Unlock() + + t.Each(func(item interface{}) bool { + s.m[item] = keyExists + return true + }) +} diff --git a/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts_test.go b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts_test.go new file mode 100644 index 000000000..8d2f509d0 --- /dev/null +++ b/Godeps/_workspace/src/gopkg.in/fatih/set.v0/set_ts_test.go @@ -0,0 +1,321 @@ +package set + +import ( + "reflect" + "strconv" + "strings" + "testing" +) + +func TestSet_New(t *testing.T) { + s := New() + + if s.Size() != 0 { + t.Error("New: calling without any parameters should create a set with zero size") + } + + u := s.New() + if u.Size() != 0 { + t.Error("New: creating a new set via s.New() should create a set with zero size") + } +} + +func TestSet_New_parameters(t *testing.T) { + s := New("string", "another_string", 1, 3.14) + + if s.Size() != 4 { + t.Error("New: calling with parameters should create a set with size of four") + } +} + +func TestSet_Add(t *testing.T) { + s := New() + s.Add(1) + s.Add(2) + s.Add(2) // duplicate + s.Add("fatih") + s.Add("zeynep") + s.Add("zeynep") // another duplicate + + if s.Size() != 4 { + t.Error("Add: items are not unique. The set size should be four") + } + + if !s.Has(1, 2, "fatih", "zeynep") { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSet_Add_multiple(t *testing.T) { + s := New() + s.Add("ankara", "san francisco", 3.14) + + if s.Size() != 3 { + t.Error("Add: items are not unique. The set size should be three") + } + + if !s.Has("ankara", "san francisco", 3.14) { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSet_Remove(t *testing.T) { + s := New() + s.Add(1) + s.Add(2) + s.Add("fatih") + + s.Remove(1) + if s.Size() != 2 { + t.Error("Remove: set size should be two after removing") + } + + s.Remove(1) + if s.Size() != 2 { + t.Error("Remove: set size should be not change after trying to remove a non-existing item") + } + + s.Remove(2) + s.Remove("fatih") + if s.Size() != 0 { + t.Error("Remove: set size should be zero") + } + + s.Remove("fatih") // try to remove something from a zero length set +} + +func TestSet_Remove_multiple(t *testing.T) { + s := New() + s.Add("ankara", "san francisco", 3.14, "istanbul") + s.Remove("ankara", "san francisco", 3.14) + + if s.Size() != 1 { + t.Error("Remove: items are not unique. The set size should be four") + } + + if !s.Has("istanbul") { + t.Error("Add: added items are not availabile in the set.") + } +} + +func TestSet_Pop(t *testing.T) { + s := New() + s.Add(1) + s.Add(2) + s.Add("fatih") + + a := s.Pop() + if s.Size() != 2 { + t.Error("Pop: set size should be two after popping out") + } + + if s.Has(a) { + t.Error("Pop: returned item should not exist") + } + + s.Pop() + s.Pop() + b := s.Pop() + if b != nil { + t.Error("Pop: should return nil because set is empty") + } + + s.Pop() // try to remove something from a zero length set +} + +func TestSet_Has(t *testing.T) { + s := New("1", "2", "3", "4") + + if !s.Has("1") { + t.Error("Has: the item 1 exist, but 'Has' is returning false") + } + + if !s.Has("1", "2", "3", "4") { + t.Error("Has: the items all exist, but 'Has' is returning false") + } +} + +func TestSet_Clear(t *testing.T) { + s := New() + s.Add(1) + s.Add("istanbul") + s.Add("san francisco") + + s.Clear() + if s.Size() != 0 { + t.Error("Clear: set size should be zero") + } +} + +func TestSet_IsEmpty(t *testing.T) { + s := New() + + empty := s.IsEmpty() + if !empty { + t.Error("IsEmpty: set is empty, it should be true") + } + + s.Add(2) + s.Add(3) + notEmpty := s.IsEmpty() + + if notEmpty { + t.Error("IsEmpty: set is filled, it should be false") + } +} + +func TestSet_IsEqual(t *testing.T) { + s := New("1", "2", "3") + u := New("1", "2", "3") + + ok := s.IsEqual(u) + if !ok { + t.Error("IsEqual: set s and t are equal. However it returns false") + } + + // same size, different content + a := New("1", "2", "3") + b := New("4", "5", "6") + + ok = a.IsEqual(b) + if ok { + t.Error("IsEqual: set a and b are now equal (1). However it returns true") + } + + // different size, similar content + a = New("1", "2", "3") + b = New("1", "2", "3", "4") + + ok = a.IsEqual(b) + if ok { + t.Error("IsEqual: set s and t are now equal (2). However it returns true") + } + +} + +func TestSet_IsSubset(t *testing.T) { + s := New("1", "2", "3", "4") + u := New("1", "2", "3") + + ok := s.IsSubset(u) + if !ok { + t.Error("IsSubset: u is a subset of s. However it returns false") + } + + ok = u.IsSubset(s) + if ok { + t.Error("IsSubset: s is not a subset of u. However it returns true") + } + +} + +func TestSet_IsSuperset(t *testing.T) { + s := New("1", "2", "3", "4") + u := New("1", "2", "3") + + ok := u.IsSuperset(s) + if !ok { + t.Error("IsSuperset: s is a superset of u. However it returns false") + } + + ok = s.IsSuperset(u) + if ok { + t.Error("IsSuperset: u is not a superset of u. However it returns true") + } + +} + +func TestSet_String(t *testing.T) { + s := New() + if s.String() != "[]" { + t.Errorf("String: output is not what is excepted '%s'", s.String()) + } + + s.Add("1", "2", "3", "4") + if !strings.HasPrefix(s.String(), "[") { + t.Error("String: output should begin with a square bracket") + } + + if !strings.HasSuffix(s.String(), "]") { + t.Error("String: output should end with a square bracket") + } +} + +func TestSet_List(t *testing.T) { + s := New("1", "2", "3", "4") + + // this returns a slice of interface{} + if len(s.List()) != 4 { + t.Error("List: slice size should be four.") + } + + for _, item := range s.List() { + r := reflect.TypeOf(item) + if r.Kind().String() != "string" { + t.Error("List: slice item should be a string") + } + } +} + +func TestSet_Copy(t *testing.T) { + s := New("1", "2", "3", "4") + r := s.Copy() + + if !s.IsEqual(r) { + t.Error("Copy: set s and r are not equal") + } +} + +func TestSet_Merge(t *testing.T) { + s := New("1", "2", "3") + r := New("3", "4", "5") + s.Merge(r) + + if s.Size() != 5 { + t.Error("Merge: the set doesn't have all items in it.") + } + + if !s.Has("1", "2", "3", "4", "5") { + t.Error("Merge: merged items are not availabile in the set.") + } +} + +func TestSet_Separate(t *testing.T) { + s := New("1", "2", "3") + r := New("3", "5") + s.Separate(r) + + if s.Size() != 2 { + t.Error("Separate: the set doesn't have all items in it.") + } + + if !s.Has("1", "2") { + t.Error("Separate: items after separation are not availabile in the set.") + } +} + +func TestSet_RaceAdd(t *testing.T) { + // Create two sets. Add concurrently items to each of them. Remove from the + // other one. + // "go test -race" should detect this if the library is not thread-safe. + s := New() + u := New() + + go func() { + for i := 0; i < 1000; i++ { + item := "item" + strconv.Itoa(i) + go func(i int) { + s.Add(item) + u.Add(item) + }(i) + } + }() + + for i := 0; i < 1000; i++ { + item := "item" + strconv.Itoa(i) + go func(i int) { + s.Add(item) + u.Add(item) + }(i) + } +} |