1 package org.unicode.cldr.unittest; 2 3 import com.google.common.base.Joiner; 4 import com.google.common.collect.ImmutableList; 5 import java.util.ArrayList; 6 import java.util.Arrays; 7 import java.util.LinkedHashSet; 8 import java.util.List; 9 10 /** Build a total order from a partial order. TODO optimize! */ 11 public class TotalOrderBuilder<T> { 12 private boolean DEBUG = true; 13 private LinkedHashSet<List<T>> rows = new LinkedHashSet<>(); 14 static final List<String> TEST = ImmutableList.of("meter", "kilogram"); 15 add(List<T> items)16 public TotalOrderBuilder<T> add(List<T> items) { 17 if (TEST.equals(items)) { 18 int debug = 0; 19 } 20 LinkedHashSet<T> rowCheck = new LinkedHashSet<>(items); 21 if (rowCheck.size() != items.size()) { 22 throw new IllegalArgumentException("Duplicate items in input"); 23 } 24 if (!items.isEmpty()) { 25 rows.add(new ArrayList<>(items)); 26 } 27 return this; 28 } 29 add(T... items)30 public TotalOrderBuilder<T> add(T... items) { 31 return add(Arrays.asList(items)); 32 } 33 build()34 public List<T> build() { 35 List<T> result = new ArrayList<>(); 36 // whenever a first item in a row is not in any other row (other than first position) put it 37 // into the result, and remove 38 main: 39 while (true) { 40 boolean failed = false; 41 if (rows.size() == 6) { 42 int debug = 0; 43 } 44 45 for (List<T> row : rows) { 46 if (row.isEmpty()) { 47 continue; 48 } 49 T first = row.iterator().next(); 50 if (inNonFirstPosition(first)) { 51 failed = true; 52 continue; 53 } 54 // got through the gauntlet 55 if (DEBUG) { 56 System.out.println("Removing " + first); 57 } 58 result.add(first); 59 removeFromRows(first); 60 failed = false; 61 continue main; 62 } 63 if (failed) { 64 final String items = toString(); 65 rows.clear(); 66 throw new IllegalArgumentException("incompatible orderings, eg:\n" + items); 67 } 68 rows.clear(); 69 return result; 70 } 71 } 72 removeFromRows(T first)73 private void removeFromRows(T first) { 74 for (List<T> row : rows) { 75 if (DEBUG && row.contains("kilogram")) { 76 int debug = 0; 77 } 78 row.remove(first); 79 } 80 rows = new LinkedHashSet<>(rows); // consolidate 81 } 82 inNonFirstPosition(T item)83 private boolean inNonFirstPosition(T item) { 84 for (List<T> row : rows) { 85 if (DEBUG && row.contains("kilogram")) { 86 int debug = 0; 87 } 88 if (!row.isEmpty() && row.contains(item) && !row.iterator().next().equals(item)) { 89 return true; 90 } 91 } 92 return false; 93 } 94 95 @Override toString()96 public String toString() { 97 return Joiner.on('\n').join(new LinkedHashSet<>(rows)); 98 } 99 } 100