fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.HashSet;
  4. import java.util.Iterator;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.ListIterator;
  8. import java.util.Map;
  9. import java.util.Objects;
  10. import java.util.PriorityQueue;
  11. import java.util.Set;
  12. import java.util.stream.Collectors;
  13. import java.util.stream.Stream;
  14.  
  15. class Ideone
  16. {
  17. 	private static final class ListManager<ValueType extends Comparable<ValueType>> {
  18. 	    private static final class ParentChildrenWrapper<ValueType> {
  19. 	        private final ValueType parent;
  20. 	        private final Set<ValueType> childrenByReference;
  21.  
  22. 	        public ParentChildrenWrapper(ValueType parent, Set<ValueType> childrenByReference) {
  23. 				this.parent = parent;
  24. 				this.childrenByReference = childrenByReference;
  25. 	        }
  26.  
  27. 	        public ValueType getParent() {
  28. 	            return this.parent;
  29. 	        }
  30.  
  31. 	        public Set<ValueType> getChildrenByReference() {
  32. 	            return this.childrenByReference;
  33. 	        }
  34. 	    }
  35.  
  36. 	    private static final class QueuedItem<ValueType> implements Comparable<QueuedItem<ValueType>> {
  37. 	        private final ValueType item;
  38. 	        private final int index;
  39.  
  40. 	        public QueuedItem(ValueType item, int index) {
  41. 	            this.item = item;
  42. 	            this.index = index;
  43. 	        }
  44.  
  45. 	        public ValueType getItem() {
  46. 	            return this.item;
  47. 	        }
  48.  
  49. 	        public int getIndex() {
  50. 	            return this.index;
  51. 	        }
  52.  
  53. 	        @Override
  54. 	        public int compareTo(QueuedItem<ValueType> other) {
  55. 	            if (this.index < other.index) {
  56. 	                return -1;
  57. 	            } else if (this.index > other.index) {
  58. 	                return 1;
  59. 	            } else {
  60. 	                return 0;
  61. 	            }
  62. 	        }
  63. 	    }
  64.  
  65. 		private final Set<ValueType> unsortedItems;
  66. 	    private final Map<ValueType, Set<ValueType>> dependentsOfParents;
  67.  
  68. 	    public ListManager() {
  69. 			this.unsortedItems = new HashSet<>();
  70. 	        this.dependentsOfParents = new HashMap<>();
  71. 	    }
  72.  
  73. 	    public void addItem(ValueType value) {
  74. 			this.unsortedItems.add(value);
  75. 	    }
  76.  
  77. 	    public final void registerDependency(ValueType parent, ValueType child) {
  78. 	        if (!this.unsortedItems.contains(parent)) {
  79. 	            throw new IllegalArgumentException("Unrecognized parent");
  80. 	        } else if (!this.unsortedItems.contains(child)) {
  81. 	            throw new IllegalArgumentException("Unrecognized child");
  82. 	        } else if (Objects.equals(parent,child)) {
  83. 	            throw new IllegalArgumentException("Parent and child are the same");
  84. 	        } else {
  85. 	            this.dependentsOfParents.computeIfAbsent(parent, __ -> new HashSet<>()).add(child);
  86. 	        }
  87. 	    }
  88.  
  89. 	    public List<ValueType> createSortedList() {
  90. 	        // Create a copy of dependentsOfParents where the sets of children can be modified without impacting the original.
  91. 	        // These sets will representing the set of children for each parent that are yet to be dealt with, and such sets will shrink as more items are processed.
  92. 	        Map<ValueType, Set<ValueType>> blockingDependentsOfParents = new HashMap<>(this.dependentsOfParents.size());
  93. 	        for (Map.Entry<ValueType, Set<ValueType>> parentEntry : this.dependentsOfParents.entrySet()) {
  94. 	            Set<ValueType> childrenOfParent = parentEntry.getValue();
  95. 	            if (childrenOfParent != null && !childrenOfParent.isEmpty()) {
  96. 	                blockingDependentsOfParents.put(parentEntry.getKey(), new HashSet<>(childrenOfParent));
  97. 	            }
  98. 	        }
  99.  
  100. 	        // Compute a list of which children impact which parents, alongside the set of children belonging to each parent.
  101. 	        // This will allow a child to remove itself from all of it's parents' lists of blocking children.
  102. 	        Map<ValueType,List<ParentChildrenWrapper<ValueType>>> childImpacts = new HashMap<>();
  103. 	        for (Map.Entry<ValueType, Set<ValueType>> entry : blockingDependentsOfParents.entrySet()) {
  104. 	            ValueType parent = entry.getKey();
  105. 	            Set<ValueType> childrenForParent = entry.getValue();
  106. 	            ParentChildrenWrapper<ValueType> childrenForParentWrapped = new ParentChildrenWrapper<>(parent,childrenForParent);
  107. 	            for (ValueType child : childrenForParent) {
  108. 	                childImpacts.computeIfAbsent(child, __ -> new LinkedList<>()).add(childrenForParentWrapped);
  109. 	            }
  110. 	        }
  111.  
  112. 	        // If there are no relationships, the remaining code can be massively optimised.
  113. 	        boolean hasNoRelationships = blockingDependentsOfParents.isEmpty();
  114.  
  115. 	        // Create a pre-sorted stream of items.
  116. 	        Stream<ValueType> rankedItemStream = this.unsortedItems.stream().sorted();
  117. 	        List<ValueType> outputList;
  118. 	        if (hasNoRelationships) {
  119. 	            // There are no relationships, and as such, the stream is already in a perfectly fine order.
  120. 	            outputList = rankedItemStream.collect(Collectors.toList());
  121. 	        } else {
  122. 	            Iterator<ValueType> rankedIterator = rankedItemStream.iterator();
  123.  
  124. 	            int queueIndex = 0;
  125. 	            outputList = new ArrayList<>(this.unsortedItems.size());
  126.  
  127. 	            // A collection of items that have been visited but are blocked by children, stored in map form for easy deletion.
  128. 	            Map<ValueType,QueuedItem<ValueType>> lockedItems = new HashMap<>();
  129. 	            // A list of items that have been freed from their blocking children, but have yet to be processed, ordered by order originally encountered.
  130. 	            PriorityQueue<QueuedItem<ValueType>> freedItems = new PriorityQueue<>();
  131.  
  132. 	            while (true) {
  133. 	                // Grab the earliest-seen item which was once locked but has now been freed. Otherwise, grab the next unseen item.
  134. 	                ValueType item;
  135. 	                boolean mustBeUnblocked;
  136. 	                QueuedItem<ValueType> queuedItem = freedItems.poll();
  137. 	                if (queuedItem == null) {
  138. 	                    if (rankedIterator.hasNext()) {
  139. 	                        item = rankedIterator.next();
  140. 	                        mustBeUnblocked = false;
  141. 	                    } else {
  142. 	                        break;
  143. 	                    }
  144. 	                } else {
  145. 	                    item = queuedItem.getItem();
  146. 	                    mustBeUnblocked = true;
  147. 	                }
  148.  
  149. 	                // See if this item has any children that are blocking it from being added to the output list.
  150. 	                Set<ValueType> childrenWaitingUpon = blockingDependentsOfParents.get(item);
  151. 	                if (childrenWaitingUpon == null || childrenWaitingUpon.isEmpty()) {
  152. 	                    // There are no children blocking this item, so start removing it from all blocking lists.
  153.  
  154. 	                    // Get a list of all parents that is item was blocking, if there are any.
  155. 	                    List<ParentChildrenWrapper<ValueType>> childImpact = childImpacts.get(item);
  156. 	                    if (childImpact != null) {
  157. 	                        // Iterate over all those parents
  158. 	                        ListIterator<ParentChildrenWrapper<ValueType>> childImpactIterator = childImpact.listIterator();
  159. 	                        while (childImpactIterator.hasNext()) {
  160. 	                            // Remove this item from that parent's blocking children.
  161. 	                            ParentChildrenWrapper<ValueType> wrappedParentImpactedByChild = childImpactIterator.next();
  162. 	                            Set<ValueType> childrenOfParentImpactedByChild = wrappedParentImpactedByChild.getChildrenByReference();
  163. 	                            childrenOfParentImpactedByChild.remove(item);
  164.  
  165. 	                            // Does this parent no longer have any children blocking it?
  166. 	                            if (childrenOfParentImpactedByChild.isEmpty()) {
  167. 	                                // Remove it from the children impacts map, to prevent unnecessary processing of a now empty set in future iterations.
  168. 	                                childImpactIterator.remove();
  169.  
  170. 	                                // If this parent was locked, mark it as now freed.
  171. 	                                QueuedItem<ValueType> freedQueuedItem = lockedItems.remove(wrappedParentImpactedByChild.getParent());
  172. 	                                if (freedQueuedItem != null) {
  173. 	                                    freedItems.add(freedQueuedItem);
  174. 	                                }
  175. 	                            }
  176. 	                        }
  177. 	                        // If there are no longer any parents at all being blocked by this child, remove it from the map.
  178. 	                        if (childImpact.isEmpty()) {
  179. 	                            childImpacts.remove(item);
  180. 	                        }
  181. 	                    }
  182. 	                    outputList.add(item);
  183. 	                } else if (mustBeUnblocked) {
  184. 	                    throw new IllegalStateException("Freed item is still blocked. This should not happen.");
  185. 	                } else {
  186. 	                    // Mark the item as locked.
  187. 	                    lockedItems.put(item,new QueuedItem<>(item,queueIndex++));
  188. 	                }
  189. 	            }
  190.  
  191. 	            // Check that all items were processed successfully. Given there is only one path that will add an item to to the output list without an exception, we can just compare sizes.
  192. 	            if (outputList.size() != this.unsortedItems.size()) {
  193. 	                throw new IllegalStateException("Could not complete ordering. Are there recursive chains of items?");
  194. 	            }
  195. 	        }
  196. 	        return outputList;
  197. 	    }
  198. 	}
  199.  
  200. 	private static class MyObj implements Comparable<MyObj> {
  201. 		private final char identifier;
  202. 		private final int value;
  203.  
  204. 		public MyObj(char identifier, int value) {
  205. 			this.identifier = identifier;
  206. 			this.value = value;
  207. 		}
  208.  
  209. 		public int getValue() {
  210. 			return this.value;
  211. 		}
  212.  
  213. 		@Override
  214. 		public String toString() {
  215. 			return "{" + this.identifier + ',' + this.value + '}';
  216. 		}
  217.  
  218. 		@Override
  219. 		public int compareTo(MyObj other) {
  220. 			if (this.value < other.value) {
  221. 				return -1;
  222. 			} else if (this.value > other.value) {
  223. 				return 1;
  224. 			} else {
  225. 				return 0;
  226. 			}
  227. 		}
  228. 	}
  229.  
  230. 	public static void main (String[] args)
  231. 	{
  232. 		MyObj a = new MyObj('a',6);
  233. 		MyObj b = new MyObj('b',1);
  234. 		MyObj c = new MyObj('c',5);
  235. 		MyObj d = new MyObj('d',15);
  236. 		MyObj e = new MyObj('e',12);
  237. 		MyObj f = new MyObj('f',20);
  238. 		MyObj g = new MyObj('g',14);
  239. 		MyObj h	= new MyObj('h',7);
  240.  
  241. 		ListManager<MyObj> listManager = new ListManager<>();
  242. 		listManager.addItem(a);
  243. 		listManager.addItem(b);
  244. 		listManager.addItem(c);
  245. 		listManager.addItem(d);
  246. 		listManager.addItem(e);
  247. 		listManager.addItem(f);
  248. 		listManager.addItem(g);
  249. 		listManager.addItem(h);
  250.  
  251. 		System.out.println(listManager.createSortedList());
  252.  
  253. 		listManager.registerDependency(a,e);
  254. 		listManager.registerDependency(g,d);
  255. 		listManager.registerDependency(c,b);
  256.  
  257. 		System.out.println(listManager.createSortedList());
  258. 	}
  259. }
Success #stdin #stdout 0.15s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[{b,1}, {c,5}, {a,6}, {h,7}, {e,12}, {g,14}, {d,15}, {f,20}]
[{b,1}, {c,5}, {h,7}, {e,12}, {a,6}, {d,15}, {g,14}, {f,20}]
https://ideone.com/XrhSeA
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!