forked from projectcalico/libcalico-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
stringset.go
70 lines (65 loc) · 2 KB
/
stringset.go
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
// Copyright (c) 2016 Tigera, Inc. All rights reserved.
//
// 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 parser
import "sort"
type StringSet []string
// Contains returns true if a given string in current set
func (ss StringSet) Contains(s string) bool {
if len(ss) == 0 {
// Empty set or nil.
return false
}
// There's at least one item, do a binary chop to find the correct
// entry. [minIdx, maxIdx) defines the (half-open) search interval.
minIdx := 0
maxIdx := len(ss)
for minIdx < (maxIdx - 1) {
// Select the partition index. The loop condition ensures that
// minIdx < partitionIdx < maxIdx so we'll always shrink the
// search interval on each iteration.
partitionIdx := (minIdx + maxIdx) / 2
partition := ss[partitionIdx]
if s < partition {
// target is strictly less than the partition, we can
// move maxIdx down.
maxIdx = partitionIdx
} else {
// Target is >= the partition, move minIdx up.
minIdx = partitionIdx
}
}
// When we exit the loop, minIdx == (maxIdx - 1). Since the interval
// is half-open that means that, if the value is present, it must be at
// minIdx. (minIdx cannot equal maxIdx due to the empty list check
// above and the loop condition.)
return ss[minIdx] == s
}
func ConvertToStringSetInPlace(s []string) StringSet {
if s != nil {
sort.Strings(s)
}
j := 0
var last string
for _, v := range s {
if j != 0 && last == v {
// Same as last value, skip.
continue
}
s[j] = v
j++
last = v
}
s = s[:j]
return StringSet(s)
}