Implement a virtual list using Vue

Big list problem

Large lists present performance problems that are difficult to overcome because of DOM performance bottlenecks. Hence the optimization of “local rendering”, which is the core idea of virtual lists.

The realization of virtual list needs to focus on the following points:

The calculation method of visual area
DOM update scheme for visual area
Event handling scheme

The following is a breakdown.

Visual area calculation

The calculation of visual area is to use the height of the current viewport and the distance of the current scroll bar to get the coordinate interval of a visual area. After calculating the coordinate interval of the visible area, the coordinate of the list item must be able to be calculated in the process of filtering out the list item that falls within this area.

Think about the following situation,

Our viewport height is 100px
We have so far scrolled 100px
Each of our list items is 20px high

Based on these conditions, we can calculate that the current visible area is item 11 to 20.

01-05, Viewing area above + - + -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- - | 06 | | + 100 ~ 120 - + -- -- -- -- -- -- -- -- -- -- -- + | 07 | | + 120 ~ 140 - + -- -- -- -- -- -- -- -- -- -- -- + | | 08, 140 ~ 160 | viewing area + - + -- -- -- -- -- -- -- -- -- -- -- + | 09 | | + 160 ~ 180 - + -- -- -- -- -- -- -- -- -- -- - + 10 | | | + 180 ~ 200 - + -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- 11 -n, below the viewable areaCopy the code

This is because the height of the list items is fixed, and we can use a simple four-way operation to figure out that out of the 100px that has been scrolled, five list items have been scrolled, so the viewport is 100px high and can hold 100/20, or five items.

The situation in the example above is so simple and does not have a performance problem that it is not really worth discussing. There is another, much more complicated case, where the list item height is not fixed, depending on the content.

At this point, we can’t directly use the four operations to figure out the items corresponding to the visible area in one step.

Instead, you have to implement a mechanism to record the coordinates of all list items and then check that list items fall within the viewport.

The following focuses on this issue.

Coordinates of list items

The coordinates of list items can be defined by the following formula:

< top coordinate of list item > = < top coordinate of previous item > + < height of previous item >Copy the code

The top coordinate value of the first list item is 0, so as long as the height of all list items is recorded, the top coordinate value of any list item can be calculated. The problem then becomes that some way must be found to store the height of each entry.

The easiest solution, I think, is to use an array that stores the height of each item in the list. Then when the coordinate value of a specific item is obtained, the value of the first item to the target item is extracted and the sum operation is carried out. See the following code to understand:

// Suppose we use this array to store the height of each item in the list
const itemHeightStore = [20.20.20.20.20]

// Use this method to calculate the top coordinate of the specified item in the list
const getTop = (index) = > {
  let sum = 0
  while (index--) sum += itemHeightStore[index] || 0
  return sum
}

/ / the first item
getTop(0) / / 0

/ / the second
getTop(1) / / 20
// ...
Copy the code

The implementation works fine.

However, this algorithm has a serious performance problem. Every coordinate of a list item needs to be traversed, and the complexity is O(n), which is very uneconomical.

What if we could just store the coordinates of each of these terms?

The essence is the same. Because the height of our list items is not fixed, when we quickly drag the scrollbar to different areas, we need to calculate the height according to the local rendering results to update the array record, and when updating an item, all the subsequent items of that item also need to be updated, with the same complexity of O(n).

Therefore, using arrays to maintain the height or coordinates of each item can consume a lot of CPU time when the list size is large.

Maybe TypedArray would be better?

Looking closely at the array in the above example, combined with the list in real life, we can observe one phenomenon:

List items tend to be similar and, in many cases, probably the same height.

Based on this experience, we can use ranges to store the heights of list items.

Reduce list traversal by collapsing adjacent list items of the same height.

For example:

const range = {
  start: 0.end: 4.value: 20
}
Copy the code

The height of items 1 through 5 in the list is 20px.

If we want to find the height of the sixth term, we can just do a simple four operations, instead of going through and adding up the five terms.

It is easy to conclude that if most of the list is the same height and only a few items are not the same height (such as text wrapping), you will have very good performance.

And the use of intervals, of course, is not free. This brings complexity to the data structure.

Collapsing adjacent nodes of the same height will result in a stored list that does not correspond to the original entry. Therefore, it is not easy to know where the height of the list item we want to query is stored, so we need to design a special storage mechanism.

This storage mechanism needs to have these features:

Efficient queries. You can quickly obtain the corresponding range and all ranges before the range through the serial number of the list item.
Modify efficiently. You can efficiently insert and remove ranges, merge ranges, and split ranges.

With the data structure knowledge we have learned, we can consider using some kind of BST for storage, so as to obtain good query and insert performance. Range merge, split, etc., can achieve a special class to manage.

Update: Using Binary Indexed Tree performs very well in testing. But this is mainly to explain the idea, the code will not be updated.

Segment Tree is also a solution of a similar nature and may also be tried.

Here is a simple code implementation for reference, the code has been added to a large number of comments, direct reading should be clearer than the explanation.

// Avl.ts
const SLIGHTLY_UNBALANCED_RIGHT = - 1
const SLIGHTLY_UNBALANCED_LEFT = 1
const UNBALANCED_RIGHT = 2 -
const UNBALANCED_LEFT = 2

