1package gtreap
2
3import (
4	"bytes"
5	"testing"
6)
7
8func stringCompare(a, b interface{}) int {
9	return bytes.Compare([]byte(a.(string)), []byte(b.(string)))
10}
11
12func TestTreap(t *testing.T) {
13	x := NewTreap(stringCompare)
14	if x == nil {
15		t.Errorf("expected NewTreap to work")
16	}
17
18	tests := []struct {
19		op  string
20		val string
21		pri int
22		exp string
23	}{
24		{"get", "not-there", -1, "NIL"},
25		{"ups", "a", 100, ""},
26		{"get", "a", -1, "a"},
27		{"ups", "b", 200, ""},
28		{"get", "a", -1, "a"},
29		{"get", "b", -1, "b"},
30		{"ups", "c", 300, ""},
31		{"get", "a", -1, "a"},
32		{"get", "b", -1, "b"},
33		{"get", "c", -1, "c"},
34		{"get", "not-there", -1, "NIL"},
35		{"ups", "a", 400, ""},
36		{"get", "a", -1, "a"},
37		{"get", "b", -1, "b"},
38		{"get", "c", -1, "c"},
39		{"get", "not-there", -1, "NIL"},
40		{"del", "a", -1, ""},
41		{"get", "a", -1, "NIL"},
42		{"get", "b", -1, "b"},
43		{"get", "c", -1, "c"},
44		{"get", "not-there", -1, "NIL"},
45		{"ups", "a", 10, ""},
46		{"get", "a", -1, "a"},
47		{"get", "b", -1, "b"},
48		{"get", "c", -1, "c"},
49		{"get", "not-there", -1, "NIL"},
50		{"del", "a", -1, ""},
51		{"del", "b", -1, ""},
52		{"del", "c", -1, ""},
53		{"get", "a", -1, "NIL"},
54		{"get", "b", -1, "NIL"},
55		{"get", "c", -1, "NIL"},
56		{"get", "not-there", -1, "NIL"},
57		{"del", "a", -1, ""},
58		{"del", "b", -1, ""},
59		{"del", "c", -1, ""},
60		{"get", "a", -1, "NIL"},
61		{"get", "b", -1, "NIL"},
62		{"get", "c", -1, "NIL"},
63		{"get", "not-there", -1, "NIL"},
64		{"ups", "a", 10, ""},
65		{"get", "a", -1, "a"},
66		{"get", "b", -1, "NIL"},
67		{"get", "c", -1, "NIL"},
68		{"get", "not-there", -1, "NIL"},
69		{"ups", "b", 1000, "b"},
70		{"del", "b", -1, ""}, // cover join that is nil
71		{"ups", "b", 20, "b"},
72		{"ups", "c", 12, "c"},
73		{"del", "b", -1, ""}, // cover join second return
74		{"ups", "a", 5, "a"}, // cover upsert existing with lower priority
75	}
76
77	for testIdx, test := range tests {
78		switch test.op {
79		case "get":
80			i := x.Get(test.val)
81			if i != test.exp && !(i == nil && test.exp == "NIL") {
82				t.Errorf("test: %v, on Get, expected: %v, got: %v", testIdx, test.exp, i)
83			}
84		case "ups":
85			x = x.Upsert(test.val, test.pri)
86		case "del":
87			x = x.Delete(test.val)
88		}
89	}
90}
91
92func load(x *Treap, arr []string) *Treap {
93	for i, s := range arr {
94		x = x.Upsert(s, i)
95	}
96	return x
97}
98
99func visitExpect(t *testing.T, x *Treap, start string, arr []string) {
100	n := 0
101	x.VisitAscend(start, func(i Item) bool {
102		if i.(string) != arr[n] {
103			t.Errorf("expected visit item: %v, saw: %v", arr[n], i)
104		}
105		n++
106		return true
107	})
108	if n != len(arr) {
109		t.Errorf("expected # visit callbacks: %v, saw: %v", len(arr), n)
110	}
111}
112
113func TestVisit(t *testing.T) {
114	x := NewTreap(stringCompare)
115	visitExpect(t, x, "a", []string{})
116
117	x = load(x, []string{"e", "d", "c", "c", "a", "b", "a"})
118
119	visitX := func() {
120		visitExpect(t, x, "a", []string{"a", "b", "c", "d", "e"})
121		visitExpect(t, x, "a1", []string{"b", "c", "d", "e"})
122		visitExpect(t, x, "b", []string{"b", "c", "d", "e"})
123		visitExpect(t, x, "b1", []string{"c", "d", "e"})
124		visitExpect(t, x, "c", []string{"c", "d", "e"})
125		visitExpect(t, x, "c1", []string{"d", "e"})
126		visitExpect(t, x, "d", []string{"d", "e"})
127		visitExpect(t, x, "d1", []string{"e"})
128		visitExpect(t, x, "e", []string{"e"})
129		visitExpect(t, x, "f", []string{})
130	}
131	visitX()
132
133	var y *Treap
134	y = x.Upsert("f", 1)
135	y = y.Delete("a")
136	y = y.Upsert("cc", 2)
137	y = y.Delete("c")
138
139	visitExpect(t, y, "a", []string{"b", "cc", "d", "e", "f"})
140	visitExpect(t, y, "a1", []string{"b", "cc", "d", "e", "f"})
141	visitExpect(t, y, "b", []string{"b", "cc", "d", "e", "f"})
142	visitExpect(t, y, "b1", []string{"cc", "d", "e", "f"})
143	visitExpect(t, y, "c", []string{"cc", "d", "e", "f"})
144	visitExpect(t, y, "c1", []string{"cc", "d", "e", "f"})
145	visitExpect(t, y, "d", []string{"d", "e", "f"})
146	visitExpect(t, y, "d1", []string{"e", "f"})
147	visitExpect(t, y, "e", []string{"e", "f"})
148	visitExpect(t, y, "f", []string{"f"})
149	visitExpect(t, y, "z", []string{})
150
151	// an uninitialized treap
152	z := NewTreap(stringCompare)
153
154	// a treap to force left traversal of min
155	lmt := NewTreap(stringCompare)
156	lmt = lmt.Upsert("b", 2)
157	lmt = lmt.Upsert("a", 1)
158
159	// The x treap should be unchanged.
160	visitX()
161
162	if x.Min() != "a" {
163		t.Errorf("expected min of a")
164	}
165	if x.Max() != "e" {
166		t.Errorf("expected max of d")
167	}
168	if y.Min() != "b" {
169		t.Errorf("expected min of b")
170	}
171	if y.Max() != "f" {
172		t.Errorf("expected max of f")
173	}
174	if z.Min() != nil {
175		t.Errorf("expected min of nil")
176	}
177	if z.Max() != nil {
178		t.Error("expected max of nil")
179	}
180	if lmt.Min() != "a" {
181		t.Errorf("expected min of a")
182	}
183	if lmt.Max() != "b" {
184		t.Errorf("expeced max of b")
185	}
186}
187
188func visitExpectEndAtC(t *testing.T, x *Treap, start string, arr []string) {
189	n := 0
190	x.VisitAscend(start, func(i Item) bool {
191		if stringCompare(i, "c") > 0 {
192			return false
193		}
194		if i.(string) != arr[n] {
195			t.Errorf("expected visit item: %v, saw: %v", arr[n], i)
196		}
197		n++
198		return true
199	})
200	if n != len(arr) {
201		t.Errorf("expected # visit callbacks: %v, saw: %v", len(arr), n)
202	}
203}
204
205func TestVisitEndEarly(t *testing.T) {
206	x := NewTreap(stringCompare)
207	visitExpectEndAtC(t, x, "a", []string{})
208
209	x = load(x, []string{"e", "d", "c", "c", "a", "b", "a", "e"})
210
211	visitX := func() {
212		visitExpectEndAtC(t, x, "a", []string{"a", "b", "c"})
213		visitExpectEndAtC(t, x, "a1", []string{"b", "c"})
214		visitExpectEndAtC(t, x, "b", []string{"b", "c"})
215		visitExpectEndAtC(t, x, "b1", []string{"c"})
216		visitExpectEndAtC(t, x, "c", []string{"c"})
217		visitExpectEndAtC(t, x, "c1", []string{})
218		visitExpectEndAtC(t, x, "d", []string{})
219		visitExpectEndAtC(t, x, "d1", []string{})
220		visitExpectEndAtC(t, x, "e", []string{})
221		visitExpectEndAtC(t, x, "f", []string{})
222	}
223	visitX()
224}
225
226func TestPriorityAfterUpsert(t *testing.T) {
227	// See https://github.com/steveyen/gtreap/issues/3 found by icexin.
228
229	var check func(n *node, level int, expectedPriority map[string]int)
230	check = func(n *node, level int, expectedPriority map[string]int) {
231		if n == nil {
232			return
233		}
234		if n.priority != expectedPriority[n.item.(string)] {
235			t.Errorf("wrong priority")
236		}
237		check(n.left, level+1, expectedPriority)
238		check(n.right, level+1, expectedPriority)
239	}
240
241	s := NewTreap(stringCompare)
242	s = s.Upsert("m", 20)
243	s = s.Upsert("l", 18)
244	s = s.Upsert("n", 19)
245
246	check(s.root, 0, map[string]int{
247		"m": 20,
248		"l": 18,
249		"n": 19,
250	})
251
252	s = s.Upsert("m", 4)
253
254	check(s.root, 0, map[string]int{
255		"m": 20,
256		"l": 18,
257		"n": 19,
258	})
259}
260