Как рекурсивно добавлять дочерние объекты в родительские объекты по ключу

Question

У меня есть плоская структура объектов, которая показывает, какие объекты имеют родителей, а какие нет. Сейчас я нахожусь в точке, где мне нужно отформатировать ее в правильной структуре, чтобы я мог просматривать ее и выполнять функции.

Просто добавлю, прежде чем углубляться в детали ... Я знаю, что структура объектов не согласована, я все еще работаю над тем, чтобы все отдельные элементы были согласованы. Наиболее важной частью является то, что дети ориентированы на родителей.

Я искал в Интернете, но, похоже, не смог найти ничего, что точно соответствовало бы моим нуждам. Структура, хорошая или плохая, это то, с чем я застрял.

Я возился с этим кодом, который делает цикл и добавляет дочерние элементы к соответствующему родительскому элементу и удаляет старый ключ. Я забыл о рекурсии и не могу обернуться, делая это ... в данном конкретном случае.

var tree = hierarchy.tree, key;
for (key in tree) {
  if (tree.hasOwnProperty(key)) tree[key].children = {};
}
iterate();
return tree;

function iterate() {
  var field, node;
  for (field in tree) {
    if (tree.hasOwnProperty(field)) {
      node = tree[field];
      if (node.parent !== undefined) {
        tree[node.parent].children[field] = node;
        delete tree[field];
      }
    }
  }
}

Это базовая структура:

var tree = {
  "submit": {
    "order": 0,
    "field": "submit"
  },
  "hc3qu2nf4": {
    "label": "title",
    "parent": "",
    "order": 0,
    "field": "title",
    "options": {
      "Font Size": "25px",
      "Font Weight": "Bold",
      "Font Style": "Italic",
      "Color": "rgb(64, 128, 128)"
    }
  },
  "dhthivju9": {
    "label": "divider",
    "parent": "",
    "order": 1,
    "field": "divider",
    "options": {
      "height": "14px",
      "color": "#21ce09",
      "width": "50%"
    }
  },
  "z5o9m7sgx": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 0,
    "field": "col"
  },
  "85ugwci2c": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 1,
    "field": "col"
  },
  "4hhsi94n7": {
    "label": "column",
    "parent": "",
    "order": 2,
    "field": "column"
  },
  "sbf0bg1o7": {
    "label": "month",
    "parent": "z5o9m7sgx",
    "order": 0,
    "field": "month",
    "options": {
      "start": "2019-04"
    },
    "required": true
  },
  "c3bwnyjmg": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 2
  },
  "n5m9d84dg": {
    "label": "number",
    "parent": "85ugwci2c",
    "order": 0,
    "field": "number",
    "options": {
      "start": "5",
      "min": "5",
      "max": "10",
      "step": "2"
    }
  },
  "krfxfnzsr": {
    "label": "date",
    "parent": "c3bwnyjmg",
    "order": 0,
    "field": "date",
    "options": {
      "start": "2019-05-03"
    }
  }
}

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

{
  "submit": {
    "order": 0,
    "field": "submit"
  },
  "hc3qu2nf4": {
    "label": "title",
    "parent": "",
    "order": 0,
    "field": "title",
    "options": {
      "Font Size": "25px",
      "Font Weight": "Bold",
      "Font Style": "Italic",
      "Color": "rgb(64, 128, 128)"
    }
  },
  "dhthivju9": {
    "label": "divider",
    "parent": "",
    "order": 1,
    "field": "divider",
    "options": {
      "height": "14px",
      "color": "#21ce09",
      "width": "50%"
    }
  },
  "4hhsi94n7": {
    "label": "column",
    "parent": "",
    "order": 2,
    "field": "column",
    "children": {
      "z5o9m7sgx": {
        "label": "",
        "order": 0,
        "field": "col",
        "children": {
          "sbf0bg1o7": {
            "label": "month",
            "parent": "z5o9m7sgx",
            "order": 0,
            "field": "month",
            "options": {
              "start": "2019-04"
            },
            "required": true
          }
        }
      },
      "85ugwci2c": {
        "label": "",
        "order": 1,
        "field": "col",
        "children": {
          "n5m9d84dg": {
            "label": "number",
            "parent": "85ugwci2c",
            "order": 0,
            "field": "number",
            "options": {
              "start": "5",
              "min": "5",
              "max": "10",
              "step": "2"
            }
          }
        }
      },
      "c3bwnyjmg": {
        "label": "",
        "order": 2,
        "children": {
          "krfxfnzsr": {
            "label": "date",
            "parent": "c3bwnyjmg",
            "order": 0,
            "field": "date",
            "options": {
              "start": "2019-05-03"
            }
          }
        }
      }
    }
  }
}

Кроме того, было бы здорово, если бы я мог поддерживать соответствующий «порядок» каждого элемента, чтобы они сортировались соответствующим образом.

---

UPDATE Я не женат на структуре вывода. Если у кого-то есть идея получше, пожалуйста, дайте мне знать.

Answer 1

В приведенном ниже примере сохраняется тип Object вместо переключения на Array. Смотрите встроенные комментарии для более подробной информации. Основная концепция состоит в том, чтобы рассматривать само дерево как основную ветвь и выполнять итерацию по ветвям до тех пор, пока не будет найден родительский объект, к которому можно переставить дочерний элемент.

