2a:null 2b:["$","title",null,{"children":"Implementing Fractional Indexing | David Greenspan | Observable"}] 30:T146d,md` See https://www.figma.com/blog/realtime-editing-of-ordered-sequences/ for an introduction to fractional indexing, including what it is used for and how it works. We're going to call the fractional indices "order keys," or "keys" for short. The simplest fractional indexing scheme imaginable is to use JavaScript numbers as keys, with 0 representing the start of the list and 1 representing the end. (Note that 0 and 1 cannot themselves be valid order keys, because for any key we need to be able to generate larger and smaller keys.) The obvious problem with this scheme is it will run out of bits of precision rather quickly. JavaScript numbers have 52 bits of "fraction," and merely appending items to a list eats up another bit each time. Item number 1 will get key 0.5, item 2 will get 0.75, then 0.875, then 0.9375, and so on. Let's solve the limited precision problem, and then look at a way to append items without growing the key size linearly in the number of items. ## Fraction strings We can represent the digits of a decimal as a string, so instead of 0.5, it's "5". When we switch from numbers to strings, the natural order we are taking advantage of is lexicographical order rather than numeric order. We will assume throughout that string order keys are compared lexicographically. For example, the string "2.1" sorts _after_ the string "10.5". We could theoretically use a custom sort comparator over strings, but it will be troublesome when we want to, for example, put the order keys in a database! So, we will always design string order keys to use standard lexicographical order. So, 0.5 is "5"; 0.75 is "75". Zero is the empty string, which sorts first. To represent one, we can use a sentinel value such as END or null. Now we have to address the issue of trailing zeros. In mathematics, trailing zeros in decimals are of course ignored. There is no difference between 0.30 and 0.3. We could deviate from this practice, now that we are in the land of strings rather than numbers, and say that "3" and "30" are distinct order keys, but the problem is there are no other digit strings that sort between them! So, it actually makes the most sense to ban trailing zeros, and treat the end of the string as equivalent to an infinite sequence of zero digits, exactly as we do when writing numbers. ## Midpoint between two fractions Now what we need is a "midpoint" algorithm that takes two string order keys and produces one in the middle. It doesn't have to be an exact midpoint, just roughly in the middle. Before writing the algorithm, let's write down the preconditions and postconditions: midpoint(A, B) * A is an order key string, or an empty string (START) * B is an order key string, greater than A, or null (END) * ...where an order key is a non-empty string of digits with no trailing zeros * Returns a key C such that A < C < B One property we'd like our midpoint algorithm to have is it doesn't needlessly grow the number of digits. We can exhaust the possibilities at the current digit length before adding a digit. Looking for a midpoint between 0.5 and 1, why not choose 0.8 instead of 0.75? And then between 0.8 and 1, we choose 0.9. Only then must we add a digit and go to 0.95. In base ten, it makes sense that we should be able to take three midpoints, adding three "bits" to the fraction, for each digit (since log base 2 of 10 is a little more than 3). Here is the algorithm for midpoint(A, B): * If there is a non-empty common prefix of A and B, set it aside and recurse on the parts of A and B where they differ. For example, given "123" and "1234", call midpoint("", "4"), and then put the common prefix "123" back at the beginning, yielding "1232". When finding the longest common prefix, we must treat A as if it is followed by as many trailing zeros as we need to match zeros in B. For example, "123" and "123004" have a common prefix of "12300". If B is null, this step does not apply. * If we get to this step, A and B must have different first digits. For the purposes of the following steps, if A is empty, we'll say the first digit is 0. If B is null, we'll say its first digit is 10 (an imaginary digit one larger than 9). We know the first digit of B is strictly greater than the first digit of A. * If there are digits that are strictly between the first digit of A and the first digit of B, pick the median one and return that. For example, if A starts with "2" and B starts with "4", return "3". * If we get to this step, B is one more than A. If the first digit of B would be a suitable return value, return that. For example, midpoint("35", "41") can return "4". If B is non-null and not just a single digit, its first digit is a suitable return value. * There's only one sliver of a case left. If we get to this step, B is the smallest string that doesn't share a first digit with A, or null. For example, if A is "823", B is "9". If A is "923", B is null. We take the first digit off of A; take the midpoint of the rest with null; and put the first digit back on the beginning. So in the first example, "8" + midpoint("23", null). In the second example, "9" + midpoint("23", null). The code and some tests follow. `31:T665,// `a` may be empty string, `b` is null or non-empty string. // `a < b` lexicographically if `b` is non-null. // no trailing zeros allowed. // digits is a string such as '0123456789' for base 10. Digits must be in // ascending character code order! function midpoint(a, b, digits) { if (b !== null && a >= b) { throw new Error(a + ' >= ' + b) } if (a.slice(-1) === '0' || (b && b.slice(-1) === '0')) { throw new Error('trailing zero') } if (b) { // remove longest common prefix. pad `a` with 0s as we // go. note that we don't need to pad `b`, because it can't // end before `a` while traversing the common prefix. let n = 0 while ((a.charAt(n) || '0') === b.charAt(n)) { n++ } if (n > 0) { return b.slice(0, n) + midpoint(a.slice(n), b.slice(n), digits) } } // first digits (or lack of digit) are different const digitA = a ? digits.indexOf(a.charAt(0)) : 0 const digitB = b !== null ? digits.indexOf(b.charAt(0)) : digits.length if (digitB - digitA > 1) { const midDigit = Math.round(0.5*(digitA + digitB)) return digits.charAt(midDigit) } else { // first digits are consecutive if (b && b.length > 1) { return b.slice(0, 1) } else { // `b` is null or has length 1 (a single digit). // the first digit of `a` is the previous digit to `b`, // or 9 if `b` is null. // given, for example, midpoint('49', '5'), return // '4' + midpoint('9', null), which will become // '4' + '9' + midpoint('', null), which is '495' return digits.charAt(digitA) + midpoint(a.slice(1), null, digits) } } }32:T11a1,md`## Appending and prepending with logarithmic key growth Now let's address the fact that even just adding items to the end of the list grows the length of the key at a linear rate. It would be nice to design a scheme where you can add to the end of the list with logarithmic key growth, and while we're at it, why not allow prepending with logarithmic key growth as well? Going back to numeric keys for a moment, what if we gave keys an integer part in addition to the fractional part? We could give list items keys like 1, 2, and 3, and only if you insert or move an item between these keys, create keys like 0.5, 1.5, and 2.5. When finding a "midpoint" between a key and END, we would always choose the smallest integer that is larger than the key. These integer keys would accumulate bits at a logarithmic rate as we increment them. We could do something similar for prepending, perhaps by using negative numbers. To represent 2.5 as a lexicographically-ordered string key, we can encode 2 as a string somehow, then encode 0.5 as "5", and then concatenate the strings. The immediate problem is how to get integers to sort in the correct order, since "2" is greater than "10" in lexicographical order. ## Encoding integers One solution is to pad the integer part to a fixed length. For example, we could decide on ten digits and count "0000000001", "0000000002", and so on as our order keys when appending items to an empty list. To illustrate how the fraction part comes in, the midpoint of "0000000001" and "0000000002" would be "00000000015". To support both prepending and appending to the list without going into the fractional part, we could start in the middle of the integers, with the first list item getting key "5000000000". Now appending and prepending actually don't change the length of the key at all, at least for a while. Once we run out of integers, we have to start using the fractional part to append or prepend new items. For example, after 9999999999 would come 9999999995. However, with base 95, ten digits gives us a little more than 65 bits of integer precision, which is many billions of billions of items. A variable-length encoding of integers that sorts correctly is also possible. We can prefix integers by their length. For example, 1 to 9 could be written A1 to A9, while 10 to 99 are written B10 to B99. In fact, we might as well use A0 to A9 and B00 to B99. Here's a system of "integer" strings that goes both down and up (note that uppercase letters come before lowercase letters in ASCII): * ... * X000 ... X999 * Y00 ... Y99 * Z0 ... Z9 * a0 ... a9 * b00 ... b99 * c000 ... c999 * ... In this scheme, the first item in an empty list gets key "a0". An item inserted after it gets "a1". An item inserted before it gets "Z9". The midpoint of "Z9" and "a0" is "Z95". The same thing works in any base, like base 62: * ... * X000 ... Xzzz * Y00 ... Yzz * Z0 ... Zz * a0 ... az * b00 ... bzz * c000 ... czzz * ... In base 62, the midpoint of "Zz" and "a0" is "ZzV". Meanwhile, the millionth item will start with "d" and be only five characters long. Note that there is a smallest and largest integer in this scheme, if we go down to A00000000000000000000000000 (A followed by 26 As) and up to zzzzzzzzzzzzzzzzzzzzzzzzzzz (z followed by 26 more zs). The set of integers is astronomical, but finite. Code and tests for incrementing and decrementing variable-length integers follow. ## Fixed or variable length? I don't see much difference between using fixed-length and variable-length integers, except that the fixed length is kind of ugly and takes up extra bytes. The extra complexity of variable-length integers is entirely internal to the variable-length integer module. Which one to choose is a matter of taste. Whichever integer system is used, the following operations are needed, and define an integer system: * Validate an integer * Extract an integer from the beginning of a string * Get zero * Increment an integer, returning null if it is the largest available integer * Decrement an integer, returning null if it is the smallest available integer * As a convenience, get the smallest integer (though an integer can be tested to see if it is the smallest by trying to decrement it) A nicely-factored set of modules would have the integer system be a pluggable object implementing an interface, which is passed in similarly to how digits are passed in in this notebook. Here, however, we just choose variable-length integers. `33:Tc8b,md` ## Algorithm combining integer and fraction encoding Now we'll specify a new kind of order key that has integer and fraction parts, and a new algorithm, generateKeyBetween(A, B), which has the property that prepending and appending items results in key growth that is logarithmic rather than linear in the number of items. An order key is now a string which can easily and unambiguously be divided into two strings, an integer part followed by a fraction part. The integer part will never be an empty string, and the fraction part will never be null. Instead of using the empty string as START and null as END, we'll refer explicitly to START and END, and use null to mean START or END when we need a sentinel value in JavaScript. Note that the empty string was not a valid order key before, but it is a valid fraction now, but only as long as the integer part is not equal to the smallest integer. We can't allow there to be an order key such that we can't construct a smaller order key, and this would happen if we allowed the smallest available integer as a key with no fraction part. (Even though this case will not be reached by prepending items to a list in normal operation because it would require an astronomical number of items, we don't want any undefined edge cases.) Ok, so in terms of preconditions and postconditions, we have: generateKeyBetween(A, B) * A is an order key string, or START * B is an order key string, greater than A, or END * An order key string is an integer part followed by a fraction part * The fraction part consists of zero or more digits with no trailing zeros * If the fraction part is empty, the integer part may not be the smallest available integer * Returns a key C such that A < C < B The algorithm will use the fraction midpoint algorithm unchanged, as well as the capability to increment and decrement integers. There is no need to actually convert our "string integers" into numeric integers or vice versa. We just need a "zero" and a way to increment and decrement. Algorithm: * If A is START and B is END, return the "zero" integer with an empty fraction part. * If A is START and the integer part of B is the smallest available integer, make the fraction part of B smaller using the midpoint algorithm with the empty string as the first argument. Otherwise, if A is START, return the largest integer less than B, with an empty fraction part. * If B is END, return the smallest integer greater than A, with an empty fraction part. If there is no such integer, make the fraction part of A larger, using the midpoint algorithm with a second argument of null. * If A and B have the same integer part, find the midpoint of the fraction parts, and return a key consisting of the common integer part and the midpoint. * Increment the integer part of A. (This is always possible, because B has a larger integer part.) If a key consisting of this integer and no fraction is less than B, return it. In other words, if A is the string equivalent of the number 3.5, see if we can return 4. * Otherwise, take the integer part of A and make the fraction part larger, using the midpoint algorithm with a second argument of null. Code and tests follow. `34:T4d5,// `a` is an order key or null (START). // `b` is an order key or null (END). // `a < b` lexicographically if both are non-null. // digits is a string such as '0123456789' for base 10. Digits must be in // ascending character code order! function generateKeyBetween(a, b, digits) { if (a !== null) { validateOrderKey(a) } if (b !== null) { validateOrderKey(b) } if (a !== null && b !== null && a >= b) { throw new Error(a + ' >= ' + b) } if (a === null && b === null) { return INTEGER_ZERO } if (a === null) { const ib = getIntegerPart(b) const fb = b.slice(ib.length) if (ib === SMALLEST_INTEGER) { return ib + midpoint('', fb, digits) } return ib < b ? ib : decrementInteger(ib, digits) } if (b === null) { const ia = getIntegerPart(a) const fa = a.slice(ia.length) const i = incrementInteger(ia, digits) return i === null ? ia + midpoint(fa, null, digits) : i } const ia = getIntegerPart(a) const fa = a.slice(ia.length) const ib = getIntegerPart(b) const fb = b.slice(ib.length) if (ia === ib) { return ia + midpoint(fa, fb, digits) } const i = incrementInteger(ia, digits) return i < b ? i : ia + midpoint(fa, null, digits) }35:T44f,// same preconditions as generateKeysBetween. // n >= 0. // Returns an array of n distinct keys in sorted order. // If a and b are both null, returns [a0, a1, ...] // If one or the other is null, returns consecutive "integer" // keys. Otherwise, returns relatively short keys between // a and b. function generateNKeysBetween(a, b, n, digits) { if (n === 0) { return [] } if (n === 1) { return [generateKeyBetween(a, b, digits)] } if (b === null) { let c = generateKeyBetween(a, b, digits) const result = [c] for (let i = 0; i < n-1; i++) { c = generateKeyBetween(c, b, digits) result.push(c) } return result } if (a === null) { let c = generateKeyBetween(a, b, digits) const result = [c] for (let i = 0; i < n-1; i++) { c = generateKeyBetween(a, c, digits) result.push(c) } result.reverse() return result } const mid = Math.floor(n/2) const c = generateKeyBetween(a, b, digits) return [ ...generateNKeysBetween(a, c, mid, digits), c, ...generateNKeysBetween(c, b, n - mid - 1, digits), ] }36:[] 2e:{"id":"2da77b9397416cf6","slug":"implementing-fractional-indexing","title":"Implementing Fractional Indexing","thumbnail":"835ec1470367936a26b5ec5704a248cbb8fe8510c394a1ae20e1e6caea14d766","access_level":"public","create_time":"$D2020-03-09T18:10:36.896Z","update_time":"$D2020-10-12T10:36:38.073Z","view_time":null,"first_public_time":"$D2020-03-09T23:27:19.054Z","fork":false,"stars":24,"starred":false,"owner":{"type":"team","id":"9524fa4c545c4564","login":"dgreensp","name":"David Greenspan","avatar_url":"https://avatars-next.observableusercontent.com/a52d796376b4fef1271ef648efe6960b88a77edb4ad1785f1677fe0c77fce94e","tier":"starter_2024"},"version":547,"publish_version":547,"role":null,"authored":false,"authors":[{"type":"individual","id":"fb9782ebcab0e79b","login":"dgreensp","name":"David Greenspan","avatar_url":"https://avatars-next.observableusercontent.com/a52d796376b4fef1271ef648efe6960b88a77edb4ad1785f1677fe0c77fce94e","tier":null}],"members":[{"type":"individual","id":"fb9782ebcab0e79b","login":"dgreensp","name":"David Greenspan","avatar_url":"https://avatars-next.observableusercontent.com/a52d796376b4fef1271ef648efe6960b88a77edb4ad1785f1677fe0c77fce94e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":12,"collection":null,"type":"notebook","body":{"title":"Implementing Fractional Indexing","cells":[{"id":0,"value":"md`# Implementing Fractional Indexing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":100,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":148,"value":"function runTests(bigString, func, digits) {\n function test(digits, ...args) {\n const result = args.pop()\n try {\n return func(...args, digits) === result\n } catch {\n return result === '!error'\n }\n }\n return bigString.split('\\n')\n .map(x => x.trim())\n .filter(x => x)\n .map(x => (test(digits, ...x.split(' ').map(\n (y, i) => y === '[' ? '' : y === ']' ? null : y === '|' ? null : y)) ? 'PASS' : 'FAIL') + ' ' + x).join('\\n')\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":88,"value":"md`In the following tests, \\`[\\` expands to \\`\"\"\\`, and \\`]\\` expands to \\`null\\`.\n\nFor each test, you will see PASS or FAIL followed by the input to the test. The input to the test consists of the arguments to the function being tested (in this case, midpoint), followed by the expected result.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":176,"value":"BASE_10_DIGITS = '0123456789'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"runTests(`\n[ ] 5\n5 ] 8\n8 ] 9\n9 ] 95\n95 ] 98\n98 ] 99\n99 ] 995\n1 2 15\n2 1 !error\n[ [ !error\n0 1 !error\n1 10 !error\n11 1 !error\n001 001002 001001\n001 001001 0010005\n[ 5 3\n[ 3 2\n[ 2 1\n[ 1 05\n05 1 08\n[ 05 03\n[ 03 02\n[ 02 01\n[ 01 005\n499 5 4995\n`, midpoint, BASE_10_DIGITS)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":145,"value":"md`## Higher bases\n\nLet's now switch from base 10 to base 62. We could also use base 64, or base 95 as in the Figma article, but for illustration purposes, we use the numbers and the uppercase and lowercase letters, for a total of 62 digits.\n\nThere's no new code here, just new tests.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":181,"value":"BASE_62_DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":155,"value":"runTests(`\n[ ] V\nV ] l\nl ] t\nt ] x\nx ] z\nz ] zV\nzV ] zl\nzl ] zt\nzt ] zx\nzx ] zz\nzz ] zzV\n1 2 1V\n2 1 !error\n[ [ !error\n0 1 !error\n1 10 !error\n11 1 !error\n001 001002 001001\n001 001001 001000V\n[ V G\n[ G 8\n[ 8 4\n[ 4 2\n[ 2 1\n[ 1 0V\n0V 1 0l\n[ 0G 08\n[ 08 04\n[ 02 01\n[ 01 00V\n4zz 5 4zzV\n`, midpoint, BASE_62_DIGITS)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":212,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":237,"value":"INTEGER_ZERO = 'a0'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":481,"value":"SMALLEST_INTEGER = \"A00000000000000000000000000\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":454,"value":"function getIntegerLength(head) {\n if (head >= 'a' && head <= 'z') {\n return head.charCodeAt(0) - 'a'.charCodeAt(0) + 2\n } else if (head >= 'A' && head <= 'Z') {\n return 'Z'.charCodeAt(0) - head.charCodeAt(0) + 2\n } else {\n throw new Error('Invalid order key head: ' + head) \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":462,"value":"function validateInteger(int) {\n if (int.length !== getIntegerLength(int.charAt(0))) {\n throw new Error('invalid integer part of order key: ' + int) \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":240,"value":"// note that this may return null, as there is a largest integer\nfunction incrementInteger(x, digits) {\n validateInteger(x)\n const [head, ...digs] = x.split('')\n let carry = true\n for (let i = digs.length - 1; carry && i >= 0; i--) {\n const d = digits.indexOf(digs[i]) + 1\n if (d === digits.length) {\n digs[i] = '0'\n } else {\n digs[i] = digits.charAt(d)\n carry = false\n }\n }\n if (carry) {\n if (head === 'Z') {\n return 'a0' \n }\n if (head === 'z') {\n return null \n }\n const h = String.fromCharCode(head.charCodeAt(0) + 1)\n if (h > 'a') {\n digs.push('0') \n } else {\n digs.pop() \n }\n return h + digs.join('')\n } else {\n return head + digs.join('') \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":516,"value":"md`In these tests, a vertical bar represents a null result.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":247,"value":"runTests(`\na0 a1\na1 a2\naz b00\nb0z b10\nb1z b20\nbzz c000\nZy Zz\nZz a0\nYzy Yzz\nYzz Z0\nXyzz Xz00\nXz00 Xz01\nXzzz Y00\ndABzz dAC00\nzzzzzzzzzzzzzzzzzzzzzzzzzzz |\n`, incrementInteger, BASE_62_DIGITS)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":292,"value":"// note that this may return null, as there is a smallest integer\nfunction decrementInteger(x, digits) {\n validateInteger(x)\n const [head, ...digs] = x.split('')\n let borrow = true\n for (let i = digs.length - 1; borrow && i >= 0; i--) {\n const d = digits.indexOf(digs[i]) - 1\n if (d === -1) {\n digs[i] = digits.slice(-1)\n } else {\n digs[i] = digits.charAt(d)\n borrow = false\n }\n }\n if (borrow) {\n if (head === 'a') {\n return 'Z' + digits.slice(-1) \n }\n if (head === 'A') {\n return null \n }\n const h = String.fromCharCode(head.charCodeAt(0) - 1)\n if (h < 'Z') {\n digs.push(digits.slice(-1)) \n } else {\n digs.pop() \n }\n return h + digs.join('')\n } else {\n return head + digs.join('') \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":297,"value":"runTests(`\na1 a0\na2 a1\nb00 az\nb10 b0z\nb20 b1z\nc000 bzz\nZz Zy\na0 Zz\nYzz Yzy\nZ0 Yzz\nXz00 Xyzz\nXz01 Xz00\nY00 Xzzz\ndAC00 dABzz\nA00000000000000000000000000 |\n`, decrementInteger, BASE_62_DIGITS)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":270,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":304,"value":"function getIntegerPart(key) {\n const integerPartLength = getIntegerLength(key.charAt(0))\n if (integerPartLength > key.length) {\n throw new Error('invalid order key: ' + key) \n }\n return key.slice(0, integerPartLength)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":492,"value":"function validateOrderKey(key) {\n if (key === SMALLEST_INTEGER) {\n throw new Error('invalid order key: ' + key) \n }\n // getIntegerPart will throw if the first character is bad,\n // or the key is too short. we'd call it to check these things\n // even if we didn't need the result\n const i = getIntegerPart(key)\n const f = key.slice(i.length)\n if (f.slice(-1) === '0') {\n throw new Error('invalid order key: ' + key) \n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":303,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":438,"value":"md`In these tests, a vertical bar represents START or END.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":322,"value":"runTests(`\n| | a0\n| a0 Zz\na0 | a1\na0 a1 a0V\na0V a1 a0l\nZz a0 ZzV\nZz a1 a0\n| Y00 Xzzz\nbzz | c000\na0 a0V a0G\na0 a0G a08\nb125 b129 b127\na0 a1V a1\nZz a01 a0\n| a0V a0\n| b999 b99\n| A00000000000000000000000000 !error\n| A000000000000000000000000001 A000000000000000000000000000V\nzzzzzzzzzzzzzzzzzzzzzzzzzzy | zzzzzzzzzzzzzzzzzzzzzzzzzzz\nzzzzzzzzzzzzzzzzzzzzzzzzzzz | zzzzzzzzzzzzzzzzzzzzzzzzzzzV\na00 | !error\na00 a1 !error\n0 1 !error\na1 a0 !error\n`, generateKeyBetween, BASE_62_DIGITS)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":241,"value":"md`## Bulk insert and move\n\nHow should one generate N keys betweeen A and B, which is needed when moving or inserting multiple items into the middle of a list? It could be a large number of items.\n\nNormally, we must accept that a series of N moves or inserts that place items in the middle of the list (rather than at the beginning or end) may result in keys with a length that is linear in N. However, in the case of a bulk insert or move, we can do better. We can generate N keys at once in a \"balanced\" way. One way to do this would be to write a variant of the midpoint algorithm that seeks to \"spread out\" N keys by making the most of each level. For example, when generating keys between 0.1 and 0.4, it would be sure to start some keys with 0.1, some with 0.2, and some with 0.3. An alternative that is much simpler is to call the existing generateKeyBetween in a recursive way.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":386,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":388,"value":"generateNKeysBetween(null, null, 5, BASE_10_DIGITS).join(' ')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":409,"value":"generateNKeysBetween(\"a4\", null, 10, BASE_10_DIGITS).join(' ')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":413,"value":"generateNKeysBetween(null, \"a0\", 5, BASE_10_DIGITS).join(' ')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":418,"value":"generateNKeysBetween(\"a0\", \"a2\", 20, BASE_10_DIGITS).join(' ')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":535,"value":"md`---\n**License:** CC0 (no rights reserved).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 2f:"$2e:body"