Как можно оптимизировать получение списка дочерних элементов "дерева"

Question

Есть дерево вида

Как можно получить список дочерних элементов по какому-то элементу (Передали в ф-цию "a", а получили массив из [b,c,d,e,f,g]. Передали "b" получили [e,f]) Элемент имеет идентификатор родителя, а так же является ли он "контейнером"

 protected void fetchChildElements(Elem parentElem, List<Elem> childElems, List<Elem> allElem) {
        for (Elem childElem : allElem) {
            String parentElemId = childElem.getParentElemId();
            if (parentElemId != null && parentElemId.equals(parentElem.getId())) {
                if (childElem.getElemCategory() == DeviceCategory.CONTAINER) {
                    fetchChildElements(childElem, childElems, allElem);
                }
                childElems.add(childElem);
            }
        }
    }

Answer 1

Ну например так.

Давайте построим отображение элемента в его родителя. Это можно сделать один раз, и обновлять таблицу при каждом изменении дерева. Или просто использовать вместо функции String getParentElemId() функцию Elem getParentElem().

Получится вот что:

Map<String, String> mapToParent = 
    Arrays.stream(allElements)
          //.collect(Collectors.toMap(Elem::getId, Elem::getParentId)); // WTF Java?
          .collect(HashMap::new,
                   (m, elem) -> m.put(elem.getId(), elem.getParentId()),
                   HashMap::putAll);

Теперь чтобы проверить каждый элемент, достаточно пройтись по цепочке родителей, и искать в ней нужное:

String rootId = "b";
Arrays.stream(allElements)
      .filter(elem -> {
          String curr = elem.getId();
          while (curr != null && !curr.equals(rootId)) curr = mapToParent.get(curr);
          return curr != null; })
      .forEach(elem -> System.out.println(elem.getValue()));

БЛОГ НА HUSL

Как можно оптимизировать получение списка дочерних элементов "дерева"

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