tests/test-lrucachedict.py

copies-rust: use imrs::OrdSet instead of imrs::HashSet

This yield small speedup all over the board, and a large one for our slower
cases:

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,   2.034596 s,   1.465264 s,  -0.569332 s, × 0.7202,    15 µs/rev
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,   0.694030 s,   0.690376 s,  -0.003654 s, × 0.9947,    13 µs/rev
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,   4.407723 s,   4.011322 s,  -0.396401 s, × 0.9101,    11 µs/rev
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.574355 s,   0.573541 s,  -0.000814 s, × 0.9986,    16 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,   4.457827 s,   3.981133 s,  -0.476694 s, × 0.8931,    10 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,   4.351696 s,   3.996647 s,  -0.355049 s, × 0.9184,    11 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs,  80.828689 s,  50.244975 s, -30.583714 s, × 0.6216,   219 µs/rev
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  34.094064 s,  20.030023 s, -14.064041 s, × 0.5875,    52 µs/rev
private                                                                         : 459513 revs,  27.435529 s,  24.490825 s,  -2.944704 s, × 0.8927,    53 µs/rev

We also got significantly faster than the implementation using is_ancestors
except for one of our reference case:

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,   5.138169 s,   4.011322 s,  -1.126847 s, × 0.7807,    11 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,   5.127809 s,   3.981133 s,  -1.146676 s, × 0.7764,    10 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,   4.971136 s,   3.996647 s,  -0.974489 s, × 0.8040,    11 µs/rev
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   1.741678 s,   1.520607 s,  -0.221071 s, × 0.8731,     7 µs/rev
private                                                                         : 459513 revs,  37.179470 s,  24.490825 s, -12.688645 s, × 0.6587,    53 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs,  40.314822 s,  50.244975 s,  +9.930153 s, × 1.2463,   219 µs/rev


Below are three different benchmark comparing this changeset to:
* the previous one,
* the implementation based on `is_anscestors`,
* the filelog copy tracing.


