Example 1
1 12344 A 1
12345 12345 B 1
12346 100000 A 1
Example 2
1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1
Example 3
1 9999 A 1
10000 100000 C 2
Example 4
1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99
Example 5
1 20 A 1
21 30 B 1
Example 6
1 10 A 1
11 20 A 2
21 30 B 1
Example 7
1 10 A 1
12 20 A 1
21 30 B 1
case 01 - single node insertion
1 10 A 1
case 02 - inserting new head of list
1 10 A 2
11 20 A 1
case 03 - new head, matching codes, not sequential
1 9 A 1
11 20 A 1
case 04 - new head, matching codes, sequential
1 20 A 1
case 05 - new head, overlaps old head, non-matching codes
1 11 A 2
12 20 A 1
case 06 - new head, overlaps old head, matching codes
1 20 A 1
case 07 - new head overlaps head and part of second node
1 15 B 1
16 20 A 1
case 08 - new head overlaps everything #1
1 25 B 1
case 09 - new head overlaps everything #2
1 100 Z 1
case 10 - new tail, not sequential
1 10 A 1
12 20 A 1
case 11 - new tail, sequential, non-matching codes
1 10 A 1
11 20 A 2
case 12 - new tail, sequential, matching codes
1 20 A 1
case 13 - new node in unused space #1
1 9 A 1
11 20 B 1
22 30 C 1
case 14 - new node in unused space #2
1 10 A 1
11 20 B 1
21 30 C 1
case 15 - new node in unused space merges with predecessor
1 20 A 1
21 30 C 1
case 16 - new node in unused space merges with successor
1 10 A 1
11 30 C 1
case 17 - new node in unused space merges with both neighbors
1 30 A 1
case 18 - new node partially overlaps both adjacent nodes
2 4 A 2
5 15 B 1
16 20 A 1
case 19 - replace node
1 10 C 1
11 20 B 1
case 20 - extend node
1 20 C 1
21 30 B 1
case 21 - single split #1
1 10 A 1
11 15 A 4
16 20 A 2
21 30 A 3
case 22 - single split #2
1 10 A 1
11 14 A 2
15 20 A 4
21 30 A 3
case 23 - single split #3
1 10 A 1
11 20 A 2
21 24 A 3
25 35 A 4
case 24 - double split
1 10 A 1
11 13 A 2
14 17 A 4
18 20 A 2
21 30 A 3
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
case 26 - random #1: lots of merges
1 4 B 2
5 29 B 1
30 41 A 2
42 44 B 2
45 57 A 1
58 69 A 2
70 97 A 1
98 99 B 2
100 100 A 2
case 27 - random #2: few merges
1 1 O 86
2 2 U 249
3 18 A 342
19 30 E 203
31 89 Y 588
90 98 S 533
99 99 X 395
100 100 H 602
case 28 - random #3: 100 large range transactions
20926071 49856736 G 534237310
49856737 72915560 I 402426449
72915561 146561266 W 2107444157
146561267 159775295 L 16744181
159775296 165812119 W 2107444157
165812120 216177318 Q 2001031497
216177319 233970259 E 1459360201
233970260 240260142 J 2042461698
240260143 302022603 K 384935347
302022604 391240896 X 1850787105
391240897 817915452 X 297482560
817915453 1521474678 X 1850787105
1521474679 1585476056 R 353630764
1585476057 1917677723 B 1244447103
1917677724 2126055361 R 353630764
2126055362 2129919557 E 1203782074
2129919558 2136775671 I 402426449
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