flexible-data-reordering

如何實現靈活的資料排序

最近遇到任意排序資料的需求，研究了一輪後找到了一個有趣的解決方案。

方案是一個名為 Fractional indexing 的演算法，能夠實現靈活的資料排序。

其特點為能夠在現有清單中任意位置插入新資料且不改變其他資料順序的情況下進行排序。

換個比喻，就像是可以在不變更其他人號碼牌的情況下，讓你手上的號碼牌變成任意位置，可以隨意插隊的感覺。◝( •ω• )◟

讓我們一步步探討看看。

如何排序？

如何自由調整資料排序呢？ლ(╹ε╹ლ)

有人可能會想說：「阿不就調整矩陣順序就好了？( ˘･з･)」

不過那是在同一個矩陣中才有辦法，如果是從 DB 取出來呢？

DB 內的資料通常都只能依靠某個欄位進行排序取值，不能像矩陣換個位置就行。

舉個類比情境，就像是 object 的 key-value 資料那樣，例如：

const data = {
  1: {
    name: 'cod',
    age: 10,
  },
  2: {
    name: 'cat',
    age: 1,
  },
  3: {
    name: 'dog',
    age: 4,
  },
}

需要將此 data 內容轉換成矩陣，若依據 age 排升序則為：

const list = [
  {
    name: 'cat',
    age: 1,
  },
  {
    name: 'dog',
    age: 4,
  },
  {
    name: 'cod',
    age: 10,
  },
]

object 不會保證資料順序，所以直接轉換成 array 不能保證順序正確，一定要先 sort() 才行。

剛剛依 age 欄位排序，現在需求改成可以隨意調整資料順序，該怎麼做呢？

大家可能應該都想到方法了，新增一個 order 欄位不就好了嗎？

const data = {
  1: {
    name: 'cod',
    age: 10,
    order: 1,
  },
  2: {
    name: 'cat',
    age: 1,
    order: 2,
  },
  3: {
    name: 'dog',
    age: 4,
    order: 3,
  },
}

若要移動位置，只需要調整 order 欄位的值即可。

例如：要將 dog 移到 cat 前面，只需要將 dog 的 order 改成 1.5 即可。

這就是 Fractional indexing 的核心概念！( •̀ ω •́ )✧

不過此演算法的數值範圍使用 0 到 1 之間的浮點數。

TIP

至於為甚麼是 0 到 1 之間，這個倒是沒有特別找到具體的原因，若有大大知道為甚麼還請不吝告訴我。(*´∀`)~♥

此演算法來自鼎鼎大名的 Figma，其 CTO 分享的這篇文章。

文章內有很生動的互動效果，能夠讓人更直覺地理解 Fractional indexing 運作方式。

浮點數精度

不過這裡還有個小問題，就是浮點數的精度有限，若交換太多次可能會導致因精度不足，讓排序異常。

以 JS 的數字（IEEE 754 的 64 位元雙精度浮點數）為例，小數點後大約可以正確表示到 15~17 位數字，若超過這個範圍，會出現數值遺失問題。

有沒有可以存好存滿的方法呢？

那就用字串吧！同時使用 Base62 編碼，讓字串短一點。(・∀・)９

TIP

JS 有時候也會使用字串表示數值，避免潛在的精度損失問題。

Decimal.js

甚麼是 Base62 編碼？這是一種將資料轉換成只包含 62 個可列印字元的編碼方式

62 個字元包括：

數字：0 到 9（共 10 個）
大寫英文字母：A 到 Z（共 26 個）
小寫英文字母：a 到 z（共 26 個）

總共：10 + 26 + 26 = 62 個字元

舉個例子：( ´ ▽ ` )ﾉ🌰

假設要將十進位的數字 125 轉成 Base62 編碼

125 ÷ 62 = 2 餘 1 → 第一個字元是 1
2 ÷ 62 = 0 餘 2 → 第二個字元是 2

最終得到 125 的 Base62 編碼為 21

所以 Fractional Indexing 範例程式碼才會都是奇怪的英文數字組合：

import { generateKeyBetween } from 'fractional-indexing'

const first = generateKeyBetween(null, null) // "a0"

// Insert after 1st
const second = generateKeyBetween(first, null) // "a1"

// Insert after 2nd
const third = generateKeyBetween(second, null) // "a2"

// Insert before 1st
const zeroth = generateKeyBetween(null, first) // "Zz"

// Insert in between 2nd and 3rd (midpoint)
const secondAndHalf = generateKeyBetween(second, third) // "a1V"

所以我說那個程式碼呢？

讓我們用工程師的語言來對話吧！來人啊，上程式碼！(≖‿ゝ≖)✧

這裡實作使用 fractional-indexing-jittered 這個套件。

