scolebourne 2003/12/03 11:04:41
Modified: collections/src/java/org/apache/commons/collections/map
HashedMap.java
collections/src/test/org/apache/commons/collections/map
TestAll.java
Added: collections/src/java/org/apache/commons/collections/map
LinkedMap.java
collections/src/test/org/apache/commons/collections/map
TestLinkedMap.java
Log:
Add LinkedMap map implementation
Revision Changes Path
1.5 +44 -15
jakarta-commons/collections/src/java/org/apache/commons/collections/map/HashedMap.java
Index: HashedMap.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/HashedMap.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- HashedMap.java 2 Dec 2003 23:51:50 -0000 1.4
+++ HashedMap.java 3 Dec 2003 19:04:41 -0000 1.5
@@ -105,21 +105,21 @@
protected static final Object NULL = new Object();
/** Load factor, normally 0.75 */
- private final float loadFactor;
+ protected final float loadFactor;
/** The size of the map */
- private transient int size;
+ protected transient int size;
/** Map entries */
- private transient HashEntry[] data;
+ protected transient HashEntry[] data;
/** Size at which to rehash */
- private transient int threshold;
+ protected transient int threshold;
/** Modification count for iterators */
- private transient int modCount;
+ protected transient int modCount;
/** Entry set */
- private transient EntrySet entrySet;
+ protected transient EntrySet entrySet;
/** Key set */
- private transient KeySet keySet;
+ protected transient KeySet keySet;
/** Values */
- private transient Values values;
+ protected transient Values values;
/**
* Constructs a new empty map with default size and load factor.
@@ -129,6 +129,7 @@
this.loadFactor = DEFAULT_LOAD_FACTOR;
this.threshold = calculateThreshold(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
this.data = new HashEntry[DEFAULT_CAPACITY];
+ init();
}
/**
@@ -162,6 +163,7 @@
this.threshold = calculateThreshold(initialCapacity, loadFactor);
initialCapacity = calculateNewCapacity(initialCapacity);
this.data = new HashEntry[initialCapacity];
+ init();
}
/**
@@ -175,6 +177,12 @@
putAll(map);
}
+ /**
+ * Initialise subclasses during construction.
+ */
+ protected void init() {
+ }
+
//-----------------------------------------------------------------------
/**
* Gets the value mapped to the key specified.
@@ -353,6 +361,25 @@
//-----------------------------------------------------------------------
/**
+ * Gets the entry mapped to the key specified.
+ *
+ * @param key the key
+ * @return the entry, null if no match
+ */
+ protected HashEntry getEntry(Object key) {
+ key = convertKey(key);
+ int hashCode = hash(key);
+ HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for
hash index
+ while (entry != null) {
+ if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
+ return entry;
+ }
+ entry = entry.next;
+ }
+ return null;
+ }
+
+ /**
* Converts input keys to another object for storage in the map.
* This implementation masks nulls.
* Subclasses can override this to perform alternate key conversions.
@@ -875,11 +902,11 @@
* Base Iterator
*/
protected static abstract class HashIterator implements Iterator {
- private final HashedMap map;
- private int hashIndex;
- private HashEntry current;
- private HashEntry next;
- private int expectedModCount;
+ protected final HashedMap map;
+ protected int hashIndex;
+ protected HashEntry current;
+ protected HashEntry next;
+ protected int expectedModCount;
protected HashIterator(HashedMap map) {
super();
@@ -966,6 +993,7 @@
int capacity = in.readInt();
int size = in.readInt();
data = new HashEntry[capacity];
+ init();
for (int i = 0; i < size; i++) {
Object key = in.readObject();
Object value = in.readObject();
@@ -987,6 +1015,7 @@
cloned.values = null;
cloned.modCount = 0;
cloned.size = 0;
+ init();
cloned.putAll(this);
return cloned;
1.1
jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java
Index: LinkedMap.java
===================================================================
/*
* $Header:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java,v
1.1 2003/12/03 19:04:41 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
*/
package org.apache.commons.collections.map;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import org.apache.commons.collections.IteratorUtils;
import org.apache.commons.collections.MapIterator;
import org.apache.commons.collections.OrderedIterator;
import org.apache.commons.collections.OrderedMap;
import org.apache.commons.collections.OrderedMapIterator;
import org.apache.commons.collections.ResettableIterator;
/**
* A <code>Map</code> implementation that maintains the order of the entries.
* The order maintained is by insertion.
* <p>
* This implementation improves on the JDK1.4 LinkedHashMap by adding the
* [EMAIL PROTECTED] org.apache.commons.collections.iterators.MapIterator
MapIterator}
* functionality, additional convenience methods and allowing
* bidirectional iteration. It also implements <code>OrderedMap</code>.
* <p>
* The <code>orderedMapIterator()</code> method provides direct access to a
* bidirectional iterator. The iterators from the other views can also be cast
* to <code>OrderedIterator</code> if required.
* <p>
* All the available iterators can be reset back to the start by casting to
* <code>ResettableIterator</code> and calling <code>reset()</code>.
*
* @since Commons Collections 3.0
* @version $Revision: 1.1 $ $Date: 2003/12/03 19:04:41 $
*
* @author java util LinkedHashMap
* @author Stephen Colebourne
*/
public class LinkedMap extends HashedMap implements OrderedMap {
/** Serialisation version */
static final long serialVersionUID = -1954063410665686469L;
/** Header in the linked list */
private transient LinkedEntry header;
/**
* Constructs a new empty map with default size and load factor.
*/
public LinkedMap() {
super();
}
/**
* Constructs a new, empty map with the specified initial capacity.
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is less than one
*/
public LinkedMap(int initialCapacity) {
super(initialCapacity);
}
/**
* Constructs a new, empty map with the specified initial capacity and
* load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is less than one
* @throws IllegalArgumentException if the load factor is less than one
*/
public LinkedMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
}
/**
* Constructor copying elements from another map.
*
* @param map the map to copy
* @throws NullPointerException if the map is null
*/
public LinkedMap(Map map) {
super(map);
}
/**
* Initialise this subclass during construction.
*/
protected void init() {
header = new LinkedEntry(null, -1, null, null);
header.before = header.after = header;
}
//-----------------------------------------------------------------------
/**
* Checks whether the map contains the specified value.
*
* @param value the value to search for
* @return true if the map contains the value
*/
public boolean containsValue(Object value) {
// override uses faster iterator
if (value == null) {
for (LinkedEntry entry = header.after; entry != header; entry =
entry.after) {
if (entry.getValue() == null) {
return true;
}
}
} else {
for (LinkedEntry entry = header.after; entry != header; entry =
entry.after) {
if (isEqualValue(value, entry.getValue())) {
return true;
}
}
}
return false;
}
/**
* Clears the map, resetting the size to zero and nullifying references
* to avoid garbage collection issues.
*/
public void clear() {
// override to reset the linked list
super.clear();
header.before = header.after = header;
}
//-----------------------------------------------------------------------
/**
* Gets the first key in the map, which is the most recently inserted.
*
* @return the most recently inserted key
*/
public Object firstKey() {
if (size == 0) {
throw new NoSuchElementException("Map is empty");
}
return header.after.getKey();
}
/**
* Gets the last key in the map, which is the first inserted.
*
* @return the eldest key
*/
public Object lastKey() {
if (size == 0) {
throw new NoSuchElementException("Map is empty");
}
return header.before.getKey();
}
/**
* Gets the next key in sequence.
*
* @param key the key to get after
* @return the next key
*/
public Object nextKey(Object key) {
LinkedEntry entry = (LinkedEntry) getEntry(key);
return (entry == null || entry.after == header ? null :
entry.after.getKey());
}
/**
* Gets the previous key in sequence.
*
* @param key the key to get before
* @return the previous key
*/
public Object previousKey(Object key) {
LinkedEntry entry = (LinkedEntry) getEntry(key);
return (entry == null || entry.before == header ? null :
entry.before.getKey());
}
//-----------------------------------------------------------------------
/**
* Creates an entry to store the data.
* This implementation creates a LinkEntry instance in the linked list.
*
* @param next the next entry in sequence
* @param hashCode the hash code to use
* @param key the key to store
* @param value the value to store
* @return the newly created entry
*/
protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object
value) {
LinkedEntry entry = new LinkedEntry(next, hashCode, key, value);
entry.after = header;
entry.before = header.before;
header.before.after = entry;
header.before = entry;
return entry;
}
/**
* Kills an entry ready for the garbage collector.
* This implementation manages the linked list and prepares the
* LinkEntry for garbage collection.
*
* @param entry the entry to destroy
* @return the value from the entry
*/
protected Object destroyEntry(HashEntry entry) {
LinkedEntry link = (LinkedEntry) entry;
link.before.after = link.after;
link.after.before = link.before;
link.next = null;
link.after = null;
link.before = null;
return entry.value;
}
//-----------------------------------------------------------------------
/**
* Gets an iterator over the map.
* Changes made to the iterator affect this map.
* <p>
* A MapIterator returns the keys in the map. It also provides convenient
* methods to get the key and value, and set the value.
* It avoids the need to create an entrySet/keySet/values object.
* It also avoids creating the Mep Entry object.
*
* @return the map iterator
*/
public MapIterator mapIterator() {
if (size == 0) {
return IteratorUtils.EMPTY_ORDERED_MAP_ITERATOR;
}
return new LinkedMapIterator(this);
}
/**
* Gets a bidirectional iterator over the map.
* Changes made to the iterator affect this map.
* <p>
* A MapIterator returns the keys in the map. It also provides convenient
* methods to get the key and value, and set the value.
* It avoids the need to create an entrySet/keySet/values object.
* It also avoids creating the Mep Entry object.
*
* @return the map iterator
*/
public OrderedMapIterator orderedMapIterator() {
if (size == 0) {
return IteratorUtils.EMPTY_ORDERED_MAP_ITERATOR;
}
return new LinkedMapIterator(this);
}
/**
* MapIterator
*/
static class LinkedMapIterator extends LinkedIterator implements
OrderedMapIterator {
LinkedMapIterator(LinkedMap map) {
super(map);
}
public Object next() {
return super.nextEntry().getKey();
}
public Object previous() {
return super.previousEntry().getKey();
}
public Object getKey() {
HashEntry current = currentEntry();
if (current == null) {
throw new IllegalStateException("Iterator remove() can only be
called once after next()");
}
return current.getKey();
}
public Object getValue() {
HashEntry current = currentEntry();
if (current == null) {
throw new IllegalStateException("Iterator remove() can only be
called once after next()");
}
return current.getValue();
}
public Object setValue(Object value) {
HashEntry current = currentEntry();
if (current == null) {
throw new IllegalStateException("Iterator remove() can only be
called once after next()");
}
return current.setValue(value);
}
}
//-----------------------------------------------------------------------
/**
* Creates an entry set iterator.
* Subclasses can override this to return iterators with different properties.
*
* @return the entrySet iterator
*/
protected Iterator createEntrySetIterator() {
if (size() == 0) {
return IteratorUtils.EMPTY_ORDERED_ITERATOR;
}
return new EntrySetIterator(this);
}
/**
* EntrySetIterator and MapEntry
*/
static class EntrySetIterator extends LinkedIterator {
EntrySetIterator(LinkedMap map) {
super(map);
}
public Object next() {
return super.nextEntry();
}
public Object previous() {
return super.previousEntry();
}
}
//-----------------------------------------------------------------------
/**
* Creates a key set iterator.
* Subclasses can override this to return iterators with different properties.
*
* @return the keySet iterator
*/
protected Iterator createKeySetIterator() {
if (size() == 0) {
return IteratorUtils.EMPTY_ORDERED_ITERATOR;
}
return new KeySetIterator(this);
}
/**
* KeySetIterator
*/
static class KeySetIterator extends EntrySetIterator {
KeySetIterator(LinkedMap map) {
super(map);
}
public Object next() {
return super.nextEntry().getKey();
}
public Object previous() {
return super.previousEntry().getKey();
}
}
//-----------------------------------------------------------------------
/**
* Creates a values iterator.
* Subclasses can override this to return iterators with different properties.
*
* @return the values iterator
*/
protected Iterator createValuesIterator() {
if (size() == 0) {
return IteratorUtils.EMPTY_ORDERED_ITERATOR;
}
return new ValuesIterator(this);
}
/**
* ValuesIterator
*/
static class ValuesIterator extends LinkedIterator {
ValuesIterator(LinkedMap map) {
super(map);
}
public Object next() {
return super.nextEntry().getValue();
}
public Object previous() {
return super.previousEntry().getValue();
}
}
//-----------------------------------------------------------------------
/**
* LinkEntry
*/
protected static class LinkedEntry extends HashEntry {
LinkedEntry before;
LinkedEntry after;
protected LinkedEntry(HashEntry next, int hashCode, Object key, Object
value) {
super(next, hashCode, key, value);
}
}
/**
* Base Iterator
*/
protected static abstract class LinkedIterator
implements OrderedIterator, ResettableIterator {
private final LinkedMap map;
private LinkedEntry current;
private LinkedEntry next;
private int expectedModCount;
protected LinkedIterator(LinkedMap map) {
super();
this.map = map;
this.next = map.header.after;
this.expectedModCount = map.modCount;
}
public boolean hasNext() {
return (next != map.header);
}
public boolean hasPrevious() {
return (next.before != map.header);
}
protected LinkedEntry nextEntry() {
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (next == map.header) {
throw new NoSuchElementException("No more elements in the
iteration");
}
current = next;
next = next.after;
return current;
}
protected LinkedEntry previousEntry() {
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
LinkedEntry previous = next.before;
if (previous == map.header) {
throw new NoSuchElementException("No more elements in the
iteration");
}
next = previous;
current = previous;
return current;
}
protected LinkedEntry currentEntry() {
return current;
}
public void remove() {
if (current == null) {
throw new IllegalStateException("Iterator remove() can only be
called once after next()");
}
if (map.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
map.remove(current.getKey());
current = null;
expectedModCount = map.modCount;
}
public void reset() {
current = null;
next = map.header.after;
}
public String toString() {
if (current != null) {
return "Iterator[" + current.getKey() + "=" + current.getValue() +
"]";
} else {
return "Iterator[]";
}
}
}
}
1.9 +3 -2
jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java
Index: TestAll.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- TestAll.java 3 Dec 2003 15:50:12 -0000 1.8
+++ TestAll.java 3 Dec 2003 19:04:41 -0000 1.9
@@ -86,6 +86,7 @@
suite.addTest(TestFlat3Map.suite());
suite.addTest(TestHashedMap.suite());
suite.addTest(TestIdentityMap.suite());
+ suite.addTest(TestLinkedMap.suite());
suite.addTest(TestReferenceMap.suite());
suite.addTest(TestStaticBucketMap.suite());
1.1
jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLinkedMap.java
Index: TestLinkedMap.java
===================================================================
/*
* $Header:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLinkedMap.java,v
1.1 2003/12/03 19:04:41 scolebourne Exp $
* ====================================================================
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001-2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
*/
package org.apache.commons.collections.map;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import junit.framework.Test;
import junit.textui.TestRunner;
import org.apache.commons.collections.BulkTest;
import org.apache.commons.collections.OrderedMap;
import org.apache.commons.collections.ResettableIterator;
/**
* JUnit tests.
*
* @version $Revision: 1.1 $ $Date: 2003/12/03 19:04:41 $
*
* @author Stephen Colebourne
*/
public class TestLinkedMap extends AbstractTestOrderedMap {
public TestLinkedMap(String testName) {
super(testName);
}
public static void main(String[] args) {
TestRunner.run(suite());
}
public static Test suite() {
return BulkTest.makeSuite(TestLinkedMap.class);
}
public Map makeEmptyMap() {
return new LinkedMap();
}
public String getCompatibilityVersion() {
return "3";
}
//-----------------------------------------------------------------------
public void testReset() {
resetEmpty();
OrderedMap ordered = (OrderedMap) map;
((ResettableIterator) ordered.mapIterator()).reset();
resetFull();
ordered = (OrderedMap) map;
List list = new ArrayList(ordered.keySet());
ResettableIterator it = (ResettableIterator) ordered.mapIterator();
assertSame(list.get(0), it.next());
assertSame(list.get(1), it.next());
it.reset();
assertSame(list.get(0), it.next());
}
// public void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk((Serializable) map,
"D:/dev/collections/data/test/LinkedMap.emptyCollection.version3.obj");
// resetFull();
// writeExternalFormToDisk((Serializable) map,
"D:/dev/collections/data/test/LinkedMap.fullCollection.version3.obj");
// }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
