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

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

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

// 使用该方法，可以算出列表中指定项的 top 坐标值
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.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)
}

import { create as createSparseRangeList } from './SparseRangeList'
// 创建一个默认预估高度为 20 的列表项存储对象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)
// 设置第二项为 40px
itemHeightStore.setValue(1, 40)
// 获取第二项的高度
itemHeightStore.getValueAt(1) // 40
// 获取列表项的 top 坐标
const top = (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
}
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)

// 内部方法，计算局部渲染数据切片的起止点
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._top(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._top(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 }
}