Advertisement
Guest User

Untitled

a guest
May 23rd, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.34 KB | None | 0 0
  1. public List<Item> dfResolve(Map<String, Item> allItems) {
  2.       int itemCount = allItems.size();
  3.       final List<Item> resolved = new ArrayList<Item>(itemCount);
  4.       final Set<Item> processed = new HashSet<Item>(itemCount);
  5.       final Set<Item> visited = new HashSet<Item>();
  6.  
  7.       for(Item item : allItems.values()) {
  8.          resolve(item, allItems, processed, visited, resolved);
  9.          visited.clear();
  10.       }
  11.       if(resolved.size() < itemCount)
  12.          throw new RuntimeException("Unresolved dependencies");
  13.  
  14.       return resolved;
  15.    }
  16.  
  17.    public void resolve(final Item item, final Map<String, Item> allItems, final Set<Item> processed, final Set<Item> visited, final List<Item> resolved) {
  18.       if(visited.contains(item))
  19.             throw new RuntimeException("Circular dependency discovered: " + visited);
  20.       visited.add(item);
  21.  
  22.       if(!processed.contains(item)) {
  23.  
  24.          processed.add(item);
  25.          for(String dep : item.getDependencies()) {
  26.             Item depItem = allItems.get(dep);
  27.             if(depItem == null)
  28.                throw new RuntimeException("Unresolved dependency: " + item.getName() + " depends on " + dep + " which can not be found");
  29.             resolve(depItem, allItems, processed, visited, resolved);
  30.          }
  31.          resolved.add(item);
  32.       }
  33.  
  34.       visited.remove(item);
  35.    }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement