Attachment #20887 for bug #31789

View | Details | Raw Unified | Return to bug 31789
Collapse All | Expand All

Lines 27-33 Link Here

(-)lang/jstl/ELEvaluator.java (-17 / +65 lines)
27	import org.apache.taglibs.standard.lang.jstl.parser.ParseException;	27	import org.apache.taglibs.standard.lang.jstl.parser.ParseException;
28	import org.apache.taglibs.standard.lang.jstl.parser.Token;	28	import org.apache.taglibs.standard.lang.jstl.parser.Token;
29	import org.apache.taglibs.standard.lang.jstl.parser.TokenMgrError;	29	import org.apache.taglibs.standard.lang.jstl.parser.TokenMgrError;
		30	import org.apache.taglibs.standard.extra.commons.collections.map.LRUMap;
30		31
		32	import javax.servlet.jsp.PageContext;
		33	import javax.servlet.jsp.jstl.core.Config;
		34
31	/**	35	/**
32	*	36	*
33	* <p>This is the main class for evaluating expression Strings. An	37	* <p>This is the main class for evaluating expression Strings. An
Lines 89-102 Link Here
89	// Member variables	93	// Member variables
90	//-------------------------------------	94	//-------------------------------------
91		95
		96	/**
		97	* Name of configuration setting for maximum number of entries in the
		98	* cached expression string map
		99	*/
		100	private static final String EXPR_CACHE_PARAM
		101	= "org.apache.taglibs.standard.lang.jstl.exprCacheSize";
		102	/**
		103	* Default maximum cache size
		104	*/
		105	private static final int MAX_SIZE = 100;
		106
92	/** The mapping from expression String to its parsed form (String,	107	/** The mapping from expression String to its parsed form (String,
93	Expression, or ExpressionString) **/	108	* Expression, or ExpressionString)
94	static Map sCachedExpressionStrings =	109	*
95	Collections.synchronizedMap (new HashMap ());	110	* Using LRU Map with a maximum capacity to avoid out of bound map
		111	* growth.
		112	*
		113	* NOTE: use LinkedHashmap if a dependency on J2SE 1.4+ is ok
		114	*/
		115	static Map sCachedExpressionStrings = null;
96		116
97	/** The mapping from ExpectedType to Maps mapping literal String to	117	/** The mapping from ExpectedType to Maps mapping literal String to
98	parsed value **/	118	parsed value **/
99	static Map sCachedExpectedTypes = new HashMap ();	119	static Map sCachedExpectedTypes = new HashMap();
100		120
101	/ The static Logger /	121	/ The static Logger /
102	static Logger sLogger = new Logger (System.out);	122	static Logger sLogger = new Logger (System.out);
Lines 107-112 Link Here
107	/ Flag if the cache should be bypassed /	127	/ Flag if the cache should be bypassed /
108	boolean mBypassCache;	128	boolean mBypassCache;
109		129
		130	/ The PageContext /
		131	PageContext pageContext;
		132
		133
110	//-------------------------------------	134	//-------------------------------------
111	/**	135	/**
112	*	136	*
Lines 123-142 Link Here
123		147
124	//-------------------------------------	148	//-------------------------------------
125	/**	149	/**
		150	* Enable cache bypass
126	*	151	*
127	* Constructor	152	* @param pBypassCache flag indicating cache should be bypassed
128	*
129	* @param pResolver the object that should be used to resolve
130	* variable names encountered in expressions. If null, all variable
131	* references will resolve to null.
132	*
133	* @param pBypassCache flag indicating if the cache should be
134	* bypassed
135	**/	153	**/
136	public ELEvaluator (VariableResolver pResolver,	154	public void setBypassCache(boolean pBypassCache) {
137	boolean pBypassCache)
138	{
139	mResolver = pResolver;
140	mBypassCache = pBypassCache;	155	mBypassCache = pBypassCache;
141	}	156	}
142		157
Lines 187-192 Link Here
187	(Constants.NULL_EXPRESSION_STRING);	202	(Constants.NULL_EXPRESSION_STRING);
188	}	203	}
189		204
		205	// Set the PageContext;
		206	pageContext = (PageContext) pContext;
		207
190	// Get the parsed version of the expression string	208	// Get the parsed version of the expression string
191	Object parsedValue = parseExpressionString (pExpressionString);	209	Object parsedValue = parseExpressionString (pExpressionString);
192		210
Lines 247-252 Link Here
247	return "";	265	return "";
248	}	266	}
249		267
		268	if (!(mBypassCache) && (sCachedExpressionStrings == null)) {
		269	createExpressionStringMap();
		270	}
		271
250	// See if it's in the cache	272	// See if it's in the cache
251	Object ret =	273	Object ret =
252	mBypassCache ?	274	mBypassCache ?
Lines 259-265 Link Here
259	ELParser parser = new ELParser (r);	281	ELParser parser = new ELParser (r);
260	try {	282	try {
261	ret = parser.ExpressionString ();	283	ret = parser.ExpressionString ();
262	sCachedExpressionStrings.put (pExpressionString, ret);	284	if (!mBypassCache) {
		285	sCachedExpressionStrings.put (pExpressionString, ret);
		286	}
263	}	287	}
264	catch (ParseException exc) {	288	catch (ParseException exc) {
265	throw new ELException	289	throw new ELException
Lines 342-347 Link Here
342	}	366	}
343		367
344	//-------------------------------------	368	//-------------------------------------
		369	/**
		370	*
		371	* Creates LRU map of expression strings. If context parameter
		372	* specifying cache size is present use that as the maximum size
		373	* of the LRU map otherwise use default.
		374	**/
		375	private synchronized void createExpressionStringMap () {
		376	if (sCachedExpressionStrings != null) {
		377	return;
		378	}
		379
		380	String value = pageContext.getServletContext().
		381	getInitParameter(EXPR_CACHE_PARAM);
		382	if (value != null) {
		383	sCachedExpressionStrings =
		384	Collections.synchronizedMap(new LRUMap(Integer.parseInt(value)));
		385	}
		386	else {
		387	sCachedExpressionStrings =
		388	Collections.synchronizedMap(new LRUMap(MAX_SIZE));
		389	}
		390	}
		391
		392	//-------------------------------------
