diva.compat.util
Class PropertyIndexSet

java.lang.Object
  extended by diva.compat.util.PropertyIndexSet

public class PropertyIndexSet
extends Object

PropertyIndexSet is a mechanism for providing efficient dynamic object annotation for data structures that might be used by a number of cooperating packages.

A nearly equivalent functionality may be provided by a more naive implementation, using a Hashtable to store object propertys:

     void traverse(HashPropertyContainer obj) {
         Boolean visited = (Boolean)obj.getProperty("visited");
         if((visited == null) || (!visited.booleanValue())) {
             // (some traversal code here...)
             obj.setAttr("visited", Boolean.TRUE);
         }
     }
 
This allows an algorithm to mark an object as "visited" without modifying the object's code and without building external data structures. However, providing annotation this way, though flexible, can be prohibitively expensive because a hash function must be called for every "getAttr" and "setAttr" invocation.

PropertyIndexSet provides nearly the same functionality, but more efficiently. It does this by a "hash once" technique, where algorithms or packages can reserve an integer "slot" once from the index set, and use it thereafter with no lookup time and constant access time. Equivalent code to the above "visited" example:

     // do this only once
     static int VISITED_INDEX = getPropertyIndexSet().getIndex("visited);

     void traverse(PropertyContainer obj) {
         Boolean visited = (Boolean)obj.getProperty(VISITED_INDEX);
         if((visited == null) || (!visited.booleanValue())) {
             // (some traversal code here...)
             obj.setAttr(VISITED_INDEX, Boolean.TRUE);
         }
     }
 
Obviously there are issues about when it is appropriate to use this scheme. For example, if the propertys are very sparse, it might be better to use an external data structure to maintain the data. It also requires a global "name space", which is not true of a one-hashtable-per- object implementation. A complementary class PropertyManager is provided to manage "scopes". For exmple, in a graph package if you would like one set of indexes for nodes in a graph and a separate set for edges, you can use PropertyManager to define a "node" scope and an "edge" scope. Alternately, you can manage multiple PropertyIndexSets in a way which makes sense to your application (e.g. make them global variables, or store them at the top of collections of annotated objects...).

Version:
$Revision: 1.1 $
Author:
Michael Shilman (michaels@eecs.berkeley.edu)
See Also:
PropertyContainer

Field Summary
static int NO_INDEX
          A constant which designates that a particular slot name does not yet have an index in the property table.
 
Constructor Summary
PropertyIndexSet()
           
 
Method Summary
 void freeIndex(String slotName)
          Free the index of slotName for use by another property.
 int getIndex(String slotName)
          Returns the index of the property named by slotName.
 String indexName(int index)
          Returns the string name of the property held by index.
 void PropertyIndexSet()
          Create an empty index set.
 int queryIndex(String slotName)
          Returns the index of the property named by slotName.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NO_INDEX

public static int NO_INDEX
A constant which designates that a particular slot name does not yet have an index in the property table.

Constructor Detail

PropertyIndexSet

public PropertyIndexSet()
Method Detail

PropertyIndexSet

public void PropertyIndexSet()
Create an empty index set.


freeIndex

public void freeIndex(String slotName)
Free the index of slotName for use by another property. Note that this does not free the the propertys on the objects which are actually being tagged, so it is up to the user of the PropertyIndexSet management facility to free that themselves.


getIndex

public int getIndex(String slotName)
Returns the index of the property named by slotName. If slotName doesn't yet have an index, it creates a new slot for it.


indexName

public String indexName(int index)
Returns the string name of the property held by index.


queryIndex

public int queryIndex(String slotName)
Returns the index of the property named by slotName. If slotName doesn't yet have an index, it returns the constant NO_INDEX.



Copyright © 2015 Central Laboratory of the Research Councils. All Rights Reserved.