Changeset 2654

Timestamp:

11/10/08 16:54:10 (2 months ago)

Author:

leo

Message:

lattice

Location:

XerialJ/trunk/xerial-core/src

Files:

• main/java/org/xerial/core/XerialErrorCode.java (modified) (1 diff)
• main/java/org/xerial/util/BitVector.java (modified) (1 diff)
• main/java/org/xerial/util/graph/Lattice.java (modified) (3 diffs)
• main/java/org/xerial/util/graph/LatticeNode.java (modified) (3 diffs)
• test/java/org/xerial/util/graph/LatticeTest.java (modified) (3 diffs)

XerialJ/trunk/xerial-core/src/main/java/org/xerial/core/XerialErrorCode.java

@@ -37 +37 @@
     SYNTAX_ERROR,
     NOT_INITIALIZED,
+    UNSUPPORTED,
     // collection
     MISSING_ELEMENT,

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/BitVector.java

@@ -149 +149 @@
     }
 
-    public static BitVector newInstance(BitVector source, int additionlBitIndex)
+    public static BitVector newInstanceWithAnAdditionalBit(BitVector source, int bitIndexToAdd)
     {
         BitVector newInstance = new BitVector(source.bitVector, source.size);
-        newInstance.on(additionlBitIndex);
+        newInstance.on(bitIndexToAdd);
         return newInstance;
     }

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/Lattice.java

@@ -25 +25 @@
 package org.xerial.util.graph;
 
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import org.xerial.core.XerialError;
+import org.xerial.core.XerialErrorCode;
 import org.xerial.util.BitVector;
 import org.xerial.util.IndexedSet;
@@ -37 +42 @@
 public class Lattice<T>
 {
-    IndexedSet<T>         elementSet     = new IndexedSet<T>();
-    IndexedSet<BitVector> latticeNodeSet = new IndexedSet<BitVector>();
+    private IndexedSet<T>                         elementSet        = new IndexedSet<T>();
+    private IndexedSet<LatticeNode<T>>            latticeNodeSet    = new IndexedSet<LatticeNode<T>>();
+    private ArrayList<HashMap<T, LatticeNode<T>>> outEdgeIndexTable = new ArrayList<HashMap<T, LatticeNode<T>>>();
+    private ArrayList<HashMap<T, LatticeNode<T>>> inEdgeIndexTable  = new ArrayList<HashMap<T, LatticeNode<T>>>();
+
+    private final LatticeNode<T>                  emptySet;
 
     public Lattice()
     {
-        latticeNodeSet.add(new BitVector());
+        emptySet = newLatticeNode(new BitVector());
+    }
+
+    private HashMap<T, LatticeNode<T>> getOutEdgeIndex(int latticeNodeID)
+    {
+        assert latticeNodeID > 0;
+        return outEdgeIndexTable.get(latticeNodeID - 1);
+    }
+
+    private HashMap<T, LatticeNode<T>> getInEdgeIndex(int latticeNodeID)
+    {
+        assert latticeNodeID > 0;
+        return inEdgeIndexTable.get(latticeNodeID - 1);
+    }
+
+    LatticeNode<T> next(LatticeNode<T> currentNode, T element)
+    {
+        int currentLatticeNodeID = currentNode.getID();
+
+        HashMap<T, LatticeNode<T>> outEdgeIndexOfTheCurrentNode = getOutEdgeIndex(currentLatticeNodeID);
+        LatticeNode<T> nextNode = outEdgeIndexOfTheCurrentNode.get(element);
+        if (nextNode != null)
+            return nextNode;
+
+        // create a new lattice node
+        LatticeNode<T> newLatticeNode = newLatticeNode(BitVector.newInstanceWithAnAdditionalBit(currentNode
+                .getElementOnOffIndicator(), elementSet.getIDwithAddition(element)));
+
+        // draw an in-edge from the current node (for back operation)
+        getInEdgeIndex(newLatticeNode.getID()).put(element, currentNode);
+
+        // draw an out-edge (labeled with the element value) from the current node to the new node
+        getOutEdgeIndex(currentLatticeNodeID).put(element, newLatticeNode);
+
+        return newLatticeNode;
+    }
+
+    LatticeNode<T> back(LatticeNode<T> currentNode, T element)
+    {
+        int currentLatticeNodeID = currentNode.getID();
+
+        HashMap<T, LatticeNode<T>> inEdgeIndexOfTheCurrentNode = getInEdgeIndex(currentLatticeNodeID);
+        LatticeNode<T> prevNode = inEdgeIndexOfTheCurrentNode.get(element);
+        if (prevNode != null)
+            return prevNode;
+        else
+            throw new XerialError(XerialErrorCode.UNSUPPORTED, String.format(
+                    "previous node must exist in the lattice. currentNode = %s, element = %s", currentNode, element));
+    }
+
+    protected LatticeNode<T> newLatticeNode(BitVector bv)
+    {
+        LatticeNode<T> newLatticeNode = new LatticeNode<T>(this, bv);
+        // allocate an new ID for the lattice node 
+        int newLatticeNodeID = latticeNodeSet.getIDwithAddition(newLatticeNode);
+        newLatticeNode.setID(newLatticeNodeID);
+
+        // create in/out edge indexes for the new node
+        inEdgeIndexTable.add(new HashMap<T, LatticeNode<T>>());
+        outEdgeIndexTable.add(new HashMap<T, LatticeNode<T>>());
+
+        assert (newLatticeNodeID == outEdgeIndexTable.size());
+        assert (newLatticeNodeID == inEdgeIndexTable.size());
+
+        return newLatticeNode;
     }
 
     public LatticeNode<T> emptyNode()
     {
-        return new LatticeNode<T>(this, new BitVector());
+        return emptySet;
+    }
+
+    public int getElementID(T element)
+    {
+        return elementSet.getID(element);
     }
 
@@ -54 +132 @@
         return elementSet.getByID(elementID);
     }