345	// Formatting ParseException	393	// Formatting ParseException
346	//-------------------------------------	394	//-------------------------------------
347	/**	395	/**

Lines 68-74 Link Here

(-)lang/jstl/Evaluator.java (+2 lines)
68	String pAttributeValue)	68	String pAttributeValue)
69	{	69	{
70	try {	70	try {
		71	sEvaluator.setBypassCache(true);
71	sEvaluator.parseExpressionString (pAttributeValue);	72	sEvaluator.parseExpressionString (pAttributeValue);
		73	sEvaluator.setBypassCache(false);
72	return null;	74	return null;
73	}	75	}
74	catch (ELException exc) {	76	catch (ELException exc) {




/*
 *  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);
    
}




/*
 *  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();

}




/*
 *  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();
    
}




/*
 *  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();

}




/*
 *  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);

}

Line 0 Link Here

(-)extra/collections/README.txt (+10 lines)
	1	Jakarta Commons Collections classes
	2	Version: 3.2
	3
	4	These classes are necessary for LRUMap implementation used in ELEvaluator to cache expression strings.
	5
	6	These classes can be deleted for any of the following reasons:
	7	- a custom caching mechanism is implemented
	8	- jakarta-commons collections jar file is made a required dependency
	9	- J2SE 1.4.x or higher is required
	10	- can leverage LRU LinkedHashmap implementation




/*
 *  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();
    }

}




/*
 *  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();
    }

}




/*
 *  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();
    }

}




/*
 *  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
    }

}




/*
 *  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();
    }

}




/*
 *  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();

}




/*
 *  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);
    }
    
}




/*
 *  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[]";
            }
        }
    }
    
}




/*
 *  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 &gt; 0.0f and generally &lt; 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();
    }
}




/*
 *  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();

}




/*
 *  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();

}

Return to bug 31789

Line 0 Link Here

(-)extra/collections/OrderedMap.java (+81 lines)
		1	/*
		2	* Copyright 2001-2004 The Apache Software Foundation
		3	*
		4	* Licensed under the Apache License, Version 2.0 (the "License");
		5	* you may not use this file except in compliance with the License.
		6	* You may obtain a copy of the License at
		7	*
		8	* http://www.apache.org/licenses/LICENSE-2.0
		9	*
		10	* Unless required by applicable law or agreed to in writing, software
		11	* distributed under the License is distributed on an "AS IS" BASIS,
		12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		13	* See the License for the specific language governing permissions and
		14	* limitations under the License.
		15	*/
		16	package org.apache.taglibs.standard.extra.commons.collections;
		17
		18	/**
		19	* Defines a map that maintains order and allows both forward and backward
		20	* iteration through that order.
		21	*
		22	* @since Commons Collections 3.0
		23	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
		24	*
		25	* @author Stephen Colebourne
		26	*/
		27	public interface OrderedMap extends IterableMap {
		28
		29	/**
		30	* Obtains an <code>OrderedMapIterator</code> over the map.
		31	* <p>
		32	* A ordered map iterator is an efficient way of iterating over maps
		33	* in both directions.
		34	* <pre>
		35	* BidiMap map = new TreeBidiMap();
		36	* MapIterator it = map.mapIterator();
		37	* while (it.hasNext()) {
		38	* Object key = it.next();
		39	* Object value = it.getValue();
		40	* it.setValue("newValue");
		41	* Object previousKey = it.previous();
		42	* }
		43	* </pre>
		44	*
		45	* @return a map iterator
		46	*/
		47	OrderedMapIterator orderedMapIterator();
		48
		49	/**
		50	* Gets the first key currently in this map.
		51	*
		52	* @return the first key currently in this map
		53	* @throws java.util.NoSuchElementException if this map is empty
		54	*/
		55	public Object firstKey();
		56
		57	/**
		58	* Gets the last key currently in this map.
		59	*
		60	* @return the last key currently in this map
		61	* @throws java.util.NoSuchElementException if this map is empty
		62	*/
		63	public Object lastKey();
		64
65	/**
66	* Gets the next key after the one specified.
67	*
68	* @param key the key to search for next from
69	* @return the next key, null if no match or at end
70	*/
71	public Object nextKey(Object key);
72
73	/**
74	* Gets the previous key before the one specified.
75	*
76	* @param key the key to search for previous from
77	* @return the previous key, null if no match or at start
78	*/
79	public Object previousKey(Object key);
80
81	}

Line 0 Link Here

(-)extra/collections/ResettableIterator.java (+38 lines)
	1	/*
	2	* Copyright 2003-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	import java.util.Iterator;
	19
	20	/**
	21	* Defines an iterator that can be reset back to an initial state.
	22	* <p>
	23	* This interface allows an iterator to be repeatedly reused.
	24	*
	25	* @since Commons Collections 3.0
	26	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	27	*
	28	* @author Stephen Colebourne
	29	*/
	30	public interface ResettableIterator extends Iterator {
	31
	32	/**
	33	* Resets the iterator back to the position at which the iterator
	34	* was created.
	35	*/
	36	public void reset();
	37
	38	}

Line 0 Link Here

(-)extra/collections/IterableMap.java (+61 lines)
	1	/*
	2	* Copyright 2003-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	import java.util.Map;
	19
	20	/**
	21	* Defines a map that can be iterated directly without needing to create an entry set.
	22	* <p>
	23	* A map iterator is an efficient way of iterating over maps.
	24	* There is no need to access the entry set or cast to Map Entry objects.
	25	* <pre>
	26	* IterableMap map = new HashedMap();
	27	* MapIterator it = map.mapIterator();
	28	* while (it.hasNext()) {
	29	* Object key = it.next();
	30	* Object value = it.getValue();
	31	* it.setValue("newValue");
	32	* }
	33	* </pre>
	34	*
	35	* @since Commons Collections 3.0
	36	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	37	*
	38	* @author Stephen Colebourne
	39	*/
	40	public interface IterableMap extends Map {
	41
	42	/**
	43	* Obtains a <code>MapIterator</code> over the map.
	44	* <p>
	45	* A map iterator is an efficient way of iterating over maps.
	46	* There is no need to access the entry set or cast to Map Entry objects.
	47	* <pre>
	48	* IterableMap map = new HashedMap();
	49	* MapIterator it = map.mapIterator();
	50	* while (it.hasNext()) {
	51	* Object key = it.next();
	52	* Object value = it.getValue();
	53	* it.setValue("newValue");
	54	* }
	55	* </pre>
	56	*
	57	* @return a map iterator
	58	*/
	59	MapIterator mapIterator();
	60
	61	}

Line 0 Link Here

(-)extra/collections/KeyValue.java (+46 lines)
	1	/*
	2	* Copyright 2003-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	/**
	19	* Defines a simple key value pair.
	20	* <p>
	21	* A Map Entry has considerable additional semantics over and above a simple
	22	* key-value pair. This interface defines the minimum key value, with just the
	23	* two get methods.
	24	*
	25	* @since Commons Collections 3.0
	26	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	27	*
	28	* @author Stephen Colebourne
	29	*/
	30	public interface KeyValue {
	31
	32	/**
	33	* Gets the key from the pair.
	34	*
	35	* @return the key
	36	*/
	37	Object getKey();
	38
	39	/**
	40	* Gets the value from the pair.
	41	*
	42	* @return the value
	43	*/
	44	Object getValue();
	45
	46	}

Line 0 Link Here

