# Reordering Part 2: Tables and Fractional Indexing  In a previous blog post, we looked at implementating four common reordering commands in a zoom UI or canvas app. Those commands are:

1. Send to Back
2. Send Backward
3. Bring Forward
4. Bring to Front

While the last post showed how we might implement these commands when our items were stored in an array, this post will focus on the more complex implementation for cases where items are stored in hash tables.

🚀 You can view the code and tests for this post at this CodeSandbox. A separate implementation using string indices is available here.

## Mise en place

Let's say we have an application where we're storing items in a hash table—in JavaScript, a regular object. Because tables (unlike arrays) have no "position" or index for items in the table, we'll need to keep track of that information ourselves.

``````type Item = { id: string; index: number }

type Items = Record<string, Item>

const itemsExample: Items = {
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
}
``````

In this structure, each item's `index` is stored as a property. In the example above, the item `{ id: "a", index: 1}` has the index of `1`, the item `{ id: "b", index: 2 }` has the index of `2`, etc. Note that the lowest index is `1`, and not `0`. This is a deliberate choice and we'll come back to it in a moment.

### Naive Implementation

How should we implement changes to our `index` properties? A simple approach could reproduce the same index logic as in an array, re-assigning each item's index whenever a reorder occurs.  ``````sendBackwards(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
},
["c"]
)

// {
//   a: { id: "a", index: 1 },
//   b: { id: "b", index: 3 },
//   c: { id: "c", index: 2 },
// }
``````

The problem with this approach is that making a change to one item's order might mean making a change to all items in the stack. This strategy could lead to excessive writes to a database, or larger packets being sent to ensure consistency between users in a multiplayer session, and even unnecessary renders depending on how changes are observed.

What we really want is a method that ensures that only the moving items will require new `index` values. Luckily for us, we do have such a method!

### Fractional Indexing

The strategy we'll be using is called "fractional indexing", common in databases but introduced to me by Figma's article on the topic.

In this strategy, an `index` only needs to ensure that, when our items are sorted by their `index`, the items end up in the right order. The `index` values themselves do not have to be integers or evenly distributed—all that matters is that they let us produce the correct sort.

This opens the option of putting items between other items.  ``````sendBackward(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
},
["c"]
)

// {
//   a: { id: "a", index: 1 },
//   b: { id: "b", index: 2 },
//   c: { id: "c", index: 1.5 },
// }
``````

In the example above, we've changed the order without changing items `a` or `b`, simply by changing the item `c` to sort after `a` and before `b`. While `c`'s index of `1.5` happens to be exactly between the `index` values of `a` and `b`, this isn't actually necessary—again, all that matters is that the `index` values let us produce the correct sort.

As we'll see at the end of this post, our indexes don't even need to be numbers!

Now that we have our stategy understood, let's look at implementations.

## Getting Indices Between

In our reordering functions, we'll use the following function to get the indices between two other `index` values:

``````function getIndicesBetween(
below: number | undefined,
above: number | undefined,
n: number
) {
let start: number
let step: number
if (below !== undefined && above !== undefined) {
// Put items between
step = (above - below) / (n + 1)
start = below + step
} else if (below === undefined && above !== undefined) {
// Put items below (bottom of the list)
step = above / (n + 1)
start = step
} else if (below !== undefined && above === undefined) {
// Put items above (top of the list)
start = below + 1
step = 1
} else {
throw Error("Must have either a below or an above.")
}
return Array.from(Array(n)).map((_, i) => start + i * step)
}
``````

If we're putting items at the "bottom" of the list, our `below` value will be `undefined` and our `above` value will be lowest `index` among our items. In that case, we'll create new fractions based on that `index`.

``````getIndicesBetween(undefined, 1, 1) // [0.5]
getIndicesBetween(undefined, 1, 3) // [0.25, 0.5, 0.75]
``````

This is also the reason why we've started our indices from `1` rather than from `0`. We can't cut zero into fractions!

We'll see this pattern in use when we implement `sendToBack` and `sendBackward`.  ``````sendToBack(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
},
["c"]
)

// {
//   a: { id: "a", index: 1 },
//   b: { id: "b", index: 2 },
//   c: { id: "c", index: 0.5 },
// }
``````

If we're putting items at the "top" of the list, then our `above` value will be `undefined` and our `below`value will be the highest`index`among our items. Here we can simply iterate by incrementing the that`index`.

``````getIndicesBetween(5, undefined, 1) // 
getIndicesBetween(5, undefined, 3) // [6, 7, 8]
``````

We'll see this in use when we implement `bringToFront` and `bringForward`.  ``````bringToFront(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
},
["a", "b"]
)

// {
//   a: { id: "a", index: 4 },
//   b: { id: "b", index: 5 },
//   c: { id: "c", index: 3 },
// }
``````

If we are moving items between two other items, then the `below` and `above` will be the lower and higher `index` values of the two. Here we'll create fractions based on the difference of the two `index` values.

``````getIndicesBetween(2, 3, 1) // [2.5]
getIndicesBetween(2, 3, 3) // [2.25, 2.5, 2.75]
``````

