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