/*
|
* Licensed to the Apache Software Foundation (ASF) under one
|
* or more contributor license agreements. See the NOTICE file
|
* distributed with this work for additional information
|
* regarding copyright ownership. The ASF licenses this file
|
* to you under the Apache License, Version 2.0 (the
|
* "License"); you may not use this file except in compliance
|
* with the License. You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing,
|
* software distributed under the License is distributed on an
|
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
|
* KIND, either express or implied. See the License for the
|
* specific language governing permissions and limitations
|
* under the License.
|
*/
|
|
import {ArrayLike} from 'zrender/src/core/types';
|
|
// return key.
|
type DiffKeyGetter<CTX = unknown> =
|
(this: DataDiffer<CTX>, value: unknown, index: number) => string;
|
|
type DiffCallbackAdd = (newIndex: number) => void;
|
type DiffCallbackUpdate = (newIndex: number, oldIndex: number) => void;
|
type DiffCallbackRemove = (oldIndex: number) => void;
|
type DiffCallbackUpdateManyToOne = (newIndex: number, oldIndex: number[]) => void;
|
type DiffCallbackUpdateOneToMany = (newIndex: number[], oldIndex: number) => void;
|
|
/**
|
* The value of `DataIndexMap` can only be:
|
* + a number
|
* + a number[] that length >= 2.
|
* + null/undefined
|
*/
|
type DataIndexMap = {[key: string]: number | number[]};
|
|
function dataIndexMapValueLength(
|
valNumOrArrLengthMoreThan2: number | number[]
|
): number {
|
return valNumOrArrLengthMoreThan2 == null
|
? 0
|
: ((valNumOrArrLengthMoreThan2 as number[]).length || 1);
|
}
|
|
function defaultKeyGetter(item: string): string {
|
return item;
|
}
|
|
export type DataDiffMode = 'oneToOne' | 'multiple';
|
|
class DataDiffer<CTX = unknown> {
|
|
private _old: ArrayLike<unknown>;
|
private _new: ArrayLike<unknown>;
|
private _oldKeyGetter: DiffKeyGetter<CTX>;
|
private _newKeyGetter: DiffKeyGetter<CTX>;
|
private _add: DiffCallbackAdd;
|
private _update: DiffCallbackUpdate;
|
private _updateManyToOne: DiffCallbackUpdateManyToOne;
|
private _updateOneToMany: DiffCallbackUpdateOneToMany;
|
private _remove: DiffCallbackRemove;
|
private _diffModeMultiple: boolean;
|
|
readonly context: CTX;
|
|
/**
|
* @param context Can be visited by this.context in callback.
|
*/
|
constructor(
|
oldArr: ArrayLike<unknown>,
|
newArr: ArrayLike<unknown>,
|
oldKeyGetter?: DiffKeyGetter<CTX>,
|
newKeyGetter?: DiffKeyGetter<CTX>,
|
context?: CTX,
|
// By default: 'oneToOne'.
|
diffMode?: DataDiffMode
|
) {
|
this._old = oldArr;
|
this._new = newArr;
|
|
this._oldKeyGetter = oldKeyGetter || defaultKeyGetter;
|
this._newKeyGetter = newKeyGetter || defaultKeyGetter;
|
|
// Visible in callback via `this.context`;
|
this.context = context;
|
|
this._diffModeMultiple = diffMode === 'multiple';
|
}
|
|
/**
|
* Callback function when add a data
|
*/
|
add(func: DiffCallbackAdd): this {
|
this._add = func;
|
return this;
|
}
|
|
/**
|
* Callback function when update a data
|
*/
|
update(func: DiffCallbackUpdate): this {
|
this._update = func;
|
return this;
|
}
|
|
/**
|
* Callback function when update a data and only work in `cbMode: 'byKey'`.
|
*/
|
updateManyToOne(func: DiffCallbackUpdateManyToOne): this {
|
this._updateManyToOne = func;
|
return this;
|
}
|
|
/**
|
* Callback function when update a data and only work in `cbMode: 'byKey'`.
|
*/
|
updateOneToMany(func: DiffCallbackUpdateOneToMany): this {
|
this._updateOneToMany = func;
|
return this;
|
}
|
|
/**
|
* Callback function when remove a data
|
*/
|
remove(func: DiffCallbackRemove): this {
|
this._remove = func;
|
return this;
|
}
|
|
execute(): void {
|
this[this._diffModeMultiple ? '_executeMultiple' : '_executeOneToOne']();
|
}
|
|
private _executeOneToOne(): void {
|
const oldArr = this._old;
|
const newArr = this._new;
|
const newDataIndexMap: DataIndexMap = {};
|
const oldDataKeyArr: string[] = new Array(oldArr.length);
|
const newDataKeyArr: string[] = new Array(newArr.length);
|
|
this._initIndexMap(oldArr, null, oldDataKeyArr, '_oldKeyGetter');
|
this._initIndexMap(newArr, newDataIndexMap, newDataKeyArr, '_newKeyGetter');
|
|
for (let i = 0; i < oldArr.length; i++) {
|
const oldKey = oldDataKeyArr[i];
|
const newIdxMapVal = newDataIndexMap[oldKey];
|
const newIdxMapValLen = dataIndexMapValueLength(newIdxMapVal);
|
|
// idx can never be empty array here. see 'set null' logic below.
|
if (newIdxMapValLen > 1) {
|
// Consider there is duplicate key (for example, use dataItem.name as key).
|
// We should make sure every item in newArr and oldArr can be visited.
|
const newIdx = (newIdxMapVal as number[]).shift();
|
if ((newIdxMapVal as number[]).length === 1) {
|
newDataIndexMap[oldKey] = (newIdxMapVal as number[])[0];
|
}
|
this._update && this._update(newIdx as number, i);
|
}
|
else if (newIdxMapValLen === 1) {
|
newDataIndexMap[oldKey] = null;
|
this._update && this._update(newIdxMapVal as number, i);
|
}
|
else {
|
this._remove && this._remove(i);
|
}
|
}
|
|
this._performRestAdd(newDataKeyArr, newDataIndexMap);
|
}
|
|
/**
|
* For example, consider the case:
|
* oldData: [o0, o1, o2, o3, o4, o5, o6, o7],
|
* newData: [n0, n1, n2, n3, n4, n5, n6, n7, n8],
|
* Where:
|
* o0, o1, n0 has key 'a' (many to one)
|
* o5, n4, n5, n6 has key 'b' (one to many)
|
* o2, n1 has key 'c' (one to one)
|
* n2, n3 has key 'd' (add)
|
* o3, o4 has key 'e' (remove)
|
* o6, o7, n7, n8 has key 'f' (many to many, treated as add and remove)
|
* Then:
|
* (The order of the following directives are not ensured.)
|
* this._updateManyToOne(n0, [o0, o1]);
|
* this._updateOneToMany([n4, n5, n6], o5);
|
* this._update(n1, o2);
|
* this._remove(o3);
|
* this._remove(o4);
|
* this._remove(o6);
|
* this._remove(o7);
|
* this._add(n2);
|
* this._add(n3);
|
* this._add(n7);
|
* this._add(n8);
|
*/
|
private _executeMultiple(): void {
|
const oldArr = this._old;
|
const newArr = this._new;
|
const oldDataIndexMap: DataIndexMap = {};
|
const newDataIndexMap: DataIndexMap = {};
|
const oldDataKeyArr: string[] = [];
|
const newDataKeyArr: string[] = [];
|
|
this._initIndexMap(oldArr, oldDataIndexMap, oldDataKeyArr, '_oldKeyGetter');
|
this._initIndexMap(newArr, newDataIndexMap, newDataKeyArr, '_newKeyGetter');
|
|
for (let i = 0; i < oldDataKeyArr.length; i++) {
|
const oldKey = oldDataKeyArr[i];
|
const oldIdxMapVal = oldDataIndexMap[oldKey];
|
const newIdxMapVal = newDataIndexMap[oldKey];
|
const oldIdxMapValLen = dataIndexMapValueLength(oldIdxMapVal);
|
const newIdxMapValLen = dataIndexMapValueLength(newIdxMapVal);
|
|
if (oldIdxMapValLen > 1 && newIdxMapValLen === 1) {
|
this._updateManyToOne && this._updateManyToOne(newIdxMapVal as number, oldIdxMapVal as number[]);
|
newDataIndexMap[oldKey] = null;
|
}
|
else if (oldIdxMapValLen === 1 && newIdxMapValLen > 1) {
|
this._updateOneToMany && this._updateOneToMany(newIdxMapVal as number[], oldIdxMapVal as number);
|
newDataIndexMap[oldKey] = null;
|
}
|
else if (oldIdxMapValLen === 1 && newIdxMapValLen === 1) {
|
this._update && this._update(newIdxMapVal as number, oldIdxMapVal as number);
|
newDataIndexMap[oldKey] = null;
|
}
|
else if (oldIdxMapValLen > 1) {
|
for (let i = 0; i < oldIdxMapValLen; i++) {
|
this._remove && this._remove((oldIdxMapVal as number[])[i]);
|
}
|
}
|
else {
|
this._remove && this._remove(oldIdxMapVal as number);
|
}
|
}
|
|
this._performRestAdd(newDataKeyArr, newDataIndexMap);
|
}
|
|
private _performRestAdd(newDataKeyArr: string[], newDataIndexMap: DataIndexMap) {
|
for (let i = 0; i < newDataKeyArr.length; i++) {
|
const newKey = newDataKeyArr[i];
|
const newIdxMapVal = newDataIndexMap[newKey];
|
const idxMapValLen = dataIndexMapValueLength(newIdxMapVal);
|
if (idxMapValLen > 1) {
|
for (let j = 0; j < idxMapValLen; j++) {
|
this._add && this._add((newIdxMapVal as number[])[j]);
|
}
|
}
|
else if (idxMapValLen === 1) {
|
this._add && this._add(newIdxMapVal as number);
|
}
|
// Support both `newDataKeyArr` are duplication removed or not removed.
|
newDataIndexMap[newKey] = null;
|
}
|
}
|
|
private _initIndexMap(
|
arr: ArrayLike<unknown>,
|
// Can be null.
|
map: DataIndexMap,
|
// In 'byKey', the output `keyArr` is duplication removed.
|
// In 'byIndex', the output `keyArr` is not duplication removed and
|
// its indices are accurately corresponding to `arr`.
|
keyArr: string[],
|
keyGetterName: '_oldKeyGetter' | '_newKeyGetter'
|
): void {
|
const cbModeMultiple = this._diffModeMultiple;
|
|
for (let i = 0; i < arr.length; i++) {
|
// Add prefix to avoid conflict with Object.prototype.
|
const key = '_ec_' + this[keyGetterName](arr[i], i);
|
if (!cbModeMultiple) {
|
keyArr[i] = key;
|
}
|
if (!map) {
|
continue;
|
}
|
|
const idxMapVal = map[key];
|
const idxMapValLen = dataIndexMapValueLength(idxMapVal);
|
|
if (idxMapValLen === 0) {
|
// Simple optimize: in most cases, one index has one key,
|
// do not need array.
|
map[key] = i;
|
if (cbModeMultiple) {
|
keyArr.push(key);
|
}
|
}
|
else if (idxMapValLen === 1) {
|
map[key] = [idxMapVal as number, i];
|
}
|
else {
|
(idxMapVal as number[]).push(i);
|
}
|
}
|
}
|
|
}
|
|
export default DataDiffer;
|