We might see this pattern with any of our methods.  ``````bringForward(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
},
["a"]
)

// {
//   a: { id: "a", index: 1.5 },
//   b: { id: "b", index: 2 },
//   c: { id: "c", index: 3 },
// }
``````

As in our last blog post, the tricky parts will be when moving multiple items that may each appear at the front, back, or middle, and that may be adjacent to one another.  ``````bringForward(
{
a: { id: "a", index: 1 },
b: { id: "b", index: 2 },
c: { id: "c", index: 3 },
d: { id: "d", index: 4 },
},
["a", "b", "d"]
)

// {
//   a: { id: "a", index: 3.33 },
//   b: { id: "b", index: 3.67 },
//   c: { id: "c", index: 3 },
//   d: { id: "d", index: 4 },
// }
``````

### Sorting by Index

One last note: in addition to our `getIndicesBetween` method, we'll also be using the following `sortByIndex` method throughout our four method implementations:

``````function sortByIndex(a: Item, b: Item) {
return a.index - b.index
}
``````

## Reordering with Fractional Indexing

### Send to Back

``````function sendToBack(items: Items, ids: string[]): Items {
const itemsArray = Object.values(items).sort(sortByIndex)
const len = itemsArray.length
if (ids.length === len) return items
const movingSet = new Set(ids.map((id) => items[id]))
let below: number | undefined
let above: number | undefined
for (const item of itemsArray) {
if (!movingSet.has(item)) {
above = item.index
break
}
movingSet.delete(item)
below = item.index
}
if (movingSet.size === 0) return items
const nextItems = { ...items }
const indices = getIndicesBetween(below, above, movingSet.size)
Array.from(movingSet.values())
.sort(sortByIndex)
.forEach((item, i) => (nextItems[item.id].index = indices[i]))
return nextItems
}
``````

For `sendToBack`, we want to move items with the provided `ids` to the bottom of the stack, or to the front of the list when it is ordered by each item's `index`.

We start by turning our items object into an array, sorted by each item's `index`. If it turns out that we're trying to move all of our items to the back, then we can bail as this would produce no change.

Next, we need to find the indices `below` and `above` our insertion range. Working from the bottom of the list, we iterate until we find a shape that is not among our set of moving items. We set this item's `index` as our `above`.  If during this iteration we first encounter an item that is among our set of moving items, then this means that the item is already at the bottom of the list. We remove the item from the set and mark the `below` as this item's index. We repeat this for any other moving item we encounter before reaching an item that is not in our moving set.  If we don't find any moving items before we find non-moving items, then the `below` value will remain `undefined`. That's okay—our `getIndicesBetween` function knows how to handle that.

Either way, we have our `below`, `above`, and a set containing all of the remaining items to move. We use `getIndicesBetween` to generate new `index` values and assign them to the items in our `movingSet`.

``````items = sendToBack(items, ["c"]) // c, a, b, d, e
``````
``````items = sendToBack(items, ["b", "d"]) // b, d, a, c, e
``````

### Bring to Front

``````function bringToFront(items: Items, ids: string[]): Items {
const itemsArray = Object.values(items).sort(sortByIndex)
const len = itemsArray.length
if (ids.length === len) return items
let below: number | undefined
let above: number | undefined
const movingSet = new Set(ids.map((id) => items[id]))
for (let i = len - 1; i > -1; i--) {
const item = itemsArray[i]
if (!movingSet.has(item)) {
below = item.index
break
}
movingSet.delete(item)
above = item.index
}
if (movingSet.size === 0) return items
const nextItems = { ...items }
const indices = getIndicesBetween(below, above, movingSet.size)
Array.from(movingSet.values())
.sort(sortByIndex)
.forEach((item, i) => (nextItems[item.id].index = indices[i]))
return nextItems
}
``````

For `bringToFront`, we perform the same work as `sendToBack`, except this time iterating down from the top of the sorted items array.  Again, if we encounter moving items before we encounter a non-moving item, we remove that item from the moving set but here mark its `index` as the `above`. Once we find an item that is not among the moving set, we mark its `index` as the `below`.  ``````items = bringToFront(items, ["b"]) // a, c, d, e, b
``````
``````items = bringToFront(items, ["a", "c"]) // b, d, e, a, c
``````

### Send Backward

``````function sendBackward(items: Items, ids: string[]): Items {
const itemsArray = Object.values(items).sort(sortByIndex)
const len = itemsArray.length
if (ids.length === len) return items
const movingIndices = new Set(ids.map((id) => itemsArray.indexOf(items[id])))
let selectIndex = -1
let isSelecting = false
let count: number
let below: number | undefined
let above: number | undefined
const nextItems = { ...items }
for (let i = len - 1; i > -1; i--) {
const isMoving = movingIndices.has(i)
if (!isSelecting && isMoving) {
isSelecting = true
selectIndex = i
} else if (isSelecting && !isMoving) {
isSelecting = false
count = selectIndex - i
above = itemsArray[i].index
below itemsArray[i - 1]?.index
const indices = getIndicesBetween(below, above, count)
for (let k = 0; k < count; k++) {
const item = itemsArray[i + k + 1]
items[item.id].index = indices[k]
}
}
}
return nextItems
}
``````

