bkjang / digging-open-source

🔍 Digging Open Source!!

digging-open-source's Issues

removedCount, addedCount, removedMap 없이 chagedBeforeAdded를 구현할 수 없을까? (feat.성환)

• utils.ts

import {IResult, IMapInteface} from '../types';
import HashMap from './Map/HashMap';
import PolyMap from './Map/PolyMap';

export function getMapInstance(
  findKeyCallback: any
): IMapInteface<any, number> {
  if (typeof Map === 'function') {
    return new Map();
  }
  if (findKeyCallback) {
    return new HashMap();
  }
  return new PolyMap();
}

export function diff<T>(
  prevList: T[],
  newList: T[],
  findKeyCallback?: (e: T, i: number, arr: T[]) => any // 왜 반환타입이 any일까?
): IResult<T> {
  const prevKeyMap: IMapInteface<any, number> = getMapInstance(findKeyCallback); // mapClass를 꼭 따로 저장해야할까?
  const newKeyMap: IMapInteface<any, number> = getMapInstance(findKeyCallback);
  const remainedKeyMap: IMapInteface<any, number> = getMapInstance(
    findKeyCallback
  );
  const defaultCallback = findKeyCallback || ((e: T) => e);
  const prevKeys = prevList.map(defaultCallback);
  const newKeys = newList.map(defaultCallback);
  const maintained: number[][] = [];
  const fixed: boolean[] = [];
  const changed: number[][] = [];
  const added: number[] = [];
  const removed: number[] = [];
  const remained: number[] = [];

  // 1. Setting prevKeyMap, newKeyMap
  prevKeys.forEach((key, index): void => {
    prevKeyMap.set(key, index);
  });

  newKeys.forEach((key, index): void => {
    newKeyMap.set(key, index);
  });

  // 2. Setting removed and removedMap
  prevKeys.forEach((key, prevListIndex): void => {
    const newListIndex = newKeyMap.get(key);

    if (typeof newListIndex === undefined) {
      removed.push(prevListIndex);
    } else {
      remainedKeyMap.set(prevListIndex, key);
      remained.push(prevListIndex);
    }
  });

  // 3. Setting maintained, changed, fixed, added, changeBeforeAdded
  newKeys.forEach((key, newListIndex): void => {
    const prevListIndex = prevKeyMap.get(key);

    if (typeof prevListIndex === undefined) {
      added.push(newListIndex);
    } else {
      maintained.push([prevListIndex, newListIndex]);
      fixed.push(prevListIndex === newListIndex);
      if (prevListIndex !== newListIndex) {
        changed.push([prevListIndex, newListIndex]);
      }
    }
  });

  const remainedKeyList = remained.map(item => {
    return remainedKeyMap.get(item);
  });

  const maintainedKeyList = maintained.map(item => {
    return prevKeys[item[0]];
  });

  const changedBeforeAdded = maintainedKeyList.map(item => {
    return [remainedKeyList.indexOf(item), maintainedKeyList.indexOf(item)];
  });

  removed.reverse(); 
  return {
    prevList,
    newList,
    added,
    removed,
    changed,
    maintained,
    changedBeforeAdded,
  };
}

utils - function diff

/*
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

@eg.js/list-differ clone coding

Reference

• Introduction
• docs
• github

HashMap과 PolyMap의 차이?

• 왜 findKeyCallback이 들어오면 HashMap을 쓰고 아니면 PolyMap을 쓸까?
• findKeyCallback을 왜 써야할까?