Algorithm
Development Kit 1.0

algs.model.searchtree.states
Class StateStorageFactory

java.lang.Object
  extended by algs.model.searchtree.states.StateStorageFactory

public class StateStorageFactory
extends java.lang.Object

Return an appropriate INodeSet entity.

Used by search algorithms to construct both OPEN and CLOSED sets. The efficiency of the underlying implementations determines the performance of the algorithms. Each of these INodeSet entities supports the INodeSet.remove() as it sees fit. In some cases, INodeSet.remove() will remove the member INode with the least score; other times, it simply removes the most recent one added. Each algorithm that uses INodeSet will properly select the one to construct from this factory.

  1. ORDERED -- A straw man implementation that should not be used since it stores its elements using a linked list. Inserts and removals are performed, therefore, in O(n). There are better implementations available.
  2. STACK -- Implementation stores elements in the set such that INodeSet.remove() removes the last element added to the set. Insert and removals are constant O(1) operations. However, INodeSet.contains(algs.model.searchtree.INode) is O(n).
  3. HASH -- Implementation stores elements in the set but doesn't support the INodeSet.remove(algs.model.searchtree.INode) method. Inserts and queries are constant O(1) operations.
  4. TREE -- Implementation stores elements in a balanced binary tree. The trouble is that the INode.score() is used as the discriminating key, thus it turns out to not be that useful at all.

    Since:
    1.0
    Version:
    1.0, 6/15/08
    Author:
    George Heineman

    Field Summary
    static int HASH
              Use hash table to maintain set.
    static int ORDERED
              Use Double-Linked lists to maintain an ordered set by score().
    static int QUEUE
              Use queue to maintain set.
    static int STACK
              Use stack to maintain set.
    static int TREE
              Use balanced binary tree to maintain set.
     
    Constructor Summary
    StateStorageFactory()
               
     
    Method Summary
    static INodeSet create(int type)
               
     
    Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
     

    Field Detail

    ORDERED

    public static final int ORDERED
    Use Double-Linked lists to maintain an ordered set by score().

    See Also:
    Constant Field Values

    STACK

    public static final int STACK
    Use stack to maintain set. No ordering, but last-in, first-out.

    See Also:
    Constant Field Values

    QUEUE

    public static final int QUEUE
    Use queue to maintain set. No ordering, but first-in, first-out.

    See Also:
    Constant Field Values

    TREE

    public static final int TREE
    Use balanced binary tree to maintain set. Ordering based on score().

    See Also:
    Constant Field Values

    HASH

    public static final int HASH
    Use hash table to maintain set. Ordering irrelevant.

    See Also:
    Constant Field Values
    Constructor Detail

    StateStorageFactory

    public StateStorageFactory()
    Method Detail

    create

    public static INodeSet create(int type)

    Algorithm Development Kit 1.0

    This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.