Source code: com/port80/graph/dot/impl/GridHeap_Test01.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.Arrays;
8 import java.util.HashMap;
9 import java.util.Map;
10
11 import junit.framework.Assert;
12 import junit.framework.TestCase;
13 import junit.framework.TestSuite;
14
15 import com.port80.util.Debug;
16 import com.port80.util.msg;
17 import com.port80.util.sprint;
18 import com.port80.util.struct.FloatList;
19
20 /**
21 * @author chrisl
22 *
23 * To change this generated comment edit the template variable "typecomment":
24 * Window>Preferences>Java>Templates.
25 * To enable and disable the creation of type comments go to
26 * Window>Preferences>Java>Code Generation.
27 */
28 public class GridHeap_Test01 extends TestCase {
29
30 ////////////////////////////////////////////////////////////////////////
31
32 private static boolean VERBOSE = false;
33 private static boolean CHECK = true;
34
35 private static Map opts = new HashMap();
36
37 // Test ////////////////////////////////////////////////////////////////
38 //
39
40 public static void main(String[] args) {
41 args = msg.getArgs(opts, "GridHeap_01", args, "- verbose=v nocheck=c");
42 if (opts.get("verbose") != null) {
43 Debug.enable("verbose");
44 VERBOSE = true;
45 }
46 if (opts.get("nocheck") != null) {
47 CHECK = false;
48 }
49 junit.textui.TestRunner.run(new TestSuite(GridHeap_Test01.class));
50 }
51
52 ////////////////////////////////////////////////////////////////////////
53
54 public GridHeap_Test01(String name) {
55 super(name);
56 }
57
58 ////////////////////////////////////////////////////////////////////////
59
60 /**
61 * sanityCheck() test.
62 * . enqueue and dequeue a random array.
63 */
64 public void test1() {
65
66 final int SIZE = 100;
67 final int MAXVALUE = 100;
68 final int[] data = new int[SIZE];
69
70 if (VERBOSE)
71 msg.println("\n###\n### test1()\n###\n");
72
73 // Init. random data.
74 int err = 0;
75 for (int i = 0; i < data.length; ++i)
76 data[i] = (int) (MAXVALUE * Math.random());
77
78 GridHeap heap = new GridHeap();
79 for (int i = 0; i < data.length; ++i) {
80 heap.enqueue(new Grid(data[i]));
81 }
82 int ret = heap.sanityCheck();
83 if (VERBOSE)
84 msg.println(
85 (ret == 0)
86 ? "### GridHeap.sanityCheck(): OK"
87 : "### GridHeap.sanityCheck(): FAIL: index=");
88 if (CHECK)
89 if (ret != 0)
90 Assert.fail("Sanity check after enqueue FAILED.");
91 //
92 //
93 Grid a = heap.get(29);
94 a.estTotal = heap.get(60).estTotal + 1;
95 ret = heap.sanityCheck();
96 if (VERBOSE)
97 msg.println(
98 (ret == 30)
99 ? "### GridHeap.sanityCheck(): OK"
100 : "### GridHeap.sanityCheck(): FAIL: should fail at 30: ret=" + ret);
101 if (CHECK)
102 if (ret != 30)
103 Assert.fail("Expected sanityCheck() to fail at 30, actual ret=" + ret);
104 a = heap.get(9);
105 a.estTotal = heap.get(19).estTotal + 1;
106 ret = heap.sanityCheck();
107 if (VERBOSE)
108 msg.println(
109 (ret != 10)
110 ? "### GridHeap.sanityCheck(): OK"
111 : "### GridHeap.sanityCheck(): FAIL: should fail at 10: ret=" + ret);
112 }
113
114 /**
115 * Check that random data sorted correctly by enqueue() and dequeue().
116 */
117 public void test2() {
118
119 final int SIZE = 100;
120 final int MAXVALUE = 100;
121 final int[] data = new int[SIZE];
122 StringBuffer buf = new StringBuffer();
123 int ret;
124
125 if (VERBOSE)
126 msg.println("\n###\n### test2()\n###\n");
127
128 GridHeap heap = new GridHeap();
129 for (int i = 0; i < data.length; ++i)
130 data[i] = (int) (MAXVALUE * Math.random());
131 //
132 if (VERBOSE) {
133 msg.println("# data[" + data.length + "]=");
134 for (int i = 0; i < data.length; ++i) {
135 buf.append(sprint.f(" %4d").a(data[i]).end());
136 if (i % 10 == 9)
137 buf.append("\n");
138 }
139 msg.println(buf.toString());
140 buf.setLength(0);
141 }
142 //
143 for (int i = 0; i < data.length; ++i) {
144 heap.enqueue(new Grid(data[i]));
145 }
146 if (VERBOSE) {
147 msg.println("# Heap[" + heap.size() + "]=");
148 for (int i = 0; i < heap.size(); ++i) {
149 buf.append(sprint.f(" %4d").a(heap.get(i).estTotal).end());
150 if (i % 10 == 9)
151 buf.append("\n");
152 }
153 msg.println(buf.toString());
154 buf.setLength(0);
155 //
156 ret = heap.printHeap(buf, 0, "");
157 msg.println(buf.toString());
158 msg.println("# " + ret + " lines");
159 buf.setLength(0);
160 }
161 //
162 ret = heap.sanityCheck();
163 if (VERBOSE)
164 msg.println(
165 (ret == 0)
166 ? "### GridHeap.sanityCheck(): OK"
167 : ("### GridHeap.sanityCheck(): FAIL: index=" + ret));
168 if (CHECK)
169 if (ret != 0)
170 Assert.fail("Sanity check FAIL: index=" + ret);
171 //
172 Arrays.sort(data);
173 if (VERBOSE) {
174 msg.println("\n# sorted data=");
175 for (int i = 0; i < data.length; ++i) {
176 buf.append(sprint.f(" %4d").a(data[i]).end());
177 if (i % 10 == 9)
178 buf.append("\n");
179 }
180 msg.println(buf.toString());
181 buf.setLength(0);
182 //
183 msg.println("\n# dequeue=");
184 }
185 int count = 0;
186 float cost;
187 for (int i = 0, max = heap.size(); i < max; ++i) {
188 cost = heap.dequeue().estTotal;
189 if (cost != data[i])
190 ++count;
191 if (VERBOSE) {
192 buf.append(sprint.f(" %4d").a(cost).end());
193 if (i % 10 == 9)
194 buf.append("\n");
195 }
196 }
197 if (VERBOSE) {
198 msg.println(buf.toString());
199 buf.setLength(0);
200 if (count != 0)
201 msg.println("Fail count=" + count);
202 }
203 if (CHECK)
204 if (count != 0)
205 Assert.fail("Compare FAIL: counts=" + count);
206 }
207
208 ////////////////////////////////////////////////////////////////////////
209
210 /**
211 * requeue() test.
212 */
213 public void test3() {
214
215 final int SIZE = 100;
216 final int MAXVALUE = 100;
217 final int[] data = new int[SIZE];
218 StringBuffer buf = new StringBuffer();
219 int ret;
220 int count;
221 //
222 if (VERBOSE)
223 msg.println("\n###\n### test3()\n###");
224 //
225 for (int i = 0; i < data.length; ++i)
226 data[i] = (int) (MAXVALUE * Math.random());
227 //
228 GridHeap heap = new GridHeap();
229 for (int i = 0; i < data.length; ++i) {
230 heap.enqueue(new Grid(data[i]));
231 }
232 //
233 for (int i = 0; i < SIZE; ++i) {
234 int k = (int) (MAXVALUE * Math.random());
235 Grid c = heap.get(i);
236 c.estTotal = k;
237 heap.requeue(c);
238 heap.sanityCheck();
239 }
240 //
241 if (VERBOSE) {
242 msg.println("\n# Before requeue: Heap[" + heap.size() + "]=");
243 for (int i = 0; i < heap.size(); ++i) {
244 buf.append(sprint.f(" %4d").a(heap.get(i).estTotal).end());
245 if (i % 10 == 9)
246 buf.append("\n");
247 }
248 msg.println(buf.toString());
249 buf.setLength(0);
250 msg.println("\n# requeue() ...");
251 }
252 //
253 for (int i = 0; i < 1; ++i) {
254 int k = (int) (MAXVALUE * Math.random());
255 int index = (int) (SIZE * Math.random());
256 Grid c = heap.get(index);
257 if (VERBOSE)
258 msg.println(
259 "requeue(): heapIndex="
260 + c.heapIndex
261 + ", old value="
262 + c.estTotal
263 + ", new value="
264 + k);
265 c.estTotal = k;
266 heap.requeue(c);
267 }
268 ret = heap.sanityCheck();
269 if (CHECK)
270 if (ret != 0)
271 Assert.fail("Sanity check FAIL: index=" + ret);
272 //
273 if (VERBOSE) {
274 msg.println("\n# After requeue: Heap[" + heap.size() + "]=");
275 for (int i = 0; i < heap.size(); ++i) {
276 buf.append(sprint.f(" %4d").a(heap.get(i).estTotal).end());
277 if (i % 10 == 9)
278 buf.append("\n");
279 }
280 msg.println(buf.toString());
281 buf.setLength(0);
282 //
283 ret = heap.printHeap(buf, 0, "");
284 msg.println(buf.toString());
285 msg.println("# " + ret + " lines");
286 buf.setLength(0);
287 }
288 //
289 count = 0;
290 float cost;
291 FloatList actual = new FloatList(100);
292 for (int i = 0, max = heap.size(); i < max; ++i) {
293 actual.add(heap.dequeue().estTotal);
294 }
295 if (VERBOSE)
296 msg.println("\n# dequeue=\n" + actual.toString("%4d"));
297 //
298 // Check that dequeue() output are sorted in ascending order.
299 //
300 if (CHECK) {
301 float prev = 0;
302 for (int i = 0; i < actual.size(); ++i)
303 if (actual.get(i) < prev)
304 Assert.fail("Dequeue() output not in ascending order: index=" + i);
305 }
306 }
307 }