1
2
3import random
4from UM.SortedList import SortedKeyList, SortedList
5import pytest
6
7def modulo(val):
8    return val % 10
9
10def test_init():
11    slt = SortedKeyList(key=modulo)
12    assert slt.key == modulo
13    slt._check()
14
15    slt = SortedKeyList(key=modulo)
16    slt._reset(10000)
17    assert slt._load == 10000
18    slt._check()
19
20    slt = SortedKeyList(range(10000), key=modulo)
21    assert all(tup[0] == tup[1] for tup in zip(slt, sorted(range(10000), key=modulo)))
22
23    slt.clear()
24    assert slt._len == 0
25    assert slt._maxes == []
26    assert slt._lists == []
27
28    assert isinstance(slt, SortedList)
29    assert isinstance(slt, SortedKeyList)
30
31    slt._check()
32
33def test_new():
34    slt = SortedList(iter(range(1000)), key=modulo)
35    assert slt == sorted(range(1000), key=modulo)
36    slt._check()
37
38    assert isinstance(slt, SortedList)
39    assert isinstance(slt, SortedKeyList)
40    assert type(slt) == SortedKeyList
41
42    slt = SortedKeyList(iter(range(1000)), key=modulo)
43    assert slt == sorted(range(1000), key=modulo)
44    slt._check()
45
46    assert isinstance(slt, SortedList)
47    assert isinstance(slt, SortedKeyList)
48    assert type(slt) == SortedKeyList
49
50def test_new_error():
51    class SortedListPlus(SortedList):
52        pass
53    with pytest.raises(TypeError):
54        SortedListPlus(key=modulo)
55
56def test_key2():
57    class Incomparable:
58        pass
59    a = Incomparable()
60    b = Incomparable()
61    slt = SortedKeyList(key=lambda val: 1)
62    slt.add(a)
63    slt.add(b)
64    assert slt == [a, b]
65
66def test_add():
67    random.seed(0)
68    slt = SortedKeyList(key=modulo)
69    for val in range(1000):
70        slt.add(val)
71    slt._check()
72
73    slt = SortedKeyList(key=modulo)
74    for val in range(1000, 0, -1):
75        slt.add(val)
76    slt._check()
77
78    slt = SortedKeyList(key=modulo)
79    for val in range(1000):
80        slt.add(random.random())
81    slt._check()
82
83def test_update():
84    slt = SortedKeyList(key=modulo)
85
86    slt.update(range(1000))
87    assert all(tup[0] == tup[1] for tup in zip(slt, sorted(range(1000), key=modulo)))
88    assert len(slt) == 1000
89    slt._check()
90
91    slt.update(range(10000))
92    assert len(slt) == 11000
93    slt._check()
94
95def test_contains():
96    slt = SortedKeyList(key=modulo)
97    slt._reset(7)
98
99    assert 0 not in slt
100
101    slt.update(range(100))
102
103    for val in range(100):
104        assert val in slt
105
106    assert 100 not in slt
107
108    slt._check()
109
110    slt = SortedKeyList(range(100), key=modulo)
111    slt._reset(4)
112    assert all(val not in slt for val in range(100, 200))
113
114def test_discard():
115    slt = SortedKeyList(key=modulo)
116
117    assert slt.discard(0) == None
118    assert len(slt) == 0
119    slt._check()
120
121    slt = SortedKeyList([1, 2, 2, 2, 3, 3, 5], key=modulo)
122    slt._reset(4)
123
124    slt.discard(6)
125    slt._check()
126    slt.discard(4)
127    slt._check()
128    slt.discard(2)
129    slt._check()
130    slt.discard(11)
131    slt.discard(12)
132    slt.discard(13)
133    slt.discard(15)
134
135    assert all(tup[0] == tup[1] for tup in zip(slt, [1, 2, 2, 3, 3, 5]))
136
137def test_remove():
138    slt = SortedKeyList(key=modulo)
139
140    assert slt.discard(0) == None
141    assert len(slt) == 0
142    slt._check()
143
144    slt = SortedKeyList([1, 2, 2, 2, 3, 3, 5], key=modulo)
145    slt._reset(4)
146
147    slt.remove(2)
148    slt._check()
149
150    assert all(tup[0] == tup[1] for tup in zip(slt, [1, 2, 2, 3, 3, 5]))
151
152def test_remove_valueerror1():
153    slt = SortedKeyList(key=modulo)
154    with pytest.raises(ValueError):
155        slt.remove(0)
156
157def test_remove_valueerror2():
158    slt = SortedKeyList(range(100), key=modulo)
159    slt._reset(10)
160    with pytest.raises(ValueError):
161        slt.remove(100)
162
163def test_remove_valueerror3():
164    slt = SortedKeyList([1, 2, 2, 2, 3, 3, 5], key=modulo)
165    with pytest.raises(ValueError):
166        slt.remove(4)
167
168def test_remove_valueerror4():
169    slt = SortedKeyList([1, 1, 1, 2, 2, 2], key=modulo)
170    with pytest.raises(ValueError):
171        slt.remove(13)
172
173def test_remove_valueerror5():
174    slt = SortedKeyList([1, 1, 1, 2, 2, 2], key=modulo)
175    with pytest.raises(ValueError):
176        slt.remove(12)
177
178def test_delete():
179    slt = SortedKeyList(range(20), key=modulo)
180    slt._reset(4)
181    slt._check()
182    for val in range(20):
183        slt.remove(val)
184        slt._check()
185    assert len(slt) == 0
186    assert slt._maxes == []
187    assert slt._lists == []
188
189def test_getitem():
190    random.seed(0)
191    slt = SortedKeyList(key=modulo)
192    slt._reset(17)
193
194    slt.add(5)
195    slt._build_index()
196    slt._check()
197    slt.clear()
198
199    lst = list(random.random() for rpt in range(100))
200    slt.update(lst)
201    lst.sort(key=modulo)
202
203    assert all(slt[idx] == lst[idx] for idx in range(100))
204    assert all(slt[idx - 99] == lst[idx - 99] for idx in range(100))
205
206def test_getitem_slice():
207    random.seed(0)
208    slt = SortedKeyList(key=modulo)
209    slt._reset(17)
210
211    lst = list()
212
213    for rpt in range(100):
214        val = random.random()
215        slt.add(val)
216        lst.append(val)
217
218    lst.sort(key=modulo)
219
220    assert all(slt[start:] == lst[start:]
221               for start in [-75, -25, 0, 25, 75])
222
223    assert all(slt[:stop] == lst[:stop]
224               for stop in [-75, -25, 0, 25, 75])
225
226    assert all(slt[::step] == lst[::step]
227               for step in [-5, -1, 1, 5])
228
229    assert all(slt[start:stop] == lst[start:stop]
230               for start in [-75, -25, 0, 25, 75]
231               for stop in [-75, -25, 0, 25, 75])
232
233    assert all(slt[:stop:step] == lst[:stop:step]
234               for stop in [-75, -25, 0, 25, 75]
235               for step in [-5, -1, 1, 5])
236
237    assert all(slt[start::step] == lst[start::step]
238               for start in [-75, -25, 0, 25, 75]
239               for step in [-5, -1, 1, 5])
240
241    assert all(slt[start:stop:step] == lst[start:stop:step]
242               for start in [-75, -25, 0, 25, 75]
243               for stop in [-75, -25, 0, 25, 75]
244               for step in [-5, -1, 1, 5])
245
246def test_getitem_slice_big():
247    slt = SortedKeyList(range(4), key=modulo)
248    lst = sorted(range(4), key=modulo)
249
250    itr = ((start, stop, step)
251           for start in [-6, -4, -2, 0, 2, 4, 6]
252           for stop in [-6, -4, -2, 0, 2, 4, 6]
253           for step in [-3, -2, -1, 1, 2, 3])
254
255    for start, stop, step in itr:
256        assert slt[start:stop:step] == lst[start:stop:step]
257
258def test_getitem_slicezero():
259    slt = SortedKeyList(range(100), key=modulo)
260    slt._reset(17)
261    with pytest.raises(ValueError):
262        slt[::0]
263
264def test_getitem_indexerror1():
265    slt = SortedKeyList(key=modulo)
266    with pytest.raises(IndexError):
267        slt[5]
268
269def test_getitem_indexerror2():
270    slt = SortedKeyList(range(100), key=modulo)
271    with pytest.raises(IndexError):
272        slt[200]
273
274def test_getitem_indexerror3():
275    slt = SortedKeyList(range(100), key=modulo)
276    with pytest.raises(IndexError):
277        slt[-101]
278
279def test_delitem():
280    random.seed(0)
281
282    slt = SortedKeyList(range(100), key=modulo)
283    slt._reset(17)
284    while len(slt) > 0:
285        del slt[random.randrange(len(slt))]
286        slt._check()
287
288    slt = SortedKeyList(range(100), key=modulo)
289    slt._reset(17)
290    del slt[:]
291    assert len(slt) == 0
292    slt._check()
293
294def test_delitem_slice():
295    slt = SortedKeyList(range(100), key=modulo)
296    slt._reset(17)
297    del slt[10:40:1]
298    del slt[10:40:-1]
299    del slt[10:40:2]
300    del slt[10:40:-2]
301
302def test_iter():
303    slt = SortedKeyList(range(10000), key=modulo)
304    itr = iter(slt)
305    assert all(tup[0] == tup[1] for tup in zip(sorted(range(10000), key=modulo), itr))
306
307def test_reversed():
308    slt = SortedKeyList(range(10000), key=modulo)
309    rev = reversed(slt)
310    assert all(tup[0] == tup[1] for tup in zip(reversed(sorted(range(10000), key=modulo)), rev))
311
312def test_reverse():
313    slt = SortedKeyList(range(10000), key=modulo)
314    with pytest.raises(NotImplementedError):
315        slt.reverse()
316
317def test_islice():
318    sl = SortedKeyList(key=modulo)
319    sl._reset(7)
320
321    assert [] == list(sl.islice())
322
323    values = sorted(range(100), key=modulo)
324    sl.update(values)
325
326    for start in range(53):
327        for stop in range(53):
328            assert list(sl.islice(start, stop)) == values[start:stop]
329
330    for start in range(53):
331        for stop in range(53):
332            assert list(sl.islice(start, stop, reverse=True)) == values[start:stop][::-1]
333
334    for start in range(53):
335        assert list(sl.islice(start=start)) == values[start:]
336        assert list(sl.islice(start=start, reverse=True)) == values[start:][::-1]
337
338    for stop in range(53):
339        assert list(sl.islice(stop=stop)) == values[:stop]
340        assert list(sl.islice(stop=stop, reverse=True)) == values[:stop][::-1]
341
342def test_irange():
343    values = sorted(range(100), key=modulo)
344
345    for load in range(5, 16):
346        slt = SortedKeyList(range(100), key=modulo)
347        slt._reset(load)
348
349        for start in range(10):
350            for end in range(start, 10):
351                temp = list(slt.irange(start, end))
352                assert temp == values[(start * 10):((end + 1) * 10)]
353
354                temp = list(slt.irange(start, end, reverse=True))
355                assert temp == values[(start * 10):((end + 1) * 10)][::-1]
356
357        for start in range(10):
358            for end in range(start, 10):
359                temp = list(slt.irange(start, end, inclusive=(True, False)))
360                assert temp == values[(start * 10):(end * 10)]
361
362        for start in range(10):
363            for end in range(start, 10):
364                temp = list(slt.irange(start, end, (False, True)))
365                assert temp == values[((start + 1) * 10):((end + 1) * 10)]
366
367        for start in range(10):
368            for end in range(start, 10):
369                temp = list(slt.irange(start, end, inclusive=(False, False)))
370                assert temp == values[((start + 1) * 10):(end * 10)]
371
372        for start in range(10):
373            temp = list(slt.irange(minimum=start))
374            assert temp == values[(start * 10):]
375
376        for end in range(10):
377            temp = list(slt.irange(maximum=end))
378            assert temp == values[:(end + 1) * 10]
379
380def test_irange_key():
381    values = sorted(range(100), key=modulo)
382
383    for load in range(5, 16):
384        slt = SortedKeyList(range(100), key=modulo)
385        slt._reset(load)
386
387        for start in range(10):
388            for end in range(start, 10):
389                temp = list(slt.irange_key(start, end))
390                assert temp == values[(start * 10):((end + 1) * 10)]
391
392                temp = list(slt.irange_key(start, end, reverse=True))
393                assert temp == values[(start * 10):((end + 1) * 10)][::-1]
394
395        for start in range(10):
396            for end in range(start, 10):
397                temp = list(slt.irange_key(start, end, inclusive=(True, False)))
398                assert temp == values[(start * 10):(end * 10)]
399
400        for start in range(10):
401            for end in range(start, 10):
402                temp = list(slt.irange_key(start, end, (False, True)))
403                assert temp == values[((start + 1) * 10):((end + 1) * 10)]
404
405        for start in range(10):
406            for end in range(start, 10):
407                temp = list(slt.irange_key(start, end, inclusive=(False, False)))
408                assert temp == values[((start + 1) * 10):(end * 10)]
409
410        for start in range(10):
411            temp = list(slt.irange_key(min_key=start))
412            assert temp == values[(start * 10):]
413
414        for end in range(10):
415            temp = list(slt.irange_key(max_key=end))
416            assert temp == values[:(end + 1) * 10]
417
418def test_len():
419    slt = SortedKeyList(key=modulo)
420
421    for val in range(10000):
422        slt.add(val)
423        assert len(slt) == (val + 1)
424
425def test_bisect_left():
426    slt = SortedKeyList(key=modulo)
427    assert slt.bisect_left(0) == 0
428    slt = SortedKeyList(range(100), key=modulo)
429    slt._reset(17)
430    slt.update(range(100))
431    slt._check()
432    assert slt.bisect_left(50) == 0
433    assert slt.bisect_left(0) == 0
434
435def test_bisect():
436    slt = SortedKeyList(key=modulo)
437    assert slt.bisect(10) == 0
438    slt = SortedKeyList(range(100), key=modulo)
439    slt._reset(17)
440    slt.update(range(100))
441    slt._check()
442    assert slt.bisect(10) == 20
443    assert slt.bisect(0) == 20
444
445def test_bisect_right():
446    slt = SortedKeyList(key=modulo)
447    assert slt.bisect_right(10) == 0
448    slt = SortedKeyList(range(100), key=modulo)
449    slt._reset(17)
450    slt.update(range(100))
451    slt._check()
452    assert slt.bisect_right(10) == 20
453    assert slt.bisect_right(0) == 20
454
455def test_bisect_key_left():
456    slt = SortedKeyList(key=modulo)
457    assert slt.bisect_key_left(10) == 0
458    slt = SortedKeyList(range(100), key=modulo)
459    slt._reset(17)
460    slt.update(range(100))
461    slt._check()
462    assert slt.bisect_key_left(0) == 0
463    assert slt.bisect_key_left(5) == 100
464    assert slt.bisect_key_left(10) == 200
465
466def test_bisect_key_right():
467    slt = SortedKeyList(key=modulo)
468    assert slt.bisect_key_right(0) == 0
469    slt = SortedKeyList(range(100), key=modulo)
470    slt._reset(17)
471    slt.update(range(100))
472    slt._check()
473    assert slt.bisect_key_right(0) == 20
474    assert slt.bisect_key_right(5) == 120
475    assert slt.bisect_key_right(10) == 200
476
477def test_bisect_key():
478    slt = SortedKeyList(key=modulo)
479    assert slt.bisect_key(0) == 0
480    slt = SortedKeyList(range(100), key=modulo)
481    slt._reset(17)
482    slt.update(range(100))
483    slt._check()
484    assert slt.bisect_key(0) == 20
485    assert slt.bisect_key(5) == 120
486    assert slt.bisect_key(10) == 200
487
488def test_copy():
489    slt = SortedKeyList(range(100), key=modulo)
490    slt._reset(7)
491    two = slt.copy()
492    slt.add(100)
493    assert len(slt) == 101
494    assert len(two) == 100
495
496def test_copy_copy():
497    import copy
498    slt = SortedKeyList(range(100), key=modulo)
499    slt._reset(7)
500    two = copy.copy(slt)
501    slt.add(100)
502    assert len(slt) == 101
503    assert len(two) == 100
504
505def test_count():
506    slt = SortedKeyList(key=modulo)
507    slt._reset(7)
508
509    assert slt.count(0) == 0
510
511    for iii in range(100):
512        for jjj in range(iii):
513            slt.add(iii)
514    slt._check()
515
516    for iii in range(100):
517        assert slt.count(iii) == iii
518
519    slt = SortedKeyList(range(8), key=modulo)
520    assert slt.count(9) == 0
521
522def test_pop():
523    slt = SortedKeyList(range(10), key=modulo)
524    slt._reset(4)
525    slt._check()
526    assert slt.pop() == 9
527    slt._check()
528    assert slt.pop(0) == 0
529    slt._check()
530    assert slt.pop(-2) == 7
531    slt._check()
532    assert slt.pop(4) == 5
533    slt._check()
534
535def test_pop_indexerror1():
536    slt = SortedKeyList(range(10), key=modulo)
537    slt._reset(4)
538    with pytest.raises(IndexError):
539        slt.pop(-11)
540
541def test_pop_indexerror2():
542    slt = SortedKeyList(range(10), key=modulo)
543    slt._reset(4)
544    with pytest.raises(IndexError):
545        slt.pop(10)
546
547def test_index():
548    slt = SortedKeyList(range(100), key=modulo)
549    slt._reset(7)
550
551    for pos, val in enumerate(sorted(range(100), key=modulo)):
552        assert val == slt.index(pos)
553
554    assert slt.index(9, 0, 1000) == 90
555
556    slt = SortedKeyList((0 for rpt in range(100)), key=modulo)
557    slt._reset(7)
558
559    for start in range(100):
560        for stop in range(start, 100):
561            assert slt.index(0, start, stop + 1) == start
562
563    for start in range(100):
564        assert slt.index(0, -(100 - start)) == start
565
566    assert slt.index(0, -1000) == 0
567
568def test_index_valueerror1():
569    slt = SortedKeyList([0] * 10, key=modulo)
570    slt._reset(4)
571    with pytest.raises(ValueError):
572        slt.index(0, 10)
573
574def test_index_valueerror2():
575    slt = SortedKeyList([0] * 10, key=modulo)
576    slt._reset(4)
577    with pytest.raises(ValueError):
578        slt.index(0, 0, -10)
579
580def test_index_valueerror3():
581    slt = SortedKeyList([0] * 10, key=modulo)
582    slt._reset(4)
583    with pytest.raises(ValueError):
584        slt.index(0, 7, 3)
585
586def test_index_valueerror4():
587    slt = SortedKeyList([0] * 10, key=modulo)
588    slt._reset(4)
589    with pytest.raises(ValueError):
590        slt.index(1)
591
592def test_index_valueerror5():
593    slt = SortedKeyList(key=modulo)
594    with pytest.raises(ValueError):
595        slt.index(1)
596
597def test_index_valueerror6():
598    slt = SortedKeyList(range(100), key=modulo)
599    slt._reset(4)
600    with pytest.raises(ValueError):
601        slt.index(91, 0, 15)
602
603def test_index_valueerror7():
604    slt = SortedKeyList([0] * 10 + [1] * 10 + [2] * 10, key=modulo)
605    slt._reset(4)
606    with pytest.raises(ValueError):
607        slt.index(1, 0, 10)
608
609def test_index_valueerror8():
610    slt = SortedKeyList(range(10), key=modulo)
611    slt._reset(4)
612    with pytest.raises(ValueError):
613        slt.index(4, 5)
614
615def test_index_valueerror9():
616    slt = SortedKeyList(key=modulo)
617    slt._reset(4)
618    with pytest.raises(ValueError):
619        slt.index(5)
620
621def test_index_valueerror10():
622    slt = SortedKeyList(range(10), key=modulo)
623    slt._reset(4)
624    with pytest.raises(ValueError):
625        slt.index(19)
626
627def test_mul():
628    this = SortedKeyList(range(10), key=modulo)
629    this._reset(4)
630    that = this * 5
631    this._check()
632    that._check()
633    assert this == sorted(range(10), key=modulo)
634    assert that == sorted(list(range(10)) * 5, key=modulo)
635    assert this != that
636
637def test_imul():
638    this = SortedKeyList(range(10), key=modulo)
639    this._reset(4)
640    this *= 5
641    this._check()
642    assert this == sorted(list(range(10)) * 5, key=modulo)
643
644def test_op_add():
645    this = SortedKeyList(range(10), key=modulo)
646    this._reset(4)
647    assert (this + this + this) == (this * 3)
648
649    that = SortedKeyList(range(10), key=modulo)
650    that._reset(4)
651    that += that
652    that += that
653    assert that == (this * 4)
654
655def test_eq():
656    this = SortedKeyList(range(10), key=modulo)
657    this._reset(4)
658    assert this == list(range(10))
659    assert this == tuple(range(10))
660    assert not (this == list(range(9)))
661
662def test_ne():
663    this = SortedKeyList(range(10, 20), key=modulo)
664    this._reset(4)
665    assert this != list(range(11, 21))
666    assert this != tuple(range(10, 21))
667    assert this != [0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
668    assert this != (val for val in range(10))
669    assert this != set()
670
671def test_lt():
672    this = SortedKeyList(range(10, 15), key=modulo)
673    this._reset(4)
674    assert this < [10, 11, 13, 13, 14]
675    assert this < [10, 11, 12, 13, 14, 15]
676    assert this < [11]
677
678def test_le():
679    this = SortedKeyList(range(10, 15), key=modulo)
680    this._reset(4)
681    assert this <= [10, 11, 12, 13, 14]
682    assert this <= [10, 11, 12, 13, 14, 15]
683    assert this <= [10, 11, 13, 13, 14]
684    assert this <= [11]
685
686def test_gt():
687    this = SortedKeyList(range(10, 15), key=modulo)
688    this._reset(4)
689    assert this > [10, 11, 11, 13, 14]
690    assert this > [10, 11, 12, 13]
691    assert this > [9]
692
693def test_ge():
694    this = SortedKeyList(range(10, 15), key=modulo)
695    this._reset(4)
696    assert this >= [10, 11, 12, 13, 14]
697    assert this >= [10, 11, 12, 13]
698    assert this >= [10, 11, 11, 13, 14]
699    assert this >= [9]
700
701def test_repr():
702    this = SortedKeyList(range(10), key=modulo)
703    this._reset(4)
704    assert repr(this).startswith('SortedKeyList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], key=<function modulo at ')
705
706def test_repr_recursion():
707    this = SortedKeyList([[1], [2], [3], [4]], key=lambda val: val)
708    this._lists[-1].append(this)
709    assert repr(this).startswith('SortedKeyList([[1], [2], [3], [4], ...], key=<function ')
710
711def test_repr_subclass():
712    class CustomSortedKeyList(SortedKeyList):
713        pass
714    this = CustomSortedKeyList(range(10), key=modulo)
715    this._reset(4)
716    assert repr(this).startswith('CustomSortedKeyList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], key=<function modulo at ')
717
718def test_check():
719    slt = SortedKeyList(range(10), key=modulo)
720    slt._reset(4)
721    slt._len = 5
722    with pytest.raises(AssertionError):
723        slt._check()
724