• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 }