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