|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectsim.field.SparseField
While it has no abstract fields, SparseField is explicitly an abstract superclass of various sparse field objects. It specifies a many-to-one relationship between objects and locations. It contains two hash tables and a bag, resulting in fairly speedy, O(1) searches for all objects at a location, all objects in the entire field, changes in location for an object, and addition or removal of an object.
There are two flags you can set to trade memory for speed. These flags are here because often in a Sparse Field, you'd load a lot of things into one location, then delete all of them, but the large Bag which held them is still hanging there. Thus: removeEmptyBags will garbage-collect any bags in the field which have been completely emptied (except for the allObjects bag). And replaceLargeBags will replace large bags (over 32 in size) with smaller ones when the bag's contents drop below 1/4 the bag size.
To create a SparseField, you need to specify exactly what type a "location" object is. You do this by overriding the removeObjectsAtlocation() and setObjectLocation() methods, with versions set to the proper location class. Further, you create a method called getObjectLocation(), which returns objects of that class (by calling getRawObjectLocation() and casting the result into the proper type). See the Example Usage below.
Warning About Hashing. Java's hashing method is broken in an important way. One can override the hashCode() and equals() methods of an object so that they hash by the value of an object rather than just the pointer to it. But if this is done, then if you use this object as a key in a hash table, then change those values in the object, it will break the hash table -- the key and the object hashed by it will both be lost in the hashtable, unable to be accessed or removed from it. The moral of the story is: do not override hashCode() and equals() to hash by value unless your object is immutable -- its values cannot be changed. This is the case, for example, with Strings, which hash by value but cannot be modified. It's also the case with Int2D, Int3D, Double2D, and Double3D, as well as Double, Integer, etc. Some of Sun's own objects are broken in this respect: Point, Point2D, etc. are both mutable and hashed by value.
This affects you in the following way. While SparseField can specify any Object as a "location", generally speaking, subclasses should only permit immutable objects as locations (Int2D, Integer, String, etc.), or warn the user to never modify the location object he provides as a key.
Computational Complexity. Adding a new object to a location is O(1). Changing an object's location, or removing the object, is O(M), where M is the number of objects currently located at the object's old location. Scanning through all objects is O(N) and fast, where N is the number of objects total -- just scan through the allObjects Bag. Scanning through all stored locations is potentially slow, probably O(H), where H is the number of hash table buckets in the objectHash hash table -- you'd have to get a hash table iterator and iterate through it. Removing all objects at a given location is O(O), where O is the number of objects at that location. Clearing the hash table is O(1) discounting GC.
Example Usage. Here is an example of a simple subclass which allows locations to be positive, non-zero integers:
public class PositiveIntegerSparseField extends SparseField { // note we return an Integer, not an Object. If the user wants // an abstract supermethod for all SparseFields, he can use // getRawObjectLocation instead. Java's a pain sometimes public Integer getObjectLocation(Object obj) { return (Integer) super.getRawObjectLocation(obj); } // note we explicitly state that the location has to be an integer public Bag removeObjectsAtLocation(Integer location) { return super.removeObjectsAtLocation(location); } // note we explicitly state that the location has to be an integer public boolean setObjectLocation(Object obj, final Integer location) { if (location.intValue() >= 0) // it's a valid location return super.setObjectLocation(obj, location); else return false; } }
Nested Class Summary | |
static class |
SparseField.LocationAndIndex
Objects stored in SparseField's locationAndIndexHash table. |
Field Summary | |
Bag |
allObjects
All the objects in the sparse field. |
static int |
LARGE_BAG_RATIO
A bag must be larger than this amount times the capacity before it is eliminated if replaceLargeBags is true |
java.util.HashMap |
locationAndIndexHash
LocationAndIndex objects (locations and indexes into the allObjects array) hashed by Object. |
static int |
MIN_BAG_SIZE
No bags smaller than this size will be replaced regardless of the setting of replaceLargeBags |
java.util.HashMap |
objectHash
Bags of objects hashed by location. |
boolean |
removeEmptyBags
Should we remove bags in the field if they have been emptied, and let them GC, or should we keep them around? This doesn't include the allObjects bag. |
boolean |
replaceLargeBags
When a bag drops to one quarter capacity, should we replace it with a new bag? This doesn't include the allObjects bag. |
Constructor Summary | |
SparseField()
|
Method Summary | |
Bag |
clear()
Deletes everything, returning all the objects as a Bag (which you can freely use and modify). |
boolean |
exists(java.lang.Object obj)
Returns true if the object is in the field. |
Bag |
getAllObjects()
Returns all the objects in the Sparse Field. |
int |
getObjectIndex(java.lang.Object obj)
Returns the index of the object in the allObjects Bag, if the object exists, else returns -1. |
Bag |
getObjectsAtLocation(java.lang.Object location)
Returns a bag containing all the objects at a given location. |
Bag |
getObjectsAtLocations(Bag locations,
Bag result)
For each location, puts all object at that location into the result bag. |
java.lang.Object |
getRawObjectLocation(java.lang.Object obj)
Get the location of the provided object, or null if the object does not exist. |
java.util.Iterator |
iterator()
Iterates over all objects. |
java.util.Iterator |
locationBagIterator()
Iterates [somewhat inefficiently] over all bags of objects grouped by location. |
java.lang.Object |
remove(java.lang.Object obj)
Removes an object if it exists. |
protected Bag |
removeObjectsAtLocation(java.lang.Object location)
Removes objects at the given location, and returns a bag of them, or null. |
protected boolean |
setObjectLocation(java.lang.Object obj,
java.lang.Object location)
Changes the location of an object, or adds if it doesn't exist yet. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
public boolean removeEmptyBags
public boolean replaceLargeBags
public static final int MIN_BAG_SIZE
public static final int LARGE_BAG_RATIO
public java.util.HashMap locationAndIndexHash
public java.util.HashMap objectHash
public Bag allObjects
Constructor Detail |
public SparseField()
Method Detail |
public int getObjectIndex(java.lang.Object obj)
public boolean exists(java.lang.Object obj)
public final java.lang.Object getRawObjectLocation(java.lang.Object obj)
public final Bag getObjectsAtLocation(java.lang.Object location)
protected Bag removeObjectsAtLocation(java.lang.Object location)
public Bag clear()
public java.lang.Object remove(java.lang.Object obj)
protected boolean setObjectLocation(java.lang.Object obj, java.lang.Object location)
public final Bag getAllObjects()
public Bag getObjectsAtLocations(Bag locations, Bag result)
public java.util.Iterator iterator()
for(int x=0;x ... but do NOT modify the allObjects.objs array.
public java.util.Iterator locationBagIterator()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |