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
|
// Copyright (C) 2015 The Android Open Source Project
//
// 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 interval
import "sort"
// intersection holds the full set of calculated information when testing for
// list intersections
type intersection struct {
overlap int // the count of intervals that overlap the span
lowIndex int // the index of the low interval
low U64Span // the span at the low index
intersectsLow bool // whether the low span intersected, or was just before
highIndex int // the index of the high interval
high U64Span // the span at the high index
intersectsHigh bool // whether the high span intersected, or was just after
}
// findSpanFor searches a list for the span that encompasses a value, returning
// the index if found, or -1 otherwise
func findSpanFor(l List, value uint64) int {
index := sort.Search(l.Length(), func(at int) bool {
return value < l.GetSpan(at).Start
})
index--
if index >= 0 {
if value < l.GetSpan(index).End {
return index
}
}
return -1
}
// search the list for the first interval that matches the predicate.
// If no interval matches, it will return the list length.
func search(l List, t Predicate) int {
i := 0
j := l.Length()
for i < j {
h := i + (j-i)/2
if !t(l.GetSpan(h)) {
i = h + 1
} else {
j = h
}
}
return i
}
// intersect a span with a list, calculating the intersection span and interval range
func (s *intersection) intersect(l List, span U64Span) {
beforeLen := search(l, func(test U64Span) bool {
return span.Start < test.End
})
afterIndex := search(l, func(test U64Span) bool {
return span.End <= test.Start
})
if afterIndex < beforeLen {
afterIndex, beforeLen = beforeLen, afterIndex
}
s.lowIndex = beforeLen
s.highIndex = afterIndex - 1
s.overlap = afterIndex - beforeLen
s.intersectsLow = false
s.intersectsHigh = false
if s.overlap > 0 {
s.low = l.GetSpan(s.lowIndex)
s.intersectsLow = s.low.Start < span.Start
s.high = l.GetSpan(s.highIndex)
s.intersectsHigh = span.End < s.high.End
}
}
// merges a new span into a list, returning the index of the span
func merge(l List, span U64Span) int {
s := intersection{}
s.intersect(l, span)
adjust(l, s.lowIndex, 1-s.overlap)
if s.intersectsLow {
span.Start = s.low.Start
}
if s.intersectsHigh {
span.End = s.high.End
}
l.SetSpan(s.lowIndex, span)
return s.lowIndex
}
// cut slices a hole matching the specified span from a list.
// If add is true, it puts a new span in that space
// It is used to implement both Remove and Replace
func cut(l List, span U64Span, add bool) (int, U64Span) {
s := intersection{}
s.intersect(l, span)
if s.overlap == 0 {
if add {
adjust(l, s.lowIndex, 1)
}
return s.lowIndex, span
}
insertLen := 0
insertPoint := s.lowIndex
if s.intersectsLow {
s.low.End = span.Start
insertLen++
insertPoint++
}
if add {
insertLen++
}
if s.intersectsHigh {
s.high.Start = span.End
insertLen++
}
delta := insertLen - s.overlap
adjust(l, insertPoint, delta)
if s.intersectsLow {
l.SetSpan(s.lowIndex, s.low)
}
if s.intersectsHigh {
l.SetSpan(s.lowIndex+insertLen-1, s.high)
}
return insertPoint, span
}
// adjust implements list size adjustment logic, given a delta in size, and an
// index to adjust at
func adjust(l List, at, delta int) {
if delta == 0 {
return
}
oldLen := l.Length()
newLen := oldLen + delta
if delta > 0 {
l.Resize(newLen)
}
copyStart := at - delta
copyTo := at
if copyStart < 0 {
copyTo -= copyStart
copyStart = 0
}
l.Copy(copyTo, copyStart, newLen-copyTo)
if delta < 0 {
l.Resize(newLen)
}
}
|
