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 
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<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")
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<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 
hasConsistentOrder(Collection<T> a, Collection<T> b)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 
hasConsistentOrderWithEachOf(Collection<T> a, Collection<Collection<T>> bs)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
removeFromSource(T item)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      */
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     /**
139      * Get first of each sets. Guaranteed non-empty
140      */
getFirsts(Set<T> result, Map<T, Collection<T>> reasons)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