+
 }

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/LatticeNode.java

@@ -26 +26 @@
 
 import java.util.ArrayList;
-import java.util.HashMap;
 
 import org.xerial.core.XerialError;
@@ -34 +33 @@
 import org.xerial.util.StringUtil;
 
+/**
+ * lattice node
+ * 
+ * @author leo
+ * 
+ * @param <T>
+ */
 public class LatticeNode<T>
 {
-    private final Lattice<T>                 lattice;
-    private final BitVector                  elementOnOffIndicator;
-    private final HashMap<T, LatticeNode<T>> linkToNextNode = new HashMap<T, LatticeNode<T>>();
+    private int              id = -1;
+    private final Lattice<T> lattice;
+    private final BitVector  elementOnOffIndicator;
 
     public LatticeNode(Lattice<T> lattice, BitVector elementOnOffIndicator)
@@ -46 +52 @@
     }
 
+    public void setID(int id)
+    {
+        this.id = id;
+    }
+
+    public int getID()
+    {
+        assert id != -1;
+        return id;
+    }
+
+    BitVector getElementOnOffIndicator()
+    {
+        return elementOnOffIndicator;
+    }
+
     public boolean contains(T element)
     {
-        int id = lattice.elementSet.getID(element);
+        int id = lattice.getElementID(element);
         if (id == IndexedSet.INVALID_ID)
             return false;
 
-        return elementOnOffIndicator.get(id - 1);
-    }
-
-    protected int getElementID(T element)
-    {
-        if (!lattice.elementSet.contains(element))
-            lattice.elementSet.add(element);
-
-        return lattice.elementSet.getID(element);
+        return elementOnOffIndicator.get(id);
     }
 
     public LatticeNode<T> next(T elementToAdd)
     {
-        if (linkToNextNode.containsKey(elementToAdd))
-        {
-            return linkToNextNode.get(elementToAdd);
-        }
+        return lattice.next(this, elementToAdd);
+    }
 
