<列表項(xiàng) top 坐標(biāo)值> = <上一項(xiàng) top 坐標(biāo)值> + <上一項(xiàng)的高度值>

// 假設(shè)使用該數(shù)組存儲列表每一項(xiàng)的高度
const itemHeightStore = [20, 20, 20, 20, 20]

// 使用該方法，可以算出列表中指定項(xiàng)的 top 坐標(biāo)值
const getTop = (index) => {
 let sum = 0
 while (index--) sum += itemHeightStore[index] || 0
 return sum
}
// 第一項(xiàng)
getTop(0) // 0

// 第二項(xiàng)
getTop(1) // 20
// ...

const range = {
 start: 0,
 end: 4,
 value: 20
}

// Avl.ts
const SLIGHTLY_UNBALANCED_RIGHT = -1
const SLIGHTLY_UNBALANCED_LEFT = 1
const UNBALANCED_RIGHT = -2
const UNBALANCED_LEFT = 2
// 樹結(jié)點(diǎn)
class AvlNode<K extends any = any> {
 key: any
 left: AvlNode<K> | null
 right: AvlNode<K> | null
 parent: AvlNode<K> | null
 _height: number
 _prevHeight: number
 constructor(key: K) {
  this.key = key
  this.left = null
  this.right = null
  this.parent = null
  this._height = 0
  this._prevHeight = 0
 }
 // 刷新前的高度，方便平衡操作
 get prevHeight() {
  return this._prevHeight | 0
 }
 get height() {
  return this._height | 0
 }
 set height(value) {
  this._prevHeight = this._height | 0
  this._height = value | 0
 }
 // 左子樹高度
 get leftHeight() {
  if (this.left === null) return -1
  return this.left.height | 0
 }
 // 右子樹高度
 get rightHeight() {
  if (this.right === null) return -1
  return this.right.height | 0
 }
 // 平衡因子
 get balanceFactor() {
  return this.leftHeight - this.rightHeight
 }
 updateHeight() {
  const { leftHeight, rightHeight } = this
  const height = ((leftHeight > rightHeight ? leftHeight : rightHeight) + 1) | 0
  this.height = height
 }
}
// AVL 樹
export class Avl<K extends any = any> {
 _root: AvlNode<K> | null
 _size: number
 constructor() {
  this._root = null
  this._size = 0
 }
 get size() {
  return this._size
 }
 // 插入節(jié)點(diǎn)
 insert(key: K) {
  const node = new AvlNode<K>(key)
  const insertPoint = this._nodeInsert(node)
  // 本次插入是重復(fù)結(jié)點(diǎn)，直接更新 key / value
  // 無新結(jié)點(diǎn)插入，所以無需進(jìn)行插入后的調(diào)整
  if (insertPoint == null) return
  // 新增結(jié)點(diǎn)成功時，回溯調(diào)整搜索路徑上的結(jié)點(diǎn)
  this._adjustAfterInsertion(insertPoint)
 }
 // 刪除節(jié)點(diǎn)，返回是否成功刪除結(jié)點(diǎn)
 delete(key: K): boolean {
  // 搜索待刪除結(jié)點(diǎn)
  const targetNode = this._nodeSearch(key)
  // 未找到 value 對應(yīng)結(jié)點(diǎn)
  if (targetNode == null) return false
  // 執(zhí)行刪除結(jié)點(diǎn)操作
  const backtracking = this._nodeErase(targetNode)
  const parent = backtracking[0]
  // 回溯調(diào)整搜索路徑上的結(jié)點(diǎn)
  if (parent !== null) {
   this._adjustAfterRemoval(parent)
  }
  return true
 }
 // 通過 key 查找包含該 key 范圍的節(jié)點(diǎn) key
 search(key: K) {
  const node = this._nodeSearch(key)
  if (node !== null) return node.key
  return null
 }
 // 搜索 start 、end 兩個 key 之間的所有 key 列表
 searchRange(start: K, end: K) {
  const results: K[] = []
  // 找到符合條件的 root 節(jié)點(diǎn)
  let root = this._root
  while (root !== null) {
   const result1 = start.compareTo(root.key)
   const result2 = end.compareTo(root.key)
   // 當(dāng)前節(jié)點(diǎn)比 start 小，不再搜索左子樹
   if (result1 > 0) {
    root = root.right
    continue
   }
   // 當(dāng)前節(jié)點(diǎn)大于 end，不再搜索右子樹
   if (result2 < 0) {
    root = root.left
    continue
   }
   break
  }
  if (!root) return results
  const stack = []
  let current: AvlNode<K> | null = root
  while (stack.length || current) {
   while (current) {
    stack.push(current)
    // 當(dāng)前節(jié)點(diǎn)比 start 小，不再搜索 current 的左子樹
    if (start.compareTo(current.key) > 0) break
    current = current.left
   }
   if (stack.length) {
    // 指向棧頂
    current = stack[stack.length - 1]
    const gteStart = start.compareTo(current.key) <= 0
    const lteEnd = end.compareTo(current.key) >= 0
    if (gteStart && lteEnd) {
     results.push(current.key)
    }
    stack.pop()
    // 只有 current 比 end 小，才繼續(xù)搜索 current 的右子樹
    if (lteEnd) {
     current = current.right
    }
    else {
     current = null
    }
   }
  }
  return results
 }
 // 增加結(jié)點(diǎn)數(shù)量
 _increaseSize() {
  this._size += 1
 }
 // 減少結(jié)點(diǎn)數(shù)量
 _decreaseSize() {
  this._size -= 1
 }
 // 設(shè)置左子結(jié)點(diǎn)，同時維護(hù) parent 關(guān)系
 _setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
  // 斷開舊 left 結(jié)點(diǎn)
  if (node.left !== null) {
   node.left.parent = null
  }
  // 連接新結(jié)點(diǎn)
  if (child !== null) {
   // 從舊 parent 中斷開
   if (child.parent !== null) {
    child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
   }
   child.parent = node
  }
  node.left = child
 }
 // 設(shè)置右子結(jié)點(diǎn)，同時維護(hù) parent 關(guān)系
 _setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
  // 斷開舊 right 結(jié)點(diǎn)
  if (node.right !== null) {
   node.right.parent = null
  }
  // 連接新結(jié)點(diǎn)
  if (child !== null) {
   // 從舊 parent 中斷開
   if (child.parent !== null) {
    child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
   }
   child.parent = node
  }
  node.right = child
 }
 // 獲取中序遍歷順序的前驅(qū)結(jié)點(diǎn)
 _inorderPredecessor(node: AvlNode<K> | null) {
  if (node == null) return null
  // 1. 有左子樹，找到左子樹最大元素
  if (node.left !== null) {
   return this._maximumNode(node.left)
  }
  // 2. 沒有左子樹，往上搜索
  let parent = node.parent
  while (parent != null) {
   if (node == parent.right) {
    return parent
   }
   node = parent
   parent = node.parent
  }
  // 4. 搜索到根
  return null
 }
 // 獲取最大的結(jié)點(diǎn)
 _maximumNode(subRoot: AvlNode<K>) {
  let current = subRoot
  while (current.right !== null) current = current.right
  return current
 }
 // 設(shè)置根結(jié)點(diǎn)
 _setRoot(node: AvlNode<K> | null) {
  if (node === null) {
   this._root = null
   return
  }
  this._root = node
  // 如果本身在樹中，則從樹中脫落，成為獨(dú)立的樹根
  if (node.parent !== null) {
   node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)
   node.parent = null
  }
 }
 // 將樹上某個結(jié)點(diǎn)替換成另一個結(jié)點(diǎn)
 private _replaceNode(node: AvlNode<K>, replacer: AvlNode<K> | null) {
  if (node === replacer) return node
  // node 為 root 的情況
  if (node === this._root) {
   this._setRoot(replacer)
  }
  else {
   // 非 root，有父結(jié)點(diǎn)的情況
   const parent = node.parent as AvlNode<K>
   if (parent.left === node) this._setLeft(parent, replacer)
   else this._setRight(parent, replacer)
  }
  return node
 }
 // 左旋，返回新頂點(diǎn)，注意旋轉(zhuǎn)完畢會從原本的樹上脫落
 private _rotateLeft(node: AvlNode<K>) {
  const parent = node.parent
  // 記錄原本在樹上的位置
  const isLeft = parent !== null && parent.left == node
  // 旋轉(zhuǎn)
  const pivot = node.right as AvlNode<K>
  const pivotLeft = pivot.left
  this._setRight(node, pivotLeft)
  this._setLeft(pivot, node)
  // 旋轉(zhuǎn)完畢
  // 新頂點(diǎn)接上樹上原本的位置
  if (parent !== null) {
   if (isLeft) this._setLeft(parent, pivot)
   else this._setRight(parent, pivot)
  }
  // ---
  if (node === this._root) {
   this._setRoot(pivot)
  }
  node.updateHeight()
  pivot.updateHeight()
  return pivot
 }
 // 右旋，返回新頂點(diǎn)，注意旋轉(zhuǎn)完畢會從原本的樹上脫落
 private _rotateRight(node: AvlNode<K>) {
  const parent = node.parent
  // 記錄原本在樹上的位置
  const isLeft = parent !== null && parent.left === node
  // 旋轉(zhuǎn)
  const pivot = node.left as AvlNode<K>
  const pivotRight = pivot.right
  this._setLeft(node, pivotRight)
  this._setRight(pivot, node)
  // 旋轉(zhuǎn)完畢
  // 新頂點(diǎn)接上樹上原本的位置
  if (parent !== null) {
   if (isLeft) this._setLeft(parent, pivot)
   else this._setRight(parent, pivot)
  }
  // ---
  if (node === this._root) {
   this._setRoot(pivot)
  }
  node.updateHeight()
  pivot.updateHeight()
  return pivot
 }
 // 搜索 Node
 private _nodeSearch(key: K) {
  let current = this._root
  while (current !== null) {
   let result = key.compareTo(current.key)
   if (result === 0) return current
   if (result < 0) current = current.left
   else current = current.right
  }
  return null
 }
 // 在樹里插入結(jié)點(diǎn)或者刷新重復(fù)結(jié)點(diǎn)
 // 返回新插入（或刷新）的結(jié)點(diǎn)
 private _nodeInsert(node: AvlNode<K>) {
  // 空樹
  if (this._root === null) {
   this._setRoot(node)
   this._increaseSize()
   return null
  }
  const key = node.key
  let current = this._root
  // 查找待插入的位置
  while (true) {
   const result = key.compareTo(current.key)
   if (result > 0) {
    if (current.right === null) {
     this._setRight(current, node)
     this._increaseSize()
     return current
    }
    current = current.right
   }
   else if (result < 0) {
    if (current.left === null) {
     this._setLeft(current, node)
     this._increaseSize()
     return current
    }
    current = current.left
   }
   else {
    // No duplicates, just update key
    current.key = key
    return null
   }
  }
 }
 // 從樹上移除一個結(jié)點(diǎn)
 private _nodeErase(node: AvlNode<K>) {
  // 同時擁有左右子樹
  // 先轉(zhuǎn)換成只有一顆子樹的情況再統(tǒng)一處理
  if (node.left !== null && node.right !== null) {
   const replacer = this._inorderPredecessor(node)!
   // 使用前驅(qū)結(jié)點(diǎn)替換身份
   // 此時問題轉(zhuǎn)換成刪掉替代結(jié)點(diǎn)（前驅(qū)），
   // 從而簡化成只有一個子結(jié)點(diǎn)的刪除情況
   node.key = replacer.key
   // 修改 node 指針
   node = replacer
  }
  // 刪除點(diǎn)的父結(jié)點(diǎn)
  const parent = node.parent
  // 待刪結(jié)點(diǎn)少于兩顆子樹時，使用子樹 (或 null，沒子樹時) 頂替移除的結(jié)點(diǎn)即可
  const child = node.left || node.right
  this._replaceNode(node, child)
  this._decreaseSize()
  return [ parent, child, node ]
 }
 // AVL 樹插入結(jié)點(diǎn)后調(diào)整動作
 // 自底向上調(diào)整結(jié)點(diǎn)的高度
 // 遇到離 current 最近的不平衡點(diǎn)需要做旋轉(zhuǎn)調(diào)整 
 // 注意: 對最近的不平衡點(diǎn)調(diào)整后 或者 結(jié)點(diǎn)的高度值沒有變化時
 // 上層結(jié)點(diǎn)便不需要更新 
 // 調(diào)整次數(shù)不大于1
 _adjustAfterInsertion(backtracking: AvlNode<K> | null) {
  let current = backtracking
  // 往上回溯，查找最近的不平衡結(jié)點(diǎn)
  while (current !== null) {
   // 更新高度
   current.updateHeight()
   // 插入前后，回溯途徑結(jié)點(diǎn)的高度沒有變化，則無需繼續(xù)回溯調(diào)整
   if (current.height === current.prevHeight) break
   // 若找到不平衡結(jié)點(diǎn)，執(zhí)行一次調(diào)整即可
   if (this._isUnbalanced(current)) {
    this._rebalance(current)
    // 調(diào)整過，則上層無需再調(diào)整了
    break
   }
   current = current.parent
  }
 }
 // AVL樹刪除結(jié)點(diǎn)后調(diào)整動作
 // 自底向上調(diào)整結(jié)點(diǎn)的高度
 // 遇到離 current 最近的不平衡點(diǎn)需要做旋轉(zhuǎn)調(diào)整
 // 注意: 對最近的不平衡點(diǎn)調(diào)整后，其上層結(jié)點(diǎn)仍然可能需要調(diào)整
 // 調(diào)整次數(shù)可能不止一次
 _adjustAfterRemoval(backtracking: AvlNode<K> | null) {
  let current = backtracking
  while (current !== null) {
   // 更新高度
   current.updateHeight()
   // 刪除前后，回溯途徑結(jié)點(diǎn)的高度沒有變化，則無需繼續(xù)回溯調(diào)整
   if (current.height === current.prevHeight) break
   if (this._isUnbalanced(current)) {
    this._rebalance(current)
   }
   // 與插入不同，調(diào)整過后，仍然需要繼續(xù)往上回溯
   // 上層結(jié)點(diǎn)（若有）仍需判斷是否需要調(diào)整
   current = current.parent
  }
 }
 // LL
 _adjustLeftLeft(node: AvlNode<K>) {
  return this._rotateRight(node)
 }
 // RR
 _adjustRightRight(node: AvlNode<K>) {
  return this._rotateLeft(node)
 }
 // LR
 _adjustLeftRight(node: AvlNode<K>) {
  this._rotateLeft(node.left!)
  return this._rotateRight(node)
 }
 // RL
 _adjustRightLeft(node: AvlNode<K>) {
  this._rotateRight(node.right!)
  return this._rotateLeft(node)
 }
 // 檢查結(jié)點(diǎn)是否平衡
 _isUnbalanced(node: AvlNode<K>) {
  const factor = node.balanceFactor
  return factor === UNBALANCED_RIGHT || factor === UNBALANCED_LEFT
 }
 // 重新平衡
 _rebalance(node: AvlNode<K>) {
  const factor = node.balanceFactor
  // Right subtree longer (node.factor: -2)
  if (factor === UNBALANCED_RIGHT) {
   let right = node.right!
   // RL, node.right.factor: 1
   if (right.balanceFactor === SLIGHTLY_UNBALANCED_LEFT) {
    return this._adjustRightLeft(node)
   }
   else {
    // RR, node.right.factor: 0|-1
    // 即 right.rightHeight >= right.leftHeight
    return this._adjustRightRight(node)
   }
  }
  else if (factor === UNBALANCED_LEFT) {
   // Left subtree longer (node.factor: 2)
   let left = node.left!
   // LR, node.left.factor: -1
   if (left.balanceFactor === SLIGHTLY_UNBALANCED_RIGHT) {
    return this._adjustLeftRight(node)
   }
   else {
    // LL, node.left.factor: 1 | 0
    // 即 left.leftHeight >= left.rightHeight
    return this._adjustLeftLeft(node)
   }
  }
  return node
 }
}
export function createAvl() {
 return new Avl()
}
// SparseRangeList.ts
import { createAvl, Avl } from './Avl'
// 區(qū)間類
class Range {
 start: number
 end: number
 constructor(start: number, end?: number) {
  this.start = start
  this.end = end || start
 }
 // 用于 Avl 中節(jié)點(diǎn)的比較
 //
 // 列表中項(xiàng)目范圍是連續(xù)的，必定不會重疊的
 // 如果傳入的 key 為重疊的，則意味著希望通過構(gòu)造一個子 Range 搜索所在的 RangeValue
 // 例如構(gòu)造一個 { start: 10, end: 10, value: 'any' }，搜索樹中
 // 范圍包含 10~10 的 RangeValue，如 { start: 0, end: 20, value: 'any' }
 compareTo(other: Range) {
  if (other.start > this.end!) return -1
  if (other.end! < this.start) return 1
  return 0
 }
}
// 區(qū)間-值 類
class RangeValue<T> extends Range {
 value: T
 constructor(start: number, end: number, value: T) {
  super(start, end)
  this.value = value
 }
 clone(): RangeValue<T> {
  return new RangeValue(this.start, this.end!, this.value)
 }
}
// 最終存儲區(qū)間-值的類，內(nèi)部使用 Avl 存儲所有 RangeValue
export default class SparseRangeList<T> {
 _size: number
 defaultValue: T
 valueTree: Avl
 constructor(size: number, defaultValue: T) {
  this._size = size
  this.defaultValue = defaultValue
  this.valueTree = createAvl()
 }
 get size() {
  return this._size
 }
 resize(newSize: number) {
  newSize = newSize | 0
  // 無調(diào)整
  if (this._size === newSize) return
  // 擴(kuò)容
  if (this._size < newSize) {
   this._size = newSize
   return
  }
  // 縮小，清空超出的部分，再縮小
  this.setRangeValue(newSize - 1, this._size - 1, this.defaultValue)
  this._size = newSize
 }
 // 返回區(qū)間包含 index 的 RangeValue 的值
 getValueAt(index: number): T {
  const result = this.valueTree.search(new Range(index))
  if (result) return result.value
  return this.defaultValue
 } 
 /**
  * 設(shè)值方法，
  * 自動與相鄰的相同值的合并成更大的 RangeValue，
  * 導(dǎo)致原本的 RangeValue 不連續(xù)，則會
  * 自動切分成兩個或者三個 RangeValue。
  *
  *     a-------------a
  * |a------------|b------------|c-----------|...
  * 
  * 結(jié)果：
  * |a-------------------|b-----|c-----------|...
  * 
  * 
  *     d-------------d
  * |a------------|b------------|c-----------|...
  * 
  * 結(jié)果：
  * |a-----|d------------|b-----|c-----------|...
  * 
  */
 setRangeValue(start: number, end: number, value: T) {
  if (!this.size) return
  if (end >= this.size) end = this.size - 1
  // 所有與當(dāng)前傳入?yún)^(qū)間范圍有重疊部分，
  // -1，+1 將接壤的毗鄰 RangeValue 也納入（如果存在的話），
  // 毗鄰的 RangeValue 要檢查否要合并。
  let prevSiblingEnd = start - 1
  let nextSiblingStart = end + 1
  let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)
  // 如果沒有重疊的部分，則作為新的 RangeValue 插入，直接結(jié)束
  // 如果有重疊的部分，就要處理合并、拆分
  if (rangeValues.length) {
   let firstRange = rangeValues[0]
   let lastRange = rangeValues[rangeValues.length - 1]
   // end 邊界比傳入的 start 小，說明是接壤毗鄰的更小的 RangeValue
   //
   // 1. 如果毗鄰的 RangeValue 的值跟當(dāng)前帶插入的值不一致，
   // 則直接將毗鄰的 RangeValue 從列表中移除，
   // 不需要做任何特殊操作，正常的插入操作即可
   //
   // 2. 否則如果毗鄰的 RangeValue 的值跟當(dāng)前待插入的值一致，
   // 則將兩個 RangeValue 的 Range 合并（修改 start即可），
   // 然后這個毗鄰的 RangeValue 也自然變成重疊的，正常執(zhí)行后續(xù)
   // 的重疊處理邏輯即可（拆分）
   if (firstRange.end < start) {
    if (firstRange.value !== value) {
     rangeValues.shift()
    }
    else {
     start = firstRange.start
    }
   }
   // 接壤毗鄰的更大的 RangeValue，處理思路
   // 跟上面處理毗鄰的更小的 RangeValue 一樣的
   if (lastRange.start > end) {
    if (lastRange.value !== value) {
     rangeValues.pop()
    }
    else {
     end = lastRange.end
    }
   }
   // 結(jié)束毗鄰 RangeValue 合并邏輯
   // 開始處理相交的 RangeValue 流程
   const length = rangeValues.length
   let index = 0
   while (index < length) {
    const currentRangeValue = rangeValues[index]
    const { value: currentValue, start: currentStart, end: currentEnd } = currentRangeValue
    // 先移除掉該重疊的 RangeValue，然后：
    this.valueTree.delete(currentRangeValue)
    // Case 1. 如果是當(dāng)前 RangeValue 完整包含在傳入的范圍內(nèi)，
    // 則不需要處理，因?yàn)檎麄€范圍都將被傳入的值覆蓋。
    if (currentStart >= start && currentEnd <= end) {
     index += 1
     continue
    }
    // Case2. 部分相交，該 RangeValue 的大的一側(cè)在傳入的范圍內(nèi)，而小的一側(cè)不在。
    // 需要做切分操作，以重疊的位置作為切分點(diǎn)，比較小的一側(cè)（不重疊的部分）重新插入，
    // 比較大的的那一部分，會被傳入的值覆蓋掉
    if (currentStart < start) {
     // 如果值不一樣，則以相交的位置作為切分點(diǎn)，非重疊部分重新插入，重疊部分用待插入的值覆蓋。
     if (currentValue !== value) {
      this._insert(currentStart, start - 1, currentValue)
     }
     else {
      start = currentStart
     }
    }
    // Case3. 部分相交，該 RangeValue 的小的一側(cè)在傳入的范圍內(nèi)，而大的一側(cè)不在。
    // 同 Case 2 做切分操作，只是反向。
    if (currentEnd > end) {
     if (currentValue !== value) {
      this._insert(end + 1, currentEnd, currentValue)
     }
     else {
      end = currentEnd
     }
    }
    index += 1
   }
  }
  this._insert(start, end, value)
 }
 setValue(index: number, value: T) {
  this.setRangeValue(index, index, value)
 }
 /**
  * 篩選出與指定區(qū)間有重疊的 RangeValue，即：
  * 
  *       1. 相互部分重疊
  * 
  * o----------o       o---------o
  *   >start------------------end<
  * 
  * 
  *      2. 相互完全重疊關(guān)系
  * 
  *      o----------------o
  *      >start--------end<
  * 
  * 
  *      3. 包含或被包含關(guān)系
  * 
  * o--------------------------------------o
  *  o-------------------------------o
  *   o-------------------------------o
  *   o-----o   o-----o   o----o
  *   >start--------------------end<
  * 
  */
 treeIntersecting(start: number, end: number): RangeValue[] {
  const startRange = new Range(start)
  const endRange = new Range(end)
  return this.valueTree.searchRange(startRange, endRange)
 }
 /**
  * 返回指定范圍內(nèi)所有 RangeValue
  * 范圍內(nèi)有無值的 Range 的話，則使用
  * 攜帶默認(rèn)值的 RangeValue 代替
  * 從而確保返回的結(jié)果是線性的、每個區(qū)間都有值的，如:
  * 
  * start>...<end 范圍內(nèi)有 A、B 兩個 RangeValue，所有空洞都用 Default 補(bǔ)足
  * +-----------|-----|-----------|-----|-----------+
  * | Default | A | Default | B | Default |
  * >start------|-----|-----------|-----|--------end<
  *
  */
 intersecting(start: number, end: number): RangeValue[] {
  const ranges = this.treeIntersecting(start, end)
  if (!ranges.length) {
   if (!this.size) return []
   return [ new RangeValue(start, end, this.defaultValue) ]
  }
  let result = []
  let range
  let index = 0
  let length = ranges.length
  while (index < length) {
   range = ranges[index].clone()
   // 傳入的 (start, end) 右側(cè)與某個 RangeValue 重疊，
   // 左側(cè)沒有命中，則左側(cè)區(qū)域手動塞入一個攜帶默認(rèn)
   // 值的 RangeValue
   if (range.start > start) {
    result.push(new RangeValue(start, range.start - 1, this.defaultValue))
   }
   result.push(range)
   // 將 start 的位置右移，
   // 以便下個 range 的比較
   start = range.end + 1
   index += 1
  }
  // 如果最后一個 range，與傳入的范圍只有左側(cè)重疊，
  // 而右側(cè)沒有重疊的地方，則手動塞入一個攜帶默認(rèn)值
  // 的 RangeValue
  if (range.end < end) {
   result.push(new RangeValue(range.end + 1, end, this.defaultValue))
  }
  else if (range.end > end) {
   // 否則如果最后一個 range 的范圍已經(jīng)超出需要的范圍，則裁剪
   range.end = end
  }
  return result
 }
 values() {
  if (!this.size) return []
  return this.intersecting(0, this.size - 1)
 }
 _insert(start: number, end: number, value: T) {
  if (value !== this.defaultValue) {
   const rangeValue = new RangeValue(start, end, value)
   this.valueTree.insert(rangeValue)
  }
 }
}
export function create<T>(size: number, value: T) {
 return new SparseRangeList(size, value)
}

