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@432: import static org.tmatesoft.hg.repo.HgRepository.TIP;
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@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@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@432: 	private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
tikhomirov@432: 	private Nodeid[] sorted; // for binary search
tikhomirov@646: 	private int[] sorted2natural; // indexes in sorted to indexes in sequential
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@432: 	private final T revlog;
tikhomirov@656: 	private IntMap<Nodeid> heads;
tikhomirov@656: 	private BitSet headsBitSet; // 1 indicates revision got children, != null only during init;
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@628: 	 * Prepare the map 
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@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@432: 		sorted = new Nodeid[revisionCount];
tikhomirov@656: 		headsBitSet = new BitSet(revisionCount);
tikhomirov@432: 		revlog.indexWalk(0, TIP, this);
tikhomirov@432: 		Arrays.sort(sorted);
tikhomirov@653: 		// FIXME use ArrayHelper instead
tikhomirov@432: 		sorted2natural = new int[revisionCount];
tikhomirov@432: 		for (int i = 0; i < revisionCount; i++) {
tikhomirov@432: 			Nodeid n = sequential[i];
tikhomirov@432: 			int x = Arrays.binarySearch(sorted, n);
tikhomirov@432: 			assertSortedIndex(x);
tikhomirov@432: 			sorted2natural[x] = i;
tikhomirov@432: 		}
tikhomirov@656: 		// no reason to keep BitSet, number of heads is usually small
tikhomirov@656: 		IntMap<Nodeid> _heads = new IntMap<Nodeid>(headsBitSet.size() - 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@432: 	private void assertSortedIndex(int x) {
tikhomirov@432: 		if (x < 0) {
tikhomirov@432: 			throw new HgInvalidStateException(String.format("Bad index", 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@432: 		return Arrays.binarySearch(sorted, 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@432: 		int x = Arrays.binarySearch(sorted, nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@432: 		int i = sorted2natural[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@432: 		int x = Arrays.binarySearch(sorted, nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@432: 		int i = sorted2natural[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@432: 		int x = Arrays.binarySearch(sorted, nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@432: 		int i = sorted2natural[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@432: 			int x = Arrays.binarySearch(sorted, r);
tikhomirov@432: 			assertSortedIndex(x);
tikhomirov@432: 			int i = sorted2natural[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@656: 	public long AAA = 0;
tikhomirov@656: 	
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@432: 		int x = Arrays.binarySearch(sorted, nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@432: 		nid = sorted[x]; // canonical instance
tikhomirov@432: 		int start = sorted2natural[x];
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@656: 			AAA++;
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@432: 		int x = Arrays.binarySearch(sorted, nid);
tikhomirov@432: 		assertSortedIndex(x);
tikhomirov@432: 		int i = sorted2natural[x];
tikhomirov@652: 		return hasChildren(i);
tikhomirov@432: 	}
tikhomirov@645: 
tikhomirov@645: 	/**
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@646: 		int x = Arrays.binarySearch(sorted, root);
tikhomirov@646: 		assertSortedIndex(x);
tikhomirov@646: 		root = sorted[x]; // canonical instance
tikhomirov@652: 		final int start = sorted2natural[x];
tikhomirov@652: 		if (!hasChildren(start)) {
tikhomirov@652: 			return false; // root got no children at all
tikhomirov@652: 		}
tikhomirov@646: 		int y = Arrays.binarySearch(sorted, wannaBeChild);
tikhomirov@652: 		if (y < 0) {
tikhomirov@652: 			return false; // not found
tikhomirov@646: 		}
tikhomirov@646: 		wannaBeChild = sorted[y]; // canonicalize
tikhomirov@646: 		final int end = sorted2natural[y];
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@652: 
tikhomirov@652: 	private boolean hasChildren(int sequentialIndex) {
tikhomirov@656: 		return !heads.containsKey(sequentialIndex);
tikhomirov@652: 	}
tikhomirov@432: }