-
Notifications
You must be signed in to change notification settings - Fork 0
/
ordered.go
84 lines (62 loc) · 1.16 KB
/
ordered.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package set
import "slices"
type ordered[T comparable] struct {
set Set[T]
order []T
}
// NewOrdered create empty ordered set for given type.
func NewOrdered[T comparable]() Set[T] {
return &ordered[T]{
set: NewUnordered[T](),
order: []T{},
}
}
func (o *ordered[T]) Add(v T) bool {
if !o.set.Add(v) {
return false
}
o.order = append(o.order, v)
return true
}
func (o *ordered[T]) Del(v T) {
prev := o.set.Len()
o.set.Del(v)
if o.set.Len() != prev {
idx := slices.Index(o.order, v)
o.order = slices.Clip(slices.Delete(o.order, idx, idx+1))
}
}
func (o *ordered[T]) Clear() {
o.set.Clear()
clear(o.order)
}
func (o *ordered[T]) Len() int {
return o.set.Len()
}
func (o *ordered[T]) Has(v T) (ok bool) {
return o.set.Has(v)
}
func (o *ordered[T]) Iter(it func(T) bool) {
for _, v := range o.order {
if !it(v) {
break
}
}
}
func (o *ordered[T]) Clone() (rv Set[T]) {
rv = NewOrdered[T]()
o.Iter(func(v T) bool {
rv.Add(v)
return true
})
return rv
}
func (o *ordered[T]) Pop() (v T, ok bool) {
ln := o.Len()
if ln < 1 {
return v, false
}
v, o.order = o.order[ln-1], o.order[:ln-1]
o.set.Del(v)
return v, true
}