blob: 39f97eac32c7a1497d8a44bafa38901593099529 (
plain)
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
|
package rangemap
type RangeMap[D any] struct {
ranges []rangeEntry
data []D
}
func New[D any]() RangeMap[D] {
return RangeMap[D]{
ranges: []rangeEntry{},
}
}
func (rm *RangeMap[D]) AppendToLast(to int, data D) bool {
if to < 0 {
return false
}
from := 0
if len(rm.ranges) != 0 {
last := rm.ranges[len(rm.ranges)-1]
if last.to >= to {
return false
}
from = last.to + 1
}
rm.ranges = append(rm.ranges, rangeEntry{
from: from,
to: to,
})
rm.data = append(rm.data, data)
return true
}
func (rm *RangeMap[D]) Get(i int) (*D, bool) {
left := 0
right := len(rm.ranges) - 1
for left <= right {
mid := (left + right) / 2
entry := rm.ranges[mid]
if i < entry.from {
right = mid - 1
} else if i > entry.to {
left = mid + 1
} else {
return &rm.data[mid], true
}
}
return nil, false
}
func (rm *RangeMap[D]) Len() int {
return len(rm.ranges)
}
type rangeEntry struct {
from int
to int
}
|
