Deep copy object with Depth-First Search

Tags: , ,



I trying to copy an object. I want to made it with algorithm Depth-First Search.

function dfs(data) {
  let stack = [];
  let res = {};

  for (let key in data) {
    stack.push({ data: data[key], keyData: key });

    while (stack.length !== 0) {
      const first = stack.shift();

      if (typeof first.data === "object") {
        for (let key in first.data) {
          if (typeof first.data[key] === "object") {
            stack.push({ data: first.data[key], keyData: key });
          } else {
            res[first.parentKey] = first.keyData;
          }
        }
      } else {
        res[first.keyData] = first.data;
      }
    }
  }

  return res;
}

const data = {
  a: 1,
  b: 2,
  c: {
    d: 3,
    g: {
      e: 4,
      r: {
        y: 5,
      },
    },
  },
};

const newData = dfs(data);

data.c.g.e = 5000;
data.c.g.d = 90000;

console.log("Original data", data);
console.log("Copied data", newData);

I create a function which will be copy my object without links on old objects. I have a problem, my function doesn’t count the result correctly. Where do i make a mistake?

Answer

dfs without recursion use additional stack to track parent properties.

    function dfs(data) {
        let stack = [];
        let stackres = [];
        let res = {};
    
        for (let key in data) {
            stack.push({ data: data[key], keyData: key });
            stackres.push(res);
    
    
            while (stack.length !== 0) {
                const first = stack.shift();
                const cur = stackres.shift();
    
                if (typeof first.data === "object") {
                    cur[first.keyData] = {};
                    for (let key in first.data) {
                        if (typeof first.data[key] === "object") {
                            stack.push({ data: first.data[key], keyData: key });
                            stackres.push(cur[first.keyData]);
                        } else {
                            cur[first.keyData][key] = first.data[key];
                        }
                    }
                } else {
                    cur[first.keyData] = first.data;
                }
            }
        }
    
        return res;
    }
    const data = {
      a: 1,
      b: 2,
      c: {
        d: 3,
        g: {
          e: 4,
          r: {
            y: 5,
          },
        },
      },
    };
    const newData = dfs(data);
    
    data.c.g.e = 5000;
    data.c.g.d = 90000;
    
    console.log("Original data", data);
    console.log("Copied data", newData);


Source: stackoverflow