There is an ArrayList with objects, say, Item . Each object has a field Long id , Long parentId and List subitems , where the same Item objects lie, or else it is empty. It is necessary to go through the list, find such an Item that is a subitem of an Item that is already on the same list, and delete such subitem.

The unpleasant limitation is Java 7 + Guava, since the streams on Android were not delivered.

  • Are items sorted by equality by reference, by id or through equals ? - Nofate ♦
  • And what is the difficulty? We create a collection storing items. Recursively go around the tree to check if this item is in the collection. If not, then add and go on, if there is - delete. - GreyGoblin
  • @Nofate by id . - Bringoff
  • @GreyGoblin complexity to make it nice and smart. - Bringoff
  • @Bringoff with the structure that you described, if there are no more conditions on which you can limit the search for existing objects faster than O (n) will not work. That is the usual linear bypass. And the beauty is realized by recursion. - GreyGoblin

1 answer 1

At the moment, came to this decision, but not sure that it is optimal

  /** * Checks if subitem's ancestor is presented in the same list and if so removes that subitem from list * * @param items list to search in (subitems must be updated {@see updateSubItems}) * @return new list with redundant subitems removed. */ public List<Item> removeSubItemsIfParentPresented(List<Item> items) { List<Item> result = new ArrayList<>(items); // iterate items, but pass and modify result for (Item item : items) { clearListFromRedundantSubitemsRecursively(result, item.getSubItems()); } return result; } /** * This method modifies input list, be careful. * * @param listToClear * @param subitemsToSearch */ private void clearListFromRedundantSubitemsRecursively(List<Item> listToClear, List<Item> subitemsToSearch) { Iterator<Item> iterator = listToClear.iterator(); while (iterator.hasNext()) { Item current = iterator.next(); for (Item subitem : subitemsToSearch) { if (!subitem.getSubItems().isEmpty()) { clearListFromRedundantSubitemsRecursively(listToClear, subitem.getSubItems()); } if (subitem.getId() == current.getId()) { iterator.remove(); } } } }