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