Repository navigation
Expand file tree
/
Copy pathset3.go
More file actions
1118 lines (959 loc) · 27.2 KB
/
Copy pathset3.go
File metadata and controls
1118 lines (959 loc) · 27.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2024 TomTonic
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package set3
import (
"fmt"
"iter"
"math/bits"
"strings"
"github.com/dolthub/maphash"
)
const (
set3groupSize = 8
set3maxAvgGroupLoad = 6.5
set3loBits uint64 = 0x0101010101010101
set3hiBits uint64 = 0x8080808080808080
set3AllEmpty uint64 = 0x8080808080808080
set3AllDeleted uint64 = 0xFEFEFEFEFEFEFEFE
set3Empty uint64 = 0b0000_1000_0000
set3Deleted uint64 = 0b0000_1111_1110
set3Sentinel uint64 = 0b0000_1111_1111
)
func set3ctlrMatchH2(m uint64, h uint64) uint64 {
return set3hasZeroByte(m ^ (set3loBits * h))
}
func set3ctlrMatchEmpty(m uint64) uint64 {
return set3hasZeroByte(m ^ set3hiBits)
}
func set3nextMatch(b *uint64) int {
s := bits.TrailingZeros64(*b)
*b &= ^(1 << s) // clear bit |s|
return s >> 3 // div by 8
}
func set3hasZeroByte(x uint64) uint64 {
return ((x - set3loBits) & ^(x)) & set3hiBits
}
// Set3 is a hash set of type K.
type Set3[T comparable] struct {
hashFunction maphash.Hasher[T]
resident uint32
dead uint32
elementLimit uint32
groupCtrl []uint64
groupSlot [][set3groupSize]T
}
/*
Returns a string representation of the elements of thisSet in Roster notation (https://en.wikipedia.org/wiki/Set_(mathematics)#Roster_notation).
The order of the elements in the result is arbitrarily.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
fmt.Println(set) // will print "{2,3,1}" with the numbers in arbitrary order
*/
func (thisSet *Set3[T]) String() string {
if thisSet == nil {
return "{nil}"
}
var builder strings.Builder
builder.WriteString("{")
total := thisSet.Size()
cnt := uint32(0)
for e := range thisSet.MutableRange() {
builder.WriteString(fmt.Sprintf("%v", e))
if cnt < total-1 {
builder.WriteString(",")
}
cnt++
}
builder.WriteString("}")
return builder.String()
}
/*
Empty creates a new and empty Set3 with a reasonable default initial capacity. Choose this constructor if you have no idea on how big your set will be.
You can add as many elements to this set as you like, the backing data structure will automatically be reorganized to fit your needs.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
*/
func Empty[T comparable]() *Set3[T] {
return EmptyWithCapacity[T](21)
}
/*
EmptyWithCapacity creates a new and empty Set3 with a given initial capacity. Choose this constructor if you have a pretty good idea on how big your set will be.
Nonetheless, you can add as many elements to this set as you like, the backing data structure will automatically be reorganized to fit your needs.
Example:
set1 := Empty[int]() // you can put 1 mio. ints in set1. set1 will rehash itself several times while adding them
set2 := EmptyWithCapacity[int](2_000_000) // you can put 1 mio. ints in set2. set2 does not need to rehash itself while adding them
*/
func EmptyWithCapacity[T comparable](initialCapacity uint32) *Set3[T] {
reqNrOfGroups := calcReqNrOfGroups(initialCapacity)
result := &Set3[T]{
hashFunction: maphash.NewHasher[T](),
elementLimit: uint32(float64(reqNrOfGroups) * set3maxAvgGroupLoad),
groupCtrl: make([]uint64, reqNrOfGroups),
groupSlot: make([][set3groupSize]T, reqNrOfGroups),
}
for i := range reqNrOfGroups {
result.groupCtrl[i] = set3AllEmpty
}
return result
}
func calcReqNrOfGroups(reqCapa uint32) uint32 {
reqNrOfGroups := uint32((float64(reqCapa) + set3maxAvgGroupLoad - 1) / set3maxAvgGroupLoad)
if reqNrOfGroups == 0 {
reqNrOfGroups = 1
}
return reqNrOfGroups
}
/*
From is a convenience constructor to directly create a Set3 from given arguments. It creates a new Set3 and adds all (unique) elements to this set.
If the arguments contain duplicates, the duplicates are omitted. If no arguments are provided, an empty Set3 is returned.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := From(1, 2, 3) // set1 and set2 are equal
*/
func From[T comparable](args ...T) *Set3[T] {
if args == nil {
return Empty[T]()
}
result := EmptyWithCapacity[T](uint32(len(args) * 7 / 5)) //nolint:gosec
for _, e := range args {
result.Add(e)
}
return result
}
/*
FromArray is a convenience constructor to directly create a Set3 from given values. It creates a new Set3 and adds all (unique) elements to this set.
If the array contains duplicates, the duplicates are omitted. If data is nil, an empty Set3 is returned.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := FromArray([]int{1, 2, 3}) // set1 and set2 are equal
*/
func FromArray[T comparable](data []T) *Set3[T] {
if data == nil {
return Empty[T]()
}
result := EmptyWithCapacity[T](uint32(len(data) * 7 / 5)) //nolint:gosec
for _, e := range data {
result.Add(e)
}
return result
}
/*
Clone creates an exact clone of thisSet. You can manipulate both clones independently.
Cloning is 'cheap' in comparison with creating a new set and adding all elements from this set, as only the backing data structures are copied (no rehashing is applied).
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := set1.Clone() // set2 will be an exact but independent clone of set1
*/
func (thisSet *Set3[T]) Clone() *Set3[T] {
result := &Set3[T]{
hashFunction: thisSet.hashFunction,
elementLimit: thisSet.elementLimit,
resident: thisSet.resident,
dead: thisSet.dead,
groupCtrl: make([]uint64, len(thisSet.groupCtrl)),
groupSlot: make([][set3groupSize]T, len(thisSet.groupSlot)),
}
copy(result.groupCtrl, thisSet.groupCtrl)
copy(result.groupSlot, thisSet.groupSlot)
return result
}
/*
Contains returns true if the element is contained in thisSet.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b1 := set.Contains(2) // b1 will be true
b2 := set.Contains(4) // b2 will be false
*/
func (thisSet *Set3[T]) Contains(element T) bool {
hash := thisSet.hashFunction.Hash(element)
H2 := (hash & 0x0000_0000_0000_007f)
groupCount := uint64(len(thisSet.groupCtrl))
currentGroupIndex := getGroupIndex(hash, groupCount)
for {
ctrl := thisSet.groupCtrl[currentGroupIndex]
H2matches := set3ctlrMatchH2(ctrl, H2)
if H2matches != 0 {
slot := &(thisSet.groupSlot[currentGroupIndex])
for H2matches != 0 {
s := set3nextMatch(&H2matches)
if element == slot[s] {
return true
}
}
}
// |key| is not in group |g|,
// stop probing if we see an empty slot
emptyMatches := set3ctlrMatchEmpty(ctrl)
if emptyMatches != 0 {
// there is an empty slot - the element, if it had been added, hat either
// been found until now or it had been added in the next empty spot -
// well, this is the next empty spot...
return false
}
currentGroupIndex++ // carousel through all groups
if currentGroupIndex >= groupCount {
currentGroupIndex = 0
}
}
}
func getGroupIndex(hash, groupCount uint64) uint64 {
// no. 1: Original approach
// H1 := (hash & 0xffff_ffff_ffff_ff80) >> 7
// no. 2: adapt constant to use Lemire's fast alternative to the modulo reduction (see https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/)
// H1 := (hash & 0x0000_007f_ffff_ff80) >> 7
// no. 3: make sure not to loose entropy from the top 25 bits (in case of weak hash function)
// H1 := (((hash >> 25) ^ hash) & 0x0000_007f_ffff_ff80) >> 7
// Original approach (no. 1)
// return H1 % groupCount
// Lemire's fast alternative to the modulo reduction (no. 2)
// return (H1 * groupCount) >> 32
// no. 3b: same as no. 3
a := hash >> 32
b := hash >> 7
c := a ^ b
d := c & 0x0000_0000_ffff_ffff
e := d * groupCount
f := e >> 32
return f
}
/*
Returns true if thisSet contains all elements from thatSet.
If thatSet is empty, ContainsAll returns true. If thatSet is nil, ContainsAll returns true.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
Empty := Empty[int]()
b := set.ContainsAll(Empty) // b will be true
*/
func (thisSet *Set3[T]) ContainsAll(thatSet *Set3[T]) bool {
if thisSet == thatSet {
return true
}
if thatSet == nil {
// nil is interpreted as empty set
return true
}
if thisSet.Size() < thatSet.Size() {
return false
}
for e := range thatSet.MutableRange() {
if !thisSet.Contains(e) {
return false
}
}
return true
}
/*
Returns true if thisSet contains all of the given argument values.
If the number of arguments is zero, ContainsAllOf returns true.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set.ContainsAllOf(2,3,4) // b will be false
*/
func (thisSet *Set3[T]) ContainsAllOf(args ...T) bool {
if args == nil {
// nil is interpreted as empty set
return true
}
for _, e := range args {
if !thisSet.Contains(e) {
return false
}
}
return true
}
/*
Returns true if thisSet contains all elements from the given data array.
If the length of data is zero, ContainsAllFromArray returns true. If data is nil, ContainsAllFromArray returns true.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set.ContainsAllFromArray([]int{2,3,4}) // b will be false
*/
func (thisSet *Set3[T]) ContainsAllFromArray(data []T) bool {
if data == nil {
// nil is interpreted as empty set
return true
}
for _, e := range data {
if !thisSet.Contains(e) {
return false
}
}
return true
}
/*
Returns true if thisSet and thatSet have the same size and contain the same elements.
If thatSet is nil, Equals returns true if and only if thisSet is empty.
Example:
set1 := Empty[int]()
set2 := Empty[int]()
b1 := set1.Equals(set2) // b1 will be true
set1.Add(7)
set2.Add(31)
b2 := set1.Equals(set2) // b2 will be false
*/
func (thisSet *Set3[T]) Equals(thatSet *Set3[T]) bool {
if thisSet == thatSet {
return true
}
if thatSet == nil {
// nil is interpreted as empty set
return thisSet.Size() == 0
}
if thisSet.Size() != thatSet.Size() {
return false
}
for elem := range thatSet.MutableRange() {
if !thisSet.Contains(elem) {
return false
}
}
return true
}
/*
Iterates over all elements in thisSet.
Caution: If thisSet is changed during the iteration, the result is unpredictable. So if you want to add or remove elements to or from thisSet during the itration, choose [ImmutableRange].
Example:
for elem := range set.MutableRange() {
// do something with elem...
}
*/
func (thisSet *Set3[T]) MutableRange() iter.Seq[T] {
return func(yield func(T) bool) {
for i, ctrl := range thisSet.groupCtrl {
if ctrl&set3hiBits != set3hiBits { // not all empty or deleted
slot := &(thisSet.groupSlot[i])
for i := 0; i < set3groupSize; i++ {
if isAnElementAt(ctrl, i) {
if !yield(slot[i]) {
return
}
}
}
}
}
}
}
/*
Iterates over all elements in thisSet.
Makes an internal copy of the stored elements first, so you can add or remove elements to or from thisSet during the itration, for example. To avoid this extra copy, e.g., for performance reasons, choose [MutableRange].
Example:
for elem := range set.ImmutableRange() {
// do something with elem...
}
*/
func (thisSet *Set3[T]) ImmutableRange() iter.Seq[T] {
return func(yield func(T) bool) {
localCtrl := make([]uint64, len(thisSet.groupCtrl))
localSlot := make([][set3groupSize]T, len(thisSet.groupSlot))
copy(localCtrl, thisSet.groupCtrl)
copy(localSlot, thisSet.groupSlot)
for i, ctrl := range localCtrl {
if ctrl&set3hiBits != set3hiBits { // not all empty or deleted
slot := &(localSlot[i])
for i := 0; i < set3groupSize; i++ {
if isAnElementAt(ctrl, i) {
if !yield(slot[i]) {
return
}
}
}
}
}
}
}
/*
ToArray allocates an array of type T and adds all elements of thisSet to it. The order of the elements in the resulting array is arbitrary.
Example:
set := Empty[int]()
set.Add(7)
set.Add(31)
intArray := set.ToArray() // will be an []int of length 2 containing 7 and 31 in arbitrary order
*/
func (thisSet *Set3[T]) ToArray() []T {
result := make([]T, thisSet.Size())
i := 0
for e := range thisSet.MutableRange() {
result[i] = e
i++
}
return result
}
/*
Inserts the element into thisSet if it is not yet in thisSet.
Example:
set := Empty[int]()
set.Add(7)
*/
func (thisSet *Set3[T]) Add(element T) {
if thisSet.resident >= thisSet.elementLimit {
thisSet.rehashToNumGroups(thisSet.calcNextGroupCount())
}
hash := thisSet.hashFunction.Hash(element)
H2 := (hash & 0x0000_0000_0000_007f)
groupCount := uint64(len(thisSet.groupCtrl))
currentGroupIndex := getGroupIndex(hash, groupCount)
for {
ctrl := thisSet.groupCtrl[currentGroupIndex]
H2matches := set3ctlrMatchH2(ctrl, H2)
if H2matches != 0 {
slot := &(thisSet.groupSlot[currentGroupIndex])
for H2matches != 0 {
s := set3nextMatch(&H2matches)
if element == slot[s] {
// found - already in Set3, just return
return
}
}
}
// element is not in group,
// stop probing if we see an empty slot
emptyMatches := set3ctlrMatchEmpty(ctrl)
if emptyMatches != 0 {
// empty spot -> element can't be in Set3 (see Contains) -> insert
s := set3nextMatch(&emptyMatches)
thisSet.groupCtrl[currentGroupIndex] = setCTRLat(ctrl, H2, s)
thisSet.groupSlot[currentGroupIndex][s] = element
thisSet.resident++
return
}
currentGroupIndex++ // carousel through all groups
if currentGroupIndex >= groupCount {
currentGroupIndex = 0
}
}
}
/*
Inserts all elements from thatSet that are not yet in thisSet into thisSet.
If thatSet is nil, nothing is added to thisSet.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set2 := Empty[int]()
set2.Add(2)
set2.Add(3)
set1.AddAll(set2) // set1 will now contain 1, 2, 3
*/
func (thisSet *Set3[T]) AddAll(thatSet *Set3[T]) {
if thatSet == nil {
return
}
for e := range thatSet.MutableRange() {
thisSet.Add(e)
}
}
/*
Inserts all parameter values that are not yet in thisSet into thisSet.
If the number of parameters is zero, nothing is added to thisSet.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.AddAllOf(2,3) // set will now contain 1, 2, 3
*/
func (thisSet *Set3[T]) AddAllOf(args ...T) {
if args == nil {
return
}
for _, e := range args {
thisSet.Add(e)
}
}
/*
Inserts all elements from the given data array that are not yet in thisSet into thisSet.
If data is nil, nothing is added to thisSet.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.AddAllFromArray([]int{2,3}]) // set will now contain 1, 2, 3
*/
func (thisSet *Set3[T]) AddAllFromArray(data []T) {
if data == nil {
return
}
for _, e := range data {
thisSet.Add(e)
}
}
/*
Creates a new Set3 as a mathematical union of the elements from thisSet and thatSet.
If thatSet is nil, Unite returns a clone of thisSet.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set2 := Empty[int]()
set2.Add(2)
set2.Add(3)
u := set1.Unite(set2) // set1 and set2 remain unchanged, u will contain 1, 2, 3
*/
func (thisSet *Set3[T]) Unite(thatSet *Set3[T]) *Set3[T] {
if thatSet == nil {
return thisSet.Clone()
}
potentialSize := thisSet.Size() + thatSet.Size()
result := EmptyWithCapacity[T](potentialSize)
for e := range thisSet.MutableRange() {
result.Add(e)
}
for e := range thatSet.MutableRange() {
result.Add(e)
}
return result
}
func setCTRLat(ctrl, val uint64, pos int) uint64 {
shift := pos << 3 // *8
ctrl &= ^(uint64(0xFF) << shift) // clear byte
ctrl |= val << shift // set byte to given value
return ctrl
}
func isAnElementAt(ctrl uint64, pos int) bool {
shift := pos << 3 // *8
ctrl &= (uint64(0x80) << shift) // clear all other bits
// if a bit is set, the according byte represented either set3Empty or set3Deleted
// -> if ctlr is 0 now, the according position stores a value
return ctrl == 0
}
/*
Removes the given element from thisSet if it is in thisSet, returns whether or not the element was in thisSet.
Example:
set := Empty[int]()
set.Add(1)
set.Remove(2) // nothing happens to set
set.Remove(1) // set will be empty
set.Remove(0) // set will still be empty
*/
func (thisSet *Set3[T]) Remove(element T) bool {
hash := thisSet.hashFunction.Hash(element)
H2 := (hash & 0x0000_0000_0000_007f)
groupCount := uint64(len(thisSet.groupCtrl))
currentGroupIndex := getGroupIndex(hash, groupCount)
for {
ctrl := thisSet.groupCtrl[currentGroupIndex]
H2matches := set3ctlrMatchH2(ctrl, H2)
if H2matches != 0 {
slot := &(thisSet.groupSlot[currentGroupIndex])
for H2matches != 0 {
s := set3nextMatch(&H2matches)
if element == slot[s] {
// found - already in Set3, just return
// optimization: if |m.ctrl[g]| contains any empty
// metadata bytes, we can physically delete |element|
// rather than placing a tombstone.
// The observation is that any probes into group |g|
// would already be terminated by the existing empty
// slot, and therefore reclaiming slot |s| will not
// cause premature termination of probes into |g|.
if set3ctlrMatchEmpty(ctrl) != 0 {
thisSet.groupCtrl[currentGroupIndex] = setCTRLat(ctrl, set3Empty, s)
thisSet.resident--
} else {
thisSet.groupCtrl[currentGroupIndex] = setCTRLat(ctrl, set3Deleted, s)
thisSet.dead++
/*
// unfortunately, this is an invalid optimization, as the algorithm might stop searching for elements to early.
// if they spilled over in the next group, we unfortunately need all the tumbstones...
if group.ctrl == set3AllDeleted {
group.ctrl = set3AllEmpty
thisSet.dead -= set3groupSize
thisSet.resident -= set3groupSize
}
*/
}
var k T
thisSet.groupSlot[currentGroupIndex][s] = k
return true
}
}
}
// |element| is not in group |g|,
// stop probing if we see an empty slot
emptyMatches := set3ctlrMatchEmpty(ctrl)
if emptyMatches != 0 {
// |element| absent
return false
}
currentGroupIndex++ // linear probing
if currentGroupIndex >= groupCount {
currentGroupIndex = 0
}
}
}
/*
Removes all elements from thisSet that are in thatSet.
If thatSet is nil, nothing happens.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
set1.RemoveAll(set2) // set1 will now contain 1, 2
*/
func (thisSet *Set3[T]) RemoveAll(thatSet *Set3[T]) {
if thatSet == nil {
return
}
for e := range thatSet.MutableRange() {
thisSet.Remove(e)
}
}
/*
Removes all elements from thisSet that are passed as arguments.
If no arguments are passed, nothing happens.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
set.RemoveAllOf(3,4) // set will now contain 1, 2
*/
func (thisSet *Set3[T]) RemoveAllOf(args ...T) {
if args == nil {
return
}
for _, e := range args {
thisSet.Remove(e)
}
}
/*
Removes all elements from thisSet that are in the data array.
If data is nil, nothing happens.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
set.RemoveAllFromArray([]int{3,4}]) // set will now contain 1, 2
*/
func (thisSet *Set3[T]) RemoveAllFromArray(data []T) {
if data == nil {
return
}
for _, e := range data {
thisSet.Remove(e)
}
}
/*
Creates a new Set3 as a mathematical difference between thisSet and thatSet. The result is a new Set3 that contains elements that are in thisSet but not in thatSet.
If thatSet is nil, Subtract returns a clone of thisSet.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
d := set1.Subtract(set2) // set1 and set2 are not altered, d will contain 1, 2
*/
func (thisSet *Set3[T]) Subtract(thatSet *Set3[T]) *Set3[T] {
if thatSet == nil {
return thisSet.Clone()
}
potentialSize := thisSet.Size()
result := EmptyWithCapacity[T](potentialSize)
for e := range thisSet.MutableRange() {
if !thatSet.Contains(e) {
result.Add(e)
}
}
return result
}
/*
Clear removes all elements from thisSet.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Clear() // set will be empty, Count() will return 0
*/
func (thisSet *Set3[T]) Clear() {
// var k T
for grpidx := range len(thisSet.groupCtrl) {
thisSet.groupCtrl[grpidx] = set3AllEmpty
/*
for j := range set3groupSize {
thisSet.groupSlot[grpidx][j] = k
}
*/
}
thisSet.resident, thisSet.dead = 0, 0
}
/*
Creates a new Set3 as a mathematical intersection between this and that. The result is a new Set3 that contains elements that are in both sets.
If thatSet is nil, Intersect returns an empty Set3.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
intersect := set1.Intersect(set2) // set1 and set2 are not altered, intersect will contain 3
*/
func (thisSet *Set3[T]) Intersect(thatSet *Set3[T]) *Set3[T] {
if thatSet == nil {
return Empty[T]()
}
var smallerSet *Set3[T]
var biggerSet *Set3[T]
if thisSet.Size() < thatSet.Size() {
smallerSet = thisSet
biggerSet = thatSet
} else {
smallerSet = thatSet
biggerSet = thisSet
}
potentialSize := smallerSet.Size()
result := EmptyWithCapacity[T](potentialSize)
for e := range smallerSet.ImmutableRange() {
if biggerSet.Contains(e) {
result.Add(e)
}
}
return result
}
/*
Creates a new Set3 as a mathematical intersection between thisSet and the elements of the data array. The result is a new Set3.
If data is nil, IntersectWithArray returns an empty Set3.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
intersect := set.IntersectWithArray([]int{3,4}]) // set1 and set2 are not altered, intersect will contain 3
*/
func (thisSet *Set3[T]) IntersectWithArray(data []T) *Set3[T] {
if data == nil {
return Empty[T]()
}
var potentialSize uint32
if thisSet.Size() < uint32(len(data)) { //nolint:gosec
potentialSize = thisSet.Size()
} else {
potentialSize = uint32(len(data)) //nolint:gosec
}
result := EmptyWithCapacity[T](potentialSize)
for _, e := range data {
if thisSet.Contains(e) {
result.Add(e)
}
}
return result
}
/*
Checks if thisSet contains any element that is also present in thatSet. This function also provides a quick way to check if two Set3 are disjoint (i.e. !ContainsAny).
Returns false if thatSet is nil.
Example:
set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(0)
set2.Add(1)
b := set1.ContainsAny(set2) // b will be true
*/
func (thisSet *Set3[T]) ContainsAny(thatSet *Set3[T]) bool {
if thatSet == nil {
return false
}
var smallerSet *Set3[T]
var biggerSet *Set3[T]
if thisSet.Size() < thatSet.Size() {
smallerSet = thisSet
biggerSet = thatSet
} else {
smallerSet = thatSet
biggerSet = thisSet
}
for e := range smallerSet.ImmutableRange() {
if biggerSet.Contains(e) {
return true
}
}
return false
}
/*
Checks if thisSet contains any of the given argument values.
Returns false if the number of arguments is zero.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set1.ContainsAnyOf(4, 5, 6) // b will be false
*/
func (thisSet *Set3[T]) ContainsAnyOf(args ...T) bool {
if args == nil {
return false
}
for _, d := range args {
if thisSet.Contains(d) {
return true
}
}
return false
}
/*
Checks if thisSet contains any element fromthe given data array.
Returns false if data is nil.
Example:
set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set1.ContainsAnyFromArray([]int{4, 5, 6}) // b will be false
*/
func (thisSet *Set3[T]) ContainsAnyFromArray(data []T) bool {
if data == nil {
return false
}
for _, d := range data {
if thisSet.Contains(d) {