(-)extra/collections/MapIterator.java (+108 lines)
		1	/*
		2	* Copyright 2003-2004 The Apache Software Foundation
		3	*
		4	* Licensed under the Apache License, Version 2.0 (the "License");
		5	* you may not use this file except in compliance with the License.
		6	* You may obtain a copy of the License at
		7	*
		8	* http://www.apache.org/licenses/LICENSE-2.0
		9	*
		10	* Unless required by applicable law or agreed to in writing, software
		11	* distributed under the License is distributed on an "AS IS" BASIS,
		12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		13	* See the License for the specific language governing permissions and
		14	* limitations under the License.
		15	*/
		16	package org.apache.taglibs.standard.extra.commons.collections;
		17
		18	import java.util.Iterator;
		19
		20	/**
		21	* Defines an iterator that operates over a <code>Map</code>.
		22	* <p>
		23	* This iterator is a special version designed for maps. It can be more
		24	* efficient to use this rather than an entry set iterator where the option
		25	* is available, and it is certainly more convenient.
		26	* <p>
		27	* A map that provides this interface may not hold the data internally using
		28	* Map Entry objects, thus this interface can avoid lots of object creation.
		29	* <p>
		30	* In use, this iterator iterates through the keys in the map. After each call
		31	* to <code>next()</code>, the <code>getValue()</code> method provides direct
		32	* access to the value. The value can also be set using <code>setValue()</code>.
		33	* <pre>
		34	* MapIterator it = map.mapIterator();
		35	* while (it.hasNext()) {
		36	* Object key = it.next();
		37	* Object value = it.getValue();
		38	* it.setValue(newValue);
		39	* }
		40	* </pre>
		41	*
		42	* @since Commons Collections 3.0
		43	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
		44	*
		45	* @author Stephen Colebourne
		46	*/
		47	public interface MapIterator extends Iterator {
		48
		49	/**
		50	* Checks to see if there are more entries still to be iterated.
		51	*
		52	* @return <code>true</code> if the iterator has more elements
		53	*/
		54	boolean hasNext();
		55
		56	/**
		57	* Gets the next <em>key</em> from the <code>Map</code>.
		58	*
		59	* @return the next key in the iteration
		60	* @throws java.util.NoSuchElementException if the iteration is finished
		61	*/
		62	Object next();
		63
		64	//-----------------------------------------------------------------------
65	/**
66	* Gets the current key, which is the key returned by the last call
67	* to <code>next()</code>.
68	*
69	* @return the current key
70	* @throws IllegalStateException if <code>next()</code> has not yet been called
71	*/
72	Object getKey();
73
74	/**
75	* Gets the current value, which is the value associated with the last key
76	* returned by <code>next()</code>.
77	*
78	* @return the current value
79	* @throws IllegalStateException if <code>next()</code> has not yet been called
80	*/
81	Object getValue();
82
83	//-----------------------------------------------------------------------
84	/**
85	* Removes the last returned key from the underlying <code>Map</code> (optional operation).
86	* <p>
87	* This method can be called once per call to <code>next()</code>.
88	*
89	* @throws UnsupportedOperationException if remove is not supported by the map
90	* @throws IllegalStateException if <code>next()</code> has not yet been called
91	* @throws IllegalStateException if <code>remove()</code> has already been called
92	* since the last call to <code>next()</code>
93	*/
94	void remove();
95
96	/**
97	* Sets the value associated with the current key (optional operation).
98	*
99	* @param value the new value
100	* @return the previous value
101	* @throws UnsupportedOperationException if setValue is not supported by the map
102	* @throws IllegalStateException if <code>next()</code> has not yet been called
103	* @throws IllegalStateException if <code>remove()</code> has been called since the
104	* last call to <code>next()</code>
105	*/
106	Object setValue(Object value);
107
108	}

Line 0 Link Here

(-)extra/collections/iterators/EmptyMapIterator.java (+44 lines)
	1	/*
	2	* Copyright 2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections.iterators;
	17
	18	import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
	19	import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
	20
	21	/**
	22	* Provides an implementation of an empty map iterator.
	23	*
	24	* @since Commons Collections 3.1
	25	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	26	*
	27	* @author Stephen Colebourne
	28	*/
	29	public class EmptyMapIterator extends AbstractEmptyIterator implements MapIterator, ResettableIterator {
	30
	31	/**
	32	* Singleton instance of the iterator.
	33	* @since Commons Collections 3.1
	34	*/
	35	public static final MapIterator INSTANCE = new EmptyMapIterator();
	36
	37	/**
	38	* Constructor.
	39	*/
	40	protected EmptyMapIterator() {
	41	super();
	42	}
	43
	44	}

Line 0 Link Here

(-)extra/collections/iterators/EmptyIterator.java (+54 lines)
	1	/*
	2	* Copyright 2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections.iterators;
	17
	18	import java.util.Iterator;
	19
	20	import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
	21
	22	/**
	23	* Provides an implementation of an empty iterator.
	24	* <p>
	25	* This class provides an implementation of an empty iterator.
	26	* This class provides for binary compatability between Commons Collections
	27	* 2.1.1 and 3.1 due to issues with <code>IteratorUtils</code>.
	28	*
	29	* @since Commons Collections 2.1.1 and 3.1
	30	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	31	*
	32	* @author Stephen Colebourne
	33	*/
	34	public class EmptyIterator extends AbstractEmptyIterator implements ResettableIterator {
	35
	36	/**
	37	* Singleton instance of the iterator.
	38	* @since Commons Collections 3.1
	39	*/
	40	public static final ResettableIterator RESETTABLE_INSTANCE = new EmptyIterator();
	41	/**
	42	* Singleton instance of the iterator.
	43	* @since Commons Collections 2.1.1 and 3.1
	44	*/
	45	public static final Iterator INSTANCE = RESETTABLE_INSTANCE;
	46
	47	/**
	48	* Constructor.
	49	*/
	50	protected EmptyIterator() {
	51	super();
	52	}
	53
	54	}

Line 0 Link Here

(-)extra/collections/iterators/EmptyOrderedMapIterator.java (+44 lines)
	1	/*
	2	* Copyright 2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections.iterators;
	17
	18	import org.apache.taglibs.standard.extra.commons.collections.OrderedMapIterator;
	19	import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
	20
	21	/**
	22	* Provides an implementation of an empty ordered map iterator.
	23	*
	24	* @since Commons Collections 3.1
	25	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	26	*
	27	* @author Stephen Colebourne
	28	*/
	29	public class EmptyOrderedMapIterator extends AbstractEmptyIterator implements OrderedMapIterator, ResettableIterator {
	30
	31	/**
	32	* Singleton instance of the iterator.
	33	* @since Commons Collections 3.1
	34	*/
	35	public static final OrderedMapIterator INSTANCE = new EmptyOrderedMapIterator();
	36
	37	/**
	38	* Constructor.
	39	*/
	40	protected EmptyOrderedMapIterator() {
	41	super();
	42	}
	43
	44	}

Line 0 Link Here

