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
