001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections;
018    
019    import java.lang.reflect.Array;
020    import java.util.ArrayList;
021    import java.util.Collection;
022    import java.util.Enumeration;
023    import java.util.HashMap;
024    import java.util.HashSet;
025    import java.util.Iterator;
026    import java.util.List;
027    import java.util.ListIterator;
028    import java.util.Map;
029    import java.util.Set;
030    
031    import org.apache.commons.collections.collection.PredicatedCollection;
032    import org.apache.commons.collections.collection.SynchronizedCollection;
033    import org.apache.commons.collections.collection.TransformedCollection;
034    import org.apache.commons.collections.collection.TypedCollection;
035    import org.apache.commons.collections.collection.UnmodifiableBoundedCollection;
036    import org.apache.commons.collections.collection.UnmodifiableCollection;
037    
038    /**
039     * Provides utility methods and decorators for {@link Collection} instances.
040     *
041     * @since Commons Collections 1.0
042     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
043     * 
044     * @author Rodney Waldhoff
045     * @author Paul Jack
046     * @author Stephen Colebourne
047     * @author Steve Downey
048     * @author Herve Quiroz
049     * @author Peter KoBek
050     * @author Matthew Hawthorne
051     * @author Janek Bogucki
052     * @author Phil Steitz
053     * @author Steven Melzer
054     * @author Jon Schewe
055     * @author Neil O'Toole
056     * @author Stephen Smith
057     */
058    public class CollectionUtils {
059    
060        /** Constant to avoid repeated object creation */
061        private static Integer INTEGER_ONE = new Integer(1);
062    
063        /**
064         * An empty unmodifiable collection.
065         * The JDK provides empty Set and List implementations which could be used for
066         * this purpose. However they could be cast to Set or List which might be
067         * undesirable. This implementation only implements Collection.
068         */
069        public static final Collection EMPTY_COLLECTION = UnmodifiableCollection.decorate(new ArrayList());
070    
071        /**
072         * <code>CollectionUtils</code> should not normally be instantiated.
073         */
074        public CollectionUtils() {
075        }
076    
077        /**
078         * Returns a {@link Collection} containing the union
079         * of the given {@link Collection}s.
080         * <p>
081         * The cardinality of each element in the returned {@link Collection}
082         * will be equal to the maximum of the cardinality of that element
083         * in the two given {@link Collection}s.
084         *
085         * @param a  the first collection, must not be null
086         * @param b  the second collection, must not be null
087         * @return  the union of the two collections
088         * @see Collection#addAll
089         */
090        public static Collection union(final Collection a, final Collection b) {
091            ArrayList list = new ArrayList();
092            Map mapa = getCardinalityMap(a);
093            Map mapb = getCardinalityMap(b);
094            Set elts = new HashSet(a);
095            elts.addAll(b);
096            Iterator it = elts.iterator();
097            while(it.hasNext()) {
098                Object obj = it.next();
099                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 collection) {
1162            return UnmodifiableCollection.decorate(collection);
1163        }
1164    
1165        /**
1166         * Returns a predicated (validating) collection backed by the given collection.
1167         * <p>
1168         * Only objects that pass the test in the given predicate can be added to the collection.
1169         * Trying to add an invalid object results in an IllegalArgumentException.
1170         * It is important not to use the original collection after invoking this method,
1171         * as it is a backdoor for adding invalid objects.
1172         *
1173         * @param collection  the collection to predicate, must not be null
1174         * @param predicate  the predicate for the collection, must not be null
1175         * @return a predicated collection backed by the given collection
1176         * @throws IllegalArgumentException  if the Collection is null
1177         */
1178        public static Collection predicatedCollection(Collection collection, Predicate predicate) {
1179            return PredicatedCollection.decorate(collection, predicate);
1180        }
1181    
1182        /**
1183         * Returns a typed collection backed by the given collection.
1184         * <p>
1185         * Only objects of the specified type can be added to the collection.
1186         * 
1187         * @param collection  the collection to limit to a specific type, must not be null
1188         * @param type  the type of objects which may be added to the collection
1189         * @return a typed collection backed by the specified collection
1190         */
1191        public static Collection typedCollection(Collection collection, Class type) {
1192            return TypedCollection.decorate(collection, type);
1193        }
1194        
1195        /**
1196         * Returns a transformed bag backed by the given collection.
1197         * <p>
1198         * Each object is passed through the transformer as it is added to the
1199         * Collection. It is important not to use the original collection after invoking this 
1200         * method, as it is a backdoor for adding untransformed objects.
1201         *
1202         * @param collection  the collection to predicate, must not be null
1203         * @param transformer  the transformer for the collection, must not be null
1204         * @return a transformed collection backed by the given collection
1205         * @throws IllegalArgumentException  if the Collection or Transformer is null
1206         */
1207        public static Collection transformedCollection(Collection collection, Transformer transformer) {
1208            return TransformedCollection.decorate(collection, transformer);
1209        }
1210    
1211    }