svn commit: r896138 [4/9] - in /hadoop/hbase/branches/0.20: ./ src/contrib/ src/contrib/indexed/ src/contrib/indexed/lib/ src/contrib/indexed/lib/fmpp-0.19.14/ src/contrib/indexed/src/ src/contrib/indexed/src/fmpp/ src/contrib/indexed/src/fmpp/src/ src...

[st...@apache.org]

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ByteArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,372 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class ByteArrayList implements List<Byte> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private byte[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public ByteArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public ByteArrayList(int initialCapacity) {
+    values = new byte[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public ByteArrayList(ByteArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(byte element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Byte needle, int compareToIndex) {
+    byte compareTo = values[compareToIndex];
+    if (needle > compareTo) {
+      return 1;
+    } else if (needle < compareTo) {
+      return -1;
+    } else {
+      return 0;
+    }
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      byte[] newValues = new byte[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public byte get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(byte searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Byte> {
+
+    private byte[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(byte[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Byte next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Byte> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, byte newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public byte remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    byte original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, byte newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public byte removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    byte result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Byte fromBytes(byte[] bytes) {
+    assert bytes.length == 1;
+    return bytes[0];
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_BYTE * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof ByteArrayList)) {
+      return false;
+    }
+
+    ByteArrayList that = (ByteArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,394 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+import org.apache.hadoop.hbase.util.ClassSize;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class CharArrayArrayList implements List<char[]> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private char[][] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+  /**
+   * The accumulated heap size of elements stored in this list.
+   */
+  private long totalElementsHeapSize;
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public CharArrayArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public CharArrayArrayList(int initialCapacity) {
+    values = new char[initialCapacity][];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public CharArrayArrayList(CharArrayArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(char[] element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+    totalElementsHeapSize += ClassSize.ARRAY +
+      (element != null ? element.length * Bytes.SIZEOF_CHAR: 0);
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(char[] needle, int compareToIndex) {
+    char[] compareTo = values[compareToIndex];
+    int length = Math.min(needle.length, compareTo.length);
+    for (int i = 0; i < length; i++) {
+      if (needle[i] != compareTo[i]) {
+        if (needle[i] > compareTo[i]) {
+          return 1;
+        } else if (needle[i] < compareTo[i]) {
+          return -1;
+        }
+      }
+    }
+
+    return needle.length - compareTo.length;
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      char[][] newValues = new char[newSize][];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public char[] get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(char[] searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (Arrays.equals(values[i], searchFor)) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<char[]> {
+
+    private char[][] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(char[][] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public char[] next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<char[]> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, char[] newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+    totalElementsHeapSize -= ClassSize.ARRAY +
+      (values[index] != null ? values[index].length * Bytes.SIZEOF_CHAR: 0);
+
+    values[index] = newValue;
+
+    totalElementsHeapSize += ClassSize.ARRAY +
+      (newValue != null ? newValue.length * Bytes.SIZEOF_CHAR: 0);
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public char[] remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    char[] original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    totalElementsHeapSize -= ClassSize.ARRAY +
+      (original != null ? original.length * Bytes.SIZEOF_CHAR: 0);
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, char[] newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+    totalElementsHeapSize += ClassSize.ARRAY +
+      (newValue != null ? newValue.length * Bytes.SIZEOF_CHAR: 0);
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public char[] removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    char[] result = values[size - 1];
+    size--;
+    values[size] = null;
+    totalElementsHeapSize -= ClassSize.ARRAY +
+      (result != null ? result.length * Bytes.SIZEOF_CHAR: 0);
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public char[] fromBytes(byte[] bytes) {
+    return Bytes.toChars(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_LONG +
+      ClassSize.REFERENCE * values.length + totalElementsHeapSize;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof CharArrayArrayList)) {
+      return false;
+    }
+
+    CharArrayArrayList that = (CharArrayArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/CharArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,371 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class CharArrayList implements List<Character> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private char[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public CharArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public CharArrayList(int initialCapacity) {
+    values = new char[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public CharArrayList(CharArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(char element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Character needle, int compareToIndex) {
+    char compareTo = values[compareToIndex];
+    if (needle > compareTo) {
+      return 1;
+    } else if (needle < compareTo) {
+      return -1;
+    } else {
+      return 0;
+    }
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      char[] newValues = new char[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public char get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(char searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Character> {
+
+    private char[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(char[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Character next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Character> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, char newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public char remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    char original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, char newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public char removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    char result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Character fromBytes(byte[] bytes) {
+    return Bytes.toChar(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_CHAR * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof CharArrayList)) {
+      return false;
+    }
+
+    CharArrayList that = (CharArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/DoubleArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,365 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class DoubleArrayList implements List<Double> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private double[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public DoubleArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public DoubleArrayList(int initialCapacity) {
+    values = new double[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public DoubleArrayList(DoubleArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(double element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Double needle, int compareToIndex) {
+    double compareTo = values[compareToIndex];
+    return Double.compare(needle, compareTo);
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      double[] newValues = new double[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public double get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(double searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Double> {
+
+    private double[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(double[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Double next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Double> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, double newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public double remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    double original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, double newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public double removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    double result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Double fromBytes(byte[] bytes) {
+    return Bytes.toDouble(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_DOUBLE * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof DoubleArrayList)) {
+      return false;
+    }
+
+    DoubleArrayList that = (DoubleArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/FloatArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,365 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class FloatArrayList implements List<Float> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private float[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public FloatArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public FloatArrayList(int initialCapacity) {
+    values = new float[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public FloatArrayList(FloatArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(float element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Float needle, int compareToIndex) {
+    float compareTo = values[compareToIndex];
+    return Float.compare(needle, compareTo);
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      float[] newValues = new float[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public float get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(float searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Float> {
+
+    private float[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(float[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Float next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Float> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, float newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public float remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    float original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, float newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public float removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    float result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Float fromBytes(byte[] bytes) {
+    return Bytes.toFloat(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_FLOAT * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof FloatArrayList)) {
+      return false;
+    }
+
+    FloatArrayList that = (FloatArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/IntegerArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/IntegerArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/IntegerArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/IntegerArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,371 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class IntegerArrayList implements List<Integer> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private int[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public IntegerArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public IntegerArrayList(int initialCapacity) {
+    values = new int[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public IntegerArrayList(IntegerArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(int element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Integer needle, int compareToIndex) {
+    int compareTo = values[compareToIndex];
+    if (needle > compareTo) {
+      return 1;
+    } else if (needle < compareTo) {
+      return -1;
+    } else {
+      return 0;
+    }
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      int[] newValues = new int[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public int get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(int searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Integer> {
+
+    private int[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(int[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Integer next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Integer> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, int newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public int remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    int original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, int newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public int removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    int result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Integer fromBytes(byte[] bytes) {
+    return Bytes.toInt(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_INT * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof IntegerArrayList)) {
+      return false;
+    }
+
+    IntegerArrayList that = (IntegerArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/List.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/List.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/List.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/List.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,75 @@
+/**
+ * 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 org.apache.hadoop.hbase.io.HeapSize;
+import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.ClassSize;
+
+/**
+ * An interface for an array list, typically used as a key store.
+ *
+ * @param <T> the element type
+ */
+public interface List<T> extends Iterable<T>, BinarySearch.Searchable<T>,
+  HeapSize {
+  
+  long FIXED_OVERHEAD =
+    ClassSize.align(ClassSize.ARRAY + Bytes.SIZEOF_INT + ClassSize.OBJECT);
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param e the new element
+   */
+  void add(byte[] e);
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  void set(int index, byte[] newValue);
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  void insert(int index, byte[] newValue);
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  boolean isEmpty();
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  int size();
+
+
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/LongArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/LongArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/LongArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/LongArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,371 @@
+/**
+ * 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 org.apache.hadoop.hbase.util.Bytes;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.lang.ArrayUtils;
+
+/**
+ * A list designed to be used as the key store for indexed HBase.  
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ */
+public class LongArrayList implements List<Long> {
+
+
+  //DO NOT EDIT THIS FILE, EDIT THE FMPP TEMPLATE INSTEAD.
+  //To generate source execute
+  // **/src/contib/indexed# ant -f build-fmpp.xml -lib lib/fmpp-0.19.14 
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private long[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public LongArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  public LongArrayList(int initialCapacity) {
+    values = new long[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public LongArrayList(LongArrayList initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param element the new element
+   */
+  public void add(long element) {
+    ensureCapacity(size + 1);
+    values[size] = element;
+    size++;
+  }
+
+  @Override
+  public void add(byte[] bytes) {
+    add(fromBytes(bytes));
+  }
+
+  @Override
+  public int compare(Long needle, int compareToIndex) {
+    long compareTo = values[compareToIndex];
+    if (needle > compareTo) {
+      return 1;
+    } else if (needle < compareTo) {
+      return -1;
+    } else {
+      return 0;
+    }
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      long[] newValues = new long[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public long get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(long searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i] == searchFor) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator
+    implements Iterator<Long> {
+
+    private long[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(long[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Long next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  @Override
+  public Iterator<Long> iterator() {
+    return new InternalIterator(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, long newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+
+  }
+
+  @Override
+  public void set(int index, byte[] newValue) {
+    set(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public long remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    long original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    size--;
+    return original;
+  }
+
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, long newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+  @Override
+  public void insert(int index, byte[] newValue) {
+    insert(index, fromBytes(newValue));
+  }
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public long removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    long result = values[size - 1];
+    size--;
+
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public Long fromBytes(byte[] bytes) {
+    return Bytes.toLong(bytes);
+  }
+
+
+  @Override
+  public long heapSize() {
+    return FIXED_OVERHEAD + Bytes.SIZEOF_LONG * values.length;
+  }
+
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  @Override
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof LongArrayList)) {
+      return false;
+    }
+
+    LongArrayList that = (LongArrayList) compareTo;
+
+    return this.size == that.size &&
+      ArrayUtils.isEquals(this.values, that.values);
+  }
+
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public int hashCode() {
+    return 31 * Arrays.hashCode(values) + size;
+  }
+}

Added: hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ObjectArrayList.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ObjectArrayList.java?rev=896138&view=auto
==============================================================================
--- hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ObjectArrayList.java (added)
+++ hadoop/hbase/branches/0.20/src/contrib/indexed/src/java/org/apache/hadoop/hbase/regionserver/idx/support/arrays/ObjectArrayList.java Tue Jan  5 17:26:49 2010
@@ -0,0 +1,313 @@
+/*
+ * 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 java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * An object array list implemented using the same methodology as the primitve
+ * arrays but without the extra heap size and {@link List} methods.
+ * <p/>
+ * NOTE: This class is completely unsynchronised.
+ *
+ * @param <T> element type
+ */
+public class ObjectArrayList<T> implements Iterable<T> {
+
+  /**
+   * Default initial size of the array backing this list.
+   */
+  private static final int DEFAULT_SIZE = 1;
+
+  /**
+   * The scaling factor we use to resize the backing buffer when the list needs to grow.
+   */
+  private static final float SCALE_FACTOR = 1.5f;
+
+  /**
+   * The array backing this list.
+   */
+  private T[] values;
+
+  /**
+   * The number of values present in the list.
+   */
+  private int size;
+
+  /**
+   * Constructor that initialises with the default size.
+   */
+  public ObjectArrayList() {
+    this(DEFAULT_SIZE);
+  }
+
+  /**
+   * Constructor which initialises with the specified initial capacity.
+   *
+   * @param initialCapacity the initial capacity of the backing array
+   */
+  @SuppressWarnings("unchecked")
+  public ObjectArrayList(int initialCapacity) {
+    values = (T[]) new Object[initialCapacity];
+  }
+
+  /**
+   * Constructor which initialises the content from the supplied array list.
+   *
+   * @param initial the initial contents
+   */
+  public ObjectArrayList(ObjectArrayList<T> initial) {
+    // Initialise the internal storage to the appropriate size
+    this(initial.size);
+
+    // Copy over the references/values
+    System.arraycopy(initial.values, 0, this.values, 0, initial.size);
+    this.size = initial.size;
+  }
+
+  /**
+   * Checks the contents of the collection for equality.
+   * <p/>
+   * {@inheritDoc}
+   */
+  @Override
+  public boolean equals(Object compareTo) {
+    if (this == compareTo) {
+      return true;
+    }
+    if (!(compareTo instanceof ObjectArrayList)) {
+      return false;
+    }
+
+    ObjectArrayList<?> that = (ObjectArrayList<?>) compareTo;
+
+    return Arrays.equals(this.values, that.values);
+  }
+
+  /**
+   * Adds the element to the end of the list.
+   *
+   * @param e the new element
+   */
+  public void add(T e) {
+    ensureCapacity(size + 1);
+    values[size] = e;
+    size++;
+  }
+
+  /**
+   * Grows the backing array to the requested size.
+   *
+   * @param requested the new capacity.
+   */
+  @SuppressWarnings("unchecked")
+  private void ensureCapacity(int requested) {
+    // If we need to resize
+    if (requested > values.length) {
+      // Calculate the new size, growing slowly at the start to avoid overallocation too early.
+      int newSize = Math.max(requested, (int) (values.length * SCALE_FACTOR + 1));
+
+      // Create the new array
+      T[] newValues = (T[]) new Object[newSize];
+
+      // Populate the new backing array
+      System.arraycopy(values, 0, newValues, 0, size);
+      values = newValues;
+    }
+  }
+
+  /**
+   * Retrieves the element at the requested index.
+   *
+   * @param index the element index you wish to retrieve
+   * @return the value at that index
+   */
+  public T get(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    return values[index];
+  }
+
+  /**
+   * Searches the list for the nominated value.
+   *
+   * @param searchFor the value you are looking for
+   * @return the first index the value was found at or -1 if not found
+   */
+  public int indexOf(T searchFor) {
+    // Check each of the values. Don't bother with get() since we don't need its protection.
+    for (int i = 0; i < size; i++) {
+      if (values[i].equals(searchFor)) {
+        return i;
+      }
+    }
+
+    // Didn't find it.
+    return -1;
+  }
+
+  /**
+   * Simple iterator that runs over the values in the list.
+   */
+  private static final class InternalIterator<T>
+    implements Iterator<T> {
+
+    private T[] values;
+    private int size;
+    private int current = 0;
+
+    private InternalIterator(T[] values, int size) {
+      this.values = values;
+      this.size = size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean hasNext() {
+      return current < size;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public T next() {
+      if (!hasNext()) {
+        throw new NoSuchElementException();
+      }
+      return values[current++];
+    }
+
+    /**
+     * Not supported.
+     */
+    public void remove() {
+      throw new UnsupportedOperationException("remove() is not supported");
+    }
+  }
+
+  /**
+   * Returns an iterator over the underlying content. Note that this is completely unsynchronised and the contents can change under you.
+   */
+  public Iterator<T> iterator() {
+    return new InternalIterator<T>(values, size);
+  }
+
+  /**
+   * Checks if the list is empty.
+   *
+   * @return true if the list is empty
+   */
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  /**
+   * Sets the specified index to the nominated value.
+   *
+   * @param index    the list index
+   * @param newValue the value
+   */
+  public void set(int index, T newValue) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    values[index] = newValue;
+  }
+
+  /**
+   * Removes the specified index from the list.
+   *
+   * @param index the index to remove
+   * @return the original value
+   */
+  public T remove(int index) {
+    if (index >= size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    T original = values[index];
+    System.arraycopy(values, index + 1, values, index, size - index - 1);
+    values[size - 1] = null;
+    size--;
+    return original;
+  }
+
+  /**
+   * Inserts at the specified index to the list.
+   *
+   * @param index    the index to insert
+   * @param newValue the value to insert
+   */
+  public void insert(int index, T newValue) {
+    if (index > size) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to access index " + index + " but array is " + size + " elements");
+    }
+
+    ensureCapacity(size + 1);
+    if (index != size) {
+      System.arraycopy(values, index, values, index + 1, size - index);
+    }
+    values[index] = newValue;
+    size++;
+  }
+
+
+  /**
+   * Removes the last item in the list.
+   *
+   * @return the original value
+   */
+  public T removeLast() {
+    if (size < 1) {
+      throw new ArrayIndexOutOfBoundsException("Attempted to remove last element from array with size 0");
+    }
+
+    T result = values[size - 1];
+    values[size - 1] = null;
+    size--;
+
+    return result;
+  }
+
+  /**
+   * Returns the current number of elements in this list.
+   *
+   * @return the number of elements.
+   */
+  public int size() {
+    return size;
+  }
+
+  /**
+   * Return a nice view of the list.
+   * {@inheritDoc}
+   */
+  public String toString() {
+    return Arrays.toString(Arrays.copyOf(values, size));
+  }
+
+
+}