### Compared to the previous ones

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :      1 revs,   0.000043 s,   0.000041 s,  -0.000002 s, × 0.9535,    41 µs/rev
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :      6 revs,   0.000114 s,   0.000116 s,  +0.000002 s, × 1.0175,    19 µs/rev
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :   1032 revs,   0.004899 s,   0.004933 s,  +0.000034 s, × 1.0069,     4 µs/rev
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :      9 revs,   0.000196 s,   0.000193 s,  -0.000003 s, × 0.9847,    21 µs/rev
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :      1 revs,   0.000049 s,   0.000048 s,  -0.000001 s, × 0.9796,    48 µs/rev
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :      7 revs,   0.000117 s,   0.000114 s,  -0.000003 s, × 0.9744,    16 µs/rev
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :      1 revs,   0.6f1f4a s,   0.000319 s,  -0.000003 s, × 0.9907,   319 µs/rev
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :      6 revs,   0.011856 s,   0.012025 s,  +0.000169 s, × 1.0143,  2004 µs/rev
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   4785 revs,   0.050992 s,   0.050525 s,  -0.000467 s, × 0.9908,    10 µs/rev
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   6780 revs,   0.087444 s,   0.085713 s,  -0.001731 s, × 0.9802,    12 µs/rev
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   5441 revs,   0.062487 s,   0.061825 s,  -0.000662 s, × 0.9894,    11 µs/rev
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  43645 revs,   0.634909 s,   0.543998 s,  -0.090911 s, × 0.8568,    12 µs/rev
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :      2 revs,   0.013360 s,   0.013455 s,  +0.000095 s, × 1.0071,  6727 µs/rev
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  11316 revs,   0.120775 s,   0.117479 s,  -0.003296 s, × 0.9727,    10 µs/rev
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :      2 revs,   0.000085 s,   0.000084 s,  -0.000001 s, × 0.9882,    42 µs/rev
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :      2 revs,   0.000108 s,   0.000111 s,  +0.000003 s, × 1.0278,    55 µs/rev
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :      3 revs,   0.000176 s,   0.000175 s,  -0.000001 s, × 0.9943,    58 µs/rev
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :      9 revs,   0.000747 s,   0.000732 s,  -0.000015 s, × 0.9799,    81 µs/rev
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   1421 revs,   0.010128 s,   0.010062 s,  -0.000066 s, × 0.9935,     7 µs/rev
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   1533 revs,   0.015899 s,   0.015659 s,  -0.000240 s, × 0.9849,    10 µs/rev
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   5750 revs,   0.062215 s,   0.062744 s,  +0.000529 s, × 1.0085,    10 µs/rev
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  66949 revs,   0.521004 s,   0.499449 s,  -0.021555 s, × 0.9586,     7 µs/rev
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :      2 revs,   0.000090 s,   0.000088 s,  -0.000002 s, × 0.9778,    44 µs/rev
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :      8 revs,   0.000264 s,   0.000266 s,  +0.000002 s, × 1.0076,    33 µs/rev
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :      9 revs,   0.000186 s,   0.000182 s,  -0.000004 s, × 0.9785,    20 µs/rev
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :      7 revs,   0.000660 s,   0.000656 s,  -0.000004 s, × 0.9939,    93 µs/rev
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :      3 revs,   0.003542 s,   0.003389 s,  -0.000153 s, × 0.9568,  1129 µs/rev
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.071574 s,   0.075882 s,  +0.004308 s, × 1.0602, 12647 µs/rev
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006498 s,   0.006479 s,  -0.000019 s, × 0.9971,     4 µs/rev
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005206 s,   0.004889 s,  -0.000317 s, × 0.9391,   119 µs/rev
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   7839 revs,   0.065535 s,   0.064394 s,  -0.001141 s, × 0.9826,     8 µs/rev
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.027139 s,   0.026815 s,  -0.000324 s, × 0.9881,    43 µs/rev
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  30263 revs,   0.201924 s,   0.cc85eb s,  +0.000940 s, × 1.0047,     6 µs/rev
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 153721 revs,   1.257201 s,   1.219445 s,  -0.037756 s, × 0.9700,     7 µs/rev
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 204976 revs,   1.663045 s,   1.613857 s,  -0.049188 s, × 0.9704,     7 µs/rev
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :      2 revs,   0.000866 s,   0.000873 s,  +0.000007 s, × 1.0081,   436 µs/rev
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :      2 revs,   0.000883 s,   0.000885 s,  +0.000002 s, × 1.0023,   442 µs/rev
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :      4 revs,   0.000163 s,   0.000161 s,  -0.000002 s, × 0.9877,    40 µs/rev
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :      2 revs,   0.001139 s,   0.001138 s,  -0.000001 s, × 0.9991,   569 µs/rev
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :      1 revs,   0.032753 s,   0.033399 s,  +0.000646 s, × 1.0197, 33399 µs/rev
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.073266 s,   0.075445 s,  +0.002179 s, × 1.0297, 12574 µs/rev
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006567 s,   0.006456 s,  -0.000111 s, × 0.9831,     4 µs/rev
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005427 s,   0.005462 s,  +0.000035 s, × 1.0064,   133 µs/rev
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   6657 revs,   0.064058 s,   0.064117 s,  +0.000059 s, × 1.0009,     9 µs/rev
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  40314 revs,   0.303320 s,   0.297563 s,  -0.005757 s, × 0.9810,     7 µs/rev
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  38690 revs,   0.288456 s,   0.282463 s,  -0.005993 s, × 0.9792,     7 µs/rev
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,   0.085925 s,   0.084038 s,  -0.001887 s, × 0.9780,     9 µs/rev
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.027302 s,   0.027306 s,  +0.000004 s, × 1.0001,    44 µs/rev
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,   2.034596 s,   1.465264 s,  -0.569332 s, × 0.7202,    15 µs/rev
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,   0.694030 s,   0.690376 s,  -0.003654 s, × 0.9947,    13 µs/rev
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,   4.407723 s,   4.011322 s,  -0.396401 s, × 0.9101,    11 µs/rev
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.574355 s,   0.573541 s,  -0.000814 s, × 0.9986,    16 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,   4.457827 s,   3.981133 s,  -0.476694 s, × 0.8931,    10 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,   4.351696 s,   3.996647 s,  -0.355049 s, × 0.9184,    11 µs/rev
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   1.570065 s,   1.520607 s,  -0.049458 s, × 0.9685,     7 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs,  80.828689 s,  50.244975 s, -30.583714 s, × 0.6216,   219 µs/rev
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  34.094064 s,  20.030023 s, -14.064041 s, × 0.5875,    52 µs/rev
private                                                                         : 459513 revs,  27.435529 s,  24.490825 s,  -2.944704 s, × 0.8927,    53 µs/rev