讓我們新增一個 createDataManager function 建立一個管理資料排序的物件。

首先新增一些預期可能用到的基礎方法。

content\blog-ocean-world\flexible-data-reordering\index.ts

export function createDataManager<Data>() {
  const dataMap: Map<string, {
    data: Data;
    order: string;
  }> = new Map()

  return {
    add(data: Data) {
      return ''
    },

    moveBefore(
      id: string,
      targetId: string,
    ) { },

    moveAfter(
      id: string,
      targetId: string,
    ) { },

    delete(id: string) { },

    getAll() {
      return []
    },
  }
}

接著讓我們新增測試檔案與測試案例。

content\blog-ocean-world\flexible-data-reordering\index.test.ts

import { describe, expect, it } from 'vitest'
import { createDataManager } from './'

interface Data {
  name: string;
  value: number;
}

describe('createDataManager', () => {
  it('新增資料並取得所有資料', () => {
    const manager = createDataManager<Data>()
    manager.add({ name: 'a', value: 1 })
    manager.add({ name: 'b', value: 2 })

    const allData = manager.getAll()

    expect(allData).toHaveLength(2)
    expect(allData[0]?.name).toBe('a')
    expect(allData[1]?.name).toBe('b')
  })

  it('根據 id 刪除資料', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    manager.add({ name: 'b', value: 2 })

    manager.delete(aId)

    const allData = manager.getAll()
    expect(allData).toHaveLength(1)
    expect(allData[0]?.name).toBe('b')
  })

  it('可以移動資料到指定資料之後', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    const bId = manager.add({ name: 'b', value: 2 })
    const cId = manager.add({ name: 'c', value: 3 })

    manager.moveAfter(aId, cId)

    const allData = manager.getAll()
    expect(
      allData.map((d) => d.name),
    ).toEqual(['b', 'c', 'a'])
  })

  it('可以移動資料到指定資料之前', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    const bId = manager.add({ name: 'b', value: 2 })
    const cId = manager.add({ name: 'c', value: 3 })

    manager.moveBefore(bId, aId)

    const allData = manager.getAll()
    expect(
      allData.map((d) => d.name),
    ).toEqual(['b', 'a', 'c'])
  })
})

執行測試，結果全部失敗，不意外，因為還沒有實作任何邏輯，如果全過我會比較驚訝。(´・ω・`)

現在讓我們完成實作吧！ヾ(◍'౪`◍)ﾉﾞ

content\blog-ocean-world\flexible-data-reordering\index.ts

import { generateKeyBetween } from 'fractional-indexing-jittered'

export function createDataManager<Data>() {
  const dataMap: Map<string, {
    data: Data;
    order: string;
  }> = new Map()

  function getDataEntriesList() {
    return Array
      .from(dataMap)
      .sort((a, b) => a[1].order < b[1].order ? -1 : 1)
  }

  return {
    add(data: Data) {
      const id = crypto.randomUUID()
      const lastData = getDataEntriesList().at(-1)

      const order = generateKeyBetween(
        lastData?.[1].order ?? null,
        null,
      )
      dataMap.set(id, { data, order })
      return id
    },
    moveBefore(
      id: string,
      targetId: string,
    ) {
      const currentData = dataMap.get(id)
      if (!currentData)
        return
      const targetData = dataMap.get(targetId)
      if (!targetData)
        return

      const dataList = getDataEntriesList()
      const targetIndex = dataList.findIndex((item) => item[0] === targetId)
      const prevTarget = dataList[targetIndex - 1]

      const newOrder = generateKeyBetween(
        prevTarget?.[1].order ?? null,
        targetData.order,
      )
      currentData.order = newOrder
      dataMap.set(id, currentData)
    },
    moveAfter(
      id: string,
      targetId: string,
    ) {
      const currentData = dataMap.get(id)
      if (!currentData)
        return
      const targetData = dataMap.get(targetId)
      if (!targetData)
        return

      const dataList = getDataEntriesList()
      const targetIndex = dataList.findIndex((item) => item[0] === targetId)
      const nextTarget = dataList[targetIndex + 1]

      const newOrder = generateKeyBetween(
        targetData.order,
        nextTarget?.[1].order ?? null,
      )
      currentData.order = newOrder
      dataMap.set(id, currentData)
    },
    delete(id: string) {
      dataMap.delete(id)
    },

    getAll() {
      return getDataEntriesList()
        .map(([_, { data }]) => data)
    },
  }
}

沒意外的話，現在測試應該全部通過了。

在 getDataEntriesList 中 log 一下內容，觀察看看 order 欄位的值。

txt

{ data: { name: 'b', value: 2 }, order: 'a1' }

{ data: { name: 'b', value: 2 }, order: 'a1' }

