Author: mes
Date: 2012-03-23 11:41:37 -0700 (Fri, 23 Mar 2012)
New Revision: 28628
Added:
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/IntTHashTest.java
Modified:
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/IntTHash.java
Log:
fixed array out of bounds problem in IntTHash and added unit tests to verify
the fix
Modified:
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/IntTHash.java
===================================================================
---
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/IntTHash.java
2012-03-23 17:04:57 UTC (rev 28627)
+++
core3/impl/trunk/model-impl/impl/src/main/java/org/cytoscape/model/internal/IntTHash.java
2012-03-23 18:41:37 UTC (rev 28628)
@@ -37,6 +37,7 @@
package org.cytoscape.model.internal;
import java.util.NoSuchElementException;
+import java.util.Arrays;
/**
@@ -110,6 +111,7 @@
* @exception NullPointerException if value is null.
*/
public final T put(final int key, final T value) {
+ //System.out.println("putting: " + key + " -> " + value);
if (key < 0)
throw new IllegalArgumentException("key is negative");
@@ -121,6 +123,7 @@
final Object returnVal = m_vals[m_prevInx];
if (returnVal == null) {
+ //System.out.println("m_elements: " + m_elements + "
m_thres: " + m_thresholdSize);
if (m_elements == m_thresholdSize) {
incrSize();
@@ -131,7 +134,10 @@
}
m_vals[m_prevInx] = value;
- m_keys[m_prevInx] = key;
+ if ( value == null )
+ m_keys[m_prevInx] = -1;
+ else
+ m_keys[m_prevInx] = key;
return clazz.cast(returnVal);
}
@@ -156,11 +162,19 @@
}
public final T remove(final int key) {
+ //System.out.println("about to remove: " + key + " size: " +
m_elements);
Object ret = get(key);
put(key,null);
+ m_elements--;
+ //System.out.println("removed: " + key + " size: " +
m_elements);
return clazz.cast(ret);
}
+ // for unit testing
+ int size() {
+ return m_elements;
+ }
+
private void calcPrevInx(int key) {
int incr = 0;
@@ -171,26 +185,26 @@
incr = 1 + (key % (m_keys.length - 1));
}
- private final void incrSize() {
- final int newSize;
-
+ private int calcNewSize() {
try {
int primesInx = 0;
- while (m_keys.length != PRIMES[primesInx++])
- ;
+ while (m_keys.length != PRIMES[primesInx++]);
- newSize = PRIMES[primesInx];
+ return PRIMES[primesInx];
} catch (ArrayIndexOutOfBoundsException e) {
throw new IllegalStateException("too many elements in
this hashtable");
}
+ }
+ private final void incrSize() {
+ //System.out.println("incrSize " + m_elements + " mkeys size:
" + m_keys.length);
+ final int newSize = calcNewSize();
+ //System.out.println("newSize " + newSize);
final int[] newKeys = new int[newSize];
final Object[] newVals = new Object[newSize];
+ Arrays.fill(newKeys, -1);
- for (int i = 0; i < newKeys.length; i++)
- newKeys[i] = -1;
-
m_thresholdSize = (int) (THRESHOLD_FACTOR * (double)
newKeys.length);
int incr;
@@ -198,22 +212,28 @@
int oldIndex = -1;
for (int i = 0; i < m_elements; i++) {
+ //System.out.println("element: " + i + " oldIndex: " +
oldIndex);
+ //System.out.println("INCR SIZE: " +
Arrays.toString(m_keys));
while (m_keys[++oldIndex] < 0);
incr = 0;
- for (newIndex = m_keys[oldIndex] % newKeys.length;
newKeys[newIndex] >= 0;
+ for (newIndex = m_keys[oldIndex] % newKeys.length;
+ newKeys[newIndex] >= 0;
newIndex = (newIndex + incr) % newKeys.length)
if (incr == 0)
incr = 1 + (m_keys[oldIndex] %
(newKeys.length - 1));
newKeys[newIndex] = m_keys[oldIndex];
newVals[newIndex] = m_vals[oldIndex];
+ //System.out.println("new index: " + newIndex + "
(old: " + oldIndex +")");
+ //System.out.println("new key: " + newKeys[newIndex] +
" (old: " + m_keys[oldIndex] +")");
}
m_keys = newKeys;
m_vals = newVals;
m_prevKey = -1;
m_prevInx = -1;
+ //System.out.println("new keys: " + Arrays.toString(newKeys));
}
}
Added:
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/IntTHashTest.java
===================================================================
---
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/IntTHashTest.java
(rev 0)
+++
core3/impl/trunk/model-impl/impl/src/test/java/org/cytoscape/model/internal/IntTHashTest.java
2012-03-23 18:41:37 UTC (rev 28628)
@@ -0,0 +1,80 @@
+
+package org.cytoscape.model.internal;
+
+import org.junit.Before;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class IntTHashTest {
+
+ @Test
+ public void testBasicPutGet() {
+ IntTHash<String> ith = new IntTHash<String>(String.class);
+ ith.put(1,"homer");
+ ith.put(2,"marge");
+ ith.put(3,"lisa");
+ assertEquals( "homer", ith.get(1) );
+ assertEquals( "marge", ith.get(2) );
+ assertEquals( "lisa", ith.get(3) );
+ }
+
+ @Test
+ public void testSize() {
+ IntTHash<String> ith = new IntTHash<String>(String.class);
+ ith.put(1,"homer");
+ ith.put(2,"marge");
+ ith.put(3,"lisa");
+ assertEquals( 3, ith.size() );
+ }
+
+ @Test
+ public void testRemove() {
+ IntTHash<String> ith = new IntTHash<String>(String.class);
+ ith.put(1,"homer");
+ ith.put(2,"marge");
+ ith.put(3,"lisa");
+
+ assertEquals( 3, ith.size() );
+
+ ith.remove(3);
+ assertEquals( 2, ith.size() );
+ assertNull( ith.get(3) );
+
+ ith.remove(2);
+ assertEquals( 1, ith.size() );
+ assertNull( ith.get(2) );
+
+ ith.remove(1);
+ assertEquals( 0, ith.size() );
+ assertNull( ith.get(1) );
+ }
+
+ @Test
+ public void testAddRemove() {
+ IntTHash<String> ith = new IntTHash<String>(String.class);
+ ith.put(1,"homer");
+ ith.put(2,"marge");
+ ith.put(3,"lisa");
+ ith.put(4,"bart");
+ ith.put(5,"maggie");
+ ith.put(6,"smithers");
+ ith.put(7,"burns");
+
+ ith.remove(1);
+ ith.remove(2);
+ ith.remove(3);
+
+ ith.put(1,"homer");
+ ith.put(2,"marge");
+ ith.put(3,"lisa");
+
+ ith.remove(4);
+ ith.remove(5);
+ ith.remove(6);
+
+ ith.put(4,"bart");
+ ith.put(5,"maggie");
+ ith.put(6,"smithers");
+ }
+
+}
--
You received this message because you are subscribed to the Google Groups
"cytoscape-cvs" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/cytoscape-cvs?hl=en.
