set_test.go

Documentation: k8s.io/apimachinery/pkg/util/sets

     1  /*
     2  Copyright 2014 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package sets
    18  
    19  import (
    20  	"fmt"
    21  	"math/rand"
    22  	"reflect"
    23  	"testing"
    24  )
    25  
    26  func TestStringSet(t *testing.T) {
    27  	s := String{}
    28  	s2 := String{}
    29  	if len(s) != 0 {
    30  		t.Errorf("Expected len=0: %d", len(s))
    31  	}
    32  	s.Insert("a", "b")
    33  	if len(s) != 2 {
    34  		t.Errorf("Expected len=2: %d", len(s))
    35  	}
    36  	s.Insert("c")
    37  	if s.Has("d") {
    38  		t.Errorf("Unexpected contents: %#v", s)
    39  	}
    40  	if !s.Has("a") {
    41  		t.Errorf("Missing contents: %#v", s)
    42  	}
    43  	s.Delete("a")
    44  	if s.Has("a") {
    45  		t.Errorf("Unexpected contents: %#v", s)
    46  	}
    47  	s.Insert("a")
    48  	if s.HasAll("a", "b", "d") {
    49  		t.Errorf("Unexpected contents: %#v", s)
    50  	}
    51  	if !s.HasAll("a", "b") {
    52  		t.Errorf("Missing contents: %#v", s)
    53  	}
    54  	s2.Insert("a", "b", "d")
    55  	if s.IsSuperset(s2) {
    56  		t.Errorf("Unexpected contents: %#v", s)
    57  	}
    58  	s2.Delete("d")
    59  	if !s.IsSuperset(s2) {
    60  		t.Errorf("Missing contents: %#v", s)
    61  	}
    62  }
    63  
    64  func TestStringSetDeleteMultiples(t *testing.T) {
    65  	s := String{}
    66  	s.Insert("a", "b", "c")
    67  	if len(s) != 3 {
    68  		t.Errorf("Expected len=3: %d", len(s))
    69  	}
    70  
    71  	s.Delete("a", "c")
    72  	if len(s) != 1 {
    73  		t.Errorf("Expected len=1: %d", len(s))
    74  	}
    75  	if s.Has("a") {
    76  		t.Errorf("Unexpected contents: %#v", s)
    77  	}
    78  	if s.Has("c") {
    79  		t.Errorf("Unexpected contents: %#v", s)
    80  	}
    81  	if !s.Has("b") {
    82  		t.Errorf("Missing contents: %#v", s)
    83  	}
    84  
    85  }
    86  
    87  func TestNewStringSet(t *testing.T) {
    88  	s := NewString("a", "b", "c")
    89  	if len(s) != 3 {
    90  		t.Errorf("Expected len=3: %d", len(s))
    91  	}
    92  	if !s.Has("a") || !s.Has("b") || !s.Has("c") {
    93  		t.Errorf("Unexpected contents: %#v", s)
    94  	}
    95  }
    96  
    97  func TestStringSetList(t *testing.T) {
    98  	s := NewString("z", "y", "x", "a")
    99  	if !reflect.DeepEqual(s.List(), []string{"a", "x", "y", "z"}) {
   100  		t.Errorf("List gave unexpected result: %#v", s.List())
   101  	}
   102  }
   103  
   104  func TestStringSetDifference(t *testing.T) {
   105  	a := NewString("1", "2", "3")
   106  	b := NewString("1", "2", "4", "5")
   107  	c := a.Difference(b)
   108  	d := b.Difference(a)
   109  	if len(c) != 1 {
   110  		t.Errorf("Expected len=1: %d", len(c))
   111  	}
   112  	if !c.Has("3") {
   113  		t.Errorf("Unexpected contents: %#v", c.List())
   114  	}
   115  	if len(d) != 2 {
   116  		t.Errorf("Expected len=2: %d", len(d))
   117  	}
   118  	if !d.Has("4") || !d.Has("5") {
   119  		t.Errorf("Unexpected contents: %#v", d.List())
   120  	}
   121  }
   122  
   123  func TestStringSetSymmetricDifference(t *testing.T) {
   124  	a := NewString("1", "2", "3")
   125  	b := NewString("1", "2", "4", "5")
   126  	c := a.SymmetricDifference(b)
   127  	d := b.SymmetricDifference(a)
   128  	if !c.Equal(NewString("3", "4", "5")) {
   129  		t.Errorf("Unexpected contents: %#v", c.List())
   130  	}
   131  	if !d.Equal(NewString("3", "4", "5")) {
   132  		t.Errorf("Unexpected contents: %#v", d.List())
   133  	}
   134  }
   135  
   136  func TestStringSetHasAny(t *testing.T) {
   137  	a := NewString("1", "2", "3")
   138  
   139  	if !a.HasAny("1", "4") {
   140  		t.Errorf("expected true, got false")
   141  	}
   142  
   143  	if a.HasAny("0", "4") {
   144  		t.Errorf("expected false, got true")
   145  	}
   146  }
   147  
   148  func TestStringSetEquals(t *testing.T) {
   149  	// Simple case (order doesn't matter)
   150  	a := NewString("1", "2")
   151  	b := NewString("2", "1")
   152  	if !a.Equal(b) {
   153  		t.Errorf("Expected to be equal: %v vs %v", a, b)
   154  	}
   155  
   156  	// It is a set; duplicates are ignored
   157  	b = NewString("2", "2", "1")
   158  	if !a.Equal(b) {
   159  		t.Errorf("Expected to be equal: %v vs %v", a, b)
   160  	}
   161  
   162  	// Edge cases around empty sets / empty strings
   163  	a = NewString()
   164  	b = NewString()
   165  	if !a.Equal(b) {
   166  		t.Errorf("Expected to be equal: %v vs %v", a, b)
   167  	}
   168  
   169  	b = NewString("1", "2", "3")
   170  	if a.Equal(b) {
   171  		t.Errorf("Expected to be not-equal: %v vs %v", a, b)
   172  	}
   173  
   174  	b = NewString("1", "2", "")
   175  	if a.Equal(b) {
   176  		t.Errorf("Expected to be not-equal: %v vs %v", a, b)
   177  	}
   178  
   179  	// Check for equality after mutation
   180  	a = NewString()
   181  	a.Insert("1")
   182  	if a.Equal(b) {
   183  		t.Errorf("Expected to be not-equal: %v vs %v", a, b)
   184  	}
   185  
   186  	a.Insert("2")
   187  	if a.Equal(b) {
   188  		t.Errorf("Expected to be not-equal: %v vs %v", a, b)
   189  	}
   190  
   191  	a.Insert("")
   192  	if !a.Equal(b) {
   193  		t.Errorf("Expected to be equal: %v vs %v", a, b)
   194  	}
   195  
   196  	a.Delete("")
   197  	if a.Equal(b) {
   198  		t.Errorf("Expected to be not-equal: %v vs %v", a, b)
   199  	}
   200  }
   201  
   202  func TestStringUnion(t *testing.T) {
   203  	tests := []struct {
   204  		s1       String
   205  		s2       String
   206  		expected String
   207  	}{
   208  		{
   209  			NewString("1", "2", "3", "4"),
   210  			NewString("3", "4", "5", "6"),
   211  			NewString("1", "2", "3", "4", "5", "6"),
   212  		},
   213  		{
   214  			NewString("1", "2", "3", "4"),
   215  			NewString(),
   216  			NewString("1", "2", "3", "4"),
   217  		},
   218  		{
   219  			NewString(),
   220  			NewString("1", "2", "3", "4"),
   221  			NewString("1", "2", "3", "4"),
   222  		},
   223  		{
   224  			NewString(),
   225  			NewString(),
   226  			NewString(),
   227  		},
   228  	}
   229  
   230  	for _, test := range tests {
   231  		union := test.s1.Union(test.s2)
   232  		if union.Len() != test.expected.Len() {
   233  			t.Errorf("Expected union.Len()=%d but got %d", test.expected.Len(), union.Len())
   234  		}
   235  
   236  		if !union.Equal(test.expected) {
   237  			t.Errorf("Expected union.Equal(expected) but not true.  union:%v expected:%v", union.List(), test.expected.List())
   238  		}
   239  	}
   240  }
   241  
   242  func TestStringIntersection(t *testing.T) {
   243  	tests := []struct {
   244  		s1       String
   245  		s2       String
   246  		expected String
   247  	}{
   248  		{
   249  			NewString("1", "2", "3", "4"),
   250  			NewString("3", "4", "5", "6"),
   251  			NewString("3", "4"),
   252  		},
   253  		{
   254  			NewString("1", "2", "3", "4"),
   255  			NewString("1", "2", "3", "4"),
   256  			NewString("1", "2", "3", "4"),
   257  		},
   258  		{
   259  			NewString("1", "2", "3", "4"),
   260  			NewString(),
   261  			NewString(),
   262  		},
   263  		{
   264  			NewString(),
   265  			NewString("1", "2", "3", "4"),
   266  			NewString(),
   267  		},
   268  		{
   269  			NewString(),
   270  			NewString(),
   271  			NewString(),
   272  		},
   273  	}
   274  
   275  	for _, test := range tests {
   276  		intersection := test.s1.Intersection(test.s2)
   277  		if intersection.Len() != test.expected.Len() {
   278  			t.Errorf("Expected intersection.Len()=%d but got %d", test.expected.Len(), intersection.Len())
   279  		}
   280  
   281  		if !intersection.Equal(test.expected) {
   282  			t.Errorf("Expected intersection.Equal(expected) but not true.  intersection:%v expected:%v", intersection.List(), test.expected.List())
   283  		}
   284  	}
   285  }
   286  
   287  type randomStringAlphabet string
   288  
   289  func (a randomStringAlphabet) makeString(minLen, maxLen int) string {
   290  	n := minLen
   291  	if minLen < maxLen {
   292  		n += rand.Intn(maxLen - minLen)
   293  	}
   294  	var s string
   295  	for i := 0; i < n; i++ {
   296  		s += string(a[rand.Intn(len(a))])
   297  	}
   298  	return s
   299  }
   300  
   301  var randomStringMaker = randomStringAlphabet("abcdefghijklmnopqrstuvwxyz0123456789")
   302  
   303  func BenchmarkStringSet(b *testing.B) {
   304  	cases := []struct {
   305  		size         int
   306  		minStringLen int
   307  		maxStringLen int
   308  	}{
   309  		{20, 10, 20},
   310  		{50, 10, 30},
   311  		{100, 20, 40},
   312  		{500, 20, 50},
   313  		{1000, 20, 60},
   314  	}
   315  
   316  	for i := range cases {
   317  		here := cases[i]
   318  		makeSet := func() String {
   319  			s := NewString()
   320  			for j := 0; j < here.size; j++ {
   321  				s.Insert(randomStringMaker.makeString(here.minStringLen, here.maxStringLen))
   322  			}
   323  			return s
   324  		}
   325  		operands := make([]String, 500)
   326  		for i := range operands {
   327  			operands[i] = makeSet()
   328  		}
   329  		randOperand := func() String { return operands[rand.Intn(len(operands))] }
   330  
   331  		b.Run(fmt.Sprintf("insert-%v", here.size), func(b *testing.B) {
   332  			b.ReportAllocs()
   333  			for i := 0; i < b.N; i++ {
   334  				makeSet()
   335  			}
   336  		})
   337  
   338  		b.Run(fmt.Sprintf("key-set-%v", here.size), func(b *testing.B) {
   339  			b.ReportAllocs()
   340  			for i := 0; i < b.N; i++ {
   341  				StringKeySet(randOperand())
   342  			}
   343  		})
   344  
   345  		b.Run(fmt.Sprintf("has-%v", here.size), func(b *testing.B) {
   346  			b.ReportAllocs()
   347  			for i := 0; i < b.N; i++ {
   348  				randOperand().Has(randomStringMaker.makeString(here.minStringLen, here.maxStringLen))
   349  			}
   350  		})
   351  
   352  		b.Run(fmt.Sprintf("intersection-%v", here.size), func(b *testing.B) {
   353  			b.ReportAllocs()
   354  			for i := 0; i < b.N; i++ {
   355  				randOperand().Intersection(randOperand())
   356  			}
   357  		})
   358  
   359  		b.Run(fmt.Sprintf("symmetric-difference-%v", here.size), func(b *testing.B) {
   360  			b.ReportAllocs()
   361  			for i := 0; i < b.N; i++ {
   362  				randOperand().SymmetricDifference(randOperand())
   363  			}
   364  		})
   365  
   366  		b.Run(fmt.Sprintf("list-%v", here.size), func(b *testing.B) {
   367  			b.ReportAllocs()
   368  			for i := 0; i < b.N; i++ {
   369  				randOperand().List()
   370  			}
   371  		})
   372  	}
   373  }
   374
View as plain text