Example 1 1 100000 A 1 12345 12345 B 1 0 Example 2 1 100000 A 1 12345 12345 B 1 12000 12999 A 2 12345 12345 B 2 0 Example 3 1 100000 A 1 12345 12345 B 1 12000 12999 A 2 12345 12345 B 2 10000 100000 C 2 0 Example 4 1 100000 A 1 12345 12345 B 1 12000 12999 A 2 12345 12345 B 2 10000 100000 C 2 1000000 1999999 Z 99 0 Example 5 1 10 A 1 21 30 B 1 11 20 A 1 0 Example 6 21 30 B 1 1 10 A 1 11 20 A 2 0 Example 7 12 20 A 1 21 30 B 1 1 10 A 1 0 case 01 - single node insertion 1 10 A 1 0 case 02 - inserting new head of list 11 20 A 1 1 10 A 2 0 case 03 - new head, matching codes, not sequential 11 20 A 1 1 9 A 1 0 case 04 - new head, matching codes, sequential 11 20 A 1 1 10 A 1 0 case 05 - new head, overlaps old head, non-matching codes 11 20 A 1 1 11 A 2 0 case 06 - new head, overlaps old head, matching codes 11 20 A 1 1 11 A 1 0 case 07 - new head overlaps head and part of second node 11 20 A 1 2 11 A 2 1 15 B 1 0 case 08 - new head overlaps everything #1 11 20 A 1 2 11 A 2 1 25 B 1 0 case 09 - new head overlaps everything #2 11 20 A 1 21 30 B 1 31 40 C 1 41 50 D 1 51 60 E 1 61 70 F 1 71 80 G 1 81 90 H 1 1 100 Z 1 0 case 10 - new tail, not sequential 1 10 A 1 12 20 A 1 0 case 11 - new tail, sequential, non-matching codes 1 10 A 1 11 20 A 2 0 case 12 - new tail, sequential, matching codes 1 10 A 1 11 20 A 1 0 case 13 - new node in unused space #1 1 9 A 1 22 30 C 1 11 20 B 1 0 case 14 - new node in unused space #2 1 10 A 1 21 30 C 1 11 20 B 1 0 case 15 - new node in unused space merges with predecessor 1 10 A 1 21 30 C 1 11 20 A 1 0 case 16 - new node in unused space merges with successor 1 10 A 1 21 30 C 1 11 20 C 1 0 case 17 - new node in unused space merges with both neighbors 1 10 A 1 21 30 A 1 11 20 A 1 0 case 18 - new node partially overlaps both adjacent nodes 11 20 A 1 2 11 A 2 5 15 B 1 0 case 19 - replace node 1 10 A 1 11 20 B 1 1 10 C 1 0 case 20 - extend node 1 10 A 1 21 30 B 1 1 20 C 1 0 case 21 - single split #1 1 10 A 1 11 20 A 2 21 30 A 3 11 15 A 4 0 case 22 - single split #2 1 10 A 1 11 20 A 2 21 30 A 3 15 20 A 4 0 case 23 - single split #3 1 10 A 1 11 20 A 2 21 30 A 3 25 35 A 4 0 case 24 - double split 1 10 A 1 11 20 A 2 21 30 A 3 14 17 A 4 0 case 25 - exercise ranges 1 1 A 1 2 2 B 2 3 3 C 3 4 4 D 4 5 5 E 5 6 6 F 6 7 7 G 7 8 8 H 8 9 9 I 9 10 10 J 10 11 11 K 11 12 12 L 12 13 13 M 13 14 14 N 14 15 15 O 15 16 16 P 16 17 17 Q 17 18 18 R 18 19 19 S 19 20 20 T 20 21 21 U 21 22 22 V 22 23 23 W 23 24 24 X 24 25 25 Y 25 26 2147483647 Z 2147483647 0 case 26 - random #1: lots of merges 44 47 B 2 6 72 A 1 51 63 A 2 8 88 A 1 22 77 A 2 40 42 A 2 18 93 B 1 40 74 A 2 1 51 A 2 2 60 B 2 63 72 A 2 1 33 A 2 15 18 A 1 18 48 A 2 12 89 B 2 3 47 B 2 27 30 A 2 44 94 B 2 6 40 A 2 25 36 A 2 5 17 B 2 61 91 B 2 18 55 B 2 11 42 B 2 17 34 B 2 5 30 A 1 44 73 A 1 88 96 A 1 5 44 A 2 60 80 B 2 80 91 A 2 15 75 A 1 25 36 B 2 17 69 B 2 4 78 B 1 58 97 A 2 4 63 A 1 48 94 B 2 10 80 A 2 5 43 A 1 11 88 A 2 18 60 B 2 27 77 B 1 68 72 B 2 20 81 B 1 18 21 B 2 27 48 A 2 21 38 B 1 69 71 A 1 93 100 A 2 26 66 A 1 67 87 A 2 5 66 A 1 21 66 A 1 23 98 A 1 48 91 A 1 71 92 B 2 29 33 A 1 63 87 B 1 25 64 A 1 49 68 A 2 5 77 B 1 48 96 B 2 17 45 B 2 20 22 B 1 33 76 B 1 25 39 A 1 38 71 A 1 58 91 A 2 14 63 B 2 15 54 B 1 62 96 B 2 48 75 A 2 34 76 A 1 63 78 A 2 63 63 A 2 42 73 A 1 3 37 B 1 27 53 A 1 51 90 A 1 53 99 B 2 11 32 A 2 84 85 B 2 14 38 A 2 33 37 B 2 5 75 A 1 25 56 B 2 4 59 A 2 7 70 A 2 7 41 B 1 1 33 B 2 60 67 A 2 18 54 A 1 21 96 A 2 17 19 B 2 42 49 B 2 45 57 A 1 42 44 B 2 70 97 A 1 5 29 B 1 0 case 27 - random #2: few merges 62 76 H 932 12 64 U 4 52 83 C 3 16 80 K 43 2 91 K 883 32 64 Y 217 29 74 B 229 46 99 E 572 32 72 S 265 36 89 Y 634 19 68 X 438 69 73 D 13 7 36 X 237 10 17 S 740 30 88 C 116 49 84 K 383 42 45 E 203 24 25 F 842 70 85 B 657 41 42 I 601 9 16 G 378 43 62 J 142 5 64 Q 36 46 62 Q 158 55 90 D 233 74 77 A 189 3 70 K 990 32 73 P 318 17 25 L 640 16 94 W 582 36 39 T 643 39 81 I 859 29 99 Q 791 62 92 U 60 25 27 Y 787 9 45 D 607 82 94 E 186 10 39 G 353 41 73 G 236 20 36 V 261 13 72 D 282 53 91 N 430 58 89 D 959 46 50 Z 280 97 100 H 602 45 65 W 14 3 24 O 939 77 81 K 809 59 86 R 378 50 70 D 496 30 38 T 925 27 37 A 931 25 53 N 37 5 65 B 630 49 66 Y 549 3 61 H 710 13 28 R 110 66 70 N 638 49 85 G 475 11 70 D 821 62 67 Y 362 77 80 T 596 37 82 C 536 86 97 Y 737 30 96 J 233 17 39 N 242 28 33 F 43 23 28 B 740 65 76 A 877 78 90 E 572 30 65 K 711 26 69 X 267 1 32 P 391 47 58 X 866 30 60 A 888 62 76 S 330 18 36 Q 44 9 18 T 10 14 61 F 45 7 66 J 29 36 70 J 555 44 82 Z 252 13 55 J 686 24 99 X 395 30 98 Z 765 40 76 C 772 41 81 B 159 1 40 O 86 2 3 U 249 52 82 I 684 20 21 T 29 55 73 R 674 6 33 C 686 65 68 B 361 75 95 V 966 52 98 S 533 21 36 R 68 5 75 E 203 3 18 A 342 31 89 Y 588 0 case 28 - random #3: 100 large range transactions 138250230 1118314917 L 924284954 30982640 805121776 J 381254719 50784066 1592846072 B 1945395284 129631337 1671100026 G 1655172230 690161499 1667899861 Y 1128998334 946056209 1445335510 A 2012416558 1359407842 1765369697 X 819414285 1487084402 1850519382 V 1617505119 726162226 1802253205 B 180646894 349382759 1211761738 M 2080783444 93204169 1914914898 P 1812860218 341372308 643430657 A 1970646939 798978354 1985895160 Q 1011336514 332360664 351286495 L 1951020626 282519659 1993905281 L 498116100 337811901 777514087 P 316424299 1128804323 1344187392 J 496063347 210446891 986785801 T 182469865 1357703329 1539185664 E 436639666 425271169 1602449037 A 2095436319 881616101 1708199003 L 863582041 725083409 1667307795 R 739272183 890901644 2078321497 M 1193545134 541716687 1604538083 E 8064552 607442052 1726600132 G 1529442541 20926071 1838237643 G 534237310 118442595 1014093506 X 332979841 324177340 1362975597 H 1828444949 946337574 1543159458 F 1021701959 486894695 817136801 G 1143569566 167422095 2133025529 U 678532049 411448881 516775709 E 1393091737 569252634 1835433009 Z 551983265 1537597712 1619302562 W 2019601304 1246173641 1671784756 Z 1774875241 677734459 762729345 D 683615107 117221036 1910054000 D 1321423441 491892093 1150497470 L 1785032653 348321000 1820944197 R 120881713 1240905670 1440626951 A 333800899 546060539 1652662090 V 1072826577 249279872 731386845 U 369308862 125353849 1614753035 P 1806472751 563530589 1893648961 J 982242922 1919414891 2011061287 H 232175546 139842458 1975167737 R 1727088392 194352522 567288993 R 182736016 738378443 1502070077 O 446530986 566730425 1447725014 K 602239428 1410581337 2105662143 R 235756656 317555803 1908975539 Z 580730521 623563847 1608842849 J 149156049 777662262 828861006 G 1582721222 857508349 1700872428 V 977804244 214663110 782350868 W 685095092 49856737 2136775671 I 402426449 1700526344 2043007094 I 1575744955 887810974 1325625634 Y 96707893 393234924 1514656266 U 1061687912 1488690286 2129919557 E 1203782074 542303093 775261653 R 2034933945 1021953709 2095335784 G 128194995 126515671 1450475962 J 616271456 72915561 1432068780 W 2107444157 555167711 1779721360 U 1415784699 1332213711 1602207321 Q 454173583 661311988 1092079775 J 1017604706 531749457 1364264774 L 1717660202 564019660 1160179054 H 1181650137 942447086 1458326275 E 200244777 331265457 369587705 U 1705502552 398875025 1607690500 J 33158131 201811680 2071691222 E 1459360201 233970260 1083870424 J 2042461698 165812120 216177318 Q 2001031497 1611514434 1957209319 P 966843686 1869258462 1943476687 X 982600807 275819951 781287076 U 1630902459 1819396395 2038511952 K 1603077984 146561267 159775295 L 16744181 1529628670 1709794221 W 1465657449 1431065341 1859331491 B 1561586964 393280792 1620855862 O 2029814756 762278510 962348248 R 583131056 731647403 1082224977 K 2054615208 649081266 1528816480 A 1318308589 1683221249 1801247069 F 1363043389 689083959 1173850764 J 2031893191 360762555 1830915566 V 104748830 248115379 283496109 O 1042168648 667466050 989378777 M 960065781 916181113 1532189000 Q 1925351628 729829833 1627598261 C 37321953 349483516 1739352075 X 1688897603 240260143 1112124797 K 384935347 483952832 761962591 F 1691486062 1161097029 2126055361 R 353630764 302022604 1521474678 X 1850787105 391240897 817915452 X 297482560 1585476057 1917677723 B 1244447103 0 case 29 - 100 unique records 1 21474836 A 1 21474837 42949672 A 2 42949673 64424508 A 3 64424509 85899344 A 4 85899345 107374180 A 5 107374181 128849016 A 6 128849017 150323852 A 7 150323853 171798688 A 8 171798689 193273524 A 9 193273525 214748360 A 10 214748361 236223196 A 11 236223197 257698032 A 12 257698033 279172868 A 13 279172869 300647704 A 14 300647705 322122540 A 15 322122541 343597376 A 16 343597377 365072212 A 17 365072213 386547048 A 18 386547049 408021884 A 19 408021885 429496720 A 20 429496721 450971556 A 21 450971557 472446392 A 22 472446393 493921228 A 23 493921229 515396064 A 24 515396065 536870900 A 25 536870901 558345736 A 26 558345737 579820572 A 27 579820573 601295408 A 28 601295409 622770244 A 29 622770245 644245080 A 30 644245081 665719916 A 31 665719917 687194752 A 32 687194753 708669588 A 33 708669589 730144424 A 34 730144425 751619260 A 35 751619261 773094096 A 36 773094097 794568932 A 37 794568933 816043768 A 38 816043769 837518604 A 39 837518605 858993440 A 40 858993441 880468276 A 41 880468277 901943112 A 42 901943113 923417948 A 43 923417949 944892784 A 44 944892785 966367620 A 45 966367621 987842456 A 46 987842457 1009317292 A 47 1009317293 1030792128 A 48 1030792129 1052266964 A 49 1052266965 1073741800 A 50 1073741801 1095216636 A 51 1095216637 1116691472 A 52 1116691473 1138166308 A 53 1138166309 1159641144 A 54 1159641145 1181115980 A 55 1181115981 1202590816 A 56 1202590817 1224065652 A 57 1224065653 1245540488 A 58 1245540489 1267015324 A 59 1267015325 1288490160 A 60 1288490161 1309964996 A 61 1309964997 1331439832 A 62 1331439833 1352914668 A 63 1352914669 1374389504 A 64 1374389505 1395864340 A 65 1395864341 1417339176 A 66 1417339177 1438814012 A 67 1438814013 1460288848 A 68 1460288849 1481763684 A 69 1481763685 1503238520 A 70 1503238521 1524713356 A 71 1524713357 1546188192 A 72 1546188193 1567663028 A 73 1567663029 1589137864 A 74 1589137865 1610612700 A 75 1610612701 1632087536 A 76 1632087537 1653562372 A 77 1653562373 1675037208 A 78 1675037209 1696512044 A 79 1696512045 1717986880 A 80 1717986881 1739461716 A 81 1739461717 1760936552 A 82 1760936553 1782411388 A 83 1782411389 1803886224 A 84 1803886225 1825361060 A 85 1825361061 1846835896 A 86 1846835897 1868310732 A 87 1868310733 1889785568 A 88 1889785569 1911260404 A 89 1911260405 1932735240 A 90 1932735241 1954210076 A 91 1954210077 1975684912 A 92 1975684913 1997159748 A 93 1997159749 2018634584 A 94 2018634585 2040109420 A 95 2040109421 2061584256 A 96 2061584257 2083059092 A 97 2083059093 2104533928 A 98 2104533929 2126008764 A 99 2126008765 2147483647 A 100 0 END