/ / tree node
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
  }

  // The height before the refresh is convenient for balancing operation
  get prevHeight() {
    return this._prevHeight | 0
  }

  get height() {
    return this._height | 0
  }

  set height(value) {
    this._prevHeight = this._height | 0
    this._height = value | 0
  }

  // Left subtree height
  get leftHeight() {
    if (this.left === null) return - 1
    return this.left.height | 0
  }

  // Right subtree height
  get rightHeight() {
    if (this.right === null) return - 1
    return this.right.height | 0
  }

  // Balancing factor
  get balanceFactor() {
    return this.leftHeight - this.rightHeight
  }

  updateHeight() {
    const { leftHeight, rightHeight } = this
    const height = ((leftHeight > rightHeight ? leftHeight : rightHeight) + 1) | 0
    this.height = height
  }
}

/ / AVL tree
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 the node
  insert(key: K) {
    const node = new AvlNode<K>(key)
    const insertPoint = this._nodeInsert(node)

    // Update key/value directly
    // No new nodes are inserted, so there is no need to adjust after insertion
    if (insertPoint == null) return

    // When the new node is successfully added, the search path is backtracked
    this._adjustAfterInsertion(insertPoint)
  }

  // Delete the node and check whether the node is successfully deleted
  delete(key: K): boolean {
    // Search for the node to be deleted
    const targetNode = this._nodeSearch(key)
    // No value is found
    if (targetNode == null) return false

    // Delete the node
    const backtracking = this._nodeErase(targetNode)
    const parent = backtracking[0]

    // Backtrack to adjust the nodes on the search path
    if(parent ! = =null) {
      this._adjustAfterRemoval(parent)
    }

    return true
  }

  // Find the node key containing the key range by key
  search(key: K) {
    const node = this._nodeSearch(key)
    if(node ! = =null) return node.key
    return null
  }

  // Search the list of all keys between start and end
  searchRange(start: K, end: K) {
    const results: K[] = []

    // Find the root node that matches the condition
    let root = this._root
    while(root ! = =null) {
      const result1 = start.compareTo(root.key)
      const result2 = end.compareTo(root.key)
      // The current node is smaller than start, and the left subtree is no longer searched
      if (result1 > 0) {
        root = root.right
        continue
      }
      // The current node is greater than end, no search for the right subtree
      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)
        // The current node is smaller than start, no longer searches the left subtree of current
        if (start.compareTo(current.key) > 0) break
        current = current.left
      }
      if (stack.length) {
        // point to the top of the stack
        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()

        // Search the right subtree of current only if current is smaller than end
        if (lteEnd) {
          current = current.right
        }
        else {
          current = null}}}return results
  }

  // Increase the number of nodes
  _increaseSize() {
    this._size += 1
  }

  // Reduce the number of nodes
  _decreaseSize() {
    this._size -= 1
  }

  // Set the left child while maintaining the parent relationship
  _setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
    Disconnect the old left node
    if(node.left ! = =null) {
      node.left.parent = null
    }
    // join the new node
    if(child ! = =null) {
      // Disconnect from the old parent
      if(child.parent ! = =null) {
        child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
      }
      child.parent = node
    }
    node.left = child
  }

  // Set the right child while maintaining the parent relationship
  _setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
    // Disconnect the old right node
    if(node.right ! = =null) {
      node.right.parent = null
    }
    // join the new node
    if(child ! = =null) {
      // Disconnect from the old parent
      if(child.parent ! = =null) {
        child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
      }
      child.parent = node
    }
    node.right = child
  }

  // Get the precursor of the sequence traversal order
  _inorderPredecessor(node: AvlNode<K> | null) {
    if (node == null) return null

    1. Find the maximum element of the left subtree
    if(node.left ! = =null) {
      return this._maximumNode(node.left)
    }

    // 2. No left subtree, search up
    let parent = node.parent
    while(parent ! =null) {
      if (node == parent.right) {
        return parent
      }
      node = parent
      parent = node.parent
    }

    // 4. Search to the root
    return null
  }

  // Get the largest node
  _maximumNode(subRoot: AvlNode<K>) {
    let current = subRoot
    while(current.right ! = =null) current = current.right
    return current
  }

  // Set the root
  _setRoot(node: AvlNode<K> | null) {
    if (node === null) {
      this._root = null
      return
    }
    this._root = node
    // If it is in a tree, it falls off the tree and becomes an independent root
    if(node.parent ! = =null) {
      node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)
      node.parent = null}}// Replace one node in the tree with another
  private _replaceNode(node: AvlNode<K>, replacer: AvlNode<K> | null) {
    if (node === replacer) return node

    // Node is root
    if (node === this._root) {
      this._setRoot(replacer)
    }
    else {
      // Non-root, with parent
      const parent = node.parent as AvlNode<K>
      if (parent.left === node) this._setLeft(parent, replacer)
      else this._setRight(parent, replacer)
    }

    return node
  }

  // Turn left to return to the new vertex, note that the rotation will fall off the original tree
  private _rotateLeft(node: AvlNode<K>) {
    const parent = node.parent
    // Record the original position in the tree
    constisLeft = parent ! = =null && parent.left == node

    / / rotation
    const pivot = node.right as AvlNode<K>
    const pivotLeft = pivot.left
    this._setRight(node, pivotLeft)
    this._setLeft(pivot, node)
    // The rotation is complete

    // The new vertex is attached to the original position on the tree
    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
  }

  // Turn right to return to the new vertex, note that the rotation will fall off the original tree
  private _rotateRight(node: AvlNode<K>) {
    const parent = node.parent
    // Record the original position in the tree
    constisLeft = parent ! = =null && parent.left === node

    / / rotation
    const pivot = node.left as AvlNode<K>
    const pivotRight = pivot.right
    this._setLeft(node, pivotRight)
    this._setRight(pivot, node)
    // The rotation is complete

    // The new vertex is attached to the original position on the tree
    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
  }

  / / search 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
  }


  // Insert nodes or refresh duplicate nodes in the tree
  // Returns the newly inserted (or refreshed) node
  private _nodeInsert(node: AvlNode<K>) {
    / / empty tree
    if (this._root === null) {
      this._setRoot(node)
      this._increaseSize()
      return null
    }

    const key = node.key
    let current = this._root

    // Find the position to insert
    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}}}// Remove a node from the tree
  private _nodeErase(node: AvlNode<K>) {
    // Have both left and right subtrees
    // Create a subtree with only one subtree
    if(node.left ! = =null&& node.right ! = =null) {
      const replacer = this._inorderPredecessor(node)!

      // Replace the identity with a precursor node
      // Then the problem is to delete the replacement node (precursor),
      // This simplifies to a deletion case with only one child
      node.key = replacer.key

      // Modify the node pointer
      node = replacer
    }

    // Delete the parent of the point
    const parent = node.parent

    // If there are less than two subtrees in the node to be deleted, use subtrees (or null, if there are no subtrees) to replace the removed node
    const child = node.left || node.right
    this._replaceNode(node, child)
    this._decreaseSize()

    return [ parent, child, node ]
  }

  // The AVL tree is inserted into the node
  // Adjust the height of the node from bottom up
  // Rotation adjustment is required when the current is nearest to the imbalance
  // Note: after adjusting the latest unbalance or the height of the node has not changed
  // The supernode does not need to be updated
  // The number of adjustments is not greater than 1
  _adjustAfterInsertion(backtracking: AvlNode<K> | null) {
    let current = backtracking
    // Back up to find the nearest unbalanced node
    while(current ! = =null) {
      // Update the height
      current.updateHeight()

      // Before and after insertion, the height of the backtracking path node does not change, so there is no need to continue the backtracking adjustment
      if (current.height === current.prevHeight) break

      // If an unbalanced node is found, perform an adjustment
      if (this._isUnbalanced(current)) {
        this._rebalance(current)
        // If yes, there is no need to adjust the upper layer
        break
      }

      current = current.parent
    }
  }

  // AVL tree to delete the node after adjusting the action
  // Adjust the height of the node from bottom up
  // Rotation adjustment is required when the current is nearest to the imbalance
  // Note: after adjusting the most recent unbalance, its upper node may still need adjusting
  // There may be more than one adjustment
  _adjustAfterRemoval(backtracking: AvlNode<K> | null) {
    let current = backtracking
    while(current ! = =null) {
      // Update the height
      current.updateHeight()
      // The height of the nodes in the backtracking path does not change before and after deletion, so there is no need to continue the backtracking adjustment
      if (current.height === current.prevHeight) break

      if (this._isUnbalanced(current)) {
        this._rebalance(current)
      }

      // Unlike insertion, after adjustment, you still need to go back and forth
      // The supernode (if any) still needs to be adjusted
      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)
  }

  // Check whether the nodes are balanced
  _isUnbalanced(node: AvlNode<K>) {
    const factor = node.balanceFactor
    return factor === UNBALANCED_RIGHT || factor === UNBALANCED_LEFT
  }

  // Rebalance
  _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 >= rightHeight
        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()
}
Copy the code

