mdh.hephaestus2.containers
Class SparseArray

java.lang.Object
  |
  +--mdh.hephaestus2.containers.SparseArray
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
IntHash

public abstract class SparseArray
extends Object
implements Serializable

A SparseArray is a hashtable using an int key rather than an object.

Author:
Copyright © 2000 by Mark Hughes <kamikaze@kuoi.asui.uidaho.edu>
See Also:
Serialized Form

Field Summary
static int DEFAULT_CAPACITY
          The default capacity, 13.
static float DEFAULT_LOADFACTOR
          The default for loadFactor, 0.75.
static int PROBABLY_NOT_FOUND
          constant used by indexOf()
 
Constructor Summary
SparseArray()
          Creates a new SparseArray with a default size of DEFAULT_CAPACITY and loadFactor of DEFAULT_LOADFACTOR.
SparseArray(int capacity)
          Creates a new SparseArray with a given capacity and default loadFactor of DEFAULT_LOADFACTOR.
SparseArray(int capacity, float loadFactor)
          Creates an SparseArray.
 
Method Summary
abstract  void clear()
          erase all contents of the SparseArray.
abstract  boolean contains(Object value)
           
abstract  boolean containsKey(int key)
           
abstract  Enumeration elements()
          Returns an Enumeration of the values in this SparseArray
abstract  Object[] elementsArray()
          Produces an unsorted Object[] array of the elements stored herein, or a zero-length array if it is empty.
abstract  Enumeration elementsCopy()
          Returns an Enumeration of the values in this SparseArray, using a copy of the arrays, so you can continue to manipulate the SparseArray while enumerating.
abstract  void ensureCapacity(int newcap)
          Resizes the hash bucket to hold at least newcap entries, before the loadFactor.
abstract  Object get(int key)
           
 boolean getBoolean(int key)
          As get(), but tries to cast it to Boolean and then get the booleanValue.
 byte getByte(int key)
           
 int getCapacity()
           
 char getChar(int key)
          As get(), but tries to cast it to Character and then get the charValue.
 double getDouble(int key)
           
 float getFloat(int key)
           
 int getInt(int key)
          As get(), but tries to cast it to Number and then get the intValue.
 float getLoadFactor()
           
 long getLong(int key)
           
 short getShort(int key)
           
 String getString(int key)
           
abstract  int indexOf(Object find)
          Finds a value that matches 'find' and returns the key.
 boolean isEmpty()
           
abstract  IntEnumeration keys()
          Returns an Enumeration of the keys in this SparseArray, each wrapped in Integers.
abstract  int[] keysArray()
          Produces an unsorted int[] array of the keys stored herein, or a zero-length array if the SparseArray is empty.
abstract  IntEnumeration keysCopy()
          Returns an Enumeration of the keys in this SparseArray, using a copy of the arrays, so you can continue to manipulate the SparseArray while enumerating.
 void put(int key, boolean value)
           
 void put(int key, byte value)
           
 void put(int key, char value)
           
 void put(int key, double value)
           
 void put(int key, float value)
           
 void put(int key, int value)
          Convenience method to store int values, after putting them in the wrapper.
 void put(int key, long value)
           
abstract  void put(int key, Object value)
          Assigns the 'value' to the entry at 'key'.
 void put(int key, short value)
           
abstract  Object remove(int key)
          Removes the entry at 'key', and returns the former value.
 void set(int key, boolean value)
          Deprecated.  
 void set(int key, byte value)
          Deprecated.  
 void set(int key, char value)
          Deprecated.  
 void set(int key, double value)
          Deprecated.  
 void set(int key, float value)
          Deprecated.  
 void set(int key, int value)
          Deprecated.  
 void set(int key, long value)
          Deprecated.  
 void set(int key, Object value)
          Deprecated.  
 void set(int key, short value)
          Deprecated.  
 void setLoadFactor(float lf)
           
 int size()
           
 String toString()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

PROBABLY_NOT_FOUND

public static final int PROBABLY_NOT_FOUND
constant used by indexOf()

See Also:
Constant Field Values

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY
The default capacity, 13.

See Also:
Constant Field Values

DEFAULT_LOADFACTOR

public static final float DEFAULT_LOADFACTOR
The default for loadFactor, 0.75.

See Also:
Constant Field Values
Constructor Detail

SparseArray

public SparseArray()
Creates a new SparseArray with a default size of DEFAULT_CAPACITY and loadFactor of DEFAULT_LOADFACTOR.


SparseArray

public SparseArray(int capacity)
Creates a new SparseArray with a given capacity and default loadFactor of DEFAULT_LOADFACTOR.


SparseArray

public SparseArray(int capacity,
                   float loadFactor)
Creates an SparseArray. When subclassing, note that this may alter the capacity and load factors given, so your constructors should look like:
public FooHash(int capacity, float loadFactor)
{
    super(capacity, loadFactor);
    bucket_ = new Foo[ capacity_ ];
}

public FooHash(int capacity)
{
    this(capacity, DEFAULT_LOADFACTOR);
}

public FooHash()
{
    this(DEFAULT_CAPACITY, DEFAULT_LOADFACTOR);
}

    

