utils - function diff

[BKJang]

/*
egjs-list-differ
Copyright (c) 2019-present NAVER Corp.
MIT license
*/
import { MapInteface, DiffResult } from "./types";
import PolyMap from "./PolyMap";
import HashMap from "./HashMap";
import { SUPPORT_MAP } from "./consts";
import Result from "./Result";

/**
 *
 * @memberof eg.ListDiffer
 * @static
 * @function
 * @param - Previous List <ko> 이전 목록 </ko>
 * @param - List to Update <ko> 업데이트 할 목록 </ko>
 * @param - This callback function returns the key of the item. <ko> 아이템의 키를 반환하는 콜백 함수입니다.</ko>
 * @return - Returns the diff between `prevList` and `list` <ko> `prevList`와 `list`의 다른 점을 반환한다.</ko>
 * @example
 * import { diff } from "@egjs/list-differ";
 * // script => eg.ListDiffer.diff
 * const result = diff([0, 1, 2, 3, 4, 5], [7, 8, 0, 4, 3, 6, 2, 1], e => e);
 * // List before update
 * // [1, 2, 3, 4, 5]
 * console.log(result.prevList);
 * // Updated list
 * // [4, 3, 6, 2, 1]
 * console.log(result.list);
 * // Index array of values added to `list`
 * // [0, 1, 5]
 * console.log(result.added);
 * // Index array of values removed in `prevList`
 * // [5]
 * console.log(result.removed);
 * // An array of index pairs of `prevList` and `list` with different indexes from `prevList` and `list`
 * // [[0, 2], [4, 3], [3, 4], [2, 6], [1, 7]]
 * console.log(result.changed);
 * // The subset of `changed` and an array of index pairs that moved data directly. Indicate an array of absolute index pairs of `ordered`.(Formatted by: Array<[index of prevList, index of list]>)
 * // [[4, 3], [3, 4], [2, 6]]
 * console.log(result.pureChanged);
 * // An array of index pairs to be `ordered` that can synchronize `list` before adding data. (Formatted by: Array<[prevIndex, nextIndex]>)
 * // [[4, 1], [4, 2], [4, 3]]
 * console.log(result.ordered);
 * // An array of index pairs of `prevList` and `list` that have not been added/removed so data is preserved
 * // [[0, 2], [4, 3], [3, 4], [2, 6], [1, 7]]
 * console.log(result.maintained);
 */
export function diff<T>(
  prevList: T[],
  list: T[],
  findKeyCallback?: (e: T, i: number, arr: T[]) => any
): DiffResult<T> {
  const mapClass: new () => MapInteface<any, number> = SUPPORT_MAP ? Map : (findKeyCallback ? HashMap : PolyMap);
  const callback = findKeyCallback || ((e: T) => e);
  const added: number[] = [];
  const removed: number[] = [];
  const maintained: number[][] = [];
  const prevKeys = prevList.map(callback);
  const keys = list.map(callback);
  const prevKeyMap: MapInteface<any, number> = new mapClass();
  const keyMap: MapInteface<any, number> = new mapClass();
  const changedBeforeAdded: number[][] = [];
  const fixed: boolean[] = [];
  const removedMap: object = {};
  let changed: number[][] = [];
  let addedCount = 0;
  let removedCount = 0;

  // Add prevKeys and keys to the hashmap.
  prevKeys.forEach((key, prevListIndex) => {
    prevKeyMap.set(key, prevListIndex);
  });
  keys.forEach((key, listIndex) => {
    keyMap.set(key, listIndex);
  });

  // Compare `prevKeys` and `keys` and add them to `removed` if they are not in `keys`.
  prevKeys.forEach((key, prevListIndex) => {
    const listIndex = keyMap.get(key);

    // In prevList, but not in list, it is removed.
    if (typeof listIndex === "undefined") {
      ++removedCount;
      removed.push(prevListIndex);
    } else {
      removedMap[listIndex] = removedCount;
    }
  });

  // Compare `prevKeys` and `keys` and add them to `added` if they are not in `prevKeys`.
  keys.forEach((key, listIndex) => {
    const prevListIndex = prevKeyMap.get(key);

    // In list, but not in prevList, it is added.
    if (typeof prevListIndex === "undefined") {
      added.push(listIndex);
      ++addedCount;
    } else {
      maintained.push([prevListIndex, listIndex]);
      removedCount = removedMap[listIndex] || 0;

      changedBeforeAdded.push([
        prevListIndex - removedCount,
        listIndex - addedCount,
      ]);
      fixed.push(listIndex === prevListIndex);
      if (prevListIndex !== listIndex) {
        changed.push([prevListIndex, listIndex]);
      }
    }
  });
  // Sort by ascending order of 'to(list's index).
  removed.reverse();

  return new Result(
    prevList,
    list,
    added,
    removed,
    changed,
    maintained,
    changedBeforeAdded,
    fixed,
  );
}

🙏 Reference

• naver/egjs-list-differ - utils.ts

[BKJang]

[BKJang]

diff function Property 정의

• prevKeyMap : 기존 리스트를 Map 형태로 변경

  • { key : [prevListValue], value: [prevListIndex] }

• newKeyMap : 변경된 리스트를 Map 형태로 변경

  • { key : [newListValue], value: [newListIndex] }

• removedMap: 기존 리스트에서 제거된 시점의 index와 해당 시점의 제거된 원소 수를 Map 형태로 구현

  • { key : [prevListIndex], value: [removedCount] }

• defaultCallback : diff function의 인자로 넘어온 findKeyCallback이 없을 경우 세팅

• maintained : 값을 기준으로 비교했을 때 유지된 값의 index를 기준으로 세팅

  • [ [prevListIndex, newListIndex] ]

• changedBeforeAdded: ???

• fixed : maintained 원소의 각각을 비교하여 같으면 true, 다르면 false

• changed : 값을 기준으로 비교했을 때 유지된 값의 index가 바뀐 경우 세팅

  • [ [prevListIndex, newListIndex] ]

• added : 기존 리스트와 변경된 리스트를 비교했을 때 추가된 원소의 index (newList의 index를 바라본다)

• removed : 기존 리스트와 변경된 리스트를 비교했을 때 삭제된 원소의 index (prevList의 index를 바라본다)

[sebride4988]

changedBeforeAdded: [ [ 1, 0 ], [ 0, 1 ], [ 2, 2 ] ]