(-)extra/collections/iterators/AbstractEmptyIterator.java (+89 lines)
		1	/*
		2	* Copyright 2004 The Apache Software Foundation
		3	*
		4	* Licensed under the Apache License, Version 2.0 (the "License");
		5	* you may not use this file except in compliance with the License.
		6	* You may obtain a copy of the License at
		7	*
		8	* http://www.apache.org/licenses/LICENSE-2.0
		9	*
		10	* Unless required by applicable law or agreed to in writing, software
		11	* distributed under the License is distributed on an "AS IS" BASIS,
		12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		13	* See the License for the specific language governing permissions and
		14	* limitations under the License.
		15	*/
		16	package org.apache.taglibs.standard.extra.commons.collections.iterators;
		17
		18	import java.util.NoSuchElementException;
		19
		20	/**
		21	* Provides an implementation of an empty iterator.
		22	*
		23	* @since Commons Collections 3.1
		24	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
		25	*
		26	* @author Stephen Colebourne
		27	*/
		28	abstract class AbstractEmptyIterator {
		29
		30	/**
		31	* Constructor.
		32	*/
		33	protected AbstractEmptyIterator() {
		34	super();
		35	}
		36
		37	public boolean hasNext() {
		38	return false;
		39	}
		40
		41	public Object next() {
		42	throw new NoSuchElementException("Iterator contains no elements");
		43	}
		44
		45	public boolean hasPrevious() {
		46	return false;
		47	}
		48
		49	public Object previous() {
		50	throw new NoSuchElementException("Iterator contains no elements");
		51	}
		52
		53	public int nextIndex() {
		54	return 0;
		55	}
		56
		57	public int previousIndex() {
		58	return -1;
		59	}
		60
		61	public void add(Object obj) {
		62	throw new UnsupportedOperationException("add() not supported for empty Iterator");
		63	}
		64
65	public void set(Object obj) {
66	throw new IllegalStateException("Iterator contains no elements");
67	}
68
69	public void remove() {
70	throw new IllegalStateException("Iterator contains no elements");
71	}
72
73	public Object getKey() {
74	throw new IllegalStateException("Iterator contains no elements");
75	}
76
77	public Object getValue() {
78	throw new IllegalStateException("Iterator contains no elements");
79	}
80
81	public Object setValue(Object value) {
82	throw new IllegalStateException("Iterator contains no elements");
83	}
84
85	public void reset() {
86	// do nothing
87	}
88
89	}

Line 0 Link Here

(-)extra/collections/OrderedMapIterator.java (+45 lines)
	1	/*
	2	* Copyright 2001-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	/**
	19	* Defines an iterator that operates over an ordered <code>Map</code>.
	20	* <p>
	21	* This iterator allows both forward and reverse iteration through the map.
	22	*
	23	* @since Commons Collections 3.0
	24	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	25	*
	26	* @author Stephen Colebourne
	27	*/
	28	public interface OrderedMapIterator extends MapIterator, OrderedIterator {
	29
	30	/**
	31	* Checks to see if there is a previous entry that can be iterated to.
	32	*
	33	* @return <code>true</code> if the iterator has a previous element
	34	*/
	35	boolean hasPrevious();
	36
	37	/**
	38	* Gets the previous <em>key</em> from the <code>Map</code>.
	39	*
	40	* @return the previous key in the iteration
	41	* @throws java.util.NoSuchElementException if the iteration is finished
	42	*/
	43	Object previous();
	44
	45	}

Line 0 Link Here

(-)extra/collections/map/LRUMap.java (+391 lines)
		1	/*
		2	* Copyright 2001-2004 The Apache Software Foundation
		3	*
		4	* Licensed under the Apache License, Version 2.0 (the "License");
		5	* you may not use this file except in compliance with the License.
		6	* You may obtain a copy of the License at
		7	*
		8	* http://www.apache.org/licenses/LICENSE-2.0
		9	*
		10	* Unless required by applicable law or agreed to in writing, software
		11	* distributed under the License is distributed on an "AS IS" BASIS,
		12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		13	* See the License for the specific language governing permissions and
		14	* limitations under the License.
		15	*/
		16	package org.apache.taglibs.standard.extra.commons.collections.map;
		17
		18	import java.io.IOException;
		19	import java.io.ObjectInputStream;
		20	import java.io.ObjectOutputStream;
		21	import java.io.Serializable;
		22	import java.util.Map;
		23
		24	import org.apache.taglibs.standard.extra.commons.collections.BoundedMap;
		25
		26	/**
		27	* A <code>Map</code> implementation with a fixed maximum size which removes
		28	* the least recently used entry if an entry is added when full.
		29	* <p>
		30	* The least recently used algorithm works on the get and put operations only.
		31	* Iteration of any kind, including setting the value by iteration, does not
		32	* change the order. Queries such as containsKey and containsValue or access
		33	* via views also do not change the order.
		34	* <p>
		35	* The map implements <code>OrderedMap</code> and entries may be queried using
		36	* the bidirectional <code>OrderedMapIterator</code>. The order returned is
		37	* least recently used to most recently used. Iterators from map views can
		38	* also be cast to <code>OrderedIterator</code> if required.
		39	* <p>
		40	* All the available iterators can be reset back to the start by casting to
		41	* <code>ResettableIterator</code> and calling <code>reset()</code>.
		42	*
		43	* @since Commons Collections 3.0 (previously in main package v1.0)
		44	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
		45	*
		46	* @author James Strachan
		47	* @author Morgan Delagrange
		48	* @author Stephen Colebourne
		49	* @author Mike Pettypiece
		50	* @author Mario Ivankovits
		51	*/
		52	public class LRUMap
		53	extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
		54
		55	/** Serialisation version */
		56	static final long serialVersionUID = -612114643488955218L;
		57	/** Default maximum size */
		58	protected static final int DEFAULT_MAX_SIZE = 100;
		59
		60	/** Maximum size */
		61	private transient int maxSize;
		62	/** Scan behaviour */
		63	private boolean scanUntilRemovable;
		64
