forked from cockroachdb/cockroach
-
Notifications
You must be signed in to change notification settings - Fork 0
/
interval.go
202 lines (177 loc) · 7.44 KB
/
interval.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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
// Copyright ©2012 The bíogo 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 interval provides two implementations for an interval tree. One is
// based on an augmented Left-Leaning Red Black tree. The other is based on an
// augmented BTree.
package interval
import (
"bytes"
"errors"
"fmt"
)
// ErrInvertedRange is returned if an interval is used where the start value is greater
// than the end value.
var ErrInvertedRange = errors.New("interval: inverted range")
// ErrEmptyRange is returned if an interval is used where the start value is equal
// to the end value.
var ErrEmptyRange = errors.New("interval: empty range")
func rangeError(r Range) error {
switch r.Start.Compare(r.End) {
case 1:
return ErrInvertedRange
case 0:
return ErrEmptyRange
default:
return nil
}
}
// A Range is a type that describes the basic characteristics of an interval.
type Range struct {
Start, End Comparable
}
// Equal returns whether the two ranges are equal.
func (r Range) Equal(other Range) bool {
return r.Start.Equal(other.Start) && r.End.Equal(other.End)
}
// String implements the Stringer interface.
func (r Range) String() string {
return fmt.Sprintf("{%x-%x}", r.Start, r.End)
}
// Overlapper specifies the overlapping relationship.
type Overlapper interface {
// Overlap checks whether two ranges overlap.
Overlap(Range, Range) bool
}
type inclusiveOverlapper struct{}
// Overlap checks where a and b overlap in the inclusive way.
func (overlapper inclusiveOverlapper) Overlap(a Range, b Range) bool {
return a.Start.Compare(b.End) <= 0 && b.Start.Compare(a.End) <= 0
}
// InclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace
// in the inclusive way. "inclusive" means that both start and end keys treated as inclusive values.
var InclusiveOverlapper = inclusiveOverlapper{}
type exclusiveOverlapper struct{}
// Overlap checks where a and b overlap in the exclusive way.
func (overlapper exclusiveOverlapper) Overlap(a Range, b Range) bool {
return a.Start.Compare(b.End) < 0 && b.Start.Compare(a.End) < 0
}
// ExclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace
// in the exclusive. "exclusive" means that the start keys are treated as inclusive and the end keys
// are treated as exclusive.
var ExclusiveOverlapper = exclusiveOverlapper{}
// An Interface is a type that can be inserted into an interval tree.
type Interface interface {
Range() Range
// Returns a unique ID for the element.
// TODO(nvanbenschoten): Should this be changed to an int64?
ID() uintptr
}
// Compare returns a value indicating the sort order relationship between a and b. The comparison is
// performed lexicographically on (a.Range().Start, a.ID()) and (b.Range().Start, b.ID()) tuples
// where Range().Start is more significant that ID().
//
// Given c = Compare(a, b):
//
// c == -1 if (a.Range().Start, a.ID()) < (b.Range().Start, b.ID());
// c == 0 if (a.Range().Start, a.ID()) == (b.Range().Start, b.ID()); and
// c == 1 if (a.Range().Start, a.ID()) > (b.Range().Start, b.ID()).
//
// "c == 0" is equivalent to "Equal(a, b) == true".
func Compare(a, b Interface) int {
startCmp := a.Range().Start.Compare(b.Range().Start)
if startCmp != 0 {
return startCmp
}
aID := a.ID()
bID := b.ID()
if aID < bID {
return -1
} else if aID > bID {
return 1
} else {
return 0
}
}
// Equal returns a boolean indicating whethter the given Interfaces are equal to each other. If
// "Equal(a, b) == true", "a.Range().End == b.Range().End" must hold. Otherwise, the interval tree
// behavior is undefined. "Equal(a, b) == true" is equivalent to "Compare(a, b) == 0". But the
// former has measurably better performance than the latter. So Equal should be used when only
// equality state is needed.
func Equal(a, b Interface) bool {
return a.Range().Start.Equal(b.Range().Start) && a.ID() == b.ID()
}
// A Comparable is a type that describes the ends of a Range.
type Comparable []byte
// Compare returns a value indicating the sort order relationship between the
// receiver and the parameter.
//
// Given c = a.Compare(b):
// c == -1 if a < b;
// c == 0 if a == b; and
// c == 1 if a > b.
//
func (c Comparable) Compare(o Comparable) int {
return bytes.Compare(c, o)
}
// Equal returns a boolean indicating if the given comparables are equal to
// each other. Note that this has measurably better performance than
// Compare() == 0, so it should be used when only equality state is needed.
func (c Comparable) Equal(o Comparable) bool {
return bytes.Equal(c, o)
}
// An Operation is a function that operates on an Interface. If done is returned true, the
// Operation is indicating that no further work needs to be done and so the DoMatching function
// should traverse no further.
type Operation func(Interface) (done bool)
// Tree is an interval tree. For all the functions which have a fast argment,
// fast being true means a fast operation which does not adjust node ranges. If
// fast is false, node ranges are adjusted.
type Tree interface {
// AdjustRanges fixes range fields for all nodes in the tree. This must be
// called before Get, Do or DoMatching* is used if fast insertion or deletion
// has been performed.
AdjustRanges()
// Len returns the number of intervals stored in the Tree.
Len() int
// Get returns a slice of Interfaces that overlap r in the tree. The slice is
// sorted nondecreasingly by interval start.
Get(r Range) []Interface
// GetWithOverlapper returns a slice of Interfaces that overlap r in the tree
// using the provided overlapper function. The slice is sorted nondecreasingly
// by interval start.
GetWithOverlapper(r Range, overlapper Overlapper) []Interface
// Insert inserts the Interface e into the tree. Insertions may replace an
// existing Interface which is equal to the Interface e.
Insert(e Interface, fast bool) error
// Delete deletes the Interface e if it exists in the tree. The deleted
// Interface is equal to the Interface e.
Delete(e Interface, fast bool) error
// Do performs fn on all intervals stored in the tree. The traversal is done
// in the nondecreasing order of interval start. A boolean is returned
// indicating whether the traversal was interrupted by an Operation returning
// true. If fn alters stored intervals' sort relationships, future tree
// operation behaviors are undefined.
Do(fn Operation) bool
// DoMatching performs fn on all intervals stored in the tree that overlaps r.
// The traversal is done in the nondecreasing order of interval start. A
// boolean is returned indicating whether the traversal was interrupted by an
// Operation returning true. If fn alters stored intervals' sort
// relationships, future tree operation behaviors are undefined.
DoMatching(fn Operation, r Range) bool
// Iterator creates an iterator to iterate over all intervals stored in the
// tree, in-order.
Iterator() TreeIterator
}
// TreeIterator iterates over all intervals stored in the interval tree, in-order.
type TreeIterator interface {
// Next returns the current interval stored in the interval tree and moves
// the iterator to the next interval. The method returns false if no intervals
// remain in the interval tree.
Next() (Interface, bool)
}
// NewTree creates a new interval tree with the given overlapper function. It
// uses the augmented Left-Leaning Red Black tree implementation.
func NewTree(overlapper Overlapper) Tree {
return newLLBRTree(overlapper)
}