?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Redo and fix layout of history graph
[egit.git] / org.spearce.jgit / tst / org / spearce / jgit / lib / LaneTest.java
blob0f57075f93964acbaacd197d6553f0c677bcc448
1 /*
2 * Copyright (C) 2007 Robin Rosenberg
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License, version 2, as published by the Free Software Foundation.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
16 */
17 package org.spearce.jgit.lib;
18
19 import java.io.StringWriter;
20 import java.util.Arrays;
21 import java.util.Comparator;
22 import java.util.Iterator;
23 import java.util.List;
24
25 import junit.framework.TestCase;
26
27 import org.spearce.jgit.lib.TopologicalSorter.Edge;
28 import org.spearce.jgit.lib.TopologicalSorter.Lane;
29
30 public class LaneTest extends TestCase {
31
32 TopologicalSorter<Data> counter = new TopologicalSorter<Data>(
33 new Comparator<Data>() {
34 public int compare(Data o1, Data o2) {
35 return o1.compareTo(o2);
36 }
37 });
38
39 class Data implements Comparable<Data> {
40 String name;
41
42 int n;
43
44 Data(String name, int n) {
45 this.name = name;
46 this.n = n;
47 }
48
49 public int compareTo(Data o) {
50 int c = n - o.n;
51 if (c != 0)
52 return c;
53 if (this == o)
54 return 0;
55 return name.compareTo(o.name);
56 }
57
58 @Override
59 public String toString() {
60 return name + "(" + n + ")";
61 }
62 }
63
64 public void testLayout() {
65 /*
66 * This is th test input. A list of nodes. The number is a weight that
67 * is used when the output order cannot be determined conclusively from
68 * the order of the nodes. Think of the number as a date in a git
69 * commit. The elements are sorted by weight (the number in parentheses)
70 * when the topological order is non defined.
71 *
72 * a(1) - b(3) - c(7) - d(10) - e(21) - f(3) - g(1) - h(1) - i(1) - j(1) -
73 * \ / /
74 * k(3) - l(2) - m(11) - n(4) - o(5) - p(5) - q(5)
75 * \ /
76 * x(6) - y(5) - z(f)
77 *
78 * a
79 * |
80 * b---·
81 * | |
82 * | k
83 * | |
84 * | l---·
85 * | | |
86 * c | |
87 * | | |
88 * d | |
89 * | | |
90 * | m---+---·
91 * | | | |
92 * | n | |
93 * | | | |
94 * | o | |
95 * | | | |
96 * x<--+---+---·
97 * | | |
98 * y | |
99 * | | |
100 * z | |
101 * | | |
102 * |-->p |
103 * | | |
104 * | q |
105 * | | |
106 * e<--+---·
107 * | |
108 * f |
109 * | |
110 * g |
111 * | |
112 * h |
113 * | |
114 * i<--|
115 * |
116 * j
117 *
118 */
119 Data a = new Data("a", 1);
120 Data b = new Data("b", 3);
121 Data c = new Data("c", 7);
122 Data d = new Data("d", 10);
123 Data e = new Data("e", 21);
124 Data f = new Data("f", 3);
125 Data g = new Data("g", 1);
126 Data h = new Data("h", 1);
127 Data i = new Data("i", 1);
128 Data j = new Data("j", 1);
129 Data k = new Data("k", 3);
130 Data l = new Data("l", 2);
131 Data m = new Data("m", 11);
132 Data n = new Data("n", 4);
133 Data o = new Data("o", 5);
134 Data p = new Data("p", 5);
135 Data q = new Data("q", 5);
136 Data x = new Data("x", 6);
137 Data y = new Data("y", 5);
138 Data z = new Data("z", 5);
139
140 counter.put(new TopologicalSorter.Edge<Data>(a, b));
141 counter.put(new TopologicalSorter.Edge<Data>(b, c));
142 counter.put(new TopologicalSorter.Edge<Data>(c, d));
143 counter.put(new TopologicalSorter.Edge<Data>(d, e));
144 counter.put(new TopologicalSorter.Edge<Data>(e, f));
145 counter.put(new TopologicalSorter.Edge<Data>(f, g));
146 counter.put(new TopologicalSorter.Edge<Data>(g, h));
147 counter.put(new TopologicalSorter.Edge<Data>(h, i));
148 counter.put(new TopologicalSorter.Edge<Data>(i, j));
149 counter.put(new TopologicalSorter.Edge<Data>(b, k));
150 counter.put(new TopologicalSorter.Edge<Data>(k, l));
151 counter.put(new TopologicalSorter.Edge<Data>(l, m));
152 counter.put(new TopologicalSorter.Edge<Data>(m, n));
153 counter.put(new TopologicalSorter.Edge<Data>(n, o));
154 counter.put(new TopologicalSorter.Edge<Data>(o, p));
155 counter.put(new TopologicalSorter.Edge<Data>(p, q));
156 counter.put(new TopologicalSorter.Edge<Data>(q, i));
157 counter.put(new TopologicalSorter.Edge<Data>(m, x));
158 counter.put(new TopologicalSorter.Edge<Data>(x, y));
159 counter.put(new TopologicalSorter.Edge<Data>(y, z));
160 counter.put(new TopologicalSorter.Edge<Data>(z, p));
161 counter.put(new TopologicalSorter.Edge<Data>(l, e));
162
163 String road = drawAsAscii(counter);
164 String road2 = drawAsAscii(counter);
165
166 assertEquals(road, road2);
167 assertEquals(
168 "a\n" +
169 "b>>>>>>>\\\n" +
170 "| k\n" +
171 "| l>>>>>>>\\\n" +
172 "c | |\n" +
173 "d>>>>>>>|>>>>>>>\\\n" +
174 " m>>>>>>>|>>>>>>>\\\n" +
175 " n | |\n" +
176 " o | |\n" +
177 " | | x\n" +
178 " | | y\n" +
179 " /<<<<<<<|<<<<<<<z\n" +
180 " p |\n" +
181 " q |\n" +
182 " | e\n" +
183 " | f\n" +
184 " | g\n" +
185 " /<<<<<<<h\n" +
186 " i\n" +
187 " j\n",
188 road);
189
190 for(Data xx : counter.getEntries()) {
191 Lane lj = counter.lane.get(xx);
192 System.out.println(":"+xx + ", lane "+ lj + "{" + (lj.startsAt!=null ? counter.lane.get(lj.startsAt).getNumber() : -1) + "," + counter.lane.get(lj.endsAt).getNumber()+"}");
193 }
194 for (TopologicalSorter<Data>.Lane li : counter.lane.values()) {
195 System.out.println("L "+li);
196 }
197
198 Data da;
199 Lane la;
200 Iterator<Data> di = counter.getEntries().iterator();
201 da=di.next(); la=counter.lane.get(da); assertEquals("a",da.name); assertEquals(0, la.getNumber());
202 da=di.next(); la=counter.lane.get(da); assertEquals("b",da.name); assertEquals(0, la.getNumber());
203 da=di.next(); la=counter.lane.get(da); assertEquals("k",da.name); assertEquals(1, la.getNumber());
204 da=di.next(); la=counter.lane.get(da); assertEquals("l",da.name); assertEquals(1, la.getNumber());
205 da=di.next(); la=counter.lane.get(da); assertEquals("c",da.name); assertEquals(0, la.getNumber());
206 da=di.next(); la=counter.lane.get(da); assertEquals("d",da.name); assertEquals(0, la.getNumber());
207 da=di.next(); la=counter.lane.get(da); assertEquals("m",da.name); assertEquals(1, la.getNumber());
208 da=di.next(); la=counter.lane.get(da); assertEquals("n",da.name); assertEquals(1, la.getNumber());
209 da=di.next(); la=counter.lane.get(da); assertEquals("o",da.name); assertEquals(1, la.getNumber());
210 da=di.next(); la=counter.lane.get(da); assertEquals("x",da.name); assertEquals(3, la.getNumber());
211 da=di.next(); la=counter.lane.get(da); assertEquals("y",da.name); assertEquals(3, la.getNumber());
212 da=di.next(); la=counter.lane.get(da); assertEquals("z",da.name); assertEquals(3, la.getNumber());
213 da=di.next(); la=counter.lane.get(da); assertEquals("p",da.name); assertEquals(1, la.getNumber());
214 da=di.next(); la=counter.lane.get(da); assertEquals("q",da.name); assertEquals(1, la.getNumber());
215 da=di.next(); la=counter.lane.get(da); assertEquals("e",da.name); assertEquals(2, la.getNumber());
216 da=di.next(); la=counter.lane.get(da); assertEquals("f",da.name); assertEquals(2, la.getNumber());
217 da=di.next(); la=counter.lane.get(da); assertEquals("g",da.name); assertEquals(2, la.getNumber());
218 da=di.next(); la=counter.lane.get(da); assertEquals("h",da.name); assertEquals(2, la.getNumber());
219 da=di.next(); la=counter.lane.get(da); assertEquals("i",da.name); assertEquals(1, la.getNumber());
220 da=di.next(); la=counter.lane.get(da); assertEquals("j",da.name); assertEquals(1, la.getNumber());
221 assertFalse(di.hasNext());
222 }
223
224 public void testZeroNodes() {
225 String road = drawAsAscii(counter);
226 String road2 = drawAsAscii(counter);
227 assertEquals(road,road2);
228 assertEquals(
229 "",
230 road);
231 }
232
233 public void testOneNode() {
234 Data a = new Data("a", 5);
235
236 counter.put(a);
237 String road = drawAsAscii(counter);
238 String road2 = drawAsAscii(counter);
239 assertEquals(road,road2);
240 assertEquals(
241 "a\n",
242 road);
243 }
244
245 public void testTwoNodes() {
246 Data a = new Data("a", 5);
247 Data b = new Data("b", 4);
248
249 counter.put(a);
250 counter.put(b);
251 String road = drawAsAscii(counter);
252 String road2 = drawAsAscii(counter);
253 assertEquals(road,road2);
254 assertEquals(
255 "b\n" +
256 " a\n",
257 road);
258 }
259
260 public void testOneInTwoOut() {
261 Data a = new Data("a", 5);
262 Data b = new Data("b", 4);
263 Data c = new Data("c", 3);
264
265 counter.put(new TopologicalSorter.Edge<Data>(a, b));
266 counter.put(new TopologicalSorter.Edge<Data>(a, c));
267 String road = drawAsAscii(counter);
268 String road2 = drawAsAscii(counter);
269 assertEquals(road,road2);
270 assertEquals(
271 "a>>>>>>>\\\n"+
272 "| c\n" +
273 "b\n"
274 , road);
275 }
276
277 public void testTwoInOneOut() {
278 Data a = new Data("a", 5);
279 Data b = new Data("b", 4);
280 Data c = new Data("c", 3);
281
282 counter.put(new TopologicalSorter.Edge<Data>(b, a));
283 counter.put(new TopologicalSorter.Edge<Data>(c, a));
284 String road = drawAsAscii(counter);
285 String road2 = drawAsAscii(counter);
286 assertEquals(road,road2);
287 assertEquals(
288 "c\n"+
289 "/<<<<<<<b\n" +
290 "a\n"
291 , road);
292 }
293
294 public void testTwoLanesWithFourNode_variant1() {
295 Data a = new Data("a", 5);
296 Data b = new Data("b", 4);
297 Data c = new Data("c", 3);
298 Data d = new Data("d", 2);
299
300 counter.put(new TopologicalSorter.Edge<Data>(a, b));
301 counter.put(new TopologicalSorter.Edge<Data>(c, d));
302 String road = drawAsAscii(counter);
303 String road2 = drawAsAscii(counter);
304 assertEquals(road,road2);
305 assertEquals(
306 "c\n"+
307 "d\n"+
308 " a\n"+
309 " b\n"
310 , road);
311 }
312
313 public void testTwoLanesWithFourNode_variant2() {
314 Data a = new Data("a", 3);
315 Data b = new Data("b", 2);
316 Data c = new Data("c", 5);
317 Data d = new Data("d", 4);
318
319 counter.put(new TopologicalSorter.Edge<Data>(a, b));
320 counter.put(new TopologicalSorter.Edge<Data>(c, d));
321 String road = drawAsAscii(counter);
322 String road2 = drawAsAscii(counter);
323 assertEquals(road,road2);
324 assertEquals(
325 "a\n"+
326 "b\n"+
327 " c\n"+
328 " d\n"
329 , road);
330 }
331
332 public void testTwoLanesWithFourNode_variant3() {
333 Data a = new Data("a", 3);
334 Data b = new Data("b", 4);
335 Data c = new Data("c", 2);
336 Data d = new Data("d", 5);
337
338 counter.put(new TopologicalSorter.Edge<Data>(a, b));
339 counter.put(new TopologicalSorter.Edge<Data>(c, d));
340 String road = drawAsAscii(counter);
341 String road2 = drawAsAscii(counter);
342 assertEquals(road,road2);
343 assertEquals(
344 "c\n"+
345 "| a\n"+
346 "| b\n"+
347 "d\n"
348 , road);
349 }
350
351 public void testTwoLanesWithFourNode_variant4() {
352 Data a = new Data("a", 3);
353 Data b = new Data("b", 5);
354 Data c = new Data("c", 2);
355 Data d = new Data("d", 4);
356
357 counter.put(new TopologicalSorter.Edge<Data>(a, b));
358 counter.put(new TopologicalSorter.Edge<Data>(c, d));
359 String road = drawAsAscii(counter);
360 String road2 = drawAsAscii(counter);
361 assertEquals(road,road2);
362 assertEquals(
363 "c\n"+
364 "| a\n"+
365 "d |\n"+
366 " b\n"
367 , road);
368 }
369
370 public void testDiamond() {
371 Data a = new Data("a", 3);
372 Data b = new Data("b", 4);
373 Data c = new Data("c", 2);
374 Data d = new Data("d", 5);
375
376 counter.put(new TopologicalSorter.Edge<Data>(a, b));
377 counter.put(new TopologicalSorter.Edge<Data>(a, c));
378 counter.put(new TopologicalSorter.Edge<Data>(b, d));
379 counter.put(new TopologicalSorter.Edge<Data>(c, d));
380 String road = drawAsAscii(counter);
381 String road2 = drawAsAscii(counter);
382 assertEquals(road,road2);
383 assertEquals(
384 "a>>>>>>>\\\n"+
385 "| c\n"+
386 "b>>>>>>>\\\n"+
387 " d\n"
388 , road);
389 }
390
391 public void testAllDirections() {
392 Data a = new Data("a",1);
393 Data b = new Data("b",2);
394 Data c = new Data("c",5);
395 Data d = new Data("d",4);
396 Data e = new Data("e",3);
397 Data f = new Data("f",6);
398 Data g = new Data("g",7);
399 counter.put(new TopologicalSorter.Edge<Data>(a,b));
400 counter.put(new TopologicalSorter.Edge<Data>(b,c));
401 counter.put(new TopologicalSorter.Edge<Data>(a,d));
402 counter.put(new TopologicalSorter.Edge<Data>(b,d));
403 counter.put(new TopologicalSorter.Edge<Data>(d,c));
404 counter.put(new TopologicalSorter.Edge<Data>(e,d));
405 counter.put(new TopologicalSorter.Edge<Data>(e,g));
406 counter.put(new TopologicalSorter.Edge<Data>(d,g));
407 counter.put(new TopologicalSorter.Edge<Data>(d,f));
408 String road = drawAsAscii(counter);
409 String road2 = drawAsAscii(counter);
410 assertEquals(road,road2);
411 assertEquals(
412 "a>>>>>>>\\\n"+
413 "b>>>>>>>\\\n"+
414 "| /<<<<<<<e\n"+
415 "/<<<<<<<d>>>>>>>\\\n"+
416 "c | |\n"+
417 " f |\n"+
418 " g\n"
419 , road);
420 }
421
422 public void testAllPossibleWithFour() {
423 Data a = new Data("a", 1);
424 Data b = new Data("b", 2);
425 Data c = new Data("c", 3);
426 Data d = new Data("d", 4);
427
428 counter.put(new TopologicalSorter.Edge<Data>(a, b));
429 counter.put(new TopologicalSorter.Edge<Data>(a, c));
430 counter.put(new TopologicalSorter.Edge<Data>(a, d));
431 counter.put(new TopologicalSorter.Edge<Data>(b, c));
432 counter.put(new TopologicalSorter.Edge<Data>(b, d));
433 counter.put(new TopologicalSorter.Edge<Data>(c, d));
434 String road = drawAsAscii(counter);
435 String road2 = drawAsAscii(counter);
436 assertEquals(road,road2);
437 assertEquals(
438 "a>>>>>>>\\>>>>>>>\\\n"+
439 "b>>>>>>>\\>>>>>>>\\\n"+
440 " c>>>>>>>\\\n"+
441 " d\n"
442 , road);
443 }
444
445 public void testAllPossibleWithFive() {
446 Data a = new Data("a", 1);
447 Data b = new Data("b", 2);
448 Data c = new Data("c", 3);
449 Data d = new Data("d", 4);
450 Data e = new Data("e", 5);
451
452 counter.put(new TopologicalSorter.Edge<Data>(a, b));
453 counter.put(new TopologicalSorter.Edge<Data>(a, c));
454 counter.put(new TopologicalSorter.Edge<Data>(a, d));
455 counter.put(new TopologicalSorter.Edge<Data>(a, e));
456 counter.put(new TopologicalSorter.Edge<Data>(b, c));
457 counter.put(new TopologicalSorter.Edge<Data>(b, d));
458 counter.put(new TopologicalSorter.Edge<Data>(b, e));
459 counter.put(new TopologicalSorter.Edge<Data>(c, d));
460 counter.put(new TopologicalSorter.Edge<Data>(c, e));
461 counter.put(new TopologicalSorter.Edge<Data>(d, e));
462 String road = drawAsAscii(counter);
463 String road2 = drawAsAscii(counter);
464 assertEquals(road,road2);
465 assertEquals(
466 "a>>>>>>>\\>>>>>>>\\>>>>>>>\\\n"+
467 "b>>>>>>>\\>>>>>>>\\>>>>>>>\\\n"+
468 " c>>>>>>>\\>>>>>>>\\\n"+
469 " d>>>>>>>\\\n"+
470 " e\n"
471 , road);
472 }
473
474 public void testAllPossibleWithFiveLessSome() {
475 Data a = new Data("a", 1);
476 Data b = new Data("b", 2);
477 Data c = new Data("c", 3);
478 Data d = new Data("d", 4);
479 Data e = new Data("e", 5);
480
481 counter.put(new TopologicalSorter.Edge<Data>(a, b));
482 counter.put(new TopologicalSorter.Edge<Data>(a, c));
483 counter.put(new TopologicalSorter.Edge<Data>(a, d));
484 counter.put(new TopologicalSorter.Edge<Data>(a, e));
485 counter.put(new TopologicalSorter.Edge<Data>(b, c));
486 counter.put(new TopologicalSorter.Edge<Data>(b, e));
487 counter.put(new TopologicalSorter.Edge<Data>(c, d));
488 counter.put(new TopologicalSorter.Edge<Data>(d, e));
489 String road = drawAsAscii(counter);
490 String road2 = drawAsAscii(counter);
491 assertEquals(road,road2);
492 assertEquals(
493 "a>>>>>>>\\>>>>>>>\\>>>>>>>\\\n"+
494 "b>>>>>>>\\>>>>>>>|>>>>>>>\\\n"+
495 " c>>>>>>>\\ |\n"+
496 " d>>>>>>>\\\n"+
497 " e\n"
498 , road);
499 }
500
501 private String drawAsAscii(TopologicalSorter<Data> counter) {
502 StringWriter w = new StringWriter();
503 List<Data> entries = counter.getEntries();
504 for (int i=0; i<entries.size(); ++i) {
505 Data xx = entries.get(i);
506 Integer io = counter.getInternalPosition(xx);
507 // System.out.print("Now at item "+xx+ " at "+io);
508 Lane lane = counter.lane.get(xx);
509 // lane.getNumber();
510 char[] points = new char[counter.currentLanes.size()];
511 char[] horiz = new char[counter.currentLanes.size()-1];
512 Arrays.fill(points,' ');
513
514 List<Edge<Data>> px = counter.getEdgeFrom(xx);
515 for (TopologicalSorter<Data>.Lane li : counter.currentLanes) {
516 Integer iost = counter.getInternalPosition(li.startsAt);
517 Integer ioen = counter.getInternalPosition(li.endsAt);
518
519 // Middle of lane
520 // o
521 // |
522 // o
523 if (iost != null && io > iost && (ioen == null || io < ioen)) {
524 points[li.getNumber()] = '|';
525 }
526 // branch out to parent
527 // o o
528 // \>>>>>>>>>>o o<<<<<<<<<</
529 if (px != null) {
530 for (int j=0; j<px.size(); ++j) {
531 Data p = px.get(j).to;
532 Lane pl = counter.getLane(p);
533 if (li == pl && lane != li) {
534 int fromn = lane.getNumber();
535 int ton = pl.getNumber();
536 if (fromn < ton) {
537 points[ton] = '\\';
538 for (int k=fromn; k<ton; ++k) {
539 horiz[k] = '>';
540 }
541 } else {
542 points[ton] = '/';
543 for (int k=fromn-1; k>=ton; --k) {
544 horiz[k] = '<';
545 }
546 }
547 }
548 }
549 }
550 // merge, SAME (unless we get really smart)
551 }
552 points[lane.getNumber()] = xx.name.charAt(0);
553 int m = points.length;
554 while (m > 0 && points[m-1] == ' ')
555 --m;
556 for (int ii=0; ii<m-1; ++ii) {
557 w.write(points[ii]);
558 char ch = horiz[ii];
559 if (ch != 0)
560 for (int jj=0; jj<7; ++jj)
561 w.write(ch);
562 else
563 w.write(" ");
564 // w.write('\t');
565 }
566 w.write(points[m-1]);
567 w.write('\n');
568 }
569 System.out.println(w);
570 return w.toString();
571 }
572 }
Eclipse Git Team Provider