{ data: { name: 'b', value: 2 }, order: 'a1' }
{ data: { name: 'c', value: 3 }, order: 'a2' }
{ data: { name: 'a', value: 1 }, order: 'a3' }

{ data: { name: 'b', value: 2 }, order: 'Zz' }
{ data: { name: 'a', value: 1 }, order: 'a0' }
{ data: { name: 'c', value: 3 }, order: 'a2' }

可以發現內容與官方範例程式碼一致，相當有趣。(´,,•ω•,,)

TIP

這裡的測試案例只有簡單驗證，沒有考慮到其他案例與邊界情況，大家有興趣可以自己擴充測試。( ‧ω‧)ノ╰(‧ω‧ )

完整程式碼可以在這裡找到。

拖來拖去玩玩看

光看程式碼還是有點抽象，不如直接動手拖動看看。( ´ ▽ ` )ﾉ

直接拖動項目調整順序，右側為該筆資料目前的 order 字串。

[]

拖動任一項目放開後，只有被移動的那筆資料的 order 會變化，其他資料完全不受影響。

這正是 Fractional indexing 的精髓，換成 DB 情境，就是一次移動只需要更新一筆資料。(≖‿ゝ≖)✧

多拖幾次會發現字串會變長，例如 a1V、a1Fzz，這就是字串精度所帶來的效果。

範例元件原始碼

vue

<template>
  <div class="w-full border border-gray-200 dark:border-gray-700 rounded p-3">
    <div class="text-sm opacity-70 mb-3">
      直接拖動項目調整順序，右側為該筆資料目前的 order 字串。
    </div>

    <div
      ref="list"
      class="flex flex-col gap-2 select-none"
    >
      <div
        v-for="item, index in itemList"
        :key="item.id"
        class="item flex items-center gap-2 px-3 py-2 rounded border border-gray-200 dark:border-gray-700 bg-white dark:bg-gray-800 cursor-grab"
        :class="{ 'cursor-grabbing! shadow-lg': item.id === dragState?.id }"
        :style="getItemStyle(index)"
        @pointerdown="startDrag($event, index)"
        @pointermove="updateDrag($event)"
        @pointerup="endDrag()"
        @pointercancel="endDrag()"
      >
        <svg
          class="w-4 h-4 opacity-40 shrink-0"
          viewBox="0 0 24 24"
          fill="currentColor"
        >
          <path d="M9 20q-.825 0-1.412-.587T7 18t.588-1.412T9 16t1.413.588T11 18t-.587 1.413T9 20m6 0q-.825 0-1.412-.587T13 18t.588-1.412T15 16t1.413.588T17 18t-.587 1.413T15 20m-6-6q-.825 0-1.412-.587T7 12t.588-1.412T9 10t1.413.588T11 12t-.587 1.413T9 14m6 0q-.825 0-1.412-.587T13 12t.588-1.412T15 10t1.413.588T17 12t-.587 1.413T15 14M9 8q-.825 0-1.412-.587T7 6t.588-1.412T9 4t1.413.588T11 6t-.587 1.413T9 8m6 0q-.825 0-1.412-.587T13 6t.588-1.412T15 4t1.413.588T17 6t-.587 1.413T15 8" />
        </svg>

        <span class="flex-1 truncate">{{ item.name }}</span>

        <span class="font-mono text-sm opacity-60">{{ item.order }}</span>
      </div>
    </div>

    <div class="flex gap-2 mt-3">
      <button
        class="px-3 py-1 text-sm rounded border border-gray-200 dark:border-gray-700 hover:bg-gray-100 dark:hover:bg-gray-800 disabled:opacity-40"
        :disabled="itemList.length >= maxLength"
        @click="addItem()"
      >
        新增資料
      </button>

      <button
        class="px-3 py-1 text-sm rounded border border-gray-200 dark:border-gray-700 hover:bg-gray-100 dark:hover:bg-gray-800"
        @click="resetList()"
      >
        重設
      </button>
    </div>

    <div class="mt-3 p-2 rounded bg-gray-100 dark:bg-gray-800 font-mono text-sm break-all">
      [{{ orderText }}]
    </div>
  </div>
</template>

<script setup lang="ts">
import type { CSSProperties } from 'vue'
import { generateKeyBetween } from 'fractional-indexing-jittered'
import { computed, nextTick, onMounted, ref, useTemplateRef } from 'vue'

interface Item {
  id: string;
  name: string;
  order: string;
}

interface DragState {
  id: string;
  fromIndex: number;
  toIndex: number;
  startY: number;
  deltaY: number;
  /** 相鄰項目的間距，單位 px */
  pitch: number;
}

const maxLength = 8
const nameList = ['鱈魚', '鮭魚', '鮪魚', '鯖魚', '秋刀魚', '比目魚', '沙丁魚', '旗魚']

const listElement = useTemplateRef<HTMLElement>('list')
const itemList = ref<Item[]>([])
const dragState = ref<DragState | undefined>()
/** 順序提交的當下，DOM 位置與 transform 會同時變化，需暫時關閉動畫避免項目滑過畫面 */
const transitionEnabled = ref(true)

let idCount = 0

const orderText = computed(
  () => itemList.value.map(({ order }) => `'${order}'`).join(', '),
)

function sortItemList(list: Item[]) {
  return list.sort((a, b) => a.order < b.order ? -1 : 1)
}

function addItem() {
  if (itemList.value.length >= maxLength)
    return

  const lastOrder = itemList.value.at(-1)?.order ?? null
  idCount += 1

  itemList.value = sortItemList([
    ...itemList.value,
    {
      id: `item-${idCount}`,
      name: nameList[itemList.value.length % nameList.length] ?? '不明魚類',
      order: generateKeyBetween(lastOrder, null),
    },
  ])
}

function resetList() {
  itemList.value = []
  idCount = 0

  for (let i = 0; i < 5; i++) {
    addItem()
  }
}

/** 移動資料，並依前後鄰居產生新的 order */
function moveItem(fromIndex: number, toIndex: number) {
  const list = [...itemList.value]
  const [target] = list.splice(fromIndex, 1)
  if (!target)
    return

  list.splice(toIndex, 0, target)

  target.order = generateKeyBetween(
    list[toIndex - 1]?.order ?? null,
    list[toIndex + 1]?.order ?? null,
  )

  itemList.value = sortItemList(list)
}

function getPitch() {
  const elementList = listElement.value?.children
  const first = elementList?.[0]
  const second = elementList?.[1]
  if (!(first instanceof HTMLElement) || !(second instanceof HTMLElement))
    return 0

  return second.offsetTop - first.offsetTop
}

function startDrag(event: PointerEvent, index: number) {
  const item = itemList.value[index]
  const element = event.currentTarget
  if (!item || !(element instanceof HTMLElement))
    return

  element.setPointerCapture(event.pointerId)
  dragState.value = {
    id: item.id,
    fromIndex: index,
    toIndex: index,
    startY: event.clientY,
    deltaY: 0,
    pitch: getPitch(),
  }
}

function updateDrag(event: PointerEvent) {
  const state = dragState.value
  if (!state)
    return

  const deltaY = event.clientY - state.startY
  const step = state.pitch > 0 ? Math.round(deltaY / state.pitch) : 0

  state.deltaY = deltaY
  state.toIndex = Math.min(
    Math.max(state.fromIndex + step, 0),
    itemList.value.length - 1,
  )
}

function endDrag() {
  const state = dragState.value
  if (!state)
    return

  dragState.value = undefined
  if (state.toIndex === state.fromIndex)
    return

  transitionEnabled.value = false
  moveItem(state.fromIndex, state.toIndex)

  // 等 DOM 更新並實際繪製後再恢復動畫
  nextTick(() => {
    requestAnimationFrame(() => {
      requestAnimationFrame(() => {
        transitionEnabled.value = true
      })
    })
  })
}

/** 拖動中的項目跟著手指移動，被擠開的項目則位移一個間距 */
function getItemStyle(index: number): CSSProperties {
  const baseStyle: CSSProperties = transitionEnabled.value
    ? {}
    : { transition: 'none' }

  const state = dragState.value
  if (!state)
    return baseStyle

  const { fromIndex, toIndex, deltaY, pitch } = state

  if (index === fromIndex) {
    return {
      transform: `translateY(${deltaY}px)`,
      transition: 'none',
      zIndex: 1,
    }
  }

  if (fromIndex < toIndex && index > fromIndex && index <= toIndex) {
    return { ...baseStyle, transform: `translateY(${-pitch}px)` }
  }

  if (toIndex < fromIndex && index >= toIndex && index < fromIndex) {
    return { ...baseStyle, transform: `translateY(${pitch}px)` }
  }

  return baseStyle
}

// order 由 jitter 亂數產生，須避免 SSR 與 client 內容不一致
onMounted(() => resetList())
</script>

<style scoped lang="sass">
.item
  touch-action: none
  transition: transform 0.2s
</style>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245

總結 🐟

Fractional indexing 演算法能夠實現靈活的資料排序，讓資料可以任意插隊。
浮點數有精度問題，使用 Base62 編碼的字串表示數值，可以避免精度損失。

如何實現靈活的資料排序 ​

如何排序？ ​

浮點數精度 ​

所以我說那個程式碼呢？ ​

拖來拖去玩玩看 ​

總結 🐟 ​