1// Copyright (c) 2015, Emir Pasic. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package linkedhashset
6
7import (
8	"fmt"
9	"testing"
10)
11
12func TestSetNew(t *testing.T) {
13	set := New(2, 1)
14	if actualValue := set.Size(); actualValue != 2 {
15		t.Errorf("Got %v expected %v", actualValue, 2)
16	}
17	values := set.Values()
18	if actualValue := values[0]; actualValue != 2 {
19		t.Errorf("Got %v expected %v", actualValue, 2)
20	}
21	if actualValue := values[1]; actualValue != 1 {
22		t.Errorf("Got %v expected %v", actualValue, 1)
23	}
24}
25
26func TestSetAdd(t *testing.T) {
27	set := New()
28	set.Add()
29	set.Add(1)
30	set.Add(2)
31	set.Add(2, 3)
32	set.Add()
33	if actualValue := set.Empty(); actualValue != false {
34		t.Errorf("Got %v expected %v", actualValue, false)
35	}
36	if actualValue := set.Size(); actualValue != 3 {
37		t.Errorf("Got %v expected %v", actualValue, 3)
38	}
39}
40
41func TestSetContains(t *testing.T) {
42	set := New()
43	set.Add(3, 1, 2)
44	set.Add(2, 3)
45	set.Add()
46	if actualValue := set.Contains(); actualValue != true {
47		t.Errorf("Got %v expected %v", actualValue, true)
48	}
49	if actualValue := set.Contains(1); actualValue != true {
50		t.Errorf("Got %v expected %v", actualValue, true)
51	}
52	if actualValue := set.Contains(1, 2, 3); actualValue != true {
53		t.Errorf("Got %v expected %v", actualValue, true)
54	}
55	if actualValue := set.Contains(1, 2, 3, 4); actualValue != false {
56		t.Errorf("Got %v expected %v", actualValue, false)
57	}
58}
59
60func TestSetRemove(t *testing.T) {
61	set := New()
62	set.Add(3, 1, 2)
63	set.Remove()
64	if actualValue := set.Size(); actualValue != 3 {
65		t.Errorf("Got %v expected %v", actualValue, 3)
66	}
67	set.Remove(1)
68	if actualValue := set.Size(); actualValue != 2 {
69		t.Errorf("Got %v expected %v", actualValue, 2)
70	}
71	set.Remove(3)
72	set.Remove(3)
73	set.Remove()
74	set.Remove(2)
75	if actualValue := set.Size(); actualValue != 0 {
76		t.Errorf("Got %v expected %v", actualValue, 0)
77	}
78}
79
80func TestSetEach(t *testing.T) {
81	set := New()
82	set.Add("c", "a", "b")
83	set.Each(func(index int, value interface{}) {
84		switch index {
85		case 0:
86			if actualValue, expectedValue := value, "c"; actualValue != expectedValue {
87				t.Errorf("Got %v expected %v", actualValue, expectedValue)
88			}
89		case 1:
90			if actualValue, expectedValue := value, "a"; actualValue != expectedValue {
91				t.Errorf("Got %v expected %v", actualValue, expectedValue)
92			}
93		case 2:
94			if actualValue, expectedValue := value, "b"; actualValue != expectedValue {
95				t.Errorf("Got %v expected %v", actualValue, expectedValue)
96			}
97		default:
98			t.Errorf("Too many")
99		}
100	})
101}
102
103func TestSetMap(t *testing.T) {
104	set := New()
105	set.Add("c", "a", "b")
106	mappedSet := set.Map(func(index int, value interface{}) interface{} {
107		return "mapped: " + value.(string)
108	})
109	if actualValue, expectedValue := mappedSet.Contains("mapped: c", "mapped: b", "mapped: a"), true; actualValue != expectedValue {
110		t.Errorf("Got %v expected %v", actualValue, expectedValue)
111	}
112	if actualValue, expectedValue := mappedSet.Contains("mapped: c", "mapped: b", "mapped: x"), false; actualValue != expectedValue {
113		t.Errorf("Got %v expected %v", actualValue, expectedValue)
114	}
115	if mappedSet.Size() != 3 {
116		t.Errorf("Got %v expected %v", mappedSet.Size(), 3)
117	}
118}
119
120func TestSetSelect(t *testing.T) {
121	set := New()
122	set.Add("c", "a", "b")
123	selectedSet := set.Select(func(index int, value interface{}) bool {
124		return value.(string) >= "a" && value.(string) <= "b"
125	})
126	if actualValue, expectedValue := selectedSet.Contains("a", "b"), true; actualValue != expectedValue {
127		fmt.Println("A: ", selectedSet.Contains("b"))
128		t.Errorf("Got %v (%v) expected %v (%v)", actualValue, selectedSet.Values(), expectedValue, "[a b]")
129	}
130	if actualValue, expectedValue := selectedSet.Contains("a", "b", "c"), false; actualValue != expectedValue {
131		t.Errorf("Got %v (%v) expected %v (%v)", actualValue, selectedSet.Values(), expectedValue, "[a b]")
132	}
133	if selectedSet.Size() != 2 {
134		t.Errorf("Got %v expected %v", selectedSet.Size(), 3)
135	}
136}
137
138func TestSetAny(t *testing.T) {
139	set := New()
140	set.Add("c", "a", "b")
141	any := set.Any(func(index int, value interface{}) bool {
142		return value.(string) == "c"
143	})
144	if any != true {
145		t.Errorf("Got %v expected %v", any, true)
146	}
147	any = set.Any(func(index int, value interface{}) bool {
148		return value.(string) == "x"
149	})
150	if any != false {
151		t.Errorf("Got %v expected %v", any, false)
152	}
153}
154
155func TestSetAll(t *testing.T) {
156	set := New()
157	set.Add("c", "a", "b")
158	all := set.All(func(index int, value interface{}) bool {
159		return value.(string) >= "a" && value.(string) <= "c"
160	})
161	if all != true {
162		t.Errorf("Got %v expected %v", all, true)
163	}
164	all = set.All(func(index int, value interface{}) bool {
165		return value.(string) >= "a" && value.(string) <= "b"
166	})
167	if all != false {
168		t.Errorf("Got %v expected %v", all, false)
169	}
170}
171
172func TestSetFind(t *testing.T) {
173	set := New()
174	set.Add("c", "a", "b")
175	foundIndex, foundValue := set.Find(func(index int, value interface{}) bool {
176		return value.(string) == "c"
177	})
178	if foundValue != "c" || foundIndex != 0 {
179		t.Errorf("Got %v at %v expected %v at %v", foundValue, foundIndex, "c", 0)
180	}
181	foundIndex, foundValue = set.Find(func(index int, value interface{}) bool {
182		return value.(string) == "x"
183	})
184	if foundValue != nil || foundIndex != -1 {
185		t.Errorf("Got %v at %v expected %v at %v", foundValue, foundIndex, nil, nil)
186	}
187}
188
189func TestSetChaining(t *testing.T) {
190	set := New()
191	set.Add("c", "a", "b")
192}
193
194func TestSetIteratorPrevOnEmpty(t *testing.T) {
195	set := New()
196	it := set.Iterator()
197	for it.Prev() {
198		t.Errorf("Shouldn't iterate on empty set")
199	}
200}
201
202func TestSetIteratorNext(t *testing.T) {
203	set := New()
204	set.Add("c", "a", "b")
205	it := set.Iterator()
206	count := 0
207	for it.Next() {
208		count++
209		index := it.Index()
210		value := it.Value()
211		switch index {
212		case 0:
213			if actualValue, expectedValue := value, "c"; actualValue != expectedValue {
214				t.Errorf("Got %v expected %v", actualValue, expectedValue)
215			}
216		case 1:
217			if actualValue, expectedValue := value, "a"; actualValue != expectedValue {
218				t.Errorf("Got %v expected %v", actualValue, expectedValue)
219			}
220		case 2:
221			if actualValue, expectedValue := value, "b"; actualValue != expectedValue {
222				t.Errorf("Got %v expected %v", actualValue, expectedValue)
223			}
224		default:
225			t.Errorf("Too many")
226		}
227		if actualValue, expectedValue := index, count-1; actualValue != expectedValue {
228			t.Errorf("Got %v expected %v", actualValue, expectedValue)
229		}
230	}
231	if actualValue, expectedValue := count, 3; actualValue != expectedValue {
232		t.Errorf("Got %v expected %v", actualValue, expectedValue)
233	}
234}
235
236func TestSetIteratorPrev(t *testing.T) {
237	set := New()
238	set.Add("c", "a", "b")
239	it := set.Iterator()
240	for it.Prev() {
241	}
242	count := 0
243	for it.Next() {
244		count++
245		index := it.Index()
246		value := it.Value()
247		switch index {
248		case 0:
249			if actualValue, expectedValue := value, "c"; actualValue != expectedValue {
250				t.Errorf("Got %v expected %v", actualValue, expectedValue)
251			}
252		case 1:
253			if actualValue, expectedValue := value, "a"; actualValue != expectedValue {
254				t.Errorf("Got %v expected %v", actualValue, expectedValue)
255			}
256		case 2:
257			if actualValue, expectedValue := value, "b"; actualValue != expectedValue {
258				t.Errorf("Got %v expected %v", actualValue, expectedValue)
259			}
260		default:
261			t.Errorf("Too many")
262		}
263		if actualValue, expectedValue := index, count-1; actualValue != expectedValue {
264			t.Errorf("Got %v expected %v", actualValue, expectedValue)
265		}
266	}
267	if actualValue, expectedValue := count, 3; actualValue != expectedValue {
268		t.Errorf("Got %v expected %v", actualValue, expectedValue)
269	}
270}
271
272func TestSetIteratorBegin(t *testing.T) {
273	set := New()
274	it := set.Iterator()
275	it.Begin()
276	set.Add("a", "b", "c")
277	for it.Next() {
278	}
279	it.Begin()
280	it.Next()
281	if index, value := it.Index(), it.Value(); index != 0 || value != "a" {
282		t.Errorf("Got %v,%v expected %v,%v", index, value, 0, "a")
283	}
284}
285
286func TestSetIteratorEnd(t *testing.T) {
287	set := New()
288	it := set.Iterator()
289
290	if index := it.Index(); index != -1 {
291		t.Errorf("Got %v expected %v", index, -1)
292	}
293
294	it.End()
295	if index := it.Index(); index != 0 {
296		t.Errorf("Got %v expected %v", index, 0)
297	}
298
299	set.Add("a", "b", "c")
300	it.End()
301	if index := it.Index(); index != set.Size() {
302		t.Errorf("Got %v expected %v", index, set.Size())
303	}
304
305	it.Prev()
306	if index, value := it.Index(), it.Value(); index != set.Size()-1 || value != "c" {
307		t.Errorf("Got %v,%v expected %v,%v", index, value, set.Size()-1, "c")
308	}
309}
310
311func TestSetIteratorFirst(t *testing.T) {
312	set := New()
313	set.Add("a", "b", "c")
314	it := set.Iterator()
315	if actualValue, expectedValue := it.First(), true; actualValue != expectedValue {
316		t.Errorf("Got %v expected %v", actualValue, expectedValue)
317	}
318	if index, value := it.Index(), it.Value(); index != 0 || value != "a" {
319		t.Errorf("Got %v,%v expected %v,%v", index, value, 0, "a")
320	}
321}
322
323func TestSetIteratorLast(t *testing.T) {
324	set := New()
325	set.Add("a", "b", "c")
326	it := set.Iterator()
327	if actualValue, expectedValue := it.Last(), true; actualValue != expectedValue {
328		t.Errorf("Got %v expected %v", actualValue, expectedValue)
329	}
330	if index, value := it.Index(), it.Value(); index != 2 || value != "c" {
331		t.Errorf("Got %v,%v expected %v,%v", index, value, 3, "c")
332	}
333}
334
335func TestSetSerialization(t *testing.T) {
336	set := New()
337	set.Add("a", "b", "c")
338
339	var err error
340	assert := func() {
341		if actualValue, expectedValue := set.Size(), 3; actualValue != expectedValue {
342			t.Errorf("Got %v expected %v", actualValue, expectedValue)
343		}
344		if actualValue := set.Contains("a", "b", "c"); actualValue != true {
345			t.Errorf("Got %v expected %v", actualValue, true)
346		}
347		if err != nil {
348			t.Errorf("Got error %v", err)
349		}
350	}
351
352	assert()
353
354	json, err := set.ToJSON()
355	assert()
356
357	err = set.FromJSON(json)
358	assert()
359}
360
361func benchmarkContains(b *testing.B, set *Set, size int) {
362	for i := 0; i < b.N; i++ {
363		for n := 0; n < size; n++ {
364			set.Contains(n)
365		}
366	}
367}
368
369func benchmarkAdd(b *testing.B, set *Set, size int) {
370	for i := 0; i < b.N; i++ {
371		for n := 0; n < size; n++ {
372			set.Add(n)
373		}
374	}
375}
376
377func benchmarkRemove(b *testing.B, set *Set, size int) {
378	for i := 0; i < b.N; i++ {
379		for n := 0; n < size; n++ {
380			set.Remove(n)
381		}
382	}
383}
384
385func BenchmarkHashSetContains100(b *testing.B) {
386	b.StopTimer()
387	size := 100
388	set := New()
389	for n := 0; n < size; n++ {
390		set.Add(n)
391	}
392	b.StartTimer()
393	benchmarkContains(b, set, size)
394}
395
396func BenchmarkHashSetContains1000(b *testing.B) {
397	b.StopTimer()
398	size := 1000
399	set := New()
400	for n := 0; n < size; n++ {
401		set.Add(n)
402	}
403	b.StartTimer()
404	benchmarkContains(b, set, size)
405}
406
407func BenchmarkHashSetContains10000(b *testing.B) {
408	b.StopTimer()
409	size := 10000
410	set := New()
411	for n := 0; n < size; n++ {
412		set.Add(n)
413	}
414	b.StartTimer()
415	benchmarkContains(b, set, size)
416}
417
418func BenchmarkHashSetContains100000(b *testing.B) {
419	b.StopTimer()
420	size := 100000
421	set := New()
422	for n := 0; n < size; n++ {
423		set.Add(n)
424	}
425	b.StartTimer()
426	benchmarkContains(b, set, size)
427}
428
429func BenchmarkHashSetAdd100(b *testing.B) {
430	b.StopTimer()
431	size := 100
432	set := New()
433	b.StartTimer()
434	benchmarkAdd(b, set, size)
435}
436
437func BenchmarkHashSetAdd1000(b *testing.B) {
438	b.StopTimer()
439	size := 1000
440	set := New()
441	for n := 0; n < size; n++ {
442		set.Add(n)
443	}
444	b.StartTimer()
445	benchmarkAdd(b, set, size)
446}
447
448func BenchmarkHashSetAdd10000(b *testing.B) {
449	b.StopTimer()
450	size := 10000
451	set := New()
452	for n := 0; n < size; n++ {
453		set.Add(n)
454	}
455	b.StartTimer()
456	benchmarkAdd(b, set, size)
457}
458
459func BenchmarkHashSetAdd100000(b *testing.B) {
460	b.StopTimer()
461	size := 100000
462	set := New()
463	for n := 0; n < size; n++ {
464		set.Add(n)
465	}
466	b.StartTimer()
467	benchmarkAdd(b, set, size)
468}
469
470func BenchmarkHashSetRemove100(b *testing.B) {
471	b.StopTimer()
472	size := 100
473	set := New()
474	for n := 0; n < size; n++ {
475		set.Add(n)
476	}
477	b.StartTimer()
478	benchmarkRemove(b, set, size)
479}
480
481func BenchmarkHashSetRemove1000(b *testing.B) {
482	b.StopTimer()
483	size := 1000
484	set := New()
485	for n := 0; n < size; n++ {
486		set.Add(n)
487	}
488	b.StartTimer()
489	benchmarkRemove(b, set, size)
490}
491
492func BenchmarkHashSetRemove10000(b *testing.B) {
493	b.StopTimer()
494	size := 10000
495	set := New()
496	for n := 0; n < size; n++ {
497		set.Add(n)
498	}
499	b.StartTimer()
500	benchmarkRemove(b, set, size)
501}
502
503func BenchmarkHashSetRemove100000(b *testing.B) {
504	b.StopTimer()
505	size := 100000
506	set := New()
507	for n := 0; n < size; n++ {
508		set.Add(n)
509	}
510	b.StartTimer()
511	benchmarkRemove(b, set, size)
512}
513