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; + } + +}
