Source code: org/sablecc/sablecc/CharSet.java
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * This file is part of SableCC. *
3 * See the file "LICENSE" for copyright information and the *
4 * terms and conditions for copying, distribution and *
5 * modification of SableCC. *
6 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
7
8 package org.sablecc.sablecc;
9
10 import java.util.*;
11 import com.sun.java.util.collections.*;
12 import java.util.Enumeration;
13 import java.util.Vector;
14
15 public class CharSet implements Cloneable
16 {
17 private final Vector intervals = new Vector(0);
18
19 public CharSet(char c)
20 {
21 intervals.addElement(new Interval(c, c));
22 }
23
24 public CharSet(char start, char end)
25 {
26 intervals.addElement(new Interval(start, end));
27 }
28
29 private CharSet(Vector intervals)
30 {
31 for(Enumeration e = intervals.elements(); e.hasMoreElements();)
32 {
33 this.intervals.addElement(((Interval) e.nextElement()).clone());
34 }
35 }
36
37 public Object clone()
38 {
39 return new CharSet(intervals);
40 }
41
42 public Interval findOverlap(Interval interval1)
43 {
44 int low = 0;
45 int high = intervals.size() - 1;
46 Interval interval2;
47 Interval result = null;
48
49 while(high >= low)
50 {
51 int middle = (high + low) / 2;
52
53 interval2 = (Interval) intervals.elementAt(middle);
54
55 if(interval1.start <= interval2.end)
56 {
57 if(interval1.end >= interval2.start)
58 {
59 result = interval2;
60 // we continue, to find the lowest matching interval!
61 }
62
63 high = middle - 1;
64 }
65 else
66 {
67 low = middle + 1;
68 }
69 }
70
71 return result;
72 }
73
74 private void remove(Interval interval)
75 {
76 intervals.removeElement(interval);
77 }
78
79 private void add(Interval interval)
80 {
81 for(int i = 0; i < intervals.size(); i++)
82 {
83 Interval iv = (Interval) intervals.elementAt(i);
84
85 if(iv.start > interval.start)
86 {
87 intervals.insertElementAt(interval, i);
88 return;
89 }
90 }
91
92 intervals.addElement(interval);
93 }
94
95 public CharSet union(CharSet chars)
96 {
97 CharSet result = (CharSet) clone();
98
99 Interval interval;
100 Interval largeInterval;
101 Interval overlap;
102
103 for(Enumeration e = chars.intervals.elements(); e.hasMoreElements();)
104 {
105 interval = (Interval) ((Interval) e.nextElement()).clone();
106
107 do
108 {
109 largeInterval = new Interval(
110 (interval.start == 0) ? (char) 0 : (char) (interval.start - 1),
111 (interval.end == 0xffff) ? (char) 0xffff : (char) (interval.end + 1));
112
113 overlap = result.findOverlap(largeInterval);
114 if(overlap != null)
115 {
116 result.remove(overlap);
117 interval.start = (char) Math.min(interval.start, overlap.start);
118 interval.end = (char) Math.max(interval.end, overlap.end);
119 }
120 }
121 while(overlap != null);
122
123 result.add(interval);
124 }
125
126 return result;
127 }
128
129 public CharSet diff(CharSet chars)
130 {
131 CharSet result = (CharSet) clone();
132
133 Interval interval;
134 Interval overlap;
135
136 for(Enumeration e = chars.intervals.elements(); e.hasMoreElements();)
137 {
138 interval = (Interval) ((Interval) e.nextElement()).clone();
139
140 do
141 {
142 overlap = result.findOverlap(interval);
143 if(overlap != null)
144 {
145 result.remove(overlap);
146 if(overlap.start < interval.start)
147 {
148 result.add(new Interval(overlap.start, (char) (interval.start - 1)));
149 }
150 if(overlap.end > interval.end)
151 {
152 result.add(new Interval((char) (interval.end + 1), overlap.end));
153 }
154 }
155 }
156 while(overlap != null);
157 }
158
159 return result;
160 }
161
162 public String toString()
163 {
164 StringBuffer result = new StringBuffer();
165
166 for(Enumeration e = intervals.elements(); e.hasMoreElements();)
167 {
168 result.append("[" + e.nextElement() + "] ");
169 }
170
171 return "" + result;
172 }
173
174
175 public static class Interval implements Cloneable
176 {
177 public Interval(char start, char end)
178 {
179 this.start = start;
180 this.end = end;
181 }
182
183 public Object clone()
184 {
185 return new Interval(start, end);
186 }
187
188 private String c(char c)
189 {
190 if((c >= 32) && (c < 127))
191 {
192 return "" + c;
193 }
194
195 return "" + ((int) c);
196 }
197
198 public String toString()
199 {
200 if(start < end)
201 {
202 return c(start) + " .. " + c(end);
203 }
204 else
205 {
206 return c(start);
207 }
208 }
209
210 public char start;
211 public char end;
212 }
213
214 public static class IntervalCast implements Cast
215 {
216 public final static IntervalCast instance = new IntervalCast();
217
218 private IntervalCast()
219 {
220 }
221
222 public Object cast(Object o)
223 {
224 return (Interval) o;
225 }
226 }
227 }
228
229