Найти глубину объекта итеративным способом

Question

Я пишу функцию для расчета глубины объекта.

Вот моя рекурсивная версия, которая, кажется, работает должным образом:

function findDepth(obj, firstCall = true) {
  if (firstCall && typeof obj !== "object") {
    return -1;
  }
  return Object.keys(obj).reduce((max, k) => {
    if (typeof obj[k] === "object" && obj[k] !== null) {
      const val = findDepth(obj[k], false) + 1;
      if (val > max) {
        max = val;
      }
    }
    return max;
  }, 1);
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepth(input1));
console.log(findDepth(input2));

Сейчас я пытаюсь написать итеративную версию, но не могу найти лучший способ заставить цикл работать.

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }
  let max = 1;
  let copy = Object.assign({}, obj);
  let keys = Object.keys(copy);
  while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }
  return max;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

Как видно из вывода и кода, он просто принимает первое свойство внутри цикла:

while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }

Идея состояла в том, чтобы удалитьсвойство каждой итерации, но я не получаю в правильном направлении.Я попытался изменить его с помощью copy[keys[keys.length - 1]], но вместо этого он принимает только последнее свойство.На самом деле проблема в том, как перебрать все ключи на всех уровнях глубины, как в рекурсивной версии.

Есть предложения о том, как реализовать этот алгоритм итеративным способом?

Даже любые предложения о том, как улучшить рекурсивный вариант (или, если я что-то упустил), более чем приветствуются.

ps НЕТ ЗАГРУЗКИ, ПОДДЕРЖКИ, РАМДА или чего-либо еще.Просто Ваниль JS

Answer 1

Вам просто нужно держать стек и толкать в него дочерние элементы, отслеживая текущую глубину.Вы можете отслеживать это, помещая массив [depth, obj] в стек, а затем, когда вы pop() добавляете единицу в глубину, прежде чем помещать дочерние элементы.

const input1  = {w: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk",q: {w: {z: "dsajkdasjdla"}}},h: "dsiaodsiad"}},a: "test",b: "test2",c: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk"},h: "dsiaodsiad"}},e: "bye"};
  
  
function findDepthIterative(obj) {
    if (typeof obj !== "object") {
      return -1;
    }
    let max = 0;
    // current depth, children
    let stack = [[0, Object.values(obj)]];
    
    while(stack.length){
        let [depth, cur] = stack.pop()
        if (depth > max) max = depth

        if (typeof cur === "object" && cur !== null){
            Object.values(cur).forEach(c => stack.push([depth+1, c]))     
        }
    }
    return max
  }
  

console.log(findDepthIterative(input1))

// sanity check:
const depth0 = {}
const depth1 = {a:1}
const depth2 = {a:{b:2}}

console.log(findDepthIterative(depth0))
console.log(findDepthIterative(depth1))
console.log(findDepthIterative(depth2))

Answer 2

Вы должны использовать массив вместо объекта, который не будет работать должным образом, если есть дубликаты ключей.Массив должен содержать все объекты, которые встречаются на определенном уровне.Для каждой итерации вы отображаете массив в новый, содержащий прямые дочерние элементы предыдущих объектов:

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];                                          // the array containing the objects that occur at a certain level, initially contains obj being the only object at the first level
  let levels = 0;                                           // levels counter

  do {                                                      // keep doing this
    levels++;                                               // increment the levels counter

    let newArr = [];                                        // make a new array for the next level
    arr.forEach(obj => {                                    // populate it with the old level objects' children
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;                                          // make arr the new array of object (next level)
  } while (arr.length);                                    // while there are still levels with objects in them

  return levels;
}

Демо:

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];
  let levels = 0;

  do {
    levels++;
    
    let newArr = [];
    arr.forEach(obj => {
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;
  } while (arr.length);

  return levels;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

Answer 3

Одним из способов итерации может быть поиск в глубину с использованием стека.

function f(obj){
  let stack = Object.keys(obj).map(k => [obj[k], 1]);
  let max = 0;

  while (stack.length){
    let [maybeObj, d] = stack.pop();
    max = Math.max(max, d);
    if (typeof maybeObj == 'object' && maybeObj !== null)
      Object.keys(maybeObj).map(k =>
        stack.push([maybeObj[k], d + 1]));
  }

  return max;
}

Мы также можем сделать рекурсию несколько более краткой:

function f(obj){
  if (typeof obj !== 'object' || obj === null)
    return 0;

  return Object.keys(obj).reduce((acc, k) => 
    Math.max(acc, 1 + f(obj[k])), 0);
}