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
|
package gtreap
type Treap struct {
compare Compare
root *node
}
// Compare returns an integer comparing the two items
// lexicographically. The result will be 0 if a==b, -1 if a < b, and
// +1 if a > b.
type Compare func(a, b interface{}) int
// Item can be anything.
type Item interface{}
type node struct {
item Item
priority int
left *node
right *node
}
func NewTreap(c Compare) *Treap {
return &Treap{compare: c, root: nil}
}
func (t *Treap) Min() Item {
n := t.root
if n == nil {
return nil
}
for n.left != nil {
n = n.left
}
return n.item
}
func (t *Treap) Max() Item {
n := t.root
if n == nil {
return nil
}
for n.right != nil {
n = n.right
}
return n.item
}
func (t *Treap) Get(target Item) Item {
n := t.root
for n != nil {
c := t.compare(target, n.item)
if c < 0 {
n = n.left
} else if c > 0 {
n = n.right
} else {
return n.item
}
}
return nil
}
// Note: only the priority of the first insert of an item is used.
// Priorities from future updates on already existing items are
// ignored. To change the priority for an item, you need to do a
// Delete then an Upsert.
func (t *Treap) Upsert(item Item, itemPriority int) *Treap {
r := t.union(t.root, &node{item: item, priority: itemPriority})
return &Treap{compare: t.compare, root: r}
}
func (t *Treap) union(this *node, that *node) *node {
if this == nil {
return that
}
if that == nil {
return this
}
if this.priority > that.priority {
left, middle, right := t.split(that, this.item)
if middle == nil {
return &node{
item: this.item,
priority: this.priority,
left: t.union(this.left, left),
right: t.union(this.right, right),
}
}
return &node{
item: middle.item,
priority: this.priority,
left: t.union(this.left, left),
right: t.union(this.right, right),
}
}
// We don't use middle because the "that" has precendence.
left, _, right := t.split(this, that.item)
return &node{
item: that.item,
priority: that.priority,
left: t.union(left, that.left),
right: t.union(right, that.right),
}
}
// Splits a treap into two treaps based on a split item "s".
// The result tuple-3 means (left, X, right), where X is either...
// nil - meaning the item s was not in the original treap.
// non-nil - returning the node that had item s.
// The tuple-3's left result treap has items < s,
// and the tuple-3's right result treap has items > s.
func (t *Treap) split(n *node, s Item) (*node, *node, *node) {
if n == nil {
return nil, nil, nil
}
c := t.compare(s, n.item)
if c == 0 {
return n.left, n, n.right
}
if c < 0 {
left, middle, right := t.split(n.left, s)
return left, middle, &node{
item: n.item,
priority: n.priority,
left: right,
right: n.right,
}
}
left, middle, right := t.split(n.right, s)
return &node{
item: n.item,
priority: n.priority,
left: n.left,
right: left,
}, middle, right
}
func (t *Treap) Delete(target Item) *Treap {
left, _, right := t.split(t.root, target)
return &Treap{compare: t.compare, root: t.join(left, right)}
}
// All the items from this are < items from that.
func (t *Treap) join(this *node, that *node) *node {
if this == nil {
return that
}
if that == nil {
return this
}
if this.priority > that.priority {
return &node{
item: this.item,
priority: this.priority,
left: this.left,
right: t.join(this.right, that),
}
}
return &node{
item: that.item,
priority: that.priority,
left: t.join(this, that.left),
right: that.right,
}
}
type ItemVisitor func(i Item) bool
// Visit items greater-than-or-equal to the pivot.
func (t *Treap) VisitAscend(pivot Item, visitor ItemVisitor) {
t.visitAscend(t.root, pivot, visitor)
}
func (t *Treap) visitAscend(n *node, pivot Item, visitor ItemVisitor) bool {
if n == nil {
return true
}
if t.compare(pivot, n.item) <= 0 {
if !t.visitAscend(n.left, pivot, visitor) {
return false
}
if !visitor(n.item) {
return false
}
}
return t.visitAscend(n.right, pivot, visitor)
}
|
