1
2 package eu.simuline.util;
3
4 import java.util.Set;
5 import java.util.SortedSet;
6 import java.util.NavigableMap;
7 import java.util.TreeMap;
8 import java.util.Comparator;
9 import java.util.NoSuchElementException; // for javadoc only
10
11 /**
12 * Represents a sorted set with multiplicities based on a {@link TreeMap}.
13 * Mathematically this is something between a set and a family.
14 * Note that this kind of set does not support <code>null</code> elements.
15 *
16 * @param <T>
17 * the class of the elements of this multi-set.
18 *
19 * @author <a href="mailto:ernst.reissner@simuline.eu">Ernst Reissner</a>
20 * @version 1.0
21 */
22 public final class TreeMultiSet<T>
23 extends AbstractMultiSet<NavigableMap<T, MultiSet.Multiplicity>, T>
24 implements SortedMultiSet<T> {
25
26
27 /* -------------------------------------------------------------------- *
28 * constructors. *
29 * -------------------------------------------------------------------- */
30
31 private TreeMultiSet(NavigableMap<T, Multiplicity> t2mult) {
32 super(t2mult);
33 }
34
35 /**
36 * Creates a new, empty <code>MultiSet</code>.
37 */
38 public TreeMultiSet() {
39 this(new TreeMap<T, Multiplicity>());
40 }
41
42 /**
43 * Creates a new, empty <code>MultiSet</code>.
44 */
45 public TreeMultiSet(Comparator<? super T> comp) {
46 this(new TreeMap<T, Multiplicity>(comp));
47 }
48
49 /**
50 * Copy constructor.
51 *
52 * @param other
53 * another <code>MultiSet</code> instance.
54 */
55 public TreeMultiSet(MultiSet<? extends T> other) {
56 this(new TreeMap<T, Multiplicity>(other.getMap()));
57 }
58
59 /**
60 * Creates a multi set with the elements of <code>sSet</code>
61 * and all elements with multiplicity <code>1</code>.
62 *
63 * @param sSet
64 * some instance of a sorted set.
65 */
66 public TreeMultiSet(Set<? extends T> sSet) {
67 this();
68 addAll(sSet);
69 }
70
71 /* -------------------------------------------------------------------- *
72 * methods. *
73 * -------------------------------------------------------------------- */
74
75 /**
76 * Returns the comparator used to order the elements in this set,
77 * or <code>null</code>
78 * if this set uses the natural ordering of its elements.
79 *
80 * @return
81 * the comparator used to order the elements in this set,
82 * or <code>null</code>
83 * if this set uses the natural ordering of its elements.
84 */
85 public Comparator<? super T> comparator() {
86 return this.obj2mult.comparator();
87 }
88
89 /**
90 * Returns the first (lowest) element currently in this set.
91 *
92 * @return
93 * the first (lowest) element currently in this set
94 * @throws NoSuchElementException
95 * if this set is empty.
96 */
97 public T first() {
98 return this.obj2mult.firstKey();
99 }
100
101 /**
102 * Returns the last (highest) element currently in this set.
103 *
104 * @return
105 * the last (highest) element currently in this set.
106 * @throws NoSuchElementException
107 * if this set is empty.
108 */
109 public T last() {
110 return this.obj2mult.lastKey();
111 }
112
113 /**
114 * Returns a view of the portion of this multi-set
115 * whose elements are strictly less than <code>toElement</code>.
116 * The returned multi-set is backed by this multi-set,
117 * so changes in the returned set are reflected in this multi-set,
118 * and vice-versa.
119 * The returned multi-set supports all optional multi-set operations
120 * that this multi-set supports.
121 * <p>
122 * The returned multi-set
123 * will throw an <code>IllegalArgumentException</code>
124 * on an attempt to insert an element outside its range.
125 *
126 * @param toElement
127 * high endpoint (exclusive) of the returned multi-set.
128 * @return
129 * a view of the portion of this multi-set
130 * whose elements are strictly less than <code>toElement</code>.
131 * @throws ClassCastException
132 * if <code>toElement</code> is not compatible
133 * with this multi-set's comparator
134 * (or, if the set has no comparator,
135 * if <code>toElement</code> does not implement {@link Comparable}).
136 * Implementations may, but are not required to,
137 * throw this exception if <code>toElement</code> cannot be compared
138 * to elements currently in this multi-set.
139 * @throws NullPointerException
140 * if <code>toElement</code> is <code>null</code>
141 * and this multi-set does not permit <code>null</code> elements.
142 * @throws IllegalArgumentException
143 * if this multi-set itself has a restricted range,
144 * and <code>toElement</code> lies outside the bounds of the range.
145 */
146 public SortedMultiSet<T> headSet(T toElement) {
147 return new TreeMultiSet<T>(this.obj2mult.headMap(toElement, false));
148 }
149
150 /**
151 * Returns a view of the portion of this multi-set
152 * whose elements are greater than or equal to <code>fromElement</code>.
153 * The returned multi-set is backed by this multi-set,
154 * so changes in the returned set are reflected in this multi-set,
155 * and vice-versa.
156 * The returned multi-set supports all optional multi-set operations
157 * that this multi-set supports.
158 * <p>
159 * The returned multi-set
160 * will throw an <code>IllegalArgumentException</code>
161 * on an attempt to insert an element outside its range.
162 *
163 * @param fromElement
164 * low endpoint (inclusive) of the returned multi-set.
165 * @return
166 * a view of the portion of this multi-set
167 * whose elements are greater than or equal to <code>fromElement</code>.
168 * @throws ClassCastException
169 * if <code>fromElement</code> is not compatible
170 * with this multi-set's comparator
171 * (or, if the set has no comparator,
172 * if <code>fromElement</code> does not implement {@link Comparable}).
173 * Implementations may, but are not required to,
174 * throw this exception if <code>fromElement</code> cannot be compared
175 * to elements currently in this multi-set.
176 * @throws NullPointerException
177 * if <code>fromElement</code> is <code>null</code>
178 * and this multi-set does not permit <code>null</code> elements.
179 * @throws IllegalArgumentException
180 * if this multi-set itself has a restricted range,
181 * and <code>fromElement</code> lies outside the bounds of the range.
182 */
183 public SortedMultiSet<T> tailSet(T fromElement) {
184 return new TreeMultiSet<T>(this.obj2mult.tailMap(fromElement, true));
185 }
186
187 /**
188 * Returns a view of the portion of this multi-set
189 * whose elements range from <code>fromElement</code> inclusively
190 * to <code>toElement</code> exclusively.
191 * The returned multi-set is backed by this multi-set,
192 * so changes in the returned set are reflected in this multi-set,
193 * and vice-versa.
194 * The returned multi-set supports all optional multi-set operations
195 * that this multi-set supports.
196 * <p>
197 * The returned multi-set
198 * will throw an <code>IllegalArgumentException</code>
199 * on an attempt to insert an element outside its range.
200 *
201 * @param fromElement
202 * low endpoint (inclusive) of the returned multi-set.
203 * @param toElement
204 * high endpoint (exclusive) of the returned multi-set.
205 * @return
206 * a view of the portion of this multi-set
207 * from <code>fromElement</code> inclusively
208 * to <code>toElement</code> exclusively.
209 * @throws ClassCastException **** maybe original documentation wrong. ****
210 * if <code>fromElement</code> and <code>toElement</code>
211 * cannot be compared to one another using this set's comparator
212 * (or, if the set has no comparator, using natural ordering).
213 * or if <code>fromElement</code> is not compatible
214 * with this multi-set's comparator
215 * (or, if the set has no comparator,
216 * if <code>fromElement</code> does not implement {@link Comparable}).
217 * Implementations may, but are not required to,
218 * throw this exception
219 * if <code>fromElement</code> or <code>toElement</code>
220 * cannot be compared to elements currently in this multi-set.
221 * @throws NullPointerException
222 * if <code>fromElement</code> or <code>toElement</code>
223 * is <code>null</code>
224 * and this multi-set does not permit <code>null</code> elements.
225 * @throws IllegalArgumentException
226 * if <code>fromElement</code> is greater than <code>toElement</code>
227 * or if this multi-set itself has a restricted range,
228 * and <code>fromElement</code> or <code>toElement</code>
229 * lies outside the bounds of the range.
230 */
231 public SortedMultiSet<T> subSet(T fromElement, T toElement) {
232 return new TreeMultiSet<T>(this.obj2mult.subMap(fromElement, true,
233 toElement, false));
234 }
235
236 /**
237 * Returns a view of the underlying set of this <code>MultiSet</code>.
238 * For certain implementations, this set is immutable
239 * to prevent implicit modification of this <code>MultiSet</code>.
240 *
241 * @return
242 * the <code>Set</code> containing exactly the objects
243 * with strictly positive multiplicity in this <code>MultiSet</code>.
244 */
245 public SortedSet<T> getSet() {
246 return this.obj2mult.navigableKeySet();
247 }
248
249 /**
250 * Returns a view of the underlying map of this <code>SortedMultiSet</code>
251 * as a map mapping each entry to its multiplicity.
252 */
253 public NavigableMap<T, Multiplicity> getMap() {
254 return this.obj2mult;
255 }
256
257 public String toString() {
258 return "<MultiSet comparator=\"" + this.obj2mult.comparator() +
259 "\">" + this.obj2mult + "</MultiSet>";
260 }
261
262 }