//iterating through an object/array that's changing can cause unexpected results
//iterate through a duplicate that will not change
let tree = {
    "submit": {
      "order": 0,
      "field": "submit"
    },
    "hc3qu2nf4": {
      "label": "title",
      "parent": "",
      "order": 0,
      "field": "title",
      "options": {
        "Font Size": "25px",
        "Font Weight": "Bold",
        "Font Style": "Italic",
        "Color": "rgb(64, 128, 128)"
      }
    },
    "dhthivju9": {
      "label": "divider",
      "parent": "",
      "order": 1,
      "field": "divider",
      "options": {
        "height": "14px",
        "color": "#21ce09",
        "width": "50%"
      }
    },
    "z5o9m7sgx": {
      "label": "",
      "parent": "4hhsi94n7",
      "order": 0,
      "field": "col"
    },
    "85ugwci2c": {
      "label": "",
      "parent": "4hhsi94n7",
      "order": 1,
      "field": "col"
    },
    "4hhsi94n7": {
      "label": "column",
      "parent": "",
      "order": 2,
      "field": "column"
    },
    "sbf0bg1o7": {
      "label": "month",
      "parent": "z5o9m7sgx",
      "order": 0,
      "field": "month",
      "options": {
        "start": "2019-04"
      },
      "required": true
    },
    "c3bwnyjmg": {
      "label": "",
      "parent": "4hhsi94n7",
      "order": 2
    },
    "n5m9d84dg": {
      "label": "number",
      "parent": "85ugwci2c",
      "order": 0,
      "field": "number",
      "options": {
        "start": "5",
        "min": "5",
        "max": "10",
        "step": "2"
      }
    },
    "krfxfnzsr": {
      "label": "date",
      "parent": "c3bwnyjmg",
      "order": 0,
      "field": "date",
      "options": {
        "start": "2019-05-03"
      }
    }
  },
  tree2 = JSON.parse(JSON.stringify(tree)); //clone, not reference

console.log(tree === tree2); //test to confirm duplicate is not a reference

function reposition_child(parent, child, node, branch) {
  //check if the parent exists in this branch
  if (branch.hasOwnProperty(parent)) {
    let bp = branch[parent];
    //create children object as needed
    if (!bp.hasOwnProperty('children')) {
      bp.children = {};
    }
    //transplant the node as a child
    bp.children[child] = node;
    return true;
  } else {
    //iterate through the branches with children looking for the parent
    let found = false;
    for (let sub_branch in branch) {
      if (branch[sub_branch].hasOwnProperty('children')) {
        found = reposition_child(parent, child, node, branch[sub_branch].children);
      }
      //exit the loop once the parent is found
      if (found) {
        return true;
      }
    }
  }
  return false;
}

//iterate through the tree (duplicate fixed version)
for (let node in tree2) {
  let tn = tree2[node];
  //reposition nodes that have a non-empty parent
  if (tn.hasOwnProperty('parent') && tn.parent.length) {
    reposition_child(tn.parent, node, tn, tree);
    delete tree[node];
  }
}

//cleanup and output
delete tree2;
console.log(tree);

Answer 2

Я нашел это решение, но оно использует массивы вместо объектов (для find, reduce, splice, push и т. Д.), Поэтому итоговый результат не совсем то, что вы хотели, но вынаписал, это не было установлено в камне.

const data = {
  "submit": {
    "order": 0,
    "field": "submit"
  },
  "hc3qu2nf4": {
    "label": "title",
    "parent": "",
    "order": 0,
    "field": "title",
    "options": {
      "Font Size": "25px",
      "Font Weight": "Bold",
      "Font Style": "Italic",
      "Color": "rgb(64, 128, 128)"
    }
  },
  "dhthivju9": {
    "label": "divider",
    "parent": "",
    "order": 1,
    "field": "divider",
    "options": {
      "height": "14px",
      "color": "#21ce09",
      "width": "50%"
    }
  },
  "z5o9m7sgx": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 0,
    "field": "col"
  },
  "85ugwci2c": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 1,
    "field": "col"
  },
  "4hhsi94n7": {
    "label": "column",
    "parent": "",
    "order": 2,
    "field": "column"
  },
  "sbf0bg1o7": {
    "label": "month",
    "parent": "z5o9m7sgx",
    "order": 0,
    "field": "month",
    "options": {
      "start": "2019-04"
    },
    "required": true
  },
  "c3bwnyjmg": {
    "label": "",
    "parent": "4hhsi94n7",
    "order": 2
  },
  "n5m9d84dg": {
    "label": "number",
    "parent": "85ugwci2c",
    "order": 0,
    "field": "number",
    "options": {
      "start": "5",
      "min": "5",
      "max": "10",
      "step": "2"
    }
  },
  "krfxfnzsr": {
    "label": "date",
    "parent": "c3bwnyjmg",
    "order": 0,
    "field": "date",
    "options": {
      "start": "2019-05-03"
    }
  }
};

function sortArray(orderedArray, remainingArray) {
  if(remainingArray.length === 0) {
    return orderedArray;
  }
  else {
    remainingArray.forEach((remainingItem, index) => {
      if(orderedArray.find(x => x.identifier === remainingItem.parent)) {
        orderedArray.push(remainingItem);
        remainingArray.splice(index, 1);
      }
    });
    return sortArray(orderedArray, remainingArray);
  }
}

function insertNode(tree, node) {
  if(!tree) return;
  let item = tree.find(x => x.identifier === node.parent);
  if(item) {
    (item.children || (item.children = [])).push(node);
  } else {
    tree.forEach(x => {
      insertNode(x.children, node);
    });
  }
  return tree;
}

function createTree(data) {
  let tempArray = [];

  for (let key in data) {
    tempArray.push({ ...data[key], identifier: key });
  }
  
  tempArray = sortArray(tempArray.filter(x => !x.parent), tempArray.filter(x => x.parent));

  return tempArray.reduce((accumulator, currentValue) => {
    if(currentValue.parent === "") {
      accumulator.push(currentValue);
    } else {
      insertNode(accumulator, currentValue);
    }
    return accumulator;
  }, []);
}

console.log(createTree(data));