1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
<html>
<body>
This package implements a general tree comparison as a
special case of visiting generic trees pairwise.
Trees are wrapped as <code>GenericTreeNode</code>, which has a static
method <code>boolean traverse(..)</code> which accepts
a visitor and traverses a pair of trees, calling the
visitor on each.
<p>This package supports four forms of generality
through the following classes:
<table border="+1">
<tr><th>Classes</th>
<th>Capability</th></tr>
<tr><td valign="top">GenericTreeNode</td>
<td>Able to handle trees of varying types
by wrapping in a generic form.<td>
</tr>
<tr><td valign="top">GenericTreeNodesVisitorI, GenericTreeNode.traverse(..)</td>
<td>Can handle any type of pairwise visitor function
by accepting visitor in the traverse method.</td>
</tr>
<tr><td valign="top">{java.util.Comparator}, GenericTreeNode.getComparator()</td>
<td>The object comparison can be sensitive to the type
of the object on a per-object basis, established during
the process of wrapping the tree.</td>
</tr>
<tr><td valign="top">GenericTreeListOrdererI, GenericTreeListOrdererFactoryI</td>
<td>The ordering of children can be appropriate to
the objective of the traversal. e.g., when computing
"set intersection" rather than "list equals", the
order of children might be changed to align matching
children for the visits.
<br>This ordering can be determined as appropriate for each
list comparison by implementing a factory which selects
from the appropriate orderers. Any factory product is used
by the traverse(..) method to order children before
visiting.</td>
<td></td>
</tr>
</table>
<p><u>Supported variants</u>:
The following variants are implemented or planned using the components above:
<table border="1">
<tr><th>Component</th><th>Description</th></tr>
<tr><td colspan=2>Current</th></tr>
<tr><td>GenericTreeNode.PRINTALL</td>
<td>A visitor which prints out the entire tree.</td></tr>
<tr><td>GenericTreeNode.PRINTERR</td>
<td>A visitor which prints the nonmatching pairs.</td></tr>
<tr><td>GenericTreeNode.EXACT</td>
<td>A visitor which returns false if any pairs do not match.</td></tr>
<tr><td>TreeCompare</td>
<td>A sample program to read in serialized trees and compare them.
(but see Structure in the compare subpackage for a better example) </td></tr>
<tr><td>CompareUtil</td>
<td>Misc comparison utilities (e.g., for short-circuiting comparisons).</td></tr>
<tr><td colspan=2>Planned</th></tr>
<tr><td>GenericTreeNode.KIDDIFF</td>
<td>A visitor which calculates tree differences, using ordering children
(catches swaps, missed or added elements, within children)</td></tr>
<tr><td>GenericTreeNode.TREEDIFF</td>
<td>A visitor which calculates tree differences, accumulating the tree
(catches swaps, missed or added elements, throughout tree.)</td></tr>
</table>
<p><u>Use</u>:
Run TreeCompare to use the comparer from the command line on a supported tree,
(currently only the Swing TreeNode implemented as DefaultMutableTreeNode).
<p><u>Programming</u>:<br>
To support a new tree, see the Structure example in the compare subpackage
or use example of the Swing TreeNode:
<li>Write an adapter that uses GenericTreeNode to wrap your tree nodes</li>
<li>Write a factory that produces a wrapped tree</li>
<li>Write a Comparator that compares the underlying node object
to include with each node object wrapped. Be sure to implement
the Comparator.equals(Object) method correctly, i.e., returning
true when it is equivalent to another comparator. It is best
to use a singleton for each type of node you support. </li>
<li>Optionally write a visitor to perform whatever operations you wish.
Note that visitors must tolerate a single null input in order to
completely traverse unmatching trees.</li>
<li>To perform operations requiring preprocessing of child List's,
write children orderer(s) and provide a factory to select them.</li>
<p>To design new algorithms/applications, bear in mind the main tools:
<li>The comparator that follows the node object</li>
<li>The visitor that traverses the tree </li>
<li>The child orderer that may preprocess the child lists </li>
<br>In particular, when going beyond pair-wise comparisons to
list-wise or tree-wise comparisons, you'll have to decide
where to put the appropriate logic. You may have a relatively
lightweight visitor and a heavyweight orderer, or no
orderer at all. In that case, you may need to invoke a
special method on your visitor after the traversal completes
to do any final processing.
<h2>Future Work</h2>:
<p><u>Smarter group comparisons</u>:
<br>Does calculating maps help with diagnosing problems?
<pre>
Given two lists,
A [ a, b, c, d, e, f, g, h ]
B [ a, e, c, d, b, g, h ]
The result should say:
- B swapped order of e and b
- B omitted f
Note the match-map (index of matching element, if any):
A->B [ 0, 4, 2, 3, 1, -, 5, 6 ]
B->A [ 0, 4, 2, 3, 1, 6, 7 ]
the shift-map (difference between expected and actual order):
A->B [ 0, 3, 0, 0, -3, -, -1, -1 ]
B->A [ 0, 3, 0, 0, -3, 1, 1 ]
Thus:
- detect swaps as complementary out-of-index order pairs
(todo: three-way or n-ary?)
- fix or ignore swaps
- detect shifts as complementary series
where shift-width n is +/- for both
- -n =>
- if negative element is actual, n elements omitted
- if negative element is expected, n elements added
<pre>
</body>
</html>
|
