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

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.compareTo(root.key)
   const result2 = end.compareTo(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.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 小，才继续搜索 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.compareTo(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.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
   }
  }
 }
 // 从树上移除一个结点
 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' }
 compareTo(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)
}