1
2 package eu.simuline.util;
3
4 import java.util.Collection;
5 import java.util.Set;
6 import java.util.Map;
7 import java.util.Iterator; // for docs only
8
9 /**
10 * Represents a set with multiplicities.
11 * Mathematically this is something between a set and a family.
12 * Note that implementations of this kind of set
13 * need not support <code>null</code> elements.
14 * <p>
15 * Allows also to create an immutable <code>MultiSet</code>
16 * either from a set or as a copy of another <code>MultiSet</code>.
17 * <p>
18 * Note that this should extend Collection, but still does not *****.
19 * maybe it should even extend Set.
20 *
21 * @param <T>
22 * the class of the elements of this multi-set.
23 *
24 * @author <a href="mailto:ernst.reissner@simuline.eu">Ernst Reissner</a>
25 * @version 1.0
26 */
27 public interface MultiSet<T> extends Iterable<T> {
28
29 /* -------------------------------------------------------------------- *
30 * inner classes. *
31 * -------------------------------------------------------------------- */
32
33 /**
34 * Represents the multiplicity of an entry of the enclosing multi-set.
35 */
36 interface Multiplicity extends Comparable<Multiplicity> {
37
38 /**
39 * Sets the multiplicity wrapped by this object
40 * to the specified value.
41 *
42 * @param mult
43 * a strictly positive <code>int</code> value
44 * representing the old multiplicity.
45 * @throws IllegalArgumentException
46 * if <code>mult</code> is not strictly positive.
47 * @throws UnsupportedOperationException
48 * if setting the multiplicity would modify this Multiplicity object
49 * in a way which is not supported.
50 */
51 int set(int mult);
52
53 /**
54 * Adds the specified multiplicity (which may well be negative)
55 * to the wrapped multiplicity which is thus modified.
56 *
57 * @param mult
58 * an <code>int</code> such that <code>this.mult + mult > 0</code>
59 * holds.
60 * @return
61 * the new multiplicity <code>this.mult + mult</code>.
62 * @throws IllegalArgumentException
63 * if <code>this.mult + mult < 0</code> holds.
64 * @throws IllegalStateException
65 * if <code>this.mult + mult == 0</code> holds.
66 * This cannot occur: if it does this is a bug within this class.
67 * @throws UnsupportedOperationException
68 * if setting the multiplicity would modify this Multiplicity object
69 * in a way which is not supported.
70 */
71 int add(int mult);
72
73 /**
74 * Returns the wrapped multiplicity.
75 */
76 int get();
77
78 /**
79 * Defines the natural ordering on natural numbers.
80 *
81 * @param mult
82 * a <code>Multiplicity</code> which should in fact
83 * be another {@link MultiSet.Multiplicity}.
84 * @return
85 * the difference of the wrapped multiplicities.
86 * @throws NullPointerException
87 * for <code>mult == null</code>.
88 * @throws ClassCastException
89 * if <code>mult</code> is neither <code>null</code>
90 * nor an instance of {@link MultiSet.Multiplicity}.
91 */
92 int compareTo(Multiplicity mult);
93
94 boolean equals(Object obj);
95 } // class Multiplicity
96
97 /* -------------------------------------------------------------------- *
98 * class constants. *
99 * -------------------------------------------------------------------- */
100
101
102 /* -------------------------------------------------------------------- *
103 * fields. *
104 * -------------------------------------------------------------------- */
105
106 /* -------------------------------------------------------------------- *
107 * methods. *
108 * -------------------------------------------------------------------- */
109
110 // Query Operations
111
112 /**
113 * Returns the number of pairwise different elements
114 * in this <code>MultiSet</code>.
115 * If this <code>MultiSet</code>
116 * contains more than <tt>Integer.MAX_VALUE</tt> elements,
117 * returns <tt>Integer.MAX_VALUE</tt>.
118 *
119 * @return
120 * the number of elements in this <code>MultiSet</code>
121 * each multiple element counted as a single one.
122 * @see #sizeWithMult()
123 */
124 int size();
125
126 /**
127 * Returns the number of elements
128 * in this <code>MultiSet</code> counted with multiplicities.
129 * If this <code>MultiSet</code>
130 * contains more than <tt>Integer.MAX_VALUE</tt> elements,
131 * returns <tt>Integer.MAX_VALUE</tt>.
132 *
133 * @return
134 * the number of elements in this <code>MultiSet</code>
135 * counted with multiplicities,
136 * provided this does not exceed {@link Integer#MAX_VALUE};
137 * otherwise just {@link Integer#MAX_VALUE}.
138 * @see #size()
139 */
140 int sizeWithMult();
141
142 /**
143 * Returns whether this multiple set contains no element.
144 *
145 * @return
146 * whether this multiple set contains no element.
147 */
148 boolean isEmpty();
149
150 /**
151 * Returns one of the elements in this multiple set
152 * with maximal multiplicity.
153 * The return value is <code>null</code>
154 * if and only if this set is empty.
155 *
156 * @return
157 * a <code>Object o != null</code> with maximal multiplicity
158 * or <code>null</code> if this multiple set is empty.
159 * @see #isEmpty
160 */
161 Object getObjWithMaxMult();
162
163 /**
164 * Returns the maximal multiplicity of an element in this set.
165 * In particular for empty sets returns <code>0</code>.
166 *
167 * @return
168 * a non-negative <code>int</code> value
169 * which is the maximal mutliplicity of an element in this set.
170 * In particular this is <code>0</code>
171 * if and only if this set is empty.
172 */
173 int getMaxMult();
174
175 /**
176 * Returns the multiplicity
177 * with which the given object occurs within this set.
178 *
179 * @param obj
180 * an <code>Object</code> and not null.
181 * @return
182 * a non-negative <code>int</code> value
183 * which is the mutliplicity of the given element in this set.
184 * In particular this is <code>0</code> if and only if
185 * <code>obj</code> is an instance which is not in this set.
186 * @throws NullPointerException
187 * for <code>obj==null</code>.
188 * @see #setMultiplicity(Object, int)
189 * @see #getMultiplicityObj(Object)
190 */
191 int getMultiplicity(Object obj);
192
193 /**
194 * Returns the multiplicity object of the given object in this set
195 * or <code>null</code>.
196 *
197 * @param obj
198 * an <code>Object</code> and not null.
199 * @return
200 * If <code>obj</code> is an instance which is in this set,
201 * a multiplicity object wrapping the multiplicity is returned.
202 * If <code>obj</code> is an instance which is not in this set,
203 * <code>null</code> is returned.
204 * @throws NullPointerException
205 * for <code>obj==null</code>.
206 * @see #getMultiplicity(Object)
207 */
208 Multiplicity getMultiplicityObj(Object obj);
209
210 /**
211 * Returns <tt>true</tt> if this <code>MultiSet</code>
212 * contains the specified element.
213 * More formally, returns <tt>true</tt> if and only if this
214 * <code>MultiSet</code> contains at least one element <tt>e</tt>
215 * such that <tt>(o==null ? e==null : o.equals(e))</tt>.
216 *
217 * @param obj
218 * element (not <code>null</code>)
219 * whose presence in this <code>MultiSet</code> is to be tested.
220 * @return
221 * <tt>true</tt> if this <code>MultiSet</code>
222 * contains the specified element.
223 * @throws NullPointerException
224 * for <code>obj==null</code>.
225 */
226 boolean contains(Object obj);
227
228 /**
229 * Returns an iterator over the elements in this collection
230 * which emits each element exactly once,
231 * without regarding its multiplicity.
232 * <!-- There are no guarantees concerning the order
233 * in which the elements are returned
234 * (unless this collection is an instance of some class
235 * that provides a guarantee). -->
236 * For certain implementations, the iterator returned
237 * does not allow modifications of the underlying (multi-)set.
238 *
239 * @return
240 * an <tt>Iterator</tt> over the elements in this collection
241 * considering each element exactly once ignoring its multiplicity.
242 */
243 MultiSetIterator<T> iterator();
244
245 /**
246 * Returns an array containing all of the elements
247 * in this <code>MultiSet</code> exactly once, ignoring its multiplicity.
248 * <!--
249 * If the <code>MultiSet</code> makes any guarantees
250 * as to what order its elements are returned by its iterator,
251 * this method must return the elements in the same order.
252 * -->
253 * <p>
254 * The returned array will be "safe" in that no references to it
255 * are maintained by this <code>MultiSet</code>.
256 * (In other words, this method must allocate a new array
257 * even if this <code>MultiSet</code> is backed by an array).
258 * The caller is thus free to modify the returned array.
259 * <!-- <p>
260 * This method acts as bridge
261 * between array-based and collection-based APIs. -->
262 *
263 * @return
264 * an array containing all of the elements in this collection
265 * @see #iterator
266 */
267 Object[] toArray();
268
269 /**
270 * Returns an array containing all of the elements
271 * in this <code>MultiSet</code>;
272 * the runtime type of the returned array is that of the specified array.
273 * If the <code>MultiSet</code> fits in the specified array,
274 * it is returned therein.
275 * Otherwise, a new array is allocated with the runtime type
276 * of the specified array and the size of this <code>MultiSet</code>.
277 * <p>
278 * If this <code>MultiSet</code> fits in the specified array
279 * with room to spare
280 * (i.e., the array has more elements than this <code>MultiSet</code>),
281 * the elementin the array
282 * immediately following the end of the <code>MultiSet</code>
283 * is set to <tt>null</tt>.
284 * This is useful in determining the length of this
285 * <code>MultiSet</code> because this <code>MultiSet</code> does
286 * not contain any <tt>null</tt> elements.
287 * <p>
288 * <!--
289 * If this <code>MultiSet</code> makes any guarantees
290 * as to what order its elements are returned by its iterator,
291 * this method must return the elements in
292 * the same order.
293 * -->
294 * <!--
295 * <p>
296 * Like the <tt>toArray</tt> method, this method acts as bridge between
297 * array-based and collection-based APIs. Further, this method allows
298 * precise control over the runtime type of the output array, and may,
299 * under certain circumstances, be used to save allocation costs.
300 * <p>
301 * -->
302 * Suppose <tt>l</tt> is a <tt>List</tt> known to contain only strings.
303 * The following code can be used to dump the list into a newly allocated
304 * array of <tt>String</tt>:
305 *
306 * <pre>
307 * String[] x = (String[]) v.toArray(new String[0]);
308 * </pre><p>
309 *
310 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
311 * <tt>toArray()</tt>.
312 *
313 * @param arr
314 * the array into which the elements of this <code>MultiSet</code>
315 * are to be stored, if it is big enough;
316 * otherwise, a new array of the same runtime type
317 * is allocated for this purpose.
318 * @return
319 * an array containing each elements of this <code>MultiSet</code>
320 * exactly once.
321 * @throws ArrayStoreException
322 * the runtime type of the specified array is not a supertype
323 * of the runtime type of every element in this <code>MultiSet</code>.
324 * @throws NullPointerException
325 * if the specified array is <tt>null</tt>.
326 */
327 T[] toArray(T[] arr);
328 // Modification Operations
329
330 /**
331 * Adds <code>obj</code> to this <code>MultiSet</code>
332 * and returns the new multiplicity of this object.
333 * In other words, increments the multiplicity of <code>obj</code> by one.
334 * This is a special case of {@link #addWithMult(Object obj, int addMult)}
335 * with <code>addMult==1</code>.
336 *
337 * @param obj
338 * a <code>Object</code>.
339 * Note that this object may not be <code>null</code>.
340 * @return
341 * a strictly positive <code>int</code> value:
342 * the new multiplicity of <code>obj</code>.
343 * @throws NullPointerException
344 * if the specified element is null.
345 * @throws UnsupportedOperationException
346 * if this <code>MultiSet</code> does not support this method.
347 */
348 int addWithMult(T obj);
349
350 /**
351 * Increases the multiplicity of <code>obj</code>
352 * in this <code>MultiSet</code>
353 * by the specified value <code>addMult</code>
354 * and returns the new multiplicity of this object.
355 * This generalizes {@link #addWithMult(Object obj)}
356 * with <code>addMult==1</code>.
357 *
358 * @param obj
359 * an <code>Object</code> instance.
360 * @param addMult
361 * a non-negative integer specifying the multiplicity
362 * with which <code>obj</code> is to be added.
363 * @return
364 * a non-negative <code>int</code> value:
365 * the new multiplicity of <code>obj</code>.
366 * @throws IllegalArgumentException
367 * for <code>addMult < 0</code>.
368 * @throws NullPointerException
369 * for <code>obj==null</code> provided <code>addMult ≥ 0</code>.
370 * @throws UnsupportedOperationException
371 * if this <code>MultiSet</code> does not support this method.
372 */
373 int addWithMult(T obj, int addMult);
374
375 /**
376 * Adds <code>obj</code> to this <code>MultiSet</code>.
377 * In other words, increments the multiplicity of <code>obj</code> by one.
378 * Returns <tt>true</tt> if this <code>MultiSet</code>
379 * interpreted as a set changed as a result of the call.
380 * (Returns <tt>false</tt> if this <code>MultiSet</code>
381 * already contains the specified element (with nontrivial multiplicity).
382 * <!--
383 * <p>
384 * <Code>MultiSet</Code>s that support this operation
385 * may place limitations on what elements may be added
386 * to this <code>MultiSet</code>.
387 * In particular, some<code>MultiSet</code>s will refuse
388 * to add <tt>null</tt> elements, and others will impose restrictions
389 * on the type of elements that may be added.
390 * <Code>MultiSet</Code> classes should clearly specify
391 * in their documentation any
392 * restrictions on what elements may be added.
393 * <p>
394 * If a <code>MultiSet</code> refuses to add a particular element
395 * for any reason other than that it already contains the element,
396 * it <i>must</i> throw an exception
397 * (rather than returning <tt>false</tt>).
398 * This preservesthe invariant
399 * that a <code>MultiSet</code> always contains the specified element
400 * after this call returns.
401 * -->
402 *
403 * @param obj
404 * element the multiplicity of which in this <code>MultiSet</code>
405 * is to be increased by one.
406 * Note that this may not be <code>null</code>.
407 * @return
408 * <tt>true</tt> if and only if
409 * the multiplicity of the specified element
410 * was <code>0</code> before the call of this method.
411 * @throws NullPointerException
412 * if the specified element is <code>null</code>.
413 * @throws UnsupportedOperationException
414 * if this <code>MultiSet</code> does not support this method.
415 */
416 boolean add(T obj);
417
418 /**
419 * Decrements the multiplicity of <code>obj</code>
420 * in this <code>MultiSet</code> if it is present and
421 * returns the <em>old</em> multiplicity of <code>obj</code>;
422 * If this is <code>0</code> returns
423 * without altering this <code>MultiSet</code>.
424 *
425 * @param obj
426 * a <code>Object</code>.
427 * Note that this object may not be <code>null</code>.
428 * @return
429 * a non-negative <code>int</code> value:
430 * the old multiplicity of <code>obj</code>
431 * before a potential modification of this <code>MultiSet</code>.
432 * @throws NullPointerException
433 * if the specified element is null.
434 * @throws UnsupportedOperationException
435 * if this <code>MultiSet</code> does not support this method.
436 */
437 int removeWithMult(Object obj);
438
439 /**
440 * Decreases the multiplicity of <code>obj</code>
441 * in this <code>MultiSet</code>
442 * by the specified value <code>removeMult</code> if possible
443 * and returns the <em>old</em> multiplicity of <code>obj</code>.
444 *
445 * @param obj
446 * an <code>Object</code> instance.
447 * @param removeMult
448 * a non-negative integer specifying the multiplicity
449 * with which <code>obj</code> is to be removed.
450 * @return
451 * a non-negative <code>int</code> value:
452 * the old multiplicity of <code>obj</code>
453 * before a potential modification of this <code>MultiSet</code>.
454 * @throws NullPointerException
455 * for <code>obj == null</code>.
456 * @throws IllegalArgumentException
457 * for <code>removeMult < 0</code> and also if
458 * <code>removeMult - obj.getMultiplicity() < 0</code>.
459 * @throws UnsupportedOperationException
460 * if this <code>MultiSet</code> does not support this method.
461 */
462 int removeWithMult(Object obj, int removeMult);
463
464 /**
465 * Removes <em>all</em> instances of the specified element from this
466 * <code>MultiSet</code>, if it is present with nontrivial multiplicity.
467 * More formally, immediately after having (successively) invoked
468 * <code>s.remove(o)</code>,
469 * the condition <code>s.contains(o) == false</code> is satisfied.
470 * Returns true if this <code>MultiSet</code> contained the specified
471 * element (or equivalently, if (the underlying set of)
472 * this <code>MultiSet</code> changed as a result of the call).
473 *
474 * @param obj
475 * element the multiplicity of which in this <code>MultiSet</code>
476 * is to be increased by one.
477 * @return
478 * <tt>true</tt> if and only if this <code>MultiSet</code> changed
479 * as a result of the call.
480 * @throws NullPointerException
481 * if the specified element is <code>null</code>.
482 * @throws UnsupportedOperationException
483 * if this <code>MultiSet</code> does not support this method.
484 */
485 boolean remove(Object obj);
486
487 /**
488 * Sets the multiplicity of <code>obj</code> to the value
489 * specified by <code>mult</code>.
490 *
491 * @param obj
492 * an <code>Object</code> instance.
493 * @param newMult
494 * a non-negative <code>int</code> value.
495 * @return
496 * the old multiplicity of <code>obj</code>
497 * as a non-negative <code>int</code> value.
498 * @throws IllegalArgumentException
499 * if either <code>obj == null</code> or <code>mult ≤ 0</code>.
500 * @throws UnsupportedOperationException
501 * if this <code>MultiSet</code> does not support this method.
502 * @see #getMultiplicity(Object)
503 */
504 int setMultiplicity(T obj, int newMult);
505
506 // Bulk Operations
507
508 /**
509 * Returns <tt>true</tt> if this <code>MultiSet</code>
510 * contains all of the elements in the specified collection
511 * with strictly positive multiplicity.
512 *
513 * @param coll
514 * collection to be checked for containment
515 * in this <code>MultiSet</code>.
516 * @return
517 * <tt>true</tt> if this <code>MultiSet</code>
518 * contains all of the elements in the specified collection.
519 * @throws NullPointerException
520 * if the specified collection contains one or more null elements.
521 * @throws NullPointerException
522 * if the specified collection is <tt>null</tt>.
523 * @see #contains(Object)
524 */
525 boolean containsAll(Collection<?> coll);
526
527 /**
528 * Adds <code>mvs</code> elementwise to this multi set
529 * taking multiplicities into account
530 * and returns whether this caused a change
531 * of the underlying set.
532 * **** strange implementation; also: change
533 *
534 * @param mvs
535 * a <code>MultiSet</code> object.
536 * @return
537 * returns whether adding changed this <code>MultiSet</code>
538 * interpreted as a set.
539 * @throws UnsupportedOperationException
540 * if this <code>MultiSet</code> does not support this method.
541 */
542 boolean addAll(MultiSet<? extends T> mvs);
543
544 /**
545 * Adds <code>set</code> elementwise to this multi set
546 * increasing multiplicities
547 * and returns whether this caused a change
548 * of the underlying set.
549 * **** strange implementation; also: change
550 *
551 * @param set
552 * a <code>Set</code> object.
553 * @return
554 * returns whether adding changed this <code>MultiSet</code>
555 * interpreted as a set.
556 * @throws UnsupportedOperationException
557 * if this <code>MultiSet</code> does not support this method.
558 */
559 boolean addAll(Set<? extends T> set);
560
561 /**
562 * Removes all this <code>MultiSet</code>'s elements
563 * that are also contained in the specified collection.
564 * After this call returns, this <code>MultiSet</code>
565 * will contain no elements in common with the specified collection.
566 *
567 * @param coll
568 * elements to be removed from this <code>MultiSet</code>.
569 * @return
570 * <tt>true</tt> if this <code>MultiSet</code>
571 * changed as a result of the call.
572 * @throws NullPointerException
573 * if the specified collection is <code>null</code>.
574 * @throws UnsupportedOperationException
575 * if this <code>MultiSet</code> does not support this method.
576 * @see #remove(Object)
577 * @see #contains(Object)
578 */
579 boolean removeAll(Collection<?> coll);
580
581 /**
582 * Retains only the elements in this <code>MultiSet</code>
583 * that are contained in the specified collection.
584 * In other words, removes from this <code>MultiSet</code>
585 * all of its elements that are not contained
586 * in the specified collection.
587 *
588 * @param coll
589 * elements to be retained in this <code>MultiSet</code>.
590 * @return
591 * <tt>true</tt> if this <code>MultiSet</code> changed
592 * as a result of the call.
593 * @throws NullPointerException
594 * if the specified collection is <tt>null</tt>.
595 * @throws UnsupportedOperationException
596 * if this <code>MultiSet</code> does not support this method.
597 * @see #remove(Object)
598 * @see #contains(Object)
599 */
600 boolean retainAll(Collection<?> coll);
601
602 /**
603 * Removes all of the elements from this <code>MultiSet</code>.
604 * This <code>MultiSet</code> will be empty after this method returns.
605 *
606 * @throws UnsupportedOperationException
607 * if this <code>MultiSet</code> does not support this method.
608 */
609 void clear();
610
611 /**
612 * Returns a view of the underlying set of this <code>MultiSet</code>.
613 * For certain implementations, this set is immutable
614 * to prevent implicit modification of this <code>MultiSet</code>.
615 *
616 * @return
617 * the <code>Set</code> containing exactly the objects
618 * with strictly positive multiplicity in this <code>MultiSet</code>.
619 */
620 Set<T> getSet();
621
622 /**
623 * Returns a view of the underlying map of this <code>MultiSet</code>
624 * as a map mapping each entry to its multiplicity.
625 */
626 Map<T, Multiplicity> getMap();
627
628 /**
629 * Returns a Set view of the mapping
630 * from the element of this <code>MultiSet</code>
631 * to the according multiplicities.
632 * The set is backed by the <code>MultiSet</code>,
633 * so changes to the map are reflected in the set, and vice-versa.
634 * If the <code>MultiSet</code> is modified
635 * while an iteration over the set is in progress
636 * (except through the iterator's own remove operation,
637 * or through the setValue operation on a map entry
638 * returned by the iterator) the results of the iteration are undefined.
639 * The set may support element removal,
640 * which removes the corresponding element from the <code>MultiSet</code>,
641 * via the {@link Iterator#remove()}, {@link Set#remove(Object)},
642 * {@link Set#removeAll(Collection)}, {@link Set#retainAll(Collection)}
643 * and {@link #clear()} operations.
644 * It does not support the methods
645 * {@link #add(Object)} or {@link Set#addAll(Collection)}.
646 */
647 Set<Map.Entry<T, Multiplicity>> getSetWithMults();
648
649 String toString();
650
651 /**
652 * Returns <code>true</code> if and only if <code>obj</code>
653 * is also a <code>MultiSet</code>
654 * and contains the same elements with the same multiplicities
655 * as this one.
656 *
657 * @param obj
658 * an <code>Object</code>, possibly <code>null</code>.
659 * @return
660 * a <code>true</code> if and only if <code>obj</code>
661 * is also a <code>MultiSet</code>
662 * and contains the same elements with the same multiplicities
663 * as this one.
664 */
665 boolean equals(Object obj);
666
667 int hashCode();
668 }