import { create as createSparseRangeList } from './SparseRangeList'
// 創(chuàng)建一個默認(rèn)預(yù)估高度為 20 的列表項(xiàng)存儲對象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)
// 設(shè)置第二項(xiàng)為 40px
itemHeightStore.setValue(1, 40)
// 獲取第二項(xiàng)的高度
itemHeightStore.getValueAt(1) // 40
// 獲取列表項(xiàng)的 top 坐標(biāo)
const top = (index: number): number => {
 if (index === 0) return 0
 // 0 ～ 上一項(xiàng)的高度累加
 const rangeValues = itemHeightStore.intersecting(0, index - 1)
 const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
  const span = rangeValue.end - rangeValue.start + 1
  return sum + rangeValue.value * span
 }, 0)
 return sumHeight
}
top(1) // 20
// 計算列表總高度：
const listHeight = itemHeightStore
 .values()
 .reduce((acc: number, rangeValue: any) => {
  const span = rangeValue.end - rangeValue.start + 1
  const height = rangeValue.value * span
  return acc + height
 }, 0)

// 內(nèi)部方法，計算局部渲染數(shù)據(jù)切片的起止點(diǎn)
private _calcSliceRange() {
 if (!this.dataView.length) {
  return { sliceFrom: 0, sliceTo: 0 }
 }
 // 數(shù)據(jù)總量
 const MAX = this.dataView.length
 // 視口上邊界
 const viewportTop = (this.$refs.viewport as any).scrollTop || 0
 // 視口下邊界
 const viewportBottom = viewportTop + this.viewportHeight
 // 預(yù)估條目高度
 const estimatedItemHeight = this.defaultItemHeight
 // 從估算值開始計算起始序號
 let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
 if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
 while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
  const itemTop = this._top(sliceFrom)
  // 條目頂部相對于 viewport 頂部的偏移
  const itemOffset = itemTop - viewportTop
  // 1. 該條目距離視口頂部有距離，說明上方還有條目元素需要顯示，繼續(xù)測試上一條
  if (itemOffset > 0) {
   // 二分法快速估算下一個嘗試位置
   const diff = itemOffset / estimatedItemHeight!
   sliceFrom -= Math.ceil(diff / 2)
   continue
  }
  // 2. 恰好顯示該條目的頂部，則該條目為本次視口的首條元素
  if (itemOffset === 0) break
  // 以下都是 itemOffset < 0
  const itemHeight = this._itemHeight(sliceFrom)
  // 3. 該條目在頂部露出了一部分，則該條目為本次視口的首條元素
  if (itemOffset < itemHeight) break
  // 4. 該條目已被滾出去視口，繼續(xù)測試下一條
  // 二分法快速估算下一個嘗試位置
  const diff = -itemOffset / estimatedItemHeight!
  sliceFrom += Math.ceil(diff / 2)
 }
 // 從估算值開始計算結(jié)束序號
 let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
 if (sliceTo > MAX) sliceTo = MAX
 while (sliceTo > sliceFrom && sliceTo <= MAX) {
  const itemTop = this._top(sliceTo)
  const itemHeight = this._itemHeight(sliceTo)
  const itemBottom = itemTop + itemHeight
  // 條目底部相對于 viewport 底部的偏移
  const itemOffset = itemBottom - viewportBottom
  // 1. 該條目的底部距離視口底部有距離，說明下方還有條目元素需要顯示，繼續(xù)測試下一條
  if (itemOffset < 0) {
   // 二分法快速估算下一個嘗試位置
   const diff = -itemOffset / estimatedItemHeight!
   sliceTo += Math.ceil(diff / 2)
   continue
  }
  // 2. 恰好顯示該條目的底部，則該條目為視口中最后一項(xiàng)
  if (itemOffset === 0) break
  // 3. 該條目在底部被裁剪了一部分，則該條目為本次視口的末項(xiàng)
  if (itemOffset < itemHeight) break
  // 該條目還未出場，繼續(xù)測試上一條
  // 二分法快速估算下一個嘗試位置
  const diff = itemOffset / estimatedItemHeight!
  sliceTo -= Math.ceil(diff / 2)
 }
 // slice 的時候，不含 end，所以 + 1
 sliceTo += 1
 return { sliceFrom, sliceTo }
}

