1 18 19 package org.sablecc.sablecc.alphabet; 20 21 import java.util.Collection ; 22 import java.util.Collections ; 23 import java.util.Iterator ; 24 import java.util.LinkedList ; 25 import java.util.SortedSet ; 26 import java.util.TreeSet ; 27 28 import org.sablecc.sablecc.exception.InternalException; 29 30 34 public final class Symbol<T extends Comparable <? super T>> 35 implements Comparable <Symbol<T>> { 36 37 41 private final SortedSet <Interval<T>> intervals; 42 43 44 private Integer hashCode; 45 46 50 private String toString; 51 52 63 public Symbol( 64 Collection <Interval<T>> intervals) { 65 66 if (intervals == null) { 67 throw new InternalException("intervals may not be null"); 68 } 69 70 if (intervals.isEmpty()) { 71 throw new InternalException( 72 "intervals must contain at least one element"); 73 } 74 75 SortedSet <Interval<T>> originalSet = new TreeSet <Interval<T>>(intervals); 77 78 SortedSet <Interval<T>> minimalSet = new TreeSet <Interval<T>>(); 80 81 Interval<T> previous = null; 82 Interval<T> combinedInterval = null; 83 for (Interval<T> current : originalSet) { 84 if (current == null) { 85 throw new InternalException("null is not a valid interval"); 86 } 87 88 if (previous != null && previous.intersects(current)) { 89 throw new InternalException("intervals may not intersect"); 90 } 91 92 if (combinedInterval != null) { 93 if (combinedInterval.isAdjacentTo(current)) { 94 combinedInterval = combinedInterval.mergeWith(current); 95 } 96 else { 97 minimalSet.add(combinedInterval); 98 combinedInterval = current; 99 } 100 } 101 else { 102 combinedInterval = current; 103 } 104 105 previous = current; 106 } 107 108 minimalSet.add(combinedInterval); 109 110 this.intervals = Collections.unmodifiableSortedSet(minimalSet); 111 } 112 113 121 public Symbol( 122 Interval<T> interval) { 123 124 if (interval == null) { 125 throw new InternalException("interval must be provided"); 126 } 127 128 SortedSet <Interval<T>> set = new TreeSet <Interval<T>>(); 129 set.add(interval); 130 this.intervals = Collections.unmodifiableSortedSet(set); 131 } 132 133 137 public Symbol() { 138 139 this.intervals = null; 140 } 141 142 147 public SortedSet <Interval<T>> getIntervals() { 148 149 if (this.intervals == null) { 150 throw new InternalException("complement symbols have no intervals"); 151 } 152 153 return this.intervals; 154 } 155 156 165 @Override 166 public boolean equals( 167 Object obj) { 168 169 if (this == obj) { 170 return true; 171 } 172 173 if (obj == null) { 174 return false; 175 } 176 177 if (getClass() != obj.getClass()) { 178 return false; 179 } 180 181 Symbol symbol = (Symbol) obj; 182 183 if (this.intervals == null || symbol.intervals == null) { 184 return this.intervals == symbol.intervals; 185 } 186 187 if (this.intervals.size() != symbol.intervals.size()) { 188 return false; 189 } 190 191 Iterator i = symbol.intervals.iterator(); 192 for (Interval<T> interval : this.intervals) { 193 if (!interval.equals(i.next())) { 194 return false; 195 } 196 } 197 198 return true; 199 } 200 201 206 @Override 207 public int hashCode() { 208 209 if (this.hashCode == null) { 210 int hashCode = 0; 211 212 if (this.intervals != null) { 213 for (Interval<T> interval : this.intervals) { 214 hashCode *= 7; 215 hashCode += interval.hashCode(); 216 } 217 } 218 219 this.hashCode = hashCode; 220 } 221 222 return this.hashCode; 223 } 224 225 230 @Override 231 public String toString() { 232 233 if (this.toString == null) { 234 StringBuilder sb = new StringBuilder (); 235 236 sb.append("{"); 237 238 if (this.intervals != null) { 239 boolean first = true; 240 for (Interval<T> interval : this.intervals) { 241 if (first) { 242 first = false; 243 } 244 else { 245 sb.append(","); 246 } 247 248 sb.append(interval); 249 } 250 } 251 else { 252 sb.append("Complement"); 253 } 254 255 sb.append("}"); 256 257 this.toString = sb.toString(); 258 } 259 260 return this.toString; 261 } 262 263 274 public int compareTo( 275 Symbol<T> symbol) { 276 277 if (this.intervals == null || symbol.intervals == null) { 278 279 if (this.intervals == symbol.intervals) { 280 return 0; 281 } 282 283 if (this.intervals == null) { 284 return -1; 285 } 286 287 return 1; 288 } 289 290 int result = 0; 291 292 Iterator <Interval<T>> i1 = this.intervals.iterator(); 293 Iterator <Interval<T>> i2 = symbol.intervals.iterator(); 294 295 while (result == 0 && i1.hasNext() && i2.hasNext()) { 296 Interval<T> interval1 = i1.next(); 297 Interval<T> interval2 = i2.next(); 298 299 result = interval1.compareTo(interval2); 300 301 if (result != 0) { 302 break; 303 } 304 } 305 306 if (result == 0 && (i1.hasNext() || i2.hasNext())) { 307 result = this.intervals.size() - symbol.intervals.size(); 308 } 309 310 return result; 311 } 312 313 318 public boolean isComplement() { 319 320 return this.intervals == null; 321 } 322 323 338 public static <T extends Comparable <? super T>> Symbol<T> merge( 339 Collection <Symbol<T>> symbols) { 340 341 if (symbols == null) { 342 throw new InternalException("symbols may not be null"); 343 } 344 345 if (symbols.isEmpty()) { 346 throw new InternalException( 347 "symbols must contain at least one element"); 348 } 349 350 352 boolean containsComplementSymbol = false; 353 354 for (Symbol<T> symbol : symbols) { 355 if (symbol.isComplement()) { 356 357 if (containsComplementSymbol) { 358 throw new InternalException( 359 "multiple complement symbols may not be merged."); 360 } 361 362 containsComplementSymbol = true; 363 } 364 } 365 366 if (containsComplementSymbol) { 367 return new Symbol<T>(); 368 } 369 370 372 Collection <Interval<T>> intervals = new LinkedList <Interval<T>>(); 373 374 for (Symbol<T> symbol : symbols) { 375 intervals.addAll(symbol.getIntervals()); 376 } 377 378 return new Symbol<T>(intervals); 379 } 380 381 393 public static <T extends Comparable <? super T>> Symbol<T> min( 394 Symbol<T> symbol1, 395 Symbol<T> symbol2) { 396 397 if (symbol1 == null) { 398 throw new InternalException("symbol1 may not be null"); 399 } 400 401 if (symbol2 == null) { 402 throw new InternalException("symbol2 may not be null"); 403 } 404 405 if (symbol1.compareTo(symbol2) <= 0) { 406 return symbol1; 407 } 408 409 return symbol2; 410 } 411 412 424 public static <T extends Comparable <? super T>> Symbol<T> max( 425 Symbol<T> symbol1, 426 Symbol<T> symbol2) { 427 428 if (symbol1 == null) { 429 throw new InternalException("symbol1 may not be null"); 430 } 431 432 if (symbol2 == null) { 433 throw new InternalException("symbol2 may not be null"); 434 } 435 436 if (symbol1.compareTo(symbol2) >= 0) { 437 return symbol1; 438 } 439 440 return symbol2; 441 } 442 } 443 | Popular Tags |