使用 Vue 实现一个虚拟列表的方法

<列表项  坐标值> = <上一项  坐标值> + <上一项的高度值>

// 假设使用该数组存储列表每一项的高度
const itemHeightStore = [20, 20, 20, 20, 20]

// 使用该方法，可以算出列表中指定项的  坐标值
const getTop = (index) => {
 let sum = 0
 while (index--) sum += itemHeightStore[index] || 0
 return sum
}
// 第一项
getTop(0) // 0

// 第二项
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
// 树结点
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
 }
 // 插入节点
 insert(key: K) {
  const node = new AvlNode<K>(key)
  const insertPoint = this._nodeInsert(node)
  // 本次插入是重复结点，直接更新 key / value
  // 无新结点插入，所以无需进行插入后的调整
  if (insertPoint == null) return
  // 新增结点成功时，回溯调整搜索路径上的结点
  this._adjustAfterInsertion(insertPoint)
 }
 // 删除节点，返回是否成功删除结点
 delete(key: K): boolean {
  // 搜索待删除结点
  const targetNode = this._nodeSearch(key)
  // 未找到 value 对应结点
  if (targetNode == null) return false
  // 执行删除结点操作
  const backtracking = this._nodeErase(targetNode)
  const parent = backtracking[0]
  // 回溯调整搜索路径上的结点
  if (parent !== null) {
   this._adjustAfterRemoval(parent)
  }
  return true
 }
 // 通过 key 查找包含该 key 范围的节点 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 节点
  let root = this._root
  while (root !== null) {
   const result1 = start.pareTo(root.key)
   const result2 = end.pareTo(root.key)
   // 当前节点比 start 小，不再搜索左子树
   if (result1 > 0) {
    root = root.right
    continue
   }
   // 当前节点大于 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)
    // 当前节点比 start 小，不再搜索 current 的左子树
    if (start.pareTo(current.key) > 0) break
    current = current.left
   }
   if (stack.length) {
    // 指向栈顶
    current = stack[stack.length - 1]
    const gteStart = start.pareTo(current.key) <= 0
    const lteEnd = end.pareTo(current.key) >= 0
    if (gteStart && lteEnd) {
     results.push(current.key)
    }
    stack.pop()
    // 只有 current 比 end 小，才继续搜索 current 的右子树
    if (lteEnd) {
     current = current.right
    }
    else {
     current = null
    }
   }
  }
  return results
 }
 // 增加结点数量
 _increaseSize() {
  this._size += 1
 }
 // 减少结点数量
 _decreaseSize() {
  this._size -= 1
 }
 // 设置左子结点，同时维护 parent 关系
 _setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
  // 断开旧 left 结点
  if (node.left !== null) {
   node.left.parent = null
  }
  // 连接新结点
  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
 }
 // 设置右子结点，同时维护 parent 关系
 _setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
  // 断开旧 right 结点
  if (node.right !== null) {
   node.right.parent = null
  }
  // 连接新结点
  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
 }
 // 获取中序遍历顺序的前驱结点
 _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
 }
 // 获取最大的结点
 _maximumNode(subRoot: AvlNode<K>) {
  let current = subRoot
  while (current.right !== null) current = current.right
  return current
 }
 // 设置根结点
 _setRoot(node: AvlNode<K> | null) {
  if (node === null) {
   this._root = null
   return
  }
  this._root = node
  // 如果本身在树中，则从树中脱落，成为独立的树根
  if (node.parent !== null) {
   node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)
   node.parent = null
  }
 }
 // 将树上某个结点替换成另一个结点
 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，有父结点的情况
   const parent = node.parent as AvlNode<K>
   if (parent.left === node) this._setLeft(parent, replacer)
   else this._setRight(parent, replacer)
  }
  return node
 }
 // 左旋，返回新顶点，注意旋转完毕会从原本的树上脱落
 private _rotateLeft(node: AvlNode<K>) {
  const parent = node.parent
  // 记录原本在树上的位置
  const isLeft = parent !== null && parent.left == node
  // 旋转
  const pivot = node.right as AvlNode<K>
  const pivotLeft = pivot.left
  this._setRight(node, pivotLeft)
  this._setLeft(pivot, node)
  // 旋转完毕
  // 新顶点接上树上原本的位置
  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
 }
 // 右旋，返回新顶点，注意旋转完毕会从原本的树上脱落
 private _rotateRight(node: AvlNode<K>) {
  const parent = node.parent
  // 记录原本在树上的位置
  const isLeft = parent !== null && parent.left === node
  // 旋转
  const pivot = node.left as AvlNode<K>
  const pivotRight = pivot.right
  this._setLeft(node, pivotRight)
  this._setRight(pivot, node)
  // 旋转完毕
  // 新顶点接上树上原本的位置
  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.pareTo(current.key)
   if (result === 0) return current
   if (result < 0) current = current.left
   else current = current.right
  }
  return null
 }
 // 在树里插入结点或者刷新重复结点
 // 返回新插入（或刷新）的结点
 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.pareTo(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
   }
  }
 }
 // 从树上移除一个结点
 private _nodeErase(node: AvlNode<K>) {
  // 同时拥有左右子树
  // 先转换成只有一颗子树的情况再统一处理
  if (node.left !== null && node.right !== null) {
   const replacer = this._inorderPredecessor(node)!
   // 使用前驱结点替换身份
   // 此时问题转换成删掉替代结点（前驱），
   // 从而简化成只有一个子结点的删除情况
   node.key = replacer.key
   // 修改 node 指针
   node = replacer
  }
  // 删除点的父结点
  const parent = node.parent
  // 待删结点少于两颗子树时，使用子树 (或 null，没子树时) 顶替移除的结点即可
  const child = node.left || node.right
  this._replaceNode(node, child)
  this._decreaseSize()
  return [ parent, child, node ]
 }
 // AVL 树插入结点后调整动作
 // 自底向上调整结点的高度
 // 遇到离 current 最近的不平衡点需要做旋转调整 
 // 注意: 对最近的不平衡点调整后 或者 结点的高度值没有变化时
 // 上层结点便不需要更新 
 // 调整次数不大于1
 _adjustAfterInsertion(backtracking: AvlNode<K> | null) {
  let current = backtracking
  // 往上回溯，查找最近的不平衡结点
  while (current !== null) {
   // 更新高度
   current.updateHeight()
   // 插入前后，回溯途径结点的高度没有变化，则无需继续回溯调整
   if (current.height === current.prevHeight) break
   // 若找到不平衡结点，执行一次调整即可
   if (this._isUnbalanced(current)) {
    this._rebalance(current)
    // 调整过，则上层无需再调整了
    break
   }
   current = current.parent
  }
 }
 // AVL树删除结点后调整动作
 // 自底向上调整结点的高度
 // 遇到离 current 最近的不平衡点需要做旋转调整
 // 注意: 对最近的不平衡点调整后，其上层结点仍然可能需要调整
 // 调整次数可能不止一次
 _adjustAfterRemoval(backtracking: AvlNode<K> | null) {
  let current = backtracking
  while (current !== null) {
   // 更新高度
   current.updateHeight()
   // 删除前后，回溯途径结点的高度没有变化，则无需继续回溯调整
   if (current.height === current.prevHeight) break
   if (this._isUnbalanced(current)) {
    this._rebalance(current)
   }
   // 与插入不同，调整过后，仍然需要继续往上回溯
   // 上层结点（若有）仍需判断是否需要调整
   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)
 }
 // 检查结点是否平衡
 _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'
