This is the main class for evaluating expression Strings. An
@@ -89,14 +93,30 @@
// Member variables
//-------------------------------------
+ /**
+ * Name of configuration setting for maximum number of entries in the
+ * cached expression string map
+ */
+ private static final String EXPR_CACHE_PARAM
+ = "org.apache.taglibs.standard.lang.jstl.exprCacheSize";
+ /**
+ * Default maximum cache size
+ */
+ private static final int MAX_SIZE = 100;
+
/** The mapping from expression String to its parsed form (String,
- Expression, or ExpressionString) **/
- static Map sCachedExpressionStrings =
- Collections.synchronizedMap (new HashMap ());
+ * Expression, or ExpressionString)
+ *
+ * Using LRU Map with a maximum capacity to avoid out of bound map
+ * growth.
+ *
+ * NOTE: use LinkedHashmap if a dependency on J2SE 1.4+ is ok
+ */
+ static Map sCachedExpressionStrings = null;
/** The mapping from ExpectedType to Maps mapping literal String to
parsed value **/
- static Map sCachedExpectedTypes = new HashMap ();
+ static Map sCachedExpectedTypes = new HashMap();
/** The static Logger **/
static Logger sLogger = new Logger (System.out);
@@ -107,6 +127,10 @@
/** Flag if the cache should be bypassed **/
boolean mBypassCache;
+ /** The PageContext **/
+ PageContext pageContext;
+
+
//-------------------------------------
/**
*
@@ -123,20 +147,11 @@
//-------------------------------------
/**
+ * Enable cache bypass
*
- * Constructor
- *
- * @param pResolver the object that should be used to resolve
- * variable names encountered in expressions. If null, all variable
- * references will resolve to null.
- *
- * @param pBypassCache flag indicating if the cache should be
- * bypassed
+ * @param pBypassCache flag indicating cache should be bypassed
**/
- public ELEvaluator (VariableResolver pResolver,
- boolean pBypassCache)
- {
- mResolver = pResolver;
+ public void setBypassCache(boolean pBypassCache) {
mBypassCache = pBypassCache;
}
@@ -187,6 +202,9 @@
(Constants.NULL_EXPRESSION_STRING);
}
+ // Set the PageContext;
+ pageContext = (PageContext) pContext;
+
// Get the parsed version of the expression string
Object parsedValue = parseExpressionString (pExpressionString);
@@ -247,6 +265,10 @@
return "";
}
+ if (!(mBypassCache) && (sCachedExpressionStrings == null)) {
+ createExpressionStringMap();
+ }
+
// See if it's in the cache
Object ret =
mBypassCache ?
@@ -259,7 +281,9 @@
ELParser parser = new ELParser (r);
try {
ret = parser.ExpressionString ();
- sCachedExpressionStrings.put (pExpressionString, ret);
+ if (!mBypassCache) {
+ sCachedExpressionStrings.put (pExpressionString, ret);
+ }
}
catch (ParseException exc) {
throw new ELException
@@ -342,6 +366,30 @@
}
//-------------------------------------
+ /**
+ *
+ * Creates LRU map of expression strings. If context parameter
+ * specifying cache size is present use that as the maximum size
+ * of the LRU map otherwise use default.
+ **/
+ private synchronized void createExpressionStringMap () {
+ if (sCachedExpressionStrings != null) {
+ return;
+ }
+
+ String value = pageContext.getServletContext().
+ getInitParameter(EXPR_CACHE_PARAM);
+ if (value != null) {
+ sCachedExpressionStrings =
+ Collections.synchronizedMap(new LRUMap(Integer.parseInt(value)));
+ }
+ else {
+ sCachedExpressionStrings =
+ Collections.synchronizedMap(new LRUMap(MAX_SIZE));
+ }
+ }
+
+ //-------------------------------------
// Formatting ParseException
//-------------------------------------
/**
Index: lang/jstl/Evaluator.java
===================================================================
--- lang/jstl/Evaluator.java (revision 579752)
+++ lang/jstl/Evaluator.java (working copy)
@@ -68,7 +68,9 @@
String pAttributeValue)
{
try {
+ sEvaluator.setBypassCache(true);
sEvaluator.parseExpressionString (pAttributeValue);
+ sEvaluator.setBypassCache(false);
return null;
}
catch (ELException exc) {
Index: extra/collections/OrderedMap.java
===================================================================
--- extra/collections/OrderedMap.java (revision 0)
+++ extra/collections/OrderedMap.java (revision 0)
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2001-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+/**
+ * Defines a map that maintains order and allows both forward and backward
+ * iteration through that order.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface OrderedMap extends IterableMap {
+
+ /**
+ * Obtains an OrderedMapIterator over the map.
+ *
+ * A ordered map iterator is an efficient way of iterating over maps + * in both directions. + *
+ * BidiMap map = new TreeBidiMap();
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue("newValue");
+ * Object previousKey = it.previous();
+ * }
+ *
+ *
+ * @return a map iterator
+ */
+ OrderedMapIterator orderedMapIterator();
+
+ /**
+ * Gets the first key currently in this map.
+ *
+ * @return the first key currently in this map
+ * @throws java.util.NoSuchElementException if this map is empty
+ */
+ public Object firstKey();
+
+ /**
+ * Gets the last key currently in this map.
+ *
+ * @return the last key currently in this map
+ * @throws java.util.NoSuchElementException if this map is empty
+ */
+ public Object lastKey();
+
+ /**
+ * Gets the next key after the one specified.
+ *
+ * @param key the key to search for next from
+ * @return the next key, null if no match or at end
+ */
+ public Object nextKey(Object key);
+
+ /**
+ * Gets the previous key before the one specified.
+ *
+ * @param key the key to search for previous from
+ * @return the previous key, null if no match or at start
+ */
+ public Object previousKey(Object key);
+
+}
Index: extra/collections/ResettableIterator.java
===================================================================
--- extra/collections/ResettableIterator.java (revision 0)
+++ extra/collections/ResettableIterator.java (revision 0)
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+import java.util.Iterator;
+
+/**
+ * Defines an iterator that can be reset back to an initial state.
+ * + * This interface allows an iterator to be repeatedly reused. + * + * @since Commons Collections 3.0 + * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $ + * + * @author Stephen Colebourne + */ +public interface ResettableIterator extends Iterator { + + /** + * Resets the iterator back to the position at which the iterator + * was created. + */ + public void reset(); + +} Index: extra/collections/IterableMap.java =================================================================== --- extra/collections/IterableMap.java (revision 0) +++ extra/collections/IterableMap.java (revision 0) @@ -0,0 +1,61 @@ +/* + * Copyright 2003-2004 The Apache Software Foundation + * + * Licensed 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.taglibs.standard.extra.commons.collections; + +import java.util.Map; + +/** + * Defines a map that can be iterated directly without needing to create an entry set. + *
+ * A map iterator is an efficient way of iterating over maps. + * There is no need to access the entry set or cast to Map Entry objects. + *
+ * IterableMap map = new HashedMap();
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue("newValue");
+ * }
+ *
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface IterableMap extends Map {
+
+ /**
+ * Obtains a MapIterator over the map.
+ * + * A map iterator is an efficient way of iterating over maps. + * There is no need to access the entry set or cast to Map Entry objects. + *
+ * IterableMap map = new HashedMap();
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue("newValue");
+ * }
+ *
+ *
+ * @return a map iterator
+ */
+ MapIterator mapIterator();
+
+}
Index: extra/collections/KeyValue.java
===================================================================
--- extra/collections/KeyValue.java (revision 0)
+++ extra/collections/KeyValue.java (revision 0)
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+/**
+ * Defines a simple key value pair.
+ *
+ * A Map Entry has considerable additional semantics over and above a simple
+ * key-value pair. This interface defines the minimum key value, with just the
+ * two get methods.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface KeyValue {
+
+ /**
+ * Gets the key from the pair.
+ *
+ * @return the key
+ */
+ Object getKey();
+
+ /**
+ * Gets the value from the pair.
+ *
+ * @return the value
+ */
+ Object getValue();
+
+}
Index: extra/collections/MapIterator.java
===================================================================
--- extra/collections/MapIterator.java (revision 0)
+++ extra/collections/MapIterator.java (revision 0)
@@ -0,0 +1,108 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+import java.util.Iterator;
+
+/**
+ * Defines an iterator that operates over a Map.
+ *
+ * This iterator is a special version designed for maps. It can be more + * efficient to use this rather than an entry set iterator where the option + * is available, and it is certainly more convenient. + *
+ * A map that provides this interface may not hold the data internally using + * Map Entry objects, thus this interface can avoid lots of object creation. + *
+ * In use, this iterator iterates through the keys in the map. After each call
+ * to next(), the getValue() method provides direct
+ * access to the value. The value can also be set using setValue().
+ *
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue(newValue);
+ * }
+ *
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface MapIterator extends Iterator {
+
+ /**
+ * Checks to see if there are more entries still to be iterated.
+ *
+ * @return true if the iterator has more elements
+ */
+ boolean hasNext();
+
+ /**
+ * Gets the next key from the Map.
+ *
+ * @return the next key in the iteration
+ * @throws java.util.NoSuchElementException if the iteration is finished
+ */
+ Object next();
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the current key, which is the key returned by the last call
+ * to next().
+ *
+ * @return the current key
+ * @throws IllegalStateException if next() has not yet been called
+ */
+ Object getKey();
+
+ /**
+ * Gets the current value, which is the value associated with the last key
+ * returned by next().
+ *
+ * @return the current value
+ * @throws IllegalStateException if next() has not yet been called
+ */
+ Object getValue();
+
+ //-----------------------------------------------------------------------
+ /**
+ * Removes the last returned key from the underlying Map (optional operation).
+ *
+ * This method can be called once per call to next().
+ *
+ * @throws UnsupportedOperationException if remove is not supported by the map
+ * @throws IllegalStateException if next() has not yet been called
+ * @throws IllegalStateException if remove() has already been called
+ * since the last call to next()
+ */
+ void remove();
+
+ /**
+ * Sets the value associated with the current key (optional operation).
+ *
+ * @param value the new value
+ * @return the previous value
+ * @throws UnsupportedOperationException if setValue is not supported by the map
+ * @throws IllegalStateException if next() has not yet been called
+ * @throws IllegalStateException if remove() has been called since the
+ * last call to next()
+ */
+ Object setValue(Object value);
+
+}
Index: extra/collections/README.txt
===================================================================
--- extra/collections/README.txt (revision 0)
+++ extra/collections/README.txt (revision 0)
@@ -0,0 +1,10 @@
+Jakarta Commons Collections classes
+Version: 3.2
+
+These classes are necessary for LRUMap implementation used in ELEvaluator to cache expression strings.
+
+These classes can be deleted for any of the following reasons:
+ - a custom caching mechanism is implemented
+ - jakarta-commons collections jar file is made a required dependency
+ - J2SE 1.4.x or higher is required
+ - can leverage LRU LinkedHashmap implementation
Index: extra/collections/iterators/EmptyMapIterator.java
===================================================================
--- extra/collections/iterators/EmptyMapIterator.java (revision 0)
+++ extra/collections/iterators/EmptyMapIterator.java (revision 0)
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.iterators;
+
+import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+
+/**
+ * Provides an implementation of an empty map iterator.
+ *
+ * @since Commons Collections 3.1
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public class EmptyMapIterator extends AbstractEmptyIterator implements MapIterator, ResettableIterator {
+
+ /**
+ * Singleton instance of the iterator.
+ * @since Commons Collections 3.1
+ */
+ public static final MapIterator INSTANCE = new EmptyMapIterator();
+
+ /**
+ * Constructor.
+ */
+ protected EmptyMapIterator() {
+ super();
+ }
+
+}
Index: extra/collections/iterators/EmptyIterator.java
===================================================================
--- extra/collections/iterators/EmptyIterator.java (revision 0)
+++ extra/collections/iterators/EmptyIterator.java (revision 0)
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.iterators;
+
+import java.util.Iterator;
+
+import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+
+/**
+ * Provides an implementation of an empty iterator.
+ *
+ * This class provides an implementation of an empty iterator.
+ * This class provides for binary compatability between Commons Collections
+ * 2.1.1 and 3.1 due to issues with IteratorUtils.
+ *
+ * @since Commons Collections 2.1.1 and 3.1
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public class EmptyIterator extends AbstractEmptyIterator implements ResettableIterator {
+
+ /**
+ * Singleton instance of the iterator.
+ * @since Commons Collections 3.1
+ */
+ public static final ResettableIterator RESETTABLE_INSTANCE = new EmptyIterator();
+ /**
+ * Singleton instance of the iterator.
+ * @since Commons Collections 2.1.1 and 3.1
+ */
+ public static final Iterator INSTANCE = RESETTABLE_INSTANCE;
+
+ /**
+ * Constructor.
+ */
+ protected EmptyIterator() {
+ super();
+ }
+
+}
Index: extra/collections/iterators/EmptyOrderedMapIterator.java
===================================================================
--- extra/collections/iterators/EmptyOrderedMapIterator.java (revision 0)
+++ extra/collections/iterators/EmptyOrderedMapIterator.java (revision 0)
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.iterators;
+
+import org.apache.taglibs.standard.extra.commons.collections.OrderedMapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+
+/**
+ * Provides an implementation of an empty ordered map iterator.
+ *
+ * @since Commons Collections 3.1
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public class EmptyOrderedMapIterator extends AbstractEmptyIterator implements OrderedMapIterator, ResettableIterator {
+
+ /**
+ * Singleton instance of the iterator.
+ * @since Commons Collections 3.1
+ */
+ public static final OrderedMapIterator INSTANCE = new EmptyOrderedMapIterator();
+
+ /**
+ * Constructor.
+ */
+ protected EmptyOrderedMapIterator() {
+ super();
+ }
+
+}
Index: extra/collections/iterators/AbstractEmptyIterator.java
===================================================================
--- extra/collections/iterators/AbstractEmptyIterator.java (revision 0)
+++ extra/collections/iterators/AbstractEmptyIterator.java (revision 0)
@@ -0,0 +1,89 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.iterators;
+
+import java.util.NoSuchElementException;
+
+/**
+ * Provides an implementation of an empty iterator.
+ *
+ * @since Commons Collections 3.1
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+abstract class AbstractEmptyIterator {
+
+ /**
+ * Constructor.
+ */
+ protected AbstractEmptyIterator() {
+ super();
+ }
+
+ public boolean hasNext() {
+ return false;
+ }
+
+ public Object next() {
+ throw new NoSuchElementException("Iterator contains no elements");
+ }
+
+ public boolean hasPrevious() {
+ return false;
+ }
+
+ public Object previous() {
+ throw new NoSuchElementException("Iterator contains no elements");
+ }
+
+ public int nextIndex() {
+ return 0;
+ }
+
+ public int previousIndex() {
+ return -1;
+ }
+
+ public void add(Object obj) {
+ throw new UnsupportedOperationException("add() not supported for empty Iterator");
+ }
+
+ public void set(Object obj) {
+ throw new IllegalStateException("Iterator contains no elements");
+ }
+
+ public void remove() {
+ throw new IllegalStateException("Iterator contains no elements");
+ }
+
+ public Object getKey() {
+ throw new IllegalStateException("Iterator contains no elements");
+ }
+
+ public Object getValue() {
+ throw new IllegalStateException("Iterator contains no elements");
+ }
+
+ public Object setValue(Object value) {
+ throw new IllegalStateException("Iterator contains no elements");
+ }
+
+ public void reset() {
+ // do nothing
+ }
+
+}
Index: extra/collections/iterators/EmptyOrderedIterator.java
===================================================================
--- extra/collections/iterators/EmptyOrderedIterator.java (revision 0)
+++ extra/collections/iterators/EmptyOrderedIterator.java (revision 0)
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.iterators;
+
+import org.apache.taglibs.standard.extra.commons.collections.OrderedIterator;
+import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+
+/**
+ * Provides an implementation of an empty ordered iterator.
+ *
+ * @since Commons Collections 3.1
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public class EmptyOrderedIterator extends AbstractEmptyIterator implements OrderedIterator, ResettableIterator {
+
+ /**
+ * Singleton instance of the iterator.
+ * @since Commons Collections 3.1
+ */
+ public static final OrderedIterator INSTANCE = new EmptyOrderedIterator();
+
+ /**
+ * Constructor.
+ */
+ protected EmptyOrderedIterator() {
+ super();
+ }
+
+}
Index: extra/collections/OrderedMapIterator.java
===================================================================
--- extra/collections/OrderedMapIterator.java (revision 0)
+++ extra/collections/OrderedMapIterator.java (revision 0)
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2001-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+/**
+ * Defines an iterator that operates over an ordered Map.
+ *
+ * This iterator allows both forward and reverse iteration through the map.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface OrderedMapIterator extends MapIterator, OrderedIterator {
+
+ /**
+ * Checks to see if there is a previous entry that can be iterated to.
+ *
+ * @return true if the iterator has a previous element
+ */
+ boolean hasPrevious();
+
+ /**
+ * Gets the previous key from the Map.
+ *
+ * @return the previous key in the iteration
+ * @throws java.util.NoSuchElementException if the iteration is finished
+ */
+ Object previous();
+
+}
Index: extra/collections/map/LRUMap.java
===================================================================
--- extra/collections/map/LRUMap.java (revision 0)
+++ extra/collections/map/LRUMap.java (revision 0)
@@ -0,0 +1,391 @@
+/*
+ * Copyright 2001-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.map;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.Map;
+
+import org.apache.taglibs.standard.extra.commons.collections.BoundedMap;
+
+/**
+ * A Map implementation with a fixed maximum size which removes
+ * the least recently used entry if an entry is added when full.
+ *
+ * The least recently used algorithm works on the get and put operations only. + * Iteration of any kind, including setting the value by iteration, does not + * change the order. Queries such as containsKey and containsValue or access + * via views also do not change the order. + *
+ * The map implements OrderedMap and entries may be queried using
+ * the bidirectional OrderedMapIterator. The order returned is
+ * least recently used to most recently used. Iterators from map views can
+ * also be cast to OrderedIterator if required.
+ *
+ * All the available iterators can be reset back to the start by casting to
+ * ResettableIterator and calling reset().
+ *
+ * @since Commons Collections 3.0 (previously in main package v1.0)
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author James Strachan
+ * @author Morgan Delagrange
+ * @author Stephen Colebourne
+ * @author Mike Pettypiece
+ * @author Mario Ivankovits
+ */
+public class LRUMap
+ extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
+
+ /** Serialisation version */
+ static final long serialVersionUID = -612114643488955218L;
+ /** Default maximum size */
+ protected static final int DEFAULT_MAX_SIZE = 100;
+
+ /** Maximum size */
+ private transient int maxSize;
+ /** Scan behaviour */
+ private boolean scanUntilRemovable;
+
+ /**
+ * Constructs a new empty map with a maximum size of 100.
+ */
+ public LRUMap() {
+ this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified maximum size.
+ *
+ * @param maxSize the maximum size of the map
+ * @throws IllegalArgumentException if the maximum size is less than one
+ */
+ public LRUMap(int maxSize) {
+ this(maxSize, DEFAULT_LOAD_FACTOR);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified maximum size.
+ *
+ * @param maxSize the maximum size of the map
+ * @param scanUntilRemovable scan until a removeable entry is found, default false
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @since Commons Collections 3.1
+ */
+ public LRUMap(int maxSize, boolean scanUntilRemovable) {
+ this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity and
+ * load factor.
+ *
+ * @param maxSize the maximum size of the map, -1 for no limit,
+ * @param loadFactor the load factor
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
+ */
+ public LRUMap(int maxSize, float loadFactor) {
+ this(maxSize, loadFactor, false);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified initial capacity and
+ * load factor.
+ *
+ * @param maxSize the maximum size of the map, -1 for no limit,
+ * @param loadFactor the load factor
+ * @param scanUntilRemovable scan until a removeable entry is found, default false
+ * @throws IllegalArgumentException if the maximum size is less than one
+ * @throws IllegalArgumentException if the load factor is less than zero
+ * @since Commons Collections 3.1
+ */
+ public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) {
+ super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
+ if (maxSize < 1) {
+ throw new IllegalArgumentException("LRUMap max size must be greater than 0");
+ }
+ this.maxSize = maxSize;
+ this.scanUntilRemovable = scanUntilRemovable;
+ }
+
+ /**
+ * Constructor copying elements from another map.
+ *
+ * The maximum size is set from the map's size. + * + * @param map the map to copy + * @throws NullPointerException if the map is null + * @throws IllegalArgumentException if the map is empty + */ + public LRUMap(Map map) { + this(map, false); + } + + /** + * Constructor copying elements from another map. + *
+ * The maximum size is set from the map's size. + * + * @param map the map to copy + * @param scanUntilRemovable scan until a removeable entry is found, default false + * @throws NullPointerException if the map is null + * @throws IllegalArgumentException if the map is empty + * @since Commons Collections 3.1 + */ + public LRUMap(Map map, boolean scanUntilRemovable) { + this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable); + putAll(map); + } + + //----------------------------------------------------------------------- + /** + * Gets the value mapped to the key specified. + *+ * This operation changes the position of the key in the map to the + * most recently used position (first). + * + * @param key the key + * @return the mapped value, null if no match + */ + public Object get(Object key) { + LinkEntry entry = (LinkEntry) getEntry(key); + if (entry == null) { + return null; + } + moveToMRU(entry); + return entry.getValue(); + } + + //----------------------------------------------------------------------- + /** + * Moves an entry to the MRU position at the end of the list. + *
+ * This implementation moves the updated entry to the end of the list. + * + * @param entry the entry to update + */ + protected void moveToMRU(LinkEntry entry) { + if (entry.after != header) { + modCount++; + // remove + entry.before.after = entry.after; + entry.after.before = entry.before; + // add first + entry.after = header; + entry.before = header.before; + header.before.after = entry; + header.before = entry; + } + } + + /** + * Updates an existing key-value mapping. + *
+ * This implementation moves the updated entry to the top of the list + * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}. + * + * @param entry the entry to update + * @param newValue the new value to store + */ + protected void updateEntry(HashEntry entry, Object newValue) { + moveToMRU((LinkEntry) entry); // handles modCount + entry.setValue(newValue); + } + + /** + * Adds a new key-value mapping into this map. + *
+ * This implementation checks the LRU size and determines whether to + * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}. + *
+ * From Commons Collections 3.1 this method uses {@link #isFull()} rather
+ * than accessing size and maxSize directly.
+ * It also handles the scanUntilRemovable functionality.
+ *
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ */
+ protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
+ if (isFull()) {
+ LinkEntry reuse = header.after;
+ boolean removeLRUEntry = false;
+ if (scanUntilRemovable) {
+ while (reuse != header) {
+ if (removeLRU(reuse)) {
+ removeLRUEntry = true;
+ break;
+ }
+ reuse = reuse.after;
+ }
+ } else {
+ removeLRUEntry = removeLRU(reuse);
+ }
+
+ if (removeLRUEntry) {
+ reuseMapping(reuse, hashIndex, hashCode, key, value);
+ } else {
+ super.addMapping(hashIndex, hashCode, key, value);
+ }
+ } else {
+ super.addMapping(hashIndex, hashCode, key, value);
+ }
+ }
+
+ /**
+ * Reuses an entry by removing it and moving it to a new place in the map.
+ *
+ * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}. + * + * @param entry the entry to reuse + * @param hashIndex the index into the data array to store at + * @param hashCode the hash code of the key to add + * @param key the key to add + * @param value the value to add + */ + protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) { + // find the entry before the entry specified in the hash table + // remember that the parameters (except the first) refer to the new entry, + // not the old one + int removeIndex = hashIndex(entry.hashCode, data.length); + HashEntry loop = data[removeIndex]; + HashEntry previous = null; + while (loop != entry) { + previous = loop; + loop = loop.next; + } + + // reuse the entry + modCount++; + removeEntry(entry, removeIndex, previous); + reuseEntry(entry, hashIndex, hashCode, key, value); + addEntry(entry, hashIndex); + } + + /** + * Subclass method to control removal of the least recently used entry from the map. + *
+ * This method exists for subclasses to override. A subclass may wish to + * provide cleanup of resources when an entry is removed. For example: + *
+ * protected boolean removeLRU(LinkEntry entry) {
+ * releaseResources(entry.getValue()); // release resources held by entry
+ * return true; // actually delete entry
+ * }
+ *
+ * + * Alternatively, a subclass may choose to not remove the entry or selectively + * keep certain LRU entries. For example: + *
+ * protected boolean removeLRU(LinkEntry entry) {
+ * if (entry.getKey().toString().startsWith("System.")) {
+ * return false; // entry not removed from LRUMap
+ * } else {
+ * return true; // actually delete entry
+ * }
+ * }
+ *
+ * The effect of returning false is dependent on the scanUntilRemovable flag.
+ * If the flag is true, the next LRU entry will be passed to this method and so on
+ * until one returns false and is removed, or every entry in the map has been passed.
+ * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
+ *
+ * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
+ * This is fixed in version 3.1 onwards.
+ *
+ * @param entry the entry to be removed
+ */
+ protected boolean removeLRU(LinkEntry entry) {
+ return true;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns true if this map is full and no new mappings can be added.
+ *
+ * @return true if the map is full
+ */
+ public boolean isFull() {
+ return (size >= maxSize);
+ }
+
+ /**
+ * Gets the maximum size of the map (the bound).
+ *
+ * @return the maximum number of elements the map can hold
+ */
+ public int maxSize() {
+ return maxSize;
+ }
+
+ /**
+ * Whether this LRUMap will scan until a removable entry is found when the
+ * map is full.
+ *
+ * @return true if this map scans
+ * @since Commons Collections 3.1
+ */
+ public boolean isScanUntilRemovable() {
+ return scanUntilRemovable;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Clones the map without cloning the keys or values.
+ *
+ * @return a shallow clone
+ */
+ public Object clone() {
+ return super.clone();
+ }
+
+ /**
+ * Write the map out using a custom routine.
+ */
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ out.defaultWriteObject();
+ doWriteObject(out);
+ }
+
+ /**
+ * Read the map in using a custom routine.
+ */
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ in.defaultReadObject();
+ doReadObject(in);
+ }
+
+ /**
+ * Writes the data necessary for put() to work in deserialization.
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeInt(maxSize);
+ super.doWriteObject(out);
+ }
+
+ /**
+ * Reads the data necessary for put() to work in the superclass.
+ */
+ protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ maxSize = in.readInt();
+ super.doReadObject(in);
+ }
+
+}
Index: extra/collections/map/AbstractLinkedMap.java
===================================================================
--- extra/collections/map/AbstractLinkedMap.java (revision 0)
+++ extra/collections/map/AbstractLinkedMap.java (revision 0)
@@ -0,0 +1,608 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.map;
+
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.OrderedIterator;
+import org.apache.taglibs.standard.extra.commons.collections.OrderedMap;
+import org.apache.taglibs.standard.extra.commons.collections.OrderedMapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
+import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedIterator;
+import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedMapIterator;
+
+/**
+ * An abstract implementation of a hash-based map that links entries to create an
+ * ordered map and which provides numerous points for subclasses to override.
+ *
+ * This class implements all the features necessary for a subclass linked
+ * hash-based map. Key-value entries are stored in instances of the
+ * LinkEntry class which can be overridden and replaced.
+ * The iterators can similarly be replaced, without the need to replace the KeySet,
+ * EntrySet and Values view classes.
+ *
+ * Overridable methods are provided to change the default hashing behaviour, and + * to change how entries are added to and removed from the map. Hopefully, all you + * need for unusual subclasses is here. + *
+ * This implementation maintains order by original insertion, but subclasses
+ * may work differently. The OrderedMap interface is implemented
+ * to provide access to bidirectional iteration and extra convenience methods.
+ *
+ * The orderedMapIterator() method provides direct access to a
+ * bidirectional iterator. The iterators from the other views can also be cast
+ * to OrderedIterator if required.
+ *
+ * All the available iterators can be reset back to the start by casting to
+ * ResettableIterator and calling reset().
+ *
+ * The implementation is also designed to be subclassed, with lots of useful + * methods exposed. + * + * @since Commons Collections 3.0 + * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $ + * + * @author java util LinkedHashMap + * @author Stephen Colebourne + */ +public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap { + + /** Header in the linked list */ + protected transient LinkEntry header; + + /** + * Constructor only used in deserialization, do not use otherwise. + */ + protected AbstractLinkedMap() { + super(); + } + + /** + * Constructor which performs no validation on the passed in parameters. + * + * @param initialCapacity the initial capacity, must be a power of two + * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f + * @param threshold the threshold, must be sensible + */ + protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold) { + super(initialCapacity, loadFactor, threshold); + } + + /** + * 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 + */ + protected AbstractLinkedMap(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 zero + */ + protected AbstractLinkedMap(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 + */ + protected AbstractLinkedMap(Map map) { + super(map); + } + + /** + * Initialise this subclass during construction. + */ + protected void init() { + header = new LinkEntry(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 (LinkEntry entry = header.after; entry != header; entry = entry.after) { + if (entry.getValue() == null) { + return true; + } + } + } else { + for (LinkEntry 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) { + LinkEntry entry = (LinkEntry) 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) { + LinkEntry entry = (LinkEntry) getEntry(key); + return (entry == null || entry.before == header ? null : entry.before.getKey()); + } + + //----------------------------------------------------------------------- + /** + * Gets the key at the specified index. + * + * @param index the index to retrieve + * @return the key at the specified index + * @throws IndexOutOfBoundsException if the index is invalid + */ + protected LinkEntry getEntry(int index) { + if (index < 0) { + throw new IndexOutOfBoundsException("Index " + index + " is less than zero"); + } + if (index >= size) { + throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size); + } + LinkEntry entry; + if (index < (size / 2)) { + // Search forwards + entry = header.after; + for (int currentIndex = 0; currentIndex < index; currentIndex++) { + entry = entry.after; + } + } else { + // Search backwards + entry = header; + for (int currentIndex = size; currentIndex > index; currentIndex--) { + entry = entry.before; + } + } + return entry; + } + + /** + * Adds an entry into this map, maintaining insertion order. + *
+ * This implementation adds the entry to the data storage table and + * to the end of the linked list. + * + * @param entry the entry to add + * @param hashIndex the index into the data array to store at + */ + protected void addEntry(HashEntry entry, int hashIndex) { + LinkEntry link = (LinkEntry) entry; + link.after = header; + link.before = header.before; + header.before.after = link; + header.before = link; + data[hashIndex] = entry; + } + + /** + * Creates an entry to store the data. + *
+ * This implementation creates a new LinkEntry instance. + * + * @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) { + return new LinkEntry(next, hashCode, key, value); + } + + /** + * Removes an entry from the map and the linked list. + *
+ * This implementation removes the entry from the linked list chain, then
+ * calls the superclass implementation.
+ *
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
+ */
+ protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
+ LinkEntry link = (LinkEntry) entry;
+ link.before.after = link.after;
+ link.after.before = link.before;
+ link.after = null;
+ link.before = null;
+ super.removeEntry(entry, hashIndex, previous);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the before field from a LinkEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the before field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected LinkEntry entryBefore(LinkEntry entry) {
+ return entry.before;
+ }
+
+ /**
+ * Gets the after field from a LinkEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the after field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected LinkEntry entryAfter(LinkEntry entry) {
+ return entry.after;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets an iterator over the map.
+ * Changes made to the iterator affect this map.
+ *
+ * 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. + * + * @return the map iterator + */ + public MapIterator mapIterator() { + if (size == 0) { + return EmptyOrderedMapIterator.INSTANCE; + } + return new LinkMapIterator(this); + } + + /** + * Gets a bidirectional iterator over the map. + * Changes made to the iterator affect this map. + *
+ * 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. + * + * @return the map iterator + */ + public OrderedMapIterator orderedMapIterator() { + if (size == 0) { + return EmptyOrderedMapIterator.INSTANCE; + } + return new LinkMapIterator(this); + } + + /** + * MapIterator implementation. + */ + protected static class LinkMapIterator extends LinkIterator implements OrderedMapIterator { + + protected LinkMapIterator(AbstractLinkedMap parent) { + super(parent); + } + + 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(AbstractHashedMap.GETKEY_INVALID); + } + return current.getKey(); + } + + public Object getValue() { + HashEntry current = currentEntry(); + if (current == null) { + throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); + } + return current.getValue(); + } + + public Object setValue(Object value) { + HashEntry current = currentEntry(); + if (current == null) { + throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); + } + 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 EmptyOrderedIterator.INSTANCE; + } + return new EntrySetIterator(this); + } + + /** + * EntrySet iterator. + */ + protected static class EntrySetIterator extends LinkIterator { + + protected EntrySetIterator(AbstractLinkedMap parent) { + super(parent); + } + + 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 EmptyOrderedIterator.INSTANCE; + } + return new KeySetIterator(this); + } + + /** + * KeySet iterator. + */ + protected static class KeySetIterator extends EntrySetIterator { + + protected KeySetIterator(AbstractLinkedMap parent) { + super(parent); + } + + 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 EmptyOrderedIterator.INSTANCE; + } + return new ValuesIterator(this); + } + + /** + * Values iterator. + */ + protected static class ValuesIterator extends LinkIterator { + + protected ValuesIterator(AbstractLinkedMap parent) { + super(parent); + } + + public Object next() { + return super.nextEntry().getValue(); + } + + public Object previous() { + return super.previousEntry().getValue(); + } + } + + //----------------------------------------------------------------------- + /** + * LinkEntry that stores the data. + *
+ * If you subclass AbstractLinkedMap but not LinkEntry
+ * then you will not be able to access the protected fields.
+ * The entryXxx() methods on AbstractLinkedMap exist
+ * to provide the necessary access.
+ */
+ protected static class LinkEntry extends HashEntry {
+ /** The entry before this one in the order */
+ protected LinkEntry before;
+ /** The entry after this one in the order */
+ protected LinkEntry after;
+
+ /**
+ * Constructs a new entry.
+ *
+ * @param next the next entry in the hash bucket sequence
+ * @param hashCode the hash code
+ * @param key the key
+ * @param value the value
+ */
+ protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
+ super(next, hashCode, key, value);
+ }
+ }
+
+ /**
+ * Base Iterator that iterates in link order.
+ */
+ protected static abstract class LinkIterator
+ implements OrderedIterator, ResettableIterator {
+
+ /** The parent map */
+ protected final AbstractLinkedMap parent;
+ /** The current (last returned) entry */
+ protected LinkEntry last;
+ /** The next entry */
+ protected LinkEntry next;
+ /** The modification count expected */
+ protected int expectedModCount;
+
+ protected LinkIterator(AbstractLinkedMap parent) {
+ super();
+ this.parent = parent;
+ this.next = parent.header.after;
+ this.expectedModCount = parent.modCount;
+ }
+
+ public boolean hasNext() {
+ return (next != parent.header);
+ }
+
+ public boolean hasPrevious() {
+ return (next.before != parent.header);
+ }
+
+ protected LinkEntry nextEntry() {
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ if (next == parent.header) {
+ throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
+ }
+ last = next;
+ next = next.after;
+ return last;
+ }
+
+ protected LinkEntry previousEntry() {
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ LinkEntry previous = next.before;
+ if (previous == parent.header) {
+ throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
+ }
+ next = previous;
+ last = previous;
+ return last;
+ }
+
+ protected LinkEntry currentEntry() {
+ return last;
+ }
+
+ public void remove() {
+ if (last == null) {
+ throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
+ }
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ parent.remove(last.getKey());
+ last = null;
+ expectedModCount = parent.modCount;
+ }
+
+ public void reset() {
+ last = null;
+ next = parent.header.after;
+ }
+
+ public String toString() {
+ if (last != null) {
+ return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
+ } else {
+ return "Iterator[]";
+ }
+ }
+ }
+
+}
Index: extra/collections/map/AbstractHashedMap.java
===================================================================
--- extra/collections/map/AbstractHashedMap.java (revision 0)
+++ extra/collections/map/AbstractHashedMap.java (revision 0)
@@ -0,0 +1,1327 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections.map;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+import org.apache.taglibs.standard.extra.commons.collections.IterableMap;
+import org.apache.taglibs.standard.extra.commons.collections.KeyValue;
+import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
+import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyIterator;
+import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyMapIterator;
+
+/**
+ * An abstract implementation of a hash-based map which provides numerous points for
+ * subclasses to override.
+ *
+ * This class implements all the features necessary for a subclass hash-based map.
+ * Key-value entries are stored in instances of the HashEntry class,
+ * which can be overridden and replaced. The iterators can similarly be replaced,
+ * without the need to replace the KeySet, EntrySet and Values view classes.
+ *
+ * Overridable methods are provided to change the default hashing behaviour, and + * to change how entries are added to and removed from the map. Hopefully, all you + * need for unusual subclasses is here. + *
+ * NOTE: From Commons Collections 3.1 this class extends AbstractMap. + * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1. + * This extends clause will be removed in v4.0. + * + * @since Commons Collections 3.0 + * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $ + * + * @author java util HashMap + * @author Stephen Colebourne + */ +public class AbstractHashedMap extends AbstractMap implements IterableMap { + + protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration"; + protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration"; + protected static final String REMOVE_INVALID = "remove() can only be called once after next()"; + protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()"; + protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()"; + protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()"; + + /** The default capacity to use */ + protected static final int DEFAULT_CAPACITY = 16; + /** The default threshold to use */ + protected static final int DEFAULT_THRESHOLD = 12; + /** The default load factor to use */ + protected static final float DEFAULT_LOAD_FACTOR = 0.75f; + /** The maximum capacity allowed */ + protected static final int MAXIMUM_CAPACITY = 1 << 30; + /** An object for masking null */ + protected static final Object NULL = new Object(); + + /** Load factor, normally 0.75 */ + protected transient float loadFactor; + /** The size of the map */ + protected transient int size; + /** Map entries */ + protected transient HashEntry[] data; + /** Size at which to rehash */ + protected transient int threshold; + /** Modification count for iterators */ + protected transient int modCount; + /** Entry set */ + protected transient EntrySet entrySet; + /** Key set */ + protected transient KeySet keySet; + /** Values */ + protected transient Values values; + + /** + * Constructor only used in deserialization, do not use otherwise. + */ + protected AbstractHashedMap() { + super(); + } + + /** + * Constructor which performs no validation on the passed in parameters. + * + * @param initialCapacity the initial capacity, must be a power of two + * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f + * @param threshold the threshold, must be sensible + */ + protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) { + super(); + this.loadFactor = loadFactor; + this.data = new HashEntry[initialCapacity]; + this.threshold = threshold; + init(); + } + + /** + * Constructs a new, empty map with the specified initial capacity and + * default load factor. + * + * @param initialCapacity the initial capacity + * @throws IllegalArgumentException if the initial capacity is less than one + */ + protected AbstractHashedMap(int initialCapacity) { + this(initialCapacity, DEFAULT_LOAD_FACTOR); + } + + /** + * 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 or equal to zero + */ + protected AbstractHashedMap(int initialCapacity, float loadFactor) { + super(); + if (initialCapacity < 1) { + throw new IllegalArgumentException("Initial capacity must be greater than 0"); + } + if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) { + throw new IllegalArgumentException("Load factor must be greater than 0"); + } + this.loadFactor = loadFactor; + this.threshold = calculateThreshold(initialCapacity, loadFactor); + initialCapacity = calculateNewCapacity(initialCapacity); + this.data = new HashEntry[initialCapacity]; + init(); + } + + /** + * Constructor copying elements from another map. + * + * @param map the map to copy + * @throws NullPointerException if the map is null + */ + protected AbstractHashedMap(Map map) { + this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); + putAll(map); + } + + /** + * Initialise subclasses during construction, cloning or deserialization. + */ + protected void init() { + } + + //----------------------------------------------------------------------- + /** + * Gets the value mapped to the key specified. + * + * @param key the key + * @return the mapped value, null if no match + */ + public Object get(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.getValue(); + } + entry = entry.next; + } + return null; + } + + /** + * Gets the size of the map. + * + * @return the size + */ + public int size() { + return size; + } + + /** + * Checks whether the map is currently empty. + * + * @return true if the map is currently size zero + */ + public boolean isEmpty() { + return (size == 0); + } + + //----------------------------------------------------------------------- + /** + * Checks whether the map contains the specified key. + * + * @param key the key to search for + * @return true if the map contains the key + */ + public boolean containsKey(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 true; + } + entry = entry.next; + } + return false; + } + + /** + * 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) { + if (value == null) { + for (int i = 0, isize = data.length; i < isize; i++) { + HashEntry entry = data[i]; + while (entry != null) { + if (entry.getValue() == null) { + return true; + } + entry = entry.next; + } + } + } else { + for (int i = 0, isize = data.length; i < isize; i++) { + HashEntry entry = data[i]; + while (entry != null) { + if (isEqualValue(value, entry.getValue())) { + return true; + } + entry = entry.next; + } + } + } + return false; + } + + //----------------------------------------------------------------------- + /** + * Puts a key-value mapping into this map. + * + * @param key the key to add + * @param value the value to add + * @return the value previously mapped to this key, null if none + */ + public Object put(Object key, Object value) { + key = convertKey(key); + int hashCode = hash(key); + int index = hashIndex(hashCode, data.length); + HashEntry entry = data[index]; + while (entry != null) { + if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) { + Object oldValue = entry.getValue(); + updateEntry(entry, value); + return oldValue; + } + entry = entry.next; + } + + addMapping(index, hashCode, key, value); + return null; + } + + /** + * Puts all the values from the specified map into this map. + *
+ * This implementation iterates around the specified map and + * uses {@link #put(Object, Object)}. + * + * @param map the map to add + * @throws NullPointerException if the map is null + */ + public void putAll(Map map) { + int mapSize = map.size(); + if (mapSize == 0) { + return; + } + int newSize = (int) ((size + mapSize) / loadFactor + 1); + ensureCapacity(calculateNewCapacity(newSize)); + for (Iterator it = map.entrySet().iterator(); it.hasNext();) { + Map.Entry entry = (Map.Entry) it.next(); + put(entry.getKey(), entry.getValue()); + } + } + + /** + * Removes the specified mapping from this map. + * + * @param key the mapping to remove + * @return the value mapped to the removed key, null if key not in map + */ + public Object remove(Object key) { + key = convertKey(key); + int hashCode = hash(key); + int index = hashIndex(hashCode, data.length); + HashEntry entry = data[index]; + HashEntry previous = null; + while (entry != null) { + if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) { + Object oldValue = entry.getValue(); + removeMapping(entry, index, previous); + return oldValue; + } + previous = entry; + entry = entry.next; + } + return null; + } + + /** + * Clears the map, resetting the size to zero and nullifying references + * to avoid garbage collection issues. + */ + public void clear() { + modCount++; + HashEntry[] data = this.data; + for (int i = data.length - 1; i >= 0; i--) { + data[i] = null; + } + size = 0; + } + + //----------------------------------------------------------------------- + /** + * Converts input keys to another object for storage in the map. + * This implementation masks nulls. + * Subclasses can override this to perform alternate key conversions. + *
+ * The reverse conversion can be changed, if required, by overriding the
+ * getKey() method in the hash entry.
+ *
+ * @param key the key convert
+ * @return the converted key
+ */
+ protected Object convertKey(Object key) {
+ return (key == null ? NULL : key);
+ }
+
+ /**
+ * Gets the hash code for the key specified.
+ * This implementation uses the additional hashing routine from JDK1.4.
+ * Subclasses can override this to return alternate hash codes.
+ *
+ * @param key the key to get a hash code for
+ * @return the hash code
+ */
+ protected int hash(Object key) {
+ // same as JDK 1.4
+ int h = key.hashCode();
+ h += ~(h << 9);
+ h ^= (h >>> 14);
+ h += (h << 4);
+ h ^= (h >>> 10);
+ return h;
+ }
+
+ /**
+ * Compares two keys, in internal converted form, to see if they are equal.
+ * This implementation uses the equals method and assumes neither key is null.
+ * Subclasses can override this to match differently.
+ *
+ * @param key1 the first key to compare passed in from outside
+ * @param key2 the second key extracted from the entry via entry.key
+ * @return true if equal
+ */
+ protected boolean isEqualKey(Object key1, Object key2) {
+ return (key1 == key2 || key1.equals(key2));
+ }
+
+ /**
+ * Compares two values, in external form, to see if they are equal.
+ * This implementation uses the equals method and assumes neither value is null.
+ * Subclasses can override this to match differently.
+ *
+ * @param value1 the first value to compare passed in from outside
+ * @param value2 the second value extracted from the entry via getValue()
+ * @return true if equal
+ */
+ protected boolean isEqualValue(Object value1, Object value2) {
+ return (value1 == value2 || value1.equals(value2));
+ }
+
+ /**
+ * Gets the index into the data storage for the hashCode specified.
+ * This implementation uses the least significant bits of the hashCode.
+ * Subclasses can override this to return alternate bucketing.
+ *
+ * @param hashCode the hash code to use
+ * @param dataSize the size of the data to pick a bucket from
+ * @return the bucket index
+ */
+ protected int hashIndex(int hashCode, int dataSize) {
+ return hashCode & (dataSize - 1);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the entry mapped to the key specified.
+ *
+ * This method exists for subclasses that may need to perform a multi-step + * process accessing the entry. The public methods in this class don't use this + * method to gain a small performance boost. + * + * @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; + } + + //----------------------------------------------------------------------- + /** + * Updates an existing key-value mapping to change the value. + *
+ * This implementation calls setValue() on the entry.
+ * Subclasses could override to handle changes to the map.
+ *
+ * @param entry the entry to update
+ * @param newValue the new value to store
+ */
+ protected void updateEntry(HashEntry entry, Object newValue) {
+ entry.setValue(newValue);
+ }
+
+ /**
+ * Reuses an existing key-value mapping, storing completely new data.
+ *
+ * This implementation sets all the data fields on the entry. + * Subclasses could populate additional entry fields. + * + * @param entry the entry to update, not null + * @param hashIndex the index in the data array + * @param hashCode the hash code of the key to add + * @param key the key to add + * @param value the value to add + */ + protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) { + entry.next = data[hashIndex]; + entry.hashCode = hashCode; + entry.key = key; + entry.value = value; + } + + //----------------------------------------------------------------------- + /** + * Adds a new key-value mapping into this map. + *
+ * This implementation calls createEntry(), addEntry()
+ * and checkCapacity().
+ * It also handles changes to modCount and size.
+ * Subclasses could override to fully control adds to the map.
+ *
+ * @param hashIndex the index into the data array to store at
+ * @param hashCode the hash code of the key to add
+ * @param key the key to add
+ * @param value the value to add
+ */
+ protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
+ modCount++;
+ HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
+ addEntry(entry, hashIndex);
+ size++;
+ checkCapacity();
+ }
+
+ /**
+ * Creates an entry to store the key-value data.
+ *
+ * This implementation creates a new HashEntry instance. + * Subclasses can override this to return a different storage class, + * or implement caching. + * + * @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) { + return new HashEntry(next, hashCode, key, value); + } + + /** + * Adds an entry into this map. + *
+ * This implementation adds the entry to the data storage table. + * Subclasses could override to handle changes to the map. + * + * @param entry the entry to add + * @param hashIndex the index into the data array to store at + */ + protected void addEntry(HashEntry entry, int hashIndex) { + data[hashIndex] = entry; + } + + //----------------------------------------------------------------------- + /** + * Removes a mapping from the map. + *
+ * This implementation calls removeEntry() and destroyEntry().
+ * It also handles changes to modCount and size.
+ * Subclasses could override to fully control removals from the map.
+ *
+ * @param entry the entry to remove
+ * @param hashIndex the index into the data structure
+ * @param previous the previous entry in the chain
+ */
+ protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
+ modCount++;
+ removeEntry(entry, hashIndex, previous);
+ size--;
+ destroyEntry(entry);
+ }
+
+ /**
+ * Removes an entry from the chain stored in a particular index.
+ *
+ * This implementation removes the entry from the data storage table. + * The size is not updated. + * Subclasses could override to handle changes to the map. + * + * @param entry the entry to remove + * @param hashIndex the index into the data structure + * @param previous the previous entry in the chain + */ + protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) { + if (previous == null) { + data[hashIndex] = entry.next; + } else { + previous.next = entry.next; + } + } + + /** + * Kills an entry ready for the garbage collector. + *
+ * This implementation prepares the HashEntry for garbage collection. + * Subclasses can override this to implement caching (override clear as well). + * + * @param entry the entry to destroy + */ + protected void destroyEntry(HashEntry entry) { + entry.next = null; + entry.key = null; + entry.value = null; + } + + //----------------------------------------------------------------------- + /** + * Checks the capacity of the map and enlarges it if necessary. + *
+ * This implementation uses the threshold to check if the map needs enlarging
+ */
+ protected void checkCapacity() {
+ if (size >= threshold) {
+ int newCapacity = data.length * 2;
+ if (newCapacity <= MAXIMUM_CAPACITY) {
+ ensureCapacity(newCapacity);
+ }
+ }
+ }
+
+ /**
+ * Changes the size of the data structure to the capacity proposed.
+ *
+ * @param newCapacity the new capacity of the array (a power of two, less or equal to max)
+ */
+ protected void ensureCapacity(int newCapacity) {
+ int oldCapacity = data.length;
+ if (newCapacity <= oldCapacity) {
+ return;
+ }
+ if (size == 0) {
+ threshold = calculateThreshold(newCapacity, loadFactor);
+ data = new HashEntry[newCapacity];
+ } else {
+ HashEntry oldEntries[] = data;
+ HashEntry newEntries[] = new HashEntry[newCapacity];
+
+ modCount++;
+ for (int i = oldCapacity - 1; i >= 0; i--) {
+ HashEntry entry = oldEntries[i];
+ if (entry != null) {
+ oldEntries[i] = null; // gc
+ do {
+ HashEntry next = entry.next;
+ int index = hashIndex(entry.hashCode, newCapacity);
+ entry.next = newEntries[index];
+ newEntries[index] = entry;
+ entry = next;
+ } while (entry != null);
+ }
+ }
+ threshold = calculateThreshold(newCapacity, loadFactor);
+ data = newEntries;
+ }
+ }
+
+ /**
+ * Calculates the new capacity of the map.
+ * This implementation normalizes the capacity to a power of two.
+ *
+ * @param proposedCapacity the proposed capacity
+ * @return the normalized new capacity
+ */
+ protected int calculateNewCapacity(int proposedCapacity) {
+ int newCapacity = 1;
+ if (proposedCapacity > MAXIMUM_CAPACITY) {
+ newCapacity = MAXIMUM_CAPACITY;
+ } else {
+ while (newCapacity < proposedCapacity) {
+ newCapacity <<= 1; // multiply by two
+ }
+ if (newCapacity > MAXIMUM_CAPACITY) {
+ newCapacity = MAXIMUM_CAPACITY;
+ }
+ }
+ return newCapacity;
+ }
+
+ /**
+ * Calculates the new threshold of the map, where it will be resized.
+ * This implementation uses the load factor.
+ *
+ * @param newCapacity the new capacity
+ * @param factor the load factor
+ * @return the new resize threshold
+ */
+ protected int calculateThreshold(int newCapacity, float factor) {
+ return (int) (newCapacity * factor);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the next field from a HashEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the next field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected HashEntry entryNext(HashEntry entry) {
+ return entry.next;
+ }
+
+ /**
+ * Gets the hashCode field from a HashEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the hashCode field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected int entryHashCode(HashEntry entry) {
+ return entry.hashCode;
+ }
+
+ /**
+ * Gets the key field from a HashEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the key field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected Object entryKey(HashEntry entry) {
+ return entry.key;
+ }
+
+ /**
+ * Gets the value field from a HashEntry.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the value field of the entry
+ * @throws NullPointerException if the entry is null
+ * @since Commons Collections 3.1
+ */
+ protected Object entryValue(HashEntry entry) {
+ return entry.value;
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets an iterator over the map.
+ * Changes made to the iterator affect this map.
+ *
+ * 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 Map.Entry object. + * + * @return the map iterator + */ + public MapIterator mapIterator() { + if (size == 0) { + return EmptyMapIterator.INSTANCE; + } + return new HashMapIterator(this); + } + + /** + * MapIterator implementation. + */ + protected static class HashMapIterator extends HashIterator implements MapIterator { + + protected HashMapIterator(AbstractHashedMap parent) { + super(parent); + } + + public Object next() { + return super.nextEntry().getKey(); + } + + public Object getKey() { + HashEntry current = currentEntry(); + if (current == null) { + throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); + } + return current.getKey(); + } + + public Object getValue() { + HashEntry current = currentEntry(); + if (current == null) { + throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); + } + return current.getValue(); + } + + public Object setValue(Object value) { + HashEntry current = currentEntry(); + if (current == null) { + throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); + } + return current.setValue(value); + } + } + + //----------------------------------------------------------------------- + /** + * Gets the entrySet view of the map. + * Changes made to the view affect this map. + * To simply iterate through the entries, use {@link #mapIterator()}. + * + * @return the entrySet view + */ + public Set entrySet() { + if (entrySet == null) { + entrySet = new EntrySet(this); + } + return entrySet; + } + + /** + * 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 EmptyIterator.INSTANCE; + } + return new EntrySetIterator(this); + } + + /** + * EntrySet implementation. + */ + protected static class EntrySet extends AbstractSet { + /** The parent map */ + protected final AbstractHashedMap parent; + + protected EntrySet(AbstractHashedMap parent) { + super(); + this.parent = parent; + } + + public int size() { + return parent.size(); + } + + public void clear() { + parent.clear(); + } + + public boolean contains(Object entry) { + if (entry instanceof Map.Entry) { + Map.Entry e = (Map.Entry) entry; + Entry match = parent.getEntry(e.getKey()); + return (match != null && match.equals(e)); + } + return false; + } + + public boolean remove(Object obj) { + if (obj instanceof Map.Entry == false) { + return false; + } + if (contains(obj) == false) { + return false; + } + Map.Entry entry = (Map.Entry) obj; + Object key = entry.getKey(); + parent.remove(key); + return true; + } + + public Iterator iterator() { + return parent.createEntrySetIterator(); + } + } + + /** + * EntrySet iterator. + */ + protected static class EntrySetIterator extends HashIterator { + + protected EntrySetIterator(AbstractHashedMap parent) { + super(parent); + } + + public Object next() { + return super.nextEntry(); + } + } + + //----------------------------------------------------------------------- + /** + * Gets the keySet view of the map. + * Changes made to the view affect this map. + * To simply iterate through the keys, use {@link #mapIterator()}. + * + * @return the keySet view + */ + public Set keySet() { + if (keySet == null) { + keySet = new KeySet(this); + } + return keySet; + } + + /** + * 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 EmptyIterator.INSTANCE; + } + return new KeySetIterator(this); + } + + /** + * KeySet implementation. + */ + protected static class KeySet extends AbstractSet { + /** The parent map */ + protected final AbstractHashedMap parent; + + protected KeySet(AbstractHashedMap parent) { + super(); + this.parent = parent; + } + + public int size() { + return parent.size(); + } + + public void clear() { + parent.clear(); + } + + public boolean contains(Object key) { + return parent.containsKey(key); + } + + public boolean remove(Object key) { + boolean result = parent.containsKey(key); + parent.remove(key); + return result; + } + + public Iterator iterator() { + return parent.createKeySetIterator(); + } + } + + /** + * KeySet iterator. + */ + protected static class KeySetIterator extends EntrySetIterator { + + protected KeySetIterator(AbstractHashedMap parent) { + super(parent); + } + + public Object next() { + return super.nextEntry().getKey(); + } + } + + //----------------------------------------------------------------------- + /** + * Gets the values view of the map. + * Changes made to the view affect this map. + * To simply iterate through the values, use {@link #mapIterator()}. + * + * @return the values view + */ + public Collection values() { + if (values == null) { + values = new Values(this); + } + return values; + } + + /** + * 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 EmptyIterator.INSTANCE; + } + return new ValuesIterator(this); + } + + /** + * Values implementation. + */ + protected static class Values extends AbstractCollection { + /** The parent map */ + protected final AbstractHashedMap parent; + + protected Values(AbstractHashedMap parent) { + super(); + this.parent = parent; + } + + public int size() { + return parent.size(); + } + + public void clear() { + parent.clear(); + } + + public boolean contains(Object value) { + return parent.containsValue(value); + } + + public Iterator iterator() { + return parent.createValuesIterator(); + } + } + + /** + * Values iterator. + */ + protected static class ValuesIterator extends HashIterator { + + protected ValuesIterator(AbstractHashedMap parent) { + super(parent); + } + + public Object next() { + return super.nextEntry().getValue(); + } + } + + //----------------------------------------------------------------------- + /** + * HashEntry used to store the data. + *
+ * If you subclass AbstractHashedMap but not HashEntry
+ * then you will not be able to access the protected fields.
+ * The entryXxx() methods on AbstractHashedMap exist
+ * to provide the necessary access.
+ */
+ protected static class HashEntry implements Map.Entry, KeyValue {
+ /** The next entry in the hash chain */
+ protected HashEntry next;
+ /** The hash code of the key */
+ protected int hashCode;
+ /** The key */
+ protected Object key;
+ /** The value */
+ protected Object value;
+
+ protected HashEntry(HashEntry next, int hashCode, Object key, Object value) {
+ super();
+ this.next = next;
+ this.hashCode = hashCode;
+ this.key = key;
+ this.value = value;
+ }
+
+ public Object getKey() {
+ return (key == NULL ? null : key);
+ }
+
+ public Object getValue() {
+ return value;
+ }
+
+ public Object setValue(Object value) {
+ Object old = this.value;
+ this.value = value;
+ return old;
+ }
+
+ public boolean equals(Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (obj instanceof Map.Entry == false) {
+ return false;
+ }
+ Map.Entry other = (Map.Entry) obj;
+ return
+ (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
+ (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
+ }
+
+ public int hashCode() {
+ return (getKey() == null ? 0 : getKey().hashCode()) ^
+ (getValue() == null ? 0 : getValue().hashCode());
+ }
+
+ public String toString() {
+ return new StringBuffer().append(getKey()).append('=').append(getValue()).toString();
+ }
+ }
+
+ /**
+ * Base Iterator
+ */
+ protected static abstract class HashIterator implements Iterator {
+
+ /** The parent map */
+ protected final AbstractHashedMap parent;
+ /** The current index into the array of buckets */
+ protected int hashIndex;
+ /** The last returned entry */
+ protected HashEntry last;
+ /** The next entry */
+ protected HashEntry next;
+ /** The modification count expected */
+ protected int expectedModCount;
+
+ protected HashIterator(AbstractHashedMap parent) {
+ super();
+ this.parent = parent;
+ HashEntry[] data = parent.data;
+ int i = data.length;
+ HashEntry next = null;
+ while (i > 0 && next == null) {
+ next = data[--i];
+ }
+ this.next = next;
+ this.hashIndex = i;
+ this.expectedModCount = parent.modCount;
+ }
+
+ public boolean hasNext() {
+ return (next != null);
+ }
+
+ protected HashEntry nextEntry() {
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ HashEntry newCurrent = next;
+ if (newCurrent == null) {
+ throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
+ }
+ HashEntry[] data = parent.data;
+ int i = hashIndex;
+ HashEntry n = newCurrent.next;
+ while (n == null && i > 0) {
+ n = data[--i];
+ }
+ next = n;
+ hashIndex = i;
+ last = newCurrent;
+ return newCurrent;
+ }
+
+ protected HashEntry currentEntry() {
+ return last;
+ }
+
+ public void remove() {
+ if (last == null) {
+ throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
+ }
+ if (parent.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ parent.remove(last.getKey());
+ last = null;
+ expectedModCount = parent.modCount;
+ }
+
+ public String toString() {
+ if (last != null) {
+ return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
+ } else {
+ return "Iterator[]";
+ }
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Writes the map data to the stream. This method must be overridden if a
+ * subclass must be setup before put() is used.
+ *
+ * Serialization is not one of the JDK's nicest topics. Normal serialization will
+ * initialise the superclass before the subclass. Sometimes however, this isn't
+ * what you want, as in this case the put() method on read can be
+ * affected by subclass state.
+ *
+ * The solution adopted here is to serialize the state data of this class in
+ * this protected method. This method must be called by the
+ * writeObject() of the first serializable subclass.
+ *
+ * Subclasses may override if they have a specific field that must be present
+ * on read before this implementation will work. Generally, the read determines
+ * what must be serialized here, if anything.
+ *
+ * @param out the output stream
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeFloat(loadFactor);
+ out.writeInt(data.length);
+ out.writeInt(size);
+ for (MapIterator it = mapIterator(); it.hasNext();) {
+ out.writeObject(it.next());
+ out.writeObject(it.getValue());
+ }
+ }
+
+ /**
+ * Reads the map data from the stream. This method must be overridden if a
+ * subclass must be setup before put() is used.
+ *
+ * Serialization is not one of the JDK's nicest topics. Normal serialization will
+ * initialise the superclass before the subclass. Sometimes however, this isn't
+ * what you want, as in this case the put() method on read can be
+ * affected by subclass state.
+ *
+ * The solution adopted here is to deserialize the state data of this class in
+ * this protected method. This method must be called by the
+ * readObject() of the first serializable subclass.
+ *
+ * Subclasses may override if the subclass has a specific field that must be present
+ * before put() or calculateThreshold() will work correctly.
+ *
+ * @param in the input stream
+ */
+ protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ loadFactor = in.readFloat();
+ int capacity = in.readInt();
+ int size = in.readInt();
+ init();
+ data = new HashEntry[capacity];
+ for (int i = 0; i < size; i++) {
+ Object key = in.readObject();
+ Object value = in.readObject();
+ put(key, value);
+ }
+ threshold = calculateThreshold(data.length, loadFactor);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Clones the map without cloning the keys or values.
+ *
+ * To implement clone(), a subclass must implement the
+ * Cloneable interface and make this method public.
+ *
+ * @return a shallow clone
+ */
+ protected Object clone() {
+ try {
+ AbstractHashedMap cloned = (AbstractHashedMap) super.clone();
+ cloned.data = new HashEntry[data.length];
+ cloned.entrySet = null;
+ cloned.keySet = null;
+ cloned.values = null;
+ cloned.modCount = 0;
+ cloned.size = 0;
+ cloned.init();
+ cloned.putAll(this);
+ return cloned;
+
+ } catch (CloneNotSupportedException ex) {
+ return null; // should never happen
+ }
+ }
+
+ /**
+ * Compares this map with another.
+ *
+ * @param obj the object to compare to
+ * @return true if equal
+ */
+ public boolean equals(Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (obj instanceof Map == false) {
+ return false;
+ }
+ Map map = (Map) obj;
+ if (map.size() != size()) {
+ return false;
+ }
+ MapIterator it = mapIterator();
+ try {
+ while (it.hasNext()) {
+ Object key = it.next();
+ Object value = it.getValue();
+ if (value == null) {
+ if (map.get(key) != null || map.containsKey(key) == false) {
+ return false;
+ }
+ } else {
+ if (value.equals(map.get(key)) == false) {
+ return false;
+ }
+ }
+ }
+ } catch (ClassCastException ignored) {
+ return false;
+ } catch (NullPointerException ignored) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Gets the standard Map hashCode.
+ *
+ * @return the hash code defined in the Map interface
+ */
+ public int hashCode() {
+ int total = 0;
+ Iterator it = createEntrySetIterator();
+ while (it.hasNext()) {
+ total += it.next().hashCode();
+ }
+ return total;
+ }
+
+ /**
+ * Gets the map as a String.
+ *
+ * @return a string version of the map
+ */
+ public String toString() {
+ if (size() == 0) {
+ return "{}";
+ }
+ StringBuffer buf = new StringBuffer(32 * size());
+ buf.append('{');
+
+ MapIterator it = mapIterator();
+ boolean hasNext = it.hasNext();
+ while (hasNext) {
+ Object key = it.next();
+ Object value = it.getValue();
+ buf.append(key == this ? "(this Map)" : key)
+ .append('=')
+ .append(value == this ? "(this Map)" : value);
+
+ hasNext = it.hasNext();
+ if (hasNext) {
+ buf.append(',').append(' ');
+ }
+ }
+
+ buf.append('}');
+ return buf.toString();
+ }
+}
Index: extra/collections/BoundedMap.java
===================================================================
--- extra/collections/BoundedMap.java (revision 0)
+++ extra/collections/BoundedMap.java (revision 0)
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+import java.util.Map;
+
+/**
+ * Defines a map that is bounded in size.
+ *
+ * The size of the map can vary, but it can never exceed a preset
+ * maximum number of elements. This interface allows the querying of details
+ * associated with the maximum number of elements.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface BoundedMap extends Map {
+
+ /**
+ * Returns true if this map is full and no new elements can be added.
+ *
+ * @return true if the map is full
+ */
+ boolean isFull();
+
+ /**
+ * Gets the maximum size of the map (the bound).
+ *
+ * @return the maximum number of elements the map can hold
+ */
+ int maxSize();
+
+}
Index: extra/collections/OrderedIterator.java
===================================================================
--- extra/collections/OrderedIterator.java (revision 0)
+++ extra/collections/OrderedIterator.java (revision 0)
@@ -0,0 +1,47 @@
+/*
+ * Copyright 2003-2004 The Apache Software Foundation
+ *
+ * Licensed 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.taglibs.standard.extra.commons.collections;
+
+import java.util.Iterator;
+
+/**
+ * Defines an iterator that operates over an ordered collection.
+ *
+ * This iterator allows both forward and reverse iteration through the collection.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
+ *
+ * @author Stephen Colebourne
+ */
+public interface OrderedIterator extends Iterator {
+
+ /**
+ * Checks to see if there is a previous element that can be iterated to.
+ *
+ * @return true if the iterator has a previous element
+ */
+ boolean hasPrevious();
+
+ /**
+ * Gets the previous element from the collection.
+ *
+ * @return the previous element in the iteration
+ * @throws java.util.NoSuchElementException if the iteration is finished
+ */
+ Object previous();
+
+}