001: package java_cup;
002:
003: import java.util.BitSet;
004:
005: /** A set of terminals implemented as a bitset.
006: * @version last updated: 11/25/95
007: * @author Scott Hudson
008: */
009: public class terminal_set {
010:
011: /*-----------------------------------------------------------*/
012: /*--- Constructor(s) ----------------------------------------*/
013: /*-----------------------------------------------------------*/
014:
015: /** Constructor for an empty set. */
016: public terminal_set() {
017: /* allocate the bitset at what is probably the right size */
018: _elements = new BitSet(terminal.number());
019: }
020:
021: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
022:
023: /** Constructor for cloning from another set.
024: * @param other the set we are cloning from.
025: */
026: public terminal_set(terminal_set other) throws internal_error {
027: not_null(other);
028: _elements = (BitSet) other._elements.clone();
029: }
030:
031: /*-----------------------------------------------------------*/
032: /*--- (Access to) Static (Class) Variables ------------------*/
033: /*-----------------------------------------------------------*/
034:
035: /** Constant for the empty set. */
036: public static final terminal_set EMPTY = new terminal_set();
037:
038: /*-----------------------------------------------------------*/
039: /*--- (Access to) Instance Variables ------------------------*/
040: /*-----------------------------------------------------------*/
041:
042: /** Bitset to implement the actual set. */
043: protected BitSet _elements;
044:
045: /*-----------------------------------------------------------*/
046: /*--- General Methods ----------------------------------------*/
047: /*-----------------------------------------------------------*/
048:
049: /** Helper function to test for a null object and throw an exception if
050: * one is found.
051: * @param obj the object we are testing.
052: */
053: protected void not_null(Object obj) throws internal_error {
054: if (obj == null)
055: throw new internal_error(
056: "Null object used in set operation");
057: }
058:
059: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
060:
061: /** Determine if the set is empty. */
062: public boolean empty() {
063: return equals(EMPTY);
064: }
065:
066: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
067:
068: /** Determine if the set contains a particular terminal.
069: * @param sym the terminal symbol we are looking for.
070: */
071: public boolean contains(terminal sym) throws internal_error {
072: not_null(sym);
073: return _elements.get(sym.index());
074: }
075:
076: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
077:
078: /** Given its index determine if the set contains a particular terminal.
079: * @param indx the index of the terminal in question.
080: */
081: public boolean contains(int indx) {
082: return _elements.get(indx);
083: }
084:
085: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
086:
087: /** Determine if this set is an (improper) subset of another.
088: * @param other the set we are testing against.
089: */
090: public boolean is_subset_of(terminal_set other)
091: throws internal_error {
092: not_null(other);
093:
094: /* make a copy of the other set */
095: BitSet copy_other = (BitSet) other._elements.clone();
096:
097: /* and or in */
098: copy_other.or(_elements);
099:
100: /* if it hasn't changed, we were a subset */
101: return copy_other.equals(other._elements);
102: }
103:
104: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
105:
106: /** Determine if this set is an (improper) superset of another.
107: * @param other the set we are testing against.
108: */
109: public boolean is_super set_of(terminal_set other)
110: throws internal_error {
111: not_null(other);
112: return other.is_subset_of(this );
113: }
114:
115: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
116:
117: /** Add a single terminal to the set.
118: * @param sym the terminal being added.
119: * @return true if this changes the set.
120: */
121: public boolean add(terminal sym) throws internal_error {
122: boolean result;
123:
124: not_null(sym);
125:
126: /* see if we already have this */
127: result = _elements.get(sym.index());
128:
129: /* if not we add it */
130: if (!result)
131: _elements.set(sym.index());
132:
133: return result;
134: }
135:
136: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
137:
138: /** Remove a terminal if it is in the set.
139: * @param sym the terminal being removed.
140: */
141: public void remove(terminal sym) throws internal_error {
142: not_null(sym);
143: _elements.clear(sym.index());
144: }
145:
146: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
147:
148: /** Add (union) in a complete set.
149: * @param other the set being added.
150: * @return true if this changes the set.
151: */
152: public boolean add(terminal_set other) throws internal_error {
153: not_null(other);
154:
155: /* make a copy */
156: BitSet copy = (BitSet) _elements.clone();
157:
158: /* or in the other set */
159: _elements.or(other._elements);
160:
161: /* changed if we are not the same as the copy */
162: return !_elements.equals(copy);
163: }
164:
165: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
166:
167: /** Determine if this set intersects another.
168: * @param other the other set in question.
169: */
170: public boolean intersects(terminal_set other) throws internal_error {
171: not_null(other);
172:
173: /* make a copy of the other set */
174: BitSet copy = (BitSet) other._elements.clone();
175:
176: /* xor out our values */
177: copy.xor(this ._elements);
178:
179: /* see if its different */
180: return !copy.equals(other._elements);
181: }
182:
183: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
184:
185: /** Equality comparison. */
186: public boolean equals(terminal_set other) {
187: if (other == null)
188: return false;
189: else
190: return _elements.equals(other._elements);
191: }
192:
193: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
194:
195: /** Generic equality comparison. */
196: public boolean equals(Object other) {
197: if (!(other instanceof terminal_set))
198: return false;
199: else
200: return equals((terminal_set) other);
201: }
202:
203: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
204:
205: /** Convert to string. */
206: public String toString() {
207: String result;
208: boolean comma_flag;
209:
210: result = "{";
211: comma_flag = false;
212: for (int t = 0; t < terminal.number(); t++) {
213: if (_elements.get(t)) {
214: if (comma_flag)
215: result += ", ";
216: else
217: comma_flag = true;
218:
219: result += terminal.find(t).name();
220: }
221: }
222: result += "}";
223:
224: return result;
225: }
226:
227: /*-----------------------------------------------------------*/
228:
229: }
|