### Compared to the implementation using `is_anscestor`

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :      1 revs,   0.000042 s,   0.000041 s,  -0.000001 s, × 0.9762,    41 µs/rev
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :      6 revs,   0.000110 s,   0.000116 s,  +0.000006 s, × 1.0545,    19 µs/rev
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :   1032 revs,   0.004945 s,   0.004933 s,  -0.000012 s, × 0.9976,     4 µs/rev
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :      9 revs,   0.000192 s,   0.000193 s,  +0.000001 s, × 1.0052,    21 µs/rev
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :      1 revs,   0.000049 s,   0.000048 s,  -0.000001 s, × 0.9796,    48 µs/rev
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :      7 revs,   0.000112 s,   0.000114 s,  +0.000002 s, × 1.0179,    16 µs/rev
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :      1 revs,   0.000323 s,   0.000319 s,  -0.000004 s, × 0.9876,   319 µs/rev
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :      6 revs,   0.010042 s,   0.012025 s,  +0.001983 s, × 1.1975,  2004 µs/rev
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   4785 revs,   0.049813 s,   0.050525 s,  +0.000712 s, × 1.0143,    10 µs/rev
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   6780 revs,   0.079937 s,   0.085713 s,  +0.005776 s, × 1.0723,    12 µs/rev
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   5441 revs,   0.059412 s,   0.061825 s,  +0.002413 s, × 1.0406,    11 µs/rev
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  43645 revs,   0.533769 s,   0.543998 s,  +0.010229 s, × 1.0192,    12 µs/rev
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :      2 revs,   0.013147 s,   0.013455 s,  +0.000308 s, × 1.0234,  6727 µs/rev
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  11316 revs,   0.110680 s,   0.117479 s,  +0.006799 s, × 1.0614,    10 µs/rev
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :      2 revs,   0.000085 s,   0.000084 s,  -0.000001 s, × 0.9882,    42 µs/rev
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :      2 revs,   0.000107 s,   0.000111 s,  +0.000004 s, × 1.0374,    55 µs/rev
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :      3 revs,   0.000175 s,   0.000175 s,  +0.000000 s, × 1.0000,    58 µs/rev
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :      9 revs,   0.000720 s,   0.000732 s,  +0.000012 s, × 1.0167,    81 µs/rev
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   1421 revs,   0.010019 s,   0.010062 s,  +0.000043 s, × 1.0043,     7 µs/rev
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   1533 revs,   0.015602 s,   0.015659 s,  +0.000057 s, × 1.0037,    10 µs/rev
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   5750 revs,   0.058759 s,   0.062744 s,  +0.003985 s, × 1.0678,    10 µs/rev
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  66949 revs,   0.491550 s,   0.499449 s,  +0.007899 s, × 1.0161,     7 µs/rev
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :      2 revs,   0.000087 s,   0.000088 s,  +0.000001 s, × 1.0115,    44 µs/rev
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :      8 revs,   0.000268 s,   0.000266 s,  -0.000002 s, × 0.9925,    33 µs/rev
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :      9 revs,   0.000181 s,   0.000182 s,  +0.000001 s, × 1.0055,    20 µs/rev
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :      7 revs,   0.000661 s,   0.000656 s,  -0.000005 s, × 0.9924,    93 µs/rev
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :      3 revs,   0.003256 s,   0.003389 s,  +0.000133 s, × 1.0408,  1129 µs/rev
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.066749 s,   0.075882 s,  +0.009133 s, × 1.1368, 12647 µs/rev
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006462 s,   0.006479 s,  +0.000017 s, × 1.0026,     4 µs/rev
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.004919 s,   0.004889 s,  -0.000030 s, × 0.9939,   119 µs/rev
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   7839 revs,   0.062421 s,   0.064394 s,  +0.001973 s, × 1.0316,     8 µs/rev
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.026633 s,   0.026815 s,  +0.000182 s, × 1.0068,    43 µs/rev
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  30263 revs,   0.197792 s,   0.cc85eb s,  +0.005072 s, × 1.0256,     6 µs/rev
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 153721 revs,   1.259970 s,   1.219445 s,  -0.040525 s, × 0.9678,     7 µs/rev
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 204976 revs,   1.689184 s,   1.613857 s,  -0.075327 s, × 0.9554,     7 µs/rev
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :      2 revs,   0.000865 s,   0.000873 s,  +0.000008 s, × 1.0092,   436 µs/rev
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :      2 revs,   0.000893 s,   0.000885 s,  -0.000008 s, × 0.9910,   442 µs/rev
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :      4 revs,   0.000172 s,   0.000161 s,  -0.000011 s, × 0.9360,    40 µs/rev
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :      2 revs,   0.001159 s,   0.001138 s,  -0.000021 s, × 0.9819,   569 µs/rev
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :      1 revs,   0.031621 s,   0.033399 s,  +0.001778 s, × 1.0562, 33399 µs/rev
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.068571 s,   0.075445 s,  +0.006874 s, × 1.1002, 12574 µs/rev
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006452 s,   0.006456 s,  +0.000004 s, × 1.0006,     4 µs/rev
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005443 s,   0.005462 s,  +0.000019 s, × 1.0035,   133 µs/rev
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   6657 revs,   0.063180 s,   0.064117 s,  +0.000937 s, × 1.0148,     9 µs/rev
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  40314 revs,   0.293564 s,   0.297563 s,  +0.003999 s, × 1.0136,     7 µs/rev
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  38690 revs,   0.286595 s,   0.282463 s,  -0.004132 s, × 0.9856,     7 µs/rev
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,   0.083256 s,   0.084038 s,  +0.000782 s, × 1.0094,     9 µs/rev
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.027282 s,   0.027306 s,  +0.000024 s, × 1.0009,    44 µs/rev
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,   1.343373 s,   1.465264 s,  +0.121891 s, × 1.0907,    15 µs/rev
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,   0.665737 s,   0.690376 s,  +0.024639 s, × 1.0370,    13 µs/rev
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,   5.138169 s,   4.011322 s,  -1.126847 s, × 0.7807,    11 µs/rev
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.573276 s,   0.573541 s,  +0.000265 s, × 1.0005,    16 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,   5.127809 s,   3.981133 s,  -1.146676 s, × 0.7764,    10 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,   4.971136 s,   3.996647 s,  -0.974489 s, × 0.8040,    11 µs/rev
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   1.741678 s,   1.520607 s,  -0.221071 s, × 0.8731,     7 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs,  40.314822 s,  50.244975 s,  +9.930153 s, × 1.2463,   219 µs/rev
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  20.048029 s,  20.030023 s,  -0.018006 s, × 0.9991,    52 µs/rev
private                                                                         : 459513 revs,  37.179470 s,  24.490825 s, -12.688645 s, × 0.6587,    53 µs/rev