// 刷新局部渲染數(shù)據(jù)切片范圍
private _updateSliceRange(forceUpdate?: boolean) {
 // 上下方額外多渲染的條目波動量
 const COUNT = this._preRenderingCount()

 // 預(yù)渲染觸發(fā)閾值
 const THRESHOLD = this._preRenderingThreshold()  

 // 數(shù)據(jù)總量
 const MAX = this.dataView.length

 // 計算出準(zhǔn)確的切片區(qū)間
 const range = this._calcSliceRange()  

 // 檢查計算出來的切片范圍，是否被當(dāng)前已經(jīng)渲染的切片返回包含了
 // 如果是，無需更新切片，（如果 forceUpdate，則無論如何都需要重新切片）
 let fromThreshold = range.sliceFrom - THRESHOLD
 if (fromThreshold < 0) fromThreshold = 0
 let toThreshold = range.sliceTo + THRESHOLD
 if (toThreshold > MAX) toThreshold = MAX

 // 無需強(qiáng)制刷新，且上下兩端都沒有觸達(dá)閾值時，無需重新切片
 if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
  return
 }

 // 下面是更新切片的情況

 // 在切片區(qū)間頭部、尾部，追加預(yù)渲染的條目
 let { sliceFrom, sliceTo } = range
 sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
 sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT

 this.sliceFrom = sliceFrom
 this.sliceTo = sliceTo
 if (forceUpdate) this._doSlice()
}

