src/main/java/org/xerial/util/graph/Lattice.java

   1 /*--------------------------------------------------------------------------\r
   2  *  Copyright 2008 Taro L. Saito\r
   3  *\r
   4  *  Licensed under the Apache License, Version 2.0 (the "License");\r
   5  *  you may not use this file except in compliance with the License.\r
   6  *  You may obtain a copy of the License at\r
   7  *\r
   8  *     http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  *  Unless required by applicable law or agreed to in writing, software\r
  11  *  distributed under the License is distributed on an "AS IS" BASIS,\r
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  *  See the License for the specific language governing permissions and\r
  14  *  limitations under the License.\r
  15  *--------------------------------------------------------------------------*/\r
  16 //--------------------------------------\r
  17 // XerialJ\r
  18 //\r
  19 // Lattic.java\r
  20 // Since: 2008/11/08 11:30:32\r
  21 //\r
  22 // $URL$\r
  23 // $Author$\r
  24 //--------------------------------------\r
  25 package org.xerial.util.graph;\r
  26 \r
  27 import java.util.ArrayList;\r
  28 import java.util.HashMap;\r
  29 \r
  30 import org.xerial.util.BitVector;\r
  31 import org.xerial.util.IndexedSet;\r
  32 \r
  33 /**\r
  34  * lattice structure\r
  35  * \r
  36  * @author leo\r
  37  * \r
  38  * @param <T>\r
  39  */\r
  40 public class Lattice<T>\r
  41 {\r
  42     private IndexedSet<T> elementSet = new IndexedSet<T>();\r
  43     private IndexedSet<LatticeNode<T>> latticeNodeSet = new IndexedSet<LatticeNode<T>>();\r
  44     private ArrayList<HashMap<T, LatticeNode<T>>> outEdgeIndexTable = new ArrayList<HashMap<T, LatticeNode<T>>>();\r
  45     private ArrayList<HashMap<T, LatticeNode<T>>> inEdgeIndexTable = new ArrayList<HashMap<T, LatticeNode<T>>>();\r
  46 \r
  47     private final LatticeNode<T> emptySet;\r
  48 \r
  49     public Lattice()\r
  50     {\r
  51         emptySet = newLatticeNode(new BitVector());\r
  52     }\r
  53 \r
  54     private HashMap<T, LatticeNode<T>> getOutEdgeIndex(int latticeNodeID)\r
  55     {\r
  56         assert latticeNodeID >= 0;\r
  57         return outEdgeIndexTable.get(latticeNodeID);\r
  58     }\r
  59 \r
  60     private HashMap<T, LatticeNode<T>> getInEdgeIndex(int latticeNodeID)\r
  61     {\r
  62         assert latticeNodeID >= 0;\r
  63         return inEdgeIndexTable.get(latticeNodeID);\r
  64     }\r
  65 \r
  66     LatticeNode<T> next(LatticeNode<T> currentNode, T element)\r
  67     {\r
  68         int currentLatticeNodeID = currentNode.getID();\r
  69 \r
  70         HashMap<T, LatticeNode<T>> outEdgeIndexOfTheCurrentNode = getOutEdgeIndex(currentLatticeNodeID);\r
  71         LatticeNode<T> nextNode = outEdgeIndexOfTheCurrentNode.get(element);\r
  72         if (nextNode != null)\r
  73             return nextNode;\r
  74 \r
  75         // search the corresponding lattice node\r
  76         BitVector toFind = BitVector.newInstanceWithAnAdditionalBit(currentNode.getElementOnOffIndicator(), elementSet\r
  77                 .getIDwithAddition(element));\r
  78         for (LatticeNode<T> each : latticeNodeSet)\r
  79         {\r
  80             if (each.getElementOnOffIndicator().equals(toFind))\r
  81             {\r
  82                 // update edges  \r
  83                 getOutEdgeIndex(currentLatticeNodeID).put(element, each);\r
  84                 getInEdgeIndex(each.getID()).put(element, currentNode);\r
  85 \r
  86                 return each;\r
  87             }\r
  88         }\r
  89 \r
  90         // create a new lattice node\r
  91         LatticeNode<T> newLatticeNode = newLatticeNode(toFind);\r
  92 \r
  93         // draw an in-edge from the current node (for back operation)\r
  94         getInEdgeIndex(newLatticeNode.getID()).put(element, currentNode);\r
  95 \r
  96         // draw an out-edge (labeled with the element value) from the current node to the new node\r
  97         getOutEdgeIndex(currentLatticeNodeID).put(element, newLatticeNode);\r
  98 \r
  99         return newLatticeNode;\r
 100     }\r
 101 \r
 102     LatticeNode<T> back(LatticeNode<T> currentNode, T element)\r
 103     {\r
 104         int currentLatticeNodeID = currentNode.getID();\r
 105 \r
 106         HashMap<T, LatticeNode<T>> inEdgeIndexOfTheCurrentNode = getInEdgeIndex(currentLatticeNodeID);\r
 107         LatticeNode<T> prevNode = inEdgeIndexOfTheCurrentNode.get(element);\r
 108         if (prevNode != null)\r
 109             return prevNode;\r
 110         else\r
 111         {\r
 112             return previousLatticeNode(currentNode.getElementOnOffIndicator(), element);\r
 113             //            throw new XerialError(XerialErrorCode.UNSUPPORTED, String.format(\r
 114             //                    "previous node must exist in the lattice. currentNode = %s, element = %s", currentNode, element));\r
 115         }\r
 116     }\r
 117 \r
 118     /**\r
 119      * recursively constructs the previous lattice node(s)\r
 120      * \r
 121      * @param current\r
 122      * @param elementToRemove\r
 123      * @return\r
 124      */\r
 125     private LatticeNode<T> previousLatticeNode(BitVector current, T elementToRemove)\r
 126     {\r
 127         if (elementToRemove == null)\r
 128         {\r
 129             // no more element to remove\r
 130             return emptySet;\r
 131         }\r
 132 \r
 133         int elementIDToRemove = getElementID(elementToRemove);\r
 134         BitVector elementOnOffIndicator = BitVector.newInstance(current);\r
 135         elementOnOffIndicator.off(elementIDToRemove);\r
 136 \r
 137         for (int i = 0; i < elementOnOffIndicator.size(); i++)\r
 138         {\r
 139             if (elementOnOffIndicator.get(i))\r
 140             {\r
 141                 T backEdgeNode = getElementByID(i);\r
 142                 LatticeNode<T> prev = previousLatticeNode(elementOnOffIndicator, backEdgeNode);\r
 143                 return prev.next(backEdgeNode);\r
 144             }\r
 145         }\r
 146         // no bit is on\r
 147         return previousLatticeNode(elementOnOffIndicator, null);\r
 148     }\r
 149 \r
 150     protected LatticeNode<T> newLatticeNode(BitVector bv)\r
 151     {\r
 152         LatticeNode<T> newLatticeNode = new LatticeNode<T>(this, bv);\r
 153         // allocate an new ID for the lattice node \r
 154         int newLatticeNodeID = latticeNodeSet.getIDwithAddition(newLatticeNode);\r
 155         newLatticeNode.setID(newLatticeNodeID);\r
 156 \r
 157         // create in/out edge indexes for the new node\r
 158         inEdgeIndexTable.add(new HashMap<T, LatticeNode<T>>());\r
 159         outEdgeIndexTable.add(new HashMap<T, LatticeNode<T>>());\r
 160 \r
 161         assert (newLatticeNodeID == outEdgeIndexTable.size() - 1);\r
 162         assert (newLatticeNodeID == inEdgeIndexTable.size() - 1);\r
 163 \r
 164         return newLatticeNode;\r
 165     }\r
 166 \r
 167     public LatticeNode<T> emptyNode()\r
 168     {\r
 169         return emptySet;\r
 170     }\r
 171 \r
 172     public LatticeCursor<T> cursor()\r
 173     {\r
 174         return new LatticeCursorImpl<T>(emptySet);\r
 175     }\r
 176 \r
 177     public int getElementID(T element)\r
 178     {\r
 179         return elementSet.getID(element);\r
 180     }\r
 181 \r
 182     public T getElementByID(int elementID)\r
 183     {\r
 184         return elementSet.getByID(elementID);\r
 185     }\r
 186 \r
 187     private static class LatticeCursorImpl<T> implements LatticeCursor<T>\r
 188     {\r
 189         private LatticeNode<T> currentLatticeNode;\r
 190 \r
 191         public LatticeCursorImpl(LatticeNode<T> latticeNode)\r
 192         {\r
 193             this.currentLatticeNode = latticeNode;\r
 194         }\r
 195 \r
 196         public LatticeNode<T> reset(LatticeNode<T> node)\r
 197         {\r
 198             this.currentLatticeNode = node;\r
 199             return currentLatticeNode;\r
 200         }\r
 201 \r
 202         public LatticeNode<T> back(T elementToRemove)\r
 203         {\r
 204             currentLatticeNode = currentLatticeNode.back(elementToRemove);\r
 205             return currentLatticeNode;\r
 206         }\r
 207 \r
 208         public boolean contains(T element)\r
 209         {\r
 210             return currentLatticeNode.contains(element);\r
 211         }\r
 212 \r
 213         public LatticeNode<T> next(T elementToAdd)\r
 214         {\r
 215             currentLatticeNode = currentLatticeNode.next(elementToAdd);\r
 216             return currentLatticeNode;\r
 217         }\r
 218 \r
 219         public LatticeNode<T> getNode()\r
 220         {\r
 221             return currentLatticeNode;\r
 222         }\r
 223 \r
 224         public int getNodeID()\r
 225         {\r
 226             return currentLatticeNode.getID();\r
 227         }\r
 228 \r
 229     }\r
 230 \r
 231 }\r