### Compared to the filelog based copy tracing

Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
---------------------------------------------------------------------------------------------------------------------------------------------------------------
mercurial       x_revs_x_added_0_copies               ad6b123de1c7 39cfcef4f463 :      1 revs,  0.000918 s,  0.000041 s,  -0.000877 s, × 0.044662,    40 µs/rev
mercurial       x_revs_x_added_x_copies               2b1c78674230 0c1d10351869 :      6 revs,  0.001853 s,  0.000116 s,  -0.001737 s, × 0.062601,    19 µs/rev
mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 dd3267698d84 :   1032 revs,  0.018994 s,  0.004933 s,  -0.014061 s, × 0.259714,     4 µs/rev
pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :      9 revs,  0.001532 s,  0.000193 s,  -0.001339 s, × 0.125979,    21 µs/rev
pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :      1 revs,  0.210633 s,  0.000048 s,  -0.210585 s, × 0.000228,    47 µs/rev
pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :      7 revs,  0.017041 s,  0.000114 s,  -0.016927 s, × 0.006690,    16 µs/rev
pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :      1 revs,  0.019474 s,  0.000319 s,  -0.019155 s, × 0.016381,   318 µs/rev
pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :      6 revs,  0.763136 s,  0.012025 s,  -0.751111 s, × 0.015757,  2003 µs/rev
pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   4785 revs,  1.226569 s,  0.050525 s,  -1.176044 s, × 0.041192,    10 µs/rev
pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   6780 revs,  1.314572 s,  0.085713 s,  -1.228859 s, × 0.065202,    12 µs/rev
pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   5441 revs,  1.686022 s,  0.061825 s,  -1.624197 s, × 0.036669,    11 µs/rev
pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  43645 revs,  0.001110 s,  0.543998 s,  +0.542888 s, × 490.0882,    12 µs/rev
pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :      2 revs,  1.106265 s,  0.013455 s,  -1.092810 s, × 0.012163,  6724 µs/rev
pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  11316 revs,  1.377398 s,  0.117479 s,  -1.259919 s, × 0.085291,    10 µs/rev
netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :      2 revs,  0.028579 s,  0.000084 s,  -0.028495 s, × 0.002939,    41 µs/rev
netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :      2 revs,  0.133644 s,  0.000111 s,  -0.133533 s, × 0.000831,    55 µs/rev
netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :      3 revs,  0.025988 s,  0.000175 s,  -0.025813 s, × 0.006734,    58 µs/rev
netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :      9 revs,  0.053011 s,  0.000732 s,  -0.052279 s, × 0.013808,    81 µs/rev
netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   1421 revs,  0.037858 s,  0.010062 s,  -0.027796 s, × 0.265783,     7 µs/rev
netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   1533 revs,  0.200517 s,  0.015659 s,  -0.184858 s, × 0.078093,    10 µs/rev
netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   5750 revs,  0.964542 s,  0.062744 s,  -0.901798 s, × 0.065051,    10 µs/rev
netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  66949 revs,  3.976210 s,  0.499449 s,  -3.476761 s, × 0.125609,     7 µs/rev
mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :      2 revs,  0.025172 s,  0.000088 s,  -0.025084 s, × 0.003496,    43 µs/rev
mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :      8 revs,  0.145144 s,  0.000266 s,  -0.144878 s, × 0.001833,    33 µs/rev
mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :      9 revs,  0.026139 s,  0.000182 s,  -0.025957 s, × 0.006963,    20 µs/rev
mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :      7 revs,  0.086184 s,  0.000656 s,  -0.085528 s, × 0.007612,    93 µs/rev
mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :      3 revs,  0.203187 s,  0.003389 s,  -0.199798 s, × 0.016679,  1129 µs/rev
mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,  2.255675 s,  0.075882 s,  -2.179793 s, × 0.033640, 12644 µs/rev
mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,  0.091147 s,  0.006479 s,  -0.084668 s, × 0.071083,     4 µs/rev
mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,  0.767530 s,  0.004889 s,  -0.762641 s, × 0.006370,   119 µs/rev
mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   7839 revs,  1.185330 s,  0.064394 s,  -1.120936 s, × 0.054326,     8 µs/rev
mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,  6.831179 s,  0.026815 s,  -6.804364 s, × 0.003925,    43 µs/rev
mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  30263 revs,  3.373551 s,  0.cc85eb s,  -3.170687 s, × 0.060134,     6 µs/rev
mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 153721 revs, 16.540604 s,  1.219445 s, -15.321159 s, × 0.073724,     7 µs/rev
mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 204976 revs, 21.527155 s,  1.613857 s, -19.913298 s, × 0.074968,     7 µs/rev
mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :      2 revs,  0.084540 s,  0.000873 s,  -0.083667 s, × 0.010326,   436 µs/rev
mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :      2 revs,  0.507151 s,  0.000885 s,  -0.506266 s, × 0.001745,   442 µs/rev
mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :      4 revs,  0.021748 s,  0.000161 s,  -0.021587 s, × 0.007403,    40 µs/rev
mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :      2 revs,  0.236786 s,  0.001138 s,  -0.235648 s, × 0.004806,   568 µs/rev
mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :      1 revs,  1.111735 s,  0.033399 s,  -1.078336 s, × 0.030042, 33365 µs/rev
mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,  2.228030 s,  0.075445 s,  -2.152585 s, × 0.033862, 12572 µs/rev
mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,  0.091289 s,  0.006456 s,  -0.084833 s, × 0.070720,     4 µs/rev
mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,  0.771361 s,  0.005462 s,  -0.765899 s, × 0.007081,   133 µs/rev
mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   6657 revs,  1.189483 s,  0.064117 s,  -1.125366 s, × 0.053903,     9 µs/rev
mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  40314 revs,  0.089756 s,  0.297563 s,  +0.207807 s, × 3.315244,     7 µs/rev
mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  38690 revs,  0.084888 s,  0.282463 s,  +0.197575 s, × 3.327479,     7 µs/rev
mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,  7.682665 s,  0.084038 s,  -7.598627 s, × 0.010939,     9 µs/rev
mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,  6.894680 s,  0.027306 s,  -6.867374 s, × 0.003960,    44 µs/rev
mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,  7.650907 s,  1.465264 s,  -6.185643 s, × 0.191515,    15 µs/rev
mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,  9.898788 s,  0.690376 s,  -9.208412 s, × 0.069743,    13 µs/rev
mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,  0.092208 s,  4.011322 s,  +3.919114 s, × 43.50297,    11 µs/rev
mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs, 28.130003 s,  0.573541 s, -27.556462 s, × 0.020389,    16 µs/rev
mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,  0.093366 s,  3.981133 s,  +3.887767 s, × 42.64007,    10 µs/rev
mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,  0.229368 s,  3.996647 s,  +3.767279 s, × 17.42460,    11 µs/rev
mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs, 19.624851 s,  1.520607 s, -18.104244 s, × 0.077484,     7 µs/rev
mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 22.070126 s, 50.244975 s, +28.174849 s, × 2.276606,   219 µs/rev
mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs, 26.006524 s, 20.030023 s,  -5.976501 s, × 0.770192,    52 µs/rev
private                                                                         : 459513 revs, 18.704612 s, 24.490825 s,  +5.786213 s, × 1.309347,    53 µs/rev

