tikhomirov@432: /*
tikhomirov@628:  * Copyright (c) 2011-2013 TMate Software Ltd
tikhomirov@432:  *  
tikhomirov@432:  * This program is free software; you can redistribute it and/or modify
tikhomirov@432:  * it under the terms of the GNU General Public License as published by
tikhomirov@432:  * the Free Software Foundation; version 2 of the License.
tikhomirov@432:  *
tikhomirov@432:  * This program is distributed in the hope that it will be useful,
tikhomirov@432:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@432:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@432:  * GNU General Public License for more details.
tikhomirov@432:  *
tikhomirov@432:  * For information on how to redistribute this software under
tikhomirov@432:  * the terms of a license other than GNU General Public License
tikhomirov@432:  * contact TMate Software at support@hg4j.com
tikhomirov@432:  */
tikhomirov@432: package org.tmatesoft.hg.repo;
tikhomirov@432: 
tikhomirov@652: import java.util.ArrayList;
tikhomirov@432: import java.util.Arrays;
tikhomirov@652: import java.util.BitSet;
tikhomirov@432: import java.util.Collection;
tikhomirov@645: import java.util.Collections;
tikhomirov@432: import java.util.HashSet;
tikhomirov@432: import java.util.LinkedList;
tikhomirov@432: import java.util.List;
tikhomirov@432: 
tikhomirov@432: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@657: import org.tmatesoft.hg.internal.ArrayHelper;
tikhomirov@656: import org.tmatesoft.hg.internal.IntMap;
tikhomirov@432: import org.tmatesoft.hg.repo.Revlog.ParentInspector;
tikhomirov@432: 
tikhomirov@432: /**
tikhomirov@432:  * Helper class to deal with parent-child relationship between revisions <i>en masse</i>.
tikhomirov@432:  * Works in terms of {@link Nodeid nodeids}, there's no need to deal with revision indexes. 
tikhomirov@432:  * For a given revision, answers questions like "who's my parent and what are my immediate children".
tikhomirov@432:  * 
tikhomirov@432:  * <p>Comes handy when multiple revisions are analyzed and distinct {@link Revlog#parents(int, int[], byte[], byte[])} 
tikhomirov@432:  * queries are ineffective. 
tikhomirov@432:  * 
tikhomirov@432:  * <p>Next code snippet shows typical use: 
tikhomirov@432:  * <pre>
tikhomirov@432:  *   HgChangelog clog = repo.getChangelog();
tikhomirov@432:  *   ParentWalker&lt;HgChangelog> pw = new ParentWalker&lt;HgChangelog>(clog);
tikhomirov@432:  *   pw.init();
tikhomirov@432:  *   
tikhomirov@432:  *   Nodeid me = Nodeid.fromAscii("...");
tikhomirov@432:  *   List<Nodei> immediateChildren = pw.directChildren(me);
tikhomirov@432:  * </pre>
tikhomirov@432:  * 
tikhomirov@668:  * <p>Note, this map represents a snapshot of repository state at specific point, and is not automatically
tikhomirov@668:  * updated/refreshed along with repository changes. I.e. any revision committed after this map was initialized
tikhomirov@668:  * won't be recognized as known.
tikhomirov@432:  * 
tikhomirov@432:  * <p> Perhaps, later may add alternative way to access (and reuse) map instance, Revlog#getParentWalker(), 
tikhomirov@432:  * that instantiates and initializes ParentWalker, and keep SoftReference to allow its reuse.
tikhomirov@432:  * 
tikhomirov@433:  * @see HgRevisionMap
tikhomirov@432:  * 
tikhomirov@432:  * @author Artem Tikhomirov
tikhomirov@432:  * @author TMate Software Ltd.
tikhomirov@432:  */
tikhomirov@432: public final class HgParentChildMap<T extends Revlog> implements ParentInspector {
tikhomirov@432: 
tikhomirov@646: 	// IMPORTANT: Nodeid instances shall be shared between all arrays
tikhomirov@646: 
tikhomirov@657: 	private final T revlog;
tikhomirov@432: 	private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
tikhomirov@657: 	private Nodeid[] sorted; // for binary search, just an origin of the actual value in use, the one inside seqWrapper
tikhomirov@652: 	private Nodeid[] firstParent; // parents by natural order (i.e. firstParent[A] is parent of revision with index A)
tikhomirov@432: 	private Nodeid[] secondParent;
tikhomirov@656: 	private IntMap<Nodeid> heads;
tikhomirov@656: 	private BitSet headsBitSet; // 1 indicates revision got children, != null only during init;
tikhomirov@657: 	private HgRevisionMap<T> revisionIndexMap;
tikhomirov@657: 	private ArrayHelper<Nodeid> seqWrapper; 
tikhomirov@432: 
tikhomirov@432: 
tikhomirov@432: 	public HgParentChildMap(T owner) {
tikhomirov@432: 		revlog = owner;
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	public HgRepository getRepo() {
tikhomirov@432: 		return revlog.getRepo();
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	public void next(int revisionNumber, Nodeid revision, int parent1Revision, int parent2Revision, Nodeid nidParent1, Nodeid nidParent2) {
tikhomirov@432: 		if (parent1Revision >= revisionNumber || parent2Revision >= revisionNumber) {
tikhomirov@432: 			throw new IllegalStateException(); // sanity, revisions are sequential
tikhomirov@432: 		}
tikhomirov@432: 		int ix = revisionNumber;
tikhomirov@432: 		sequential[ix] = sorted[ix] = revision;
tikhomirov@432: 		if (parent1Revision != -1) {
tikhomirov@432: 			firstParent[ix] = sequential[parent1Revision];
tikhomirov@656: 			headsBitSet.set(parent1Revision);
tikhomirov@432: 		}
tikhomirov@432: 		if (parent2Revision != -1) { // revlog of DataAccess.java has p2 set when p1 is -1
tikhomirov@432: 			secondParent[ix] = sequential[parent2Revision];
tikhomirov@656: 			headsBitSet.set(parent2Revision);
tikhomirov@432: 		}
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@628: 	/**
tikhomirov@672: 	 * Prepare (initialize or update) the map. Once {@link HgParentChildMap} was initialized, it keeps snapshot
tikhomirov@672: 	 * of repository state. New revisions committed to the repository are not visible. To update the map, call 
tikhomirov@672: 	 * {@link #init()} once again, it tries to refresh in effective way, and to bring in only relevant changes.
tikhomirov@672: 	 *  
tikhomirov@628: 	 * @throws HgInvalidControlFileException if failed to access revlog index/data entry. <em>Runtime exception</em>
tikhomirov@628: 	 * @throws HgRuntimeException subclass thereof to indicate other issues with the library. <em>Runtime exception</em>
tikhomirov@628: 	 */
tikhomirov@628: 	public void init() throws HgRuntimeException {
tikhomirov@432: 		final int revisionCount = revlog.getRevisionCount();
tikhomirov@672: 		Nodeid[] oldSequential = null, oldFirstParent = null, oldSecondParent = null, oldSorted = null;
tikhomirov@672: 		if (sequential != null && sequential.length > 0 && sequential.length < revisionCount) {
tikhomirov@672: 			int lastRecordedRevIndex = sequential.length-1;
tikhomirov@672: 			if (sequential[lastRecordedRevIndex].equals(revlog.getRevision(lastRecordedRevIndex))) {
tikhomirov@672: 				oldSequential = sequential;
tikhomirov@672: 				oldFirstParent = firstParent;
tikhomirov@672: 				oldSecondParent = secondParent;
tikhomirov@672: 				oldSorted = sorted;
tikhomirov@672: 				// not sure if there's a benefit in keeping sorted. assume quite some of them
tikhomirov@672: 				// might end up on the same place and thus minimize rearrangements
tikhomirov@672: 			}
tikhomirov@672: 		}
tikhomirov@432: 		firstParent = new Nodeid[revisionCount];
tikhomirov@652: 		// TODO [post 1.1] Branches/merges are less frequent, and most of secondParent would be -1/null, hence 
tikhomirov@432: 		// IntMap might be better alternative here, but need to carefully analyze (test) whether this brings
tikhomirov@656: 		// real improvement (IntMap has 2n capacity, and element lookup is log(n) instead of array's constant).
tikhomirov@656: 		// FWIW: in cpython's repo, with 70k+ revisions, there are 2618 values in secondParent 
tikhomirov@432: 		secondParent = new Nodeid[revisionCount];
tikhomirov@432: 		//
tikhomirov@432: 		sequential = new Nodeid[revisionCount];
tikhomirov@672: 		sorted = new Nodeid[revisionCount];
tikhomirov@656: 		headsBitSet = new BitSet(revisionCount);
tikhomirov@672: 		if (oldSequential != null) {
tikhomirov@672: 			assert oldFirstParent.length == oldSequential.length;
tikhomirov@672: 			assert oldSecondParent.length == oldSequential.length;
tikhomirov@672: 			assert oldSorted.length == oldSequential.length;
tikhomirov@672: 			System.arraycopy(oldSequential, 0, sequential, 0, oldSequential.length);
tikhomirov@672: 			System.arraycopy(oldFirstParent, 0, firstParent, 0, oldFirstParent.length);
tikhomirov@672: 			System.arraycopy(oldSecondParent, 0, secondParent, 0, oldSecondParent.length);
tikhomirov@672: 			System.arraycopy(oldSorted, 0, sorted, 0, oldSorted.length);
tikhomirov@672: 			// restore old heads so that new one are calculated correctly
tikhomirov@672: 			headsBitSet.set(0, oldSequential.length);
tikhomirov@672: 			for (int headIndex : heads.keys()) {
tikhomirov@672: 				headsBitSet.clear(headIndex);
tikhomirov@672: 			}
tikhomirov@672: 		}
tikhomirov@672: 		revlog.indexWalk(oldSequential == null ? 0 : oldSequential.length, revisionCount-1, this);
tikhomirov@657: 		seqWrapper = new ArrayHelper<Nodeid>(sequential);
tikhomirov@657: 		// HgRevisionMap doesn't keep sorted, try alternative here.
tikhomirov@657: 		// reference this.sorted (not only from ArrayHelper) helps to track ownership in hprof/mem dumps
tikhomirov@657: 		seqWrapper.sort(sorted, false, true);
tikhomirov@656: 		// no reason to keep BitSet, number of heads is usually small
tikhomirov@672: 		IntMap<Nodeid> _heads = new IntMap<Nodeid>(revisionCount - headsBitSet.cardinality());
tikhomirov@656: 		int index = 0;
tikhomirov@656: 		while (index < sequential.length) {
tikhomirov@656: 			index = headsBitSet.nextClearBit(index);
tikhomirov@656: 			// nextClearBit(length-1) gives length when bit is set,
tikhomirov@656: 			// however, last revision can't be a parent of any other, and
tikhomirov@656: 			// the last bit would be always 0, and no AIOOBE 
tikhomirov@656: 			_heads.put(index, sequential[index]);
tikhomirov@656: 			index++;
tikhomirov@656: 		} 
tikhomirov@656: 		headsBitSet = null;
tikhomirov@656: 		heads = _heads;
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@663: 	private static void assertSortedIndex(int x) {
tikhomirov@432: 		if (x < 0) {
tikhomirov@663: 			throw new HgInvalidStateException(String.format("Bad index %d", x));
tikhomirov@432: 		}
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	/**
tikhomirov@432: 	 * Tells whether supplied revision is from the walker's associated revlog.
tikhomirov@432: 	 * Note, {@link Nodeid#NULL}, although implicitly present as parent of a first revision, is not recognized as known. 
tikhomirov@432: 	 * @param nid revision to check, not <code>null</code>
tikhomirov@432: 	 * @return <code>true</code> if revision matches any revision in this revlog
tikhomirov@432: 	 */
tikhomirov@432: 	public boolean knownNode(Nodeid nid) {
tikhomirov@657: 		return seqWrapper.binarySearchSorted(nid) >= 0;
tikhomirov@432: 	}
tikhomirov@432: 
tikhomirov@432: 	/**
tikhomirov@432: 	 * null if none. only known nodes (as per #knownNode) are accepted as arguments
tikhomirov@432: 	 */
tikhomirov@432: 	public Nodeid firstParent(Nodeid nid) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@657: 		int i = seqWrapper.getReverseIndex(x);
tikhomirov@432: 		return firstParent[i];
tikhomirov@432: 	}
tikhomirov@432: 
tikhomirov@432: 	// never null, Nodeid.NULL if none known
tikhomirov@432: 	public Nodeid safeFirstParent(Nodeid nid) {
tikhomirov@432: 		Nodeid rv = firstParent(nid);
tikhomirov@432: 		return rv == null ? Nodeid.NULL : rv;
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	public Nodeid secondParent(Nodeid nid) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@657: 		int i = seqWrapper.getReverseIndex(x);
tikhomirov@432: 		return secondParent[i];
tikhomirov@432: 	}
tikhomirov@432: 
tikhomirov@432: 	public Nodeid safeSecondParent(Nodeid nid) {
tikhomirov@432: 		Nodeid rv = secondParent(nid);
tikhomirov@432: 		return rv == null ? Nodeid.NULL : rv;
tikhomirov@432: 	}
tikhomirov@432: 
tikhomirov@432: 	public boolean appendParentsOf(Nodeid nid, Collection<Nodeid> c) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@657: 		int i = seqWrapper.getReverseIndex(x);
tikhomirov@432: 		Nodeid p1 = firstParent[i];
tikhomirov@432: 		boolean modified = false;
tikhomirov@432: 		if (p1 != null) {
tikhomirov@432: 			modified = c.add(p1);
tikhomirov@432: 		}
tikhomirov@432: 		Nodeid p2 = secondParent[i];
tikhomirov@432: 		if (p2 != null) {
tikhomirov@432: 			modified = c.add(p2) || modified;
tikhomirov@432: 		}
tikhomirov@432: 		return modified;
tikhomirov@432: 	}
tikhomirov@432: 
tikhomirov@432: 	// XXX alternative (and perhaps more reliable) approach would be to make a copy of allNodes and remove 
tikhomirov@432: 	// nodes, their parents and so on.
tikhomirov@432: 	
tikhomirov@432: 	// @return ordered collection of all children rooted at supplied nodes. Nodes shall not be descendants of each other!
tikhomirov@432: 	// Nodeids shall belong to this revlog
tikhomirov@650: 	public List<Nodeid> childrenOf(Collection<Nodeid> roots) {
tikhomirov@645: 		if (roots.isEmpty()) {
tikhomirov@645: 			return Collections.emptyList();
tikhomirov@645: 		}
tikhomirov@432: 		HashSet<Nodeid> parents = new HashSet<Nodeid>();
tikhomirov@432: 		LinkedList<Nodeid> result = new LinkedList<Nodeid>();
tikhomirov@432: 		int earliestRevision = Integer.MAX_VALUE;
tikhomirov@432: 		assert sequential.length == firstParent.length && firstParent.length == secondParent.length;
tikhomirov@432: 		// first, find earliest index of roots in question, as there's  no sense 
tikhomirov@432: 		// to check children among nodes prior to branch's root node
tikhomirov@432: 		for (Nodeid r : roots) {
tikhomirov@657: 			int x = seqWrapper.binarySearchSorted(r);
tikhomirov@432: 			assertSortedIndex(x);
tikhomirov@657: 			int i = seqWrapper.getReverseIndex(x);
tikhomirov@432: 			if (i < earliestRevision) {
tikhomirov@432: 				earliestRevision = i;
tikhomirov@432: 			}
tikhomirov@432: 			parents.add(sequential[i]); // add canonical instance in hope equals() is bit faster when can do a ==
tikhomirov@432: 		}
tikhomirov@432: 		for (int i = earliestRevision + 1; i < sequential.length; i++) {
tikhomirov@432: 			if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
tikhomirov@432: 				parents.add(sequential[i]); // to find next child
tikhomirov@432: 				result.add(sequential[i]);
tikhomirov@432: 			}
tikhomirov@432: 		}
tikhomirov@432: 		return result;
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	/**
tikhomirov@432: 	 * @return revisions that have supplied revision as their immediate parent
tikhomirov@432: 	 */
tikhomirov@432: 	public List<Nodeid> directChildren(Nodeid nid) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@657: 		int start = seqWrapper.getReverseIndex(x);
tikhomirov@657: 		nid = sequential[start]; // canonical instance
tikhomirov@653: 		if (!hasChildren(start)) {
tikhomirov@653: 			return Collections.emptyList();
tikhomirov@653: 		}
tikhomirov@656: 		ArrayList<Nodeid> result = new ArrayList<Nodeid>(5);
tikhomirov@432: 		for (int i = start + 1; i < sequential.length; i++) {
tikhomirov@432: 			if (nid == firstParent[i] || nid == secondParent[i]) {
tikhomirov@432: 				result.add(sequential[i]);
tikhomirov@432: 			}
tikhomirov@432: 		}
tikhomirov@432: 		return result;
tikhomirov@432: 	}
tikhomirov@432: 	
tikhomirov@432: 	/**
tikhomirov@432: 	 * @param nid possibly parent node, shall be {@link #knownNode(Nodeid) known} in this revlog.
tikhomirov@432: 	 * @return <code>true</code> if there's any node in this revlog that has specified node as one of its parents. 
tikhomirov@432: 	 */
tikhomirov@432: 	public boolean hasChildren(Nodeid nid) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@657: 		int i = seqWrapper.getReverseIndex(x);
tikhomirov@652: 		return hasChildren(i);
tikhomirov@432: 	}
tikhomirov@659: 
tikhomirov@659: 	/**
tikhomirov@645: 	 * @return all revisions this map knows about
tikhomirov@645: 	 */
tikhomirov@645: 	public List<Nodeid> all() {
tikhomirov@645: 		return Arrays.asList(sequential);
tikhomirov@645: 	}
tikhomirov@646: 
tikhomirov@646: 	/**
tikhomirov@646: 	 * Find out whether a given node is among descendants of another.
tikhomirov@646: 	 * 
tikhomirov@646: 	 * @param root revision to check for being (grand-)*parent of a child
tikhomirov@646: 	 * @param wannaBeChild candidate descendant revision
tikhomirov@646: 	 * @return <code>true</code> if <code>wannaBeChild</code> is among children of <code>root</code>
tikhomirov@646: 	 */
tikhomirov@646: 	public boolean isChild(Nodeid root, Nodeid wannaBeChild) {
tikhomirov@657: 		int x = seqWrapper.binarySearchSorted(root);
tikhomirov@646: 		assertSortedIndex(x);
tikhomirov@657: 		final int start = seqWrapper.getReverseIndex(x);
tikhomirov@657: 		root = sequential[start]; // canonical instance
tikhomirov@652: 		if (!hasChildren(start)) {
tikhomirov@652: 			return false; // root got no children at all
tikhomirov@652: 		}
tikhomirov@657: 		int y = seqWrapper.binarySearchSorted(wannaBeChild);
tikhomirov@652: 		if (y < 0) {
tikhomirov@652: 			return false; // not found
tikhomirov@646: 		}
tikhomirov@657: 		final int end = seqWrapper.getReverseIndex(y);
tikhomirov@657: 		wannaBeChild = sequential[end]; // canonicalize
tikhomirov@652: 		if (end <= start) {
tikhomirov@652: 			return false; // potential child was in repository earlier than root
tikhomirov@652: 		}
tikhomirov@646: 		HashSet<Nodeid> parents = new HashSet<Nodeid>();
tikhomirov@646: 		parents.add(root);
tikhomirov@646: 		for (int i = start + 1; i < end; i++) {
tikhomirov@646: 			if (parents.contains(firstParent[i]) || parents.contains(secondParent[i])) {
tikhomirov@646: 				parents.add(sequential[i]); // collect ancestors line
tikhomirov@646: 			}
tikhomirov@646: 		}
tikhomirov@646: 		return parents.contains(firstParent[end]) || parents.contains(secondParent[end]);
tikhomirov@646: 	}
tikhomirov@652: 	
tikhomirov@652: 	/**
tikhomirov@652: 	 * @return elements of this map that do not have a child recorded therein.
tikhomirov@652: 	 */
tikhomirov@652: 	public Collection<Nodeid> heads() {
tikhomirov@656: 		return heads.values();
tikhomirov@652: 	}
tikhomirov@657: 	
tikhomirov@657: 	/**
tikhomirov@657: 	 * @return map of revision to indexes
tikhomirov@657: 	 */
tikhomirov@657: 	public HgRevisionMap<T> getRevisionMap() {
tikhomirov@657: 		if (revisionIndexMap == null) {
tikhomirov@657: 			revisionIndexMap = new HgRevisionMap<T>(revlog);
tikhomirov@657: 			revisionIndexMap.init(seqWrapper);
tikhomirov@657: 		}
tikhomirov@657: 		return revisionIndexMap;
tikhomirov@657: 	}
tikhomirov@679: 	
tikhomirov@679: 	/**
tikhomirov@679: 	 * @return common ancestor of two revisions
tikhomirov@679: 	 */
tikhomirov@679: 	public Nodeid ancestor(Nodeid r1, Nodeid r2) {
tikhomirov@679: 		if (r1.equals(r2)) {
tikhomirov@679: 			return r1;
tikhomirov@679: 		}
tikhomirov@679: 		BitSet a1 = buildAncestors(r1);
tikhomirov@679: 		BitSet a2 = buildAncestors(r2);
tikhomirov@679: 		// BitSet.and() trims to shorter bitset, it's ok as we are not 
tikhomirov@679: 		// interested in bits that are part of one bitset only
tikhomirov@679: 		a1.and(a2);
tikhomirov@679: 		final int cardinality = a1.cardinality();
tikhomirov@679: 		if (cardinality == 1) {
tikhomirov@679: 			return sequential[a1.nextSetBit(0)];
tikhomirov@679: 		}
tikhomirov@679: 		assert cardinality > 0; // every revision is child of at least rev0
tikhomirov@679: 		final int length = sequential.length;
tikhomirov@679: 		int index = length / 2;
tikhomirov@679: 		int lastBitSet = -1;
tikhomirov@679: 		do {
tikhomirov@679: 			int nextSetBit = a1.nextSetBit(index);
tikhomirov@679: 			int nextIndex;
tikhomirov@679: 			if (nextSetBit == -1) {
tikhomirov@679: 				assert lastBitSet == -1 || lastBitSet <= index;
tikhomirov@679: 				nextIndex = index - (index - (lastBitSet == -1 ? 0 : lastBitSet)) / 2;
tikhomirov@679: 			} else {
tikhomirov@679: 				lastBitSet = nextSetBit;
tikhomirov@679: 				nextIndex = lastBitSet + (length - lastBitSet) / 2;
tikhomirov@679: 			}
tikhomirov@679: 			if (nextIndex == index) {
tikhomirov@679: 				break;
tikhomirov@679: 			}
tikhomirov@679: 			index = nextIndex;
tikhomirov@679: 		} while (true);
tikhomirov@679: 		if (lastBitSet == -1) {
tikhomirov@679: 			assert false; // likely error in the algorithm above (e.g. can't reach index==0)
tikhomirov@679: 			return sequential[0];
tikhomirov@679: 		}
tikhomirov@679: 		return sequential[lastBitSet];
tikhomirov@679: 	}
tikhomirov@652: 
tikhomirov@652: 	private boolean hasChildren(int sequentialIndex) {
tikhomirov@656: 		return !heads.containsKey(sequentialIndex);
tikhomirov@652: 	}
tikhomirov@679: 	
tikhomirov@679: 	private BitSet buildAncestors(Nodeid nid) {
tikhomirov@679: 		int x = seqWrapper.binarySearchSorted(nid);
tikhomirov@679: 		assertSortedIndex(x);
tikhomirov@679: 		int i = seqWrapper.getReverseIndex(x);
tikhomirov@679: 		BitSet rv = new BitSet(sequential.length);
tikhomirov@679: 		HashSet<Nodeid> ancestors = new HashSet<Nodeid>();
tikhomirov@679: 		ancestors.add(nid);
tikhomirov@679: 		do {
tikhomirov@679: 			if (ancestors.contains(sequential[i])) {
tikhomirov@679: 				rv.set(i);
tikhomirov@679: 				if(firstParent[i] != null) {
tikhomirov@679: 					ancestors.add(firstParent[i]);
tikhomirov@679: 				}
tikhomirov@679: 				if (secondParent[i] != null) {
tikhomirov@679: 					ancestors.add(secondParent[i]);
tikhomirov@679: 				}
tikhomirov@679: 			}
tikhomirov@679: 			i--;
tikhomirov@679: 		} while (i >= 0);
tikhomirov@679: 		return rv;
tikhomirov@679: 	}
tikhomirov@432: }