> IIRC their real life solution was to leave gaps between elements (eg index 0, 100, 200… instead of 0, 1, 2) and re index when needed. Probably works well enou

> IIRC their real life solution was to leave gaps between elements (eg index 0, 100, 200… instead of 0, 1, 2) and re index when needed. Probably works well enough, what I came up with is (as you say) the idea of fractional indexing Those are the same thing. Leaving gaps is fractional indexing. It's just fixed-point rather than floating point. > an element inserted between elements 1 and 2 gets an index 11 (anything between 11-19 is fine). Between 1 and 11 is 101. Between 11 and 2 is 12 (or anything between 12-19). Note that these indexes are not numbers, they’re string that are compared lexicographically. This reminds me of the most interesting method of generating random integers in an arbitrary range from random bits: interpret the bitstream as a string representing a real number (in binary) between 0 and 1. If, for example, you want to use bits to generate a number between 0 and 5, you divide the unit interval into sixths, and examine bits until you've determined conclusively that your number lies within one of those intervals: +---- 0 = 0.000000000... ---+ | 0.000 -> 0 | | 0.00100 -> 0 | +-- 1/6 = 0.001010101... --+ | 0.0011 -> 1 | | 0.0100 -> 1 | +-- 2/6 = 0.010101010... --+ | 0.011 -> 2 | +-- 3/6 = 0.100000000... --+ | 0.100 -> 3 | +-- 4/6 = 0.101010101... --+ | 0.1011 -> 4 | | 0.1100 -> 4 | +-- 5/6 = 0.110101010... --+ | 0.11011 -> 5 | | 0.111 -> 5 | +---------------------------+