1 package jsdsi;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5 import java.util.Collection;
6 import java.util.Iterator;
7 import java.util.LinkedList;
8 import java.util.List;
9
10 import jsdsi.sexp.Sexp;
11 import jsdsi.sexp.SexpParseException;
12 import jsdsi.sexp.SexpUtil;
13
14 /***
15 * A tag that specifies a set of allowed values. <p><strong>Note:
16 * Currently empty and singleton sets are allowed, but will be made
17 * illegal in a future release.</strong></p>
18 *
19 * @author Sameer Ajmani
20 * @author Sean Radford
21 * @version $Revision: 1.11.2.2 $ $Date: 2005/11/08 03:12:52 $
22 */
23 public class SetTag extends ExprTag {
24
25 private static final long serialVersionUID = -5653879491817721014L;
26
27 /***
28 * Elements in this <code>SetTag</code>.
29 */
30 private transient final List elements;
31
32 /***
33 * Creates a new <code>SetTag</code> for a given array of tags.
34 * <p><strong>Note: Currently empty and singleton sets are allowed,
35 * but will be made illegal in a future release.</strong></p>
36 *
37 * @param e array of ExprTags.
38 * @throws IllegalArgumentException if <code>e</code> contains less
39 * than 2 elements (IN A FUTURE RELEASE)
40 * @todo check that <code>e</code> does not contain any
41 * <code>null</code>s or duplicates (is a set)
42 * @todo check that <code>list</code> does not contain NULL_TAG or ALL_TAG
43 * @todo uncomment check for size of array when backwards
44 * compatibility is deemed safe
45 */
46 public SetTag(ExprTag[] e)
47 {
48 // if (e == null || e.length < 2) {
49 // throw new IllegalArgumentException(
50 // "element array must contain at least 2 elements");
51 // }
52 elements = Arrays.asList(e);
53 }
54
55 /***
56 * Creates a new <code>SetTag</code> for a given collection of tags.
57 * <p><strong>Note: Currently empty and singleton sets are allowed,
58 * but will be made illegal in a future release.</strong></p>
59 *
60 * @param list list of ExprTags.
61 * @throws IllegalArgumentException if <code>list</code> contains
62 * less than 2 elements (IN A FUTURE RELEASE)
63 * @todo check that <code>list</code> does not contain any
64 * <code>null</code>s or duplicates (is a set)
65 * @todo check that <code>list</code> does not contain NULL_TAG or
66 * ALL_TAG
67 * @todo uncomment check for size of array when backwards
68 * compatibility is deemed safe
69 */
70 public SetTag(List /*<ExprTag>*/ list)
71 {
72 assert(list != null) : "null elements";
73 // if (list.size() < 2) {
74 // throw new IllegalArgumentException(
75 // "list must contain at least 2 elements");
76 // }
77 // create our own List from list so as to make this SetTag immutable
78 elements = new LinkedList(list);
79 }
80
81 /***
82 * Creates a new <code>SetTag</code> for a given collection of tags.
83 * <p><strong>Note: Currently empty and singleton sets are allowed,
84 * but will be made illegal in a future release.</strong></p>
85 *
86 * @param c collection of ExprTags.
87 * @deprecated use {@link #SetTag(List)}
88 */
89 public SetTag(Collection /*<ExprTag>*/ c)
90 {
91 assert(c != null) : "null elements";
92 // create our own List from list so as to make this SetTag immutable
93 elements = new LinkedList(c);
94 }
95
96 /***
97 * If <code>that</code> is a <code>SetTag</code>, returns {@link
98 * SetTag#intersect(SetTag)}. Else returns a <code>Tag</code> of
99 * the intersections of <code>that</code> with each <code>Tag</code>
100 * in this <code>SetTag</code> (if the the result is a single
101 * element then that Tag itself is returned.) Otherwise returns
102 * NULL_TAG.
103 * @param that
104 * @return a <code>SetTag</code>, <code>ExprTag</code>, or
105 * <code>Tag.NULL_TAG</code> representing the intersection.
106 * @see jsdsi.Tag#intersect(Tag)
107 **/
108 public Tag intersect(Tag that)
109 {
110 if (that instanceof SetTag)
111 {
112 return intersect((SetTag) that);
113 }
114 LinkedList newTags = new LinkedList();
115 for (Iterator i = this.elements.iterator(); i.hasNext();)
116 {
117 ExprTag thisTag = (ExprTag) i.next();
118 Tag newTag = thisTag.intersect(that);
119 if (newTag instanceof ExprTag)
120 {
121 // excludes ALL_TAG and NULL_TAG
122 newTags.add(newTag);
123 }
124 }
125 if (newTags.isEmpty())
126 {
127 return Tag.NULL_TAG;
128 } else
129 {
130 if (newTags.size() > 1)
131 {
132 reduce(newTags);
133 }
134 if (newTags.size() > 1)
135 {
136 return new SetTag(newTags);
137 } else
138 {
139 return (Tag) newTags.iterator().next();
140 }
141 }
142 }
143
144 /***
145 * Removes duplicate tags and tags implied by others in the list
146 * (ensures that <code>tags</code> is a set).
147 * @param tags
148 */
149 private void reduce(List tags)
150 {
151 int i = 0;
152 while (i < tags.size())
153 {
154 for (int j = tags.size() - 1; j >= 0; j--)
155 {
156 Tag iTag = (Tag) tags.get(i);
157 Tag jTag = (Tag) tags.get(j);
158 if (iTag != jTag)
159 {
160 if (iTag.equals(jTag) || iTag.implies(jTag))
161 {
162 tags.remove(j);
163 }
164 }
165 }
166 i++;
167 }
168 }
169
170 /***
171 * Returns a new Tag whose elements are the all-pairs intersections
172 * of the elements of <code>this</code> and <code>that</code>,
173 * excluding non-ExprTags such as NULL_TAG and ALL_TAG.
174 * @param that
175 * @return the intersection
176 */
177 public Tag intersect(SetTag that)
178 {
179 LinkedList tags = new LinkedList();
180 for (Iterator i = this.elements.iterator(); i.hasNext();)
181 {
182 ExprTag thisTag = (ExprTag) i.next();
183 for (Iterator j = that.elements.iterator(); j.hasNext();)
184 {
185 ExprTag thatTag = (ExprTag) j.next();
186 Tag newTag = thisTag.intersect(thatTag);
187 if (newTag instanceof ExprTag)
188 {
189 // excludes ALL_TAG and NULL_TAG
190 if (!tags.contains(newTag)) {
191 tags.add(newTag);
192 }
193 }
194 }
195 }
196 int len = tags.size();
197 if (len == 0)
198 {
199 return Tag.NULL_TAG;
200 } else if (len == 1)
201 {
202 return (Tag) tags.get(0);
203 } else
204 {
205 return new SetTag(tags);
206 }
207 }
208
209 /***
210 * @see java.lang.Object#equals(Object)
211 */
212 public boolean equals(Object that)
213 {
214 if (that instanceof SetTag)
215 {
216 SetTag other = (SetTag) that;
217 if (elements.size() == other.getElements().length)
218 {
219 Iterator it = elements.iterator();
220 while (it.hasNext())
221 {
222 if (!other.contains((ExprTag) it.next()))
223 {
224 return false;
225 }
226 }
227 return true;
228 }
229 }
230 return false;
231 }
232
233 /***
234 * Returns the index in this list of the first occurrence of the
235 * specified tag, or -1 if this list does not contain this tag.
236 * @param tag tag to search for.
237 * @return the index in this list of the specified tag, or -1 if
238 * this SetTag does not contain this tag.
239 */
240 public int indexOf(ExprTag tag)
241 {
242 return elements.indexOf(tag);
243 }
244
245 /***
246 * Returns <code>true</code> if this SetTag contains the specified
247 * tag.
248 * @param tag tag whose presence in this list is to be tested.
249 * @return <code>true</code> if this list contains the specified
250 * tag.
251 */
252 public boolean contains(ExprTag tag)
253 {
254 return elements.contains(tag);
255 }
256
257 /***
258 * @see java.lang.Object#hashCode()
259 */
260 public int hashCode()
261 {
262 return elements.hashCode();
263 }
264
265 /***
266 * @return the tags of this <code>SetTag</code>.
267 */
268 public ExprTag[] getElements()
269 {
270 return (ExprTag[]) elements.toArray(new ExprTag[0]);
271 }
272
273 /***
274 * @see jsdsi.Tag#toTagSexp()
275 */
276 public Sexp toTagSexp()
277 {
278 Sexp[] ss = new Sexp[elements.size() + 1];
279 ss[0] = SexpUtil.toSexp("set");
280 int i = 1;
281 for (Iterator es = elements.iterator(); es.hasNext();)
282 {
283 ss[i] = ((ExprTag) es.next()).toTagSexp();
284 i++;
285 }
286 return SexpUtil.toSexp("*", ss);
287 }
288
289 /***
290 * @param tbody
291 * @return
292 * @throws SexpParseException
293 */
294 static SetTag parseSetTag(Iterator tbody) throws SexpParseException
295 {
296 ArrayList l = new ArrayList();
297 while (tbody.hasNext())
298 {
299 l.add(ExprTag.parseExprTag(SexpUtil.getNext(tbody, "set tag")));
300 }
301 SexpUtil.checkDone(tbody, "set tag"); // sanity check
302 return new SetTag(l);
303 }
304 }
This page was automatically generated by Maven