// 区间类
class Range {
 start: number
 end: number
 constructor(start: number, end?: number) {
  this.start = start
  this.end = end || start
 }
 // 用于 Avl 中节点的比较
 //
 // 列表中项目范围是连续的，必定不会重叠的
 // 如果传入的 key 为重叠的，则意味着希望通过构造一个子 Range 搜索所在的 RangeValue
 // 例如构造一个 { start: 10, end: 10, value: 'any' }，搜索树中
 // 范围包含 10~10 的 RangeValue，如 { start: 0, end: 20, value: 'any' }
 pareTo(other: Range) {
  if (other.start > this.end!) return -1
  if (other.end! < this.start) return 1
  return 0
 }
}
// 区间-值 类
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)
 }
}
// 最终存储区间-值的类，内部使用 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
  // 无调整
  if (this._size === newSize) return
  // 扩容
  if (this._size < newSize) {
   this._size = newSize
   return
  }
  // 缩小，清空超出的部分，再缩小
  this.setRangeValue(newSize - 1, this._size - 1, this.defaultValue)
  this._size = newSize
 }
 // 返回区间包含 index 的 RangeValue 的值
 getValueAt(index: number): T {
  const result = this.valueTree.search(new Range(index))
  if (result) return result.value
  return this.defaultValue
 } 
 /**
  * 设值方法，
  * 自动与相邻的相同值的合并成更大的 RangeValue，
  * 导致原本的 RangeValue 不连续，则会
  * 自动切分成两个或者三个 RangeValue。
  *
  *     a-------------a
  * |a------------|b------------|c-----------|...
  * 
  * 结果：
  * |a-------------------|b-----|c-----------|...
  * 
  * 
  *     d-------------d
  * |a------------|b------------|c-----------|...
  * 
  * 结果：
  * |a-----|d------------|b-----|c-----------|...
  * 
  */
 setRangeValue(start: number, end: number, value: T) {
  if (!this.size) return
  if (end >= this.size) end = this.size - 1
  // 所有与当前传入区间范围有重叠部分，
  // -1，+1 将接壤的毗邻 RangeValue 也纳入（如果存在的话），
  // 毗邻的 RangeValue 要检查否要合并。
  let prevSiblingEnd = start - 1
  let nextSiblingStart = end + 1
  let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)
  // 如果没有重叠的部分，则作为新的 RangeValue 插入，直接结束
  // 如果有重叠的部分，就要处理合并、拆分
  if (rangeValues.length) {
   let firstRange = rangeValues[0]
   let lastRange = rangeValues[rangeValues.length - 1]
   // end 边界比传入的 start 小，说明是接壤毗邻的更小的 RangeValue
   //
   // 1. 如果毗邻的 RangeValue 的值跟当前带插入的值不一致，
   // 则直接将毗邻的 RangeValue 从列表中移除，
   // 不需要做任何特殊操作，正常的插入操作即可
   //
   // 2. 否则如果毗邻的 RangeValue 的值跟当前待插入的值一致，
   // 则将两个 RangeValue 的 Range 合并（修改 start即可），
   // 然后这个毗邻的 RangeValue 也自然变成重叠的，正常执行后续
   // 的重叠处理逻辑即可（拆分）
   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
    }
   }
   // 结束毗邻 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. 如果是当前 RangeValue 完整包含在传入的范围内，
    // 则不需要处理，因为整个范围都将被传入的值覆盖。
    if (currentStart >= start && currentEnd <= end) {
     index += 1
     continue
    }
    // Case2. 部分相交，该 RangeValue 的大的一侧在传入的范围内，而小的一侧不在。
    // 需要做切分操作，以重叠的位置作为切分点，比较小的一侧（不重叠的部分）重新插入，
    // 比较大的的那一部分，会被传入的值覆盖掉
    if (currentStart < start) {
     // 如果值不一样，则以相交的位置作为切分点，非重叠部分重新插入，重叠部分用待插入的值覆盖。
     if (currentValue !== value) {
      this._insert(currentStart, start - 1, currentValue)
     }
     else {
      start = currentStart
     }
    }
    // Case3. 部分相交，该 RangeValue 的小的一侧在传入的范围内，而大的一侧不在。
    // 同 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)
 }
 /**
  * 筛选出与指定区间有重叠的 RangeValue，即：
  * 
  *       1. 相互部分重叠
  * 
  * o----------o       o---------o
  *   >start------------------end<
  * 
  * 
  *      2. 相互完全重叠关系
  * 
  *      o----------------o
  *      >start--------end<
  * 
  * 
  *      3. 包含或被包含关系
  * 
  * 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)
 }
 /**
  * 返回指定范围内所有 RangeValue
  * 范围内有无值的 Range 的话，则使用
  * 携带默认值的 RangeValue 代替
  * 从而确保返回的结果是线性的、每个区间都有值的，如:
  * 
  * start>...<end 范围内有 A、B 两个 RangeValue，所有空洞都用 Default 补足
  * +-----------|-----|-----------|-----|-----------+
  * | 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) 右侧与某个 RangeValue 重叠，
   // 左侧没有命中，则左侧区域手动塞入一个携带默认
   // 值的 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，与传入的范围只有左侧重叠，
  // 而右侧没有重叠的地方，则手动塞入一个携带默认值
  // 的 RangeValue
  if (range.end < end) {
   result.push(new RangeValue(range.end + 1, end, this.defaultValue))
  }
  else if (range.end > end) {
   // 否则如果最后一个 range 的范围已经超出需要的范围，则裁剪
   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'
// 创建一个默认预估高度为 20 的列表项存储对象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)
// 设置第二项为 40px
itemHeightStore.setValue(1, 40)
// 获取第二项的高度
itemHeightStore.getValueAt(1) // 40
// 获取列表项的  坐标
const  = (index: number): number => {
 if (index === 0) return 0
 // 0 ～ 上一项的高度累加
 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
}
(1) // 20
// 计算列表总高度：
const listHeight = itemHeightStore
 .values()
 .reduce((a: number, rangeValue: any) => {
  const span = rangeValue.end - rangeValue.start + 1
  const height = rangeValue.value * span
  return a + height
 }, 0)

// 内部方法，计算局部渲染数据切片的起止点
private _calcSliceRange() {
 if (!this.dataView.length) {
  return { sliceFrom: 0, sliceTo: 0 }
 }
 // 数据总量
 const MAX = this.dataView.length
 // 视口上边界
 const viewportTop = (this.$refs.viewport as any).scrollTop || 0
 // 视口下边界
 const viewportBottom = viewportTop + this.viewportHeight
 // 预估条目高度
 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._(sliceFrom)
  // 条目顶部相对于 viewport 顶部的偏移
  const itemOffset = itemTop - viewportTop
  // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
  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. 该条目已被滚出去视口，继续测试下一条
  // 二分法快速估算下一个尝试位置
  const diff = -itemOffset / estimatedItemHeight!
  sliceFrom += Math.ceil(diff / 2)
 }
 // 从估算值开始计算结束序号
 let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
 if (sliceTo > MAX) sliceTo = MAX
 while (sliceTo > sliceFrom && sliceTo <= MAX) {
  const itemTop = this._(sliceTo)
  const itemHeight = this._itemHeight(sliceTo)
  const itemBottom = itemTop + itemHeight
  // 条目底部相对于 viewport 底部的偏移
  const itemOffset = itemBottom - viewportBottom
  // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
  if (itemOffset < 0) {
   // 二分法快速估算下一个尝试位置
   const diff = -itemOffset / estimatedItemHeight!
   sliceTo += Math.ceil(diff / 2)
   continue
  }
  // 2. 恰好显示该条目的底部，则该条目为视口中最后一项
  if (itemOffset === 0) break
  // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
  if (itemOffset < itemHeight) break
  // 该条目还未出场，继续测试上一条
  // 二分法快速估算下一个尝试位置
  const diff = itemOffset / estimatedItemHeight!
  sliceTo -= Math.ceil(diff / 2)
 }
 // slice 的时候，不含 end，所以 + 1
 sliceTo += 1
 return { sliceFrom, sliceTo }
}

// 刷新局部渲染数据切片范围
private _updateSliceRange(forceUpdate?: boolean) {
 // 上下方额外多渲染的条目波动量
 const COUNT = this._preRenderingCount()

 // 预渲染触发阈值
 const THRESHOLD = this._preRenderingThreshold()  

 // 数据总量
 const MAX = this.dataView.length

 // 计算出准确的切片区间
 const range = this._calcSliceRange()  

 // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
 // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
 let fromThreshold = range.sliceFrom - THRESHOLD
 if (fromThreshold < 0) fromThreshold = 0
 let toThreshold = range.sliceTo + THRESHOLD
 if (toThreshold > MAX) toThreshold = MAX

 // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
 if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
  return
 }

 // 狼蚁网站SEO优化是更新切片的情况

 // 在切片区间头部、尾部，追加预渲染的条目
 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'
// 列表项数据包裹，data 字段存放原始数据
// 组件所有操作不应该改变 data 的内容，而是修改该包裹对象的属性
class ItemWrapper {
 // 原始数据
 data: any
 // 数据唯一 key
 key: any
 // 条目高度
 // 1. 正数代表已经计算出来的高度
 // 2. 0 代表未计算的高度，不显示
 // 3. 负数代表需要隐藏的高度，绝对值为已经计算出来的高度，方便取消隐藏
 height: number
 // 记录是否已经根据实际 DOM 计算过高度
 realHeight: boolean
 // 条目在当前过滤视图中的序号
 viewIndex: number
 constructor(data: any, key: any, height: number) {
  this.data = data
  // 数据的唯一id，是初始化数据时候的序号
  // 每次传入的 data 改变，都会重新生成
  this.key = key
  // 条目的高度缓存
  // 1. 用于重建高度存储时快速恢复
  // 2. 用于快速通过数据取高度
  this.height = height >> 0
  this.realHeight = false
  // 每次生成 dataView 都刷新
  this.viewIndex = -1
 }
}
@Component({ name: 'VList' })
export default class VList extends Vue {
 [key: string]: any
 // 高度存储 不响应式
 private itemHeightStore: any
 // 组件宽度，不设置则为容器的 100%
 @Prop({ type: Number })
 private width?: number
 // 组件高度，不设置则为容器的 100%
 @Prop({ type: Number })
 private height?: number
 // 传入高度值，固定条目高度
 @Prop({ type: Number })
 private fixedItemHeight?: number
 // 预估元素高度，
 // 在高度不确定的列表中，未计算出高度时使用，
 // 该值与元素平均高度越相近，则越高效（修正时估算次数越少）
 @Prop({ type: Number, default: 30 })
 private estimatedItemHeight!: number
 // 数据列表
 @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
 // 数据过滤方法（可以用于外部实现搜索框过滤）
 @Prop({ type: Function })
 private filterMethod?: (data: any) => boolean
 // 数据排序方法（可以用于外部实现数据自定义过滤）
 @Prop({ type: Function })
 private sortMethod?: (a: any, b: any) => number
 // 包裹后的数据列表（必须 freeze，否则大列表性能撑不住）
 private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data))
 // 真实渲染上屏的数据列表切片
 private dataSlice: ReadonlyArray<ItemWrapper> = []
 // viewport 宽度
 private viewportWidth = this.width || 0
 // viewport 高度
 private viewportHeight = this.height || 0
 // 当前 viewport 中第一条数据的序号
 private sliceFrom = 0
 // 当前 viewport 中最后一条数据的序号
 private sliceTo = 0
 // 列表高度
 private listHeight = 0
 // 检查是否固定高度模式
 private get isFixedHeight() {
  return this.fixedItemHeight! >= 0
 }
 // 获取默认条目高度
 private get defaultItemHeight() {
  return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight
 }
 // 当前筛选条件下的数据列表
 // 依赖：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)
   })
  }
  // 重新记录数据在视图中的位置，用于隐藏部分条目时，可以精确计算高度、坐标
  const size = data.length
  for (let index = 0; index < size; index += 1) {
   const wrappedItem = data[index]
   wrappedItem.viewIndex = index
  }
  return Object.freeze(data)
 }
 // 原始列表数据变化，重新包裹数据
 @Watch('data')
 private onDataChange(data: any[]) {
  this.wrappedData = Object.freeze(this._wrapData(data))
 }
 // 当前过滤、排序视图变化，重新布局
 @Watch('dataView')
 private onDataViewChange(wrappedItems: ItemWrapper[]) {
  // 重建高度存储
  const estimatedItemHeight = this.defaultItemHeight
  this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)
  // 从缓存中快速恢复已计算出高度的条目的高度
  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
  // 重新切片当前 viewport 需要的数据
  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 })
  // 非固定高度场景，监听子元素插入，提取高度
  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 结构比较简单，无需 template，直接使用渲染函数输出 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', // 滚动区域的可见范围
     {
      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', // 内容容器，内容真实高度由此容器体现
       {
        class: 'VList_scollable',
        ref: 'content',
        style: {
         'box-sizing': 'border-box',
         position: 'relative',
         margin: '0',
         padding: '0',
         height: this.listHeight + 'px'
        }
       },
       // 列表项
       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, ${})`
           // transform: `translate3d(0, ${}, 0)`
           : this._(wrappedItem.viewIndex) + 'px'
          }
         },
         // 将原始数据，key 注入到 slot 里，
         // 以便自定义条目内容使用
         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 插入时候，计算高度，然后
 // 批量刷新高度，避免频繁调整列表高度带来性能问题
 public batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number }>) {
  records.forEach(({ wrappedItem, height }) => {
   this._updateHeight(wrappedItem, height, true)
  })
  this.updateListHeight()
  this._updateSliceRange()
 }
 // 通过数据 key，设置对应条目的高度
 public updateHeightByKey(key: any, height: number) {
  const wrappedItem = this.wrappedData[key]
  if (!wrappedItem) return
  this._updateHeight(wrappedItem, height)
  this.updateListHeight()
  this._updateSliceRange()
 }
 // 通过数据 key，设置对应条目的显示状态
 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()
   // 强制重绘
   this._doSlice()
  }
 }
 // 通过数据 key，设置对应条目的显示状态
 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()
   // 强制重绘
   this._updateSliceRange(true)
  }
 }
 // 通过数据 key 列表，设置对应条目的显示状态
 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()
  // 强制重绘
  this._updateSliceRange(true)
 }
 // 通过数据 key 列表，设置对应条目的显示状态
 public hideByKeys(keys: any[]) {
  const wrappedItems = keys.map((key) => this.wrappedData[key])
   .filter(wrappedItem => wrappedItem && wrappedItem.height > 0)
  wrappedItems.forEach((wrappedItem) => {
   // 设置为负数，表示隐藏
   const height = -wrappedItem.height
   wrappedItem.height = height
   this._updateHeight(wrappedItem, height)
  })
  this.updateListHeight()
  // 强制重绘
  this._updateSliceRange(true)
 }
 // 内部方法，计算局部渲染数据切片的起止点
 private _calcSliceRange() {
  if (!this.dataView.length) {
   return { sliceFrom: 0, sliceTo: 0 }
  }
  // 数据总量
  const MAX = this.dataView.length
  // 视口上边界
  const viewportTop = (this.$refs.viewport as any).scrollTop || 0
  // 视口下边界
  const viewportBottom = viewportTop + this.viewportHeight
  // 预估条目高度
  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._(sliceFrom)
   // 条目顶部相对于 viewport 顶部的偏移
   const itemOffset = itemTop - viewportTop
   // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
   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. 该条目已被滚出去视口，继续测试下一条
   // 二分法快速估算下一个尝试位置
   const diff = -itemOffset / estimatedItemHeight!
   sliceFrom += Math.ceil(diff / 2)
  }
  // 从估算值开始计算结束序号
  let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
  if (sliceTo > MAX) sliceTo = MAX
  while (sliceTo > sliceFrom && sliceTo <= MAX) {
   const itemTop = this._(sliceTo)
   const itemHeight = this._itemHeight(sliceTo)
   const itemBottom = itemTop + itemHeight
   // 条目底部相对于 viewport 底部的偏移
   const itemOffset = itemBottom - viewportBottom
   // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
   if (itemOffset < 0) {
    // 二分法快速估算下一个尝试位置
    const diff = -itemOffset / estimatedItemHeight!
    sliceTo += Math.ceil(diff / 2)
    continue
   }
   // 2. 恰好显示该条目的底部，则该条目为视口中最后一项
   if (itemOffset === 0) break
   // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
   if (itemOffset < itemHeight) break
   // 该条目还未出场，继续测试上一条
   // 二分法快速估算下一个尝试位置
   const diff = itemOffset / estimatedItemHeight!
   sliceTo -= Math.ceil(diff / 2)
  }
  // slice 的时候，不含 end，所以 + 1
  sliceTo += 1
  return { sliceFrom, sliceTo }
 }
 // 上下两端预先批量渲染的项目波动量
 // 原理是，每次插入删除都是一个小批量动作，
 // 而不是每次只插入一条、销毁一条
 // 计算出的局部渲染数据范围，跟上一次计算出来的结果，差距
 // 在这个波动量范围内，则不重新切片渲染，用于
 // 防止 IE 11 频繁插入内容导致性能压力
 private _preRenderingCount() {
  // 默认预渲染 2 屏
  return Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2
 }
 // 滚动到上下方剩下多少个条目时，加载下一批
 // 缓解 Macbook & iOS 触摸滚动时的白屏
 private _preRenderingThreshold() {
  // 默认触达预渲染的一半数量时，加载下一批切片
  return Math.floor(this._preRenderingCount() / 2)
 }
 // 刷新局部渲染数据切片范围
 private _updateSliceRange(forceUpdate?: boolean) {
  // 上下方额外多渲染的条目波动量
  const COUNT = this._preRenderingCount()
  // 预渲染触发阈值
  const THRESHOLD = this._preRenderingThreshold()  
  // 数据总量
  const MAX = this.dataView.length
  // 计算出准确的切片区间
  const range = this._calcSliceRange()  
  // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
  // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
  let fromThreshold = range.sliceFrom - THRESHOLD
  if (fromThreshold < 0) fromThreshold = 0
  let toThreshold = range.sliceTo + THRESHOLD
  if (toThreshold > MAX) toThreshold = MAX
  // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
  if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
   return
  }
  // 更新切片的情况
  // 在切片区间头部、尾部，追加预渲染的条目
  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()
 }
 // 当前需要渲染的数据切片
 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` 数据在 dataView 中的 index
 private _itemHeight(index: number): number {
  return this.itemHeightStore.getValueAt(index)
 }
 // `index` 数据在 dataView 中的 index
 private _(index: number): number {
  if (index === 0) return 0
  // 0 ～ 上一项的高度累加
  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
 }
 // 包裹原始数据列表
 private _wrapData(list: any[]): ItemWrapper[] {
  return list.map((item, index) => new ItemWrapper(item, index, this.defaultItemHeight!))
 }
 // 通过 DOM Node 获取对应的数据
 private _getDataByNode(node: Node): ItemWrapper {
  return this.wrappedData[(node as any).dataset.key]
 }
 // 刷新列表项高度
 private _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight?: boolean) {
  height = height >> 0
  // 更新结点高度缓存
  wrappedItem.height = height
  if (isRealHeight) {
   wrappedItem.realHeight = true
  }
  // 如果 wrappedItem 为当前过滤下的项目，
  // 则同时刷新高度存储 store
  const index = this.dataView.indexOf(wrappedItem)
  if (index !== -1) {
   // 小于等于零表示折叠不显示，计算高度为零
   // 负值存在 wrappedItem 中，用于反折叠时恢复
   this.itemHeightStore.setValue(index, height > 0 ? height : 0)
  }
 }
 // 节点插入时，检查是否首次插入，如果是，计算高度并更新对应的 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 中已经存储了计算过的高度，
   // 则直接返回，不访问 clientHeight
   // 以避免性能开销（IE 11 中访问 clientHeight 性能非常差）
   if (wrappedItem.realHeight) {
    return
   }
   const height = this.itemHeightMethod(node, wrappedItem) >> 0
   if (wrappedItem.height !== height) {
    batch.push({ wrappedItem, height })
   } else {
    // 计算出来的高度跟默认值一致，
    // 则无需更新，但是设置已经计算状态
    // 以便下次可以直接使用缓存
    wrappedItem.realHeight = true
   }
  })
  if (batch.length) {
   this.batchUpdateHeight(batch)
  }
 }
 // 滚动事件处理器
 private _onScroll() {
  this._updateSliceRange()
 }
}