65	/**
66	* Constructs a new empty map with a maximum size of 100.
67	*/
68	public LRUMap() {
69	this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
70	}
71
72	/**
73	* Constructs a new, empty map with the specified maximum size.
74	*
75	* @param maxSize the maximum size of the map
76	* @throws IllegalArgumentException if the maximum size is less than one
77	*/
78	public LRUMap(int maxSize) {
79	this(maxSize, DEFAULT_LOAD_FACTOR);
80	}
81
82	/**
83	* Constructs a new, empty map with the specified maximum size.
84	*
85	* @param maxSize the maximum size of the map
86	* @param scanUntilRemovable scan until a removeable entry is found, default false
87	* @throws IllegalArgumentException if the maximum size is less than one
88	* @since Commons Collections 3.1
89	*/
90	public LRUMap(int maxSize, boolean scanUntilRemovable) {
91	this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
92	}
93
94	/**
95	* Constructs a new, empty map with the specified initial capacity and
96	* load factor.
97	*
98	* @param maxSize the maximum size of the map, -1 for no limit,
99	* @param loadFactor the load factor
100	* @throws IllegalArgumentException if the maximum size is less than one
101	* @throws IllegalArgumentException if the load factor is less than zero
102	*/
103	public LRUMap(int maxSize, float loadFactor) {
104	this(maxSize, loadFactor, false);
105	}
106
107	/**
108	* Constructs a new, empty map with the specified initial capacity and
109	* load factor.
110	*
111	* @param maxSize the maximum size of the map, -1 for no limit,
112	* @param loadFactor the load factor
113	* @param scanUntilRemovable scan until a removeable entry is found, default false
114	* @throws IllegalArgumentException if the maximum size is less than one
115	* @throws IllegalArgumentException if the load factor is less than zero
116	* @since Commons Collections 3.1
117	*/
118	public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) {
119	super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
120	if (maxSize < 1) {
121	throw new IllegalArgumentException("LRUMap max size must be greater than 0");
122	}
123	this.maxSize = maxSize;
124	this.scanUntilRemovable = scanUntilRemovable;
125	}
126
127	/**
128	* Constructor copying elements from another map.
129	* <p>
130	* The maximum size is set from the map's size.
131	*
132	* @param map the map to copy
133	* @throws NullPointerException if the map is null
134	* @throws IllegalArgumentException if the map is empty
135	*/
136	public LRUMap(Map map) {
137	this(map, false);
138	}
139
140	/**
141	* Constructor copying elements from another map.
142	* <p/>
143	* The maximum size is set from the map's size.
144	*
145	* @param map the map to copy
146	* @param scanUntilRemovable scan until a removeable entry is found, default false
147	* @throws NullPointerException if the map is null
148	* @throws IllegalArgumentException if the map is empty
149	* @since Commons Collections 3.1
150	*/
151	public LRUMap(Map map, boolean scanUntilRemovable) {
152	this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
153	putAll(map);
154	}
155
156	//-----------------------------------------------------------------------
157	/**
158	* Gets the value mapped to the key specified.
159	* <p>
160	* This operation changes the position of the key in the map to the
161	* most recently used position (first).
162	*
163	* @param key the key
164	* @return the mapped value, null if no match
165	*/
166	public Object get(Object key) {
167	LinkEntry entry = (LinkEntry) getEntry(key);
168	if (entry == null) {
169	return null;
170	}
171	moveToMRU(entry);
172	return entry.getValue();
173	}
174
175	//-----------------------------------------------------------------------
176	/**
177	* Moves an entry to the MRU position at the end of the list.
178	* <p>
179	* This implementation moves the updated entry to the end of the list.
180	*
181	* @param entry the entry to update
182	*/
183	protected void moveToMRU(LinkEntry entry) {
184	if (entry.after != header) {
185	modCount++;
186	// remove
187	entry.before.after = entry.after;
188	entry.after.before = entry.before;
189	// add first
190	entry.after = header;
191	entry.before = header.before;
192	header.before.after = entry;
193	header.before = entry;
194	}
195	}
196
197	/**
198	* Updates an existing key-value mapping.
199	* <p>
200	* This implementation moves the updated entry to the top of the list
201	* using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
202	*
203	* @param entry the entry to update
204	* @param newValue the new value to store
205	*/
206	protected void updateEntry(HashEntry entry, Object newValue) {
207	moveToMRU((LinkEntry) entry); // handles modCount
208	entry.setValue(newValue);
209	}
210
211	/**
212	* Adds a new key-value mapping into this map.
213	* <p>
214	* This implementation checks the LRU size and determines whether to
215	* discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
216	* <p>
217	* From Commons Collections 3.1 this method uses {@link #isFull()} rather
218	* than accessing <code>size</code> and <code>maxSize</code> directly.
219	* It also handles the scanUntilRemovable functionality.
220	*
221	* @param hashIndex the index into the data array to store at
222	* @param hashCode the hash code of the key to add
223	* @param key the key to add
224	* @param value the value to add
225	*/
226	protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
227	if (isFull()) {
228	LinkEntry reuse = header.after;
229	boolean removeLRUEntry = false;
230	if (scanUntilRemovable) {
231	while (reuse != header) {
232	if (removeLRU(reuse)) {
233	removeLRUEntry = true;
234	break;
235	}
236	reuse = reuse.after;
237	}
238	} else {
239	removeLRUEntry = removeLRU(reuse);
240	}
241
242	if (removeLRUEntry) {
243	reuseMapping(reuse, hashIndex, hashCode, key, value);
244	} else {
245	super.addMapping(hashIndex, hashCode, key, value);
246	}
247	} else {
248	super.addMapping(hashIndex, hashCode, key, value);
249	}
250	}
251
252	/**
253	* Reuses an entry by removing it and moving it to a new place in the map.
254	* <p>
255	* This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
256	*
257	* @param entry the entry to reuse
258	* @param hashIndex the index into the data array to store at
259	* @param hashCode the hash code of the key to add
260	* @param key the key to add
261	* @param value the value to add
262	*/
263	protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
264	// find the entry before the entry specified in the hash table
265	// remember that the parameters (except the first) refer to the new entry,
266	// not the old one
267	int removeIndex = hashIndex(entry.hashCode, data.length);
268	HashEntry loop = data[removeIndex];
269	HashEntry previous = null;
270	while (loop != entry) {
271	previous = loop;
272	loop = loop.next;
273	}
274
275	// reuse the entry
276	modCount++;
277	removeEntry(entry, removeIndex, previous);
278	reuseEntry(entry, hashIndex, hashCode, key, value);
279	addEntry(entry, hashIndex);
280	}
281
282	/**
283	* Subclass method to control removal of the least recently used entry from the map.
284	* <p>
285	* This method exists for subclasses to override. A subclass may wish to
286	* provide cleanup of resources when an entry is removed. For example:
287	* <pre>
288	* protected boolean removeLRU(LinkEntry entry) {
289	* releaseResources(entry.getValue()); // release resources held by entry
290	* return true; // actually delete entry
291	* }
292	* </pre>
293	* <p>
294	* Alternatively, a subclass may choose to not remove the entry or selectively
295	* keep certain LRU entries. For example:
296	* <pre>
297	* protected boolean removeLRU(LinkEntry entry) {
298	* if (entry.getKey().toString().startsWith("System.")) {
299	* return false; // entry not removed from LRUMap
300	* } else {
301	* return true; // actually delete entry
302	* }
303	* }
304	* </pre>
305	* The effect of returning false is dependent on the scanUntilRemovable flag.
306	* If the flag is true, the next LRU entry will be passed to this method and so on
307	* until one returns false and is removed, or every entry in the map has been passed.
308	* If the scanUntilRemovable flag is false, the map will exceed the maximum size.
309	* <p>
310	* NOTE: Commons Collections 3.0 passed the wrong entry to this method.
311	* This is fixed in version 3.1 onwards.
312	*
313	* @param entry the entry to be removed
314	*/
315	protected boolean removeLRU(LinkEntry entry) {
316	return true;
317	}
318
319	//-----------------------------------------------------------------------
320	/**
321	* Returns true if this map is full and no new mappings can be added.
322	*
323	* @return <code>true</code> if the map is full
324	*/
325	public boolean isFull() {
326	return (size >= maxSize);
327	}
328
329	/**
330	* Gets the maximum size of the map (the bound).
331	*
332	* @return the maximum number of elements the map can hold
333	*/
334	public int maxSize() {
335	return maxSize;
336	}
337
338	/**
339	* Whether this LRUMap will scan until a removable entry is found when the
340	* map is full.
341	*
342	* @return true if this map scans
343	* @since Commons Collections 3.1
344	*/
345	public boolean isScanUntilRemovable() {
346	return scanUntilRemovable;
347	}
348
349	//-----------------------------------------------------------------------
350	/**
351	* Clones the map without cloning the keys or values.
352	*
353	* @return a shallow clone
354	*/
355	public Object clone() {
356	return super.clone();
357	}
358
359	/**
360	* Write the map out using a custom routine.
361	*/
362	private void writeObject(ObjectOutputStream out) throws IOException {
363	out.defaultWriteObject();
364	doWriteObject(out);
365	}
366
367	/**
368	* Read the map in using a custom routine.
369	*/
370	private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
371	in.defaultReadObject();
372	doReadObject(in);
373	}
374
375	/**
376	* Writes the data necessary for <code>put()</code> to work in deserialization.
377	*/
378	protected void doWriteObject(ObjectOutputStream out) throws IOException {
379	out.writeInt(maxSize);
380	super.doWriteObject(out);
381	}
382
383	/**
384	* Reads the data necessary for <code>put()</code> to work in the superclass.
385	*/
386	protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
387	maxSize = in.readInt();
388	super.doReadObject(in);
389	}
390
391	}