Sending an item backward is complex. Here we want to iterate from the top of the stack until we find an item that is moving. Once we've found a moving item, we'll begin "selecting" and continue iterating down until we find an item that is not moving. Here we'll stop selecting and assign indexes such that our "selected" items are placed below this item.  Then we'll continue iterating until we again reach a selected item, or we reach the front of the list. If we end with items selected, this means that those items are at the back of the list and require no change.

``````items = sendBackward(items, ["c"]) // a, c, b, d, e
``````
``````items = sendBackward(items, ["b", "c"]) // b, c, a, d, e
``````
``````items = sendBackward(items, ["c", "e"]) // a, c, b, e, d
``````

### Bring Forward

``````function bringForward(items: Items, ids: string[]): Items {
const itemsArray = Object.values(items).sort(sortByIndex)
const len = itemsArray.length
if (ids.length === len) return items
const movingIndices = new Set(ids.map((id) => itemsArray.indexOf(items[id])))
let selectIndex = -1
let isSelecting = false
let below: number | undefined
let above: number | undefined
let count: number
const nextItems = { ...items }
for (let i = 0; i < len; i++) {
const isMoving = movingIndices.has(i)
if (!isSelecting && isMoving) {
isSelecting = true
selectIndex = i
above = undefined
} else if (isSelecting && !isMoving) {
isSelecting = false
count = i - selectIndex
below = itemsArray[i].index
above = itemsArray[i + 1]?.index
const indices = getIndicesBetween(below, above, count)
for (let k = 0; k < count; k++) {
const item = itemsArray[selectIndex + k]
items[item.id].index = indices[k]
}
}
}
return nextItems
}
``````

The `bringForward` method is implemented in a similar way, but here we iterate from bottom to top. Again, if we encounter a moving item then we begin selecting. If we encounter a non-moving item while selecting then we stop selecting and insert our selected items above this item. If we end with a selection, then we know that those items were already at the top of the list.  ``````items = bringForward(items, ["b"]) // a, c, b, d, e
``````
``````items = bringForward(items, ["b", "c"]) // a, d, b, c, e
``````
``````items = bringForward(items, ["a", "c"]) // b, a, d, c, e
``````

## Wrapup

Fractional indexing makes reordering operations much cheaper in terms of writes to the document or database, as we only need to mutate the items that have actually moved.

There is one issue, however, and you may have spotted it already: how many times can you divide a number before the difference is less than your program's floating point precision?

With the implementation shown here, that number is 52.

``````let below = 1
let above = 2
for (let i = 0; i < 53; i++) {
above = below + (above - below) / 2
}
below // 1
above // 1.0000000000000002
below < above // true
``````
``````let below = 1
let above = 2
for (let i = 0; i < 53; i++) {
above = below + (above - below) / 2
}
below // 1
above // 1
below < above // false
``````

In JavaScript at least, you can split a number 52 times before the number loses precision and returns to an integer. In our case, this means that there is a certain limit to the number of times we could put items between other items.

``````for (let i = 0; i < 53; i++) {
const sorted = Object.values(items).sort((a, b) => a.index - b.index)
items = sendBackward(items, [sorted.id])
}
// Indexes are: 1, 1.0000000000000002, 1, 4, 5, 6, 7
``````

In the example above, we're moving the third item from the start backward 53 times. After the 52nd iteration, that item's index loses its precision. On the next iteration, the item in position 1 would lose its precision as well.

### Better Indexing!

The solution to this is to use a more accurate index.

Remember that the `index` value only matters insofar as it will produce the correct order when sorted. At the moment we're sorting based on the greater of two numbers; however, we can also sort alphabetically.

``````bringForward(
{
a: { id: "a", index: "a0" },
b: { id: "b", index: "a1" },
c: { id: "c", index: "a2" },
d: { id: "d", index: "a3" },
},
["b"]
)

// {
//   a: { id: "a", index: "a0"},
//   b: { id: "b", index: "a2a"},
//   c: { id: "c", index: "a2" },
//   d: { id: "d", index: "a3" },
// }
``````

This method for representing indices is described in detail in an article by David Greenspan. It lets us split indices pretty much indefinitely.

While I won't reproduce the code here, I have reproduced it in a separate CodeSandbox. The methods operate in the same was as described in this article and the code is virtually identical: the only difference is how indices are represented and how our `getIndicesBetween` method generates indices.

And with that, I believe we've covered everything there is to know about implementing our four reordering methods.

🚀 You can view the code and tests from this post at this CodeSandbox. A separate implementation using string indices is available here.

Thanks for reading! For more like this, follow me on Twitter. To support my work and nudge me toward more blogging, sponsor me on Github.

• ### Reordering Part 1: Arrays

Implementing ordering commands (Send to Back, Send Backward, Bring Forward, and Bring to Front) in an array of items.

• ### Copy to Multiplayer Project

How I used Liveblock's Storage APIs to create a new feature.