Wiki

Ticket #263: TestTreap.cobra

File TestTreap.cobra, 10.4 KB (added by hopscc, 7 years ago)
Line 
1# Test run for treap (Tree Heap) Gneric implementation
2use System.Diagnostics
3use System.Data
4
5use Treap
6
7namespace 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