1 2 package java_cup; 3 4 import java.util.BitSet; 5 6 /** A set of terminals implemented as a bitset. 7 * @version last updated: 11/25/95 8 * @author Scott Hudson 9 */ 10 public class terminal_set { 11 12 /*-----------------------------------------------------------*/ 13 /*--- Constructor(s) ----------------------------------------*/ 14 /*-----------------------------------------------------------*/ 15 16 /** Constructor for an empty set. */ 17 public terminal_set() 18 { 19 /* allocate the bitset at what is probably the right size */ 20 _elements = new BitSet(terminal.number()); 21 }; 22 23 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 24 25 /** Constructor for cloning from another set. 26 * @param other the set we are cloning from. 27 */ 28 public terminal_set(terminal_set other) 29 throws internal_error 30 { 31 not_null(other); 32 _elements = (BitSet)other._elements.clone(); 33 }; 34 35 /*-----------------------------------------------------------*/ 36 /*--- (Access to) Static (Class) Variables ------------------*/ 37 /*-----------------------------------------------------------*/ 38 39 /** Constant for the empty set. */ 40 public static final terminal_set EMPTY = new terminal_set(); 41 42 /*-----------------------------------------------------------*/ 43 /*--- (Access to) Instance Variables ------------------------*/ 44 /*-----------------------------------------------------------*/ 45 46 /** Bitset to implement the actual set. */ 47 protected BitSet _elements; 48 49 /*-----------------------------------------------------------*/ 50 /*--- General Methods ----------------------------------------*/ 51 /*-----------------------------------------------------------*/ 52 53 /** Helper function to test for a null object and throw an exception if 54 * one is found. 55 * @param obj the object we are testing. 56 */ 57 protected void not_null(Object obj) throws internal_error 58 { 59 if (obj == null) 60 throw new internal_error("Null object used in set operation"); 61 } 62 63 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 64 65 /** Determine if the set is empty. */ 66 public boolean empty() 67 { 68 return equals(EMPTY); 69 } 70 71 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 72 73 /** Determine if the set contains a particular terminal. 74 * @param sym the terminal symbol we are looking for. 75 */ 76 public boolean contains(terminal sym) 77 throws internal_error 78 { 79 not_null(sym); 80 return _elements.get(sym.index()); 81 }; 82 83 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 84 85 /** Given its index determine if the set contains a particular terminal. 86 * @param indx the index of the terminal in question. 87 */ 88 public boolean contains(int indx) 89 { 90 return _elements.get(indx); 91 }; 92 93 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 94 95 /** Determine if this set is an (improper) subset of another. 96 * @param other the set we are testing against. 97 */ 98 public boolean is_subset_of(terminal_set other) 99 throws internal_error 100 { 101 not_null(other); 102 103 /* make a copy of the other set */ 104 BitSet copy_other = (BitSet)other._elements.clone(); 105 106 /* and or in */ 107 copy_other.or(_elements); 108 109 /* if it hasn't changed, we were a subset */ 110 return copy_other.equals(other._elements); 111 } 112 113 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 114 115 /** Determine if this set is an (improper) superset of another. 116 * @param other the set we are testing against. 117 */ 118 public boolean is_superset_of(terminal_set other) 119 throws internal_error 120 { 121 not_null(other); 122 return other.is_subset_of(this); 123 } 124 125 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 126 127 /** Add a single terminal to the set. 128 * @param sym the terminal being added. 129 * @return true if this changes the set. 130 */ 131 public boolean add(terminal sym) 132 throws internal_error 133 { 134 boolean result; 135 136 not_null(sym); 137 138 /* see if we already have this */ 139 result = _elements.get(sym.index()); 140 141 /* if not we add it */ 142 if (!result) 143 _elements.set(sym.index()); 144 145 return result; 146 }; 147 148 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 149 150 /** Remove a terminal if it is in the set. 151 * @param sym the terminal being removed. 152 */ 153 public void remove(terminal sym) 154 throws internal_error 155 { 156 not_null(sym); 157 _elements.clear(sym.index()); 158 }; 159 160 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 161 162 /** Add (union) in a complete set. 163 * @param other the set being added. 164 * @return true if this changes the set. 165 */ 166 public boolean add(terminal_set other) 167 throws internal_error 168 { 169 not_null(other); 170 171 /* make a copy */ 172 BitSet copy = (BitSet)_elements.clone(); 173 174 /* or in the other set */ 175 _elements.or(other._elements); 176 177 /* changed if we are not the same as the copy */ 178 return !_elements.equals(copy); 179 }; 180 181 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 182 183 /** Determine if this set intersects another. 184 * @param other the other set in question. 185 */ 186 public boolean intersects(terminal_set other) 187 throws internal_error 188 { 189 not_null(other); 190 191 /* make a copy of the other set */ 192 BitSet copy = (BitSet)other._elements.clone(); 193 194 /* xor out our values */ 195 copy.xor(this._elements); 196 197 /* see if its different */ 198 return !copy.equals(other._elements); 199 } 200 201 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 202 203 /** Equality comparison. */ 204 public boolean equals(terminal_set other) 205 { 206 if (other == null) 207 return false; 208 else 209 return _elements.equals(other._elements); 210 } 211 212 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 213 214 /** Generic equality comparison. */ 215 public boolean equals(Object other) 216 { 217 if (!(other instanceof terminal_set)) 218 return false; 219 else 220 return equals((terminal_set)other); 221 } 222 223 /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/ 224 225 /** Convert to string. */ 226 public String toString() 227 { 228 String result; 229 boolean comma_flag; 230 231 result = "{"; 232 comma_flag = false; 233 for (int t = 0; t < terminal.number(); t++) 234 { 235 if (_elements.get(t)) 236 { 237 if (comma_flag) 238 result += ", "; 239 else 240 comma_flag = true; 241 242 result += terminal.find(t).name(); 243 } 244 } 245 result += "}"; 246 247 return result; 248 } 249 250 /*-----------------------------------------------------------*/ 251 252 }; 253 254
