Глубокое копирование объекта без использования рекурсии, JSON.parse \ stringify, structuredClone()

Question

Как реализовать глубокое копирование без использования рекурсии, JSON.parse, JSON.stringify, structuredClone(), lodash и другие готовые решения. Необходимо реализовать свой собственный алгоритм. Глубина дерева может очень глубокой, типы данных в значениях могут быть разные.

const data1 = {
  a: 10,
  y: null,
  k: [1, 2],
  b: 3,
  c: {
    d: 4,
    e: {
      w: 50,
      u: undefined,
      s: {
        f: {
          v: 5,
        },
      },
    },
  },
};

const data2 = [
{
  a: 10,
  y: null,
  k: [1, 2],
  b: 3,
  c: {
    d: 4,
    e: {
      w: 50,
      u: undefined,
      s: {
        f: {
          v: 5,
        },
      },
    },
  },
};
];

В моем примере не получается пройтись по всем ключам, я останавливаюсь на втором цикле.

function deepCopy(dataType) {
  const copy = {};
  let data = dataType;

  if (Array.isArray(data)) {
    data = dataType[0];
  }

  for (const [key, value] of Object.entries(data)) {
    if (typeof data[key] === "object") {
      copy[key] = Array.isArray(data[key]) ? [] : value;
      for (let deepKey in data[key]) {
        copy[key][deepKey] = data[key][deepKey];
      }
    } else {
      copy[key] = data[key];
    }
  }
  return copy;
}

Можем ли мы реализовать данный алгоритм используя стек ?

Answer 1

Что бы упростить решение, создадим объект object сразу, а в стек поместим записи [object, key, value], каждая из которых означает: обработай значение value и помести его в object[key]. Обработка состоит в определении типа объекта - скаляр, массив или словарь. Скаляры записываются по адресу без изменений. Для массивов и словарей по адресу записываются пустые контейнеры, а все их будущие элементы кладутся в стек.

Очередь подошла бы лучше чем стек, но в языке нет нормальной очереди. А так как у нас стек, обратите внимание на то что ключи словарей кладутся в стек задом наперёд. Иначе стек вставит ключи в обратном порядке. Формально этот будет тот же словарь, но выглядит это плохо. Поэтому reverse(). Для массива этот трюк не нужен, массив всегда перебирается по увеличению индексов. Цикл по массиву разреженный. Если массив был с пропусками, его копия будет такой же.

Обратите внимание что клоны объектов верхнего уровня создаются сразу, а затем редактируются задним числом. Это не соответствует естественному рекурсивному решению, не является его механическим переводом, но так итеративный код проще.

const kindOf = v => {
    if (
        v === null ||
        v === undefined ||
        [
            'bigint',
            'boolean',
            'function',
            'number',
            'string',
            'symbol'
        ].includes(typeof v)
    ) {
        return 'scalar';
    }
    return (Array.isArray(v)) ? 'array' : 'object';
};

const clone = value => {
    const result = [];
    const stack = [[result, 0, value]];
    while (stack.length > 0) {
        let clone;
        const [target, key, value] = stack.pop();
        switch (kindOf(value)) {
        case 'scalar':
            clone = value;
            break;
        case 'array':
            clone = [];
            value.forEach((item, index) =>
                stack.push([clone, index, item])
            );
            break;
        case 'object':
            clone = {};
            for (const [k, v] of Object.entries(value).reverse()) {
                stack.push([clone, k, v])
            }
            break;
        }
        target[key] = clone;
    }
    return result[0];
};

console.log(clone({
  a: 10,
  y: null,
  k: [1, 2],
  b: 3,
  c: {
    d: 4,
    e: { w: 50, u: undefined, s: { f: { v: 5 } } }
  }
}));

console.log(clone([{
  a: 10,
  y: null,
  k: [1, 2],
  b: 3,
  c: {
    d: 4,
    e: { w: 50, u: undefined, s: { f: { v: 5 } } }
  }
}]));

БЛОГ НА HUSL

Глубокое копирование объекта без использования рекурсии, JSON.parse \ stringify, structuredClone()

Ответы (1 шт):