Using sparse arrays is the key!

We’ve talked in detail about sparse arrays and how they can get the most out of a front-end spreadsheet in a real project. This time, we will introduce the specific application of sparse array in the front end from practical application.

We all know that in Javascript we create a sparse matrix by building up the Array() constructor, or by creating an Array whose index length is larger than the current Array’s length.

Var arr = new Array(100) var arr = new Array(100) A [50] = 50; // Assign to add an element with length 51Copy the code

In a sparse array, there are no elements whose nodes are empty. Fetching these nodes returns undefined. We can determine whether a node has elements by using index in array. For example, in the following code, both a[0] and a[1] return undefined, but a[1] is null.

JS already supports the storage of sparse array, but in practice, the storage of sparse array is not directly carried out, but other storage methods will be constructed to save sparse array according to the actual situation. To understand why this is unnecessary, you need to understand the concept of data persistence.

When we perform many operations in the front end, a lot of data will be generated. For example, when many people fill in and cooperate in the front end table, there will be a lot of data that need to be stored for a long time, and some data will be transferred to other locations for people to store, manage and operate. The key to achieving this goal is persistence of data. We need to serialize the data in memory to a storage format such as JSON to the database and deserialize it to memory. Json data in spreadsheets: serialization and deserialization have been introduced in detail in the previous article, you can have a look.

See here, you think the problem is solved once and for all? Pattern Tucson.

For data persistence, we use JSON, but a new problem arises: JSON stores don’t have undefined. When we operate on an array, the empty field in the array is serialized to NULL, as shown in the figure below.

JSON.stringify(a) '[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,nul l,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,nul l,null,null,50]'Copy the code

When parsed again, the array is no longer sparse.

JSON.parse(JSON.stringify(a))
(51) [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, 50]

Copy the code

In this case, in order to solve the problem of converting JSON data, we need to build some other storage methods to solve the problem.

1. Object storage

At the front end, we can easily realize Sparse Array through Object by using THE language features of JS. For example, in Spread JS, the object attribute name corresponds to the row and column of the cell, the value attribute stores the value of the cell, and the formula and style attributes can also be extended to store the formula and style of the cell. With a Sparse Array, there is no need to initialize the size or expand the data, and only the reference of the row attribute needs to be changed for row operations.

The data store results in the figure above are as follows

{
    "0": {
        "0": {
            "value": 0
        }
    },
    "2": {
        "1": {
            "value": 2
        },
        "3": {
            "value": "S"
        }
    },
    "4": {
        "3": {
            "value": 3
        }
    }
}
 
Copy the code

Data is accessed directly through object properties when needed. Below is a simple object implementation of JS Sparse Array.

function SparseArray(){ this._array = {} } SparseArray.prototype.setValue = function(row, col, data){ if(! this._array[row]){ this._array[row] = {} } this._array[row][col] = data } SparseArray.prototype.getValue = function(row,  col){ if(this._array[row]){ return this._array[row][col] } return undefined; } let arr = new SparseArray(); arr.setValue(3, 3, 5); console.log(arr.getValue(3, 3)) // 5Copy the code

2. Triples

Each element in the matrix has three information: row label, column label and element value. Putting elements into the array as needed is triplet storage. The storage structure can be an object containing element information, or it can be simplified to an array of length 3. The storage mode of triplet can easily record track information or free curve information similar to the following figure. By pushing and pop the array, it can be easily back and forward.

The track information in the figure above is stored as an array triplet as follows, with the element value representing the current number of elements. You can also use objects to record time and other information.

[[1,1,1], [5,8,2], [4,3,3], [1,5,4]Copy the code

Let’s set up an undoStack record fallback in this way.

function TSMatrix(){ this._array = []; this.undoStack = [] } TSMatrix.prototype.addNode = function(row, col, value){ this._array.push([row, col, value]) } TSMatrix.prototype.canUndo = function(){ return this._array.length > 0; } TSMatrix.prototype.undo = function(){ if(this._array.length > 0){ this.undoStack.push(this._array.pop()) } } TSMatrix.prototype.canRedo = function(){ return this.undoStack.length > 0; } TSMatrix.prototype.redo = function(){ if(this._array.length > 0){ this._array.push(this.undoStack.pop()) } } TSMatrix.prototype.print = function(){ console.log(JSON.stringify(this._array)) } let mat = new TSMatrix(); mat.addNode(1, 1, 1) mat.addNode(5, 8, 2) mat.addNode(4, 3, 3) mat.addNode(1, 5, 4) mat. Print () / / [,1,1 [1], [5,8,2], filling [4], [1,5,4]] mat. Undo (mat). Print () / / [,1,1 [1], [5,8,2], [4 filling]] mat. Redo () Mat. Print () / / [,1,1 [1], [5,8,2], filling [4], [1,5,4]]Copy the code

In addition to the above two methods, you can also combine the above methods to create cross-linked lists for more complex scenarios. Give it a thumbs up if you’re interested and we’ll pick it up next time.

We’ll continue to bring you in-depth decryption of other front-end spreadsheet technologies in the future, so don’t miss it.