This repository has been archived by the owner on Jan 8, 2019. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 47
/
sorted.go
107 lines (87 loc) · 1.67 KB
/
sorted.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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package set
type SortedStrings struct {
indexes map[string]int
keys []string
}
func NewSortedStrings() SortedStrings {
return SortedStrings{
indexes: make(map[string]int),
keys: make([]string, 0),
}
}
func (s *SortedStrings) Put(key string) {
if s.HasKey(key) {
return
}
s.indexes[key] = len(s.keys)
s.keys = append(s.keys, key)
}
func (s *SortedStrings) Remove(key string) {
index, has := s.indexes[key]
if !has {
return
}
delete(s.indexes, key)
for l := len(s.keys); index < l-1; index++ {
k := s.keys[index+1]
s.keys[index] = k
s.indexes[k] = index
}
s.keys = s.keys[:index]
}
func (s *SortedStrings) HasKey(key string) bool {
_, has := s.indexes[key]
return has
}
func (s *SortedStrings) Keys() []string {
return s.keys
}
func (s *SortedStrings) Clear() {
for k := range s.indexes {
delete(s.indexes, k)
}
s.keys = s.keys[:0]
}
type SortedInts struct {
indexes map[int]int
keys []int
}
func (s *SortedInts) Put(key int) {
if s.HasKey(key) {
return
}
s.indexes[key] = len(s.keys)
s.keys = append(s.keys, key)
}
func (s *SortedInts) Remove(key int) {
index, has := s.indexes[key]
if !has {
return
}
delete(s.indexes, key)
for l := len(s.keys); index < l-1; index++ {
k := s.keys[index+1]
s.keys[index] = k
s.indexes[k] = index
}
s.keys = s.keys[:index]
}
func (s *SortedInts) HasKey(key int) bool {
_, has := s.indexes[key]
return has
}
func (s *SortedInts) Keys() []int {
return s.keys
}
func NewSortedInts() SortedInts {
return SortedInts{
indexes: make(map[int]int),
keys: make([]int, 0),
}
}
func (s *SortedInts) Clear() {
for k := range s.indexes {
delete(s.indexes, k)
}
s.keys = s.keys[:0]
}