# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1374334852 -7200
# Node ID 19f5167c2155b02b22c258cba6fe67a491967f5a
# Parent  8625cba0a5a883aff9429532f7859fc42d22b34a
HgParentChildMap: deduce common ancestor functionality

diff -r 8625cba0a5a8 -r 19f5167c2155 src/org/tmatesoft/hg/internal/IntSliceSeq.java
--- a/src/org/tmatesoft/hg/internal/IntSliceSeq.java	Fri Jul 19 15:36:29 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/IntSliceSeq.java	Sat Jul 20 17:40:52 2013 +0200
@@ -101,6 +101,22 @@
 			}
 		};
 	}
+	
+	@Override
+	public String toString() {
+		StringBuilder sb = new StringBuilder();
+		for (int i = 0; i < size(); i++) {
+			sb.append('(');
+			for (int j = 0; j < slice; j++) {
+				sb.append(slices.get(i*slice + j));
+				sb.append(',');
+			}
+			sb.setLength(sb.length() - 1);
+			sb.append(')');
+			sb.append(' ');
+		}
+		return sb.toString();
+	}
 
 	private void checkArgRange(int rangeSize, int index) {
 		if (index >= 0 && index < rangeSize) {
diff -r 8625cba0a5a8 -r 19f5167c2155 src/org/tmatesoft/hg/repo/HgParentChildMap.java
--- a/src/org/tmatesoft/hg/repo/HgParentChildMap.java	Fri Jul 19 15:36:29 2013 +0200
+++ b/src/org/tmatesoft/hg/repo/HgParentChildMap.java	Sat Jul 20 17:40:52 2013 +0200
@@ -347,8 +347,72 @@
 		}
 		return revisionIndexMap;
 	}
+	
+	/**
+	 * @return common ancestor of two revisions
+	 */
+	public Nodeid ancestor(Nodeid r1, Nodeid r2) {
+		if (r1.equals(r2)) {
+			return r1;
+		}
+		BitSet a1 = buildAncestors(r1);
+		BitSet a2 = buildAncestors(r2);
+		// BitSet.and() trims to shorter bitset, it's ok as we are not 
+		// interested in bits that are part of one bitset only
+		a1.and(a2);
+		final int cardinality = a1.cardinality();
+		if (cardinality == 1) {
+			return sequential[a1.nextSetBit(0)];
+		}
+		assert cardinality > 0; // every revision is child of at least rev0
+		final int length = sequential.length;
+		int index = length / 2;
+		int lastBitSet = -1;
+		do {
+			int nextSetBit = a1.nextSetBit(index);
+			int nextIndex;
+			if (nextSetBit == -1) {
+				assert lastBitSet == -1 || lastBitSet <= index;
+				nextIndex = index - (index - (lastBitSet == -1 ? 0 : lastBitSet)) / 2;
+			} else {
+				lastBitSet = nextSetBit;
+				nextIndex = lastBitSet + (length - lastBitSet) / 2;
+			}
+			if (nextIndex == index) {
+				break;
+			}
+			index = nextIndex;
+		} while (true);
+		if (lastBitSet == -1) {
+			assert false; // likely error in the algorithm above (e.g. can't reach index==0)
+			return sequential[0];
+		}
+		return sequential[lastBitSet];
+	}
 
 	private boolean hasChildren(int sequentialIndex) {
 		return !heads.containsKey(sequentialIndex);
 	}
+	
+	private BitSet buildAncestors(Nodeid nid) {
+		int x = seqWrapper.binarySearchSorted(nid);
+		assertSortedIndex(x);
+		int i = seqWrapper.getReverseIndex(x);
+		BitSet rv = new BitSet(sequential.length);
+		HashSet<Nodeid> ancestors = new HashSet<Nodeid>();
+		ancestors.add(nid);
+		do {
+			if (ancestors.contains(sequential[i])) {
+				rv.set(i);
+				if(firstParent[i] != null) {
+					ancestors.add(firstParent[i]);
+				}
+				if (secondParent[i] != null) {
+					ancestors.add(secondParent[i]);
+				}
+			}
+			i--;
+		} while (i >= 0);
+		return rv;
+	}
 }
\ No newline at end of file
diff -r 8625cba0a5a8 -r 19f5167c2155 test/org/tmatesoft/hg/test/TestRevisionMaps.java
--- a/test/org/tmatesoft/hg/test/TestRevisionMaps.java	Fri Jul 19 15:36:29 2013 +0200
+++ b/test/org/tmatesoft/hg/test/TestRevisionMaps.java	Sat Jul 20 17:40:52 2013 +0200
@@ -100,6 +100,16 @@
 		errorCollector.assertEquals(Arrays.asList(allRevs[2], allRevs[3]), parentHelper.directChildren(allRevs[1]));
 		errorCollector.assertEquals(Arrays.asList(allRevs[8]), parentHelper.directChildren(allRevs[6]));
 		errorCollector.assertEquals(Collections.emptyList(), parentHelper.directChildren(allRevs[7]));
+		// ancestors on the same line
+		errorCollector.assertEquals(allRevs[4], parentHelper.ancestor(allRevs[4], allRevs[4]));
+		errorCollector.assertEquals(allRevs[8], parentHelper.ancestor(allRevs[8], allRevs[9]));
+		errorCollector.assertEquals(allRevs[1], parentHelper.ancestor(allRevs[9], allRevs[1]));
+		errorCollector.assertEquals(allRevs[5], parentHelper.ancestor(allRevs[5], allRevs[7]));
+		// ancestor
+		errorCollector.assertEquals(allRevs[1], parentHelper.ancestor(allRevs[2], allRevs[3]));
+		errorCollector.assertEquals(allRevs[1], parentHelper.ancestor(allRevs[4], allRevs[6]));
+		errorCollector.assertEquals(allRevs[2], parentHelper.ancestor(allRevs[9], allRevs[7]));
+		errorCollector.assertEquals(allRevs[2], parentHelper.ancestor(allRevs[4], allRevs[7]));
 	}
 
 	@Test