jars/icu4j-4_2_1-src/src/com/ibm/icu/text/RBBINode.java

   1 /********************************************************************\r
   2  * COPYRIGHT:\r
   3  * Copyright (c) 2001-2007, International Business Machines Corporation and\r
   4  * others. All Rights Reserved.\r
   5  ********************************************************************/\r
   6 \r
   7 package com.ibm.icu.text;\r
   8 \r
   9 import java.util.List;\r
  10 import java.util.HashSet;\r
  11 import java.util.Set;\r
  12 \r
  13 import com.ibm.icu.impl.Assert;\r
  14 \r
  15 /**\r
  16  *   This class represents a node in the parse tree created by the RBBI Rule compiler.\r
  17  * @internal\r
  18  *\r
  19  */\r
  20 class RBBINode {\r
  21 \r
  22     \r
  23  //   enum NodeType {\r
  24      static final int    setRef = 0;\r
  25      static final int    uset = 1;\r
  26      static final int    varRef = 2;\r
  27      static final int    leafChar = 3;\r
  28      static final int    lookAhead = 4;\r
  29      static final int    tag = 5;\r
  30      static final int    endMark = 6;\r
  31      static final int    opStart = 7;\r
  32      static final int    opCat = 8;\r
  33      static final int    opOr = 9;\r
  34      static final int    opStar = 10;\r
  35      static final int    opPlus = 11;\r
  36      static final int    opQuestion = 12;\r
  37      static final int    opBreak = 13;\r
  38      static final int    opReverse = 14;\r
  39      static final int    opLParen = 15;\r
  40      static final int    nodeTypeLimit = 16;    //  For Assertion checking only.\r
  41      \r
  42      static final String []  nodeTypeNames = {\r
  43          "setRef",\r
  44          "uset",\r
  45          "varRef",\r
  46          "leafChar",\r
  47          "lookAhead",\r
  48          "tag",\r
  49          "endMark",\r
  50          "opStart",\r
  51          "opCat",\r
  52          "opOr",\r
  53          "opStar",\r
  54          "opPlus",\r
  55          "opQuestion",\r
  56          "opBreak",\r
  57          "opReverse",\r
  58          "opLParen"\r
  59      };\r
  60 \r
  61 //    enum OpPrecedence {      \r
  62     static final int    precZero   = 0;\r
  63     static final int    precStart  = 1;\r
  64     static final int    precLParen = 2;\r
  65     static final int    precOpOr   = 3;\r
  66     static final int    precOpCat  = 4;\r
  67         \r
  68     int          fType;   // enum NodeType\r
  69     RBBINode      fParent;\r
  70     RBBINode      fLeftChild;\r
  71     RBBINode      fRightChild;\r
  72     UnicodeSet    fInputSet;           // For uset nodes only.\r
  73     int          fPrecedence = precZero;   // enum OpPrecedence, For binary ops only.\r
  74     \r
  75     String       fText;                 // Text corresponding to this node.\r
  76                                         //   May be lazily evaluated when (if) needed\r
  77                                         //   for some node types.\r
  78     int           fFirstPos;            // Position in the rule source string of the\r
  79                                         //   first text associated with the node.\r
  80                                         //   If there's a left child, this will be the same\r
  81                                         //   as that child's left pos.\r
  82     int           fLastPos;             //  Last position in the rule source string\r
  83                                         //    of any text associated with this node.\r
  84                                         //    If there's a right child, this will be the same\r
  85                                         //    as that child's last postion.\r
  86 \r
  87     boolean      fNullable;            //  See Aho DFA table generation algorithm\r
  88     int           fVal;                 // For leafChar nodes, the value.\r
  89                                         //   Values are the character category,\r
  90                                         //   corresponds to columns in the final\r
  91                                         //   state transition table.\r
  92 \r
  93     boolean      fLookAheadEnd;        // For endMark nodes, set TRUE if\r
  94                                         //   marking the end of a look-ahead rule.\r
  95 \r
  96     Set           fFirstPosSet;         // See Aho DFA table generation algorithm\r
  97     Set           fLastPosSet;          // See Aho.       \r
  98     Set           fFollowPos;           // See Aho.\r
  99     \r
 100     int           fSerialNum;           //  Debugging aids.  Each node gets a unique serial number.\r
 101     static int    gLastSerial;\r
 102 \r
 103     RBBINode(int t) {\r
 104         Assert.assrt(t < nodeTypeLimit);\r
 105         fSerialNum = ++gLastSerial;\r
 106         fType = t;\r
 107 \r
 108         fFirstPosSet = new HashSet();\r
 109         fLastPosSet = new HashSet();\r
 110         fFollowPos = new HashSet();\r
 111         if (t == opCat) {\r
 112             fPrecedence = precOpCat;\r
 113         } else if (t == opOr) {\r
 114             fPrecedence = precOpOr;\r
 115         } else if (t == opStart) {\r
 116             fPrecedence = precStart;\r
 117         } else if (t == opLParen) {\r
 118             fPrecedence = precLParen;\r
 119         } else {\r
 120             fPrecedence = precZero;\r
 121         }\r
 122     }\r
 123 \r
 124     RBBINode(RBBINode other) {\r
 125         fSerialNum = ++gLastSerial;\r
 126         fType = other.fType;\r
 127         fInputSet = other.fInputSet;\r
 128         fPrecedence = other.fPrecedence;\r
 129         fText = other.fText;\r
 130         fFirstPos = other.fFirstPos;\r
 131         fLastPos = other.fLastPos;\r
 132         fNullable = other.fNullable;\r
 133         fVal = other.fVal;\r
 134         fFirstPosSet = new HashSet(other.fFirstPosSet);\r
 135         fLastPosSet = new HashSet(other.fLastPosSet);\r
 136         fFollowPos = new HashSet(other.fFollowPos);\r
 137     }\r
 138 \r
 139     //-------------------------------------------------------------------------\r
 140     //\r
 141     //        cloneTree Make a copy of the subtree rooted at this node.\r
 142     //                      Discard any variable references encountered along the way,\r
 143     //                      and replace with copies of the variable's definitions.\r
 144     //                      Used to replicate the expression underneath variable\r
 145     //                      references in preparation for generating the DFA tables.\r
 146     //\r
 147     //-------------------------------------------------------------------------\r
 148     RBBINode cloneTree() {\r
 149         RBBINode n;\r
 150 \r
 151         if (fType == RBBINode.varRef) {\r
 152             // If the current node is a variable reference, skip over it\r
 153             //   and clone the definition of the variable instead.\r
 154             n = fLeftChild.cloneTree();\r
 155         } else if (fType == RBBINode.uset) {\r
 156             n = this;\r
 157         } else {\r
 158             n = new RBBINode(this);\r
 159             if (fLeftChild != null) {\r
 160                 n.fLeftChild = fLeftChild.cloneTree();\r
 161                 n.fLeftChild.fParent = n;\r
 162             }\r
 163             if (fRightChild != null) {\r
 164                 n.fRightChild = fRightChild.cloneTree();\r
 165                 n.fRightChild.fParent = n;\r
 166             }\r
 167         }\r
 168         return n;\r
 169     }\r
 170 \r
 171 \r
 172 \r
 173     //-------------------------------------------------------------------------\r
 174     //\r
 175     //       flattenVariables Walk a parse tree, replacing any variable\r
 176     //                          references with a copy of the variable's definition.\r
 177     //                          Aside from variables, the tree is not changed.\r
 178     //\r
 179     //                          Return the root of the tree. If the root was not a variable\r
 180     //                          reference, it remains unchanged - the root we started with\r
 181     //                          is the root we return. If, however, the root was a variable\r
 182     //                          reference, the root of the newly cloned replacement tree will\r
 183     //                          be returned, and the original tree deleted.\r
 184     //\r
 185     //                          This function works by recursively walking the tree\r
 186     //                          without doing anything until a variable reference is\r
 187     //                          found, then calling cloneTree() at that point. Any\r
 188     //                          nested references are handled by cloneTree(), not here.\r
 189     //\r
 190     //-------------------------------------------------------------------------\r
 191     RBBINode flattenVariables() {\r
 192         if (fType == varRef) {\r
 193             RBBINode retNode = fLeftChild.cloneTree();\r
 194             // delete this;\r
 195             return retNode;\r
 196         }\r
 197 \r
 198         if (fLeftChild != null) {\r
 199             fLeftChild = fLeftChild.flattenVariables();\r
 200             fLeftChild.fParent = this;\r
 201         }\r
 202         if (fRightChild != null) {\r
 203             fRightChild = fRightChild.flattenVariables();\r
 204             fRightChild.fParent = this;\r
 205         }\r
 206         return this;\r
 207     }\r
 208 \r
 209     //-------------------------------------------------------------------------\r
 210     //\r
 211     //      flattenSets Walk the parse tree, replacing any nodes of type setRef\r
 212     //                     with a copy of the expression tree for the set. A set's\r
 213     //                     equivalent expression tree is precomputed and saved as\r
 214     //                     the left child of the uset node.\r
 215     //\r
 216     //-------------------------------------------------------------------------\r
 217     void flattenSets() {\r
 218         Assert.assrt(fType != setRef);\r
 219 \r
 220         if (fLeftChild != null) {\r
 221             if (fLeftChild.fType == setRef) {\r
 222                 RBBINode setRefNode = fLeftChild;\r
 223                 RBBINode usetNode = setRefNode.fLeftChild;\r
 224                 RBBINode replTree = usetNode.fLeftChild;\r
 225                 fLeftChild = replTree.cloneTree();\r
 226                 fLeftChild.fParent = this;\r
 227             } else {\r
 228                 fLeftChild.flattenSets();\r
 229             }\r
 230         }\r
 231 \r
 232         if (fRightChild != null) {\r
 233             if (fRightChild.fType == setRef) {\r
 234                 RBBINode setRefNode = fRightChild;\r
 235                 RBBINode usetNode = setRefNode.fLeftChild;\r
 236                 RBBINode replTree = usetNode.fLeftChild;\r
 237                 fRightChild = replTree.cloneTree();\r
 238                 fRightChild.fParent = this;\r
 239                 // delete setRefNode;\r
 240             } else {\r
 241                 fRightChild.flattenSets();\r
 242             }\r
 243         }\r
 244     }\r
 245 \r
 246     //-------------------------------------------------------------------------\r
 247     //\r
 248     //       findNodes() Locate all the nodes of the specified type, starting\r
 249     //                       at the specified root.\r
 250     //\r
 251     //-------------------------------------------------------------------------\r
 252     void findNodes(List dest, int kind) {\r
 253         if (fType == kind) {\r
 254             dest.add(this);\r
 255         }\r
 256         if (fLeftChild != null) {\r
 257             fLeftChild.findNodes(dest, kind);\r
 258         }\r
 259         if (fRightChild != null) {\r
 260             fRightChild.findNodes(dest, kind);\r
 261         }\r
 262     }\r
 263 \r
 264     \r
 265  \r
 266     //-------------------------------------------------------------------------\r
 267     //\r
 268     //        print. Print out a single node, for debugging.\r
 269     //\r
 270     //-------------------------------------------------------------------------\r
 271     ///CLOVER:OFF\r
 272     static void printNode(RBBINode n) {\r
 273 \r
 274         if (n==null) {\r
 275             System.out.print (" -- null --\n");\r
 276         } else {\r
 277             RBBINode.printInt( n.fSerialNum, 10);\r
 278             RBBINode.printString(nodeTypeNames[n.fType], 11);\r
 279             RBBINode.printInt(n.fParent==null? 0     : n.fParent.fSerialNum, 11);\r
 280             RBBINode.printInt(n.fLeftChild==null? 0  : n.fLeftChild.fSerialNum, 11);\r
 281             RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12);\r
 282             RBBINode.printInt(n.fFirstPos, 12);\r
 283             RBBINode.printInt(n.fVal, 7);\r
 284             \r
 285             if (n.fType == varRef) {\r
 286                 System.out.print(" " + n.fText);\r
 287             }\r
 288         }\r
 289         System.out.println("");\r
 290     }\r
 291     ///CLOVER:ON\r
 292  \r
 293 \r
 294     // Print a String in a fixed field size.\r
 295     // Debugging function.\r
 296     ///CLOVER:OFF\r
 297     static void printString(String s, int minWidth) {\r
 298         for (int i = minWidth; i < 0; i++) {\r
 299             // negative width means pad leading spaces, not fixed width.\r
 300             System.out.print(' ');\r
 301         }\r
 302         for (int i = s.length(); i < minWidth; i++) {\r
 303             System.out.print(' ');\r
 304         }\r
 305         System.out.print(s);\r
 306     }\r
 307     ///CLOVER:ON\r
 308 \r
 309     //\r
 310     //  Print an int in a fixed size field.\r
 311     //  Debugging function.\r
 312     //\r
 313     ///CLOVER:OFF\r
 314     static void printInt(int i, int minWidth) {\r
 315         String s = Integer.toString(i);\r
 316         printString(s, Math.max(minWidth, s.length() + 1));\r
 317     }\r
 318     ///CLOVER:ON\r
 319 \r
 320     ///CLOVER:OFF\r
 321     static void printHex(int i, int minWidth) {\r
 322         String s = Integer.toString(i, 16);\r
 323         String leadingZeroes = "00000"\r
 324                 .substring(0, Math.max(0, 5 - s.length()));\r
 325         s = leadingZeroes + s;\r
 326         printString(s, minWidth);\r
 327     }\r
 328     ///CLOVER:ON\r
 329 \r
 330 \r
 331     // -------------------------------------------------------------------------\r
 332     //\r
 333     //        print. Print out the tree of nodes rooted at "this"\r
 334     //\r
 335     // -------------------------------------------------------------------------\r
 336     ///CLOVER:OFF\r
 337     void printTree(boolean printHeading) {\r
 338         if (printHeading) {\r
 339             System.out.println( "-------------------------------------------------------------------");\r
 340             System.out.println("    Serial       type     Parent  LeftChild  RightChild    position  value");\r
 341         }\r
 342         printNode(this);\r
 343             // Only dump the definition under a variable reference if asked to.\r
 344             // Unconditinally dump children of all other node types.\r
 345             if (fType != varRef) {\r
 346                 if (fLeftChild != null) {\r
 347                     fLeftChild.printTree(false);\r
 348                 }\r
 349                 \r
 350                 if (fRightChild != null) {\r
 351                     fRightChild.printTree(false);\r
 352                 }\r
 353             }\r
 354     }\r
 355     ///CLOVER:ON\r
 356 \r
 357 }\r