Line 0 Link Here

(-)extra/collections/map/AbstractLinkedMap.java (+608 lines)
		1	/*
		2	* Copyright 2003-2004 The Apache Software Foundation
		3	*
		4	* Licensed under the Apache License, Version 2.0 (the "License");
		5	* you may not use this file except in compliance with the License.
		6	* You may obtain a copy of the License at
		7	*
		8	* http://www.apache.org/licenses/LICENSE-2.0
		9	*
		10	* Unless required by applicable law or agreed to in writing, software
		11	* distributed under the License is distributed on an "AS IS" BASIS,
		12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		13	* See the License for the specific language governing permissions and
		14	* limitations under the License.
		15	*/
		16	package org.apache.taglibs.standard.extra.commons.collections.map;
		17
		18	import java.util.ConcurrentModificationException;
		19	import java.util.Iterator;
		20	import java.util.Map;
		21	import java.util.NoSuchElementException;
		22
		23	import org.apache.taglibs.standard.extra.commons.collections.MapIterator;
		24	import org.apache.taglibs.standard.extra.commons.collections.OrderedIterator;
		25	import org.apache.taglibs.standard.extra.commons.collections.OrderedMap;
		26	import org.apache.taglibs.standard.extra.commons.collections.OrderedMapIterator;
		27	import org.apache.taglibs.standard.extra.commons.collections.ResettableIterator;
		28	import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedIterator;
		29	import org.apache.taglibs.standard.extra.commons.collections.iterators.EmptyOrderedMapIterator;
		30
		31	/**
		32	* An abstract implementation of a hash-based map that links entries to create an
		33	* ordered map and which provides numerous points for subclasses to override.
		34	* <p>
		35	* This class implements all the features necessary for a subclass linked
		36	* hash-based map. Key-value entries are stored in instances of the
		37	* <code>LinkEntry</code> class which can be overridden and replaced.
		38	* The iterators can similarly be replaced, without the need to replace the KeySet,
		39	* EntrySet and Values view classes.
		40	* <p>
		41	* Overridable methods are provided to change the default hashing behaviour, and
		42	* to change how entries are added to and removed from the map. Hopefully, all you
		43	* need for unusual subclasses is here.
		44	* <p>
		45	* This implementation maintains order by original insertion, but subclasses
		46	* may work differently. The <code>OrderedMap</code> interface is implemented
		47	* to provide access to bidirectional iteration and extra convenience methods.
		48	* <p>
		49	* The <code>orderedMapIterator()</code> method provides direct access to a
		50	* bidirectional iterator. The iterators from the other views can also be cast
		51	* to <code>OrderedIterator</code> if required.
		52	* <p>
		53	* All the available iterators can be reset back to the start by casting to
		54	* <code>ResettableIterator</code> and calling <code>reset()</code>.
		55	* <p>
		56	* The implementation is also designed to be subclassed, with lots of useful
		57	* methods exposed.
		58	*
		59	* @since Commons Collections 3.0
		60	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
		61	*
		62	* @author java util LinkedHashMap
		63	* @author Stephen Colebourne
		64	*/
