1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.healthmarketscience.jackcess.impl;
18
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.Collections;
22 import java.util.HashMap;
23 import java.util.List;
24 import java.util.Map;
25
26 import junit.framework.TestCase;
27
28
29
30
31
32 public class TopoSorterTest extends TestCase
33 {
34
35 public TopoSorterTest(String name) {
36 super(name);
37 }
38
39 public void testTopoSort() throws Exception
40 {
41 doTopoTest(Arrays.asList("A", "B", "C"),
42 Arrays.asList("A", "B", "C"));
43
44 doTopoTest(Arrays.asList("B", "A", "C"),
45 Arrays.asList("A", "B", "C"),
46 "B", "C",
47 "A", "B");
48
49 try {
50 doTopoTest(Arrays.asList("B", "A", "C"),
51 Arrays.asList("C", "B", "A"),
52 "B", "C",
53 "A", "B",
54 "C", "A");
55 fail("IllegalStateException should have been thrown");
56 } catch(IllegalStateException expected) {
57
58 assertTrue(expected.getMessage().startsWith("Cycle"));
59 }
60
61 try {
62 doTopoTest(Arrays.asList("B", "A", "C"),
63 Arrays.asList("C", "B", "A"),
64 "B", "D");
65 fail("IllegalStateException should have been thrown");
66 } catch(IllegalStateException expected) {
67
68 assertTrue(expected.getMessage().startsWith("Unknown descendent"));
69 }
70
71 doTopoTest(Arrays.asList("B", "D", "A", "C"),
72 Arrays.asList("D", "A", "B", "C"),
73 "B", "C",
74 "A", "B");
75
76 doTopoTest(Arrays.asList("B", "D", "A", "C"),
77 Arrays.asList("A", "D", "B", "C"),
78 "B", "C",
79 "A", "B",
80 "A", "D");
81
82 doTopoTest(Arrays.asList("B", "D", "A", "C"),
83 Arrays.asList("D", "A", "C", "B"),
84 "D", "A",
85 "C", "B");
86
87 doTopoTest(Arrays.asList("B", "D", "A", "C"),
88 Arrays.asList("D", "C", "A", "B"),
89 "D", "A",
90 "C", "B",
91 "C", "A");
92
93 doTopoTest(Arrays.asList("B", "D", "A", "C"),
94 Arrays.asList("C", "D", "A", "B"),
95 "D", "A",
96 "C", "B",
97 "C", "D");
98
99 doTopoTest(Arrays.asList("B", "D", "A", "C"),
100 Arrays.asList("D", "A", "C", "B"),
101 "D", "A",
102 "C", "B",
103 "D", "B");
104 }
105
106 private static void doTopoTest(List<String> original,
107 List<String> expected,
108 String... descs) {
109
110 List<String> values = new ArrayList<String>();
111 values.addAll(original);
112
113 TestTopoSorter tsorter = new TestTopoSorter(values, false);
114 for(int i = 0; i < descs.length; i+=2) {
115 tsorter.addDescendents(descs[i], descs[i+1]);
116 }
117
118 tsorter.sort();
119
120 assertEquals(expected, values);
121
122
123 values = new ArrayList<String>();
124 values.addAll(original);
125
126 tsorter = new TestTopoSorter(values, true);
127 for(int i = 0; i < descs.length; i+=2) {
128 tsorter.addDescendents(descs[i], descs[i+1]);
129 }
130
131 tsorter.sort();
132
133 List<String> expectedReverse = new ArrayList<String>(expected);
134 Collections.reverse(expectedReverse);
135
136 assertEquals(expectedReverse, values);
137 }
138
139 private static class TestTopoSorter extends TopoSorter<String>
140 {
141 private final Map<String,List<String>> _descMap =
142 new HashMap<String,List<String>>();
143
144 protected TestTopoSorter(List<String> values, boolean reverse) {
145 super(values, reverse);
146 }
147
148 public void addDescendents(String from, String... tos) {
149 List<String> descs = _descMap.get(from);
150 if(descs == null) {
151 descs = new ArrayList<String>();
152 _descMap.put(from, descs);
153 }
154
155 descs.addAll(Arrays.asList(tos));
156 }
157
158 @Override
159 protected void getDescendents(String from, List<String> descendents) {
160 List<String> descs = _descMap.get(from);
161 if(descs != null) {
162 descendents.addAll(descs);
163 }
164 }
165 }
166 }