-        // Add new edge to a LatticeNode
-        // First, create a new bit vector that additionally set the target element ID
-        int elementID = getElementID(elementToAdd);
-        BitVector newIndicator = BitVector.newInstance(elementOnOffIndicator, elementID - 1);
+    public LatticeNode<T> back(T elementToRemove)
+    {
+        return lattice.back(this, elementToRemove);
+    }
 
-        int latticeNodeID = lattice.latticeNodeSet.getID(newIndicator);
-        if (latticeNodeID == IndexedSet.INVALID_ID)
-        {
-            lattice.latticeNodeSet.add(newIndicator);
-            return new LatticeNode<T>(lattice, newIndicator);
-        }
-        else
-            return new LatticeNode<T>(lattice, lattice.latticeNodeSet.getByID(latticeNodeID));
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals(Object obj)
+    {
+        if (!this.getClass().isInstance(obj))
+            return false;
+
+        LatticeNode<T> other = (LatticeNode<T>) obj;
+        return this.lattice == other.lattice && this.elementOnOffIndicator.equals(other.elementOnOffIndicator);
+    }
+
+    @Override
+    public int hashCode()
+    {
+        int hashValue = 3;
+        hashValue += lattice.hashCode() * 31;
+        hashValue += elementOnOffIndicator.hashCode() * 31;
+        return hashValue % 1987;
     }
 

XerialJ/trunk/xerial-core/src/test/java/org/xerial/util/graph/LatticeTest.java

@@ -25 +25 @@
 package org.xerial.util.graph;
 
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotSame;
 import static org.junit.Assert.assertTrue;
 
@@ -31 +33 @@
 import org.junit.Before;
 import org.junit.Test;
+import org.xerial.util.StopWatch;
+import org.xerial.util.log.Logger;
 
 public class LatticeTest
 {
+    private static Logger _logger = Logger.getLogger(LatticeTest.class);
 
     @Before
@@ -59 +64 @@
         assertFalse(abNode.contains("C"));
 
+        LatticeNode<String> acNode = aNode.next("C");
+        assertTrue(acNode.contains("A"));
+        assertTrue(acNode.contains("C"));
+        assertFalse(acNode.contains("B"));
+
+        LatticeNode<String> acdNode = acNode.next("D");
+        assertTrue(acdNode.contains("A"));
+        assertTrue(acdNode.contains("C"));
+        assertTrue(acdNode.contains("D"));
+        assertTrue(!acdNode.contains("B"));
+
+        LatticeNode<String> acdMinusDNode = acdNode.back("D");
+        assertEquals(acNode, acdMinusDNode);
+        assertNotSame(acNode, acdNode);
+        assertEquals(acNode.getID(), acdMinusDNode.getID());
+
+        LatticeNode<String> acdMinusDCNode = acdNode.back("D").back("C");
+        assertEquals(aNode, acdMinusDCNode);
+        assertNotSame(abNode, acdMinusDCNode);
+        assertEquals(aNode.getID(), acdMinusDCNode.getID());
+
+    }
+
+    @Test
+    public void latticePerformance()
+    {
+        Lattice<String> lattice = new Lattice<String>();
+        LatticeNode<String> emptyNode = lattice.emptyNode();
+
+        StopWatch timer = new StopWatch();
+        int N = 10000;
+
+        timer.reset();
+        LatticeNode<String> emptyNode2 = emptyNode.next("A").next("B").next("C").next("D").back("D").back("C")
+                .back("B").back("A");
+        assertEquals(emptyNode, emptyNode2);
+
+        emptyNode2 = emptyNode.next("A").next("B").back("B").back("A");
+        assertEquals(emptyNode, emptyNode2);
+
+        _logger.debug(timer.getElapsedTime());
+
     }