65	public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap {
66
67	/** Header in the linked list */
68	protected transient LinkEntry header;
69
70	/**
71	* Constructor only used in deserialization, do not use otherwise.
72	*/
73	protected AbstractLinkedMap() {
74	super();
75	}
76
77	/**
78	* Constructor which performs no validation on the passed in parameters.
79	*
80	* @param initialCapacity the initial capacity, must be a power of two
81	* @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
82	* @param threshold the threshold, must be sensible
83	*/
84	protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold) {
85	super(initialCapacity, loadFactor, threshold);
86	}
87
88	/**
89	* Constructs a new, empty map with the specified initial capacity.
90	*
91	* @param initialCapacity the initial capacity
92	* @throws IllegalArgumentException if the initial capacity is less than one
93	*/
94	protected AbstractLinkedMap(int initialCapacity) {
95	super(initialCapacity);
96	}
97
98	/**
99	* Constructs a new, empty map with the specified initial capacity and
100	* load factor.
101	*
102	* @param initialCapacity the initial capacity
103	* @param loadFactor the load factor
104	* @throws IllegalArgumentException if the initial capacity is less than one
105	* @throws IllegalArgumentException if the load factor is less than zero
106	*/
107	protected AbstractLinkedMap(int initialCapacity, float loadFactor) {
108	super(initialCapacity, loadFactor);
109	}
110
111	/**
112	* Constructor copying elements from another map.
113	*
114	* @param map the map to copy
115	* @throws NullPointerException if the map is null
116	*/
117	protected AbstractLinkedMap(Map map) {
118	super(map);
119	}
120
121	/**
122	* Initialise this subclass during construction.
123	*/
124	protected void init() {
125	header = new LinkEntry(null, -1, null, null);
126	header.before = header.after = header;
127	}
128
129	//-----------------------------------------------------------------------
130	/**
131	* Checks whether the map contains the specified value.
132	*
133	* @param value the value to search for
134	* @return true if the map contains the value
135	*/
136	public boolean containsValue(Object value) {
137	// override uses faster iterator
138	if (value == null) {
139	for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
140	if (entry.getValue() == null) {
141	return true;
142	}
143	}
144	} else {
145	for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
146	if (isEqualValue(value, entry.getValue())) {
147	return true;
148	}
149	}
150	}
151	return false;
152	}
153
154	/**
155	* Clears the map, resetting the size to zero and nullifying references
156	* to avoid garbage collection issues.
157	*/
158	public void clear() {
159	// override to reset the linked list
160	super.clear();
161	header.before = header.after = header;
162	}
163
164	//-----------------------------------------------------------------------
165	/**
166	* Gets the first key in the map, which is the most recently inserted.
167	*
168	* @return the most recently inserted key
169	*/
170	public Object firstKey() {
171	if (size == 0) {
172	throw new NoSuchElementException("Map is empty");
173	}
174	return header.after.getKey();
175	}
176
177	/**
178	* Gets the last key in the map, which is the first inserted.
179	*
180	* @return the eldest key
181	*/
182	public Object lastKey() {
183	if (size == 0) {
184	throw new NoSuchElementException("Map is empty");
185	}
186	return header.before.getKey();
187	}
188
189	/**
190	* Gets the next key in sequence.
191	*
192	* @param key the key to get after
193	* @return the next key
194	*/
195	public Object nextKey(Object key) {
196	LinkEntry entry = (LinkEntry) getEntry(key);
197	return (entry == null \|\| entry.after == header ? null : entry.after.getKey());
198	}
199
200	/**
201	* Gets the previous key in sequence.
202	*
203	* @param key the key to get before
204	* @return the previous key
205	*/
206	public Object previousKey(Object key) {
207	LinkEntry entry = (LinkEntry) getEntry(key);
208	return (entry == null \|\| entry.before == header ? null : entry.before.getKey());
209	}
210
211	//-----------------------------------------------------------------------
212	/**
213	* Gets the key at the specified index.
214	*
215	* @param index the index to retrieve
216	* @return the key at the specified index
217	* @throws IndexOutOfBoundsException if the index is invalid
218	*/
219	protected LinkEntry getEntry(int index) {
220	if (index < 0) {
221	throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
222	}
223	if (index >= size) {
224	throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
225	}
226	LinkEntry entry;
227	if (index < (size / 2)) {
228	// Search forwards
229	entry = header.after;
230	for (int currentIndex = 0; currentIndex < index; currentIndex++) {
231	entry = entry.after;
232	}
233	} else {
234	// Search backwards
235	entry = header;
236	for (int currentIndex = size; currentIndex > index; currentIndex--) {
237	entry = entry.before;
238	}
239	}
240	return entry;
241	}
242
243	/**
244	* Adds an entry into this map, maintaining insertion order.
245	* <p>
246	* This implementation adds the entry to the data storage table and
247	* to the end of the linked list.
248	*
249	* @param entry the entry to add
250	* @param hashIndex the index into the data array to store at
251	*/
252	protected void addEntry(HashEntry entry, int hashIndex) {
253	LinkEntry link = (LinkEntry) entry;
254	link.after = header;
255	link.before = header.before;
256	header.before.after = link;
257	header.before = link;
258	data[hashIndex] = entry;
259	}
260
261	/**
262	* Creates an entry to store the data.
263	* <p>
264	* This implementation creates a new LinkEntry instance.
265	*
266	* @param next the next entry in sequence
267	* @param hashCode the hash code to use
268	* @param key the key to store
269	* @param value the value to store
270	* @return the newly created entry
271	*/
272	protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
273	return new LinkEntry(next, hashCode, key, value);
274	}
275
276	/**
277	* Removes an entry from the map and the linked list.
278	* <p>
279	* This implementation removes the entry from the linked list chain, then
280	* calls the superclass implementation.
281	*
282	* @param entry the entry to remove
283	* @param hashIndex the index into the data structure
284	* @param previous the previous entry in the chain
285	*/
286	protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
287	LinkEntry link = (LinkEntry) entry;
288	link.before.after = link.after;
289	link.after.before = link.before;
290	link.after = null;
291	link.before = null;
292	super.removeEntry(entry, hashIndex, previous);
293	}
294
295	//-----------------------------------------------------------------------
296	/**
297	* Gets the <code>before</code> field from a <code>LinkEntry</code>.
298	* Used in subclasses that have no visibility of the field.
299	*
300	* @param entry the entry to query, must not be null
301	* @return the <code>before</code> field of the entry
302	* @throws NullPointerException if the entry is null
303	* @since Commons Collections 3.1
304	*/
305	protected LinkEntry entryBefore(LinkEntry entry) {
306	return entry.before;
307	}
308
309	/**
310	* Gets the <code>after</code> field from a <code>LinkEntry</code>.
311	* Used in subclasses that have no visibility of the field.
312	*
313	* @param entry the entry to query, must not be null
314	* @return the <code>after</code> field of the entry
315	* @throws NullPointerException if the entry is null
316	* @since Commons Collections 3.1
317	*/
318	protected LinkEntry entryAfter(LinkEntry entry) {
319	return entry.after;
320	}
321
322	//-----------------------------------------------------------------------
323	/**
324	* Gets an iterator over the map.
325	* Changes made to the iterator affect this map.
326	* <p>
327	* A MapIterator returns the keys in the map. It also provides convenient
328	* methods to get the key and value, and set the value.
329	* It avoids the need to create an entrySet/keySet/values object.
330	*
331	* @return the map iterator
332	*/
333	public MapIterator mapIterator() {
334	if (size == 0) {
335	return EmptyOrderedMapIterator.INSTANCE;
336	}
337	return new LinkMapIterator(this);
338	}
339
340	/**
341	* Gets a bidirectional iterator over the map.
342	* Changes made to the iterator affect this map.
343	* <p>
344	* A MapIterator returns the keys in the map. It also provides convenient
345	* methods to get the key and value, and set the value.
346	* It avoids the need to create an entrySet/keySet/values object.
347	*
348	* @return the map iterator
349	*/
350	public OrderedMapIterator orderedMapIterator() {
351	if (size == 0) {
352	return EmptyOrderedMapIterator.INSTANCE;
353	}
354	return new LinkMapIterator(this);
355	}
356
357	/**
358	* MapIterator implementation.
359	*/
360	protected static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
361
362	protected LinkMapIterator(AbstractLinkedMap parent) {
363	super(parent);
364	}
365
366	public Object next() {
367	return super.nextEntry().getKey();
368	}
369
370	public Object previous() {
371	return super.previousEntry().getKey();
372	}
373
374	public Object getKey() {
375	HashEntry current = currentEntry();
376	if (current == null) {
377	throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
378	}
379	return current.getKey();
380	}
381
382	public Object getValue() {
383	HashEntry current = currentEntry();
384	if (current == null) {
385	throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
386	}
387	return current.getValue();
388	}
389
390	public Object setValue(Object value) {
391	HashEntry current = currentEntry();
392	if (current == null) {
393	throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
394	}
395	return current.setValue(value);
396	}
397	}
398
399	//-----------------------------------------------------------------------
400	/**
401	* Creates an entry set iterator.
402	* Subclasses can override this to return iterators with different properties.
403	*
404	* @return the entrySet iterator
405	*/
406	protected Iterator createEntrySetIterator() {
407	if (size() == 0) {
408	return EmptyOrderedIterator.INSTANCE;
409	}
410	return new EntrySetIterator(this);
411	}
412
413	/**
414	* EntrySet iterator.
415	*/
416	protected static class EntrySetIterator extends LinkIterator {
417
418	protected EntrySetIterator(AbstractLinkedMap parent) {
419	super(parent);
420	}
421
422	public Object next() {
423	return super.nextEntry();
424	}
425
426	public Object previous() {
427	return super.previousEntry();
428	}
429	}
430
431	//-----------------------------------------------------------------------
432	/**
433	* Creates a key set iterator.
434	* Subclasses can override this to return iterators with different properties.
435	*
436	* @return the keySet iterator
437	*/
438	protected Iterator createKeySetIterator() {
439	if (size() == 0) {
440	return EmptyOrderedIterator.INSTANCE;
441	}
442	return new KeySetIterator(this);
443	}
444
445	/**
446	* KeySet iterator.
447	*/
448	protected static class KeySetIterator extends EntrySetIterator {
449
450	protected KeySetIterator(AbstractLinkedMap parent) {
451	super(parent);
452	}
453
454	public Object next() {
455	return super.nextEntry().getKey();
456	}
457
458	public Object previous() {
459	return super.previousEntry().getKey();
460	}
461	}
462
463	//-----------------------------------------------------------------------
464	/**
465	* Creates a values iterator.
466	* Subclasses can override this to return iterators with different properties.
467	*
468	* @return the values iterator
469	*/
470	protected Iterator createValuesIterator() {
471	if (size() == 0) {
472	return EmptyOrderedIterator.INSTANCE;
473	}
474	return new ValuesIterator(this);
475	}
476
477	/**
478	* Values iterator.
479	*/
480	protected static class ValuesIterator extends LinkIterator {
481
482	protected ValuesIterator(AbstractLinkedMap parent) {
483	super(parent);
484	}
485
486	public Object next() {
487	return super.nextEntry().getValue();
488	}
489
490	public Object previous() {
491	return super.previousEntry().getValue();
492	}
493	}
494
495	//-----------------------------------------------------------------------
496	/**
497	* LinkEntry that stores the data.
498	* <p>
499	* If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
500	* then you will not be able to access the protected fields.
501	* The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> exist
502	* to provide the necessary access.
503	*/
504	protected static class LinkEntry extends HashEntry {
505	/** The entry before this one in the order */
506	protected LinkEntry before;
507	/** The entry after this one in the order */
508	protected LinkEntry after;
509
510	/**
511	* Constructs a new entry.
512	*
513	* @param next the next entry in the hash bucket sequence
514	* @param hashCode the hash code
515	* @param key the key
516	* @param value the value
517	*/
518	protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
519	super(next, hashCode, key, value);
520	}
521	}
522
523	/**
524	* Base Iterator that iterates in link order.
525	*/
526	protected static abstract class LinkIterator
527	implements OrderedIterator, ResettableIterator {
528
529	/** The parent map */
530	protected final AbstractLinkedMap parent;
531	/** The current (last returned) entry */
532	protected LinkEntry last;
533	/** The next entry */
534	protected LinkEntry next;
535	/** The modification count expected */
536	protected int expectedModCount;
537
538	protected LinkIterator(AbstractLinkedMap parent) {
539	super();
540	this.parent = parent;
541	this.next = parent.header.after;
542	this.expectedModCount = parent.modCount;
543	}
544
545	public boolean hasNext() {
546	return (next != parent.header);
547	}
548
549	public boolean hasPrevious() {
550	return (next.before != parent.header);
551	}
552
553	protected LinkEntry nextEntry() {
554	if (parent.modCount != expectedModCount) {
555	throw new ConcurrentModificationException();
556	}
557	if (next == parent.header) {
558	throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
559	}
560	last = next;
561	next = next.after;
562	return last;
563	}
564
565	protected LinkEntry previousEntry() {
566	if (parent.modCount != expectedModCount) {
567	throw new ConcurrentModificationException();
568	}
569	LinkEntry previous = next.before;
570	if (previous == parent.header) {
571	throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
572	}
573	next = previous;
574	last = previous;
575	return last;
576	}
577
578	protected LinkEntry currentEntry() {
579	return last;
580	}
581
582	public void remove() {
583	if (last == null) {
584	throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
585	}
586	if (parent.modCount != expectedModCount) {
587	throw new ConcurrentModificationException();
588	}
589	parent.remove(last.getKey());
590	last = null;
591	expectedModCount = parent.modCount;
592	}
593
594	public void reset() {
595	last = null;
596	next = parent.header.after;
597	}
598
599	public String toString() {
600	if (last != null) {
601	return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
602	} else {
603	return "Iterator[]";
604	}
605	}
606	}
607
608	}

