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<Collection<T>>(); 16 Set<T> orderedWorkingSet; 17 18 public MergeLists() { 19 this(new LinkedHashSet<T>()); 20 } 21 22 public MergeLists(Set<T> orderedWorkingSet) { 23 this.orderedWorkingSet = orderedWorkingSet; 24 } 25 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<T>(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") 39 public MergeLists<T> add(T... stuff) { 40 return add(Arrays.asList(stuff)); 41 } 42 43 public MergeLists<T> addAll(Collection<Collection<T>> collectionsOfOrderedItems) { 44 for (Collection<T> orderedItems : collectionsOfOrderedItems) { 45 add(orderedItems); 46 } 47 return this; 48 } 49 50 public List<T> merge() { 51 List<T> result = new ArrayList<T>(); 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 list 58 // this is slower, but puts things into as much of the order specified as possible 59 // could be optimized further, but we don't care that much 60 61 Set<T> first = new LinkedHashSet<T>(); 62 while (orderedWorkingSet.size() != 0) { 63 getFirsts(first); 64 if (first.size() == 0) { 65 Map<T, Collection<T>> reasons = new LinkedHashMap<T, Collection<T>>(); 66 getFirsts(first, reasons); 67 throw new IllegalArgumentException( 68 "Inconsistent requested ordering: cannot merge if we have [...A...B...] and [...B...A...]: " 69 + reasons); 70 } 71 // now get first item that is in first 72 T best = extractFirstOk(orderedWorkingSet, first); // removes from working set 73 // remaining items now contains no non-first items 74 removeFromSource(best); 75 result.add(best); 76 } 77 return result; 78 } 79 80 public static <T> boolean hasConsistentOrder(Collection<T> a, Collection<T> b) { 81 LinkedHashSet<T> remainder = new LinkedHashSet<T>(a); 82 remainder.retainAll(b); 83 if (remainder.size() == 0) { 84 return true; 85 } 86 // remainder is now in a's order, and contains only the items that are in both 87 Iterator<T> bi = b.iterator(); 88 T current = bi.next(); 89 for (T item : remainder) { 90 if (item.equals(current)) { 91 if (!bi.hasNext()) { 92 return true; 93 } 94 current = bi.next(); 95 } 96 } 97 return !bi.hasNext(); // if we have any left over, we failed 98 } 99 100 public static <T> Collection<T> hasConsistentOrderWithEachOf(Collection<T> a, Collection<Collection<T>> bs) { 101 for (Collection<T> b : bs) { 102 if (!hasConsistentOrder(a, b)) { 103 return b; 104 } 105 } 106 return null; 107 } 108 109 // could be optimized since we know the item will only occur at the head of a list 110 private void removeFromSource(T item) { 111 for (Iterator<Collection<T>> iterator = source.iterator(); iterator.hasNext();) { 112 Collection<T> sublist = iterator.next(); 113 sublist.remove(item); 114 if (sublist.size() == 0) { 115 iterator.remove(); 116 } 117 } 118 } 119 120 /** 121 * Get the first item that is also in the ok set. 122 */ 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 134 public void getFirsts(Set<T> result) { 135 getFirsts(result, null); 136 } 137 138 /** 139 * Get first of each sets. Guaranteed non-empty 140 */ 141 public void getFirsts(Set<T> result, Map<T, Collection<T>> reasons) { 142 result.clear(); 143 result.addAll(orderedWorkingSet); 144 for (Collection<T> sublist : source) { 145 // get all the first items 146 final Iterator<T> iterator = sublist.iterator(); 147 iterator.next(); // skip first 148 while (iterator.hasNext()) { 149 final T nextItem = iterator.next(); 150 boolean changed = result.remove(nextItem); 151 if (changed && reasons != null) { 152 reasons.put(nextItem, sublist); 153 } 154 } 155 } 156 } 157 } 158
