SubtypeSet


1   package polyglot.util;
2   
3   import java.util.*;
4   import polyglot.types.*;
5   
6   /**
7    * Class to implement sets containing <code>polyglot.types.Type </code>.  
8    * Set membership is based on the subtype relationships.  Thus, if 
9    * <code>S</code> is a supertype of <code>A</code> and <code>B</code>, then
10   * { <code>S</code> } union { <code>A</code>,<code>B</code> } = 
11   * { <code>S</code> }.  Similarily, we remove elements from the set such 
12   * that if <code>s</code> is an element of a set <code>S</code>, then a
13   * call to remove <code>r</code> removes all <code>s</code> s.t. r is a 
14   * a supertype of s.
15   */
16  public class SubtypeSet implements java.util.Set  
17  {
18      Vector v; 
19      TypeSystem ts;
20      Type topType;  // Everything in the set must be a subtype of topType.
21  
22      /**
23       * Creates an empty SubtypeSet
24       */
25      public SubtypeSet(TypeSystem ts) {
26      this(ts.Object());
27      }
28  
29      public SubtypeSet(Type top) {
30      v = new Vector();
31          this.ts = top.typeSystem();
32      this.topType = top;
33      }
34  
35      /**
36       * Creates a copy of the given SubtypeSet
37       */
38      public SubtypeSet(SubtypeSet s) {
39        v = new Vector(s.v);
40        ts = s.ts;
41        topType = s.topType;
42      }
43  
44      public SubtypeSet(TypeSystem ts, Collection c) {
45        this(ts);
46        addAll(c);
47      }
48  
49      public SubtypeSet(Type top, Collection c) {
50        this(top);
51        addAll(c);
52      }
53  
54      /**
55       * Add an element of type <code>polyglot.types.Type</code> to the set
56       * only if it has no supertypes already in the set. If we do add it, 
57       * remove any subtypes of <code>o</code>
58       * 
59       * @param o The element to add.
60       */
61      public boolean add(Object   o) {
62          if (o == null) {
63          return false;
64      }
65  
66      if (o instanceof Type) {
67          Type type = (Type) o;
68  
69          if (ts.isSubtype(type, topType)) {
70          boolean haveToAdd = true;
71  
72          for (Iterator i = v.iterator(); i.hasNext(); ) {
73              Type t = (Type) i.next();
74  
75              if (ts.descendsFrom(t, type)) {
76              i.remove();
77              }
78  
79              if (ts.isSubtype(type, t)) {
80              haveToAdd = false;
81              break;
82              }
83          }
84  
85          if (haveToAdd) {
86              v.add(type);
87          }
88  
89          return haveToAdd;
90          }
91      }
92  
93      throw new InternalCompilerError(
94            "Can only add " + topType + "s to the set. Got a " + o);
95      }
96  
97      /**
98       * Adds all elements from c into this set.
99       */
100     public boolean addAll(Collection c) {
101     if (c == null) {
102         return false;
103     }
104 
105     boolean changed = false;
106 
107     for (Iterator i = c.iterator(); i.hasNext(); ) {
108         changed |= add(i.next()); 
109     }
110 
111     return changed;
112     }
113 
114     /**
115      * Removes all elements from the set
116      */
117     public void clear() {
118     v.clear();
119     }
120 
121     /**
122      * Check whether object <code>o</code> is in the set. Because of the 
123      * semantics of the subtype set, <code>o</code> is in the set iff
124      * it descends from (or is equal to) one of the elements in the set.
125      */
126     public boolean contains(Object   o) {
127     if (o instanceof Type) {
128         Type type = (Type) o;
129         
130         for (Iterator i = v.iterator(); i.hasNext(); ) {
131         Type t = (Type) i.next();
132         if (ts.isSubtype(type, t)) {
133             return true;
134         }
135         }
136     }
137 
138     return false;
139     }
140 
141     /**
142      * Check whether the type <code>t</code> or a subtype is in the set.
143      * Returns true iff it descends from, is equal to, or is a super type of
144      * one of the elements in the set.
145      */
146     public boolean containsSubtype(Type type) {
147     for (Iterator i = v.iterator(); i.hasNext(); ) {
148         Type t = (Type)i.next();
149         if (ts.isSubtype(type, t) || ts.isSubtype(t, type)) return true;
150     }
151 
152     return false;
153     }
154 
155     /**
156      * Checks whether all elements of the collection are in the set
157      */
158     public boolean containsAll(Collection c) {
159     for (Iterator i = c.iterator(); i.hasNext(); ) {
160         if (! contains (i.next())) {
161         return false;
162         }
163     }
164 
165     return true;
166     }
167 
168     public boolean isEmpty() {
169     return v.isEmpty();
170     }
171     
172     public Iterator iterator() {
173     return v.iterator();
174     }
175 
176     /**
177      * Removes all elements <code>s</code> in the set such that 
178      * <code>s</code> decends from <code>o</code>
179      *
180      * @return whether or not an element was removed.
181      */
182     public boolean remove(Object   o) {
183     Type type = (Type) o;
184 
185     boolean removed = false;
186 
187     for (Iterator i = v.iterator(); i.hasNext(); ) {
188         Type t = (Type) i.next();
189 
190         if (ts.isSubtype(t, type)) {
191         removed = true;
192         i.remove(); 
193         }
194     }
195 
196     return removed;
197     }
198     
199     public boolean removeAll(Collection c) {
200         boolean changed = false;
201 
202     for (Iterator i = c.iterator(); i.hasNext(); ) {
203         Object   o = i.next();
204         changed |= remove(o);
205     }
206 
207     return changed;
208     }
209 
210     public boolean retainAll(Collection c) {
211     throw new UnsupportedOperationException  ("Not supported");
212     }
213 
214     public int size() {
215     return v.size();
216     }
217 
218     public Object  [] toArray() {
219     return v.toArray();
220     }
221 
222     public Object  [] toArray(Object  [] a) {
223     return v.toArray(a);
224     }
225 
226     public String   toString() {
227     return v.toString();
228     }
229 }
230
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags