Applying Bjorn's patch for Bug 31789, bringing Justyna's patch r218351 over from the 1.0.x
branch. Justyna noted that Commons EL needs to be modified to use this solution, but I
think that was with the view that JSTL 1.1 would depend on Commons EL - which it does
not (yet). Still - this solution also needs to be applied to Commons EL. This solution
adds an extract of code from Commons Collections
diff --git a/NOTICE b/NOTICE
new file mode 100644
index 0000000..91a2d9a
--- /dev/null
+++ b/NOTICE
@@ -0,0 +1 @@
+Includes code from Commons Collections (LRUMap and the classes/interfaces it requires).
diff --git a/src/org/apache/taglibs/standard/extra/collections/BoundedMap.java b/src/org/apache/taglibs/standard/extra/collections/BoundedMap.java
new file mode 100644
index 0000000..8ba7096
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/BoundedMap.java
@@ -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.
+ * <p>
+ * 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 <code>true</code> 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();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/IterableMap.java b/src/org/apache/taglibs/standard/extra/collections/IterableMap.java
new file mode 100644
index 0000000..9f13e75
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/IterableMap.java
@@ -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.
+ * <p>
+ * 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.
+ * <pre>
+ * IterableMap map = new HashedMap();
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue("newValue");
+ * }
+ * </pre>
+ *
+ * @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 <code>MapIterator</code> over the map.
+ * <p>
+ * 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.
+ * <pre>
+ * IterableMap map = new HashedMap();
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue("newValue");
+ * }
+ * </pre>
+ *
+ * @return a map iterator
+ */
+ MapIterator mapIterator();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/KeyValue.java b/src/org/apache/taglibs/standard/extra/collections/KeyValue.java
new file mode 100644
index 0000000..fae391d
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/KeyValue.java
@@ -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.
+ * <p>
+ * 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();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/MapIterator.java b/src/org/apache/taglibs/standard/extra/collections/MapIterator.java
new file mode 100644
index 0000000..1478629
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/MapIterator.java
@@ -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 <code>Map</code>.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * In use, this iterator iterates through the keys in the map. After each call
+ * to <code>next()</code>, the <code>getValue()</code> method provides direct
+ * access to the value. The value can also be set using <code>setValue()</code>.
+ * <pre>
+ * MapIterator it = map.mapIterator();
+ * while (it.hasNext()) {
+ * Object key = it.next();
+ * Object value = it.getValue();
+ * it.setValue(newValue);
+ * }
+ * </pre>
+ *
+ * @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 <code>true</code> if the iterator has more elements
+ */
+ boolean hasNext();
+
+ /**
+ * Gets the next <em>key</em> from the <code>Map</code>.
+ *
+ * @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 <code>next()</code>.
+ *
+ * @return the current key
+ * @throws IllegalStateException if <code>next()</code> has not yet been called
+ */
+ Object getKey();
+
+ /**
+ * Gets the current value, which is the value associated with the last key
+ * returned by <code>next()</code>.
+ *
+ * @return the current value
+ * @throws IllegalStateException if <code>next()</code> has not yet been called
+ */
+ Object getValue();
+
+ //-----------------------------------------------------------------------
+ /**
+ * Removes the last returned key from the underlying <code>Map</code> (optional operation).
+ * <p>
+ * This method can be called once per call to <code>next()</code>.
+ *
+ * @throws UnsupportedOperationException if remove is not supported by the map
+ * @throws IllegalStateException if <code>next()</code> has not yet been called
+ * @throws IllegalStateException if <code>remove()</code> has already been called
+ * since the last call to <code>next()</code>
+ */
+ 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 <code>next()</code> has not yet been called
+ * @throws IllegalStateException if <code>remove()</code> has been called since the
+ * last call to <code>next()</code>
+ */
+ Object setValue(Object value);
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/OrderedIterator.java b/src/org/apache/taglibs/standard/extra/collections/OrderedIterator.java
new file mode 100644
index 0000000..b099bda
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/OrderedIterator.java
@@ -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.
+ * <p>
+ * 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 <code>true</code> 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();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/OrderedMap.java b/src/org/apache/taglibs/standard/extra/collections/OrderedMap.java
new file mode 100644
index 0000000..fe3861e
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/OrderedMap.java
@@ -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 <code>OrderedMapIterator</code> over the map.
+ * <p>
+ * A ordered map iterator is an efficient way of iterating over maps
+ * in both directions.
+ * <pre>
+ * 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();
+ * }
+ * </pre>
+ *
+ * @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);
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/OrderedMapIterator.java b/src/org/apache/taglibs/standard/extra/collections/OrderedMapIterator.java
new file mode 100644
index 0000000..96d34ad
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/OrderedMapIterator.java
@@ -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 <code>Map</code>.
+ * <p>
+ * 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 <code>true</code> if the iterator has a previous element
+ */
+ boolean hasPrevious();
+
+ /**
+ * Gets the previous <em>key</em> from the <code>Map</code>.
+ *
+ * @return the previous key in the iteration
+ * @throws java.util.NoSuchElementException if the iteration is finished
+ */
+ Object previous();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/README.txt b/src/org/apache/taglibs/standard/extra/collections/README.txt
new file mode 100644
index 0000000..03b1de9
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/README.txt
@@ -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
diff --git a/src/org/apache/taglibs/standard/extra/collections/ResettableIterator.java b/src/org/apache/taglibs/standard/extra/collections/ResettableIterator.java
new file mode 100644
index 0000000..73c08c7
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/ResettableIterator.java
@@ -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.
+ * <p>
+ * 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();
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/iterators/AbstractEmptyIterator.java b/src/org/apache/taglibs/standard/extra/collections/iterators/AbstractEmptyIterator.java
new file mode 100644
index 0000000..8877ef0
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/iterators/AbstractEmptyIterator.java
@@ -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
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyIterator.java b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyIterator.java
new file mode 100644
index 0000000..f2e67b1
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyIterator.java
@@ -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.
+ * <p>
+ * 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 <code>IteratorUtils</code>.
+ *
+ * @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();
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyMapIterator.java b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyMapIterator.java
new file mode 100644
index 0000000..8b2ed7c
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyMapIterator.java
@@ -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();
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedIterator.java b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedIterator.java
new file mode 100644
index 0000000..3939d77
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedIterator.java
@@ -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();
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedMapIterator.java b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedMapIterator.java
new file mode 100644
index 0000000..cfdd3e7
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/iterators/EmptyOrderedMapIterator.java
@@ -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();
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/map/AbstractHashedMap.java b/src/org/apache/taglibs/standard/extra/collections/map/AbstractHashedMap.java
new file mode 100644
index 0000000..f88e7f5
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/map/AbstractHashedMap.java
@@ -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.
+ * <p>
+ * This class implements all the features necessary for a subclass hash-based map.
+ * Key-value entries are stored in instances of the <code>HashEntry</code> 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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 <code>entry.key</code>
+ * @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 <code>getValue()</code>
+ * @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.
+ * <p>
+ * 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.
+ * <p>
+ * This implementation calls <code>setValue()</code> 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.
+ * <p>
+ * 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.
+ * <p>
+ * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
+ * and <code>checkCapacity()</code>.
+ * It also handles changes to <code>modCount</code> and <code>size</code>.
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
+ * It also handles changes to <code>modCount</code> and <code>size</code>.
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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 <code>next</code> field from a <code>HashEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>next</code> 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 <code>hashCode</code> field from a <code>HashEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>hashCode</code> 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 <code>key</code> field from a <code>HashEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>key</code> 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 <code>value</code> field from a <code>HashEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>value</code> 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.
+ * <p>
+ * A MapIterator returns the keys in the map. It also provides convenient
+ * methods to get the key and value, and set the value.
+ * It avoids the need to create an entrySet/keySet/values object.
+ * It also avoids creating the 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.
+ * <p>
+ * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
+ * then you will not be able to access the protected fields.
+ * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> 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 <code>put()</code> is used.
+ * <p>
+ * 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 <code>put()</code> method on read can be
+ * affected by subclass state.
+ * <p>
+ * The solution adopted here is to serialize the state data of this class in
+ * this protected method. This method must be called by the
+ * <code>writeObject()</code> of the first serializable subclass.
+ * <p>
+ * 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 <code>put()</code> is used.
+ * <p>
+ * 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 <code>put()</code> method on read can be
+ * affected by subclass state.
+ * <p>
+ * The solution adopted here is to deserialize the state data of this class in
+ * this protected method. This method must be called by the
+ * <code>readObject()</code> of the first serializable subclass.
+ * <p>
+ * Subclasses may override if the subclass has a specific field that must be present
+ * before <code>put()</code> or <code>calculateThreshold()</code> 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.
+ * <p>
+ * To implement <code>clone()</code>, a subclass must implement the
+ * <code>Cloneable</code> 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();
+ }
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java b/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
new file mode 100644
index 0000000..9cbb9f0
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/map/AbstractLinkedMap.java
@@ -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.
+ * <p>
+ * This class implements all the features necessary for a subclass linked
+ * hash-based map. Key-value entries are stored in instances of the
+ * <code>LinkEntry</code> 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.
+ * <p>
+ * 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.
+ * <p>
+ * This implementation maintains order by original insertion, but subclasses
+ * may work differently. The <code>OrderedMap</code> interface is implemented
+ * to provide access to bidirectional iteration and extra convenience methods.
+ * <p>
+ * The <code>orderedMapIterator()</code> method provides direct access to a
+ * bidirectional iterator. The iterators from the other views can also be cast
+ * to <code>OrderedIterator</code> if required.
+ * <p>
+ * All the available iterators can be reset back to the start by casting to
+ * <code>ResettableIterator</code> and calling <code>reset()</code>.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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 <code>before</code> field from a <code>LinkEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>before</code> 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 <code>after</code> field from a <code>LinkEntry</code>.
+ * Used in subclasses that have no visibility of the field.
+ *
+ * @param entry the entry to query, must not be null
+ * @return the <code>after</code> 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.
+ * <p>
+ * A MapIterator returns the keys in the map. It also provides convenient
+ * methods to get the key and value, and set the value.
+ * It avoids the need to create an entrySet/keySet/values object.
+ *
+ * @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.
+ * <p>
+ * A MapIterator returns the keys in the map. It also provides convenient
+ * methods to get the key and value, and set the value.
+ * It avoids the need to create an entrySet/keySet/values object.
+ *
+ * @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.
+ * <p>
+ * If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
+ * then you will not be able to access the protected fields.
+ * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> 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[]";
+ }
+ }
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java b/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
new file mode 100644
index 0000000..5953980
--- /dev/null
+++ b/src/org/apache/taglibs/standard/extra/collections/map/LRUMap.java
@@ -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 <code>Map</code> implementation with a fixed maximum size which removes
+ * the least recently used entry if an entry is added when full.
+ * <p>
+ * 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.
+ * <p>
+ * The map implements <code>OrderedMap</code> and entries may be queried using
+ * the bidirectional <code>OrderedMapIterator</code>. The order returned is
+ * least recently used to most recently used. Iterators from map views can
+ * also be cast to <code>OrderedIterator</code> if required.
+ * <p>
+ * All the available iterators can be reset back to the start by casting to
+ * <code>ResettableIterator</code> and calling <code>reset()</code>.
+ *
+ * @since Commons Collections 3.0 (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.
+ * <p>
+ * 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.
+ * <p/>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * 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.
+ * <p>
+ * This implementation checks the LRU size and determines whether to
+ * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
+ * <p>
+ * From Commons Collections 3.1 this method uses {@link #isFull()} rather
+ * than accessing <code>size</code> and <code>maxSize</code> 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.
+ * <p>
+ * 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.
+ * <p>
+ * This method exists for subclasses to override. A subclass may wish to
+ * provide cleanup of resources when an entry is removed. For example:
+ * <pre>
+ * protected boolean removeLRU(LinkEntry entry) {
+ * releaseResources(entry.getValue()); // release resources held by entry
+ * return true; // actually delete entry
+ * }
+ * </pre>
+ * <p>
+ * Alternatively, a subclass may choose to not remove the entry or selectively
+ * keep certain LRU entries. For example:
+ * <pre>
+ * protected boolean removeLRU(LinkEntry entry) {
+ * if (entry.getKey().toString().startsWith("System.")) {
+ * return false; // entry not removed from LRUMap
+ * } else {
+ * return true; // actually delete entry
+ * }
+ * }
+ * </pre>
+ * 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.
+ * <p>
+ * 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 <code>true</code> 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 <code>put()</code> to work in deserialization.
+ */
+ protected void doWriteObject(ObjectOutputStream out) throws IOException {
+ out.writeInt(maxSize);
+ super.doWriteObject(out);
+ }
+
+ /**
+ * Reads the data necessary for <code>put()</code> to work in the superclass.
+ */
+ protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ maxSize = in.readInt();
+ super.doReadObject(in);
+ }
+
+}
diff --git a/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java b/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
index 28d2661..8317dcf 100644
--- a/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
+++ b/src/org/apache/taglibs/standard/lang/jstl/ELEvaluator.java
@@ -27,6 +27,10 @@
import org.apache.taglibs.standard.lang.jstl.parser.ParseException;
import org.apache.taglibs.standard.lang.jstl.parser.Token;
import org.apache.taglibs.standard.lang.jstl.parser.TokenMgrError;
+import org.apache.taglibs.standard.extra.commons.collections.map.LRUMap;
+
+import javax.servlet.jsp.PageContext;
+import javax.servlet.jsp.jstl.core.Config;
/**
*
@@ -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
//-------------------------------------
/**
diff --git a/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java b/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
index 457cf45..baf3250 100644
--- a/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
+++ b/src/org/apache/taglibs/standard/lang/jstl/Evaluator.java
@@ -68,7 +68,9 @@
String pAttributeValue)
{
try {
+ sEvaluator.setBypassCache(true);
sEvaluator.parseExpressionString (pAttributeValue);
+ sEvaluator.setBypassCache(false);
return null;
}
catch (ELException exc) {
