1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections;
18
19 import java.lang.reflect.Array;
20 import java.util.ArrayList;
21 import java.util.Collection;
22 import java.util.Enumeration;
23 import java.util.HashMap;
24 import java.util.HashSet;
25 import java.util.Iterator;
26 import java.util.List;
27 import java.util.ListIterator;
28 import java.util.Map;
29 import java.util.Set;
30
31 import org.apache.commons.collections.collection.PredicatedCollection;
32 import org.apache.commons.collections.collection.SynchronizedCollection;
33 import org.apache.commons.collections.collection.TransformedCollection;
34 import org.apache.commons.collections.collection.TypedCollection;
35 import org.apache.commons.collections.collection.UnmodifiableBoundedCollection;
36 import org.apache.commons.collections.collection.UnmodifiableCollection;
37
38 /**
39 * Provides utility methods and decorators for {@link Collection} instances.
40 *
41 * @since Commons Collections 1.0
42 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
43 *
44 * @author Rodney Waldhoff
45 * @author Paul Jack
46 * @author Stephen Colebourne
47 * @author Steve Downey
48 * @author Herve Quiroz
49 * @author Peter KoBek
50 * @author Matthew Hawthorne
51 * @author Janek Bogucki
52 * @author Phil Steitz
53 * @author Steven Melzer
54 * @author Jon Schewe
55 * @author Neil O'Toole
56 * @author Stephen Smith
57 */
58 public class CollectionUtils {
59
60 /** Constant to avoid repeated object creation */
61 private static Integer INTEGER_ONE = new Integer(1);
62
63 /**
64 * An empty unmodifiable collection.
65 * The JDK provides empty Set and List implementations which could be used for
66 * this purpose. However they could be cast to Set or List which might be
67 * undesirable. This implementation only implements Collection.
68 */
69 public static final Collection EMPTY_COLLECTION = UnmodifiableCollection.decorate(new ArrayList());
70
71 /**
72 * <code>CollectionUtils</code> should not normally be instantiated.
73 */
74 public CollectionUtils() {
75 }
76
77 /**
78 * Returns a {@link Collection} containing the union
79 * of the given {@link Collection}s.
80 * <p>
81 * The cardinality of each element in the returned {@link Collection}
82 * will be equal to the maximum of the cardinality of that element
83 * in the two given {@link Collection}s.
84 *
85 * @param a the first collection, must not be null
86 * @param b the second collection, must not be null
87 * @return the union of the two collections
88 * @see Collection#addAll
89 */
90 public static Collection union(final Collection a, final Collection b) {
91 ArrayList list = new ArrayList();
92 Map mapa = getCardinalityMap(a);
93 Map mapb = getCardinalityMap(b);
94 Set elts = new HashSet(a);
95 elts.addAll(b);
96 Iterator it = elts.iterator();
97 while(it.hasNext()) {
98 Object obj = it.next();
99 for(int i=0,m=Math.max(getFreq(obj,mapa),getFreq(obj,mapb));i<m;i++) {
100 list.add(obj);
101 }
102 }
103 return list;
104 }
105
106 /**
107 * Returns a {@link Collection} containing the intersection
108 * of the given {@link Collection}s.
109 * <p>
110 * The cardinality of each element in the returned {@link Collection}
111 * will be equal to the minimum of the cardinality of that element
112 * in the two given {@link Collection}s.
113 *
114 * @param a the first collection, must not be null
115 * @param b the second collection, must not be null
116 * @return the intersection of the two collections
117 * @see Collection#retainAll
118 * @see #containsAny
119 */
120 public static Collection intersection(final Collection a, final Collection b) {
121 ArrayList list = new ArrayList();
122 Map mapa = getCardinalityMap(a);
123 Map mapb = getCardinalityMap(b);
124 Set elts = new HashSet(a);
125 elts.addAll(b);
126 Iterator it = elts.iterator();
127 while(it.hasNext()) {
128 Object obj = it.next();
129 for(int i=0,m=Math.min(getFreq(obj,mapa),getFreq(obj,mapb));i<m;i++) {
130 list.add(obj);
131 }
132 }
133 return list;
134 }
135
136 /**
137 * Returns a {@link Collection} containing the exclusive disjunction
138 * (symmetric difference) of the given {@link Collection}s.
139 * <p>
140 * The cardinality of each element <i>e</i> in the returned {@link Collection}
141 * will be equal to
142 * <tt>max(cardinality(<i>e</i>,<i>a</i>),cardinality(<i>e</i>,<i>b</i>)) - min(cardinality(<i>e</i>,<i>a</i>),cardinality(<i>e</i>,<i>b</i>))</tt>.
143 * <p>
144 * This is equivalent to
145 * <tt>{@link #subtract subtract}({@link #union union(a,b)},{@link #intersection intersection(a,b)})</tt>
146 * or
147 * <tt>{@link #union union}({@link #subtract subtract(a,b)},{@link #subtract subtract(b,a)})</tt>.
148 *
149 * @param a the first collection, must not be null
150 * @param b the second collection, must not be null
151 * @return the symmetric difference of the two collections
152 */
153 public static Collection disjunction(final Collection a, final Collection b) {
154 ArrayList list = new ArrayList();
155 Map mapa = getCardinalityMap(a);
156 Map mapb = getCardinalityMap(b);
157 Set elts = new HashSet(a);
158 elts.addAll(b);
159 Iterator it = elts.iterator();
160 while(it.hasNext()) {
161 Object obj = it.next();
162 for(int i=0,m=((Math.max(getFreq(obj,mapa),getFreq(obj,mapb)))-(Math.min(getFreq(obj,mapa),getFreq(obj,mapb))));i<m;i++) {
163 list.add(obj);
164 }
165 }
166 return list;
167 }
168
169 /**
170 * Returns a new {@link Collection} containing <tt><i>a</i> - <i>b</i></tt>.
171 * The cardinality of each element <i>e</i> in the returned {@link Collection}
172 * will be the cardinality of <i>e</i> in <i>a</i> minus the cardinality
173 * of <i>e</i> in <i>b</i>, or zero, whichever is greater.
174 *
175 * @param a the collection to subtract from, must not be null
176 * @param b the collection to subtract, must not be null
177 * @return a new collection with the results
178 * @see Collection#removeAll
179 */
180 public static Collection subtract(final Collection a, final Collection b) {
181 ArrayList list = new ArrayList( a );
182 for (Iterator it = b.iterator(); it.hasNext();) {
183 list.remove(it.next());
184 }
185 return list;
186 }
187
188 /**
189 * Returns <code>true</code> iff at least one element is in both collections.
190 * <p>
191 * In other words, this method returns <code>true</code> iff the
192 * {@link #intersection} of <i>coll1</i> and <i>coll2</i> is not empty.
193 *
194 * @param coll1 the first collection, must not be null
195 * @param coll2 the first collection, must not be null
196 * @return <code>true</code> iff the intersection of the collections is non-empty
197 * @since 2.1
198 * @see #intersection
199 */
200 public static boolean containsAny(final Collection coll1, final Collection coll2) {
201 if (coll1.size() < coll2.size()) {
202 for (Iterator it = coll1.iterator(); it.hasNext();) {
203 if (coll2.contains(it.next())) {
204 return true;
205 }
206 }
207 } else {
208 for (Iterator it = coll2.iterator(); it.hasNext();) {
209 if (coll1.contains(it.next())) {
210 return true;
211 }
212 }
213 }
214 return false;
215 }
216
217 /**
218 * Returns a {@link Map} mapping each unique element in the given
219 * {@link Collection} to an {@link Integer} representing the number
220 * of occurrences of that element in the {@link Collection}.
221 * <p>
222 * Only those elements present in the collection will appear as
223 * keys in the map.
224 *
225 * @param coll the collection to get the cardinality map for, must not be null
226 * @return the populated cardinality map
227 */
228 public static Map getCardinalityMap(final Collection coll) {
229 Map count = new HashMap();
230 for (Iterator it = coll.iterator(); it.hasNext();) {
231 Object obj = it.next();
232 Integer c = (Integer) (count.get(obj));
233 if (c == null) {
234 count.put(obj,INTEGER_ONE);
235 } else {
236 count.put(obj,new Integer(c.intValue() + 1));
237 }
238 }
239 return count;
240 }
241
242 /**
243 * Returns <tt>true</tt> iff <i>a</i> is a sub-collection of <i>b</i>,
244 * that is, iff the cardinality of <i>e</i> in <i>a</i> is less
245 * than or equal to the cardinality of <i>e</i> in <i>b</i>,
246 * for each element <i>e</i> in <i>a</i>.
247 *
248 * @param a the first (sub?) collection, must not be null
249 * @param b the second (super?) collection, must not be null
250 * @return <code>true</code> iff <i>a</i> is a sub-collection of <i>b</i>
251 * @see #isProperSubCollection
252 * @see Collection#containsAll
253 */
254 public static boolean isSubCollection(final Collection a, final Collection b) {
255 Map mapa = getCardinalityMap(a);
256 Map mapb = getCardinalityMap(b);
257 Iterator it = a.iterator();
258 while (it.hasNext()) {
259 Object obj = it.next();
260 if (getFreq(obj, mapa) > getFreq(obj, mapb)) {
261 return false;
262 }
263 }
264 return true;
265 }
266
267 /**
268 * Returns <tt>true</tt> iff <i>a</i> is a <i>proper</i> sub-collection of <i>b</i>,
269 * that is, iff the cardinality of <i>e</i> in <i>a</i> is less
270 * than or equal to the cardinality of <i>e</i> in <i>b</i>,
271 * for each element <i>e</i> in <i>a</i>, and there is at least one
272 * element <i>f</i> such that the cardinality of <i>f</i> in <i>b</i>
273 * is strictly greater than the cardinality of <i>f</i> in <i>a</i>.
274 * <p>
275 * The implementation assumes
276 * <ul>
277 * <li><code>a.size()</code> and <code>b.size()</code> represent the
278 * total cardinality of <i>a</i> and <i>b</i>, resp. </li>
279 * <li><code>a.size() < Integer.MAXVALUE</code></li>
280 * </ul>
281 *
282 * @param a the first (sub?) collection, must not be null
283 * @param b the second (super?) collection, must not be null
284 * @return <code>true</code> iff <i>a</i> is a <i>proper</i> sub-collection of <i>b</i>
285 * @see #isSubCollection
286 * @see Collection#containsAll
287 */
288 public static boolean isProperSubCollection(final Collection a, final Collection b) {
289 return (a.size() < b.size()) && CollectionUtils.isSubCollection(a,b);
290 }
291
292 /**
293 * Returns <tt>true</tt> iff the given {@link Collection}s contain
294 * exactly the same elements with exactly the same cardinalities.
295 * <p>
296 * That is, iff the cardinality of <i>e</i> in <i>a</i> is
297 * equal to the cardinality of <i>e</i> in <i>b</i>,
298 * for each element <i>e</i> in <i>a</i> or <i>b</i>.
299 *
300 * @param a the first collection, must not be null
301 * @param b the second collection, must not be null
302 * @return <code>true</code> iff the collections contain the same elements with the same cardinalities.
303 */
304 public static boolean isEqualCollection(final Collection a, final Collection b) {
305 if(a.size() != b.size()) {
306 return false;
307 } else {
308 Map mapa = getCardinalityMap(a);
309 Map mapb = getCardinalityMap(b);
310 if(mapa.size() != mapb.size()) {
311 return false;
312 } else {
313 Iterator it = mapa.keySet().iterator();
314 while(it.hasNext()) {
315 Object obj = it.next();
316 if(getFreq(obj,mapa) != getFreq(obj,mapb)) {
317 return false;
318 }
319 }
320 return true;
321 }
322 }
323 }
324
325 /**
326 * Returns the number of occurrences of <i>obj</i> in <i>coll</i>.
327 *
328 * @param obj the object to find the cardinality of
329 * @param coll the collection to search
330 * @return the the number of occurrences of obj in coll
331 */
332 public static int cardinality(Object obj, final Collection coll) {
333 if (coll instanceof Set) {
334 return (coll.contains(obj) ? 1 : 0);
335 }
336 if (coll instanceof Bag) {
337 return ((Bag) coll).getCount(obj);
338 }
339 int count = 0;
340 if (obj == null) {
341 for (Iterator it = coll.iterator();it.hasNext();) {
342 if (it.next() == null) {
343 count++;
344 }
345 }
346 } else {
347 for (Iterator it = coll.iterator();it.hasNext();) {
348 if (obj.equals(it.next())) {
349 count++;
350 }
351 }
352 }
353 return count;
354 }
355
356 /**
357 * Finds the first element in the given collection which matches the given predicate.
358 * <p>
359 * If the input collection or predicate is null, or no element of the collection
360 * matches the predicate, null is returned.
361 *
362 * @param collection the collection to search, may be null
363 * @param predicate the predicate to use, may be null
364 * @return the first element of the collection which matches the predicate or null if none could be found
365 */
366 public static Object find(Collection collection, Predicate predicate) {
367 if (collection != null && predicate != null) {
368 for (Iterator iter = collection.iterator(); iter.hasNext();) {
369 Object item = iter.next();
370 if (predicate.evaluate(item)) {
371 return item;
372 }
373 }
374 }
375 return null;
376 }
377
378 /**
379 * Executes the given closure on each element in the collection.
380 * <p>
381 * If the input collection or closure is null, there is no change made.
382 *
383 * @param collection the collection to get the input from, may be null
384 * @param closure the closure to perform, may be null
385 */
386 public static void forAllDo(Collection collection, Closure closure) {
387 if (collection != null && closure != null) {
388 for (Iterator it = collection.iterator(); it.hasNext();) {
389 closure.execute(it.next());
390 }
391 }
392 }
393
394 /**
395 * Filter the collection by applying a Predicate to each element. If the
396 * predicate returns false, remove the element.
397 * <p>
398 * If the input collection or predicate is null, there is no change made.
399 *
400 * @param collection the collection to get the input from, may be null
401 * @param predicate the predicate to use as a filter, may be null
402 */
403 public static void filter(Collection collection, Predicate predicate) {
404 if (collection != null && predicate != null) {
405 for (Iterator it = collection.iterator(); it.hasNext();) {
406 if (predicate.evaluate(it.next()) == false) {
407 it.remove();
408 }
409 }
410 }
411 }
412
413 /**
414 * Transform the collection by applying a Transformer to each element.
415 * <p>
416 * If the input collection or transformer is null, there is no change made.
417 * <p>
418 * This routine is best for Lists, for which set() is used to do the
419 * transformations "in place." For other Collections, clear() and addAll()
420 * are used to replace elements.
421 * <p>
422 * If the input collection controls its input, such as a Set, and the
423 * Transformer creates duplicates (or are otherwise invalid), the
424 * collection may reduce in size due to calling this method.
425 *
426 * @param collection the collection to get the input from, may be null
427 * @param transformer the transformer to perform, may be null
428 */
429 public static void transform(Collection collection, Transformer transformer) {
430 if (collection != null && transformer != null) {
431 if (collection instanceof List) {
432 List list = (List) collection;
433 for (ListIterator it = list.listIterator(); it.hasNext();) {
434 it.set(transformer.transform(it.next()));
435 }
436 } else {
437 Collection resultCollection = collect(collection, transformer);
438 collection.clear();
439 collection.addAll(resultCollection);
440 }
441 }
442 }
443
444 /**
445 * Counts the number of elements in the input collection that match the predicate.
446 * <p>
447 * A <code>null</code> collection or predicate matches no elements.
448 *
449 * @param inputCollection the collection to get the input from, may be null
450 * @param predicate the predicate to use, may be null
451 * @return the number of matches for the predicate in the collection
452 */
453 public static int countMatches(Collection inputCollection, Predicate predicate) {
454 int count = 0;
455 if (inputCollection != null && predicate != null) {
456 for (Iterator it = inputCollection.iterator(); it.hasNext();) {
457 if (predicate.evaluate(it.next())) {
458 count++;
459 }
460 }
461 }
462 return count;
463 }
464
465 /**
466 * Answers true if a predicate is true for at least one element of a collection.
467 * <p>
468 * A <code>null</code> collection or predicate returns false.
469 *
470 * @param collection the collection to get the input from, may be null
471 * @param predicate the predicate to use, may be null
472 * @return true if at least one element of the collection matches the predicate
473 */
474 public static boolean exists(Collection collection, Predicate predicate) {
475 if (collection != null && predicate != null) {
476 for (Iterator it = collection.iterator(); it.hasNext();) {
477 if (predicate.evaluate(it.next())) {
478 return true;
479 }
480 }
481 }
482 return false;
483 }
484
485 /**
486 * Selects all elements from input collection which match the given predicate
487 * into an output collection.
488 * <p>
489 * A <code>null</code> predicate matches no elements.
490 *
491 * @param inputCollection the collection to get the input from, may not be null
492 * @param predicate the predicate to use, may be null
493 * @return the elements matching the predicate (new list)
494 * @throws NullPointerException if the input collection is null
495 */
496 public static Collection select(Collection inputCollection, Predicate predicate) {
497 ArrayList answer = new ArrayList(inputCollection.size());
498 select(inputCollection, predicate, answer);
499 return answer;
500 }
501
502 /**
503 * Selects all elements from input collection which match the given predicate
504 * and adds them to outputCollection.
505 * <p>
506 * If the input collection or predicate is null, there is no change to the
507 * output collection.
508 *
509 * @param inputCollection the collection to get the input from, may be null
510 * @param predicate the predicate to use, may be null
511 * @param outputCollection the collection to output into, may not be null
512 */
513 public static void select(Collection inputCollection, Predicate predicate, Collection outputCollection) {
514 if (inputCollection != null && predicate != null) {
515 for (Iterator iter = inputCollection.iterator(); iter.hasNext();) {
516 Object item = iter.next();
517 if (predicate.evaluate(item)) {
518 outputCollection.add(item);
519 }
520 }
521 }
522 }
523
524 /**
525 * Selects all elements from inputCollection which don't match the given predicate
526 * into an output collection.
527 * <p>
528 * If the input predicate is <code>null</code>, the result is an empty list.
529 *
530 * @param inputCollection the collection to get the input from, may not be null
531 * @param predicate the predicate to use, may be null
532 * @return the elements <b>not</b> matching the predicate (new list)
533 * @throws NullPointerException if the input collection is null
534 */
535 public static Collection selectRejected(Collection inputCollection, Predicate predicate) {
536 ArrayList answer = new ArrayList(inputCollection.size());
537 selectRejected(inputCollection, predicate, answer);
538 return answer;
539 }
540
541 /**
542 * Selects all elements from inputCollection which don't match the given predicate
543 * and adds them to outputCollection.
544 * <p>
545 * If the input predicate is <code>null</code>, no elements are added to <code>outputCollection</code>.
546 *
547 * @param inputCollection the collection to get the input from, may be null
548 * @param predicate the predicate to use, may be null
549 * @param outputCollection the collection to output into, may not be null
550 */
551 public static void selectRejected(Collection inputCollection, Predicate predicate, Collection outputCollection) {
552 if (inputCollection != null && predicate != null) {
553 for (Iterator iter = inputCollection.iterator(); iter.hasNext();) {
554 Object item = iter.next();
555 if (predicate.evaluate(item) == false) {
556 outputCollection.add(item);
557 }
558 }
559 }
560 }
561
562 /**
563 * Returns a new Collection consisting of the elements of inputCollection transformed
564 * by the given transformer.
565 * <p>
566 * If the input transformer is null, the result is an empty list.
567 *
568 * @param inputCollection the collection to get the input from, may not be null
569 * @param transformer the transformer to use, may be null
570 * @return the transformed result (new list)
571 * @throws NullPointerException if the input collection is null
572 */
573 public static Collection collect(Collection inputCollection, Transformer transformer) {
574 ArrayList answer = new ArrayList(inputCollection.size());
575 collect(inputCollection, transformer, answer);
576 return answer;
577 }
578
579 /**
580 * Transforms all elements from the inputIterator with the given transformer
581 * and adds them to the outputCollection.
582 * <p>
583 * If the input iterator or transformer is null, the result is an empty list.
584 *
585 * @param inputIterator the iterator to get the input from, may be null
586 * @param transformer the transformer to use, may be null
587 * @return the transformed result (new list)
588 */
589 public static Collection collect(Iterator inputIterator, Transformer transformer) {
590 ArrayList answer = new ArrayList();
591 collect(inputIterator, transformer, answer);
592 return answer;
593 }
594
595 /**
596 * Transforms all elements from inputCollection with the given transformer
597 * and adds them to the outputCollection.
598 * <p>
599 * If the input collection or transformer is null, there is no change to the
600 * output collection.
601 *
602 * @param inputCollection the collection to get the input from, may be null
603 * @param transformer the transformer to use, may be null
604 * @param outputCollection the collection to output into, may not be null
605 * @return the outputCollection with the transformed input added
606 * @throws NullPointerException if the output collection is null
607 */
608 public static Collection collect(Collection inputCollection, final Transformer transformer, final Collection outputCollection) {
609 if (inputCollection != null) {
610 return collect(inputCollection.iterator(), transformer, outputCollection);
611 }
612 return outputCollection;
613 }
614
615 /**
616 * Transforms all elements from the inputIterator with the given transformer
617 * and adds them to the outputCollection.
618 * <p>
619 * If the input iterator or transformer is null, there is no change to the
620 * output collection.
621 *
622 * @param inputIterator the iterator to get the input from, may be null
623 * @param transformer the transformer to use, may be null
624 * @param outputCollection the collection to output into, may not be null
625 * @return the outputCollection with the transformed input added
626 * @throws NullPointerException if the output collection is null
627 */
628 public static Collection collect(Iterator inputIterator, final Transformer transformer, final Collection outputCollection) {
629 if (inputIterator != null && transformer != null) {
630 while (inputIterator.hasNext()) {
631 Object item = inputIterator.next();
632 Object value = transformer.transform(item);
633 outputCollection.add(value);
634 }
635 }
636 return outputCollection;
637 }
638
639 //-----------------------------------------------------------------------
640 /**
641 * Adds an element to the collection unless the element is null.
642 *
643 * @param collection the collection to add to, must not be null
644 * @param object the object to add, if null it will not be added
645 * @return true if the collection changed
646 * @throws NullPointerException if the collection is null
647 * @since Commons Collections 3.2
648 */
649 public static boolean addIgnoreNull(Collection collection, Object object) {
650 return (object == null ? false : collection.add(object));
651 }
652
653 /**
654 * Adds all elements in the iteration to the given collection.
655 *
656 * @param collection the collection to add to, must not be null
657 * @param iterator the iterator of elements to add, must not be null
658 * @throws NullPointerException if the collection or iterator is null
659 */
660 public static void addAll(Collection collection, Iterator iterator) {
661 while (iterator.hasNext()) {
662 collection.add(iterator.next());
663 }
664 }
665
666 /**
667 * Adds all elements in the enumeration to the given collection.
668 *
669 * @param collection the collection to add to, must not be null
670 * @param enumeration the enumeration of elements to add, must not be null
671 * @throws NullPointerException if the collection or enumeration is null
672 */
673 public static void addAll(Collection collection, Enumeration enumeration) {
674 while (enumeration.hasMoreElements()) {
675 collection.add(enumeration.nextElement());
676 }
677 }
678
679 /**
680 * Adds all elements in the array to the given collection.
681 *
682 * @param collection the collection to add to, must not be null
683 * @param elements the array of elements to add, must not be null
684 * @throws NullPointerException if the collection or array is null
685 */
686 public static void addAll(Collection collection, Object[] elements) {
687 for (int i = 0, size = elements.length; i < size; i++) {
688 collection.add(elements[i]);
689 }
690 }
691
692 /**
693 * Given an Object, and an index, returns the nth value in the
694 * object.
695 * <ul>
696 * <li>If obj is a Map, returns the nth value from the <b>keySet</b> iterator, unless
697 * the Map contains an Integer key with integer value = idx, in which case the
698 * corresponding map entry value is returned. If idx exceeds the number of entries in
699 * the map, an empty Iterator is returned.
700 * <li>If obj is a List or an array, returns the nth value, throwing IndexOutOfBoundsException,
701 * ArrayIndexOutOfBoundsException, resp. if the nth value does not exist.
702 * <li>If obj is an iterator, enumeration or Collection, returns the nth value from the iterator,
703 * returning an empty Iterator (resp. Enumeration) if the nth value does not exist.
704 * <li>Returns the original obj if it is null or not a Collection or Iterator.
705 * </ul>
706 *
707 * @param obj the object to get an index of, may be null
708 * @param idx the index to get
709 * @throws IndexOutOfBoundsException
710 * @throws ArrayIndexOutOfBoundsException
711 *
712 * @deprecated use {@link #get(Object, int)} instead. Will be removed in v4.0
713 */
714 public static Object index(Object obj, int idx) {
715 return index(obj, new Integer(idx));
716 }
717
718 /**
719 * Given an Object, and a key (index), returns the value associated with
720 * that key in the Object. The following checks are made:
721 * <ul>
722 * <li>If obj is a Map, use the index as a key to get a value. If no match continue.
723 * <li>Check key is an Integer. If not, return the object passed in.
724 * <li>If obj is a Map, get the nth value from the <b>keySet</b> iterator.
725 * If the Map has fewer than n entries, return an empty Iterator.
726 * <li>If obj is a List or an array, get the nth value, throwing IndexOutOfBoundsException,
727 * ArrayIndexOutOfBoundsException, resp. if the nth value does not exist.
728 * <li>If obj is an iterator, enumeration or Collection, get the nth value from the iterator,
729 * returning an empty Iterator (resp. Enumeration) if the nth value does not exist.
730 * <li>Return the original obj.
731 * </ul>
732 *
733 * @param obj the object to get an index of
734 * @param index the index to get
735 * @return the object at the specified index
736 * @throws IndexOutOfBoundsException
737 * @throws ArrayIndexOutOfBoundsException
738 *
739 * @deprecated use {@link #get(Object, int)} instead. Will be removed in v4.0
740 */
741 public static Object index(Object obj, Object index) {
742 if(obj instanceof Map) {
743 Map map = (Map)obj;
744 if(map.containsKey(index)) {
745 return map.get(index);
746 }
747 }
748 int idx = -1;
749 if(index instanceof Integer) {
750 idx = ((Integer)index).intValue();
751 }
752 if(idx < 0) {
753 return obj;
754 }
755 else if(obj instanceof Map) {
756 Map map = (Map)obj;
757 Iterator iterator = map.keySet().iterator();
758 return index(iterator, idx);
759 }
760 else if(obj instanceof List) {
761 return ((List)obj).get(idx);
762 }
763 else if(obj instanceof Object[]) {
764 return ((Object[])obj)[idx];
765 }
766 else if(obj instanceof Enumeration) {
767 Enumeration it = (Enumeration)obj;
768 while(it.hasMoreElements()) {
769 idx--;
770 if(idx == -1) {
771 return it.nextElement();
772 } else {
773 it.nextElement();
774 }
775 }
776 }
777 else if(obj instanceof Iterator) {
778 return index((Iterator)obj, idx);
779 }
780 else if(obj instanceof Collection) {
781 Iterator iterator = ((Collection)obj).iterator();
782 return index(iterator, idx);
783 }
784 return obj;
785 }
786
787 private static Object index(Iterator iterator, int idx) {
788 while(iterator.hasNext()) {
789 idx--;
790 if(idx == -1) {
791 return iterator.next();
792 } else {
793 iterator.next();
794 }
795 }
796 return iterator;
797 }
798
799 /**
800 * Returns the <code>index</code>-th value in <code>object</code>, throwing
801 * <code>IndexOutOfBoundsException</code> if there is no such element or
802 * <code>IllegalArgumentException</code> if <code>object</code> is not an
803 * instance of one of the supported types.
804 * <p>
805 * The supported types, and associated semantics are:
806 * <ul>
807 * <li> Map -- the value returned is the <code>Map.Entry</code> in position
808 * <code>index</code> in the map's <code>entrySet</code> iterator,
809 * if there is such an entry.</li>
810 * <li> List -- this method is equivalent to the list's get method.</li>
811 * <li> Array -- the <code>index</code>-th array entry is returned,
812 * if there is such an entry; otherwise an <code>IndexOutOfBoundsException</code>
813 * is thrown.</li>
814 * <li> Collection -- the value returned is the <code>index</code>-th object
815 * returned by the collection's default iterator, if there is such an element.</li>
816 * <li> Iterator or Enumeration -- the value returned is the
817 * <code>index</code>-th object in the Iterator/Enumeration, if there
818 * is such an element. The Iterator/Enumeration is advanced to
819 * <code>index</code> (or to the end, if <code>index</code> exceeds the
820 * number of entries) as a side effect of this method.</li>
821 * </ul>
822 *
823 * @param object the object to get a value from
824 * @param index the index to get
825 * @return the object at the specified index
826 * @throws IndexOutOfBoundsException if the index is invalid
827 * @throws IllegalArgumentException if the object type is invalid
828 */
829 public static Object get(Object object, int index) {
830 if (index < 0) {
831 throw new IndexOutOfBoundsException("Index cannot be negative: " + index);
832 }
833 if (object instanceof Map) {
834 Map map = (Map) object;
835 Iterator iterator = map.entrySet().iterator();
836 return get(iterator, index);
837 } else if (object instanceof List) {
838 return ((List) object).get(index);
839 } else if (object instanceof Object[]) {
840 return ((Object[]) object)[index];
841 } else if (object instanceof Iterator) {
842 Iterator it = (Iterator) object;
843 while (it.hasNext()) {
844 index--;
845 if (index == -1) {
846 return it.next();
847 } else {
848 it.next();
849 }
850 }
851 throw new IndexOutOfBoundsException("Entry does not exist: " + index);
852 } else if (object instanceof Collection) {
853 Iterator iterator = ((Collection) object).iterator();
854 return get(iterator, index);
855 } else if (object instanceof Enumeration) {
856 Enumeration it = (Enumeration) object;
857 while (it.hasMoreElements()) {
858 index--;
859 if (index == -1) {
860 return it.nextElement();
861 } else {
862 it.nextElement();
863 }
864 }
865 throw new IndexOutOfBoundsException("Entry does not exist: " + index);
866 } else if (object == null) {
867 throw new IllegalArgumentException("Unsupported object type: null");
868 } else {
869 try {
870 return Array.get(object, index);
871 } catch (IllegalArgumentException ex) {
872 throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
873 }
874 }
875 }
876
877 /**
878 * Gets the size of the collection/iterator specified.
879 * <p>
880 * This method can handles objects as follows
881 * <ul>
882 * <li>Collection - the collection size
883 * <li>Map - the map size
884 * <li>Array - the array size
885 * <li>Iterator - the number of elements remaining in the iterator
886 * <li>Enumeration - the number of elements remaining in the enumeration
887 * </ul>
888 *
889 * @param object the object to get the size of
890 * @return the size of the specified collection
891 * @throws IllegalArgumentException thrown if object is not recognised or null
892 * @since Commons Collections 3.1
893 */
894 public static int size(Object object) {
895 int total = 0;
896 if (object instanceof Map) {
897 total = ((Map) object).size();
898 } else if (object instanceof Collection) {
899 total = ((Collection) object).size();
900 } else if (object instanceof Object[]) {
901 total = ((Object[]) object).length;
902 } else if (object instanceof Iterator) {
903 Iterator it = (Iterator) object;
904 while (it.hasNext()) {
905 total++;
906 it.next();
907 }
908 } else if (object instanceof Enumeration) {
909 Enumeration it = (Enumeration) object;
910 while (it.hasMoreElements()) {
911 total++;
912 it.nextElement();
913 }
914 } else if (object == null) {
915 throw new IllegalArgumentException("Unsupported object type: null");
916 } else {
917 try {
918 total = Array.getLength(object);
919 } catch (IllegalArgumentException ex) {
920 throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
921 }
922 }
923 return total;
924 }
925
926 /**
927 * Checks if the specified collection/array/iterator is empty.
928 * <p>
929 * This method can handles objects as follows
930 * <ul>
931 * <li>Collection - via collection isEmpty
932 * <li>Map - via map isEmpty
933 * <li>Array - using array size
934 * <li>Iterator - via hasNext
935 * <li>Enumeration - via hasMoreElements
936 * </ul>
937 * <p>
938 * Note: This method is named to avoid clashing with
939 * {@link #isEmpty(Collection)}.
940 *
941 * @param object the object to get the size of, not null
942 * @return true if empty
943 * @throws IllegalArgumentException thrown if object is not recognised or null
944 * @since Commons Collections 3.2
945 */
946 public static boolean sizeIsEmpty(Object object) {
947 if (object instanceof Collection) {
948 return ((Collection) object).isEmpty();
949 } else if (object instanceof Map) {
950 return ((Map) object).isEmpty();
951 } else if (object instanceof Object[]) {
952 return ((Object[]) object).length == 0;
953 } else if (object instanceof Iterator) {
954 return ((Iterator) object).hasNext() == false;
955 } else if (object instanceof Enumeration) {
956 return ((Enumeration) object).hasMoreElements() == false;
957 } else if (object == null) {
958 throw new IllegalArgumentException("Unsupported object type: null");
959 } else {
960 try {
961 return Array.getLength(object) == 0;
962 } catch (IllegalArgumentException ex) {
963 throw new IllegalArgumentException("Unsupported object type: " + object.getClass().getName());
964 }
965 }
966 }
967
968 //-----------------------------------------------------------------------
969 /**
970 * Null-safe check if the specified collection is empty.
971 * <p>
972 * Null returns true.
973 *
974 * @param coll the collection to check, may be null
975 * @return true if empty or null
976 * @since Commons Collections 3.2
977 */
978 public static boolean isEmpty(Collection coll) {
979 return (coll == null || coll.isEmpty());
980 }
981
982 /**
983 * Null-safe check if the specified collection is not empty.
984 * <p>
985 * Null returns false.
986 *
987 * @param coll the collection to check, may be null
988 * @return true if non-null and non-empty
989 * @since Commons Collections 3.2
990 */
991 public static boolean isNotEmpty(Collection coll) {
992 return !CollectionUtils.isEmpty(coll);
993 }
994
995 //-----------------------------------------------------------------------
996 /**
997 * Reverses the order of the given array.
998 *
999 * @param array the array to reverse
1000 */
1001 public static void reverseArray(Object[] array) {
1002 int i = 0;
1003 int j = array.length - 1;
1004 Object tmp;
1005
1006 while (j > i) {
1007 tmp = array[j];
1008 array[j] = array[i];
1009 array[i] = tmp;
1010 j--;
1011 i++;
1012 }
1013 }
1014
1015 private static final int getFreq(final Object obj, final Map freqMap) {
1016 Integer count = (Integer) freqMap.get(obj);
1017 if (count != null) {
1018 return count.intValue();
1019 }
1020 return 0;
1021 }
1022
1023 /**
1024 * Returns true if no more elements can be added to the Collection.
1025 * <p>
1026 * This method uses the {@link BoundedCollection} interface to determine the
1027 * full status. If the collection does not implement this interface then
1028 * false is returned.
1029 * <p>
1030 * The collection does not have to implement this interface directly.
1031 * If the collection has been decorated using the decorators subpackage
1032 * then these will be removed to access the BoundedCollection.
1033 *
1034 * @param coll the collection to check
1035 * @return true if the BoundedCollection is full
1036 * @throws NullPointerException if the collection is null
1037 */
1038 public static boolean isFull(Collection coll) {
1039 if (coll == null) {
1040 throw new NullPointerException("The collection must not be null");
1041 }
1042 if (coll instanceof BoundedCollection) {
1043 return ((BoundedCollection) coll).isFull();
1044 }
1045 try {
1046 BoundedCollection bcoll = UnmodifiableBoundedCollection.decorateUsing(coll);
1047 return bcoll.isFull();
1048
1049 } catch (IllegalArgumentException ex) {
1050 return false;
1051 }
1052 }
1053
1054 /**
1055 * Get the maximum number of elements that the Collection can contain.
1056 * <p>
1057 * This method uses the {@link BoundedCollection} interface to determine the
1058 * maximum size. If the collection does not implement this interface then
1059 * -1 is returned.
1060 * <p>
1061 * The collection does not have to implement this interface directly.
1062 * If the collection has been decorated using the decorators subpackage
1063 * then these will be removed to access the BoundedCollection.
1064 *
1065 * @param coll the collection to check
1066 * @return the maximum size of the BoundedCollection, -1 if no maximum size
1067 * @throws NullPointerException if the collection is null
1068 */
1069 public static int maxSize(Collection coll) {
1070 if (coll == null) {
1071 throw new NullPointerException("The collection must not be null");
1072 }
1073 if (coll instanceof BoundedCollection) {
1074 return ((BoundedCollection) coll).maxSize();
1075 }
1076 try {
1077 BoundedCollection bcoll = UnmodifiableBoundedCollection.decorateUsing(coll);
1078 return bcoll.maxSize();
1079
1080 } catch (IllegalArgumentException ex) {
1081 return -1;
1082 }
1083 }
1084
1085 //-----------------------------------------------------------------------
1086 /**
1087 * Returns a collection containing all the elements in <code>collection</code>
1088 * that are also in <code>retain</code>. The cardinality of an element <code>e</code>
1089 * in the returned collection is the same as the cardinality of <code>e</code>
1090 * in <code>collection</code> unless <code>retain</code> does not contain <code>e</code>, in which
1091 * case the cardinality is zero. This method is useful if you do not wish to modify
1092 * the collection <code>c</code> and thus cannot call <code>c.retainAll(retain);</code>.
1093 *
1094 * @param collection the collection whose contents are the target of the #retailAll operation
1095 * @param retain the collection containing the elements to be retained in the returned collection
1096 * @return a <code>Collection</code> containing all the elements of <code>collection</code>
1097 * that occur at least once in <code>retain</code>.
1098 * @throws NullPointerException if either parameter is null
1099 * @since Commons Collections 3.2
1100 */
1101 public static Collection retainAll(Collection collection, Collection retain) {
1102 return ListUtils.retainAll(collection, retain);
1103 }
1104
1105 /**
1106 * Removes the elements in <code>remove</code> from <code>collection</code>. That is, this
1107 * method returns a collection containing all the elements in <code>c</code>
1108 * that are not in <code>remove</code>. The cardinality of an element <code>e</code>
1109 * in the returned collection is the same as the cardinality of <code>e</code>
1110 * in <code>collection</code> unless <code>remove</code> contains <code>e</code>, in which
1111 * case the cardinality is zero. This method is useful if you do not wish to modify
1112 * the collection <code>c</code> and thus cannot call <code>collection.removeAll(remove);</code>.
1113 *
1114 * @param collection the collection from which items are removed (in the returned collection)
1115 * @param remove the items to be removed from the returned <code>collection</code>
1116 * @return a <code>Collection</code> containing all the elements of <code>collection</code> except
1117 * any elements that also occur in <code>remove</code>.
1118 * @throws NullPointerException if either parameter is null
1119 * @since Commons Collections 3.2
1120 */
1121 public static Collection removeAll(Collection collection, Collection remove) {
1122 return ListUtils.retainAll(collection, remove);
1123 }
1124
1125 //-----------------------------------------------------------------------
1126 /**
1127 * Returns a synchronized collection backed by the given collection.
1128 * <p>
1129 * You must manually synchronize on the returned buffer's iterator to
1130 * avoid non-deterministic behavior:
1131 *
1132 * <pre>
1133 * Collection c = CollectionUtils.synchronizedCollection(myCollection);
1134 * synchronized (c) {
1135 * Iterator i = c.iterator();
1136 * while (i.hasNext()) {
1137 * process (i.next());
1138 * }
1139 * }
1140 * </pre>
1141 *
1142 * This method uses the implementation in the decorators subpackage.
1143 *
1144 * @param collection the collection to synchronize, must not be null
1145 * @return a synchronized collection backed by the given collection
1146 * @throws IllegalArgumentException if the collection is null
1147 */
1148 public static Collection synchronizedCollection(Collection collection) {
1149 return SynchronizedCollection.decorate(collection);
1150 }
1151
1152 /**
1153 * Returns an unmodifiable collection backed by the given collection.
1154 * <p>
1155 * This method uses the implementation in the decorators subpackage.
1156 *
1157 * @param collection the collection to make unmodifiable, must not be null
1158 * @return an unmodifiable collection backed by the given collection
1159 * @throws IllegalArgumentException if the collection is null
1160 */
1161 public static Collection unmodifiableCollection(Collection