/
sortedmap.go
162 lines (129 loc) · 3.57 KB
/
sortedmap.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
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
// Copyright 2018 the u-root Authors. All rights reserved
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package sortedmap
import (
"errors"
"sort"
"sync"
)
var ErrNoSuchKey = errors.New("no such key exists")
// SearchInt64s implements sort.SearchInts for int64.
func SearchInt64s(a []int64, x int64) int {
return sort.Search(len(a), func(i int) bool { return a[i] >= x })
}
// sortedSlice is a sorted slice of unique int64s.
type sortedSlice []int64
// Insert inserts value v int64o the appropriate location in the slice.
func (s *sortedSlice) Insert(v int64) {
// Search returns the index to insert v if it exists,
// so check that it doesn't exist before adding it.
i := SearchInt64s(*s, v)
if i < len(*s) && (*s)[i] == v {
return
}
// Grow the slice by one element.
*s = append(*s, 0)
// Move the upper part of the slice out of the way and open a hole.
copy((*s)[i+1:], (*s)[i:])
// Store the new value.
(*s)[i] = v
}
// Delete deletes the value v from the slice.
func (s *sortedSlice) Delete(v int64) {
// Search returns the index to insert v if it doesn't exist,
// so check that it exists before deleting it.
i := SearchInt64s(*s, v)
if i >= len(*s) || (*s)[i] != v {
return
}
*s = append((*s)[:i], (*s)[i+1:]...)
}
// Search returns the index of v in the slice, if exists is true.
// Otherwise, it is the location v would be inserted. All indices less
// than i contain values less than v.
func (s *sortedSlice) Search(v int64) (i int, exists bool) {
i = SearchInt64s(*s, v)
// Does v exist, or is this just the location to insert it.
if i < len(*s) && (*s)[i] == v {
exists = true
}
return
}
// Map is a sorted map[int64]int64.
type Map struct {
// m is the underlying map store
m map[int64]int64
// k is the sorted list of keys
k sortedSlice
// mu locks the Map.
mu sync.RWMutex
}
// Insert inserts a key, value pair.
func (m *Map) Insert(k, v int64) {
m.mu.Lock()
defer m.mu.Unlock()
// Delete any duplicate entry.
m.deleteImpl(k)
m.m[k] = v
m.k.Insert(k)
}
// Delete key from map, must be called with mu held.
func (m *Map) deleteImpl(k int64) {
delete(m.m, k)
m.k.Delete(k)
}
// Delete deletes the value stored at k from the map.
func (m *Map) Delete(k int64) {
m.mu.Lock()
defer m.mu.Unlock()
m.deleteImpl(k)
}
// Get gets the value at a specific key.
func (m *Map) Get(k int64) (v int64, ok bool) {
m.mu.RLock()
defer m.mu.RUnlock()
v, ok = m.m[k]
return
}
// NearestLessEqual returns the nearest key, value pair that exists in
// the map with a key <= want.
func (m *Map) NearestLessEqual(want int64) (key, value int64, err error) {
m.mu.RLock()
defer m.mu.RUnlock()
i, exists := m.k.Search(want)
// Key already exists in the map.
if exists {
return want, m.m[want], nil
}
// i - 1 contains the nearest key less than the desired key.
if i < 1 {
return 0, 0, ErrNoSuchKey
}
key = m.k[i-1]
value = m.m[key]
return key, value, nil
}
// NearestGreater returns the nearest key, value pair that exists in
// the map with a key > want.
func (m *Map) NearestGreater(want int64) (key, value int64, err error) {
m.mu.RLock()
defer m.mu.RUnlock()
// By searching for want + 1, we the lowest possible index for
// want + 1, which must either not exist or contain something
// larger than want.
i, _ := m.k.Search(want + 1)
// i is off the end of the slice, there is nothing > want.
if i >= len(m.k) {
return 0, 0, ErrNoSuchKey
}
key = m.k[i]
value = m.m[key]
return key, value, nil
}
func NewMap() Map {
return Map{
m: make(map[int64]int64),
k: make(sortedSlice, 0),
}
}