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. */
terminal_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    */
terminal_set(terminal_set other)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    */
not_null(Object obj)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. */
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    */
contains(terminal sym)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    */
contains(int indx)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    */
is_subset_of(terminal_set other)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    */
is_superset_of(terminal_set other)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    */
add(terminal sym)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    */
remove(terminal sym)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    */
add(terminal_set other)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    */
intersects(terminal_set other)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. */
equals(terminal_set other)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. */
equals(Object other)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. */
toString()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