src/com/stevesoft/pat/FastBracket.java

   1 //\r
   2 // This software is now distributed according to\r
   3 // the Lesser Gnu Public License.  Please see\r
   4 // http://www.gnu.org/copyleft/lesser.txt for\r
   5 // the details.\r
   6 //    -- Happy Computing!\r
   7 //\r
   8 package com.stevesoft.pat;\r
   9 \r
  10 import java.util.*;\r
  11 \r
  12 /** Uses table lookup to match [] type constructs, but\r
  13     only if it can use a lookup table 256 bits in size.\r
  14     It is impractical to make a table if it is too large.\r
  15     */\r
  16 public class FastBracket extends Bracket {\r
  17     int min, max;\r
  18     BitSet bs;\r
  19     FastBracket(boolean n) { super(n); }\r
  20     // This routine can optimize a bracket, possibly\r
  21     // it will replace it with a FastBracket.\r
  22     static Bracket process(Bracket b,boolean ignc) {\r
  23         Vector v = b.v;\r
  24         b.pv = null;\r
  25         try {\r
  26 \r
  27             // Expand out the vector to make separate\r
  28             // entries for other cases if ignoreCase is\r
  29             // turned on.\r
  30             Vector nv = v;\r
  31             if(ignc) {\r
  32                 nv = new Vector();\r
  33                 for(int i=0;i<v.size();i++) {\r
  34                     Pattern p = (Pattern)v.elementAt(i);\r
  35                     nv.addElement(p);\r
  36                     if(p instanceof oneChar) {\r
  37                         oneChar oc = (oneChar)p;\r
  38                         nv.addElement(new oneChar(oc.altc));\r
  39                     } else if(p instanceof Range) {\r
  40                         Range ra = (Range)p;\r
  41                         nv.addElement(new Range(ra.altlo,ra.althi));\r
  42                     }\r
  43                 }\r
  44             }\r
  45             v = nv;\r
  46 \r
  47             // Bubble sort, make sure elements\r
  48             // are in order.  This will allow us\r
  49             // to merge them.\r
  50             for(int i=0;i<v.size()-1;i++) {\r
  51                 for(int j=0;j<v.size()-1;j++) {\r
  52                     char c1 = getl(v.elementAt(j));\r
  53                     char c2 = getl(v.elementAt(j+1));\r
  54                     if(c2 < c1) {\r
  55                         Object o = v.elementAt(j);\r
  56                         v.setElementAt(v.elementAt(j+1),j);\r
  57                         v.setElementAt(o,j+1);\r
  58                     }\r
  59                 }\r
  60             }\r
  61 \r
  62             nv = new Vector();\r
  63             // merge -- remove overlaps\r
  64             Pattern p = (Pattern)v.elementAt(0);\r
  65             nv.addElement(p);\r
  66             for(int i=1;i<v.size();i++) {\r
  67                 if(geth(p)+1 >= getl(v.elementAt(i))) {\r
  68                     Pattern p2 = (Pattern)v.elementAt(i);\r
  69                     char lo = min(getl(p),getl(p2));\r
  70                     char hi = max(geth(p),geth(p2));\r
  71                     nv.setElementAt(p=mkelem(lo,hi),nv.size()-1);\r
  72                 } else {\r
  73                     p = (Pattern)v.elementAt(i);\r
  74                     nv.addElement(p);\r
  75                 }\r
  76             }\r
  77 \r
  78             b.v = v = nv;\r
  79         } catch(RegSyntax e) {\r
  80             e.printStackTrace();\r
  81         }\r
  82 \r
  83         // We don't want these things to be empty.\r
  84         Vector negv = neg(v);\r
  85         if(v.size()==1) return b;\r
  86         if(negv.size()==1) {\r
  87             b.v = negv;\r
  88             b.neg = !b.neg;\r
  89             return b;\r
  90         }\r
  91 \r
  92         // Now consider if we can make a FastBracket.\r
  93         // Uses a BitSet to do a lookup.\r
  94         FastBracket fb = newbrack(v,b.neg);\r
  95         if(fb == null)\r
  96             fb = newbrack(negv,!b.neg);\r
  97         if(fb != null) {\r
  98             fb.parent = b.parent;\r
  99             fb.next = b.next;\r
 100             return fb;\r
 101         }\r
 102 \r
 103         // return the normal Bracket.\r
 104         return b;\r
 105     }\r
 106 \r
 107     // Build a FastBracket and set bits.  If this can't\r
 108     // be done, return null.\r
 109     final static FastBracket newbrack(Vector v,boolean neg) {\r
 110         FastBracket fb = new FastBracket(neg);\r
 111         fb.v = v;\r
 112         if(v.size()==0) return null;\r
 113         fb.min = getl(v.elementAt(0));\r
 114         fb.max = geth(v.elementAt(v.size()-1));\r
 115         if(fb.max-fb.min <= 256) {\r
 116             fb.bs = new BitSet(fb.max-fb.min+1);\r
 117             for(int i=0;i<v.size();i++) {\r
 118                 Object o = v.elementAt(i);\r
 119                 int min0 = getl(o)-fb.min;\r
 120                 int max0 = geth(o)-fb.min;\r
 121                 for(int j=min0;j<=max0;j++)\r
 122                     fb.bs.set(j);\r
 123             }\r
 124             return fb;\r
 125         }\r
 126         return null;\r
 127     }\r
 128 \r
 129     // Negate a sorted Vector.  Applying this\r
 130     // operation twice should yield the same Vector\r
 131     // back.\r
 132     final static Vector neg(Vector v) {\r
 133         try {\r
 134             Vector nv = new Vector();\r
 135             if(v.size()==0) {\r
 136                 nv.addElement(new Range((char)0,(char)65535));\r
 137                 return nv;\r
 138             }\r
 139             int p0 = getl(v.elementAt(0));\r
 140             if(p0!=0)\r
 141                 nv.addElement(mkelem((char)0,(char)(p0-1) ));\r
 142             for(int i=0;i<v.size()-1;i++) {\r
 143                 int hi = getl(v.elementAt(i+1))-1;\r
 144                 int lo = geth(v.elementAt(i))+1;\r
 145                 nv.addElement(mkelem((char)lo,(char)hi));\r
 146             }\r
 147             int pN = geth(v.lastElement());\r
 148             if(pN != 65535)\r
 149                 nv.addElement(mkelem((char)(pN+1),(char)65535));\r
 150             return nv;\r
 151         } catch(RegSyntax rs) {\r
 152             return null;\r
 153         }\r
 154     }\r
 155     // Make either a Range or oneChar Object, depending on which\r
 156     // is appropriate.\r
 157     final static Pattern mkelem(char lo,char hi) throws RegSyntax {\r
 158         return lo==hi ? (Pattern)(new oneChar(lo)) : (Pattern)(new Range(lo,hi));\r
 159     }\r
 160     static final char min(char a,char b) {\r
 161         return a<b ? a : b;\r
 162     }\r
 163     static final char max(char a,char b) {\r
 164         return a>b ? a : b;\r
 165     }\r
 166 \r
 167     // getl -- get lower value of Range object,\r
 168     // or get value of oneChar object.\r
 169     final static char getl(Object o) {\r
 170         Pattern p = (Pattern)o;\r
 171         if(p instanceof Range)\r
 172             return ((Range)p).lo;\r
 173         return ((oneChar)p).c;\r
 174     }\r
 175     // geth -- get higher value of Range object,\r
 176     // or get value of oneChar object.\r
 177     final static char geth(Object o) {\r
 178         Pattern p = (Pattern)o;\r
 179         if(p instanceof Range)\r
 180             return ((Range)p).hi;\r
 181         return ((oneChar)p).c;\r
 182     }\r
 183 \r
 184     // This is the easy part!\r
 185     public int matchInternal(int pos,Pthings pt) {\r
 186         if(pos >= pt.src.length() || Masked(pos,pt)) return -1;\r
 187         char c = pt.src.charAt(pos);\r
 188         return (neg ^ (c >= min && c <= max && bs.get(c-min)) ) ?\r
 189             nextMatch(pos+1,pt) : -1;\r
 190     }\r
 191 }\r