Mercurial > hg4j

comparison src/org/tmatesoft/hg/repo/HgParentChildMap.java @ 646:3b7d51ed4c65

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Push: phase3 - update matching remote bookmarks
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 21 Jun 2013 18:30:35 +0200
parents 14dac192aa26
children 3b275cc2d2aa
comparison
equal deleted inserted replaced
645:14dac192aa26 646:3b7d51ed4c65
55 * @author Artem Tikhomirov 55 * @author Artem Tikhomirov
56 * @author TMate Software Ltd. 56 * @author TMate Software Ltd.
57 */ 57 */
58 public final class HgParentChildMap<T extends Revlog> implements ParentInspector { 58 public final class HgParentChildMap<T extends Revlog> implements ParentInspector {
59 59
60 // IMPORTANT: Nodeid instances shall be shared between all arrays
61
60 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering 62 private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
61 private Nodeid[] sorted; // for binary search 63 private Nodeid[] sorted; // for binary search
62 private int[] sorted2natural; 64 private int[] sorted2natural; // indexes in sorted to indexes in sequential
63 private Nodeid[] firstParent; 65 private Nodeid[] firstParent;
64 private Nodeid[] secondParent; 66 private Nodeid[] secondParent;
65 private final T revlog; 67 private final T revlog;
66 68
67 // Nodeid instances shall be shared between all arrays
68 69
69 public HgParentChildMap(T owner) { 70 public HgParentChildMap(T owner) {
70 revlog = owner; 71 revlog = owner;
71 } 72 }
72 73
252 * @return all revisions this map knows about 253 * @return all revisions this map knows about
253 */ 254 */
254 public List<Nodeid> all() { 255 public List<Nodeid> all() {
255 return Arrays.asList(sequential); 256 return Arrays.asList(sequential);
256 } 257 }
258
259 /**
260 * Find out whether a given node is among descendants of another.
261 *
262 * @param root revision to check for being (grand-)*parent of a child
263 * @param wannaBeChild candidate descendant revision
264 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code>
265 */
266 public boolean isChild(Nodeid root, Nodeid wannaBeChild) {
267 int x = Arrays.binarySearch(sorted, root);
268 assertSortedIndex(x);
269 root = sorted[x]; // canonical instance
270 int y = Arrays.binarySearch(sorted, wannaBeChild);
271 if (y < 0 || y <= x) {
272 // not found or comes earlier than root
273 return false;
274 }
275 wannaBeChild = sorted[y]; // canonicalize
276 final int start = sorted2natural[x];
277 final int end = sorted2natural[y];
278 HashSet<Nodeid> parents = new HashSet<Nodeid>();
279 parents.add(root);
280 for (int i = start + 1; i < end; i++) {
281 if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
282 parents.add(sequential[i]); // collect ancestors line
283 }
284 }
285 return parents.contains(firstParent[end]) || parents.contains(secondParent[end]);
286 }
257 } 287 }