Line 0 Link Here

(-)extra/collections/BoundedMap.java (+48 lines)
	1	/*
	2	* Copyright 2003-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	import java.util.Map;
	19
	20	/**
	21	* Defines a map that is bounded in size.
	22	* <p>
	23	* The size of the map can vary, but it can never exceed a preset
	24	* maximum number of elements. This interface allows the querying of details
	25	* associated with the maximum number of elements.
	26	*
	27	* @since Commons Collections 3.0
	28	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	29	*
	30	* @author Stephen Colebourne
	31	*/
	32	public interface BoundedMap extends Map {
	33
	34	/**
	35	* Returns true if this map is full and no new elements can be added.
	36	*
	37	* @return <code>true</code> if the map is full
	38	*/
	39	boolean isFull();
	40
	41	/**
	42	* Gets the maximum size of the map (the bound).
	43	*
	44	* @return the maximum number of elements the map can hold
	45	*/
	46	int maxSize();
	47
	48	}

Line 0 Link Here

(-)extra/collections/OrderedIterator.java (+47 lines)
	1	/*
	2	* Copyright 2003-2004 The Apache Software Foundation
	3	*
	4	* Licensed under the Apache License, Version 2.0 (the "License");
	5	* you may not use this file except in compliance with the License.
	6	* You may obtain a copy of the License at
	7	*
	8	* http://www.apache.org/licenses/LICENSE-2.0
	9	*
	10	* Unless required by applicable law or agreed to in writing, software
	11	* distributed under the License is distributed on an "AS IS" BASIS,
	12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	13	* See the License for the specific language governing permissions and
	14	* limitations under the License.
	15	*/
	16	package org.apache.taglibs.standard.extra.commons.collections;
	17
	18	import java.util.Iterator;
	19
	20	/**
	21	* Defines an iterator that operates over an ordered collection.
	22	* <p>
	23	* This iterator allows both forward and reverse iteration through the collection.
	24	*
	25	* @since Commons Collections 3.0
	26	* @version $Revision: 218351 $ $Date: 2004-10-20 17:58:23 -0700 (Wed, 20 Oct 2004) $
	27	*
	28	* @author Stephen Colebourne
	29	*/
	30	public interface OrderedIterator extends Iterator {
	31
	32	/**
	33	* Checks to see if there is a previous element that can be iterated to.
	34	*
	35	* @return <code>true</code> if the iterator has a previous element
	36	*/
	37	boolean hasPrevious();
	38
	39	/**
	40	* Gets the previous element from the collection.
	41	*
	42	* @return the previous element in the iteration
	43	* @throws java.util.NoSuchElementException if the iteration is finished
	44	*/
	45	Object previous();
	46
	47	}