// SparseRangeList.ts

import { createAvl, Avl } from './Avl'

/ / class
class Range {
  start: number
  end: number

  constructor(start: number, end? :number) {
    this.start = start
    this.end = end || start
  }

  // For comparison of Avl nodes
  //
  // The items in the list are contiguous and must not overlap
  // If the key passed is overlapped, it means that you want to search for the RangeValue by constructing a subrange
  {start: 10, end: 10, value: 'any'}
  // Ranges from 10 to 10, such as {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}}// Interval-value class
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)
  }
}

// The class that finally stores RangeValue values, internally uses Avl to store all RangeValue values
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

    / / no adjustment
    if (this._size === newSize) return

    / / capacity
    if (this._size < newSize) {
      this._size = newSize
      return
    }

    // Zoom out, clear out the excess, zoom out again
    this.setRangeValue(newSize - 1.this._size - 1.this.defaultValue)
    this._size = newSize
  }

  // Return the value of RangeValue containing index
  getValueAt(index: number): T {
    const result = this.valueTree.search(new Range(index))
    if (result) return result.value
    return this.defaultValue
  }  

  /** * Set the value method, * automatically merges adjacent values of the same value into a larger RangeValue, * causes the original RangeValue to be discontinuous, * automatically splits into two or three RangeValue. * * a-------------a * |a------------|b------------|c-----------|... Results: * * * | a -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | b c -- -- -- -- -- -- -- -- -- -- - |... * * * d-------------d * |a------------|b------------|c-----------|... Results: * * * | a -- -- -- -- - | d -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | b c -- -- -- -- -- -- -- -- -- -- - |... * * /
  setRangeValue(start: number, end: number, value: T) {
    if (!this.size) return
    if (end >= this.size) end = this.size - 1

    // All overlaps with the current incoming range,
    // -1, +1 will include adjacent RangeValue (if present),
    // The adjacent RangeValue checks to see if it wants to merge.
    let prevSiblingEnd = start - 1
    let nextSiblingStart = end + 1
    let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)

    // If there is no overlap, it is inserted as a new RangeValue, ending directly
    // If there are overlaps, merge and split
    if (rangeValues.length) {
      let firstRange = rangeValues[0]
      let lastRange = rangeValues[rangeValues.length - 1]

      // The end boundary is smaller than the start passed in, indicating that the border is adjacent to the smaller RangeValue
      //
      // 1. If the value of the adjacent RangeValue is inconsistent with the value of the current band insert,
      // Immediately remove the adjacent RangeValue from the list,
      // There is no need to do any special operations, just normal insert operations
      //
      // 2. Otherwise, if the value of the adjacent RangeValue is the same as the value to be inserted,
      // Merge two RangeValue ranges (start)
      // Then the adjacent RangeValue also naturally becomes overlapped, normal execution follows
      // Can be overlapped processing logic.
      if (firstRange.end < start) {
        if(firstRange.value ! == value) { rangeValues.shift() }else {
          start = firstRange.start
        }
      }

      // Border adjacent to the larger RangeValue, processing ideas
      // Same as above for adjacent smaller RangeValue
      if (lastRange.start > end) {
        if(lastRange.value ! == value) { rangeValues.pop() }else {
          end = lastRange.end
        }
      }

      // End the contiguous RangeValue merge logic
      // Start processing the intersecting RangeValue process
      const length = rangeValues.length
      let index = 0
      while (index < length) {
        const currentRangeValue = rangeValues[index]
        const { value: currentValue, start: currentStart, end: currentEnd } = currentRangeValue

        // Remove the overlapping RangeValue, then:
        this.valueTree.delete(currentRangeValue)

        // Case 1. If the current RangeValue is fully contained within the range passed in,
        // No processing is required because the entire range will be covered by the value passed in.
        if (currentStart >= start && currentEnd <= end) {
          index += 1
          continue
        }

        The larger side of the RangeValue is in the incoming range, but the smaller side is not.
        // The smaller side (the non-overlapping part) should be inserted again.
        // The larger part will be overwritten by the value passed in
        if (currentStart < start) {
          // If the values are not the same, the intersection position is used as the point of segmentation, and the non-overlapping part is re-inserted, and the overlapping part is overwritten by the values to be inserted.
          if(currentValue ! == value) {this._insert(currentStart, start - 1, currentValue)
          }
          else {
            start = currentStart
          }
        }

        // Case3. Partially intersects, the smaller side of the RangeValue is in the range passed in, but the larger side is not.
        // Do the same shard as Case 2, but in reverse.
        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)
  }

  /** * Select a RangeValue that overlaps with the specified range, i.e. ** 1. Overlap each other * * o -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - o o - o * > start -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- end < * * * 2. Completely overlap each other relations * * o -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - o * > start -- -- -- -- -- -- -- -- end < * * * 3. Included or included relationship * * 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)
  }

  /** * return all RangeValue * values within the specified Range, then use RangeValue with default values instead of * to ensure that the result returned is linear, each Range has a value, for example: ** start>... < span style = "box-sizing: border-box; color: RGB (74, 74, 74); All empty by Default complement * + -- -- -- -- -- -- -- -- -- -- - | -- - | -- -- -- -- -- -- -- -- -- -- - | -- - | -- -- -- -- -- -- -- -- -- -- - + * | 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()
      // The right side of the passed (start, end) is overlapped with a RangeValue,
      // If the left side does not hit, a carry default is manually inserted into the left side area
      / / value RangeValue
      if (range.start > start) {
        result.push(new RangeValue(start, range.start - 1.this.defaultValue))
      }

      result.push(range)

      // Move the start position to the right,
      // for the next range comparison
      start = range.end + 1
      index += 1
    }

    // If the last range overlaps only the left of the incoming range,
    // If there is no overlap on the right, manually insert a carrying default value
    / / RangeValue
    if (range.end < end) {
      result.push(new RangeValue(range.end + 1, end, this.defaultValue))
    }
    else if (range.end > end) {
      Otherwise, if the last range exceeds the desired range, crop
      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)
}
Copy the code

With this storage mechanism in place, we can more efficiently manage the height of list items and count list heights.

Read the code to understand:

import { create as createSparseRangeList } from './SparseRangeList'

// Create a list store object with a default estimated height of 20
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)

// Set the second item to 40px
itemHeightStore.setValue(1.40)

// Get the height of the second item
itemHeightStore.getValueAt(1) / / 40

// Get the top coordinate of the list item
const top = (index: number) :number= > {
  if (index === 0) return 0
  // 0 ~ the sum of the height of the previous term
  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

// Calculate the total height of the list:
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)

Copy the code

Calculate visual entries

Having managed the height of the list items, the next thing you need to do is figure out which items are visible.

The simplest way to do this is to simply walk through our node height store list, comparing it one by one with the viewport’s coordinate range, and filtering out items that fall (or partially fall) inside the viewport. For performance reasons, we can’t be so blunt. We can do the following to improve performance:

First, the entry of the estimated starting point + dichotomy correction.

Figure out the first entry that is likely to appear in the viewport based on the estimated or default height of the entry. For example, if our viewport’s upper coordinate (the distance the scroll bar has traveled) is 100px and our entry’s estimated height is 20px, then we can guess that the first entry to appear in the viewport will be 100/20 + 1, i.e. item 6. We directly calculate the coordinates of article 6, check whether it falls in the viewport, and then make dichotomy guesses according to the gap of results until we find the true starting point entry.

2. Estimated end point entries + dichotomy correction

After calculating the starting entry, divide the viewport height by the estimated entry height to figure out how many items might be displayed inside the viewport. Add the starting number to this number to obtain the estimated end entry number. Use the same correction logic as above until the correct viewport end entry is found.

The description can be difficult to follow, but here are the key snippets:

// Internal method to calculate the start and stop points of local render data slices
private _calcSliceRange() {
  if (!this.dataView.length) {
    return { sliceFrom: 0, sliceTo: 0}}// Total amount of data
  const MAX = this.dataView.length

  // Upper boundary of viewport
  const viewportTop = (this.$refs.viewport as any).scrollTop || 0
  // Lower edge of viewport
  const viewportBottom = viewportTop + this.viewportHeight
  // Estimate item height
  const estimatedItemHeight = this.defaultItemHeight

  // Calculate the starting sequence from the estimated value
  let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
  if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
  while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
    const itemTop = this._top(sliceFrom)

    // The offset from the top of the entry to the top of the viewport
    const itemOffset = itemTop - viewportTop

    // 1. There is a distance between this entry and the top of the viewport
    if (itemOffset > 0) {
      // The dichotomy method quickly estimates the next try location
      const diff = itemOffset / estimatedItemHeight!
      sliceFrom -= Math.ceil(diff / 2)
      continue
    }

    // 2. If the top of the entry is displayed, the entry is the first element of the viewport
    if (itemOffset === 0) break

    ItemOffset < 0

    const itemHeight = this._itemHeight(sliceFrom)

    // 3. If part of this entry is exposed at the top, it is the first element of this viewport
    if (itemOffset < itemHeight) break

    // 4. The entry has been rolled out of the viewport, continue to test the next entry
    // The dichotomy method quickly estimates the next try location
    const diff = -itemOffset / estimatedItemHeight!
    sliceFrom += Math.ceil(diff / 2)}// Calculate the end sequence from the estimated value
  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

    // The offset at the bottom of the entry relative to the bottom of the viewport
    const itemOffset = itemBottom - viewportBottom

    // 1. There is a distance between the bottom of this item and the bottom of the viewport, indicating that there are items below the item to display, continue to test the next item
    if (itemOffset < 0) {
      // The dichotomy method quickly estimates the next try location
      const diff = -itemOffset / estimatedItemHeight!
      sliceTo += Math.ceil(diff / 2)
      continue
    }

    // 2. If the bottom of the item is displayed, it is the last item in the viewport
    if (itemOffset === 0) break

    // 3. If part of the entry is clipped at the bottom, it is the last item of the viewport
    if (itemOffset < itemHeight) break

    // This item has not appeared yet, continue to test the previous item
    // The dichotomy method quickly estimates the next try location
    const diff = itemOffset / estimatedItemHeight!
    sliceTo -= Math.ceil(diff / 2)}// Slice does not contain end, so + 1
  sliceTo += 1

  return { sliceFrom, sliceTo }
}
Copy the code

So that’s the core of calculating the viewable area. The full code will be presented later.

DOM updates

Since we use Vue to implement the virtual list, we can save a lot of tedious detail management in DOM updating. We only need to worry about figuring out what items should appear in the current viewport once the list has been scrolled somewhere.

Still, considering the smoothness of scrolling and DOM manipulation in browsers like IE11, we had to do a lot more.

Batch DOM operation

As you can see in the Developer tools panel of IE11, scrolling, and frequent insertion and removal of nodes at the beginning and end of the virtual list, can cause serious performance problems. Therefore, we must control the frequency of DOM operations.

Batch production is part of the solution.

The idea is that in the scroll callback, we calculate the node start and end number of the visible area, not directly, but by adding an additional render number. For example, if we calculate that we should render 20 to 30 items, we can render 30 nodes at once by adding 10 additional rendered items before and after, i.e. 10 to 40. As we continue scrolling, we check whether the new start and end ranges are still in the range of 10 to 40. If so, we do not add or delete new nodes.

Core implementation:

// Refresh the local render data slice range
private_updateSliceRange(forceUpdate? :boolean) {
  // The number of extra rendered items fluctuates up and down
  const COUNT = this._preRenderingCount()

  // Pre-render trigger threshold
  const THRESHOLD = this._preRenderingThreshold()    

  // Total amount of data
  const MAX = this.dataView.length

  // Calculate the exact section interval
  const range = this._calcSliceRange()    

  // Check whether the calculated slice range is included in the currently rendered slice return
  // If so, no slices need to be updated, (if forceUpdate, then slices need to be re-sliced anyway)
  let fromThreshold = range.sliceFrom - THRESHOLD
  if (fromThreshold < 0) fromThreshold = 0
  let toThreshold = range.sliceTo + THRESHOLD
  if (toThreshold > MAX) toThreshold = MAX

  // There is no need to force refresh, and the upper and lower ends do not reach the threshold, no need to slice again
  if(! forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
    return
  }

  // Here is how to update the slice

  // Append pre-rendered items to the head and tail of the section
  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()
}
Copy the code

After using this batch operation, you can see that the normal mouse scroll, IE can also be relatively smooth scrolling.

The event

Because the DOM of a virtual list is constantly generated and destroyed, it is inefficient to bind events directly to list items. Therefore, it is a good solution to use the event broker, which registers the event at the root of the component, and distinguishes which list item is bubbling up from the event. Target.

Component implementation

import { Component, Vue, Prop, Watch } from 'vue-property-decorator'
import { createSparseRangeList } from './SparseRangeList'

// List item data package, data field stores the original data
// All component operations should not change the contents of data, but instead modify the properties of the package object
class ItemWrapper {
  // Raw data
  data: any

  // Data is a unique key
  key: any

  // Entry height
  // 1. The positive number represents the height that has been calculated
  // 2. 0 represents the uncalculated height and is not displayed
  // 3. The negative number represents the height that needs to be hidden, and the absolute value is the height that has been calculated to facilitate unhiding
  height: number

  // Record whether the height has been calculated based on the actual DOM
  realHeight: boolean

  // Sequence number of entries in the current filtering view
  viewIndex: number

  constructor(data: any, key: any, height: number) {
    this.data = data

    // The unique id of the data, which is the serial number of the initialization data
    // Every time the data passed in changes, it is regenerated
    this.key = key

    // High cache of entries
    // 1. Used for quick recovery when rebuilding height storage
    // 2. Used to quickly get the height from the data
    this.height = height >> 0

    this.realHeight = false

    // Refresh every time a dataView is generated
    this.viewIndex = - 1}}@Component({ name: 'VList' })
export default class VList extends Vue {
  [key: string] :any

  // Height storage is not responsive
  private itemHeightStore: any

  // The component width is 100% of the container if not set
  @Prop({ type: Number })
  privatewidth? :number

  // Component height, if not set to 100% of the container
  @Prop({ type: Number })
  privateheight? :number

  // Pass the height value to fix the item height
  @Prop({ type: Number })
  privatefixedItemHeight? :number

  // Estimate element height,
  // In a list of indeterminate heights, when the height has not been calculated,
  // The closer the value is to the average height of the element, the more efficient it is.
  @Prop({ type: Number.default: 30 })
  privateestimatedItemHeight! :number

  // Data list
  @Prop({ type: Array.default: (a)= >([])})privatedata! :any[]

  // A method to calculate the height of items
  @Prop({
    type: Function.default(node: Node, wrappedData: ItemWrapper) {
      return (node as HTMLElement).clientHeight
    }
  })
  privateitemHeightMethod! :(node: Node, wrappedItem: ItemWrapper) = > number

  // Data filtering method (can be used for external implementation of search box filtering)
  @Prop({ type: Function })
  privatefilterMethod? :(data: any) = > boolean

  // Data sort method (can be used for external implementation of data custom filtering)
  @Prop({ type: Function })
  privatesortMethod? :(a: any, b: any) = > number

  // List of wrapped data (must be freeze, otherwise large list performance will not hold)
  private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data))

  // Actually render a slice of the data list on the screen
  private dataSlice: ReadonlyArray<ItemWrapper> = []

  / / viewport width
  private viewportWidth = this.width || 0

  / / the viewport height
  private viewportHeight = this.height || 0

  // The serial number of the first data in the current viewPort
  private sliceFrom = 0

  // The sequence number of the last data in the current viewport
  private sliceTo = 0

  // List height
  private listHeight = 0

  // Check whether the height mode is fixed
  private get isFixedHeight() {
    return this.fixedItemHeight! > =0
  }

  // Get the default entry height
  private get defaultItemHeight() {
    return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight
  }

  // The list of data under the current filter condition
  // Dependencies: 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)
      })
    }

    // Re-record the position of the data in the view, which can be used to hide part of the entry, so that the height and coordinates can be calculated accurately
    const size = data.length
    for (let index = 0; index < size; index += 1) {
      const wrappedItem = data[index]
      wrappedItem.viewIndex = index
    }

    return Object.freeze(data)
  }

  // The original list data changes, rewrap the data
  @Watch('data')
  private onDataChange(data: any[]) {
    this.wrappedData = Object.freeze(this._wrapData(data))
  }

  // Current filtering, sorting view changes, relayout
  @Watch('dataView')
  private onDataViewChange(wrappedItems: ItemWrapper[]) {
    // Rebuild the height storage
    const estimatedItemHeight = this.defaultItemHeight
    this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)
    // Quickly recover the height of items whose height has been calculated from the cache
    wrappedItems.forEach((wrappedItem, index) = > {
      // Those less than zero need to be hidden, so the height is 0
      this.itemHeightStore.setValue(index,
        wrappedItem.height > 0 ? wrappedItem.height : 0)})// Refresh list height
    this.updateListHeight()

    // Reset the scroll position
    // TODO, anchor element
    const { viewport } = this.$refs as any
    if (viewport) viewport.scrollTop = 0

    // Re-slice the data required by the current 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(a) {
    this.redraw(a)
    this.layoutObserver.observe(this.$el, { attributes: true }) // If the height is not fixed, listen for child element insertion and extract heightif (!this.isFixedHeight) {
      this.childObserver.observe(this.$refs.content, { childList: true })}}private beforeDestory(a) {
    this.layoutObserver.disconnect(a)
    if (!this.isFixedHeight) {
      this.childObserver.disconnect(a)
    }
    this.itemHeightStore = null} / /DOMThe structure is relatively simple, no needtemplate, directly using the render function outputVDOM
  private render(createElement: any) {
    return createElement(
      'div', // Component container, with external layout
      {
        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', // The visible range of the scroll area
          {
            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', // The content container, from which the real height of the content is reflected
              {
                class: 'VList_scollable',
                ref: 'content',
                style: {
                  'box-sizing': 'border-box',
                  position: 'relative',
                  margin: '0',
                  padding: '0',
                  height: this.listHeight + 'px'
                }
              },
              / / the list items
              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', // Note: There is a black screen bug when using transfrom // transform: `translate(0, ${top})` // transform: `translate3d(0, ${top}, 0)` top: this._top(wrappedItem.viewIndex) + 'px' } }, // Insert raw data, key into slot, // For custom entry content use this.$scopedSlots.default! ({ item: wrappedItem.data, listKey: wrappedItem.key }) )})
            )])]} // Redraw the interface to make sure the list is rendered correctlypublic redraw(a) {
    const viewport = this. $refs.viewport as HTMLElement
    const { clientWidth.clientHeight } = viewport
    this.viewportWidth = clientWidth
    this.viewportHeight = clientHeight
    this.updateListHeight(a)
    this. _updateSliceRange(true} // Refresh the total height of the listpublic updateListHeight(a) {
    const { itemHeightStore } = this
    const rangeValues = itemHeightStore.values(a)
    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} / /DomWhen inserting, calculate the height and then // batch refresh the height to avoid performance issues from frequently adjusting the list heightpublic batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number} >) {
    records.forEach(({ wrappedItem, height }) = > {this._updateHeight(wrappedItem, height, true)})
    this.updateListHeight(a)
    this. _updateSliceRange(a)} // Pass datakey, set the height of the corresponding entrypublic updateHeightByKey(key: any, height: number) {
    const wrappedItem = this.wrappedData[key]
    if (! wrappedItem) return
    this. _updateHeight(wrappedItem, height)
    this.updateListHeight(a)
    this. _updateSliceRange(a)} // Pass datakeyTo set the display status of the corresponding entrypublic 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(a)
      this. _updateSliceRange(a)// Force redrawthis. _doSlice(a)}} // Pass datakeyTo set the display status of the corresponding entrypublic 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(a)// Force redrawthis. _updateSliceRange(true}} // Pass datakeyList to set the display state of the corresponding entrypublic 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(a)// Force redrawthis. _updateSliceRange(true} // Pass datakeyList to set the display state of the corresponding entrypublic hideByKeys(keys: any[]) {
    const wrappedItems = keys.map((key) = >this.wrappedData[key]).filter(wrappedItem => wrappedItem && wrappedItem.height > 0)
    wrappedItems.forEach((wrappedItem) = > {// Set the value to negative to indicate hiding
      const height = -wrappedItem.height
      wrappedItem.height = height
      this._updateHeight(wrappedItem, height)})
    this.updateListHeight(a)// Force redrawthis. _updateSliceRange(true} // Internal method to calculate the start and stop points of local render data slicesprivate _calcSliceRange(a) {
    if (!this.dataView.length) {
      return { sliceFrom: 0.sliceTo: 0}} // Total amount of dataconst MAX = this.dataView.length// Upper boundary of viewportconst viewportTop = (this.$refs.viewport as any).scrollTop| | 0 / / boundary under the viewportconst viewportBottom = viewportTop + this.viewportHeight// Estimate item heightconst estimatedItemHeight = this.defaultItemHeight// Calculate the starting sequence from the estimated valuelet sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
    if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
    while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
      const itemTop = this. _top(sliceFrom// The top of the entry is relative toviewportTop offsetconst itemOffset = itemTop - viewportTop// 1. There is a distance between this entry and the top of the viewportif (itemOffset > 0) {// The dichotomy method quickly estimates the next try locationconst diff = itemOffset / estimatedItemHeight!
        sliceFrom- =Math.ceil(diff / 2)
        continue} // 2. If the top of the entry is displayed, the entry is the first element of the viewportif (itemOffset === 0) break// All of the followingitemOffset < 0

      const itemHeight = this. _itemHeight(sliceFrom) // 3. If part of this entry is exposed at the top, it is the first element of this viewportif (itemOffset < itemHeight) break// 4. The entry has been rolled out of the viewport, continue to test the next entry // dichotomy to quickly estimate the next try positionconst diff = -itemOffset / estimatedItemHeight!
      sliceFrom+ =Math.ceil(diff / 2} // Calculate the end sequence from the estimated valuelet 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// The bottom of the entry is relative toviewportBottom offsetconst itemOffset = itemBottom - viewportBottom// 1. There is a distance between the bottom of this item and the bottom of the viewport, indicating that there are items below the item to display, continue to test the next itemif (itemOffset < 0) {// The dichotomy method quickly estimates the next try locationconst diff = -itemOffset / estimatedItemHeight!
        sliceTo+ =Math.ceil(diff / 2)
        continue} // 2. If the bottom of the item is displayed, it is the last item in the viewportif (itemOffset === 0) break// 3. If part of the entry is clipped at the bottom, it is the last item of the viewportif (itemOffset < itemHeight) break// This entry has not been played yet, continue to test the previous entry // dichotomy to quickly estimate the next try locationconst diff = itemOffset / estimatedItemHeight!
      sliceTo- =Math.ceil(diff / 2} / /sliceDo not includeendSo plus 1sliceTo+ = 1return { sliceFrom.sliceTo}} / / both ends up and down in batch render project quantity / / principle is that every time insert the delete is a small batch action, / / not only insert a, destroyed a / / calculate the partial rendering data range, with the last calculated, the result of the gap / / in this amount of fluctuation range, is not to slice rendering, Used to // preventIE11 Frequent content insertion causes performance pressureprivate _preRenderingCount(a){// Prerender 2 screens by defaultreturn Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2} // Scroll down to how many items are left, load the next batch // reliefMacbook & iOSWhite screen for touch scrollingprivate _preRenderingThreshold(a){// The default is to load the next batch of slices when half the number of pre-rendered slices is reachedreturn Math.floor(this._preRenderingCount() / 2} // Refresh the local render data slice rangeprivate _updateSliceRange(forceUpdate? :boolean) {// The number of extra rendered items fluctuates up and downconst COUNT = this. _preRenderingCount(a)// Pre-render trigger thresholdconst THRESHOLD = this. _preRenderingThreshold(a)// Total amount of dataconst MAX = this.dataView.length// Calculate the exact section intervalconst range = this. _calcSliceRange(a)// Check whether the calculated slice range is included by the currently rendered slice return // If so, no need to update the slice, (ifforceUpdate, it needs to be re-sliced anyway.)let fromThreshold = range.sliceFrom - THRESHOLD
    if (fromThreshold < 0) fromThreshold = 0
    let toThreshold = range.sliceTo + THRESHOLD
    if (toThreshold > MAX) toThreshold = MAX// There is no need to force refresh, and the upper and lower ends do not reach the threshold, no need to slice againif (! forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
      return} // Update the slice condition // Append pre-rendered items to the head and tail of the slice rangelet { 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(a)} // The slice of data that needs to be renderedprivate _doSlice(a) {
    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` data indataViewIn theindex
  private _itemHeight(index: number) :number {
    return this.itemHeightStore.getValueAt(index/ / `)}index` data indataViewIn theindex
  private _top(index: number) :number {
    if (index === 0) return0 // 0 ~ height summation of the previous termconst 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} // Package raw data listprivate _wrapData(list: any[]) :ItemWrapper[] {
    return list.map((item, index) = >new ItemWrapper(item, index, this.defaultItemHeight!)} // passDOM NodeGet the corresponding dataprivate _getDataByNode(node: Node) :ItemWrapper {
    return this.wrappedData[(node as any).dataset.key} // Refresh the list item heightprivate _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight? :boolean) {
    height = height>> 0 // Update the node height cachewrappedItem.height = height

    if (isRealHeight) {
      wrappedItem.realHeight = true} / / ifwrappedItemIs the item under the current filter, // the height store is refreshed at the same timestore
    const index = this.dataView.indexOf(wrappedItem)
    if (index ! = = 1) {// Less than or equal to zero indicates that the fold is not displayed, and the calculated height is zero // negative values existwrappedItemIn, used for recovery when folding againstthis.itemHeightStore.setValue(index, height > 0 ? height : 0)}} // Check whether the node is inserted for the first time, if so, calculate the height and update the correspondingItemWrapper
  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: ArrayThe < {wrappedItem: ItemWrapper.height: number} > = []addedNodes.forEach((node: Node) = > {const wrappedItem = this._getDataByNode(node)

      // If the calculated height is stored in the wrappedItem,
      // 则直接返回，不访问 clientHeight
      // To avoid performance overhead (IE 11 has very poor clientHeight performance)
      if (wrappedItem.realHeight) {
        return
      }

      const height = this.itemHeightMethod(node, wrappedItem) > > 0if (wrappedItem.height ! == height) {
        batch.push({ wrappedItem, height })}else {
        // The calculated height is the same as the default value,
        // No update is required, but the calculated state is set
        // So that the cache can be used directly next time
        wrappedItem.realHeight = true}})

    if (batch.length) {
      this.batchUpdateHeight(batch}} // Scroll event handlerprivate _onScroll(a) {
    this. _updateSliceRange(a)}}Copy the code

application

Once virtual lists are implemented, they can be used for many purposes.

Typical examples are:

Normal list. For example, a long list of articles.
Table component. Large data tables are appropriate.
Tree components. Simply deal with the next level of indentation and folding, tick linkage and other logic, you can realize the tree component.

In some scenarios where a large amount of data must be loaded and processed at once, such as a large tree of multi-choice components, it is difficult to meet performance requirements without virtual lists. For example, the tree component in Element UI, on a PC I5 7th generation CPU, with 1000 nodes, can take a few seconds to switch to full selection, which is a terrible thing.

At this point, in the bar but product demand, customer scenario, might as well consider the virtual list to do.

The full text.

Big list problem

Visual area calculation

Coordinates of list items

Calculate visual entries

DOM updates

Batch DOM operation

The event

Component implementation

application

Related Posts

Vue Fruit bookkeeping – Vuex for global data management

Front-end Console debugging tips

D3 Basics 02 – Core operations on SVG