SortUtils { public static <T> List<T> sort(Collection<T> objects, Visitor<T> visitor) throws IllegalNodeConfigException, CircularReferencesException { if (objects.size() == 0) { return Collections.emptyList(); } final Map<String, Node<T>> nodes = new LinkedHashMap<String, Node<T>>(); for (T obj : objects) { String name = visitor.getName(obj); Node<T> node = new Node<T>(name, obj, visitor.afterOthers(obj), visitor.beforeOthers(obj), visitor.getAfterNames(obj), visitor.getBeforeNames(obj)); if (node.beforeOthers && node.afterOthers) { throw new IllegalNodeConfigException(name, "Before others and after others could not be configured at the sametime "); } nodes.put(name, node); } for (Node<T> node : nodes.values()) { if (node.after.contains(node.name)) { throw new IllegalNodeConfigException(node.name, "The fragment could not be configured to after itself"); } for (String afterNodeName : node.after) { Node<T> afterNode = nodes.get(afterNodeName); if (afterNode != null) { node.dependOns.add(afterNode); } } if (node.before.contains(node.name)) { throw new IllegalNodeConfigException(node.name, "The fragment could not be configured to before itself"); } for (String beforeNodeName : node.before) { Node<T> beforeNode = nodes.get(beforeNodeName); if (beforeNode != null) { beforeNode.dependOns.add(node); } } } boolean circuitFounded = false; for (Node<T> node : nodes.values()) { Set<Node<T>> visitedNodes = new HashSet<Node<T>>(); if (!normalizeNodeReferences(node, node, visitedNodes)) { circuitFounded = true; break; } node.dependOns.addAll(visitedNodes); } if (circuitFounded) { Set<Circuit<T>> circuits = new LinkedHashSet<Circuit<T>>(); for (Node<T> node : nodes.values()) { findCircuits(circuits, node, new java.util.Stack<Node<T>>()); } ArrayList<Circuit<T>> list = new ArrayList<Circuit<T>>(circuits); Collections.sort(list); List<List> all = new ArrayList<List>(); for (Circuit circuit : list) { all.add(unwrap(circuit.nodes)); } throw new CircularReferencesException(all); } Node<T> rootNode = new Node<T>(); rootNode.previous = rootNode; rootNode.next = nodes.values().iterator().next(); for (Node<T> node : nodes.values()) { node.previous = rootNode.previous; rootNode.previous.next = node; node.next = rootNode; rootNode.previous = node; } Node<T> lastBeforeNode = rootNode; for (Node<T> node : nodes.values()) { if (node.beforeOthers) { moveAfter(node, lastBeforeNode); lastBeforeNode = node; } else if (node.afterOthers) { moveBefore(node, rootNode); } } for (Node<T> node : nodes.values()) { for (Node<T> reference : node.dependOns) { swap(node, reference, rootNode); } } List<T> sortedList = new ArrayList<T>(nodes.size()); Node<T> currentNode = rootNode.next; while (currentNode != rootNode) { sortedList.add(currentNode.object); currentNode = currentNode.next; } return sortedList; }  static List<T> sort(Collection<T> objects, Visitor<T> visitor);  }
@Test public void testFragmentSortA() throws Exception { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 6; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } List<String> sortedList = SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { if (t.equals("A") || t.equals("C")) { return true; } return false; } @Override public boolean beforeOthers(String t) { if (t.equals("B") || t.equals("F")) { return true; } return false; } @Override public List<String> getAfterNames(String t) { if (t.equals("A")) { return Arrays.asList("C"); } return Collections.emptyList(); } @Override public List<String> getBeforeNames(String t) { if (t.equals("F")) { return Arrays.asList("B"); } return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); Assert.assertEquals(Arrays.asList("F", "B", "D", "E", "C", "A"), sortedList); }
@Test public void testFragmentSortB() throws Exception { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 6; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } List<String> sortedList = SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { if (t.equals("A") || t.equals("D")) { return true; } return false; } @Override public boolean beforeOthers(String t) { if (t.equals("B") || t.equals("E")) { return true; } return false; } @Override public List<String> getAfterNames(String t) { return Collections.emptyList(); } @Override public List<String> getBeforeNames(String t) { if (t.equals("A")) { return Arrays.asList("C"); } return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); Assert.assertEquals(Arrays.asList("B", "E", "F", "A", "C", "D"), sortedList); }
@Test public void testFragmentSortC() throws Exception { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 4; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } List<String> sortedList = SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { return t.equals("A"); } @Override public boolean beforeOthers(String t) { return t.equals("C"); } @Override public List<String> getAfterNames(String t) { return Collections.emptyList(); } @Override public List<String> getBeforeNames(String t) { return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); Assert.assertEquals(Arrays.asList("C", "B", "D", "A"), sortedList); }
@Test public void testBothAfterAndBeforeOthers() { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 2; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } Exception actualException = null; try { SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { return t.equals("A"); } @Override public boolean beforeOthers(String t) { return t.equals("A"); } @Override public List<String> getAfterNames(String t) { return Collections.emptyList(); } @Override public List<String> getBeforeNames(String t) { return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); } catch (IllegalNodeConfigException e) { actualException = e; } catch (CircularReferencesException e) { Assert.fail("Should not get CircularReference Exception here"); } Assert.assertNotNull("Should get an IllegalNodeConfigException", actualException); }
@Test public void testBeforeOrAfterItselfException() { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 2; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } IllegalNodeConfigException actualException = null; try { SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { return false; } @Override public boolean beforeOthers(String t) { return false; } @Override public List<String> getAfterNames(String t) { if (t.equals("A")) { return Arrays.asList("A"); } else { return Collections.emptyList(); } } @Override public List<String> getBeforeNames(String t) { return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); } catch (IllegalNodeConfigException e) { actualException = e; } catch (CircularReferencesException e) { Assert.fail("Should not get CircularReferencesException here"); } Assert.assertNotNull("Should get an IllegalNodeConfigException", actualException); }
@Test public void testCircularReferenceExceptionA() { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 2; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } CircularReferencesException actualException = null; try { SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { return false; } @Override public boolean beforeOthers(String t) { return false; } @Override public List<String> getAfterNames(String t) { if (t.equals("A")) { return Arrays.asList("B"); } else { return Collections.emptyList(); } } @Override public List<String> getBeforeNames(String t) { if (t.equals("A")) { return Arrays.asList("B"); } else { return Collections.emptyList(); } } @Override public String getName(String t) { return t; } }); } catch (IllegalNodeConfigException e) { Assert.fail("Should not get IllegalNodeConfigException here"); } catch (CircularReferencesException e) { actualException = e; } Assert.assertNotNull("Should get an CircularReferencesException", actualException); }
@Test public void testCircularReferenceExceptionB() { List<String> fragmentList = new ArrayList<String>(); for (int i = 0; i < 3; i++) { fragmentList.add(String.valueOf((char) ('A' + i))); } Exception actualException = null; try { SortUtils.sort(fragmentList, new Visitor<String>() { @Override public boolean afterOthers(String t) { return false; } @Override public boolean beforeOthers(String t) { return false; } @Override public List<String> getAfterNames(String t) { if (t.equals("A")) { return Arrays.asList("B"); } else if (t.equals("B")) { return Arrays.asList("C"); } else if (t.equals("C")) { return Arrays.asList("A"); } return Collections.emptyList(); } @Override public List<String> getBeforeNames(String t) { return Collections.emptyList(); } @Override public String getName(String t) { return t; } }); } catch (IllegalNodeConfigException e) { Assert.fail("Should not get IllegalNodeConfigException here"); } catch (CircularReferencesException e) { actualException = e; } Assert.assertNotNull("Should get an CircularReferencesException", actualException); }