Create new RefList and RefMap utility types

These types can be used by RefDatabase implementations to manage
the collection.

A RefList stores items sorted by their name, and is an immutable
type using copy-on-write semantics to perform modifications to
the collection.  Binary search is used to locate an existing item
by name, or to locate the proper insertion position if an item does
not exist.

A RefMap can merge up to 3 RefList collections at once during its
entry iteration, allowing items in the resolved or loose RefList
to override items by the same name in the packed RefList.

The RefMap's goal is O(log N) lookup time, and O(N) iteration time,
which is suitable for returning from a RefDatabase.  By relying on
the immutable RefList we might be able to make map construction
nearly constant, making Repository.getAllRefs() an inexpensive
operation if the caches are current.  Since modification is not
common, changes require up to O(N + log N) time to copy the internal
list and collapse or expand the list's array.  As most changes
are made to the loose collection and not the packed collection,
in practice most changes would require less than the full O(N)
time, due to a significantly smaller N in the loose list.

Almost complete test coverage is included in the corresponding
unit tests.  A handful of methods on RefMap are not tested in this
change, as writing the proper test depends on a future refactoring
of how the Ref class represents symbolic reference names.

Change-Id: Ic2095274000336556f719edd75a5c5dd6dd1d857
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

2 files changed, 813 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java
new file mode 100644
index 0000000000..c9522341b0
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java
@@ -0,0 +1,431 @@
+/*
+ * Copyright (C) 2010, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.util;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import junit.framework.TestCase;
+
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Ref;
+
+public class RefListTest extends TestCase {
+	private static final ObjectId ID = ObjectId
+			.fromString("41eb0d88f833b558bddeb269b7ab77399cdf98ed");
+
+	private static final Ref REF_A = newRef("A");
+
+	private static final Ref REF_B = newRef("B");
+
+	private static final Ref REF_c = newRef("c");
+
+	public void testEmpty() {
+		RefList<Ref> list = RefList.emptyList();
+		assertEquals(0, list.size());
+		assertTrue(list.isEmpty());
+		assertFalse(list.iterator().hasNext());
+		assertEquals(-1, list.find("a"));
+		assertEquals(-1, list.find("z"));
+		assertFalse(list.contains("a"));
+		assertNull(list.get("a"));
+		try {
+			list.get(0);
+			fail("RefList.emptyList should have 0 element array");
+		} catch (ArrayIndexOutOfBoundsException err) {
+			// expected
+		}
+	}
+
+	public void testEmptyBuilder() {
+		RefList<Ref> list = new RefList.Builder<Ref>().toRefList();
+		assertEquals(0, list.size());
+		assertFalse(list.iterator().hasNext());
+		assertEquals(-1, list.find("a"));
+		assertEquals(-1, list.find("z"));
+		assertFalse(list.contains("a"));
+		assertNull(list.get("a"));
+		assertTrue(list.asList().isEmpty());
+		assertEquals("[]", list.toString());
+
+		// default array capacity should be 16, with no bounds checking.
+		assertNull(list.get(16 - 1));
+		try {
+			list.get(16);
+			fail("default RefList should have 16 element array");
+		} catch (ArrayIndexOutOfBoundsException err) {
+			// expected
+		}
+	}
+
+	public void testBuilder_AddThenSort() {
+		RefList.Builder<Ref> builder = new RefList.Builder<Ref>(1);
+		builder.add(REF_B);
+		builder.add(REF_A);
+
+		RefList<Ref> list = builder.toRefList();
+		assertEquals(2, list.size());
+		assertSame(REF_B, list.get(0));
+		assertSame(REF_A, list.get(1));
+
+		builder.sort();
+		list = builder.toRefList();
+		assertEquals(2, list.size());
+		assertSame(REF_A, list.get(0));
+		assertSame(REF_B, list.get(1));
+	}
+
+	public void testBuilder_AddAll() {
+		RefList.Builder<Ref> builder = new RefList.Builder<Ref>(1);
+		Ref[] src = { REF_A, REF_B, REF_c, REF_A };
+		builder.addAll(src, 1, 2);
+
+		RefList<Ref> list = builder.toRefList();
+		assertEquals(2, list.size());
+		assertSame(REF_B, list.get(0));
+		assertSame(REF_c, list.get(1));
+	}
+
+	public void testBuilder_Set() {
+		RefList.Builder<Ref> builder = new RefList.Builder<Ref>();
+		builder.add(REF_A);
+		builder.add(REF_A);
+
+		assertEquals(2, builder.size());
+		assertSame(REF_A, builder.get(0));
+		assertSame(REF_A, builder.get(1));
+
+		RefList<Ref> list = builder.toRefList();
+		assertEquals(2, list.size());
+		assertSame(REF_A, list.get(0));
+		assertSame(REF_A, list.get(1));
+		builder.set(1, REF_B);
+
+		list = builder.toRefList();
+		assertEquals(2, list.size());
+		assertSame(REF_A, list.get(0));
+		assertSame(REF_B, list.get(1));
+	}
+
+	public void testBuilder_Remove() {
+		RefList.Builder<Ref> builder = new RefList.Builder<Ref>();
+		builder.add(REF_A);
+		builder.add(REF_B);
+		builder.remove(0);
+
+		assertEquals(1, builder.size());
+		assertSame(REF_B, builder.get(0));
+	}
+
+	public void testSet() {
+		RefList<Ref> one = toList(REF_A, REF_A);
+		RefList<Ref> two = one.set(1, REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified
+		assertEquals(2, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_A, one.get(1));
+
+		// but two is
+		assertEquals(2, two.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_B, two.get(1));
+	}
+
+	public void testAddToEmptyList() {
+		RefList<Ref> one = toList();
+		RefList<Ref> two = one.add(0, REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(0, one.size());
+		assertEquals(1, two.size());
+		assertFalse(two.isEmpty());
+		assertSame(REF_B, two.get(0));
+	}
+
+	public void testAddToFrontOfList() {
+		RefList<Ref> one = toList(REF_A);
+		RefList<Ref> two = one.add(0, REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(1, one.size());
+		assertSame(REF_A, one.get(0));
+		assertEquals(2, two.size());
+		assertSame(REF_B, two.get(0));
+		assertSame(REF_A, two.get(1));
+	}
+
+	public void testAddToEndOfList() {
+		RefList<Ref> one = toList(REF_A);
+		RefList<Ref> two = one.add(1, REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(1, one.size());
+		assertSame(REF_A, one.get(0));
+		assertEquals(2, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_B, two.get(1));
+	}
+
+	public void testAddToMiddleOfListByInsertionPosition() {
+		RefList<Ref> one = toList(REF_A, REF_c);
+
+		assertEquals(-2, one.find(REF_B.getName()));
+
+		RefList<Ref> two = one.add(one.find(REF_B.getName()), REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(2, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_c, one.get(1));
+
+		assertEquals(3, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_B, two.get(1));
+		assertSame(REF_c, two.get(2));
+	}
+
+	public void testPutNewEntry() {
+		RefList<Ref> one = toList(REF_A, REF_c);
+		RefList<Ref> two = one.put(REF_B);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(2, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_c, one.get(1));
+
+		assertEquals(3, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_B, two.get(1));
+		assertSame(REF_c, two.get(2));
+	}
+
+	public void testPutReplaceEntry() {
+		Ref otherc = newRef(REF_c.getName());
+		assertNotSame(REF_c, otherc);
+
+		RefList<Ref> one = toList(REF_A, REF_c);
+		RefList<Ref> two = one.put(otherc);
+		assertNotSame(one, two);
+
+		// one is not modified, but two is
+		assertEquals(2, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_c, one.get(1));
+
+		assertEquals(2, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(otherc, two.get(1));
+	}
+
+	public void testRemoveFrontOfList() {
+		RefList<Ref> one = toList(REF_A, REF_B, REF_c);
+		RefList<Ref> two = one.remove(0);
+		assertNotSame(one, two);
+
+		assertEquals(3, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_B, one.get(1));
+		assertSame(REF_c, one.get(2));
+
+		assertEquals(2, two.size());
+		assertSame(REF_B, two.get(0));
+		assertSame(REF_c, two.get(1));
+	}
+
+	public void testRemoveMiddleOfList() {
+		RefList<Ref> one = toList(REF_A, REF_B, REF_c);
+		RefList<Ref> two = one.remove(1);
+		assertNotSame(one, two);
+
+		assertEquals(3, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_B, one.get(1));
+		assertSame(REF_c, one.get(2));
+
+		assertEquals(2, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_c, two.get(1));
+	}
+
+	public void testRemoveEndOfList() {
+		RefList<Ref> one = toList(REF_A, REF_B, REF_c);
+		RefList<Ref> two = one.remove(2);
+		assertNotSame(one, two);
+
+		assertEquals(3, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_B, one.get(1));
+		assertSame(REF_c, one.get(2));
+
+		assertEquals(2, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_B, two.get(1));
+	}
+
+	public void testRemoveMakesEmpty() {
+		RefList<Ref> one = toList(REF_A);
+		RefList<Ref> two = one.remove(1);
+		assertNotSame(one, two);
+		assertSame(two, RefList.emptyList());
+	}
+
+	public void testToString() {
+		StringBuilder exp = new StringBuilder();
+		exp.append("[");
+		exp.append(REF_A);
+		exp.append(", ");
+		exp.append(REF_B);
+		exp.append("]");
+
+		RefList<Ref> list = toList(REF_A, REF_B);
+		assertEquals(exp.toString(), list.toString());
+	}
+
+	public void testBuilder_ToString() {
+		StringBuilder exp = new StringBuilder();
+		exp.append("[");
+		exp.append(REF_A);
+		exp.append(", ");
+		exp.append(REF_B);
+		exp.append("]");
+
+		RefList.Builder<Ref> list = new RefList.Builder<Ref>();
+		list.add(REF_A);
+		list.add(REF_B);
+		assertEquals(exp.toString(), list.toString());
+	}
+
+	public void testFindContainsGet() {
+		RefList<Ref> list = toList(REF_A, REF_B, REF_c);
+
+		assertEquals(0, list.find("A"));
+		assertEquals(1, list.find("B"));
+		assertEquals(2, list.find("c"));
+
+		assertEquals(-1, list.find("0"));
+		assertEquals(-2, list.find("AB"));
+		assertEquals(-3, list.find("a"));
+		assertEquals(-4, list.find("z"));
+
+		assertSame(REF_A, list.get("A"));
+		assertSame(REF_B, list.get("B"));
+		assertSame(REF_c, list.get("c"));
+		assertNull(list.get("AB"));
+		assertNull(list.get("z"));
+
+		assertTrue(list.contains("A"));
+		assertTrue(list.contains("B"));
+		assertTrue(list.contains("c"));
+		assertFalse(list.contains("AB"));
+		assertFalse(list.contains("z"));
+	}
+
+	public void testIterable() {
+		RefList<Ref> list = toList(REF_A, REF_B, REF_c);
+
+		int idx = 0;
+		for (Ref ref : list)
+			assertSame(list.get(idx++), ref);
+		assertEquals(3, idx);
+
+		Iterator<Ref> i = RefList.emptyList().iterator();
+		try {
+			i.next();
+			fail("did not throw NoSuchElementException");
+		} catch (NoSuchElementException err) {
+			// expected
+		}
+
+		i = list.iterator();
+		assertTrue(i.hasNext());
+		assertSame(REF_A, i.next());
+		try {
+			i.remove();
+			fail("did not throw UnsupportedOperationException");
+		} catch (UnsupportedOperationException err) {
+			// expected
+		}
+	}
+
+	public void testCopyLeadingPrefix() {
+		RefList<Ref> one = toList(REF_A, REF_B, REF_c);
+		RefList<Ref> two = one.copy(2).toRefList();
+		assertNotSame(one, two);
+
+		assertEquals(3, one.size());
+		assertSame(REF_A, one.get(0));
+		assertSame(REF_B, one.get(1));
+		assertSame(REF_c, one.get(2));
+
+		assertEquals(2, two.size());
+		assertSame(REF_A, two.get(0));
+		assertSame(REF_B, two.get(1));
+	}
+
+	public void testCopyConstructorReusesArray() {
+		RefList.Builder<Ref> one = new RefList.Builder<Ref>();
+		one.add(REF_A);
+
+		RefList<Ref> two = new RefList<Ref>(one.toRefList());
+		one.set(0, REF_B);
+		assertSame(REF_B, two.get(0));
+	}
+
+	private RefList<Ref> toList(Ref... refs) {
+		RefList.Builder<Ref> b = new RefList.Builder<Ref>(refs.length);
+		b.addAll(refs, 0, refs.length);
+		return b.toRefList();
+	}
+
+	private static Ref newRef(final String name) {
+		return new Ref(Ref.Storage.LOOSE, name, ID);
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java
new file mode 100644
index 0000000000..6ce206e013
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java
@@ -0,0 +1,382 @@
+/*
+ * Copyright (C) 2010, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.util;
+
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+import junit.framework.TestCase;
+
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Ref;
+
+public class RefMapTest extends TestCase {
+	private static final ObjectId ID_ONE = ObjectId
+			.fromString("41eb0d88f833b558bddeb269b7ab77399cdf98ed");
+
+	private static final ObjectId ID_TWO = ObjectId
+			.fromString("698dd0b8d0c299f080559a1cffc7fe029479a408");
+
+	private RefList<Ref> packed;
+
+	private RefList<Ref> loose;
+
+	private RefList<Ref> resolved;
+
+	protected void setUp() throws Exception {
+		super.setUp();
+		packed = RefList.emptyList();
+		loose = RefList.emptyList();
+		resolved = RefList.emptyList();
+	}
+
+	public void testEmpty_NoPrefix1() {
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertTrue(map.isEmpty()); // before size was computed
+		assertEquals(0, map.size());
+		assertTrue(map.isEmpty()); // after size was computed
+
+		assertFalse(map.entrySet().iterator().hasNext());
+		assertFalse(map.keySet().iterator().hasNext());
+		assertFalse(map.containsKey("a"));
+		assertNull(map.get("a"));
+	}
+
+	public void testEmpty_NoPrefix2() {
+		RefMap map = new RefMap();
+		assertTrue(map.isEmpty()); // before size was computed
+		assertEquals(0, map.size());
+		assertTrue(map.isEmpty()); // after size was computed
+
+		assertFalse(map.entrySet().iterator().hasNext());
+		assertFalse(map.keySet().iterator().hasNext());
+		assertFalse(map.containsKey("a"));
+		assertNull(map.get("a"));
+	}
+
+	public void testNotEmpty_NoPrefix() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		packed = toList(master);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertFalse(map.isEmpty()); // before size was computed
+		assertEquals(1, map.size());
+		assertFalse(map.isEmpty()); // after size was computed
+		assertSame(master, map.values().iterator().next());
+	}
+
+	public void testEmpty_WithPrefix() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		packed = toList(master);
+
+		RefMap map = new RefMap("refs/tags/", packed, loose, resolved);
+		assertTrue(map.isEmpty()); // before size was computed
+		assertEquals(0, map.size());
+		assertTrue(map.isEmpty()); // after size was computed
+
+		assertFalse(map.entrySet().iterator().hasNext());
+		assertFalse(map.keySet().iterator().hasNext());
+	}
+
+	public void testNotEmpty_WithPrefix() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		packed = toList(master);
+
+		RefMap map = new RefMap("refs/heads/", packed, loose, resolved);
+		assertFalse(map.isEmpty()); // before size was computed
+		assertEquals(1, map.size());
+		assertFalse(map.isEmpty()); // after size was computed
+		assertSame(master, map.values().iterator().next());
+	}
+
+	public void testClear() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		loose = toList(master);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertSame(master, map.get("refs/heads/master"));
+
+		map.clear();
+		assertNull(map.get("refs/heads/master"));
+		assertTrue(map.isEmpty());
+		assertEquals(0, map.size());
+	}
+
+	public void testIterator_RefusesRemove() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		loose = toList(master);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		Iterator<Ref> itr = map.values().iterator();
+		assertTrue(itr.hasNext());
+		assertSame(master, itr.next());
+		try {
+			itr.remove();
+			fail("iterator allowed remove");
+		} catch (UnsupportedOperationException err) {
+			// expected
+		}
+	}
+
+	public void testIterator_FailsAtEnd() {
+		final Ref master = newRef("refs/heads/master", ID_ONE);
+		loose = toList(master);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		Iterator<Ref> itr = map.values().iterator();
+		assertTrue(itr.hasNext());
+		assertSame(master, itr.next());
+		try {
+			itr.next();
+			fail("iterator allowed next");
+		} catch (NoSuchElementException err) {
+			// expected
+		}
+	}
+
+	public void testMerge_PackedLooseLoose() {
+		final Ref refA = newRef("A", ID_ONE);
+		final Ref refB_ONE = newRef("B", ID_ONE);
+		final Ref refB_TWO = newRef("B", ID_TWO);
+		final Ref refc = newRef("c", ID_ONE);
+
+		packed = toList(refA, refB_ONE);
+		loose = toList(refB_TWO, refc);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertEquals(3, map.size());
+		assertFalse(map.isEmpty());
+		assertTrue(map.containsKey(refA.getName()));
+		assertSame(refA, map.get(refA.getName()));
+
+		// loose overrides packed given same name
+		assertSame(refB_TWO, map.get(refB_ONE.getName()));
+
+		Iterator<Ref> itr = map.values().iterator();
+		assertTrue(itr.hasNext());
+		assertSame(refA, itr.next());
+		assertTrue(itr.hasNext());
+		assertSame(refB_TWO, itr.next());
+		assertTrue(itr.hasNext());
+		assertSame(refc, itr.next());
+		assertFalse(itr.hasNext());
+	}
+
+	public void testMerge_WithPrefix() {
+		final Ref a = newRef("refs/heads/A", ID_ONE);
+		final Ref b = newRef("refs/heads/foo/bar/B", ID_TWO);
+		final Ref c = newRef("refs/heads/foo/rab/C", ID_TWO);
+		final Ref g = newRef("refs/heads/g", ID_ONE);
+		packed = toList(a, b, c, g);
+
+		RefMap map = new RefMap("refs/heads/foo/", packed, loose, resolved);
+		assertEquals(2, map.size());
+
+		assertSame(b, map.get("bar/B"));
+		assertSame(c, map.get("rab/C"));
+		assertNull(map.get("refs/heads/foo/bar/B"));
+		assertNull(map.get("refs/heads/A"));
+
+		assertTrue(map.containsKey("bar/B"));
+		assertTrue(map.containsKey("rab/C"));
+		assertFalse(map.containsKey("refs/heads/foo/bar/B"));
+		assertFalse(map.containsKey("refs/heads/A"));
+
+		Iterator<Map.Entry<String, Ref>> itr = map.entrySet().iterator();
+		Map.Entry<String, Ref> ent;
+		assertTrue(itr.hasNext());
+		ent = itr.next();
+		assertEquals("bar/B", ent.getKey());
+		assertSame(b, ent.getValue());
+		assertTrue(itr.hasNext());
+		ent = itr.next();
+		assertEquals("rab/C", ent.getKey());
+		assertSame(c, ent.getValue());
+		assertFalse(itr.hasNext());
+	}
+
+	public void testPut_KeyMustMatchName_NoPrefix() {
+		final Ref refA = newRef("refs/heads/A", ID_ONE);
+		RefMap map = new RefMap("", packed, loose, resolved);
+		try {
+			map.put("FOO", refA);
+			fail("map accepted invalid key/value pair");
+		} catch (IllegalArgumentException err) {
+			// expected
+		}
+	}
+
+	public void testPut_KeyMustMatchName_WithPrefix() {
+		final Ref refA = newRef("refs/heads/A", ID_ONE);
+		RefMap map = new RefMap("refs/heads/", packed, loose, resolved);
+		try {
+			map.put("FOO", refA);
+			fail("map accepted invalid key/value pair");
+		} catch (IllegalArgumentException err) {
+			// expected
+		}
+	}
+
+	public void testPut_NoPrefix() {
+		final Ref refA_one = newRef("refs/heads/A", ID_ONE);
+		final Ref refA_two = newRef("refs/heads/A", ID_TWO);
+
+		packed = toList(refA_one);
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertSame(refA_one, map.get(refA_one.getName()));
+		assertSame(refA_one, map.put(refA_one.getName(), refA_two));
+
+		// map changed, but packed, loose did not
+		assertSame(refA_two, map.get(refA_one.getName()));
+		assertSame(refA_one, packed.get(0));
+		assertEquals(0, loose.size());
+
+		assertSame(refA_two, map.put(refA_one.getName(), refA_one));
+		assertSame(refA_one, map.get(refA_one.getName()));
+	}
+
+	public void testPut_WithPrefix() {
+		final Ref refA_one = newRef("refs/heads/A", ID_ONE);
+		final Ref refA_two = newRef("refs/heads/A", ID_TWO);
+
+		packed = toList(refA_one);
+
+		RefMap map = new RefMap("refs/heads/", packed, loose, resolved);
+		assertSame(refA_one, map.get("A"));
+		assertSame(refA_one, map.put("A", refA_two));
+
+		// map changed, but packed, loose did not
+		assertSame(refA_two, map.get("A"));
+		assertSame(refA_one, packed.get(0));
+		assertEquals(0, loose.size());
+
+		assertSame(refA_two, map.put("A", refA_one));
+		assertSame(refA_one, map.get("A"));
+	}
+
+	public void testToString_NoPrefix() {
+		final Ref a = newRef("refs/heads/A", ID_ONE);
+		final Ref b = newRef("refs/heads/B", ID_TWO);
+
+		packed = toList(a, b);
+
+		StringBuilder exp = new StringBuilder();
+		exp.append("[");
+		exp.append(a.toString());
+		exp.append(", ");
+		exp.append(b.toString());
+		exp.append("]");
+
+		RefMap map = new RefMap("", packed, loose, resolved);
+		assertEquals(exp.toString(), map.toString());
+	}
+
+	public void testToString_WithPrefix() {
+		final Ref a = newRef("refs/heads/A", ID_ONE);
+		final Ref b = newRef("refs/heads/foo/B", ID_TWO);
+		final Ref c = newRef("refs/heads/foo/C", ID_TWO);
+		final Ref g = newRef("refs/heads/g", ID_ONE);
+
+		packed = toList(a, b, c, g);
+
+		StringBuilder exp = new StringBuilder();
+		exp.append("[");
+		exp.append(b.toString());
+		exp.append(", ");
+		exp.append(c.toString());
+		exp.append("]");
+
+		RefMap map = new RefMap("refs/heads/foo/", packed, loose, resolved);
+		assertEquals(exp.toString(), map.toString());
+	}
+
+	public void testEntryType() {
+		final Ref a = newRef("refs/heads/A", ID_ONE);
+		final Ref b = newRef("refs/heads/B", ID_TWO);
+
+		packed = toList(a, b);
+
+		RefMap map = new RefMap("refs/heads/", packed, loose, resolved);
+		Iterator<Map.Entry<String, Ref>> itr = map.entrySet().iterator();
+		Map.Entry<String, Ref> ent_a = itr.next();
+		Map.Entry<String, Ref> ent_b = itr.next();
+
+		assertEquals(ent_a.hashCode(), "A".hashCode());
+		assertTrue(ent_a.equals(ent_a));
+		assertFalse(ent_a.equals(ent_b));
+
+		assertEquals(a.toString(), ent_a.toString());
+	}
+
+	public void testEntryTypeSet() {
+		final Ref refA_one = newRef("refs/heads/A", ID_ONE);
+		final Ref refA_two = newRef("refs/heads/A", ID_TWO);
+
+		packed = toList(refA_one);
+
+		RefMap map = new RefMap("refs/heads/", packed, loose, resolved);
+		assertSame(refA_one, map.get("A"));
+
+		Map.Entry<String, Ref> ent = map.entrySet().iterator().next();
+		assertEquals("A", ent.getKey());
+		assertSame(refA_one, ent.getValue());
+
+		assertSame(refA_one, ent.setValue(refA_two));
+		assertSame(refA_two, ent.getValue());
+		assertSame(refA_two, map.get("A"));
+		assertEquals(1, map.size());
+	}
+
+	private RefList<Ref> toList(Ref... refs) {
+		RefList.Builder<Ref> b = new RefList.Builder<Ref>(refs.length);
+		b.addAll(refs, 0, refs.length);
+		return b.toRefList();
+	}
+
+	private static Ref newRef(String name, ObjectId id) {
+		return new Ref(Ref.Storage.LOOSE, name, id);
+	}
+}