import { Component, Vue, Prop, Watch } from 'vue-property-decorator'
import { createSparseRangeList } from './SparseRangeList'
// 列表項(xiàng)數(shù)據(jù)包裹，data 字段存放原始數(shù)據(jù)
// 組件所有操作不應(yīng)該改變 data 的內(nèi)容，而是修改該包裹對象的屬性
class ItemWrapper {
 // 原始數(shù)據(jù)
 data: any
 // 數(shù)據(jù)唯一 key
 key: any
 // 條目高度
 // 1. 正數(shù)代表已經(jīng)計算出來的高度
 // 2. 0 代表未計算的高度，不顯示
 // 3. 負(fù)數(shù)代表需要隱藏的高度，絕對值為已經(jīng)計算出來的高度，方便取消隱藏
 height: number
 // 記錄是否已經(jīng)根據(jù)實(shí)際 DOM 計算過高度
 realHeight: boolean
 // 條目在當(dāng)前過濾視圖中的序號
 viewIndex: number
 constructor(data: any, key: any, height: number) {
  this.data = data
  // 數(shù)據(jù)的唯一id，是初始化數(shù)據(jù)時候的序號
  // 每次傳入的 data 改變，都會重新生成
  this.key = key
  // 條目的高度緩存
  // 1. 用于重建高度存儲時快速恢復(fù)
  // 2. 用于快速通過數(shù)據(jù)取高度
  this.height = height >> 0
  this.realHeight = false
  // 每次生成 dataView 都刷新
  this.viewIndex = -1
 }
}
@Component({ name: 'VList' })
export default class VList extends Vue {
 [key: string]: any
 // 高度存儲 不響應(yīng)式
 private itemHeightStore: any
 // 組件寬度，不設(shè)置則為容器的 100%
 @Prop({ type: Number })
 private width?: number
 // 組件高度，不設(shè)置則為容器的 100%
 @Prop({ type: Number })
 private height?: number
 // 傳入高度值，固定條目高度
 @Prop({ type: Number })
 private fixedItemHeight?: number
 // 預(yù)估元素高度，
 // 在高度不確定的列表中，未計算出高度時使用，
 // 該值與元素平均高度越相近，則越高效（修正時估算次數(shù)越少）
 @Prop({ type: Number, default: 30 })
 private estimatedItemHeight!: number
 // 數(shù)據(jù)列表
 @Prop({ type: Array, default: () => ([]) })
 private data!: any[]
 // 計算條目高度的方法
 @Prop({
  type: Function,
  default(node: Node, wrappedData: ItemWrapper) {
   return (node as HTMLElement).clientHeight
  }
 })
 private itemHeightMethod!: (node: Node, wrappedItem: ItemWrapper) => number
 // 數(shù)據(jù)過濾方法（可以用于外部實(shí)現(xiàn)搜索框過濾）
 @Prop({ type: Function })
 private filterMethod?: (data: any) => boolean
 // 數(shù)據(jù)排序方法（可以用于外部實(shí)現(xiàn)數(shù)據(jù)自定義過濾）
 @Prop({ type: Function })
 private sortMethod?: (a: any, b: any) => number
 // 包裹后的數(shù)據(jù)列表（必須 freeze，否則大列表性能撐不?。?
 private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data))
 // 真實(shí)渲染上屏的數(shù)據(jù)列表切片
 private dataSlice: ReadonlyArray<ItemWrapper> = []
 // viewport 寬度
 private viewportWidth = this.width || 0
 // viewport 高度
 private viewportHeight = this.height || 0
 // 當(dāng)前 viewport 中第一條數(shù)據(jù)的序號
 private sliceFrom = 0
 // 當(dāng)前 viewport 中最后一條數(shù)據(jù)的序號
 private sliceTo = 0
 // 列表高度
 private listHeight = 0
 // 檢查是否固定高度模式
 private get isFixedHeight() {
  return this.fixedItemHeight! >= 0
 }
 // 獲取默認(rèn)條目高度
 private get defaultItemHeight() {
  return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight
 }
 // 當(dāng)前篩選條件下的數(shù)據(jù)列表
 // 依賴：wrappedData, filterMethod, sortMethod
 private get dataView() {
  const { wrappedData, filterMethod, sortMethod } = this
  let data = []
  if (typeof filterMethod === 'function') {
   const len = wrappedData.length
   for (let index = 0; index < len; index += 1) {
    const item = wrappedData[index]
    if (filterMethod(item.data)) {
     data.push(item)
    }
   }
  } else {
   data = wrappedData.map(i => i)
  }
  if (typeof sortMethod === 'function') {
   data.sort((a, b) => {
    return sortMethod(a, b)
   })
  }
  // 重新記錄數(shù)據(jù)在視圖中的位置，用于隱藏部分條目時，可以精確計算高度、坐標(biāo)
  const size = data.length
  for (let index = 0; index < size; index += 1) {
   const wrappedItem = data[index]
   wrappedItem.viewIndex = index
  }
  return Object.freeze(data)
 }
 // 原始列表數(shù)據(jù)變化，重新包裹數(shù)據(jù)
 @Watch('data')
 private onDataChange(data: any[]) {
  this.wrappedData = Object.freeze(this._wrapData(data))
 }
 // 當(dāng)前過濾、排序視圖變化，重新布局
 @Watch('dataView')
 private onDataViewChange(wrappedItems: ItemWrapper[]) {
  // 重建高度存儲
  const estimatedItemHeight = this.defaultItemHeight
  this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)
  // 從緩存中快速恢復(fù)已計算出高度的條目的高度
  wrappedItems.forEach((wrappedItem, index) => {
   // 小于零的需要隱藏，所以高度為 0
   this.itemHeightStore.setValue(index,
    wrappedItem.height > 0 ? wrappedItem.height : 0)
  })
  // 刷新列表高度
  this.updateListHeight()
  // 重置滾動位置
  // TODO, 錨定元素
  const { viewport } = this.$refs as any
  if (viewport) viewport.scrollTop = 0
  // 重新切片當(dāng)前 viewport 需要的數(shù)據(jù)
  this._updateSliceRange(true)
  this.$emit('data-view-change', this.dataSlice.map((wrappedItem) => wrappedItem.data))
 }
 private created() {
  const estimatedItemHeight = this.defaultItemHeight
  this.itemHeightStore = createSparseRangeList(this.dataView.length, estimatedItemHeight)
  this.layoutObserver = new MutationObserver(this.redraw.bind(this))
  this.childObserver = new MutationObserver((mutations: MutationRecord[]) => {
   this._updateHeightWhenItemInserted(mutations)
  })
  this.$watch(((vm: any) => `${vm.sliceFrom},${vm.sliceTo}`) as any, this._doSlice)
 }
 private mounted() {
  this.redraw()
  this.layoutObserver.observe(this.$el, { attributes: true })
  // 非固定高度場景，監(jiān)聽子元素插入，提取高度
  if (!this.isFixedHeight) {
   this.childObserver.observe(this.$refs.content, { childList: true })
  }
 }
 private beforeDestory() {
  this.layoutObserver.disconnect()
  if (!this.isFixedHeight) {
   this.childObserver.disconnect()
  }
  this.itemHeightStore = null
 }
 // DOM 結(jié)構(gòu)比較簡單，無需 template，直接使用渲染函數(shù)輸出 VDOM
 private render(createElement: any) {
  return createElement(
   'div', // 組件容器，與外部布局
   {
    class: 'VList',
    style: {
     'box-sizing': 'border-box',
     display: 'inline-block',
     margin: '0',
     padding: '0',
     width: this.width ? this.width + 'px' : '100%',
     height: this.height ? this.height + 'px' : '100%',
    }
   },
   [
    createElement(
     'div', // 滾動區(qū)域的可見范圍
     {
      ref: 'viewport',
      class: 'VList_viewport',
      style:
       'box-sizing:border-box;position:relative;overflow:hidden;width:100%;height:100%;margin:0;padding:0;overflow:auto;overflow-scrolling:touch;',
      on: { scroll: this._onScroll }
     },
     [
      createElement(
       'div', // 內(nèi)容容器，內(nèi)容真實(shí)高度由此容器體現(xiàn)
       {
        class: 'VList_scollable',
        ref: 'content',
        style: {
         'box-sizing': 'border-box',
         position: 'relative',
         margin: '0',
         padding: '0',
         height: this.listHeight + 'px'
        }
       },
       // 列表項(xiàng)
       this.dataSlice.map((wrappedItem) => {
        return createElement(
         'div',
         {
          key: wrappedItem.key,
          class: `VList_item VList_item-${wrappedItem.key % 2 === 0 ? 'even' : 'odd'}`,
          attrs: {
           'data-key': wrappedItem.key
          },
          style: {
           'box-sizing': 'border-box',
           'z-index': '1',
           position: 'absolute',
           right: '0',
           bottom: 'auto',
           left: '0',
           margin: '0',
           padding: '0',
           cursor: 'default',
           // 注：使用 transfrom 有黑屏 bug
           // transform: `translate(0, ${top})`
           // transform: `translate3d(0, ${top}, 0)`
           top: this._top(wrappedItem.viewIndex) + 'px'
          }
         },
         // 將原始數(shù)據(jù)，key 注入到 slot 里，
         // 以便自定義條目內(nèi)容使用
         this.$scopedSlots.default!({
          item: wrappedItem.data,
          listKey: wrappedItem.key
         })
        )
       })
      )
     ]
    )
   ]
  )
 }
 // 重繪界面，確保列表渲染正確
 public redraw() {
  const viewport = this.$refs.viewport as HTMLElement
  const { clientWidth, clientHeight } = viewport
  this.viewportWidth = clientWidth
  this.viewportHeight = clientHeight
  this.updateListHeight()
  this._updateSliceRange(true)
 }
 // 刷新列表總高度
 public updateListHeight() {
  const { itemHeightStore } = this
  const rangeValues = itemHeightStore.values()
  if (!rangeValues.length) {
   this.listHeight = 0
   return
  }
  const listHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
   const span = rangeValue.end - rangeValue.start + 1
   const height = rangeValue.value * span
   return sum + height
  }, 0)
  this.listHeight = listHeight
 }
 // Dom 插入時候，計算高度，然后
 // 批量刷新高度，避免頻繁調(diào)整列表高度帶來性能問題
 public batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number }>) {
  records.forEach(({ wrappedItem, height }) => {
   this._updateHeight(wrappedItem, height, true)
  })
  this.updateListHeight()
  this._updateSliceRange()
 }
 // 通過數(shù)據(jù) key，設(shè)置對應(yīng)條目的高度
 public updateHeightByKey(key: any, height: number) {
  const wrappedItem = this.wrappedData[key]
  if (!wrappedItem) return
  this._updateHeight(wrappedItem, height)
  this.updateListHeight()
  this._updateSliceRange()
 }
 // 通過數(shù)據(jù) key，設(shè)置對應(yīng)條目的顯示狀態(tài)
 public showByKey(key: any) {
  const wrappedItem = this.wrappedData[key]
  if (!wrappedItem) return
  if (wrappedItem.height <= 0) {
   const height = -wrappedItem.height || this.defaultItemHeight
   this._updateHeight(wrappedItem, height!)
   this.updateListHeight()
   this._updateSliceRange()
   // 強(qiáng)制重繪
   this._doSlice()
  }
 }
 // 通過數(shù)據(jù) key，設(shè)置對應(yīng)條目的顯示狀態(tài)
 public hideByKey(key: any) {
  const wrappedItem = this.wrappedData[key]
  if (!wrappedItem) return
  if (wrappedItem.height > 0) {
   const height = -wrappedItem.height
   wrappedItem.height = height
   this._updateHeight(wrappedItem, height)
   this.updateListHeight()
   // 強(qiáng)制重繪
   this._updateSliceRange(true)
  }
 }
 // 通過數(shù)據(jù) key 列表，設(shè)置對應(yīng)條目的顯示狀態(tài)
 public showByKeys(keys: any[]) {
  const wrappedItems = keys.map((key) => this.wrappedData[key])
   .filter((wrappedItem) => wrappedItem && wrappedItem.height <= 0)
  wrappedItems.forEach((wrappedItem) => {
   const height = (-wrappedItem.height || this.defaultItemHeight)!
   this._updateHeight(wrappedItem, height)
  })
  this.updateListHeight()
  // 強(qiáng)制重繪
  this._updateSliceRange(true)
 }
 // 通過數(shù)據(jù) key 列表，設(shè)置對應(yīng)條目的顯示狀態(tài)
 public hideByKeys(keys: any[]) {
  const wrappedItems = keys.map((key) => this.wrappedData[key])
   .filter(wrappedItem => wrappedItem && wrappedItem.height > 0)
  wrappedItems.forEach((wrappedItem) => {
   // 設(shè)置為負(fù)數(shù)，表示隱藏
   const height = -wrappedItem.height
   wrappedItem.height = height
   this._updateHeight(wrappedItem, height)
  })
  this.updateListHeight()
  // 強(qiáng)制重繪
  this._updateSliceRange(true)
 }
 // 內(nèi)部方法，計算局部渲染數(shù)據(jù)切片的起止點(diǎn)
 private _calcSliceRange() {
  if (!this.dataView.length) {
   return { sliceFrom: 0, sliceTo: 0 }
  }
  // 數(shù)據(jù)總量
  const MAX = this.dataView.length
  // 視口上邊界
  const viewportTop = (this.$refs.viewport as any).scrollTop || 0
  // 視口下邊界
  const viewportBottom = viewportTop + this.viewportHeight
  // 預(yù)估條目高度
  const estimatedItemHeight = this.defaultItemHeight
  // 從估算值開始計算起始序號
  let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
  if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
  while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
   const itemTop = this._top(sliceFrom)
   // 條目頂部相對于 viewport 頂部的偏移
   const itemOffset = itemTop - viewportTop
   // 1. 該條目距離視口頂部有距離，說明上方還有條目元素需要顯示，繼續(xù)測試上一條
   if (itemOffset > 0) {
    // 二分法快速估算下一個嘗試位置
    const diff = itemOffset / estimatedItemHeight!
    sliceFrom -= Math.ceil(diff / 2)
    continue
   }
   // 2. 恰好顯示該條目的頂部，則該條目為本次視口的首條元素
   if (itemOffset === 0) break
   // 以下都是 itemOffset < 0
   const itemHeight = this._itemHeight(sliceFrom)
   // 3. 該條目在頂部露出了一部分，則該條目為本次視口的首條元素
   if (itemOffset < itemHeight) break
   // 4. 該條目已被滾出去視口，繼續(xù)測試下一條
   // 二分法快速估算下一個嘗試位置
   const diff = -itemOffset / estimatedItemHeight!
   sliceFrom += Math.ceil(diff / 2)
  }
  // 從估算值開始計算結(jié)束序號
  let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
  if (sliceTo > MAX) sliceTo = MAX
  while (sliceTo > sliceFrom && sliceTo <= MAX) {
   const itemTop = this._top(sliceTo)
   const itemHeight = this._itemHeight(sliceTo)
   const itemBottom = itemTop + itemHeight
   // 條目底部相對于 viewport 底部的偏移
   const itemOffset = itemBottom - viewportBottom
   // 1. 該條目的底部距離視口底部有距離，說明下方還有條目元素需要顯示，繼續(xù)測試下一條
   if (itemOffset < 0) {
    // 二分法快速估算下一個嘗試位置
    const diff = -itemOffset / estimatedItemHeight!
    sliceTo += Math.ceil(diff / 2)
    continue
   }
   // 2. 恰好顯示該條目的底部，則該條目為視口中最后一項(xiàng)
   if (itemOffset === 0) break
   // 3. 該條目在底部被裁剪了一部分，則該條目為本次視口的末項(xiàng)
   if (itemOffset < itemHeight) break
   // 該條目還未出場，繼續(xù)測試上一條
   // 二分法快速估算下一個嘗試位置
   const diff = itemOffset / estimatedItemHeight!
   sliceTo -= Math.ceil(diff / 2)
  }
  // slice 的時候，不含 end，所以 + 1
  sliceTo += 1
  return { sliceFrom, sliceTo }
 }
 // 上下兩端預(yù)先批量渲染的項(xiàng)目波動量
 // 原理是，每次插入刪除都是一個小批量動作，
 // 而不是每次只插入一條、銷毀一條
 // 計算出的局部渲染數(shù)據(jù)范圍，跟上一次計算出來的結(jié)果，差距
 // 在這個波動量范圍內(nèi)，則不重新切片渲染，用于
 // 防止 IE 11 頻繁插入內(nèi)容導(dǎo)致性能壓力
 private _preRenderingCount() {
  // 默認(rèn)預(yù)渲染 2 屏
  return Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2
 }
 // 滾動到上下方剩下多少個條目時，加載下一批
 // 緩解 Macbook & iOS 觸摸滾動時的白屏
 private _preRenderingThreshold() {
  // 默認(rèn)觸達(dá)預(yù)渲染的一半數(shù)量時，加載下一批切片
  return Math.floor(this._preRenderingCount() / 2)
 }
 // 刷新局部渲染數(shù)據(jù)切片范圍
 private _updateSliceRange(forceUpdate?: boolean) {
  // 上下方額外多渲染的條目波動量
  const COUNT = this._preRenderingCount()
  // 預(yù)渲染觸發(fā)閾值
  const THRESHOLD = this._preRenderingThreshold()  
  // 數(shù)據(jù)總量
  const MAX = this.dataView.length
  // 計算出準(zhǔn)確的切片區(qū)間
  const range = this._calcSliceRange()  
  // 檢查計算出來的切片范圍，是否被當(dāng)前已經(jīng)渲染的切片返回包含了
  // 如果是，無需更新切片，（如果 forceUpdate，則無論如何都需要重新切片）
  let fromThreshold = range.sliceFrom - THRESHOLD
  if (fromThreshold < 0) fromThreshold = 0
  let toThreshold = range.sliceTo + THRESHOLD
  if (toThreshold > MAX) toThreshold = MAX
  // 無需強(qiáng)制刷新，且上下兩端都沒有觸達(dá)閾值時，無需重新切片
  if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
   return
  }
  // 更新切片的情況
  // 在切片區(qū)間頭部、尾部，追加預(yù)渲染的條目
  let { sliceFrom, sliceTo } = range
  sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
  sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT
  this.sliceFrom = sliceFrom
  this.sliceTo = sliceTo
  if (forceUpdate) this._doSlice()
 }
 // 當(dāng)前需要渲染的數(shù)據(jù)切片
 private _doSlice() {
  const { dataView, sliceFrom, sliceTo } = this
  const slice = dataView.slice(sliceFrom, sliceTo)
   .filter((wrappedItem) => wrappedItem.height > 0)
  this.dataSlice = Object.freeze(slice)
  this.$emit('slice', slice.map((wrappedItem) => wrappedItem.data))
 }
 // `index` 數(shù)據(jù)在 dataView 中的 index
 private _itemHeight(index: number): number {
  return this.itemHeightStore.getValueAt(index)
 }
 // `index` 數(shù)據(jù)在 dataView 中的 index
 private _top(index: number): number {
  if (index === 0) return 0
  // 0 ～ 上一項(xiàng)的高度累加
  const rangeValues = this.itemHeightStore.intersecting(0, index - 1)
  const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
   const span = rangeValue.end - rangeValue.start + 1
   return sum + rangeValue.value * span
  }, 0)
  return sumHeight
 }
 // 包裹原始數(shù)據(jù)列表
 private _wrapData(list: any[]): ItemWrapper[] {
  return list.map((item, index) => new ItemWrapper(item, index, this.defaultItemHeight!))
 }
 // 通過 DOM Node 獲取對應(yīng)的數(shù)據(jù)
 private _getDataByNode(node: Node): ItemWrapper {
  return this.wrappedData[(node as any).dataset.key]
 }
 // 刷新列表項(xiàng)高度
 private _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight?: boolean) {
  height = height >> 0
  // 更新結(jié)點(diǎn)高度緩存
  wrappedItem.height = height
  if (isRealHeight) {
   wrappedItem.realHeight = true
  }
  // 如果 wrappedItem 為當(dāng)前過濾下的項(xiàng)目，
  // 則同時刷新高度存儲 store
  const index = this.dataView.indexOf(wrappedItem)
  if (index !== -1) {
   // 小于等于零表示折疊不顯示，計算高度為零
   // 負(fù)值存在 wrappedItem 中，用于反折疊時恢復(fù)
   this.itemHeightStore.setValue(index, height > 0 ? height : 0)
  }
 }
 // 節(jié)點(diǎn)插入時，檢查是否首次插入，如果是，計算高度并更新對應(yīng)的 ItemWrapper
 private _updateHeightWhenItemInserted(mutations: MutationRecord[]) {
  const addedNodes: Node[] = mutations
   .map((mutation: MutationRecord) => mutation.addedNodes)
   .reduce((result: any, items: NodeList) => {
    result.push(...items)
    return result
   }, [])
  const batch: Array<{ wrappedItem: ItemWrapper, height: number }> = []
  addedNodes.forEach((node: Node) => {
   const wrappedItem = this._getDataByNode(node)
   // 如果 wrappedItem 中已經(jīng)存儲了計算過的高度，
   // 則直接返回，不訪問 clientHeight
   // 以避免性能開銷（IE 11 中訪問 clientHeight 性能非常差）
   if (wrappedItem.realHeight) {
    return
   }
   const height = this.itemHeightMethod(node, wrappedItem) >> 0
   if (wrappedItem.height !== height) {
    batch.push({ wrappedItem, height })
   } else {
    // 計算出來的高度跟默認(rèn)值一致，
    // 則無需更新，但是設(shè)置已經(jīng)計算狀態(tài)
    // 以便下次可以直接使用緩存
    wrappedItem.realHeight = true
   }
  })
  if (batch.length) {
   this.batchUpdateHeight(batch)
  }
 }
 // 滾動事件處理器
 private _onScroll() {
  this._updateSliceRange()
 }
}