Differential Revision: https://phab.mercurial-scm.org/D9656

from __future__ import absolute_import, print_function

import unittest

import silenttestrunner

from mercurial import util


class testlrucachedict(unittest.TestCase):
    def testsimple(self):
        d = util.lrucachedict(4)
        self.assertEqual(d.capacity, 4)
        d.insert('a', 'va', cost=2)
        d['b'] = 'vb'
        d['c'] = 'vc'
        d.insert('d', 'vd', cost=42)

        self.assertEqual(d['a'], 'va')
        self.assertEqual(d['b'], 'vb')
        self.assertEqual(d['c'], 'vc')
        self.assertEqual(d['d'], 'vd')

        self.assertEqual(d.totalcost, 44)

        # 'a' should be dropped because it was least recently used.
        d['e'] = 've'
        self.assertNotIn('a', d)
        self.assertIsNone(d.get('a'))
        self.assertEqual(d.totalcost, 42)

        self.assertEqual(d['b'], 'vb')
        self.assertEqual(d['c'], 'vc')
        self.assertEqual(d['d'], 'vd')
        self.assertEqual(d['e'], 've')

        # Replacing item with different cost adjusts totalcost.
        d.insert('e', 've', cost=4)
        self.assertEqual(d.totalcost, 46)

        # Touch entries in some order (both get and set).
        d['e']
        d['c'] = 'vc2'
        d['d']
        d['b'] = 'vb2'

        # 'e' should be dropped now
        d['f'] = 'vf'
        self.assertNotIn('e', d)
        self.assertEqual(d['b'], 'vb2')
        self.assertEqual(d['c'], 'vc2')
        self.assertEqual(d['d'], 'vd')
        self.assertEqual(d['f'], 'vf')

        d.clear()
        for key in ('a', 'b', 'c', 'd', 'e', 'f'):
            self.assertNotIn(key, d)

    def testunfull(self):
        d = util.lrucachedict(4)
        d['a'] = 1
        d['b'] = 2
        d['a']
        d['b']

        for key in ('a', 'b'):
            self.assertIn(key, d)

    def testget(self):
        d = util.lrucachedict(4)
        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'

        self.assertIsNone(d.get('missing'))
        self.assertEqual(list(d), ['c', 'b', 'a'])

        self.assertEqual(d.get('a'), 'va')
        self.assertEqual(list(d), ['a', 'c', 'b'])

    def testpeek(self):
        d = util.lrucachedict(4)
        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'

        with self.assertRaises(KeyError):
            d.peek('missing')
        self.assertEqual(list(d), ['c', 'b', 'a'])
        self.assertIsNone(d.peek('missing', None))
        self.assertEqual(list(d), ['c', 'b', 'a'])

        self.assertEqual(d.peek('a'), 'va')
        self.assertEqual(list(d), ['c', 'b', 'a'])

    def testpop(self):
        d = util.lrucachedict(4)
        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'

        with self.assertRaises(KeyError):
            d.pop('missing')
        self.assertEqual(list(d), ['c', 'b', 'a'])
        self.assertIsNone(d.pop('missing', None))
        self.assertEqual(list(d), ['c', 'b', 'a'])

        self.assertEqual(d.pop('b'), 'vb')
        self.assertEqual(list(d), ['c', 'a'])

    def testcopypartial(self):
        d = util.lrucachedict(4)
        d.insert('a', 'va', cost=4)
        d.insert('b', 'vb', cost=2)

        dc = d.copy()

        self.assertEqual(len(dc), 2)
        self.assertEqual(dc.totalcost, 6)
        for key in ('a', 'b'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        self.assertEqual(len(d), 2)
        for key in ('a', 'b'):
            self.assertIn(key, d)
            self.assertEqual(d[key], 'v%s' % key)

        d['c'] = 'vc'
        del d['b']
        self.assertEqual(d.totalcost, 4)
        dc = d.copy()
        self.assertEqual(len(dc), 2)
        self.assertEqual(dc.totalcost, 4)
        for key in ('a', 'c'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

    def testcopyempty(self):
        d = util.lrucachedict(4)
        dc = d.copy()
        self.assertEqual(len(dc), 0)

    def testcopyfull(self):
        d = util.lrucachedict(4)
        d.insert('a', 'va', cost=42)
        d['b'] = 'vb'
        d['c'] = 'vc'
        d['d'] = 'vd'

        dc = d.copy()

        for key in ('a', 'b', 'c', 'd'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        self.assertEqual(d.totalcost, 42)
        self.assertEqual(dc.totalcost, 42)

        # 'a' should be dropped because it was least recently used.
        dc['e'] = 've'
        self.assertNotIn('a', dc)
        for key in ('b', 'c', 'd', 'e'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        self.assertEqual(d.totalcost, 42)
        self.assertEqual(dc.totalcost, 0)

        # Contents and order of original dict should remain unchanged.
        dc['b'] = 'vb_new'

        self.assertEqual(list(iter(d)), ['d', 'c', 'b', 'a'])
        for key in ('a', 'b', 'c', 'd'):
            self.assertEqual(d[key], 'v%s' % key)

        d = util.lrucachedict(4, maxcost=42)
        d.insert('a', 'va', cost=5)
        d.insert('b', 'vb', cost=4)
        d.insert('c', 'vc', cost=3)
        dc = d.copy()
        self.assertEqual(dc.maxcost, 42)
        self.assertEqual(len(dc), 3)

        # Max cost can be lowered as part of copy.
        dc = d.copy(maxcost=10)
        self.assertEqual(dc.maxcost, 10)
        self.assertEqual(len(dc), 2)
        self.assertEqual(dc.totalcost, 7)
        self.assertIn('b', dc)
        self.assertIn('c', dc)

    def testcopydecreasecapacity(self):
        d = util.lrucachedict(5)
        d.insert('a', 'va', cost=4)
        d.insert('b', 'vb', cost=2)
        d['c'] = 'vc'
        d['d'] = 'vd'

        dc = d.copy(2)
        self.assertEqual(dc.totalcost, 0)
        for key in ('a', 'b'):
            self.assertNotIn(key, dc)
        for key in ('c', 'd'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        dc.insert('e', 've', cost=7)
        self.assertEqual(dc.totalcost, 7)
        self.assertNotIn('c', dc)
        for key in ('d', 'e'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        # Original should remain unchanged.
        self.assertEqual(d.totalcost, 6)
        for key in ('a', 'b', 'c', 'd'):
            self.assertIn(key, d)
            self.assertEqual(d[key], 'v%s' % key)

    def testcopyincreasecapacity(self):
        d = util.lrucachedict(5)
        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'
        d['d'] = 'vd'

        dc = d.copy(6)
        for key in ('a', 'b', 'c', 'd'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        dc['e'] = 've'
        dc['f'] = 'vf'
        for key in ('a', 'b', 'c', 'd', 'e', 'f'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        dc['g'] = 'vg'
        self.assertNotIn('a', dc)
        for key in ('b', 'c', 'd', 'e', 'f', 'g'):
            self.assertIn(key, dc)
            self.assertEqual(dc[key], 'v%s' % key)

        # Original should remain unchanged.
        for key in ('a', 'b', 'c', 'd'):
            self.assertIn(key, d)
            self.assertEqual(d[key], 'v%s' % key)

    def testpopoldest(self):
        d = util.lrucachedict(4)
        d.insert('a', 'va', cost=10)
        d.insert('b', 'vb', cost=5)

        self.assertEqual(len(d), 2)
        self.assertEqual(d.popoldest(), ('a', 'va'))
        self.assertEqual(len(d), 1)
        self.assertEqual(d.totalcost, 5)
        self.assertEqual(d.popoldest(), ('b', 'vb'))
        self.assertEqual(len(d), 0)
        self.assertEqual(d.totalcost, 0)
        self.assertIsNone(d.popoldest())

        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'
        d['d'] = 'vd'

        self.assertEqual(d.popoldest(), ('a', 'va'))
        self.assertEqual(len(d), 3)
        for key in ('b', 'c', 'd'):
            self.assertEqual(d[key], 'v%s' % key)

        d['a'] = 'va'
        self.assertEqual(d.popoldest(), ('b', 'vb'))

    def testmaxcost(self):
        # Item cost is zero by default.
        d = util.lrucachedict(6, maxcost=10)
        d['a'] = 'va'
        d['b'] = 'vb'
        d['c'] = 'vc'
        d['d'] = 'vd'
        self.assertEqual(len(d), 4)
        self.assertEqual(d.totalcost, 0)

        d.clear()

        # Insertion to exact cost threshold works without eviction.
        d.insert('a', 'va', cost=6)
        d.insert('b', 'vb', cost=4)

        self.assertEqual(len(d), 2)
        self.assertEqual(d['a'], 'va')
        self.assertEqual(d['b'], 'vb')

        # Inserting a new element with 0 cost works.
        d['c'] = 'vc'
        self.assertEqual(len(d), 3)

        # Inserting a new element with cost putting us above high
        # water mark evicts oldest single item.
        d.insert('d', 'vd', cost=1)
        self.assertEqual(len(d), 3)
        self.assertEqual(d.totalcost, 5)
        self.assertNotIn('a', d)
        for key in ('b', 'c', 'd'):
            self.assertEqual(d[key], 'v%s' % key)

        # Inserting a new element with enough room for just itself
        # evicts all items before.
        d.insert('e', 've', cost=10)
        self.assertEqual(len(d), 1)
        self.assertEqual(d.totalcost, 10)
        self.assertIn('e', d)

        # Inserting a new element with cost greater than threshold
        # still retains that item.
        d.insert('f', 'vf', cost=11)
        self.assertEqual(len(d), 1)
        self.assertEqual(d.totalcost, 11)
        self.assertIn('f', d)

        # Inserting a new element will evict the last item since it is
        # too large.
        d['g'] = 'vg'
        self.assertEqual(len(d), 1)
        self.assertEqual(d.totalcost, 0)
        self.assertIn('g', d)

        d.clear()

        d.insert('a', 'va', cost=7)
        d.insert('b', 'vb', cost=3)
        self.assertEqual(len(d), 2)

        # Replacing a value with smaller cost won't result in eviction.
        d.insert('b', 'vb2', cost=2)
        self.assertEqual(len(d), 2)

        # Replacing a value with a higher cost will evict when threshold
        # exceeded.
        d.insert('b', 'vb3', cost=4)
        self.assertEqual(len(d), 1)
        self.assertNotIn('a', d)

    def testmaxcostcomplex(self):
        d = util.lrucachedict(100, maxcost=100)
        d.insert('a', 'va', cost=9)
        d.insert('b', 'vb', cost=21)
        d.insert('c', 'vc', cost=7)
        d.insert('d', 'vc', cost=50)
        self.assertEqual(d.totalcost, 87)

        # Inserting new element should free multiple elements so we hit
        # low water mark.
        d.insert('e', 'vd', cost=25)
        self.assertEqual(len(d), 2)
        self.assertNotIn('a', d)
        self.assertNotIn('b', d)
        self.assertNotIn('c', d)
        self.assertIn('d', d)
        self.assertIn('e', d)


if __name__ == '__main__':
    silenttestrunner.main(__name__)