You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pivot.apache.org by gb...@apache.org on 2009/08/24 19:46:06 UTC
svn commit: r807318 - in /incubator/pivot/trunk/core:
src/org/apache/pivot/collections/ArrayList.java
src/org/apache/pivot/collections/HashMap.java
src/org/apache/pivot/collections/LinkedList.java
test/org/apache/pivot/collections/test/HashMapTest.java
Author: gbrown
Date: Mon Aug 24 17:46:05 2009
New Revision: 807318
URL: http://svn.apache.org/viewvc?rev=807318&view=rev
Log:
Resolve PIVOT-20.
Modified:
incubator/pivot/trunk/core/src/org/apache/pivot/collections/ArrayList.java
incubator/pivot/trunk/core/src/org/apache/pivot/collections/HashMap.java
incubator/pivot/trunk/core/src/org/apache/pivot/collections/LinkedList.java
incubator/pivot/trunk/core/test/org/apache/pivot/collections/test/HashMapTest.java
Modified: incubator/pivot/trunk/core/src/org/apache/pivot/collections/ArrayList.java
URL: http://svn.apache.org/viewvc/incubator/pivot/trunk/core/src/org/apache/pivot/collections/ArrayList.java?rev=807318&r1=807317&r2=807318&view=diff
==============================================================================
--- incubator/pivot/trunk/core/src/org/apache/pivot/collections/ArrayList.java (original)
+++ incubator/pivot/trunk/core/src/org/apache/pivot/collections/ArrayList.java Mon Aug 24 17:46:05 2009
@@ -21,6 +21,7 @@
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
+import java.util.NoSuchElementException;
import org.apache.pivot.util.ListenerList;
@@ -46,6 +47,10 @@
}
public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
if (length != ArrayList.this.length) {
throw new ConcurrentModificationException();
}
@@ -398,12 +403,14 @@
sb.append(getClass().getName());
sb.append(" [");
- for (int i = 0; i < length; i++) {
+ int i = 0;
+ for (T item : this) {
if (i > 0) {
sb.append(", ");
}
- sb.append(items[i]);
+ sb.append(item);
+ i++;
}
sb.append("]");
Modified: incubator/pivot/trunk/core/src/org/apache/pivot/collections/HashMap.java
URL: http://svn.apache.org/viewvc/incubator/pivot/trunk/core/src/org/apache/pivot/collections/HashMap.java?rev=807318&r1=807317&r2=807318&view=diff
==============================================================================
--- incubator/pivot/trunk/core/src/org/apache/pivot/collections/HashMap.java (original)
+++ incubator/pivot/trunk/core/src/org/apache/pivot/collections/HashMap.java Mon Aug 24 17:46:05 2009
@@ -18,33 +18,92 @@
import java.io.Serializable;
import java.util.Comparator;
+import java.util.ConcurrentModificationException;
import java.util.Iterator;
+import java.util.NoSuchElementException;
import org.apache.pivot.util.ImmutableIterator;
import org.apache.pivot.util.ListenerList;
-
/**
* Implementation of the {@link Map} interface that is backed by a
* hash table.
* <p>
- * TODO We're temporarily using a java.util.HashMap to back this map.
- * Eventually, we'll replace this with an internal map representation.
+ * TODO Optimize bucket management when a comparator is applied by using binary search to
+ * sort bucket contents and locate pairs.
*/
public class HashMap<K, V> implements Map<K, V>, Serializable {
+ private class KeyIterator implements Iterator<K> {
+ private int bucketIndex = 0;
+ private int pairIndex = 0;
+ private int count;
+
+ public KeyIterator() {
+ count = HashMap.this.count;
+ }
+
+ public boolean hasNext() {
+ // Locate the next pair
+ while (bucketIndex < buckets.getLength()
+ && pairIndex == buckets.get(bucketIndex).getLength()) {
+ bucketIndex++;
+ pairIndex = 0;
+ }
+
+ return (bucketIndex < buckets.getLength()
+ && pairIndex < buckets.get(bucketIndex).getLength());
+ }
+
+ public K next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ if (count != HashMap.this.count) {
+ throw new ConcurrentModificationException();
+ }
+
+ // Return the current pair
+ ArrayList<Pair<K, V>> bucket = buckets.get(bucketIndex);
+ Pair<K, V> pair = bucket.get(pairIndex++);
+
+ return pair.key;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
private static final long serialVersionUID = 0;
- protected java.util.Map<K, V> hashMap = null;
+ private ArrayList<ArrayList<Pair<K, V>>> buckets;
+ private float loadFactor;
+
+ private int count = 0;
+ private ArrayList<K> keys = null;
- private Comparator<K> comparator = null;
private transient MapListenerList<K, V> mapListeners = new MapListenerList<K, V>();
+ public static final int DEFAULT_CAPACITY = 16;
+ public static final float DEFAULT_LOAD_FACTOR = 0.75f;
+
public HashMap() {
- hashMap = new java.util.HashMap<K, V>();
+ this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+ }
+
+ public HashMap(int capacity) {
+ this(capacity, DEFAULT_LOAD_FACTOR);
+ }
+
+ public HashMap(int capacity, float loadFactor) {
+ this.loadFactor = loadFactor;
+
+ rehash(capacity);
}
public HashMap(Pair<K, V>... pairs) {
- this();
+ this(Math.max((int)((float)pairs.length / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_CAPACITY));
for (int i = 0; i < pairs.length; i++) {
Pair<K, V> pair = pairs[i];
@@ -53,7 +112,7 @@
}
public HashMap(Map<K, V> map) {
- this();
+ this(Math.max((int)((float)map.getCount() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_CAPACITY));
if (map != null) {
for (K key : map) {
@@ -63,24 +122,67 @@
}
public HashMap(Comparator<K> comparator) {
- // TODO
- throw new UnsupportedOperationException("HashMap auto-sorting is not yet supported.");
+ this();
- // this.comparator = comparator;
+ setComparator(comparator);
}
public V get(K key) {
- return hashMap.get(key);
+ V value = null;
+
+ // Locate the pair
+ int bucketIndex = getBucketIndex(key);
+ ArrayList<Pair<K, V>> bucket = buckets.get(bucketIndex);
+
+ int n = bucket.getLength();
+ int i = 0;
+
+ while (i < n
+ && !bucket.get(i).key.equals(key)) {
+ i++;
+ }
+
+ if (i < n) {
+ value = bucket.get(i).value;
+ }
+
+ return value;
}
public V put(K key, V value) {
- boolean update = hashMap.containsKey(key);
- V previousValue = hashMap.put(key, value);
+ V previousValue = null;
- if (update) {
- mapListeners.valueUpdated(this, key, previousValue);
+ // Locate the pair
+ int bucketIndex = getBucketIndex(key);
+ ArrayList<Pair<K, V>> bucket = buckets.get(bucketIndex);
+
+ int n = bucket.getLength();
+ int i = 0;
+
+ while (i < n
+ && !bucket.get(i).key.equals(key)) {
+ i++;
}
- else {
+
+ if (i < n) {
+ // Update the pair
+ previousValue = bucket.update(i, new Pair<K, V>(key, value)).value;
+ mapListeners.valueUpdated(this, key, previousValue);
+ } else {
+ // Add the pair
+ bucket.add(new Pair<K, V>(key, value));
+
+ if (keys != null) {
+ keys.add(key);
+ }
+
+ count++;
+
+ int capacity = getCapacity();
+ if (count > (int)((float)capacity * loadFactor)) {
+ rehash(capacity * 2);
+ }
+
mapListeners.valueAdded(this, key);
}
@@ -90,8 +192,29 @@
public V remove(K key) {
V value = null;
- if (hashMap.containsKey(key)) {
- value = hashMap.remove(key);
+ // Locate the pair
+ int bucketIndex = getBucketIndex(key);
+ ArrayList<Pair<K, V>> bucket = buckets.get(bucketIndex);
+
+ int n = bucket.getLength();
+ int i = 0;
+
+ while (i < n
+ && !bucket.get(i).key.equals(key)) {
+ i++;
+ }
+
+ if (i < n) {
+ // Remove the pair
+ Sequence<Pair<K, V>> removed = bucket.remove(i, 1);
+ value = removed.get(0).value;
+
+ if (keys != null) {
+ keys.remove(key);
+ }
+
+ count--;
+
mapListeners.valueRemoved(this, key, value);
}
@@ -99,35 +222,101 @@
}
public void clear() {
- if (!hashMap.isEmpty()) {
- hashMap.clear();
+ if (count > 0) {
+ for (ArrayList<Pair<K, V>> bucket : buckets) {
+ bucket.clear();
+ }
+
+ if (keys != null) {
+ keys.clear();
+ }
+
+ count = 0;
+
mapListeners.mapCleared(this);
}
}
public boolean containsKey(K key) {
- return hashMap.containsKey(key);
+ // Locate the pair
+ int bucketIndex = getBucketIndex(key);
+ ArrayList<Pair<K, V>> bucket = buckets.get(bucketIndex);
+
+ int n = bucket.getLength();
+ int i = 0;
+
+ while (i < n
+ && !bucket.get(i).key.equals(key)) {
+ i++;
+ }
+
+ return (i < n);
}
public boolean isEmpty() {
- return hashMap.isEmpty();
+ return (count == 0);
}
public int getCount() {
- return hashMap.size();
+ return count;
+ }
+
+ public int getCapacity() {
+ return buckets.getLength();
+ }
+
+ private void rehash(int capacity) {
+ ArrayList<ArrayList<Pair<K, V>>> previousBuckets = this.buckets;
+ buckets = new ArrayList<ArrayList<Pair<K, V>>>(capacity);
+
+ for (int i = 0; i < capacity; i++) {
+ buckets.add(new ArrayList<Pair<K, V>>());
+ }
+
+ if (previousBuckets != null) {
+ for (ArrayList<Pair<K, V>> bucket : previousBuckets) {
+ for (Pair<K, V> pair : bucket) {
+ put(pair.key, pair.value);
+ }
+ }
+ }
+ }
+
+ private int getBucketIndex(K key) {
+ int hashCode = key.hashCode();
+ return Math.abs(hashCode % getCapacity());
}
public Comparator<K> getComparator() {
- return comparator;
+ return (keys == null) ? null : keys.getComparator();
}
public void setComparator(Comparator<K> comparator) {
- // TODO
- throw new UnsupportedOperationException("HashMap auto-sorting is not yet supported.");
+ Comparator<K> previousComparator = getComparator();
+
+ if (comparator != previousComparator) {
+ if (comparator == null) {
+ keys = null;
+ } else {
+ if (keys == null) {
+ // Populate key list
+ ArrayList<K> keys = new ArrayList<K>((int)((float)getCapacity() * loadFactor));
+ for (K key : this) {
+ keys.add(key);
+ }
+
+ this.keys = keys;
+ }
+
+ keys.setComparator(comparator);
+ }
+
+ mapListeners.comparatorChanged(this, previousComparator);
+ }
}
public Iterator<K> iterator() {
- return new ImmutableIterator<K>(hashMap.keySet().iterator());
+ return (keys == null) ? new KeyIterator() : new ImmutableIterator<K>(keys.iterator());
}
public ListenerList<MapListener<K, V>> getMapListeners() {
@@ -135,6 +324,23 @@
}
public String toString() {
- return hashMap.toString();
+ StringBuilder sb = new StringBuilder();
+
+ sb.append(getClass().getName());
+ sb.append(" {");
+
+ int i = 0;
+ for (K key : this) {
+ if (i > 0) {
+ sb.append(", ");
+ }
+
+ sb.append(key + ":" + get(key));
+ i++;
+ }
+
+ sb.append("}");
+
+ return sb.toString();
}
}
Modified: incubator/pivot/trunk/core/src/org/apache/pivot/collections/LinkedList.java
URL: http://svn.apache.org/viewvc/incubator/pivot/trunk/core/src/org/apache/pivot/collections/LinkedList.java?rev=807318&r1=807317&r2=807318&view=diff
==============================================================================
--- incubator/pivot/trunk/core/src/org/apache/pivot/collections/LinkedList.java (original)
+++ incubator/pivot/trunk/core/src/org/apache/pivot/collections/LinkedList.java Mon Aug 24 17:46:05 2009
@@ -60,7 +60,7 @@
}
public T next() {
- if (node == null) {
+ if (!hasNext()) {
throw new NoSuchElementException();
}
Modified: incubator/pivot/trunk/core/test/org/apache/pivot/collections/test/HashMapTest.java
URL: http://svn.apache.org/viewvc/incubator/pivot/trunk/core/test/org/apache/pivot/collections/test/HashMapTest.java?rev=807318&r1=807317&r2=807318&view=diff
==============================================================================
--- incubator/pivot/trunk/core/test/org/apache/pivot/collections/test/HashMapTest.java (original)
+++ incubator/pivot/trunk/core/test/org/apache/pivot/collections/test/HashMapTest.java Mon Aug 24 17:46:05 2009
@@ -27,6 +27,7 @@
import java.util.Comparator;
import java.util.Iterator;
+import org.apache.pivot.collections.ArrayList;
import org.apache.pivot.collections.HashMap;
import org.apache.pivot.collections.Map;
import org.junit.Test;
@@ -98,7 +99,7 @@
@Test
@SuppressWarnings("unchecked")
public void constructorTests() throws Exception {
- // don't like the warning generated here ...
+ // TODO Verify that this does not generate a warning under JDK 7
HashMap<String, Integer> map = new HashMap<String, Integer>(
new Map.Pair<String, Integer>("a", 1),
new Map.Pair<String, Integer>("b", 2));
@@ -113,28 +114,28 @@
}
@Test
- public void exceptionTests() throws Exception {
- Comparator<String> comparator = new Comparator<String>() {
- @Override
- public int compare(String o1, String o2) {
- return o1.compareTo(o2);
+ public void comparatorTest() {
+ Comparator<Character> comparator = new Comparator<Character>() {
+ public int compare(Character c1, Character c2) {
+ return c1.compareTo(c2);
}
};
- try {
- new HashMap<String, Integer>(comparator);
- fail("Expected " + UnsupportedOperationException.class);
- } catch (UnsupportedOperationException e) {
- // ignore, we're expecting this as part of the test
+ HashMap<Character, Integer> map = new HashMap<Character, Integer>(comparator);
+ ArrayList<Character> keys = new ArrayList<Character>('c', 'a', 'x', 'r', 'd', 'n', 'f');
+
+ int n = keys.getLength();
+
+ int i = 0;
+ while (i < n) {
+ map.put(keys.get(i), i++);
}
- try {
- HashMap<String, Integer> map = new HashMap<String, Integer>();
- map.setComparator(comparator);
- fail("Expected " + UnsupportedOperationException.class);
- } catch (UnsupportedOperationException e) {
- // ignore, we're expecting this as part of the test
+ keys.setComparator(comparator);
+
+ int j = 0;
+ for (Character c : keys) {
+ assertEquals(keys.get(j++), c);
}
}
-
}