hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tjungb...@apache.org
Subject svn commit: r1387533 [8/10] - in /hama/trunk: ./ core/ core/src/main/java/org/apache/hama/bsp/ graph/ graph/src/main/java/org/apache/hama/graph/ jdbm/ jdbm/src/ jdbm/src/main/ jdbm/src/main/java/ jdbm/src/main/java/org/ jdbm/src/main/java/org/apache/ j...
Date Wed, 19 Sep 2012 11:52:24 GMT
Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeBucketTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeBucketTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeBucketTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeBucketTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,100 @@
+/**
+ * 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.hama.jdbm;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.io.Serializable;
+import java.util.Map;
+
+/**
+ * This class contains all Unit tests for {@link HTreeBucket}.
+ */
+public class HTreeBucketTest extends TestCaseWithTestFile {
+
+  /**
+   * Basic tests
+   */
+  public void testBasics() throws IOException {
+
+    DB db = newDBCache();
+
+    HTree tree = (HTree) db.createHashMap("test");
+
+    HTreeBucket bucket = new HTreeBucket(tree, (byte) 0);
+
+    // add
+    bucket.addElement("key", "value");
+    String s = (String) bucket.getValue("key");
+    assertEquals("value", s);
+
+    // replace
+    bucket.addElement("key", "value2");
+    s = (String) bucket.getValue("key");
+    assertEquals("value2", s);
+
+    // add
+    bucket.addElement("key2", "value3");
+    s = (String) bucket.getValue("key2");
+    assertEquals("value3", s);
+
+    // remove
+    bucket.removeElement("key2");
+    s = (String) bucket.getValue("key2");
+    assertEquals(null, s);
+    bucket.removeElement("key");
+    s = (String) bucket.getValue("key");
+    assertEquals(null, s);
+
+    db.close();
+  }
+
+  public static class LongSerializer implements Serializer<Long>, Serializable {
+
+    public LongSerializer() {
+
+    }
+
+    public void serialize(DataOutput out, Long obj) throws IOException {
+      out.writeLong(obj);
+    }
+
+    public Long deserialize(DataInput in) throws IOException,
+        ClassNotFoundException {
+      return in.readLong();
+    }
+  }
+
+  public void testCustomSerializer() throws IOException {
+    Serializer<Long> ser = new LongSerializer();
+
+    DB db = newDBCache();
+    Map<Long, Long> s = db.createHashMap("test", ser, ser);
+
+    s.put(new Long(1), new Long(2));
+    s.put(new Long(4), new Long(5));
+    db.commit();
+    db.clearCache();
+    assertTrue(s.size() == 2);
+    assertEquals(s.get(new Long(1)), new Long(2));
+    assertEquals(s.get(new Long(4)), new Long(5));
+
+  }
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeDirectoryTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeDirectoryTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeDirectoryTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeDirectoryTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,145 @@
+/**
+ * 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.hama.jdbm;
+
+import java.io.IOException;
+import java.util.Hashtable;
+import java.util.Iterator;
+
+/**
+ * This class contains all Unit tests for {@link HTreeDirectory}.
+ */
+public class HTreeDirectoryTest extends TestCaseWithTestFile {
+
+  /**
+   * Basic tests
+   */
+  public void testBasics() throws IOException {
+    System.out.println("testBasics");
+
+    DBAbstract db = newDBCache();
+
+    HTree tree = (HTree) db.createHashMap("test");
+    HTreeDirectory dir = tree.getRoot();
+
+    dir.put("key", "value");
+    String s = (String) dir.get("key");
+    assertEquals("value", s);
+
+    db.close();
+  }
+
+  /**
+   * Mixed tests
+   */
+  public void testMixed() throws IOException {
+    System.out.println("testMixed");
+
+    DBAbstract db = newDBCache();
+
+    HTree tree = (HTree) db.createHashMap("test");
+    HTreeDirectory dir = tree.getRoot();
+
+    Hashtable hash = new Hashtable(); // use to compare results
+
+    int max = 30; // must be even
+
+    // insert & check values
+    for (int i = 0; i < max; i++) {
+      dir.put("key" + i, "value" + i);
+      hash.put("key" + i, "value" + i);
+    }
+    db.commit();
+
+    for (int i = 0; i < max; i++) {
+      String s = (String) dir.get("key" + i);
+      assertEquals("value" + i, s);
+    }
+    db.commit();
+
+    // replace only even values
+    for (int i = 0; i < max; i += 2) {
+      dir.put("key" + i, "value" + (i * 2 + 1));
+      hash.put("key" + i, "value" + (i * 2 + 1));
+    }
+    db.commit();
+
+    for (int i = 0; i < max; i++) {
+      if ((i % 2) == 1) {
+        // odd
+        String s = (String) dir.get("key" + i);
+        assertEquals("value" + i, s);
+      } else {
+        // even
+        String s = (String) dir.get("key" + i);
+        assertEquals("value" + (i * 2 + 1), s);
+      }
+    }
+    db.commit();
+
+    // remove odd numbers
+    for (int i = 1; i < max; i += 2) {
+      dir.remove("key" + i);
+      hash.remove("key" + i);
+    }
+    db.commit();
+
+    for (int i = 0; i < max; i++) {
+      if ((i % 2) == 1) {
+        // odd
+        String s = (String) dir.get("key" + i);
+        assertEquals(null, s);
+      } else {
+        // even
+        String s = (String) dir.get("key" + i);
+        assertEquals("value" + (i * 2 + 1), s);
+      }
+    }
+    db.commit();
+
+    db.close();
+    db = null;
+  }
+
+  void checkEnumerations(Hashtable hash, HTreeDirectory dir) throws IOException {
+
+    // test keys
+    Hashtable clone = (Hashtable) hash.clone();
+    int count = 0;
+    Iterator<String> iter = dir.keys();
+
+    while (iter.hasNext()) {
+      String s = iter.next();
+      count++;
+      clone.remove(s);
+    }
+    assertEquals(hash.size(), count);
+
+    // test values
+    clone = (Hashtable) hash.clone();
+    count = 0;
+    iter = dir.values();
+    while (iter.hasNext()) {
+      String s = iter.next();
+      count++;
+      clone.remove(s);
+    }
+    assertEquals(hash.size(), count);
+  }
+
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeSetTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeSetTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeSetTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeSetTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,157 @@
+/**
+ * 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.hama.jdbm;
+
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * Tests for HashSet which comes with JDBM. Original code comes from Apache
+ * Harmony, Modified by Jan Kotek for use in JDBM
+ */
+public class HTreeSetTest extends TestCaseWithTestFile {
+
+  Set hs;
+  DB db;
+
+  static Object[] objArray;
+
+  {
+    objArray = new Object[1000];
+    for (int i = 0; i < objArray.length; i++)
+      objArray[i] = new Integer(i);
+  }
+
+  /**
+   * @tests java.util.HashSet#HashSet()
+   */
+  public void test_Constructor() {
+    // Test for method java.util.HashSet()
+    Set hs2 = db.createHashSet("secondHashSet", null);
+    assertEquals("Created incorrect HashSet", 0, hs2.size());
+  }
+
+  /**
+   * @tests java.util.HashSet#add(java.lang.Object)
+   */
+  public void test_addLjava_lang_Object() {
+    // Test for method boolean java.util.HashSet.add(java.lang.Object)
+    int size = hs.size();
+    hs.add(new Integer(8));
+    assertTrue("Added element already contained by set", hs.size() == size);
+    hs.add(new Integer(-9));
+    assertTrue("Failed to increment set size after add", hs.size() == size + 1);
+    assertTrue("Failed to add element to set", hs.contains(new Integer(-9)));
+  }
+
+  /**
+   * @tests java.util.HashSet#clear()
+   */
+  public void test_clear() {
+    // Test for method void java.util.HashSet.clear()
+    Set orgSet = new java.util.HashSet(hs);
+    hs.clear();
+    Iterator i = orgSet.iterator();
+    assertEquals("Returned non-zero size after clear", 0, hs.size());
+    while (i.hasNext())
+      assertTrue("Failed to clear set", !hs.contains(i.next()));
+  }
+
+  /**
+   * @tests java.util.HashSet#contains(java.lang.Object)
+   */
+  public void test_containsLjava_lang_Object() {
+    // Test for method boolean java.util.HashSet.contains(java.lang.Object)
+    assertTrue("Returned false for valid object", hs.contains(objArray[90]));
+    assertTrue("Returned true for invalid Object", !hs.contains(new Object()));
+
+  }
+
+  /**
+   * @tests java.util.HashSet#isEmpty()
+   */
+  public void test_isEmpty() {
+    // Test for method boolean java.util.HashSet.isEmpty()
+    assertTrue("Empty set returned false",
+        db.createHashSet("secondHashSet", null).isEmpty());
+    assertTrue("Non-empty set returned true", !hs.isEmpty());
+  }
+
+  /**
+   * @tests java.util.HashSet#iterator()
+   */
+  public void test_iterator() {
+    // Test for method java.util.Iterator java.util.HashSet.iterator()
+    Iterator i = hs.iterator();
+    int x = 0;
+    while (i.hasNext()) {
+      assertTrue("Failed to iterate over all elements", hs.contains(i.next()));
+      ++x;
+    }
+    assertTrue("Returned iteration of incorrect size", hs.size() == x);
+
+  }
+
+  /**
+   * @tests java.util.HashSet#remove(java.lang.Object)
+   */
+  public void test_removeLjava_lang_Object() {
+    // Test for method boolean java.util.HashSet.remove(java.lang.Object)
+    int size = hs.size();
+    hs.remove(new Integer(98));
+    assertTrue("Failed to remove element", !hs.contains(new Integer(98)));
+    assertTrue("Failed to decrement set size", hs.size() == size - 1);
+
+  }
+
+  /**
+   * @tests java.util.HashSet#size()
+   */
+  public void test_size() {
+    // Test for method int java.util.HashSet.size()
+    assertTrue("Returned incorrect size", hs.size() == (objArray.length));
+    hs.clear();
+    assertEquals("Cleared set returned non-zero size", 0, hs.size());
+  }
+
+  /**
+   * Sets up the fixture, for example, open a network connection. This method is
+   * called before a test is executed.
+   */
+  public void setUp() throws Exception {
+    super.setUp();
+    db = newDBNoCache();
+    hs = db.createHashSet("testHashSet", null);
+    for (int i = 0; i < objArray.length; i++)
+      hs.add(objArray[i]);
+  }
+
+  /**
+   * Tears down the fixture, for example, close a network connection. This
+   * method is called after a test is executed.
+   */
+  public void tearDown() throws Exception {
+    db.close();
+    super.tearDown();
+  }
+
+  public void testContains() {
+
+  }
+
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/HTreeTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,133 @@
+/**
+ * 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.hama.jdbm;
+
+import java.io.IOException;
+import java.util.AbstractMap.SimpleEntry;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * This class contains all Unit tests for {@link HTree}.
+ */
+public class HTreeTest extends TestCaseWithTestFile {
+
+  /**
+   * Basic tests
+   */
+  public void testIterator() throws IOException {
+
+    DBAbstract db = newDBCache();
+
+    HTree testTree = (HTree) db.createHashMap("tree");
+
+    int total = 10;
+    for (int i = 0; i < total; i++) {
+      testTree.put(Long.valueOf("" + i), Long.valueOf("" + i));
+    }
+    db.commit();
+
+    Iterator fi = testTree.values().iterator();
+    Object item;
+    int count = 0;
+    while (fi.hasNext()) {
+      fi.next();
+      count++;
+    }
+    assertEquals(count, total);
+
+    db.close();
+  }
+
+  public void testRecordListener() throws IOException {
+    DBAbstract db = newDBCache();
+    HTree<Integer, String> tree = (HTree) db.createHashMap("test");
+    final List<SimpleEntry<Integer, String>> dels = new ArrayList();
+    final List<SimpleEntry<Integer, String>> ins = new ArrayList();
+    final List<SimpleEntry<Integer, String>> updNew = new ArrayList();
+    final List<SimpleEntry<Integer, String>> updOld = new ArrayList();
+
+    tree.addRecordListener(new RecordListener<Integer, String>() {
+
+      public void recordUpdated(Integer key, String oldValue, String newValue)
+          throws IOException {
+        updOld.add(new SimpleEntry<Integer, String>(key, oldValue));
+        updNew.add(new SimpleEntry<Integer, String>(key, newValue));
+      }
+
+      public void recordRemoved(Integer key, String value) throws IOException {
+        dels.add(new SimpleEntry<Integer, String>(key, value));
+      }
+
+      public void recordInserted(Integer key, String value) throws IOException {
+        ins.add(new SimpleEntry<Integer, String>(key, value));
+      }
+    });
+
+    // test insert
+    tree.put(11, "aa11");
+    tree.put(12, "aa12");
+    assertTrue(ins.contains(new SimpleEntry(11, "aa11")));
+    assertTrue(ins.contains(new SimpleEntry(12, "aa12")));
+    assertTrue(ins.size() == 2);
+    ins.clear();
+    assertTrue(dels.isEmpty());
+    assertTrue(updNew.isEmpty());
+    assertTrue(updOld.isEmpty());
+
+    // test update
+    tree.put(12, "aa123");
+    assertTrue(ins.isEmpty());
+    assertTrue(dels.isEmpty());
+    assertTrue(updOld.contains(new SimpleEntry(12, "aa12")));
+    assertTrue(updOld.size() == 1);
+    updOld.clear();
+    assertTrue(updNew.contains(new SimpleEntry(12, "aa123")));
+    assertTrue(updNew.size() == 1);
+    updNew.clear();
+
+    // test remove
+    tree.remove(11);
+    assertTrue(dels.contains(new SimpleEntry(11, "aa11")));
+    assertTrue(dels.size() == 1);
+    dels.clear();
+    assertTrue(ins.isEmpty());
+    assertTrue(updOld.isEmpty());
+    assertTrue(updNew.isEmpty());
+
+  }
+
+  public void testIssue() {
+    int size = 100000;
+    int commitSize = 100000;
+    DB build = DBMaker.openFile(newTestFile()).setMRUCacheSize(100).make();
+    Map<String, String> hashMap = build.createHashMap("hashMap");
+    for (int i = 0; i < size; i++) {
+      hashMap.put(i + "asdddfdgf" + i + "sddfdfsf" + i, "dsfgfg.dfcdfsgfg");
+      if (i % commitSize == 0) {
+        build.commit();
+      }
+    }
+    build.commit();
+    build.calculateStatistics();
+    build.close();
+  }
+
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LinkedListTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LinkedListTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LinkedListTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LinkedListTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,455 @@
+/**
+ * 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.hama.jdbm;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+
+/**
+ * Tests for LinkedList2 which comes with JDBM. Original code comes from Apache
+ * Harmony, Modified by Jan Kotek for use in JDBM
+ */
+public class LinkedListTest extends TestCaseWithTestFile {
+
+  DB db;
+
+  LinkedList ll;
+
+  LinkedList<Object> testList;
+
+  private Object testObjOne;
+
+  private Object testObjTwo;
+
+  private Object testObjThree;
+
+  private Object testObjFour;
+
+  private Object testObjLast;
+
+  static Object[] objArray;
+
+  {
+    objArray = new Object[100];
+    for (int i = 0; i < objArray.length; i++)
+      objArray[i] = new Integer(i);
+  }
+
+  /**
+   * @tests java.util.LinkedList2#add(int, java.lang.Object)
+   */
+  public void test_addILjava_lang_Object() {
+    // Test for method void java.util.LinkedList2.add(int, java.lang.Object)
+    Object o = "Test";
+    ll.add(50, o);
+    assertEquals("Failed to add Object>: " + ll.get(50).toString(), ll.get(50),
+        o);
+    assertEquals("Failed to fix up list after insert", ll.get(51), objArray[50]);
+    assertEquals(ll.get(52), objArray[51]);
+    ll.add(50, null);
+    assertNull("Did not add null correctly", ll.get(50));
+
+    try {
+      ll.add(-1, "Test");
+      fail("Should throw IndexOutOfBoundsException");
+    } catch (IndexOutOfBoundsException e) {
+      // Excepted
+    }
+
+    try {
+      ll.add(-1, null);
+      fail("Should throw IndexOutOfBoundsException");
+    } catch (IndexOutOfBoundsException e) {
+      // Excepted
+    }
+
+    try {
+      ll.add(ll.size() + 1, "Test");
+      fail("Should throw IndexOutOfBoundsException");
+    } catch (IndexOutOfBoundsException e) {
+      // Excepted
+    }
+
+    try {
+      ll.add(ll.size() + 1, null);
+      fail("Should throw IndexOutOfBoundsException");
+    } catch (IndexOutOfBoundsException e) {
+      // Excepted
+    }
+  }
+
+  /**
+   * @tests java.util.LinkedList2#addAll(int, java.util.Collection)
+   */
+  public void test_addAllILjava_util_Collection() {
+    // Test for method boolean java.util.LinkedList2.addAll(int,
+    // java.util.Collection)
+    ll.addAll(50, new ArrayList(ll));
+    assertEquals("Returned incorrect size after adding to existing list", 200,
+        ll.size());
+    for (int i = 0; i < 50; i++)
+      assertEquals("Manipulated elements < index", ll.get(i), objArray[i]);
+    for (int i = 0; i >= 50 && (i < 150); i++)
+      assertTrue("Failed to ad elements properly",
+          ll.get(i) == objArray[i - 50]);
+    for (int i = 0; i >= 150 && (i < 200); i++)
+      assertTrue("Failed to ad elements properly",
+          ll.get(i) == objArray[i - 100]);
+    List myList = db.createLinkedList("testXX");
+    myList.add(null);
+    myList.add("Blah");
+    myList.add(null);
+    myList.add("Booga");
+    myList.add(null);
+    ll.addAll(50, myList);
+    assertNull("a) List w/nulls not added correctly", ll.get(50));
+    assertEquals("b) List w/nulls not added correctly", "Blah", ll.get(51));
+    assertNull("c) List w/nulls not added correctly", ll.get(52));
+    assertEquals("d) List w/nulls not added correctly", "Booga", ll.get(53));
+    assertNull("e) List w/nulls not added correctly", ll.get(54));
+
+    try {
+      ll.addAll(50, null);
+      fail("Should throw NullPointerException");
+    } catch (NullPointerException e) {
+      // Excepted
+    }
+  }
+
+  /**
+   * @tests java.util.LinkedList2#addAll(int, java.util.Collection)
+   */
+  public void test_addAllILjava_util_Collection_2() {
+    // Regression for HARMONY-467
+    LinkedList obj = (LinkedList) db.createLinkedList("testXX");
+    try {
+      obj.addAll(-1, (Collection) null);
+      fail("IndexOutOfBoundsException expected");
+    } catch (IndexOutOfBoundsException e) {
+    }
+  }
+
+  /**
+   * @tests java.util.LinkedList2#addAll(java.util.Collection)
+   */
+  public void test_addAllLjava_util_Collection() {
+
+    // Test for method boolean
+    // java.util.LinkedList2.addAll(java.util.Collection)
+    List l = new ArrayList();
+    l.addAll(new ArrayList(ll));
+
+    for (int i = 0; i < ll.size(); i++)
+      assertTrue("Failed to add elements properly", l.get(i).equals(ll.get(i)));
+    ll.addAll(new ArrayList(ll));
+    assertEquals("Returned incorrect siZe after adding to existing list", 200,
+        ll.size());
+    for (int i = 0; i < 100; i++) {
+      assertTrue("Added to list in incorrect order", ll.get(i).equals(l.get(i)));
+      assertTrue("Failed to add to existing list",
+          ll.get(i + 100).equals(l.get(i)));
+    }
+    List myList = db.createLinkedList("testXX");
+    myList.add(null);
+    myList.add("Blah");
+    myList.add(null);
+    myList.add("Booga");
+    myList.add(null);
+    ll.addAll(myList);
+    assertNull("a) List w/nulls not added correctly", ll.get(200));
+    assertEquals("b) List w/nulls not added correctly", "Blah", ll.get(201));
+    assertNull("c) List w/nulls not added correctly", ll.get(202));
+    assertEquals("d) List w/nulls not added correctly", "Booga", ll.get(203));
+    assertNull("e) List w/nulls not added correctly", ll.get(204));
+
+    try {
+      ll.addAll(null);
+      fail("Should throw NullPointerException");
+    } catch (NullPointerException e) {
+      // Excepted
+    }
+  }
+
+  /**
+   * @tests java.util.LinkedList2#clear()
+   */
+  public void test_clear() {
+    // Test for method void java.util.LinkedList2.clear()
+    ll.clear();
+    for (int i = 0; i < ll.size(); i++)
+      assertNull("Failed to clear list", ll.get(i));
+  }
+
+  /**
+   * @tests java.util.LinkedList2#contains(java.lang.Object)
+   */
+  public void test_containsLjava_lang_Object() {
+    // Test for method boolean
+    // java.util.LinkedList2.contains(java.lang.Object)
+    assertTrue("Returned false for valid element", ll.contains(objArray[99]));
+    assertTrue("Returned false for equal element", ll.contains(new Integer(8)));
+    assertTrue("Returned true for invalid element", !ll.contains(new Object()));
+    assertTrue("Should not contain null", !ll.contains(null));
+    ll.add(25, null);
+    assertTrue("Should contain null", ll.contains(null));
+  }
+
+  /**
+   * @tests java.util.LinkedList2#get(int)
+   */
+  public void test_getI() {
+    // Test for method java.lang.Object java.util.LinkedList2.get(int)
+    assertEquals("Returned incorrect element", ll.get(22), objArray[22]);
+    try {
+      ll.get(8765);
+      fail("Failed to throw expected exception for index > size");
+    } catch (IndexOutOfBoundsException e) {
+    }
+  }
+
+  /**
+   * @tests java.util.LinkedList2#indexOf(java.lang.Object)
+   */
+  public void test_indexOfLjava_lang_Object() {
+    // Test for method int java.util.LinkedList2.indexOf(java.lang.Object)
+    assertEquals("Returned incorrect index", 87, ll.indexOf(objArray[87]));
+    assertEquals("Returned index for invalid Object", -1,
+        ll.indexOf(new Object()));
+    ll.add(20, null);
+    ll.add(24, null);
+    assertTrue("Index of null should be 20, but got: " + ll.indexOf(null),
+        ll.indexOf(null) == 20);
+  }
+
+  /**
+   * @tests java.util.LinkedList2#lastIndexOf(java.lang.Object)
+   */
+  public void test_lastIndexOfLjava_lang_Object() {
+    // Test for method int
+    // java.util.LinkedList2.lastIndexOf(java.lang.Object)
+    ll.add(new Integer(99));
+    assertEquals("Returned incorrect index", 100, ll.lastIndexOf(objArray[99]));
+    assertEquals("Returned index for invalid Object", -1,
+        ll.lastIndexOf(new Object()));
+    ll.add(20, null);
+    ll.add(24, null);
+    assertTrue(
+        "Last index of null should be 20, but got: " + ll.lastIndexOf(null),
+        ll.lastIndexOf(null) == 24);
+  }
+
+  /**
+   * @tests java.util.LinkedList2#listIterator(int)
+   */
+  public void test_listIteratorI() {
+    // Test for method java.util.ListIterator
+    // java.util.LinkedList2.listIterator(int)
+    ListIterator i = ll.listIterator();
+    Object elm;
+    int n = 0;
+    while (i.hasNext()) {
+      if (n == 0 || n == objArray.length - 1) {
+        if (n == 0)
+          assertTrue("First element claimed to have a previous",
+              !i.hasPrevious());
+        if (n == objArray.length)
+          assertTrue("Last element claimed to have next", !i.hasNext());
+      }
+      elm = i.next();
+      assertEquals("Iterator returned elements in wrong order", elm,
+          objArray[n]);
+      if (n > 0 && n < objArray.length - 1) {
+        assertEquals("Next index returned incorrect value", i.nextIndex(),
+            n + 1);
+        assertEquals(
+            "previousIndex returned incorrect value : " + i.previousIndex()
+                + ", n val: " + n, i.previousIndex(), n);
+      }
+      ++n;
+    }
+    List myList = db.createLinkedList("testXX");
+    myList.add(null);
+    myList.add("Blah");
+    myList.add(null);
+    myList.add("Booga");
+    myList.add(null);
+    ListIterator li = myList.listIterator();
+    assertTrue("li.hasPrevious() should be false", !li.hasPrevious());
+    assertNull("li.next() should be null", li.next());
+    assertTrue("li.hasPrevious() should be true", li.hasPrevious());
+    assertNull("li.prev() should be null", li.previous());
+    assertNull("li.next() should be null", li.next());
+    assertEquals("li.next() should be Blah", "Blah", li.next());
+    assertNull("li.next() should be null", li.next());
+    assertEquals("li.next() should be Booga", "Booga", li.next());
+    assertTrue("li.hasNext() should be true", li.hasNext());
+    assertNull("li.next() should be null", li.next());
+    assertTrue("li.hasNext() should be false", !li.hasNext());
+  }
+
+  /**
+   * @tests java.util.LinkedList2#remove(int)
+   */
+  public void test_removeI() {
+    // Test for method java.lang.Object java.util.LinkedList2.remove(int)
+    ll.remove(10);
+    assertEquals("Failed to remove element", -1, ll.indexOf(objArray[10]));
+    try {
+      ll.remove(999);
+      fail("Failed to throw expected exception when index out of range");
+    } catch (IndexOutOfBoundsException e) {
+      // Correct
+    }
+
+    ll.add(20, null);
+    ll.remove(20);
+    assertNotNull("Should have removed null", ll.get(20));
+  }
+
+  /**
+   * @tests java.util.LinkedList2#remove(java.lang.Object)
+   */
+  public void test_removeLjava_lang_Object() {
+    // Test for method boolean java.util.LinkedList2.remove(java.lang.Object)
+    assertTrue("Failed to remove valid Object", ll.remove(objArray[87]));
+    assertTrue("Removed invalid object", !ll.remove(new Object()));
+    assertEquals("Found Object after removal", -1, ll.indexOf(objArray[87]));
+    ll.add(null);
+    ll.remove(null);
+    assertTrue("Should not contain null afrer removal", !ll.contains(null));
+  }
+
+  /**
+   * @tests java.util.LinkedList2#set(int, java.lang.Object)
+   */
+  public void test_setILjava_lang_Object() {
+    // Test for method java.lang.Object java.util.LinkedList2.set(int,
+    // java.lang.Object)
+    ll.set(65, "aa");
+    assertEquals("Failed to set object", ll.get(65), "aa");
+  }
+
+  /**
+   * @tests java.util.LinkedList2#size()
+   */
+  public void test_size() {
+    // Test for method int java.util.LinkedList2.size()
+    assertEquals("Returned incorrect size", ll.size(), objArray.length);
+
+    int counter = 0;
+    Iterator iter = ll.iterator();
+    while (iter.hasNext()) {
+      counter++;
+      iter.next();
+    }
+    assertEquals("Returned incorrect size", counter, objArray.length);
+
+    ll.remove(0);
+    assertEquals("Returned incorrect size", ll.size(), objArray.length - 1);
+  }
+
+  /**
+   * @tests java.util.LinkedList2#toArray()
+   */
+  public void test_toArray() {
+    // Test for method java.lang.Object [] java.util.LinkedList2.toArray()
+    ll.add(null);
+    Object[] obj = ll.toArray();
+    assertEquals("Returned array of incorrect size", objArray.length + 1,
+        obj.length);
+
+    for (int i = 0; i < obj.length - 1; i++)
+      assertEquals("Returned incorrect array: " + i, obj[i], objArray[i]);
+    assertNull("Returned incorrect array--end isn't null", obj[obj.length - 1]);
+  }
+
+  /**
+   * @tests java.util.LinkedList2#toArray(java.lang.Object[])
+   */
+  public void test_toArray$Ljava_lang_Object() {
+    // Test for method java.lang.Object []
+    // java.util.LinkedList2.toArray(java.lang.Object [])
+    Integer[] argArray = new Integer[100];
+    Object[] retArray;
+    retArray = ll.toArray(argArray);
+    assertTrue("Returned different array than passed", retArray == argArray);
+    List retList = db.createLinkedList("testXX1");
+    retList.addAll(Arrays.asList(retArray));
+    Iterator li = ll.iterator();
+    Iterator ri = retList.iterator();
+    while (li.hasNext())
+      assertEquals(li.next(), ri.next());
+    argArray = new Integer[1000];
+    retArray = ll.toArray(argArray);
+    assertNull("Failed to set first extra element to null", argArray[ll.size()]);
+    for (int i = 0; i < ll.size(); i++)
+      assertEquals("Returned incorrect array: " + i, retArray[i], objArray[i]);
+    ll.add(50, null);
+    argArray = new Integer[101];
+    retArray = ll.toArray(argArray);
+    assertTrue("Returned different array than passed", retArray == argArray);
+    retArray = ll.toArray(argArray);
+    assertTrue("Returned different array than passed", retArray == argArray);
+    retList = db.createLinkedList("testXX2");
+    retList.addAll(Arrays.asList(retArray));
+    li = ll.iterator();
+    ri = retList.iterator();
+    while (li.hasNext())
+      assertTrue("Lists are not equal", li.next() == ri.next());
+  }
+
+  /**
+   * @tests {@link java.util.LinkedList#remove()}
+   */
+  public void test_remove() {
+    for (int i = 0; i < objArray.length; i++) {
+      assertEquals("should remove the head", objArray[i], ll.remove(0));
+    }
+    assertEquals("should be empty", 0, ll.size());
+    try {
+      ll.remove(0);
+      fail("IndexOutOfBoundsException is expected when removing from the empty list");
+    } catch (IndexOutOfBoundsException e) {
+      // -- expected
+    }
+  }
+
+  /**
+   * Sets up the fixture, for example, open a network connection. This method is
+   * called before a test is executed.
+   */
+  @Override
+  public void setUp() throws Exception {
+    super.setUp();
+    this.db = newDBCache();
+    ll = (LinkedList) db.createLinkedList("ll");
+    for (int i = 0; i < objArray.length; i++) {
+      ll.add(objArray[i]);
+    }
+    testList = (LinkedList<Object>) db.createLinkedList("testList");
+    testObjOne = new Object();
+    testObjTwo = new Object();
+    testObjThree = new Object();
+    testObjFour = new Object();
+    testObjLast = new Object();
+  }
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LogicalRowIdManagerTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LogicalRowIdManagerTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LogicalRowIdManagerTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LogicalRowIdManagerTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,75 @@
+/**
+ * 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.hama.jdbm;
+
+/**
+ * This class contains all Unit tests for {@link LogicalRowIdManager}.
+ */
+public class LogicalRowIdManagerTest extends TestCaseWithTestFile {
+
+  /**
+   * Test constructor
+   */
+  public void testCtor() throws Exception {
+    PageFile f = newRecordFile();
+    PageManager pm = new PageManager(f);
+    PageFile free = newRecordFile();
+    PageManager pmfree = new PageManager(free);
+
+    LogicalRowIdManager logMgr = new LogicalRowIdManager(f, pm);
+
+    f.forceClose();
+  }
+
+  /**
+   * Test basics
+   */
+  public void testBasics() throws Exception {
+    PageFile f = newRecordFile();
+    PageManager pm = new PageManager(f);
+    PageFile free = newRecordFile();
+    PageManager pmfree = new PageManager(free);
+    LogicalRowIdManager logMgr = new LogicalRowIdManager(f, pm);
+    long physid = 20 << Storage.PAGE_SIZE_SHIFT + 234;
+
+    long logid = logMgr.insert(physid);
+    assertEquals("check one", physid, logMgr.fetch(logid));
+
+    physid = 10 << Storage.PAGE_SIZE_SHIFT + 567;
+    logMgr.update(logid, physid);
+    assertEquals("check two", physid, logMgr.fetch(logid));
+
+    logMgr.delete(logid);
+
+    f.forceClose();
+  }
+
+  public void testFreeBasics() throws Exception {
+    PageFile f = newRecordFile();
+    PageManager pm = new PageManager(f);
+    LogicalRowIdManager freeMgr = new LogicalRowIdManager(f, pm);
+
+    // allocate a rowid - should fail on an empty file
+    long loc = freeMgr.getFreeSlot();
+    assertTrue("loc is not null?", loc == 0);
+
+    pm.close();
+    f.close();
+  }
+
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongHashMapTest.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongHashMapTest.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongHashMapTest.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongHashMapTest.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,138 @@
+/**
+ * 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.hama.jdbm;
+
+import java.util.Iterator;
+import java.util.Random;
+import java.util.TreeMap;
+
+import junit.framework.TestCase;
+
+public class LongHashMapTest extends TestCase {
+
+  public void testAll() {
+    LongHashMap<String> t = new LongHashMap<String>();
+    t.put(1, "aa");
+    t.put(2, "bb");
+    t.put(2, "bb");
+    t.put(4, "cc");
+    t.put(9, "FF");
+    assertEquals(4, t.size());
+    t.remove(1);
+    assertEquals(3, t.size());
+    assertEquals(t.get(1), null);
+    assertEquals(t.get(2), "bb");
+    assertEquals(t.get(3), null);
+    assertEquals(t.get(4), "cc");
+    assertEquals(t.get(5), null);
+    assertEquals(t.get(-1), null);
+    assertEquals(t.get(9), "FF");
+
+    Iterator<String> vals = t.valuesIterator();
+    assertTrue(vals.hasNext());
+    assertEquals(vals.next(), "bb");
+    assertTrue(vals.hasNext());
+    assertEquals(vals.next(), "cc");
+    assertTrue(vals.hasNext());
+    assertEquals(vals.next(), "FF");
+
+    assertFalse(vals.hasNext());
+
+    t.clear();
+    assertEquals(0, t.size());
+    t.put(2, "bb");
+    assertEquals(1, t.size());
+    assertEquals(t.get(1), null);
+    assertEquals(t.get(2), "bb");
+    assertEquals(t.get(3), null);
+
+  }
+
+  public void testRandomCompare() {
+    LongHashMap<String> v1 = new LongHashMap<String>();
+    TreeMap<Long, String> v2 = new TreeMap<Long, String>();
+    Random d = new Random();
+    for (int i = 0; i < 1000; i++) {
+      long key = d.nextInt() % 100;
+      double random = d.nextDouble();
+      if (random < 0.8) {
+        // System.out.println("put "+key);
+        v1.put(key, "" + key);
+        v2.put(key, "" + key);
+      } else {
+        // System.out.println("remove "+key);
+        v1.remove(key);
+        v2.remove(key);
+      }
+      checkEquals(v1, v2);
+
+    }
+  }
+
+  public void checkEquals(LongHashMap<String> v1, TreeMap<Long, String> v2) {
+    assertEquals(v1.size(), v2.size());
+    for (long k : v2.keySet()) {
+      assertEquals(v1.get(k), v2.get(k));
+    }
+
+    int counter = 0;
+    Iterator<String> it = v1.valuesIterator();
+    while (it.hasNext()) {
+      String v = it.next();
+      long key = Long.valueOf(v);
+      assertEquals(v1.get(key), v);
+      assertEquals("" + key, v);
+      counter++;
+    }
+    assertEquals(counter, v2.size());
+  }
+
+  public void test2() {
+    LongHashMap<String> v1 = new LongHashMap<String>();
+    v1.put(1611, "1611");
+    v1.put(15500, "15500");
+    v1.put(9446, "9446");
+    System.out.println(v1.get(9446));
+    System.out.println(v1.toString());
+    assertEquals(3, v1.size());
+    assertEquals(v1.get(9446), "9446");
+
+  }
+
+  public void testMemoryConsuptio() {
+    System.out.println("Memory available: "
+        + (Runtime.getRuntime().maxMemory() / 1e6) + "MB");
+    System.out.println("Memory used: "
+        + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime()
+            .freeMemory()) / 1e6) + "MB");
+    long counter = 0;
+    LongHashMap<String> e = new LongHashMap<String>();
+    // LongKeyChainedHashMap<String> e = new LongKeyChainedHashMap<String>();
+    // LongTreeMap<String> e = new LongTreeMap<String>();
+    while (counter < 1e6) {
+      counter++;
+      e.put(counter, "");
+    }
+    System.out.println(counter + " items");
+    System.out.println("Memory used: "
+        + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime()
+            .freeMemory()) / 1e6) + "MB");
+
+  }
+
+}

Added: hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongTreeMap.java
URL: http://svn.apache.org/viewvc/hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongTreeMap.java?rev=1387533&view=auto
==============================================================================
--- hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongTreeMap.java (added)
+++ hama/trunk/jdbm/src/test/java/org/apache/hama/jdbm/LongTreeMap.java Wed Sep 19 11:52:20 2012
@@ -0,0 +1,510 @@
+/**
+ * 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.hama.jdbm;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+/**
+ * B-Tree Map which uses primitive long as key. Main advantage is new instanceof
+ * of Long does not have to be created for each lookup.
+ * <p/>
+ * This code comes from Android, which in turns comes to Apache Harmony. This
+ * class was modified to use primitive longs and stripped down to consume less
+ * space.
+ * <p/>
+ * Author of JDBM modifications: Jan Kotek
+ * <p/>
+ * It is much slower then LongKeyChainedHashMap, but may be usefull in future
+ * for better licence.
+ * 
+ * @param <V>
+ */
+public class LongTreeMap<V> {
+
+  private Entry<V> root;
+
+  private int size;
+
+  /**
+   * counts modifications to throw ConcurrentAccessException
+   */
+  private transient int modCount;
+
+  /**
+   * Returns the value of the mapping with the specified key.
+   * 
+   * @param key the key.
+   * @return the value of the mapping with the specified key.
+   * @throws ClassCastException if the key cannot be compared with the keys in
+   *           this map.
+   * @throws NullPointerException if the key is {@code null} and the comparator
+   *           cannot handle {@code null}.
+   * @since Android 1.0
+   */
+  public V get(long key) {
+    Entry<V> node = find(key);
+    if (node != null) {
+      return node.value;
+    }
+    return null;
+  }
+
+  /**
+   * Maps the specified key to the specified value.
+   * 
+   * @param key the key.
+   * @param value the value.
+   * @return the value of any previous mapping with the specified key or
+   *         {@code null} if there was no mapping.
+   * @throws ClassCastException if the specified key cannot be compared with the
+   *           keys in this map.
+   * @throws NullPointerException if the specified key is {@code null} and the
+   *           comparator cannot handle {@code null} keys.
+   * @since Android 1.0
+   */
+  public V put(long key, V value) {
+    Entry<V> entry = rbInsert(key);
+    V result = entry.value;
+    entry.value = value;
+    return result;
+  }
+
+  /**
+   * Removes the mapping with the specified key from this map.
+   * 
+   * @param key the key of the mapping to remove.
+   * @return the value of the removed mapping or {@code null} if no mapping for
+   *         the specified key was found.
+   * @throws ClassCastException if the specified key cannot be compared with the
+   *           keys in this map.
+   * @throws NullPointerException if the specified key is {@code null} and the
+   *           comparator cannot handle {@code null} keys.
+   * @since Android 1.0
+   */
+  public V remove(long key) {
+    if (size == 0) {
+      return null;
+    }
+    Entry<V> node = find(key);
+    if (node == null) {
+      return null;
+    }
+    V result = node.value;
+    rbDelete(node);
+    return result;
+  }
+
+  /**
+   * Removes all mappings from this TreeMap, leaving it empty.
+   * 
+   * @see Map#isEmpty()
+   * @see #size()
+   * @since Android 1.0
+   */
+  public void clear() {
+    root = null;
+    size = 0;
+    modCount++;
+  }
+
+  /**
+   * Entry is an internal class which is used to hold the entries of a TreeMap.
+   */
+  private static class Entry<V> {
+    Entry<V> parent, left, right;
+
+    long key;
+    V value;
+
+    boolean color;
+
+    Entry(long key, V value) {
+      this.key = key;
+      this.value = value;
+    }
+
+    public String toString() {
+      return super.toString() + " - " + key + " - " + value;
+    }
+  }
+
+  /**
+   * @return iterator over values in map
+   */
+  public Iterator<V> valuesIterator() {
+    return new ValueIterator();
+  }
+
+  /**
+   * @return iterator over keys in map
+   */
+  public LongIterator keyIterator() {
+    return new LongIterator();
+  }
+
+  private class MapIterator {
+
+    int expectedModCount;
+    Entry<V> node;
+    Entry<V> lastNode;
+
+    MapIterator() {
+      expectedModCount = modCount;
+      if (root != null)
+        node = minimum(root);
+    }
+
+    public boolean hasNext() {
+      return node != null;
+    }
+
+    final public void remove() {
+      if (expectedModCount == modCount) {
+        if (lastNode != null) {
+          rbDelete(lastNode);
+          lastNode = null;
+          expectedModCount++;
+        } else {
+          throw new IllegalStateException();
+        }
+      } else {
+        throw new ConcurrentModificationException();
+      }
+    }
+
+    final void makeNext() {
+      if (expectedModCount != modCount) {
+        throw new ConcurrentModificationException();
+      } else if (node == null) {
+        throw new NoSuchElementException();
+      }
+      lastNode = node;
+      node = successor(node);
+    }
+  }
+
+  private class ValueIterator extends MapIterator implements Iterator<V> {
+    public V next() {
+      makeNext();
+      return lastNode.value;
+    }
+  }
+
+  public class LongIterator extends MapIterator implements Iterator<Long> {
+    public Long next() {
+      makeNext();
+      return lastNode.key;
+    }
+
+    public long nextLong() {
+      makeNext();
+      return lastNode.key;
+    }
+
+  }
+
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  public int size() {
+    return size;
+  }
+
+  public String toString() {
+    String s = this.getClass().getName();
+    s += "[";
+    LongIterator iter = keyIterator();
+    boolean first = true;
+
+    while (iter.hasNext()) {
+      if (!first) {
+        s += ", ";
+      }
+      first = false;
+      long k = iter.nextLong();
+      s += k + "=" + get(k);
+    }
+    s += "]";
+    return s;
+  }
+
+  private Entry<V> find(long object) {
+    Entry<V> x = root;
+    while (x != null) {
+      // result = object != null ? object.compareTo(x.key) : comparator
+      // .compare(key, x.key);
+      // if (result == 0) {
+      // return x;
+      // }
+      // x = result < 0 ? x.left : x.right;
+      if (object == x.key)
+        return x;
+      x = object < x.key ? x.left : x.right;
+    }
+    return null;
+  }
+
+  private Entry<V> minimum(Entry<V> x) {
+    while (x.left != null) {
+      x = x.left;
+    }
+    return x;
+  }
+
+  Entry<V> successor(Entry<V> x) {
+    if (x.right != null) {
+      return minimum(x.right);
+    }
+    Entry<V> y = x.parent;
+    while (y != null && x == y.right) {
+      x = y;
+      y = y.parent;
+    }
+    return y;
+  }
+
+  void rbDelete(Entry<V> z) {
+    Entry<V> y = z.left == null || z.right == null ? z : successor(z);
+    Entry<V> x = y.left != null ? y.left : y.right;
+    if (x != null) {
+      x.parent = y.parent;
+    }
+    if (y.parent == null) {
+      root = x;
+    } else if (y == y.parent.left) {
+      y.parent.left = x;
+    } else {
+      y.parent.right = x;
+    }
+    modCount++;
+    if (y != z) {
+      z.key = y.key;
+      z.value = y.value;
+    }
+    if (!y.color && root != null) {
+      if (x == null) {
+        fixup(y.parent);
+      } else {
+        fixup(x);
+      }
+    }
+    size--;
+  }
+
+  private void fixup(Entry<V> x) {
+    Entry<V> w;
+    while (x != root && !x.color) {
+      if (x == x.parent.left) {
+        w = x.parent.right;
+        if (w == null) {
+          x = x.parent;
+          continue;
+        }
+        if (w.color) {
+          w.color = false;
+          x.parent.color = true;
+          leftRotate(x.parent);
+          w = x.parent.right;
+          if (w == null) {
+            x = x.parent;
+            continue;
+          }
+        }
+        if ((w.left == null || !w.left.color)
+            && (w.right == null || !w.right.color)) {
+          w.color = true;
+          x = x.parent;
+        } else {
+          if (w.right == null || !w.right.color) {
+            w.left.color = false;
+            w.color = true;
+            rightRotate(w);
+            w = x.parent.right;
+          }
+          w.color = x.parent.color;
+          x.parent.color = false;
+          w.right.color = false;
+          leftRotate(x.parent);
+          x = root;
+        }
+      } else {
+        w = x.parent.left;
+        if (w == null) {
+          x = x.parent;
+          continue;
+        }
+        if (w.color) {
+          w.color = false;
+          x.parent.color = true;
+          rightRotate(x.parent);
+          w = x.parent.left;
+          if (w == null) {
+            x = x.parent;
+            continue;
+          }
+        }
+        if ((w.left == null || !w.left.color)
+            && (w.right == null || !w.right.color)) {
+          w.color = true;
+          x = x.parent;
+        } else {
+          if (w.left == null || !w.left.color) {
+            w.right.color = false;
+            w.color = true;
+            leftRotate(w);
+            w = x.parent.left;
+          }
+          w.color = x.parent.color;
+          x.parent.color = false;
+          w.left.color = false;
+          rightRotate(x.parent);
+          x = root;
+        }
+      }
+    }
+    x.color = false;
+  }
+
+  private void leftRotate(Entry<V> x) {
+    Entry<V> y = x.right;
+    x.right = y.left;
+    if (y.left != null) {
+      y.left.parent = x;
+    }
+    y.parent = x.parent;
+    if (x.parent == null) {
+      root = y;
+    } else {
+      if (x == x.parent.left) {
+        x.parent.left = y;
+      } else {
+        x.parent.right = y;
+      }
+    }
+    y.left = x;
+    x.parent = y;
+  }
+
+  private void rightRotate(Entry<V> x) {
+    Entry<V> y = x.left;
+    x.left = y.right;
+    if (y.right != null) {
+      y.right.parent = x;
+    }
+    y.parent = x.parent;
+    if (x.parent == null) {
+      root = y;
+    } else {
+      if (x == x.parent.right) {
+        x.parent.right = y;
+      } else {
+        x.parent.left = y;
+      }
+    }
+    y.right = x;
+    x.parent = y;
+  }
+
+  private Entry<V> rbInsert(long object) {
+    boolean smaller = false;
+    Entry<V> y = null;
+    if (size != 0) {
+      Entry<V> x = root;
+      while (x != null) {
+        y = x;
+        // result = key != null ? key.compareTo(x.key) : comparator
+        // .compare(object, x.key);
+        // if (result == 0) {
+        // return x;
+        // }
+        // x = result < 0 ? x.left : x.right;
+        if (object == x.key)
+          return x;
+        if (object < x.key) {
+          x = x.left;
+          smaller = true;
+        } else {
+          x = x.right;
+          smaller = false;
+        }
+      }
+    }
+
+    size++;
+    modCount++;
+    Entry<V> z = new Entry<V>(object, null);
+    if (y == null) {
+      return root = z;
+    }
+    z.parent = y;
+    if (smaller) {
+      y.left = z;
+    } else {
+      y.right = z;
+    }
+    balance(z);
+    return z;
+  }
+
+  void balance(Entry<V> x) {
+    Entry<V> y;
+    x.color = true;
+    while (x != root && x.parent.color) {
+      if (x.parent == x.parent.parent.left) {
+        y = x.parent.parent.right;
+        if (y != null && y.color) {
+          x.parent.color = false;
+          y.color = false;
+          x.parent.parent.color = true;
+          x = x.parent.parent;
+        } else {
+          if (x == x.parent.right) {
+            x = x.parent;
+            leftRotate(x);
+          }
+          x.parent.color = false;
+          x.parent.parent.color = true;
+          rightRotate(x.parent.parent);
+        }
+      } else {
+        y = x.parent.parent.left;
+        if (y != null && y.color) {
+          x.parent.color = false;
+          y.color = false;
+          x.parent.parent.color = true;
+          x = x.parent.parent;
+        } else {
+          if (x == x.parent.left) {
+            x = x.parent;
+            rightRotate(x);
+          }
+          x.parent.color = false;
+          x.parent.parent.color = true;
+          leftRotate(x.parent.parent);
+        }
+      }
+    }
+    root.color = false;
+  }
+
+}



Mime
View raw message