tikhomirov@433: /*
tikhomirov@433:  * Copyright (c) 2011-2012 TMate Software Ltd
tikhomirov@433:  *  
tikhomirov@433:  * This program is free software; you can redistribute it and/or modify
tikhomirov@433:  * it under the terms of the GNU General Public License as published by
tikhomirov@433:  * the Free Software Foundation; version 2 of the License.
tikhomirov@433:  *
tikhomirov@433:  * This program is distributed in the hope that it will be useful,
tikhomirov@433:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@433:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@433:  * GNU General Public License for more details.
tikhomirov@433:  *
tikhomirov@433:  * For information on how to redistribute this software under
tikhomirov@433:  * the terms of a license other than GNU General Public License
tikhomirov@433:  * contact TMate Software at support@hg4j.com
tikhomirov@433:  */
tikhomirov@433: package org.tmatesoft.hg.repo;
tikhomirov@433: 
tikhomirov@433: import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
tikhomirov@433: import static org.tmatesoft.hg.repo.HgRepository.TIP;
tikhomirov@433: 
tikhomirov@433: import java.util.Arrays;
tikhomirov@433: 
tikhomirov@433: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@433: import org.tmatesoft.hg.internal.ArrayHelper;
tikhomirov@433: import org.tmatesoft.hg.repo.Revlog.RevisionInspector;
tikhomirov@433: 
tikhomirov@433: /**
tikhomirov@433:  * Effective int to Nodeid and vice versa translation. It's advised to use this class instead of 
tikhomirov@433:  * multiple {@link Revlog#getRevisionIndex(Nodeid)} calls. Rule of thumb is 20+ calls (given 
tikhomirov@433:  * initialization costs). It's also important to take into account memory consumption, for huge
tikhomirov@433:  * repositories use of this class may pay off only when accessing greatest fraction of all revisions.  
tikhomirov@433:  * 
tikhomirov@433:  * <p>Next code snippet shows instantiation and sample use: 
tikhomirov@433:  * <pre>
tikhomirov@433:  *   RevisionMap<HgChangelog> clogMap = new RevisionMap<HgChangelog>(clog).init();
tikhomirov@433:  *   RevisionMap<HgDataFile> fileMap = new RevisionMap<HgDataFile>(fileNode).init();
tikhomirov@433:  *   
tikhomirov@433:  *   int fileRevIndex = 0;
tikhomirov@433:  *   Nodeid fileRev = fileMap.revision(fileRevIndex);
tikhomirov@433:  *   int csetRevIndex = fileNode.getChangesetRevisionIndex(fileRevIndex);
tikhomirov@433:  *   Nodeid csetRev = clogMap.revision(localCset);
tikhomirov@433:  *   changesetToNodeidMap.put(csetRev, fileRev);
tikhomirov@433:  * </pre>
tikhomirov@433:  * 
tikhomirov@433:  * <p>
tikhomirov@433:  * {@link Revlog#getRevisionIndex(Nodeid)} with straightforward lookup approach performs O(n/2)
tikhomirov@433:  * <p>
tikhomirov@433:  * {@link HgRevisionMap#revisionIndex(Nodeid)} is log(n), plus initialization is O(n) (just once).
tikhomirov@433:  * 
tikhomirov@433:  * @see HgParentChildMap
tikhomirov@433:  * 
tikhomirov@433:  * @author Artem Tikhomirov
tikhomirov@433:  * @author TMate Software Ltd.
tikhomirov@433:  */
tikhomirov@433: public final class HgRevisionMap<T extends Revlog> implements RevisionInspector {
tikhomirov@433: 	/*
tikhomirov@433: 	 * in fact, initialization is much slower as it instantiates Nodeids, while #getRevisionIndex
tikhomirov@433: 	 * compares directly against byte buffer. Measuring cpython with 70k+ gives 3 times difference (47 vs 171)
tikhomirov@433: 	 * for complete changelog iteration. 
tikhomirov@433: 	 */
tikhomirov@433: 	
tikhomirov@433: 	/*
tikhomirov@433: 	 * XXX 3 * (x * 4) bytes. Can I do better?
tikhomirov@433: 	 * It seems, yes. Don't need to keep sorted, always can emulate it with indirect access to sequential through sorted2natural.
tikhomirov@433: 	 * i.e. instead sorted[mid].compareTo(toFind), do sequential[sorted2natural[mid]].compareTo(toFind) 
tikhomirov@433: 	 */
tikhomirov@433: 	private Nodeid[] sequential; // natural repository order, childrenOf rely on ordering
tikhomirov@433: 	private Nodeid[] sorted; // for binary search
tikhomirov@433: 	private int[] sorted2natural;
tikhomirov@433: 	private final T revlog;
tikhomirov@433: 
tikhomirov@433: 	public HgRevisionMap(T owner) {
tikhomirov@433: 		revlog = owner;
tikhomirov@433: 	}
tikhomirov@433: 	
tikhomirov@433: 	public HgRepository getRepo() {
tikhomirov@433: 		return revlog.getRepo();
tikhomirov@433: 	}
tikhomirov@433: 	
tikhomirov@433: 	public void next(int revisionIndex, Nodeid revision, int linkedRevision) {
tikhomirov@433: 		sequential[revisionIndex] = sorted[revisionIndex] = revision;
tikhomirov@433: 	}
tikhomirov@433: 
tikhomirov@433: 	/**
tikhomirov@433: 	 * @return <code>this</code> for convenience.
tikhomirov@433: 	 */
tikhomirov@433: 	public HgRevisionMap<T> init(/*XXX Pool<Nodeid> to reuse nodeids, if possible. */) throws HgInvalidControlFileException{
tikhomirov@433: 		// XXX HgRepository.register((RepoChangeListener) this); // listen to changes in repo, re-init if needed?
tikhomirov@433: 		final int revisionCount = revlog.getRevisionCount();
tikhomirov@433: 		sequential = new Nodeid[revisionCount];
tikhomirov@433: 		sorted = new Nodeid[revisionCount];
tikhomirov@433: 		revlog.indexWalk(0, TIP, this);
tikhomirov@433: 		// next is alternative to Arrays.sort(sorted), and build sorted2natural looking up each element of sequential in sorted.
tikhomirov@433: 		// the way sorted2natural was build is O(n*log n).  
tikhomirov@433: 		final ArrayHelper ah = new ArrayHelper();
tikhomirov@433: 		ah.sort(sorted);
tikhomirov@433: 		// note, values in ArrayHelper#getReversed are 1-based indexes, not 0-based 
tikhomirov@433: 		sorted2natural = ah.getReverse();
tikhomirov@433: 		return this;
tikhomirov@433: 	}
tikhomirov@433: 	
tikhomirov@433: 	public Nodeid revision(int revisionIndex) {
tikhomirov@433: 		return sequential[revisionIndex];
tikhomirov@433: 	}
tikhomirov@433: 	public int revisionIndex(Nodeid revision) {
tikhomirov@433: 		if (revision == null || revision.isNull()) {
tikhomirov@433: 			return BAD_REVISION;
tikhomirov@433: 		}
tikhomirov@433: 		int x = Arrays.binarySearch(sorted, revision);
tikhomirov@433: 		if (x < 0) {
tikhomirov@433: 			return BAD_REVISION;
tikhomirov@433: 		}
tikhomirov@433: 		return sorted2natural[x]-1;
tikhomirov@433: 	}
tikhomirov@433: }