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