Parameters:
capacity - The number of spaces allocated to the hash, which should be (expected size / loadFactor). Capacity should be a prime number for best efficiency. The minimum capacity is 5; if you give a smaller value, it is raised to 5.
loadFactor - The proportion of data to spaces that is allowed before the capacity is incresed. It cannot be less than 0.1 or more than 0.9. The higher the loadFactor, the more likely the worst-case performance will be, approaching O(n). The lower it is, the more memory you'll use and the faster it'll go, approaching O(1). 0.75 is a good default for most applications.
Method Detail

clear

public abstract void clear()
erase all contents of the SparseArray. synchronized.


contains

public abstract boolean contains(Object value)
Returns:
true if the value is contained in the SparseArray (slow). synchronized

containsKey

public abstract boolean containsKey(int key)
Returns:
true if the key is contained in the SparseArray (fast). synchronized

elements

public abstract Enumeration elements()
Returns an Enumeration of the values in this SparseArray


elementsArray

public abstract Object[] elementsArray()
Produces an unsorted Object[] array of the elements stored herein, or a zero-length array if it is empty. You can continue to manipulate the FlatHash while using this array. This is only a shallow copy, it does not duplicate the contents. synchronized


elementsCopy

public abstract Enumeration elementsCopy()
Returns an Enumeration of the values in this SparseArray, using a copy of the arrays, so you can continue to manipulate the SparseArray while enumerating. This is only a shallow copy, it does not duplicate the contents.


ensureCapacity

public abstract void ensureCapacity(int newcap)
Resizes the hash bucket to hold at least newcap entries, before the loadFactor. synchronized


get

public abstract Object get(int key)
Returns:
(Object) value stored for the given key, or 'null' if not found. synchronized

getBoolean

public final boolean getBoolean(int key)
As get(), but tries to cast it to Boolean and then get the booleanValue.

Returns:
false if the key does not match anything.
Throws:
ClassCastException - if the cast fails.

getByte

public final byte getByte(int key)
See Also:
getInt(int)

getCapacity

public final int getCapacity()

getChar

public final char getChar(int key)
As get(), but tries to cast it to Character and then get the charValue.

Returns:
char 0 if the key does not match anything.
Throws:
ClassCastException - if the cast fails.

getDouble

public final double getDouble(int key)
See Also:
getInt(int)

getFloat

public final float getFloat(int key)
See Also:
getInt(int)

getInt

public final int getInt(int key)
As get(), but tries to cast it to Number and then get the intValue.

Returns:
0 if the key does not match anything.
Throws:
ClassCastException - if the cast fails.

getLoadFactor

public final float getLoadFactor()

getLong

public final long getLong(int key)
See Also:
getInt(int)

getShort

public final short getShort(int key)
See Also:
getInt(int)

getString

public final String getString(int key)
Returns:
get(key).toString(), or null if the key was not matched.

indexOf

public abstract int indexOf(Object find)
Finds a value that matches 'find' and returns the key. Note that this is not necessarily the lowest-numbered index. If it returns PROBABLY_NOT_FOUND, and it's possible for that to be a valid key in your program, you should check get(PROBABLY_NOT_FOUND) to see if it's defined or not.

This is fairly slow - it's O(n) instead of O(log n) as most things are. synchronized


isEmpty

public final boolean isEmpty()
Returns:
(boolean) true if there are no entries in the array

keys

public abstract IntEnumeration keys()
Returns an Enumeration of the keys in this SparseArray, each wrapped in Integers.


keysArray

public abstract int[] keysArray()
Produces an unsorted int[] array of the keys stored herein, or a zero-length array if the SparseArray is empty. You can continue to manipulate the FlatHash while using this array. This is only a shallow copy, it does not duplicate the contents. synchronized


keysCopy

public abstract IntEnumeration keysCopy()
Returns an Enumeration of the keys in this SparseArray, using a copy of the arrays, so you can continue to manipulate the SparseArray while enumerating. This is only a shallow copy, it does not duplicate the contents.


put

public final void put(int key,
                      byte value)

put

public final void put(int key,
                      char value)

put

public final void put(int key,
                      double value)

put

public final void put(int key,
                      float value)

put

public final void put(int key,
                      int value)
Convenience method to store int values, after putting them in the wrapper.


put

public final void put(int key,
                      long value)

put

public abstract void put(int key,
                         Object value)
Assigns the 'value' to the entry at 'key'. If you try to store a null, it just deletes whatever was formerly at that key. synchronized


put

public final void put(int key,
                      short value)

put

public final void put(int key,
                      boolean value)

remove

public abstract Object remove(int key)
Removes the entry at 'key', and returns the former value. synchronized

Returns:
(Object) former value, or null if nothing was found to remove.

set

public final void set(int key,
                      byte value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      char value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      double value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      float value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      int value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      long value)
Deprecated.  

See Also:
put(int,long)

set

public final void set(int key,
                      Object value)
Deprecated.  

A convenience method - I often want to type set() instead of put().

See Also:
put(int,Object)

set

public final void set(int key,
                      short value)
Deprecated.  

See Also:
put(int,int)

set

public final void set(int key,
                      boolean value)
Deprecated.  

See Also:
put(int,int)

setLoadFactor

public final void setLoadFactor(float lf)

size

public final int size()
Returns:
(int) Number of elements stored in the array.

toString

public final String toString()
Overrides:
toString in class Object