Graphical bits moved into files to save jar size
[jalview.git] / 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