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