# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1314964761 -7200
# Node ID 81e9a3c9bafee5baed13aba6d352e1cdb26350f6
# Parent  35125450c8045aa4f8158ca4bb11342ed750c8cc
Utilize IntMap when caching manifest revisions

diff -r 35125450c804 -r 81e9a3c9bafe cmdline/org/tmatesoft/hg/console/Main.java
--- a/cmdline/org/tmatesoft/hg/console/Main.java	Fri Sep 02 13:40:09 2011 +0200
+++ b/cmdline/org/tmatesoft/hg/console/Main.java	Fri Sep 02 13:59:21 2011 +0200
@@ -49,7 +49,6 @@
 import org.tmatesoft.hg.repo.HgSubrepoLocation.Kind;
 import org.tmatesoft.hg.repo.HgWorkingCopyStatusCollector;
 import org.tmatesoft.hg.repo.HgChangelog.RawChangeset;
-import org.tmatesoft.hg.util.FileIterator;
 import org.tmatesoft.hg.util.FileWalker;
 import org.tmatesoft.hg.util.Pair;
 import org.tmatesoft.hg.util.Path;
diff -r 35125450c804 -r 81e9a3c9bafe src/org/tmatesoft/hg/internal/IntMap.java
--- a/src/org/tmatesoft/hg/internal/IntMap.java	Fri Sep 02 13:40:09 2011 +0200
+++ b/src/org/tmatesoft/hg/internal/IntMap.java	Fri Sep 02 13:59:21 2011 +0200
@@ -109,6 +109,39 @@
 		}
 		return null;
 	}
+	
+	public void remove(int key) {
+		int ix = binarySearch(keys, size, key);
+		if (ix >= 0) {
+			if (ix <= size - 1) {
+				System.arraycopy(keys, ix+1, keys, ix, size - ix - 1);
+				System.arraycopy(values, ix+1, values, ix, size - ix - 1);
+			} // if ix points to last element, no reason to attempt a copy
+			size--;
+			keys[size] = 0;
+			values[size] = null;
+		}
+	}
+	
+	/**
+	 * Forget first N entries (in natural order) in the map.
+	 */
+	@Experimental
+	public void removeFromStart(int count) {
+		if (count > 0 && count <= size) {
+			if (count < size) {
+				System.arraycopy(keys, count, keys, 0, size - count);
+				System.arraycopy(values, count, values, 0, size - count);
+			}
+			for (int i = size - count; i < size; i++) {
+				keys[i] = 0;
+				values[i] = null;
+			}
+			size -= count;
+		} 
+	}
+	
+	
 
 	// copy of Arrays.binarySearch, with upper search limit as argument
 	private static int binarySearch(int[] a, int high, int key) {
diff -r 35125450c804 -r 81e9a3c9bafe src/org/tmatesoft/hg/repo/HgStatusCollector.java
--- a/src/org/tmatesoft/hg/repo/HgStatusCollector.java	Fri Sep 02 13:40:09 2011 +0200
+++ b/src/org/tmatesoft/hg/repo/HgStatusCollector.java	Fri Sep 02 13:59:21 2011 +0200
@@ -25,12 +25,11 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.SortedMap;
-import java.util.TreeMap;
 import java.util.TreeSet;
 
 import org.tmatesoft.hg.core.HgDataStreamException;
 import org.tmatesoft.hg.core.Nodeid;
+import org.tmatesoft.hg.internal.IntMap;
 import org.tmatesoft.hg.internal.ManifestRevision;
 import org.tmatesoft.hg.internal.Pool;
 import org.tmatesoft.hg.util.Path;
@@ -47,7 +46,7 @@
 public class HgStatusCollector {
 
 	private final HgRepository repo;
-	private final SortedMap<Integer, ManifestRevision> cache; // sparse array, in fact
+	private final IntMap<ManifestRevision> cache; // sparse array, in fact
 	// with cpython repository, ~70 000 changes, complete Log (direct out, no reverse) output 
 	// no cache limit, no nodeids and fname caching - OOME on changeset 1035
 	// no cache limit, but with cached nodeids and filenames - 1730+
@@ -62,7 +61,7 @@
 
 	public HgStatusCollector(HgRepository hgRepo) {
 		this.repo = hgRepo;
-		cache = new TreeMap<Integer, ManifestRevision>();
+		cache = new IntMap<ManifestRevision>(cacheMaxSize);
 		cacheNodes = new Pool<Nodeid>();
 		cacheFilenames = new Pool<String>();
 
@@ -81,10 +80,7 @@
 			if (rev == -1) {
 				return emptyFakeState;
 			}
-			while (cache.size() > cacheMaxSize) {
-				// assume usually we go from oldest to newest, hence remove oldest as most likely to be no longer necessary
-				cache.remove(cache.firstKey());
-			}
+			ensureCacheSize();
 			i = new ManifestRevision(cacheNodes, cacheFilenames);
 			cache.put(rev, i);
 			repo.getManifest().walk(rev, rev, i);
@@ -96,11 +92,15 @@
 		return cache.containsKey(revision) || revision == -1;
 	}
 	
+	private void ensureCacheSize() {
+		if (cache.size() > cacheMaxSize) {
+			// assume usually we go from oldest to newest, hence remove oldest as most likely to be no longer necessary
+			cache.removeFromStart(cache.size() - cacheMaxSize + 1 /* room for new element */);
+		}
+	}
+	
 	private void initCacheRange(int minRev, int maxRev) {
-		while (cache.size() > cacheMaxSize) {
-			// assume usually we go from oldest to newest, hence remove oldest as most likely to be no longer necessary
-			cache.remove(cache.firstKey());
-		}
+		ensureCacheSize();
 		repo.getManifest().walk(minRev, maxRev, new HgManifest.Inspector() {
 			private ManifestRevision delegate;
 			private boolean cacheHit; // range may include revisions we already know about, do not re-create them