svn commit: r897547 [8/10] - in /hadoop/hbase/branches/0.20_on_hadoop-0.18.3: ./ bin/ conf/ lib/ src/contrib/ src/contrib/ec2/ src/contrib/ec2/bin/ src/contrib/ec2/bin/image/ src/contrib/indexed/ src/contrib/indexed/lib/ src/contrib/indexed/lib/fmpp-0....

[ap...@apache.org]

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestByteArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestByteArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestByteArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestByteArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestByteArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    ByteArrayList test = new ByteArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new ByteArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((byte) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    ByteArrayList original = new ByteArrayList(2);
+    original.add((byte) 1);
+    byte[] values = (byte[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    ByteArrayList copy = new ByteArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (byte) 1);
+    values = (byte[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    ByteArrayList test1a = new ByteArrayList();
+    test1a.add((byte) 1);
+    ByteArrayList test1b = new ByteArrayList();
+    test1b.add((byte) 1);
+    ByteArrayList test2 = new ByteArrayList();
+    test2.add((byte) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(ByteArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    byte[] values = (byte[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    ByteArrayList test = new ByteArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((byte) 1);
+    Assert.assertEquals(test.get(0), (byte) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((byte) 2);
+    Assert.assertEquals(test.get(1), (byte) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((byte) 3);
+    Assert.assertEquals(test.get(2), (byte) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((byte) 4);
+    Assert.assertEquals(test.get(3), (byte) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((byte) 5);
+    Assert.assertEquals(test.get(4), (byte) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        ByteArrayList test = new ByteArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    ByteArrayList test = new ByteArrayList();
+
+    // Test with first value added to list
+    byte testValue = (byte) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (byte) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (byte) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    ByteArrayList test = new ByteArrayList();
+
+    // Test with first value added to list
+    byte testValue = (byte) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (byte) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (byte) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        ByteArrayList test = new ByteArrayList();
+        test.set(index, (byte) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Byte> testData = new ArrayList<Byte>();
+
+    // Test with no content first
+    ByteArrayList test = new ByteArrayList();
+    testData.clear();
+    for (byte item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((byte) 1);
+    testData.clear();
+    for (byte item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(byte) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((byte) 1);
+    testData.clear();
+    for (byte item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(byte) 1, (byte) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    ByteArrayList test = new ByteArrayList();
+    test.add((byte) 1);
+    Assert.assertEquals(test.get(0), (byte) 1);
+    //Assert.assertEquals(test.get(0), (byte) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((byte) 0);
+    test.add((byte) 1);
+    test.add((byte) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (byte) 1);
+    Assert.assertEquals(test.get(0), (byte) 0);
+    Assert.assertEquals(test.get(1), (byte) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    ByteArrayList test = new ByteArrayList();
+    test.insert(0, (byte) 1);
+    Assert.assertEquals(test.get(0), (byte) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (byte) 0);
+    Assert.assertEquals(test.get(0), (byte) 0);
+    Assert.assertEquals(test.get(1), (byte) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (byte) 2);
+    Assert.assertEquals(test.get(0), (byte) 0);
+    Assert.assertEquals(test.get(1), (byte) 2);
+    Assert.assertEquals(test.get(2), (byte) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (byte) 3);
+    Assert.assertEquals(test.get(0), (byte) 0);
+    Assert.assertEquals(test.get(1), (byte) 2);
+    Assert.assertEquals(test.get(2), (byte) 1);
+    Assert.assertEquals(test.get(3), (byte) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    ByteArrayList test = new ByteArrayList();
+    test.add((byte) 1);
+    test.add((byte) 2);
+
+    Assert.assertEquals(test.removeLast(), (byte) 2);
+    Assert.assertEquals(test.get(0), (byte) 1);
+
+    Assert.assertEquals(test.removeLast(), (byte) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        ByteArrayList test = new ByteArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,350 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+
+public class TestCharArrayArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    CharArrayArrayList test = new CharArrayArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new CharArrayArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add(new char[]{5});
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    CharArrayArrayList original = new CharArrayArrayList(2);
+    original.add(new char[]{1});
+    char[][] values = (char[][]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    CharArrayArrayList copy = new CharArrayArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertTrue(Arrays.equals(copy.get(0), new char[]{1}));
+    values = (char[][]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    CharArrayArrayList test1a = new CharArrayArrayList();
+    test1a.add(new char[]{1});
+    CharArrayArrayList test1b = new CharArrayArrayList();
+    test1b.add(new char[]{1});
+    CharArrayArrayList test2 = new CharArrayArrayList();
+    test2.add(new char[]{2});
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(CharArrayArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    char[][] values = (char[][]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    CharArrayArrayList test = new CharArrayArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add(new char[]{1});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{1}));
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add(new char[]{2});
+    Assert.assertTrue(Arrays.equals(test.get(1), new char[]{2}));
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add(new char[]{3});
+    Assert.assertTrue(Arrays.equals(test.get(2), new char[]{3}));
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add(new char[]{4});
+    Assert.assertTrue(Arrays.equals(test.get(3), new char[]{4}));
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add(new char[]{5});
+    Assert.assertTrue(Arrays.equals(test.get(4), new char[]{5}));
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayArrayList test = new CharArrayArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    CharArrayArrayList test = new CharArrayArrayList();
+
+    // Test with first value added to list
+    char[] testValue = new char[]{4, 2, 3};
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = new char[]{4, 3, 2};
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = new char[]{4, 1, 5, 6};
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    CharArrayArrayList test = new CharArrayArrayList();
+
+    // Test with first value added to list
+    char[] testValue = new char[]{4, 2, 3};
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = new char[]{4, 3, 2};
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = new char[]{4, 1, 5, 6};
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayArrayList test = new CharArrayArrayList();
+        test.set(index, new char[]{0});
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<char[]> testData = new ArrayList<char[]>();
+
+    // Test with no content first
+    CharArrayArrayList test = new CharArrayArrayList();
+    testData.clear();
+    for (char[] item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add(new char[]{1});
+    testData.clear();
+    for (char[] item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{new char[]{1}}));
+
+    // Add another value and ensure it is returned
+    test.add(new char[]{1});
+    testData.clear();
+    for (char[] item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{new char[]{1}, new char[]{1}}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    CharArrayArrayList test = new CharArrayArrayList();
+    test.add(new char[]{1});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{1}));
+    //Assert.assertEquals(test.get(0), new char[]{1});
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add(new char[]{0});
+    test.add(new char[]{1});
+    test.add(new char[]{2});
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertTrue(Arrays.equals(test.remove(1), new char[]{1}));
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{0}));
+    Assert.assertTrue(Arrays.equals(test.get(1), new char[]{2}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    CharArrayArrayList test = new CharArrayArrayList();
+    test.insert(0, new char[]{1});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{1}));
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, new char[]{0});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{0}));
+    Assert.assertTrue(Arrays.equals(test.get(1), new char[]{1}));
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, new char[]{2});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{0}));
+    Assert.assertTrue(Arrays.equals(test.get(1), new char[]{2}));
+    Assert.assertTrue(Arrays.equals(test.get(2), new char[]{1}));
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, new char[]{3});
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{0}));
+    Assert.assertTrue(Arrays.equals(test.get(1), new char[]{2}));
+    Assert.assertTrue(Arrays.equals(test.get(2), new char[]{1}));
+    Assert.assertTrue(Arrays.equals(test.get(3), new char[]{3}));
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    CharArrayArrayList test = new CharArrayArrayList();
+    test.add(new char[]{1});
+    test.add(new char[]{2});
+
+    Assert.assertTrue(Arrays.equals(test.removeLast(), new char[]{2}));
+    Assert.assertTrue(Arrays.equals(test.get(0), new char[]{1}));
+
+    Assert.assertTrue(Arrays.equals(test.removeLast(), new char[]{1}));
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayArrayList test = new CharArrayArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestCharArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestCharArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    CharArrayList test = new CharArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new CharArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((char) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    CharArrayList original = new CharArrayList(2);
+    original.add((char) 1);
+    char[] values = (char[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    CharArrayList copy = new CharArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (char) 1);
+    values = (char[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    CharArrayList test1a = new CharArrayList();
+    test1a.add((char) 1);
+    CharArrayList test1b = new CharArrayList();
+    test1b.add((char) 1);
+    CharArrayList test2 = new CharArrayList();
+    test2.add((char) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(CharArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    char[] values = (char[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    CharArrayList test = new CharArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((char) 1);
+    Assert.assertEquals(test.get(0), (char) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((char) 2);
+    Assert.assertEquals(test.get(1), (char) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((char) 3);
+    Assert.assertEquals(test.get(2), (char) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((char) 4);
+    Assert.assertEquals(test.get(3), (char) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((char) 5);
+    Assert.assertEquals(test.get(4), (char) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayList test = new CharArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    CharArrayList test = new CharArrayList();
+
+    // Test with first value added to list
+    char testValue = (char) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (char) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (char) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    CharArrayList test = new CharArrayList();
+
+    // Test with first value added to list
+    char testValue = (char) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (char) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (char) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayList test = new CharArrayList();
+        test.set(index, (char) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Character> testData = new ArrayList<Character>();
+
+    // Test with no content first
+    CharArrayList test = new CharArrayList();
+    testData.clear();
+    for (char item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((char) 1);
+    testData.clear();
+    for (char item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(char) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((char) 1);
+    testData.clear();
+    for (char item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(char) 1, (char) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    CharArrayList test = new CharArrayList();
+    test.add((char) 1);
+    Assert.assertEquals(test.get(0), (char) 1);
+    //Assert.assertEquals(test.get(0), (char) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((char) 0);
+    test.add((char) 1);
+    test.add((char) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (char) 1);
+    Assert.assertEquals(test.get(0), (char) 0);
+    Assert.assertEquals(test.get(1), (char) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    CharArrayList test = new CharArrayList();
+    test.insert(0, (char) 1);
+    Assert.assertEquals(test.get(0), (char) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (char) 0);
+    Assert.assertEquals(test.get(0), (char) 0);
+    Assert.assertEquals(test.get(1), (char) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (char) 2);
+    Assert.assertEquals(test.get(0), (char) 0);
+    Assert.assertEquals(test.get(1), (char) 2);
+    Assert.assertEquals(test.get(2), (char) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (char) 3);
+    Assert.assertEquals(test.get(0), (char) 0);
+    Assert.assertEquals(test.get(1), (char) 2);
+    Assert.assertEquals(test.get(2), (char) 1);
+    Assert.assertEquals(test.get(3), (char) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    CharArrayList test = new CharArrayList();
+    test.add((char) 1);
+    test.add((char) 2);
+
+    Assert.assertEquals(test.removeLast(), (char) 2);
+    Assert.assertEquals(test.get(0), (char) 1);
+
+    Assert.assertEquals(test.removeLast(), (char) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        CharArrayList test = new CharArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestDoubleArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestDoubleArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestDoubleArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestDoubleArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestDoubleArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    DoubleArrayList test = new DoubleArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new DoubleArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((double) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    DoubleArrayList original = new DoubleArrayList(2);
+    original.add((double) 1);
+    double[] values = (double[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    DoubleArrayList copy = new DoubleArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (double) 1);
+    values = (double[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    DoubleArrayList test1a = new DoubleArrayList();
+    test1a.add((double) 1);
+    DoubleArrayList test1b = new DoubleArrayList();
+    test1b.add((double) 1);
+    DoubleArrayList test2 = new DoubleArrayList();
+    test2.add((double) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(DoubleArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    double[] values = (double[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    DoubleArrayList test = new DoubleArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((double) 1);
+    Assert.assertEquals(test.get(0), (double) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((double) 2);
+    Assert.assertEquals(test.get(1), (double) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((double) 3);
+    Assert.assertEquals(test.get(2), (double) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((double) 4);
+    Assert.assertEquals(test.get(3), (double) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((double) 5);
+    Assert.assertEquals(test.get(4), (double) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        DoubleArrayList test = new DoubleArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    DoubleArrayList test = new DoubleArrayList();
+
+    // Test with first value added to list
+    double testValue = (double) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (double) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (double) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    DoubleArrayList test = new DoubleArrayList();
+
+    // Test with first value added to list
+    double testValue = (double) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (double) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (double) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        DoubleArrayList test = new DoubleArrayList();
+        test.set(index, (double) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Double> testData = new ArrayList<Double>();
+
+    // Test with no content first
+    DoubleArrayList test = new DoubleArrayList();
+    testData.clear();
+    for (double item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((double) 1);
+    testData.clear();
+    for (double item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(double) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((double) 1);
+    testData.clear();
+    for (double item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(double) 1, (double) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    DoubleArrayList test = new DoubleArrayList();
+    test.add((double) 1);
+    Assert.assertEquals(test.get(0), (double) 1);
+    //Assert.assertEquals(test.get(0), (double) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((double) 0);
+    test.add((double) 1);
+    test.add((double) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (double) 1);
+    Assert.assertEquals(test.get(0), (double) 0);
+    Assert.assertEquals(test.get(1), (double) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    DoubleArrayList test = new DoubleArrayList();
+    test.insert(0, (double) 1);
+    Assert.assertEquals(test.get(0), (double) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (double) 0);
+    Assert.assertEquals(test.get(0), (double) 0);
+    Assert.assertEquals(test.get(1), (double) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (double) 2);
+    Assert.assertEquals(test.get(0), (double) 0);
+    Assert.assertEquals(test.get(1), (double) 2);
+    Assert.assertEquals(test.get(2), (double) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (double) 3);
+    Assert.assertEquals(test.get(0), (double) 0);
+    Assert.assertEquals(test.get(1), (double) 2);
+    Assert.assertEquals(test.get(2), (double) 1);
+    Assert.assertEquals(test.get(3), (double) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    DoubleArrayList test = new DoubleArrayList();
+    test.add((double) 1);
+    test.add((double) 2);
+
+    Assert.assertEquals(test.removeLast(), (double) 2);
+    Assert.assertEquals(test.get(0), (double) 1);
+
+    Assert.assertEquals(test.removeLast(), (double) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        DoubleArrayList test = new DoubleArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestFloatArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestFloatArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestFloatArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestFloatArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestFloatArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    FloatArrayList test = new FloatArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new FloatArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((float) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    FloatArrayList original = new FloatArrayList(2);
+    original.add((float) 1);
+    float[] values = (float[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    FloatArrayList copy = new FloatArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (float) 1);
+    values = (float[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    FloatArrayList test1a = new FloatArrayList();
+    test1a.add((float) 1);
+    FloatArrayList test1b = new FloatArrayList();
+    test1b.add((float) 1);
+    FloatArrayList test2 = new FloatArrayList();
+    test2.add((float) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(FloatArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    float[] values = (float[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    FloatArrayList test = new FloatArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((float) 1);
+    Assert.assertEquals(test.get(0), (float) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((float) 2);
+    Assert.assertEquals(test.get(1), (float) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((float) 3);
+    Assert.assertEquals(test.get(2), (float) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((float) 4);
+    Assert.assertEquals(test.get(3), (float) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((float) 5);
+    Assert.assertEquals(test.get(4), (float) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        FloatArrayList test = new FloatArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    FloatArrayList test = new FloatArrayList();
+
+    // Test with first value added to list
+    float testValue = (float) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (float) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (float) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    FloatArrayList test = new FloatArrayList();
+
+    // Test with first value added to list
+    float testValue = (float) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (float) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (float) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        FloatArrayList test = new FloatArrayList();
+        test.set(index, (float) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Float> testData = new ArrayList<Float>();
+
+    // Test with no content first
+    FloatArrayList test = new FloatArrayList();
+    testData.clear();
+    for (float item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((float) 1);
+    testData.clear();
+    for (float item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(float) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((float) 1);
+    testData.clear();
+    for (float item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(float) 1, (float) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    FloatArrayList test = new FloatArrayList();
+    test.add((float) 1);
+    Assert.assertEquals(test.get(0), (float) 1);
+    //Assert.assertEquals(test.get(0), (float) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((float) 0);
+    test.add((float) 1);
+    test.add((float) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (float) 1);
+    Assert.assertEquals(test.get(0), (float) 0);
+    Assert.assertEquals(test.get(1), (float) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    FloatArrayList test = new FloatArrayList();
+    test.insert(0, (float) 1);
+    Assert.assertEquals(test.get(0), (float) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (float) 0);
+    Assert.assertEquals(test.get(0), (float) 0);
+    Assert.assertEquals(test.get(1), (float) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (float) 2);
+    Assert.assertEquals(test.get(0), (float) 0);
+    Assert.assertEquals(test.get(1), (float) 2);
+    Assert.assertEquals(test.get(2), (float) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (float) 3);
+    Assert.assertEquals(test.get(0), (float) 0);
+    Assert.assertEquals(test.get(1), (float) 2);
+    Assert.assertEquals(test.get(2), (float) 1);
+    Assert.assertEquals(test.get(3), (float) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    FloatArrayList test = new FloatArrayList();
+    test.add((float) 1);
+    test.add((float) 2);
+
+    Assert.assertEquals(test.removeLast(), (float) 2);
+    Assert.assertEquals(test.get(0), (float) 1);
+
+    Assert.assertEquals(test.removeLast(), (float) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        FloatArrayList test = new FloatArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestIntegerArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestIntegerArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestIntegerArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestIntegerArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestIntegerArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    IntegerArrayList test = new IntegerArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new IntegerArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((int) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    IntegerArrayList original = new IntegerArrayList(2);
+    original.add((int) 1);
+    int[] values = (int[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    IntegerArrayList copy = new IntegerArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (int) 1);
+    values = (int[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    IntegerArrayList test1a = new IntegerArrayList();
+    test1a.add((int) 1);
+    IntegerArrayList test1b = new IntegerArrayList();
+    test1b.add((int) 1);
+    IntegerArrayList test2 = new IntegerArrayList();
+    test2.add((int) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(IntegerArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    int[] values = (int[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    IntegerArrayList test = new IntegerArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((int) 1);
+    Assert.assertEquals(test.get(0), (int) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((int) 2);
+    Assert.assertEquals(test.get(1), (int) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((int) 3);
+    Assert.assertEquals(test.get(2), (int) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((int) 4);
+    Assert.assertEquals(test.get(3), (int) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((int) 5);
+    Assert.assertEquals(test.get(4), (int) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        IntegerArrayList test = new IntegerArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    IntegerArrayList test = new IntegerArrayList();
+
+    // Test with first value added to list
+    int testValue = (int) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (int) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (int) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    IntegerArrayList test = new IntegerArrayList();
+
+    // Test with first value added to list
+    int testValue = (int) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (int) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (int) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        IntegerArrayList test = new IntegerArrayList();
+        test.set(index, (int) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Integer> testData = new ArrayList<Integer>();
+
+    // Test with no content first
+    IntegerArrayList test = new IntegerArrayList();
+    testData.clear();
+    for (int item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((int) 1);
+    testData.clear();
+    for (int item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(int) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((int) 1);
+    testData.clear();
+    for (int item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(int) 1, (int) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    IntegerArrayList test = new IntegerArrayList();
+    test.add((int) 1);
+    Assert.assertEquals(test.get(0), (int) 1);
+    //Assert.assertEquals(test.get(0), (int) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((int) 0);
+    test.add((int) 1);
+    test.add((int) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (int) 1);
+    Assert.assertEquals(test.get(0), (int) 0);
+    Assert.assertEquals(test.get(1), (int) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    IntegerArrayList test = new IntegerArrayList();
+    test.insert(0, (int) 1);
+    Assert.assertEquals(test.get(0), (int) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (int) 0);
+    Assert.assertEquals(test.get(0), (int) 0);
+    Assert.assertEquals(test.get(1), (int) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (int) 2);
+    Assert.assertEquals(test.get(0), (int) 0);
+    Assert.assertEquals(test.get(1), (int) 2);
+    Assert.assertEquals(test.get(2), (int) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (int) 3);
+    Assert.assertEquals(test.get(0), (int) 0);
+    Assert.assertEquals(test.get(1), (int) 2);
+    Assert.assertEquals(test.get(2), (int) 1);
+    Assert.assertEquals(test.get(3), (int) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    IntegerArrayList test = new IntegerArrayList();
+    test.add((int) 1);
+    test.add((int) 2);
+
+    Assert.assertEquals(test.removeLast(), (int) 2);
+    Assert.assertEquals(test.get(0), (int) 1);
+
+    Assert.assertEquals(test.removeLast(), (int) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        IntegerArrayList test = new IntegerArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}

Added: hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestLongArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestLongArrayList.java?rev=897547&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestLongArrayList.java (added)
+++ hadoop/hbase/branches/0.20_on_hadoop-0.18.3/src/contrib/indexed/src/test/org/apache/hadoop/hbase/regionserver/idx/support/arrays/TestLongArrayList.java Sat Jan  9 21:09:59 2010
@@ -0,0 +1,349 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.idx.support.arrays;
+
+import junit.framework.Assert;
+import org.apache.hadoop.hbase.HBaseTestCase;
+import org.apache.commons.lang.ArrayUtils;
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+
+
+public class TestLongArrayList extends HBaseTestCase {
+
+
+
+  private static final int[] INVALID_INDEXES = {0, -1, 1};
+
+  /**
+   * Verifies that the initial size constructor initialises as expected.
+   */
+  public void testInitialSizeAndEmpty() {
+    LongArrayList test = new LongArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+    Assert.assertTrue(test.isEmpty());
+
+    test = new LongArrayList(1000);
+    checkSizeAndCapacity(test, 0, 1000);
+    Assert.assertTrue(test.isEmpty());
+
+    test.add((long) 5);
+    Assert.assertFalse(test.isEmpty());
+  }
+
+  /**
+   * Verifies copy constructor.
+   */
+  public void testCopyConstructor() {
+    // Create an original with a capacity of 2, but only one entry
+    LongArrayList original = new LongArrayList(2);
+    original.add((long) 1);
+    long[] values = (long[]) getField(original, "values");
+    Assert.assertEquals(values.length, 2);
+    Assert.assertEquals(original.size(), 1);
+
+    // Create a copy of the original and check that its size + capacity are the minimum
+    LongArrayList copy = new LongArrayList(original);
+    Assert.assertEquals(copy.size(), 1);
+    Assert.assertEquals(copy.get(0), (long) 1);
+    values = (long[]) getField(copy, "values");
+    Assert.assertEquals(values.length, 1);
+  }
+
+  /**
+   * Ensures the equals() method behaves as expected.
+   */
+  public void testEquals() {
+    LongArrayList test1a = new LongArrayList();
+    test1a.add((long) 1);
+    LongArrayList test1b = new LongArrayList();
+    test1b.add((long) 1);
+    LongArrayList test2 = new LongArrayList();
+    test2.add((long) 2);
+
+    Assert.assertTrue(test1a.equals(test1b));
+    Assert.assertFalse(test1a.equals(test2));
+  }
+
+
+  /**
+   * Ensures the number of elements in the list and its backing capacity are what we expect.
+   *
+   * @param test     the list to test
+   * @param size     the expected number of elements in the list
+   * @param capacity the expected capacity
+   */
+  private void checkSizeAndCapacity(LongArrayList test, int size, int capacity) {
+    Assert.assertEquals(test.size(), size);
+
+    long[] values = (long[]) getField(test, "values");
+
+    Assert.assertEquals(values.length, capacity);
+  }
+
+  /**
+   * Tests that adding elements grows the array size and capacity as expected.
+   */
+  public void testAddGetAndGrow() {
+    // Initialise
+    LongArrayList test = new LongArrayList();
+    checkSizeAndCapacity(test, 0, 1);
+
+    // Add the first element and we expect the capacity to be unchanged since we don't have any spots consumed.
+    test.add((long) 1);
+    Assert.assertEquals(test.get(0), (long) 1);
+    checkSizeAndCapacity(test, 1, 1);
+
+    // Add the next element and we expect the capacity to grow by one only
+    test.add((long) 2);
+    Assert.assertEquals(test.get(1), (long) 2);
+    checkSizeAndCapacity(test, 2, 2);
+
+    // Add the next element and we expect the capacity to grow by two
+    test.add((long) 3);
+    Assert.assertEquals(test.get(2), (long) 3);
+    checkSizeAndCapacity(test, 3, 4);
+
+    // Add the next element and we expect the capacity to be unchanged
+    test.add((long) 4);
+    Assert.assertEquals(test.get(3), (long) 4);
+    checkSizeAndCapacity(test, 4, 4);
+
+    // Add the next element and we expect the capacity to be 1.5+1 times larger
+    test.add((long) 5);
+    Assert.assertEquals(test.get(4), (long) 5);
+    checkSizeAndCapacity(test, 5, 7);
+  }
+
+  /**
+   * Tests get() with various invalid ranges.
+   */
+  public void testInvalidGet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        LongArrayList test = new LongArrayList();
+        test.get(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+         continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests the indexOf() and set() methods.
+   */
+  public void testIndexOfAndSet() {
+    LongArrayList test = new LongArrayList();
+
+    // Test with first value added to list
+    long testValue = (long) 42;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+
+    // Add a second one
+    testValue = (long) 43;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(test.indexOf(testValue), 1);
+
+    // Change the first to a new value
+    testValue = (long) 41;
+    Assert.assertEquals(test.indexOf(testValue), -1);
+    test.set(0, testValue);
+    Assert.assertEquals(test.indexOf(testValue), 0);
+  }
+
+  /**
+   * Tests the Searchable implementation.
+   */
+  public void testSearchable() {
+    LongArrayList test = new LongArrayList();
+
+    // Test with first value added to list
+    long testValue = (long) 42;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 0);
+
+    // Add a second one
+    testValue = (long) 43;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -2);
+    test.add(testValue);
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), 1);
+
+    // Search for something off the start
+    testValue = (long) 41;
+    Assert.assertEquals(BinarySearch.search(test, test.size(), testValue), -1);
+  }
+
+  /**
+   * Tests set() with various invalid ranges.
+   */
+  public void testInvalidSet() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        LongArrayList test = new LongArrayList();
+        test.set(index, (long) 0);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+
+  /**
+   * Tests iteration via the Iterable interface.
+   */
+  public void testIterable() {
+    final java.util.List<Long> testData = new ArrayList<Long>();
+
+    // Test with no content first
+    LongArrayList test = new LongArrayList();
+    testData.clear();
+    for (long item : test) {
+      testData.add(item);
+    }
+    Assert.assertEquals(testData.size(), 0);
+
+    // Add a value and ensure it is returned
+    test.add((long) 1);
+    testData.clear();
+    for (long item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(long) 1}));
+
+    // Add another value and ensure it is returned
+    test.add((long) 1);
+    testData.clear();
+    for (long item : test) {
+      testData.add(item);
+    }
+    Assert.assertTrue(ArrayUtils.isEquals(testData.toArray(),
+      new Object[]{(long) 1, (long) 1}));
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testRemove() {
+    LongArrayList test = new LongArrayList();
+    test.add((long) 1);
+    Assert.assertEquals(test.get(0), (long) 1);
+    //Assert.assertEquals(test.get(0), (long) 1);
+    test.remove(0);
+    Assert.assertTrue(test.isEmpty());
+
+    // Add some
+    test.add((long) 0);
+    test.add((long) 1);
+    test.add((long) 2);
+
+    // Remove a value from the middle and ensure correct operation
+    Assert.assertEquals(test.remove(1), (long) 1);
+    Assert.assertEquals(test.get(0), (long) 0);
+    Assert.assertEquals(test.get(1), (long) 2);
+  }
+
+  /**
+   * Tests the remove() method.
+   */
+  public void testInsert() {
+    LongArrayList test = new LongArrayList();
+    test.insert(0, (long) 1);
+    Assert.assertEquals(test.get(0), (long) 1);
+    Assert.assertEquals(test.size(), 1);
+
+    test.insert(0, (long) 0);
+    Assert.assertEquals(test.get(0), (long) 0);
+    Assert.assertEquals(test.get(1), (long) 1);
+    Assert.assertEquals(test.size(), 2);
+
+    test.insert(1, (long) 2);
+    Assert.assertEquals(test.get(0), (long) 0);
+    Assert.assertEquals(test.get(1), (long) 2);
+    Assert.assertEquals(test.get(2), (long) 1);
+    Assert.assertEquals(test.size(), 3);
+
+    test.insert(3, (long) 3);
+    Assert.assertEquals(test.get(0), (long) 0);
+    Assert.assertEquals(test.get(1), (long) 2);
+    Assert.assertEquals(test.get(2), (long) 1);
+    Assert.assertEquals(test.get(3), (long) 3);
+    Assert.assertEquals(test.size(), 4);
+  }
+
+  /**
+   * Verifies the removeLast() method works as expected.
+   */
+  public void testRemoveLast() {
+    LongArrayList test = new LongArrayList();
+    test.add((long) 1);
+    test.add((long) 2);
+
+    Assert.assertEquals(test.removeLast(), (long) 2);
+    Assert.assertEquals(test.get(0), (long) 1);
+
+    Assert.assertEquals(test.removeLast(), (long) 1);
+    Assert.assertTrue(test.isEmpty());
+  }
+
+  /**
+   * Tests remove() with various invalid ranges.
+   */
+  public void testInvalidRemove() {
+    for (int index : INVALID_INDEXES) {
+      try {
+        LongArrayList test = new LongArrayList();
+        test.remove(index);
+      } catch (ArrayIndexOutOfBoundsException ignored) {
+        continue;
+      }
+      Assert.fail("Expected an array index out of bounds exception");
+    }
+  }
+
+  /**
+   * Extracts a declared field from a given object.
+   *
+   * @param target the object from which to extract the field
+   * @param name   the name of the field
+   * @return the declared field
+   */
+  public static Object getField(Object target, String name) {
+    try {
+      Field field = target.getClass().getDeclaredField(name);
+      field.setAccessible(true);
+      return field.get(target);
+    } catch (IllegalAccessException e) {
+      Assert.fail("Exception " + e);
+    } catch (NoSuchFieldException e) {
+      Assert.fail("Exception " + e);
+    }
+    return null;
+  }
+
+}