1 package org.unicode.cldr.util; 2 3 import java.util.ArrayList; 4 import java.util.Arrays; 5 import java.util.Collection; 6 import java.util.Iterator; 7 import java.util.LinkedHashMap; 8 import java.util.LinkedHashSet; 9 import java.util.List; 10 import java.util.Map; 11 import java.util.Set; 12 13 public class MergeLists<T> { 14 15 Collection<Collection<T>> source = new ArrayList<>(); 16 Set<T> orderedWorkingSet; 17 MergeLists()18 public MergeLists() { 19 this(new LinkedHashSet<T>()); 20 } 21 MergeLists(Set<T> orderedWorkingSet)22 public MergeLists(Set<T> orderedWorkingSet) { 23 this.orderedWorkingSet = orderedWorkingSet; 24 } 25 add(Collection<T> orderedItems)26 public MergeLists<T> add(Collection<T> orderedItems) { 27 if (orderedItems.size() == 0) { // skip empties 28 return this; 29 } 30 final LinkedHashSet<T> linkedHashSet = new LinkedHashSet<>(orderedItems); 31 if (linkedHashSet.size() != orderedItems.size()) { 32 throw new IllegalArgumentException("Multiple items in ordering!"); 33 } 34 source.add(linkedHashSet); 35 return this; 36 } 37 38 @SuppressWarnings("unchecked") add(T... stuff)39 public MergeLists<T> add(T... stuff) { 40 return add(Arrays.asList(stuff)); 41 } 42 addAll(Collection<Collection<T>> collectionsOfOrderedItems)43 public MergeLists<T> addAll(Collection<Collection<T>> collectionsOfOrderedItems) { 44 for (Collection<T> orderedItems : collectionsOfOrderedItems) { 45 add(orderedItems); 46 } 47 return this; 48 } 49 merge()50 public List<T> merge() { 51 List<T> result = new ArrayList<>(); 52 53 for (Collection<T> sublist : source) { 54 orderedWorkingSet.addAll(sublist); 55 } 56 57 // now that we have things ordered, we take the first one that is only at the front of a 58 // list 59 // this is slower, but puts things into as much of the order specified as possible 60 // could be optimized further, but we don't care that much 61 62 Set<T> first = new LinkedHashSet<>(); 63 while (orderedWorkingSet.size() != 0) { 64 getFirsts(first); 65 if (first.size() == 0) { 66 Map<T, Collection<T>> reasons = new LinkedHashMap<>(); 67 getFirsts(first, reasons); 68 throw new IllegalArgumentException( 69 "Inconsistent requested ordering: cannot merge if we have [...A...B...] and [...B...A...]: " 70 + reasons); 71 } 72 // now get first item that is in first 73 T best = extractFirstOk(orderedWorkingSet, first); // removes from working set 74 // remaining items now contains no non-first items 75 removeFromSource(best); 76 result.add(best); 77 } 78 return result; 79 } 80 hasConsistentOrder(Collection<T> a, Collection<T> b)81 public static <T> boolean hasConsistentOrder(Collection<T> a, Collection<T> b) { 82 LinkedHashSet<T> remainder = new LinkedHashSet<>(a); 83 remainder.retainAll(b); 84 if (remainder.size() == 0) { 85 return true; 86 } 87 // remainder is now in a's order, and contains only the items that are in both 88 Iterator<T> bi = b.iterator(); 89 T current = bi.next(); 90 for (T item : remainder) { 91 if (item.equals(current)) { 92 if (!bi.hasNext()) { 93 return true; 94 } 95 current = bi.next(); 96 } 97 } 98 return !bi.hasNext(); // if we have any left over, we failed 99 } 100 hasConsistentOrderWithEachOf( Collection<T> a, Collection<Collection<T>> bs)101 public static <T> Collection<T> hasConsistentOrderWithEachOf( 102 Collection<T> a, Collection<Collection<T>> bs) { 103 for (Collection<T> b : bs) { 104 if (!hasConsistentOrder(a, b)) { 105 return b; 106 } 107 } 108 return null; 109 } 110 111 // could be optimized since we know the item will only occur at the head of a list removeFromSource(T item)112 private void removeFromSource(T item) { 113 for (Iterator<Collection<T>> iterator = source.iterator(); iterator.hasNext(); ) { 114 Collection<T> sublist = iterator.next(); 115 sublist.remove(item); 116 if (sublist.size() == 0) { 117 iterator.remove(); 118 } 119 } 120 } 121 122 /** Get the first item that is also in the ok set. */ extractFirstOk(Collection<T> remainingItems, Set<T> ok)123 private T extractFirstOk(Collection<T> remainingItems, Set<T> ok) { 124 for (Iterator<T> it = remainingItems.iterator(); it.hasNext(); ) { 125 T item = it.next(); 126 if (ok.contains(item)) { 127 it.remove(); 128 return item; 129 } 130 } 131 throw new IllegalArgumentException("Internal Error"); 132 } 133 getFirsts(Set<T> result)134 public void getFirsts(Set<T> result) { 135 getFirsts(result, null); 136 } 137 138 /** Get first of each sets. Guaranteed non-empty */ getFirsts(Set<T> result, Map<T, Collection<T>> reasons)139 public void getFirsts(Set<T> result, Map<T, Collection<T>> reasons) { 140 result.clear(); 141 result.addAll(orderedWorkingSet); 142 for (Collection<T> sublist : source) { 143 // get all the first items 144 final Iterator<T> iterator = sublist.iterator(); 145 iterator.next(); // skip first 146 while (iterator.hasNext()) { 147 final T nextItem = iterator.next(); 148 boolean changed = result.remove(nextItem); 149 if (changed && reasons != null) { 150 reasons.put(nextItem, sublist); 151 } 152 } 153 } 154 } 155 } 156