//--------------------------------------------------------------------------
// Copyright (c) 1998-2004, Drew Davidson and Luke Blanshard
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// Neither the name of the Drew Davidson nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
// OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
// AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//--------------------------------------------------------------------------
package ognl;
import java.util.*;
/**
* A Map that uses ints as the keys.
* <p>Use just like any java.util.Map, except that the keys must be ints.
* This is much faster than creating a new Integer for each access.</p>
* <p>For non-Map access (faster) use the put(int, Object) method.</p>
* <p>This class implements Map for convenience, but this is not the most
* efficient usage.</p>
* @see java.util.HashMap
* @see java.util.Map
*/
public class
IntHashMap extends
Object implements
Map
{
private
Entry table[];
private int
count;
private int
threshold;
private float
loadFactor;
/*===================================================================
Private static classes
===================================================================*/
private static class
IntHashMapIterator implements
Iterator
{
boolean
keys;
int
index;
Entry table[];
Entry entry;
IntHashMapIterator(
Entry table[], boolean
keys)
{
super();
this.
table =
table;
this.
keys =
keys;
this.
index =
table.length;
}
/*===================================================================
Iterator interface
===================================================================*/
public boolean
hasNext()
{
if (
entry != null) {
return true;
}
while (
index-- > 0) {
if ((
entry =
table[
index]) != null) {
return true;
}
}
return false;
}
public
Object next()
{
if (
entry == null) {
while ((
index-- > 0) && ((
entry =
table[
index]) == null)) {
/* do nothing */
}
}
if (
entry != null) {
Entry e =
entry;
entry =
e.
next;
return
keys ? new
Integer(
e.
key) :
e.
value;
}
throw new
NoSuchElementException("IntHashMapIterator");
}
public void
remove()
{
throw new
UnsupportedOperationException("remove");
}
}
/*===================================================================
Public static classes
===================================================================*/
public static class
Entry extends
Object
{
int
hash;
int
key;
Object value;
Entry next;
public
Entry()
{
super();
}
}
/*===================================================================
Constructors
===================================================================*/
public
IntHashMap(int
initialCapacity, float
loadFactor)
{
super();
if (
initialCapacity <= 0 ||
loadFactor <= 0.0) {
throw new
IllegalArgumentException();
}
this.
loadFactor =
loadFactor;
table = new
Entry[
initialCapacity];
threshold = (int)(
initialCapacity *
loadFactor);
}
public
IntHashMap(int
initialCapacity)
{
this(
initialCapacity, 0.75f);
}
public
IntHashMap()
{
this(101, 0.75f);
}
/*===================================================================
Protected methods
===================================================================*/
protected void
rehash()
{
int
oldCapacity =
table.length;
Entry oldTable[] =
table;
int
newCapacity =
oldCapacity * 2 + 1;
Entry newTable[] = new
Entry[
newCapacity];
threshold = (int)(
newCapacity *
loadFactor);
table =
newTable;
for (int
i =
oldCapacity ;
i-- > 0 ;) {
for (
Entry old =
oldTable[
i] ;
old != null;) {
Entry e =
old;
int
index = (
e.
hash & 0x7FFFFFFF ) %
newCapacity;
old =
old.
next;
e.
next =
newTable[
index];
newTable[
index] =
e;
}
}
}
/*===================================================================
Public methods
===================================================================*/
public final boolean
containsKey(int
key)
{
int
index = (
key & 0x7FFFFFFF) %
table.length;
for (
Entry e =
table[
index] ;
e != null ;
e =
e.
next) {
if ((
e.
hash ==
key) && (
e.
key ==
key)) {
return true;
}
}
return false;
}
public final
Object get(int
key)
{
int
index = (
key & 0x7FFFFFFF) %
table.length;
for (
Entry e =
table[
index] ;
e != null ;
e =
e.
next) {
if ((
e.
hash ==
key) && (
e.
key ==
key)) {
return
e.
value;
}
}
return null;
}
public final
Object put(int
key,
Object value)
{
int
index = (
key & 0x7FFFFFFF ) %
table.length;
if (
value == null) {
throw new
IllegalArgumentException();
}
for (
Entry e =
table[
index] ;
e != null ;
e =
e.
next) {
if ((
e.
hash ==
key) && (
e.
key ==
key)) {
Object old =
e.
value;
e.
value =
value;
return
old;
}
}
if (
count >=
threshold) {
// Rehash the table if the threshold is exceeded.
rehash();
return
put(
key,
value);
}
Entry e = new
Entry();
e.
hash =
key;
e.
key =
key;
e.
value =
value;
e.
next =
table[
index];
table[
index] =
e;
++
count;
return null;
}
public final
Object remove(int
key)
{
int
index = (
key & 0x7FFFFFFF) %
table.length;
for (
Entry e =
table[
index],
prev = null ;
e != null ;
prev =
e,
e =
e.
next) {
if ((
e.
hash ==
key) && (
e.
key ==
key)) {
if (
prev != null ) {
prev.
next =
e.
next;
} else {
table[
index] =
e.
next;
}
--
count;
return
e.
value;
}
}
return null;
}
/*===================================================================
Map interface
===================================================================*/
public int
size()
{
return
count;
}
public boolean
isEmpty()
{
return
count == 0;
}
public
Object get(
Object key)
{
if (!(
key instanceof
Number)) {
throw new
IllegalArgumentException("key is not an Number subclass");
}
return
get(((
Number)
key).
intValue());
}
public
Object put(
Object key,
Object value)
{
if (!(
key instanceof
Number)) {
throw new
IllegalArgumentException( "key cannot be null" );
}
return
put(((
Number)
key).
intValue(),
value );
}
public void
putAll(
Map otherMap)
{
for (
Iterator it =
otherMap.
keySet().
iterator();
it.
hasNext();) {
Object k =
it.
next();
put(
k,
otherMap.
get(
k));
}
}
public
Object remove(
Object key)
{
if (!(
key instanceof
Number)) {
throw new
IllegalArgumentException("key cannot be null");
}
return
remove(((
Number)
key).
intValue());
}
public void
clear()
{
Entry tab[] =
table;
for (int
index =
tab.length; --
index >= 0;) {
tab[
index] = null;
}
count = 0;
}
public boolean
containsKey(
Object key)
{
if (!(
key instanceof
Number)) {
throw new
InternalError( "key is not an Number subclass" );
}
return
containsKey(((
Number)
key).
intValue());
}
public boolean
containsValue(
Object value)
{
Entry tab[] =
table;
if (
value == null) {
throw new
IllegalArgumentException();
}
for (int
i =
tab.length ;
i-- > 0;) {
for (
Entry e =
tab[
i] ;
e != null ;
e =
e.
next ) {
if (
e.
value.
equals(
value)) {
return true;
}
}
}
return false;
}
public
Set keySet()
{
Set result = new
HashSet();
for (
Iterator it = new
IntHashMapIterator(
table, true);
it.
hasNext();) {
result.
add(
it.
next());
}
return
result;
}
public
Collection values()
{
List result = new
ArrayList();
for (
Iterator it = new
IntHashMapIterator(
table, false);
it.
hasNext();) {
result.
add(
it.
next());
}
return
result;
}
public
Set entrySet()
{
throw new
UnsupportedOperationException("entrySet");
}
}