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