Ticket #263: TestTreap.cobra

File TestTreap.cobra, 10.4 KB (added by hopscc, 14 years ago)

Line
1	# Test run for treap (Tree Heap) Gneric implementation
2	use System.Diagnostics
3	use System.Data
4
5	use Treap
6
7	namespace Test
8
9	#
10	# demonstrates using a key as a separate object
11	#
12	class MyKey implements IComparable
13	var __key as int
14	pro key from var
15
16	cue init(key as int)
17	base.init
18	__key = key
19
20	def compareTo(key as Object) as int
21	if .key > (key to MyKey).key
22	return 1
23	else if .key < (key to MyKey).key
24	return -1
25	return 0
26
27	def toString as String is override
28	return __key.toString
29
30
31	#
32	# Demonstrates using a key embedded with an object
33	#
34	class MyKeyObj implements IComparable
35	var __key as int
36	var __strData as String
37
38	pro key from var
39	pro data from __strData
40
41	cue init(key as int, data as String)
42	base.init
43	.key = key
44	.data = data
45
46	def compareTo(key as Object) as int
47	if .key > (key to MyKeyObj).key
48	return 1
49	else if .key < (key to MyKeyObj).key
50	return -1
51	return 0
52
53	def toString as String is override
54	return .key.toString
55
56
57	class MyObj
58
59	var __myKey as int
60	var __myData as String
61
62	pro key from __myKey
63	pro data from __myData
64
65	cue init(key as int, data as String)
66	base.init
67	.key = key
68	.data = data
69
70	def toString as String is override
71	return '[__myKey]:[__myData]'
72
73
74
75	class TestTreap
76	shared
77	var treapS = Treap<of String, int>()
78
79	var treap as Treap<of MyKey, MyObj>
80	var obj3 = MyObj(0003, "MyObj C")
81	var obj1 = MyObj(0001, "MyObj A")
82	var obj2 = MyObj(0002, "MyObj B")
83	var obj4 = MyObj(0004, "MyObj D")
84	var obj5 = MyObj(0005, "MyObj E")
85
86	var mko3= MyKey(.obj3.key)
87	var mko1= MyKey(.obj1.key)
88	var mko2= MyKey(.obj2.key)
89	var mko4= MyKey(.obj4.key)
90	var mko5= MyKey(.obj5.key)
91
92	def main is shared
93	.testEquality
94	.testString
95
96	# These tests from original C# code - more complex objects
97	.testAdd
98	.testContent
99	.testRemove
100	.testClear
101
102	def testEquality is shared
103	treap2 = Treap<of String, int>()
104	#assert .treapS
105	assert .treapS to Object inherits Treap<of String,int>
106	assert .treapS == .treapS
107	assert .treapS.toString == .treapS.toString
108	assert .treapS.toString.equals(.treapS.toString)
109	#print .treapS.toString
110	#print Treap<of String,int>().toString
111	assert .treapS.getHashCode == .treapS.getHashCode
112
113	assert .treapS.equals(.treapS)
114	assert not .treapS.equals(.treap)
115	#assert .treapS <> treap2
116
117	# test usable as key in dict and in a set
118	s = Dictionary<of Object, Treap<of String,int>>()
119	#s = Dictionary<of Treap<of String,int>, Treap<of String,int>>()
120	s.add(.treapS, .treapS)
121	#s[.treapS] = .treapS
122	assert s.containsKey(.treapS)
123
124	s1 = Dictionary<of Treap<of String,int>, Treap<of String,int>>()
125	s1.add(.treapS, .treapS)
126	#s[.treapS] = .treapS
127	assert s.containsKey(.treapS)
128	s1.clear
129	assert s1.count == 0
130	s1[.treapS] = .treapS
131	assert s1.containsKey(.treapS)
132
133	aset = Set<of Object>()
134	aset.add(.treapS)
135	assert aset.contains(.treapS)
136
137	aset1 = Set<of Treap<of String,int>>()
138	aset1.add(.treapS)
139	assert aset1.contains(.treapS)
140	assert not aset1.contains(treap2)
141
142	def testString is shared
143	.treapS = Treap<of String, int>()
144	assert .treapS.isEmpty
145	assert not .treapS.count
146	.treapS.add( 'hotel', 99)
147	.treapS.add( 'alpha', 1)
148	.treapS.add( 'zebra', 147)
149	assert not .treapS.isEmpty
150	assert .treapS.count == 3
151	assert .treapS.contains('hotel')
152	assert .treapS['hotel'] == 99
153	expect TreapException
154	assert .treapS['nohotel'] == 0
155
156	.treapS.add('hotel', 45)
157	assert .treapS.count == 3
158	assert .treapS.getValue('hotel') == 45
159	assert .treapS['hotel'] == 45
160
161	.treapS['hotel'] = 22
162	assert .treapS.count == 3
163	assert .treapS.getValue('hotel') == 22
164	assert .treapS['hotel'] == 22
165
166	assert .treapS.getMinKey == 'alpha'
167	assert .treapS.getMaxKey == 'zebra'
168
169	expectedKeys = ['alpha', 'hotel', 'zebra']
170	assert .treapS.keys == expectedKeys
171
172	expectedValues = [1, 22, 147]
173	#expectedValues = [1, 22, 140]
174	assert .treapS.values == expectedValues
175
176	exp = {'alpha':1, 'hotel':22, 'zebra':147}
177	n = 0
178	for tn in .treapS.ascendingOrder
179	assert exp.containsKey(tn.key)
180	assert tn.key == expectedKeys[n]
181	assert tn.value == expectedValues[n]
182	n += 1
183
184	n = exp.count-1
185	for tn in .treapS.descendingOrder
186	assert exp.containsKey(tn.key)
187	assert tn.key == expectedKeys[n]
188	assert tn.value == expectedValues[n]
189	n -= 1
190
191	n = 0
192	for tn in .treapS
193	assert exp.containsKey(tn.key)
194	assert tn.key == expectedKeys[n]
195	assert tn.value == expectedValues[n]
196	n += 1
197
198	e = .treapS.getEnumerator
199	n = 0
200	while e.moveNext
201	tn = e.current
202	assert exp.containsKey(tn.key)
203	assert tn.key == expectedKeys[n]
204	assert tn.value == expectedValues[n]
205	n += 1
206
207
208	arr = KeyValuePair<of String,int>[](5)
209	.treapS.copyTo(arr,0)
210	assert arr[0].key == 'alpha'
211	assert arr[1].key == 'hotel'
212	assert arr[2].key == 'zebra'
213
214	.treapS.remove('alpha')
215	assert not .treapS.isEmpty
216	.treapS.remove('hotel')
217	assert not .treapS.isEmpty
218	.treapS.remove('zebra')
219	assert .treapS.isEmpty
220
221	def testAdd is shared
222	# create MyObjs containing key and string data
223
224	.treap = Treap<of MyKey, MyObj>()
225	assert not .treap.count
226	.treap.add(.mko3, .obj3)
227	assert .treap.count ==1
228	.treap.add(.mko1, .obj1)
229	assert .treap.count ==2
230	.treap.add( .mko2, .obj2)
231	assert .treap.count ==3
232	.treap.add(.mko4, .obj4)
233	assert .treap.count ==4
234	.treap.add(.mko5, .obj5)
235	assert .treap.count ==5
236
237	expectedKeys as dynamic = [.mko1 to IComparable, .mko2, .mko3, .mko4, .mko5]
238	expectedVals as dynamic = [.obj1 to Object, .obj2, .obj3, .obj4, .obj5]
239	.chkTreap(true, 5, expectedKeys, expectedVals)
240
241	#- Treap Values Collection
242	values = .treap.values
243	assert values == expectedVals
244
245	#- Treap Keys Collection
246	keys = .treap.keys
247	assert keys == expectedKeys
248
249	#keysEnumerator
250	i = 0
251	for kv in .treap
252	assert kv.key == expectedKeys[i]
253	i += 1
254
255	#valuesEnumerator - values ascending order by keys
256	i = 0
257	for kv in .treap
258	assert kv.value == expectedVals[i]
259	i += 1
260
261	#min/Max keys and values
262	.chkMinMaxValue(.mko1, .mko5, .obj1, .obj5)
263
264	def testContent is shared
265	assert .treap.contains(.mko3)
266	obj99 = MyObj(0099, "MyObj 99")
267	mko99 = MyKey(obj99.key)
268	assert not .treap.contains(mko99)
269
270	assert .treap.getValue(.mko3) == .obj3
271	expect TreapException
272	.treap.getValue(mko99)
273	val as MyObj?
274	r = .treap.tryGetValue(mko99, out val)
275	assert not r
276
277	def testRemove is shared
278	tObjKey = .treap.getMinKey
279	tObj = .treap.getValue(tObjKey)
280	assert tObj == .obj1
281	.treap.remove(tObjKey)
282
283	ekeys as ICollection<of IComparable> = [.mko5 to IComparable, .mko4, .mko3, .mko2]
284	evals as ICollection<of Object> = [.obj2 to Object, .obj3 to Object, .obj4 to Object, .obj5 to Object]
285	.chkTreap(false, 4, ekeys, evals)
286	.chkMinMaxValue(.mko2, .mko5, .obj2, .obj5)
287
288	assert .treap.getMaxValue == .obj5
289	.treap.removeMax
290	assert .treap.getMaxValue == .obj4
291	assert .treap.getMinValue == .obj2
292	.treap.removeMin
293	assert .treap.getMinValue == .obj3
294	.chkMinMaxValue(.mko3, .mko4, .obj3, .obj4)
295
296	# remove nonexistent OK
297	.treap.remove(.mko5)
298
299	ekeys = [.mko3 to IComparable, .mko4]
300	evals = [.obj3 to Object, .obj4 to Object]
301	.chkTreap(true, 2, ekeys, evals)
302
303	.treap.removeMin
304	assert .treap.getMinValue == .obj4
305	assert .treap.getMaxValue == .obj4
306	.treap.removeMax
307	assert .treap.count == 0
308
309	ekeys.clear
310	evals.clear
311	.chkTreap(true, 0, ekeys, evals)
312
313	def testClear is shared
314	# //add some Objs with embedded keys and clear the treap
315	myKeyObj1 = MyKeyObj(0025, "MyKeyObj W")
316	myKeyObj2 = MyKeyObj(0023, "MyKeyObj X")
317	myKeyObj3 = MyKeyObj(0026, "MyKeyObj Y")
318	myKeyObj4 = MyKeyObj(0024, "MyKeyObj Z")
319	treap = Treap<of int, MyKeyObj>()
320	treap.add(myKeyObj1.key, myKeyObj1)
321	assert treap.count == 1
322	treap.add(myKeyObj2.key, myKeyObj2)
323	assert treap.count == 2
324	treap.add(myKeyObj3.key, myKeyObj3)
325	assert treap.count == 3
326	treap.add(myKeyObj4.key, myKeyObj4)
327	assert treap.count == 4
328
329	ekeys as ICollection<of IComparable> = [.mko5 to IComparable]
330	ekeys.clear
331	evals as ICollection<of Object> = [.obj2 to Object]
332	evals.clear
333	for i in [23, 24, 25, 26]
334	ekeys.add(i to IComparable)
335	for mko in [myKeyObj2, myKeyObj4, myKeyObj1, myKeyObj3]
336	evals.add( mko to Object)
337
338	assert treap.count ==4
339	assert treap.keys == ekeys
340	assert treap.values == evals
341	ke = ekeys.getEnumerator
342	ve = evals.getEnumerator
343	for tn in treap
344	if ke.moveNext
345	assert ke.current == tn.key
346	if ve.moveNext
347	assert tn.value == ve.current
348	.chkEnumerator(treap, ekeys, evals)
349
350	treap.clear
351	assert treap.isEmpty
352	assert treap.count == 0
353
354	def chkTreap(ascending as bool, size as int, keys as ICollection<of IComparable>, values as ICollection<of Object>) is shared
355	assert .treap.count == size
356	assert keys.count == size
357	assert values.count == size
358
359	k = if(ascending, .treap.ascendingOrder.getEnumerator, .treap.descendingOrder.getEnumerator)
360	ke = keys.getEnumerator
361	while k.moveNext
362	if ke.moveNext
363	assert k.current.key == ke.current
364
365	ve = values.getEnumerator
366	for tn in .treap
367	if ve.moveNext
368	assert tn.value == ve.current
369
370	def chkMinMaxValue(minKey as MyKey, maxKey as MyKey, minVal as MyObj, maxVal as MyObj) is shared
371	assert .treap.getMinKey == minKey
372	assert .treap.getMaxKey == maxKey
373	assert .treap.getMinValue == minVal
374	assert .treap.getMaxValue == maxVal
375
376	def chkEnumerator( t as Treap<of int,MyKeyObj>, keys as ICollection<of IComparable>, values as ICollection<of Object>) is shared
377	e = t.getEnumerator
378	ke = keys.getEnumerator
379	ve = values.getEnumerator
380	while e.moveNext
381	node = e.current
382	ke.moveNext
383	assert node.key == ke.current
384	ve.moveNext
385	assert node.value == ve.current
386
387

Download in other formats:

Original Format