?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Use the proper comparison algorithm
[egit/zawir.git] / org.spearce.jgit / src / org / spearce / jgit / lib / IndexTreeWalker.java
blobc17cea10be7695ae8aa367944298368c2acebc0d
1 /*
2 * Copyright (C) 2007 David Watson <dwatson@mimvista.com>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License, version 2.1, 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 * Lesser 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
18 package org.spearce.jgit.lib;
19
20 import java.io.File;
21 import java.io.IOException;
22
23 import org.spearce.jgit.lib.GitIndex.Entry;
24
25 /**
26 * A class for traversing the index and one or two trees.
27 *
28 * A visitor is invoked for executing actions, like figuring out how to merge.
29 */
30 public class IndexTreeWalker {
31 private final Tree mainTree;
32 private final Tree newTree;
33 private final File root;
34 private final IndexTreeVisitor visitor;
35 private boolean threeTrees;
36
37 /**
38 * Construct a walker for the index and one tree.
39 *
40 * @param index
41 * @param tree
42 * @param root
43 * @param visitor
44 */
45 public IndexTreeWalker(GitIndex index, Tree tree, File root, IndexTreeVisitor visitor) {
46 this.mainTree = tree;
47 this.root = root;
48 this.visitor = visitor;
49 this.newTree = null;
50
51 threeTrees = false;
52
53 indexMembers = index.getMembers();
54 }
55
56 /**
57 * Construct a walker for the index and two trees.
58 *
59 * @param index
60 * @param mainTree
61 * @param newTree
62 * @param root
63 * @param visitor
64 */
65 public IndexTreeWalker(GitIndex index, Tree mainTree, Tree newTree, File root, IndexTreeVisitor visitor) {
66 this.mainTree = mainTree;
67 this.newTree = newTree;
68 this.root = root;
69 this.visitor = visitor;
70
71 threeTrees = true;
72
73 indexMembers = index.getMembers();
74 }
75
76 Entry[] indexMembers;
77 int indexCounter = 0;
78
79 /**
80 * Actually walk the index tree
81 *
82 * @throws IOException
83 */
84 public void walk() throws IOException {
85 walk(mainTree, newTree, "/");
86 }
87
88 private void walk(Tree tree, Tree auxTree, String curDir) throws IOException {
89 TreeEntry[] treeMembers = tree == null ? new TreeEntry[0] : tree.members();
90 TreeEntry[] auxTreeMembers = auxTree == null ? new TreeEntry[0] : auxTree.members();
91 int treeCounter = 0;
92 int auxTreeCounter = 0;
93
94 int curIndexPos = indexCounter;
95
96 while (treeCounter < treeMembers.length ||
97 indexCounter < indexMembers.length ||
98 auxTreeCounter < auxTreeMembers.length) {
99 TreeEntry h = treeCounter < treeMembers.length ? treeMembers[treeCounter] : null;
100 TreeEntry m = auxTreeCounter < auxTreeMembers.length ? auxTreeMembers[auxTreeCounter] : null;
101 Entry i = indexCounter < indexMembers.length ? indexMembers[indexCounter] : null;
102
103 String indexName = i == null ? null : i.getName();
104 String treeName = h == null ? null : h.getFullName();
105 String auxTreeName = m == null ? null : m.getFullName();
106
107 if (treeName != null && indexName != null && auxTreeName != null) {
108 if (eq(h, i) && eq(m, i)) {
109 // H == I == M
110 visitor.visitEntry(h, m, i, new File(root, treeName));
111
112 treeCounter++;
113 indexCounter++;
114 auxTreeCounter++;
115 } else if (eq(h, i) && lt(h, m)) {
116 // H == I, H < M
117 visitor.visitEntry(h, null, i, new File(root, treeName));
118
119 treeCounter++;
120 indexCounter++;
121 } else if (eq(h, m) && lt(h, i)) {
122 // H == M, H < I
123 if (h instanceof Tree) {
124 walk((Tree)h, (Tree)m, "/" + treeName);
125 } else {
126 visitor.visitEntry(h, m, null, new File(root, treeName));
127 }
128
129 treeCounter++;
130 auxTreeCounter++;
131
132
133 } else if (eq(m, i) && lt(i, h)) {
134 // I == M, I < H
135 visitor.visitEntry(null, m, i, new File(root, indexName));
136
137 indexCounter++;
138 auxTreeCounter++;
139 } else if (lt(h, i) && lt(h, m)) {
140 // H < I, H < M
141 if (h instanceof Tree) {
142 walk((Tree) h, null, "/" + treeName);
143 } else {
144 visitor.visitEntry(h, null, null, new File(root, treeName));
145 }
146
147 treeCounter++;
148 } else if (lt(m, i) && lt(m, h)) {
149 // M < I, M < H
150 if (m instanceof Tree) {
151 walk(null, (Tree) m, "/" + auxTreeName);
152 } else {
153 visitor.visitEntry(null, m, null, new File(root, auxTreeName));
154 }
155
156 auxTreeCounter++;
157 } else { // index entry is first
158 // I < H, I < M
159 visitor.visitEntry(null, null, i, new File(root, indexName));
160
161 indexCounter++;
162 }
163 } else if (treeName != null && indexName != null) {
164 if (eq(h, i)) {
165 if (threeTrees)
166 visitor.visitEntry(h, null, i, new File(root, indexName));
167 else visitor.visitEntry(h, i, new File(root, indexName));
168
169 treeCounter++;
170 indexCounter++;
171 } else if (lt(h, i)) {
172 if (h instanceof Tree)
173 walk((Tree) h, null, "/" + treeName);
174 else {
175 if (threeTrees) {
176 visitor.visitEntry(h, null, null, new File(root, treeName));
177 } else visitor.visitEntry(h, null, new File(root, treeName));
178 }
179
180 treeCounter++;
181 } else { // lt(i, h)
182 if (threeTrees) {
183 visitor.visitEntry(null, null, i, new File(root, indexName));
184 } else visitor.visitEntry(null, i, new File(root, indexName));
185
186 indexCounter++;
187 }
188 } else if (treeName != null && auxTreeName != null) {
189 if (eq(h, m)) {
190 if (h instanceof Tree) {
191 walk((Tree) h, (Tree) m, "/" + treeName);
192 } else {
193 visitor.visitEntry(h, m, null, new File(root, treeName));
194 }
195
196 treeCounter++;
197 auxTreeCounter++;
198 } else if (lt(h, m)) {
199 if (h instanceof Tree) {
200 walk((Tree) h, null, "/" + treeName);
201 } else {
202 visitor.visitEntry(h, null, null, new File(root, treeName));
203 }
204
205 treeCounter++;
206 } else { // lt(m, h)
207 if (m instanceof Tree) {
208 walk(null, (Tree) m, "/" + auxTreeName);
209 } else {
210 visitor.visitEntry(null, m, null, new File("/" + auxTreeName));
211 }
212
213 auxTreeCounter++;
214 }
215
216 } else if (indexName != null && auxTreeName != null) {
217 if (eq(m, i)) {
218 visitor.visitEntry(null, m, i, new File(root, indexName));
219
220 auxTreeCounter++;
221 indexCounter++;
222 } else if (lt(m, i)) {
223 if (m instanceof Tree)
224 walk(null, (Tree) m, "/" + auxTreeName);
225 else {
226 visitor.visitEntry(null, m, null, new File(root, auxTreeName));
227 }
228
229 auxTreeCounter++;
230 } else { // lt(i, m)
231 visitor.visitEntry(null, null, i, new File(root, indexName));
232
233 indexCounter++;
234 }
235 } else if (treeName != null) {
236 if (h instanceof Tree) {
237 walk((Tree) h, null, "/" + treeName);
238 } else if (threeTrees)
239 visitor.visitEntry(h, null, null, new File(root, treeName));
240 else visitor.visitEntry(h, null, new File(root, treeName));
241
242 treeCounter++;
243 } else if (auxTreeName != null) {
244 if (m instanceof Tree) {
245 walk(null, (Tree)m, "/" + auxTreeName);
246 } else visitor.visitEntry(null, m, null, new File(root, auxTreeName));
247
248 auxTreeCounter++;
249 } else if (indexName != null) {
250 // need to check if we're done with this tree
251 String curDirNoSlash = curDir.substring(1);
252 if (!indexName.startsWith(curDirNoSlash + "/") && curDirNoSlash.length() != 0)
253 break;
254
255 if (threeTrees)
256 visitor.visitEntry(null, null, i, new File(root, indexName));
257 else visitor.visitEntry(null, i, new File(root, indexName));
258 indexCounter++;
259 }
260 }
261
262 if (threeTrees) {
263 visitor.finishVisitTree(tree, auxTree, indexCounter - curIndexPos,
264 curDir.substring(1));
265 } else {
266 visitor.finishVisitTree(tree, indexCounter - curIndexPos, curDir);
267 }
268 }
269
270 static boolean lt(TreeEntry h, Entry i) {
271 return compare(h, i) < 0;
272 }
273
274 static boolean lt(Entry i, TreeEntry t) {
275 return compare(t, i) > 0;
276 }
277
278 static boolean lt(TreeEntry h, TreeEntry m) {
279 return compare(h, m) < 0;
280 }
281
282 static boolean eq(TreeEntry t1, TreeEntry t2) {
283 return compare(t1, t2) == 0;
284 }
285
286 static boolean eq(TreeEntry t1, Entry e) {
287 return compare(t1, e) == 0;
288 }
289
290 static int compare(TreeEntry t, Entry i) {
291 return Tree.compareNames(t.getFullNameUTF8(), i.getNameUTF8(), TreeEntry.lastChar(t), TreeEntry.lastChar(i));
292 }
293
294 static int compare(TreeEntry t1, TreeEntry t2) {
295 return Tree.compareNames(t1.getNameUTF8(), t2.getNameUTF8(), TreeEntry.lastChar(t1), TreeEntry.lastChar(t2));
296 }
297
298 }
zawir's GSoC egit tree