1 package org.unicode.cldr.unittest;
2 
3 import java.util.Arrays;
4 import java.util.Comparator;
5 import java.util.HashSet;
6 import java.util.LinkedHashSet;
7 import java.util.Random;
8 import java.util.Set;
9 import java.util.TreeSet;
10 
11 import org.unicode.cldr.util.DiscreteComparator;
12 import org.unicode.cldr.util.DiscreteComparator.Builder;
13 import org.unicode.cldr.util.DiscreteComparator.CycleException;
14 import org.unicode.cldr.util.DiscreteComparator.MissingItemException;
15 import org.unicode.cldr.util.DiscreteComparator.Ordering;
16 import org.unicode.cldr.util.DtdType;
17 import org.unicode.cldr.util.ElementAttributeInfo;
18 
19 import com.ibm.icu.dev.test.TestFmwk;
20 import com.ibm.icu.impl.Relation;
21 import com.ibm.icu.impl.Row;
22 import com.ibm.icu.impl.Row.R2;
23 
24 /**
25  * Tests the ordering of DTD elements and attributes within the dtd files.
26  */
27 public class TestComparisonBuilder extends TestFmwk {
main(String[] args)28     public static void main(String[] args) {
29         new TestComparisonBuilder().run(args);
30     }
31 
verifyOrdering(DiscreteComparator<String> comp, Set<String> children)32     private void verifyOrdering(DiscreteComparator<String> comp,
33         Set<String> children) {
34         String last = null;
35         for (String child : children) {
36             if (last != null) {
37                 int compare = comp.compare(last, child);
38                 if (compare != -1) {
39                     errln("Elements not ordered:\t" + last + ", " + child
40                         + "; in " + children);
41                     break;
42                 }
43             }
44             last = child;
45         }
46     }
47 
dtdAttributes()48     private void dtdAttributes() {
49         // NOTE: This method was originally TestDtdAttributes. It's been
50         // disabled
51         // because DTD attributes aren't managed
52         // by FindDtdOrder, which leads to a lot of ordering cycles being found.
53         // There's no point in reordering the dtd contents to make this test
54         // pass
55         // unless FindDtdOrder also checks attributes.
56         Builder<String> builder = new Builder<String>(Ordering.NATURAL);
57         for (DtdType dtd : DtdType.values()) {
58             Relation<String, String> eaInfo = ElementAttributeInfo.getInstance(
59                 dtd).getElement2Attributes();
60             for (String element : eaInfo.keySet()) {
61                 Set<String> attributes = eaInfo.getAll(element);
62                 if (attributes.size() == 0)
63                     continue;
64                 // logln(dtd + ": " + element + ": " + attributes);
65                 builder.add(attributes);
66             }
67 
68         }
69         DiscreteComparator<String> comp;
70         try {
71             comp = builder.get();
72         } catch (CycleException e) {
73             errln(e.getMessage() + ",\t" + builder.getCycle());
74             throw e;
75         }
76 
77         logln("Attribute Ordering:\t" + comp.getOrdering().toString());
78         for (DtdType dtd : DtdType.values()) {
79             // check that the ordering is right
80             Relation<String, String> eaInfo = ElementAttributeInfo.getInstance(
81                 dtd).getElement2Attributes();
82             for (String element : eaInfo.keySet()) {
83                 Set<String> children = eaInfo.getAll(element);
84                 verifyOrdering(comp, children);
85             }
86         }
87     }
88 
TestDtdElements()89     public void TestDtdElements() {
90         Set<String> specials = new HashSet<String>(Arrays.asList(new String[] {
91             "EMPTY", "PCDATA", "ANY" }));
92         for (DtdType dtd : DtdType.values()) {
93             if (dtd.rootType != dtd) {
94                 continue;
95             }
96             Builder<String> builder = new Builder<String>(Ordering.NATURAL);
97             builder.add(dtd.toString());
98             Relation<String, String> eaInfo = ElementAttributeInfo.getInstance(
99                 dtd).getElement2Children();
100             for (String element : eaInfo.keySet()) {
101                 Set<String> children = new LinkedHashSet<String>(
102                     eaInfo.getAll(element));
103                 children.removeAll(specials);
104                 if (children.size() == 0)
105                     continue;
106                 logln(dtd + ": " + element + ": " + children);
107                 builder.add(children);
108             }
109 
110             DiscreteComparator<String> comp = builder.get();
111             logln("Element Ordering: " + comp.getOrdering().toString());
112 
113             Relation<String, String> eaInfo2 = ElementAttributeInfo.getInstance(
114                 dtd).getElement2Children();
115             // check that the ordering is right
116             for (String element : eaInfo2.keySet()) {
117                 Set<String> elements = eaInfo2.getAll(element);
118                 Set<String> children = new LinkedHashSet<String>(elements);
119                 children.removeAll(specials);
120                 verifyOrdering(comp, children);
121             }
122             // check that all can be ordered
123             try {
124                 Set<String> items = new TreeSet<String>(comp);
125                 items.addAll(eaInfo2.keySet()); // we'll get exception if it
126                 // fails
127             } catch (Exception e) {
128                 Set<String> missing = new LinkedHashSet<String>(eaInfo2.keySet());
129                 missing.removeAll(comp.getOrdering());
130                 errln(dtd + "\t" + e.getClass().getName() + "\t"
131                     + e.getMessage() + ";\tMissing: " + missing);
132             }
133         }
134     }
135 
TestMonkey()136     public void TestMonkey() {
137         Random random = new Random(1);
138         Set<R2<Integer, Integer>> soFar = new HashSet<R2<Integer, Integer>>();
139         for (int j = 0; j < 100; ++j) {
140             int itemCount = 50;
141             int linkCount = 1000;
142             buildNodes(random, soFar, random.nextInt(itemCount - 1) + 1,
143                 random.nextInt(linkCount));
144 
145             for (Ordering order : Ordering.values()) {
146                 Builder<Integer> builder = new Builder<Integer>(order);
147                 for (R2<Integer, Integer> pair : soFar) {
148                     builder.add(pair.get0(), pair.get1());
149                 }
150                 logln(builder.toString());
151                 DiscreteComparator<Integer> comp = builder.get();
152                 logln("\t" + comp);
153 
154                 for (R2<Integer, Integer> pair : soFar) {
155                     int value = comp.compare(pair.get0(), pair.get1());
156                     if (value >= 0) {
157                         errln("Failure with " + pair);
158                     }
159                 }
160             }
161         }
162     }
163 
buildNodes(Random random, Set<R2<Integer, Integer>> soFar, int items, int links)164     private void buildNodes(Random random, Set<R2<Integer, Integer>> soFar,
165         int items, int links) {
166         soFar.clear();
167         for (int i = 0; i < links; ++i) {
168             Integer start = random.nextInt(items);
169             Integer end = random.nextInt(10);
170             if (start.intValue() <= end.intValue())
171                 continue;
172             soFar.add(Row.of(start, end));
173         }
174     }
175 
TestCycle3()176     public void TestCycle3() {
177         for (Ordering order : Ordering.values()) {
178             Builder<String> builder = new Builder<String>(order);
179             builder.add("c", "a");
180             builder.add("a", "b");
181             builder.add("b", "c");
182             mustHaveException(builder);
183         }
184     }
185 
TestCycle7()186     public void TestCycle7() {
187         for (Ordering order : Ordering.values()) {
188             Builder<String> builder = new Builder<String>(order);
189             builder.add("f", "a");
190             builder.add("a", "b");
191             builder.add("b", "c");
192             builder.add("b", "q");
193             builder.add("c", "d");
194             builder.add("d", "e");
195             builder.add("e", "f");
196             mustHaveException(builder);
197         }
198     }
199 
TestCycle2()200     public void TestCycle2() {
201         for (Ordering order : Ordering.values()) {
202             Builder<String> builder = new Builder<String>(order);
203             try {
204                 builder.add("c", "d");
205                 builder.add("d", "e");
206                 builder.add("e", "f");
207                 builder.add("b", "b");
208                 DiscreteComparator<String> comp = builder.get();
209             } catch (CycleException e) {
210                 logln("Expected cycle and got one at:\t" + e.getMessage()
211                     + ", " + builder.getCycle());
212                 return;
213             }
214             throw new IllegalArgumentException(
215                 "Failed to generate CycleException");
216         }
217     }
218 
TestFallback()219     public void TestFallback() {
220         for (Ordering order : Ordering.values()) {
221             DiscreteComparator<String> comp = new Builder<String>(order)
222                 .add("a", "b", "c", "d").add("a", "m", "n").get();
223             logln("Ordering " + comp.getOrdering());
224             expectException(comp, "a", "a1");
225             expectException(comp, "a1", "b");
226             expectException(comp, "a1", "a2");
227         }
228     }
229 
expectException(DiscreteComparator<String> comp, String a, String b)230     private void expectException(DiscreteComparator<String> comp, String a,
231         String b) {
232         try {
233             comp.compare(a, b);
234         } catch (MissingItemException e) {
235             logln("Expected missing item and got one at:\t" + e.getMessage());
236             return;
237         }
238         throw new IllegalArgumentException("Failed to generate CycleException");
239     }
240 
TestFallback2()241     public void TestFallback2() {
242         for (Ordering order : Ordering.values()) {
243             Builder<String> builder = new Builder<String>(order);
244             builder.setFallbackComparator(new Comparator<String>() {
245                 @Override
246                 public int compare(String o1, String o2) {
247                     return o1.compareTo(o2);
248                 }
249             });
250             builder.add("a", "b");
251             builder.add("b", "c");
252             builder.add("b", "d");
253             DiscreteComparator<String> comp = builder.get();
254             int result = comp.compare("a", "a1");
255             if (result != -1)
256                 errln("a >= a1");
257             result = comp.compare("b", "a1");
258             if (result != -1)
259                 errln("a1 >= b");
260             result = comp.compare("a1", "a2");
261             if (result != -1)
262                 errln("a1 >= a2");
263         }
264     }
265 
mustHaveException(Builder<T> builder)266     private <T> void mustHaveException(Builder<T> builder) {
267         try {
268             logln(builder.toString());
269             DiscreteComparator<T> comp = builder.get();
270         } catch (CycleException e) {
271             logln("Expected cycle and got one at:\t" + e.getMessage() + ",\t"
272                 + builder.getCycle());
273             return;
274         }
275         throw new IllegalArgumentException("Failed to generate CycleException");
276     }
277 }
278