OpenConcerto

Dépôt officiel du code source de l'ERP OpenConcerto
sonarqube

svn://code.openconcerto.org/openconcerto

Rev

Rev 174 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
17 ilm 1
/*
2
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3
 *
4
 * Copyright 2011 OpenConcerto, by ILM Informatique. All rights reserved.
5
 *
6
 * The contents of this file are subject to the terms of the GNU General Public License Version 3
7
 * only ("GPL"). You may not use this file except in compliance with the License. You can obtain a
8
 * copy of the License at http://www.gnu.org/licenses/gpl-3.0.html See the License for the specific
9
 * language governing permissions and limitations under the License.
10
 *
11
 * When distributing the software, include this License Header Notice in each file.
12
 */
13
 
14
 package org.openconcerto.utils;
15
 
19 ilm 16
import org.openconcerto.utils.cc.IClosure;
17
import org.openconcerto.utils.cc.IPredicate;
17 ilm 18
import org.openconcerto.utils.cc.ITransformer;
65 ilm 19
import org.openconcerto.utils.cc.IdentityHashSet;
20
import org.openconcerto.utils.cc.IdentitySet;
174 ilm 21
import org.openconcerto.utils.cc.LinkedIdentitySet;
132 ilm 22
import org.openconcerto.utils.cc.Transformer;
17 ilm 23
 
73 ilm 24
import java.io.Serializable;
25
import java.util.AbstractSet;
17 ilm 26
import java.util.ArrayList;
27
import java.util.Arrays;
28
import java.util.Collection;
29
import java.util.Collections;
30
import java.util.HashMap;
31
import java.util.HashSet;
32
import java.util.Iterator;
33
import java.util.LinkedHashMap;
73 ilm 34
import java.util.LinkedList;
17 ilm 35
import java.util.List;
73 ilm 36
import java.util.ListIterator;
17 ilm 37
import java.util.Map;
132 ilm 38
import java.util.Map.Entry;
73 ilm 39
import java.util.NoSuchElementException;
17 ilm 40
import java.util.RandomAccess;
41
import java.util.Set;
42
import java.util.regex.Pattern;
43
 
44
/**
45
 * Une classe regroupant des méthodes utilitaires pour les collections.
46
 *
47
 * @author ILM Informatique 30 sept. 2004
48
 */
67 ilm 49
public class CollectionUtils {
17 ilm 50
 
51
    /**
52
     * Concatene une collection. Cette méthode va appliquer un transformation sur chaque élément
53
     * avant d'appeler toString(). join([-1, 3, 0], " ,", doubleTransformer) == "-2, 6, 0"
54
     *
55
     * @param <E> type of items
56
     * @param c la collection a concaténer.
57
     * @param sep le séparateur entre chaque élément.
58
     * @param tf la transformation à appliquer à chaque élément.
59
     * @return la chaine composée de chacun des éléments séparés par <code>sep</code>.
60
     */
61
    static public final <E> String join(final Collection<E> c, final String sep, final ITransformer<? super E, ?> tf) {
19 ilm 62
        final int size = c.size();
63
        if (size == 0)
17 ilm 64
            return "";
65
 
19 ilm 66
        final StringBuffer res = new StringBuffer(size * 4);
17 ilm 67
        if (c instanceof RandomAccess && c instanceof List) {
68
            final List<E> list = (List<E>) c;
19 ilm 69
            for (int i = 0; i < size; i++) {
17 ilm 70
                res.append(tf.transformChecked(list.get(i)));
19 ilm 71
                if (i < size - 1)
72
                    res.append(sep);
17 ilm 73
            }
74
        } else {
75
            final Iterator<E> iter = c.iterator();
76
            while (iter.hasNext()) {
77
                final E elem = iter.next();
78
                res.append(tf.transformChecked(elem));
79
                if (iter.hasNext())
80
                    res.append(sep);
81
            }
82
        }
83
        return res.toString();
84
    }
85
 
86
    /**
87
     * Concatene une collection en appelant simplement toString() sur chaque élément.
88
     *
89
     * @param <T> type of collection
90
     * @param c la collection a concaténer.
91
     * @param sep le séparateur entre chaque élément.
92
     * @return la chaine composée de chacun des éléments séparés par <code>sep</code>.
93
     * @see #join(Collection, String, ITransformer)
94
     */
95
    static public <T> String join(Collection<T> c, String sep) {
149 ilm 96
        return join(c, sep, org.openconcerto.utils.cc.Transformer.<T> nopTransformer());
17 ilm 97
    }
98
 
67 ilm 99
    static public <T, U, C extends Collection<? super U>> C transform(final Collection<T> c, final ITransformer<? super T, U> transf, final C res) {
100
        return transformAndFilter(c, transf, IPredicate.truePredicate(), res);
101
    }
102
 
103
    static public <T, U, C extends Collection<? super U>> C transformAndFilter(final Collection<T> c, final ITransformer<? super T, U> transf, final IPredicate<? super U> filterAfter, final C res) {
104
        return filterTransformAndFilter(c, IPredicate.truePredicate(), transf, filterAfter, res);
105
    }
106
 
107
    static public <T, U, C extends Collection<? super U>> C filterAndTransform(final Collection<T> c, final IPredicate<? super T> filterBefore, final ITransformer<? super T, U> transf, final C res) {
108
        return filterTransformAndFilter(c, filterBefore, transf, IPredicate.truePredicate(), res);
109
    }
110
 
111
    static public <T, U, C extends Collection<? super U>> C filterTransformAndFilter(final Collection<T> c, final IPredicate<? super T> filterBefore, final ITransformer<? super T, U> transf,
112
            final IPredicate<? super U> filterAfter, final C res) {
113
        iterate(c, filterBefore, new IClosure<T>() {
19 ilm 114
            @Override
115
            public void executeChecked(T input) {
116
                final U item = transf.transformChecked(input);
67 ilm 117
                if (filterAfter.evaluateChecked(item))
19 ilm 118
                    res.add(item);
119
            }
120
        });
121
        return res;
122
    }
17 ilm 123
 
19 ilm 124
    static public <T> void iterate(final Collection<T> c, final IClosure<T> cl) {
67 ilm 125
        iterate(c, IPredicate.truePredicate(), cl);
126
    }
127
 
128
    static public <T> void iterate(final Collection<T> c, final IPredicate<? super T> filterBefore, final IClosure<T> cl) {
19 ilm 129
        if (c instanceof RandomAccess && c instanceof List) {
130
            final List<T> list = (List<T>) c;
131
            final int size = c.size();
132
            for (int i = 0; i < size; i++) {
67 ilm 133
                final T item = list.get(i);
134
                if (filterBefore.evaluateChecked(item))
135
                    cl.executeChecked(item);
19 ilm 136
            }
137
        } else {
138
            final Iterator<T> iter = c.iterator();
139
            while (iter.hasNext()) {
67 ilm 140
                final T item = iter.next();
141
                if (filterBefore.evaluateChecked(item))
142
                    cl.executeChecked(item);
19 ilm 143
            }
144
        }
145
    }
146
 
17 ilm 147
    private static final Pattern COMMA = Pattern.compile("\\p{Space}*,\\p{Space}*");
148
 
149
    static public List<String> split(String s) {
150
        return split(s, COMMA);
151
    }
152
 
153
    static public List<String> split(String s, String sep) {
154
        return split(s, Pattern.compile(sep));
155
    }
156
 
157
    /**
158
     * Split a string into a list based on a pattern.
159
     *
160
     * @param s the string to split.
161
     * @param pattern the pattern where to cut the string.
162
     * @return the splitted string, empty list if <code>s</code> is "".
163
     */
164
    static public List<String> split(String s, Pattern pattern) {
149 ilm 165
        return s.length() == 0 ? Collections.<String> emptyList() : Arrays.asList(pattern.split(s));
17 ilm 166
    }
167
 
168
    /**
169
     * Return an index between <code>0</code> and <code>l.size()</code> inclusive. If <code>i</code>
93 ilm 170
     * is negative, it is added to <code>l.size()</code> (i.e. -1 is the index of the last item and
171
     * -size is the first) :
17 ilm 172
     *
173
     * <pre>
174
     *    a  b  c  a  b  c
175
     *   -3 -2 -1  0  1  2  3
176
     * </pre>
177
     *
93 ilm 178
     * @param l the list, e.g. a list of 3 items.
179
     * @param i the virtual index, e.g. -1.
180
     * @return the real index, e.g. 2.
181
     * @throws IndexOutOfBoundsException if not <code>0 &le; abs(i) &le; l.size()</code>
17 ilm 182
     */
93 ilm 183
    static public int getValidIndex(final List<?> l, final int i) throws IndexOutOfBoundsException {
184
        return getValidIndex(l, i, true);
61 ilm 185
    }
186
 
93 ilm 187
    /**
188
     * Return an index between <code>0</code> and <code>l.size()</code> inclusive. If <code>i</code>
189
     * is negative, it is added to <code>l.size()</code> (bounded to 0 if <code>strict</code> is
190
     * <code>false</code>), i.e. for a list of 3 items, -1 is the index of the last item ; -3 and -4
191
     * are both the first. If <code>i</code> is greater than <code>l.size()</code> then
192
     * <code>l.size()</code> is returned if not <code>strict</code>.
193
     *
194
     * @param l the list, e.g. a list of 3 items.
195
     * @param i the virtual index, e.g. -1.
196
     * @param strict if <code>true</code> <code>abs(i)</code> must be between <code>0</code> and
197
     *        <code>l.size()</code>, else values are bounded between <code>0</code> and
198
     *        <code>l.size()</code>.
199
     * @return the real index between <code>0</code> and <code>l.size()</code>, e.g. 2.
200
     * @throws IndexOutOfBoundsException if <code>strict</code> is <code>true</code> and not
201
     *         <code>0 &le; abs(i) &le; l.size()</code>
202
     */
203
    static public int getValidIndex(final List<?> l, final int i, final boolean strict) throws IndexOutOfBoundsException {
61 ilm 204
        final int size = l.size();
205
        if (i > size) {
206
            if (strict)
207
                throw new IndexOutOfBoundsException("Too high : " + i + " > " + size);
208
            return size;
209
        } else if (i < -size) {
210
            if (strict)
211
                throw new IndexOutOfBoundsException("Too low : " + i + " < " + -size);
212
            return 0;
17 ilm 213
        } else if (i >= 0) {
214
            return i;
61 ilm 215
        } else {
216
            return size + i;
217
        }
17 ilm 218
    }
219
 
220
    /**
93 ilm 221
     * Deletes a slice of a list. Pass indexes to {@link #getValidIndex(List, int, boolean)} to
222
     * allow delete(l, 0, -1) to clear l or delete(l, -2, -2) to remove the penultimate item.
17 ilm 223
     *
224
     * @param l the list to delete from.
225
     * @param from the first index to be removed (inclusive).
226
     * @param to the last index to be removed (inclusive).
227
     */
228
    static public void delete(List<?> l, int from, int to) {
229
        if (!l.isEmpty())
93 ilm 230
            l.subList(getValidIndex(l, from, false), getValidIndex(l, to, false) + 1).clear();
17 ilm 231
    }
232
 
233
    /**
234
     * Deletes the tail of a list. The resulting list will have a size of <code>from</code>.
235
     *
236
     * @param l the list to delete from.
237
     * @param from the first index to be removed (inclusive).
238
     */
239
    static public void delete(List<?> l, int from) {
240
        delete(l, from, -1);
241
    }
242
 
67 ilm 243
    public static <T> void filter(Collection<T> collection, IPredicate<? super T> predicate) {
244
        org.apache.commons.collections.CollectionUtils.filter(collection, predicate);
19 ilm 245
    }
246
 
67 ilm 247
    public static <T> boolean exists(Collection<T> collection, IPredicate<? super T> predicate) {
248
        return org.apache.commons.collections.CollectionUtils.exists(collection, predicate);
249
    }
250
 
17 ilm 251
    /**
252
     * Convertit une map en 2 listes, une pour les clefs, une pour les valeurs.
253
     *
254
     * @param map la Map à convertir.
255
     * @return un tuple de 2 List, en 0 les clefs, en 1 les valeurs.
256
     * @param <K> type of key
257
     * @param <V> type of value
258
     */
259
    static public <K, V> Tuple2<List<K>, List<V>> mapToLists(Map<K, V> map) {
260
        final List<K> keys = new ArrayList<K>(map.size());
261
        final List<V> vals = new ArrayList<V>(map.size());
262
        for (final Map.Entry<K, V> e : map.entrySet()) {
263
            keys.add(e.getKey());
264
            vals.add(e.getValue());
265
        }
266
 
267
        return Tuple2.create(keys, vals);
268
    }
269
 
270
    /**
271
     * Add entries from <code>toAdd</code> into <code>map</code> only if the key is not already
272
     * present.
273
     *
274
     * @param <K> type of keys.
275
     * @param <V> type of values.
276
     * @param map the map to fill.
277
     * @param toAdd the entries to add.
278
     * @return <code>map</code>.
279
     */
280
    static public <K, V> Map<K, V> addIfNotPresent(Map<K, V> map, Map<? extends K, ? extends V> toAdd) {
281
        for (final Map.Entry<? extends K, ? extends V> e : toAdd.entrySet()) {
282
            if (!map.containsKey(e.getKey()))
283
                map.put(e.getKey(), e.getValue());
284
        }
285
        return map;
286
    }
287
 
288
    /**
289
     * Compute the index that have changed (added or removed) between 2 lists. One of the lists MUST
290
     * be a sublist of the other, ie the to go from one to the other we just add or remove items but
291
     * we don't do both.
292
     *
293
     * @param oldList the first list.
294
     * @param newList the second list.
295
     * @return a list of Integer.
296
     * @param <E> type of item
297
     * @throws IllegalStateException if one list is not a sublist of the other.
298
     */
299
    static public <E> List<Integer> getIndexesChanged(List<E> oldList, List<E> newList) {
300
        final List<E> longer;
301
        final List<E> shorter;
302
        if (newList.size() > oldList.size()) {
303
            longer = new ArrayList<E>(newList);
304
            shorter = new ArrayList<E>(oldList);
305
        } else {
306
            longer = new ArrayList<E>(oldList);
307
            shorter = new ArrayList<E>(newList);
308
        }
309
 
310
        final List<Integer> res = new ArrayList<Integer>();
311
        int offset = 0;
312
        while (shorter.size() > 0) {
313
            if (longer.size() < shorter.size())
314
                throw new IllegalStateException(shorter + " is not a sublist of " + longer);
315
            // compare nulls
316
            if (CompareUtils.equals(shorter.get(0), longer.get(0))) {
317
                shorter.remove(0);
318
                longer.remove(0);
319
            } else {
320
                longer.remove(0);
321
                res.add(offset);
322
            }
323
            offset++;
324
        }
325
 
326
        for (int i = 0; i < longer.size(); i++) {
327
            res.add(i + offset);
328
        }
329
 
330
        return res;
331
    }
332
 
333
    /**
334
     * Aggregate a list of ints into a list of intervals. Eg aggregate([-1,0,1,2,5]) returns
335
     * [[-1,2], [5,5]].
336
     *
337
     * @param ints a list of Integer strictly increasing.
338
     * @return a list of int[2].
339
     */
340
    static public List<int[]> aggregate(Collection<? extends Number> ints) {
341
        final List<int[]> res = new ArrayList<int[]>();
342
        int[] currentInterval = null;
343
        for (final Number n : ints) {
344
            final int index = n.intValue();
345
            if (currentInterval == null || index != currentInterval[1] + 1) {
346
                currentInterval = new int[2];
347
                currentInterval[0] = index;
348
                currentInterval[1] = currentInterval[0];
349
                res.add(currentInterval);
350
            } else {
351
                currentInterval[1] = index;
352
            }
353
        }
354
        return res;
355
    }
356
 
357
    /**
358
     * Test whether col2 is contained in col1.
359
     *
360
     * @param <T> type of collection
361
     * @param col1 the first collection
362
     * @param col2 the second collection
363
     * @return <code>null</code> if col1 contains all of col2, else return the extra items that col2
364
     *         have.
365
     */
366
    static public <T> Set<T> contains(final Set<T> col1, final Set<T> col2) {
367
        if (col1.containsAll(col2))
368
            return null;
369
        else {
370
            final Set<T> names = new HashSet<T>(col2);
371
            names.removeAll(col1);
372
            return names;
373
        }
374
    }
375
 
67 ilm 376
    static public <C extends Collection<?>> boolean containsAny(final C coll1, final C coll2) {
142 ilm 377
        return !Collections.disjoint(coll1, coll2);
67 ilm 378
    }
379
 
93 ilm 380
    static public final <T> boolean identityContains(final Collection<T> coll, final T item) {
381
        for (final T v : coll) {
382
            if (item == v)
383
                return true;
384
        }
385
        return false;
386
    }
387
 
17 ilm 388
    /**
389
     * Convert an array to a list of a different type.
390
     *
391
     * @param <U> type of array
392
     * @param <T> type of list
393
     * @param array the array to convert, eg new Object[]{"a", "b"}.
394
     * @param clazz the class of the list items, eg String.class.
395
     * @return all items of <code>array</code> into a list, eg ["a", "b"].
396
     * @throws ClassCastException if some item of <code>array</code> is not a <code>T</code>.
397
     */
398
    static public <U, T extends U> List<T> castToList(U[] array, Class<T> clazz) throws ClassCastException {
399
        final List<T> res = new ArrayList<T>(array.length);
400
        for (final U item : array) {
401
            res.add(clazz.cast(item));
402
        }
403
        return res;
404
    }
405
 
406
    /**
142 ilm 407
     * Cast list
408
     *
409
     * @param <E> type of result list
410
     * @param list the list to convert
411
     * @param c the class of the result list
412
     * @return a new ArrayList create from <code>list</code> or null if <code>list</code> is null
413
     * @throws ClassCastException if some item of <code>list</code> is not a <code>E</code>.
414
     */
415
    public static <E> List<E> castList(final List<?> list, Class<E> c) throws ClassCastException {
416
        if (list == null) {
417
            return null;
418
        }
419
 
177 ilm 420
        final int size = list.size();
421
        final List<E> result = new ArrayList<E>(size);
142 ilm 422
        for (int i = 0; i < list.size(); i++) {
423
            result.add(c.cast(list.get(i)));
424
        }
425
        return result;
426
    }
427
 
428
    /**
429
     * Cast Map
430
     *
431
     * @param <E> type of key
432
     * @param <F> type of value
433
     * @param map the map to convert
434
     * @param cKey the class of key
435
     * @param cValue the class of value
436
     * @return a new HashMap create from the <code>map</code> or null if <code>map</code> is null
437
     * @throws ClassCastException if some item of <code>map</code> have a key which the type is not
438
     *         a <code>E</code> or a value which the type is not a <code>F</code>.
439
     */
440
    public static <E, F> Map<E, F> castMap(final Map<?, ?> map, Class<E> cKey, Class<F> cValue) throws ClassCastException {
441
        if (map == null) {
442
            return null;
443
        }
444
 
445
        final Map<E, F> result = new HashMap<E, F>();
446
        for (final Entry<?, ?> mapEntry : map.entrySet()) {
447
            final E key;
448
            try {
449
                key = cKey.cast(mapEntry.getKey());
450
            } catch (final ClassCastException ex) {
451
                throw new ClassCastException("Key " + mapEntry.getKey().toString() + " is not valid: " + ex.getMessage());
452
            }
453
            final F value;
454
            try {
455
                value = cValue.cast(mapEntry.getValue());
456
            } catch (final ClassCastException ex) {
457
                throw new ClassCastException("Value " + mapEntry.getKey().toString() + " is not valid: " + ex.getMessage());
458
            }
459
            result.put(key, value);
460
        }
461
        return result;
462
    }
463
 
464
    /**
17 ilm 465
     * The number of equals item between a and b, starting from the end.
466
     *
467
     * @param <T> type of items.
468
     * @param a the first list, eg [a, b, c].
469
     * @param b the second list, eg [a, null, z, c].
470
     * @return the number of common items, eg 1.
471
     */
472
    public static <T> int equalsFromEnd(final List<T> a, final List<T> b) {
473
        return equals(a, b, true, null);
474
    }
475
 
476
    public static <T> int equalsFromStart(final List<T> a, final List<T> b) {
477
        return equals(a, b, false, null);
478
    }
479
 
480
    /**
481
     * The number of equals item between a and b, starting from the choosen end.
482
     *
483
     * @param <A> type of the first list.
484
     * @param <B> type of the second list.
485
     * @param a the first list, eg [a, b, c].
486
     * @param b the second list, eg [a, null, z, c].
487
     * @param fromEnd whether search from the start or the end, <code>true</code>.
488
     * @param transf how items of <code>a</code> should be transformed before being compared, can be
489
     *        <code>null</code>.
490
     * @return the number of common items, eg 1.
491
     */
492
    public final static <A, B> int equals(final List<A> a, final List<B> b, boolean fromEnd, ITransformer<A, B> transf) {
493
        final int sizeA = a.size();
494
        final int sizeB = b.size();
495
        final int lastI = Math.min(sizeA, sizeB);
496
        for (int i = 0; i < lastI; i++) {
497
            final A itemA = a.get(fromEnd ? sizeA - 1 - i : i);
498
            final B itemB = b.get(fromEnd ? sizeB - 1 - i : i);
499
            if (!CompareUtils.equals(transf == null ? itemA : transf.transformChecked(itemA), itemB))
500
                return i;
501
        }
502
        return lastI;
503
    }
504
 
83 ilm 505
    public final static <T> int getEqualsCount(final Iterator<? extends T> a, final Iterator<? extends T> b) {
506
        return getEqualsCount(a, b, null);
507
    }
508
 
509
    public final static <A, B> int getEqualsCount(final Iterator<A> a, final Iterator<B> b, final ITransformer<A, B> transf) {
510
        int res = 0;
511
        while (a.hasNext() && b.hasNext()) {
512
            final A itemA = a.next();
513
            final B itemB = b.next();
514
            if (!CompareUtils.equals(transf == null ? itemA : transf.transformChecked(itemA), itemB))
515
                break;
516
            res++;
517
        }
518
        return res;
519
    }
520
 
67 ilm 521
    public static <T> Collection<T> select(final Collection<T> a, final IPredicate<? super T> pred) {
522
        return select(a, pred, new ArrayList<T>());
65 ilm 523
    }
524
 
67 ilm 525
    public static <T, C extends Collection<? super T>> C select(final Collection<T> a, final IPredicate<? super T> pred, final C b) {
65 ilm 526
        for (final T item : a)
527
            if (pred.evaluateChecked(item))
528
                b.add(item);
529
        return b;
530
    }
531
 
17 ilm 532
    // avoid name collision causing eclipse bug https://bugs.eclipse.org/bugs/show_bug.cgi?id=319603
533
    @SuppressWarnings("unchecked")
534
    public static <T> Collection<T> intersection(final Collection<T> a, final Collection<T> b) {
535
        return org.apache.commons.collections.CollectionUtils.intersection(a, b);
536
    }
537
 
538
    /**
539
     * Compute the intersection of a and b. <code>null</code>s are ignored : x ∩ null = x.
540
     *
541
     * @param <T> type of collection.
542
     * @param a the first set, can be <code>null</code>.
543
     * @param b the second set, can be <code>null</code>.
544
     * @return the intersection.
545
     */
546
    @SuppressWarnings("unchecked")
547
    public static <T> Set<T> inter(final Set<T> a, final Set<T> b) {
548
        return (Set<T>) interSubtype(a, b);
549
    }
550
 
551
    public static <T> Set<? extends T> interSubtype(final Set<? extends T> a, final Set<? extends T> b) {
552
        if (a == b)
553
            return a;
554
        else if (a == null)
555
            return b;
556
        else if (b == null)
557
            return a;
558
        else if (a.size() > b.size()) {
559
            return interSubtype(b, a);
560
        }
561
 
562
        final Set<T> res = new HashSet<T>();
563
        for (final T item : a) {
564
            if (b.contains(item))
565
                res.add(item);
566
        }
567
        return res;
568
    }
569
 
570
    public static <T> Set<T> inter(final Set<T>... sets) {
571
        return inter(Arrays.asList(sets));
572
    }
573
 
574
    public static <T> Set<T> inter(final List<Set<T>> sets) {
575
        final List<Set<T>> mutable = new ArrayList<Set<T>>(sets.size());
576
        for (final Set<T> s : sets) {
577
            // ignore nulls
578
            if (s != null)
579
                mutable.add(s);
580
        }
581
 
582
        if (mutable.isEmpty())
583
            return null;
584
        else if (mutable.size() == 1)
585
            return mutable.get(0);
586
 
587
        final int indexMin = indexOfMinSize(mutable);
588
        if (indexMin != 0) {
589
            mutable.add(0, mutable.remove(indexMin));
590
            return inter(mutable);
591
        }
592
 
593
        if (mutable.get(0).isEmpty())
594
            return Collections.emptySet();
595
 
596
        // replace the first 2 by their intersection
597
        // (inter will swap as appropriate if java doesn't evalute args in source order)
598
        mutable.add(0, inter(mutable.remove(0), mutable.remove(0)));
599
        return inter(mutable);
600
    }
601
 
602
    private static final <T> int indexOfMinSize(final List<Set<T>> sets) {
603
        if (sets.isEmpty())
604
            throw new IllegalArgumentException("empty sets");
605
 
606
        int res = 0;
607
        for (int i = 1; i < sets.size(); i++) {
608
            if (sets.get(i).size() < sets.get(res).size())
609
                res = i;
610
        }
611
        return res;
612
    }
613
 
614
    /**
615
     * Returns a {@link Set} containing the union of the given {@link Set}s.
616
     *
617
     * @param <T> type of items.
618
     * @param a the first set, must not be <code>null</code>
619
     * @param b the second set, must not be <code>null</code>
620
     * @return the union of the two.
621
     */
622
    public static <T> Set<T> union(final Set<? extends T> a, final Set<? extends T> b) {
623
        final Set<T> res = new HashSet<T>(a);
624
        if (a != b)
625
            res.addAll(b);
626
        return res;
627
    }
628
 
132 ilm 629
    public static <T> Set<T> union(final Collection<? extends Collection<? extends T>> colls) {
630
        return union(new HashSet<T>(), colls);
631
    }
632
 
633
    public static <T> List<T> cat(final Collection<? extends Collection<? extends T>> colls) {
634
        return union(new ArrayList<T>(), colls);
635
    }
636
 
637
    public static <T, C extends Collection<? super T>> C union(final C collector, final Collection<? extends Collection<? extends T>> colls) {
149 ilm 638
        return union(collector, colls, Transformer.<Collection<? extends T>> nopTransformer());
132 ilm 639
    }
640
 
641
    public static <T, C extends Collection<? super T>, A> C union(final C collector, final Collection<? extends A> colls, final ITransformer<? super A, ? extends Collection<? extends T>> transf) {
642
        for (final A coll : colls) {
643
            collector.addAll(transf.transformChecked(coll));
644
        }
645
        return collector;
646
    }
647
 
17 ilm 648
    public static <T> Collection<T> subtract(final Collection<T> a, final Collection<? extends T> b) {
174 ilm 649
        final Collection<T> res = a instanceof IdentitySet ? new LinkedIdentitySet<>(a) : new ArrayList<>(a);
650
        for (Iterator<? extends T> it = b.iterator(); it.hasNext();) {
651
            res.remove(it.next());
652
        }
653
        return res;
17 ilm 654
    }
655
 
656
    public static <T> Collection<T> substract(final Collection<T> a, final Collection<? extends T> b) {
174 ilm 657
        return subtract(a, b);
17 ilm 658
    }
659
 
83 ilm 660
    public static final <T> T coalesce(T o1, T o2) {
661
        return o1 != null ? o1 : o2;
662
    }
663
 
664
    public static final <T> T coalesce(T... objects) {
665
        for (T o : objects) {
666
            if (o != null)
667
                return o;
668
        }
669
        return null;
670
    }
671
 
17 ilm 672
    /**
132 ilm 673
     * Return the one and only item of <code>l</code>, otherwise <code>null</code>.
17 ilm 674
     *
675
     * @param <T> type of list.
676
     * @param l the list.
132 ilm 677
     * @param atMostOne <code>true</code> if the passed collection must not have more than one item.
678
     * @return the only item of <code>l</code>, <code>null</code> if there's not exactly one.
679
     * @throws IllegalArgumentException if <code>atMostOne</code> and <code>l.size() > 1</code>.
17 ilm 680
     */
132 ilm 681
    public static <T> T getSole(Collection<T> l, final boolean atMostOne) throws IllegalArgumentException {
682
        final int size = l.size();
683
        if (atMostOne && size > 1)
684
            throw new IllegalArgumentException("More than one");
685
        if (size != 1)
686
            return null;
687
        else if (l instanceof List)
688
            return ((List<T>) l).get(0);
689
        else
690
            return l.iterator().next();
17 ilm 691
    }
692
 
693
    public static <T> T getSole(Collection<T> l) {
132 ilm 694
        return getSole(l, false);
17 ilm 695
    }
696
 
697
    public static <T> T getFirst(Collection<T> l) {
698
        return l.size() > 0 ? l.iterator().next() : null;
699
    }
700
 
701
    /**
702
     * Return the first item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
703
     *
704
     * @param <T> type of list.
705
     * @param l the list.
706
     * @return the first item of <code>l</code> or <code>null</code>.
707
     */
708
    public static <T> T getFirst(List<T> l) {
709
        return getNoExn(l, 0);
710
    }
711
 
712
    /**
713
     * Return the last item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
714
     *
715
     * @param <T> type of list.
716
     * @param l the list.
717
     * @return the last item of <code>l</code> or <code>null</code>.
718
     */
719
    public static <T> T getLast(List<T> l) {
720
        return getNoExn(l, l.size() - 1);
721
    }
722
 
723
    /**
724
     * Return the item no <code>index</code> of <code>l</code> if it exists, otherwise
725
     * <code>null</code>.
726
     *
727
     * @param <T> type of list.
728
     * @param l the list.
729
     * @param index the wanted index.
730
     * @return the corresponding item of <code>l</code> or <code>null</code>.
731
     */
732
    public static <T> T getNoExn(List<T> l, int index) {
733
        return index >= 0 && index < l.size() ? l.get(index) : null;
734
    }
735
 
73 ilm 736
    @SuppressWarnings("rawtypes")
737
    private static final Iterator EMPTY_ITERATOR = new Iterator() {
738
        @Override
739
        public boolean hasNext() {
740
            return false;
741
        }
742
 
743
        @Override
744
        public Object next() {
745
            throw new NoSuchElementException();
746
        }
747
 
748
        @Override
749
        public void remove() {
750
            throw new UnsupportedOperationException();
751
        }
752
    };
753
 
754
    @SuppressWarnings("unchecked")
755
    public static <T> Iterator<T> emptyIterator() {
83 ilm 756
        return EMPTY_ITERATOR;
73 ilm 757
    }
758
 
759
    public static <T> LinkedList<T> toLinkedList(final Iterator<T> iter) {
760
        return addTo(iter, new LinkedList<T>());
761
    }
762
 
763
    public static <T> ArrayList<T> toArrayList(final Iterator<T> iter, final int estimatedSize) {
764
        return addTo(iter, new ArrayList<T>(estimatedSize));
765
    }
766
 
767
    public static <T, C extends Collection<? super T>> C addTo(final Iterator<T> iter, final C c) {
768
        while (iter.hasNext())
769
            c.add(iter.next());
770
        return c;
771
    }
772
 
773
    public static <T> ListIterator<T> getListIterator(final List<T> l, final boolean reversed) {
774
        if (!reversed)
775
            return l.listIterator();
776
 
777
        return reverseListIterator(l.listIterator(l.size()));
778
    }
779
 
780
    public static <T> ListIterator<T> reverseListIterator(final ListIterator<T> listIter) {
781
        if (listIter instanceof ReverseListIter)
782
            return ((ReverseListIter<T>) listIter).listIter;
783
        else
784
            return new ReverseListIter<T>(listIter);
785
    }
786
 
787
    private static final class ReverseListIter<T> implements ListIterator<T> {
788
        private final ListIterator<T> listIter;
789
 
790
        private ReverseListIter(ListIterator<T> listIter) {
791
            this.listIter = listIter;
792
        }
793
 
794
        @Override
795
        public boolean hasNext() {
796
            return this.listIter.hasPrevious();
797
        }
798
 
799
        @Override
800
        public T next() {
801
            return this.listIter.previous();
802
        }
803
 
804
        @Override
805
        public boolean hasPrevious() {
806
            return this.listIter.hasNext();
807
        }
808
 
809
        @Override
810
        public T previous() {
811
            return this.listIter.next();
812
        }
813
 
814
        @Override
815
        public int nextIndex() {
816
            return this.listIter.previousIndex();
817
        }
818
 
819
        @Override
820
        public int previousIndex() {
821
            return this.listIter.nextIndex();
822
        }
823
 
824
        @Override
825
        public void remove() {
826
            this.listIter.remove();
827
        }
828
 
829
        @Override
830
        public void set(T e) {
831
            this.listIter.set(e);
832
        }
833
 
834
        @Override
835
        public void add(T e) {
836
            throw new UnsupportedOperationException();
837
        }
838
    }
839
 
142 ilm 840
    public static <T> List<T> createList(T item1, T item2) {
841
        final List<T> res = new ArrayList<T>();
842
        res.add(item1);
843
        res.add(item2);
844
        return res;
845
    }
846
 
847
    // workaround for lack of @SafeVarargs in Java 6, TODO use Arrays.asList() in Java 7
848
    public static <T> List<T> createList(T item1, T item2, T item3) {
849
        final List<T> res = createList(item1, item2);
850
        res.add(item3);
851
        return res;
852
    }
853
 
17 ilm 854
    public static <T> Set<T> createSet(T... items) {
855
        return new HashSet<T>(Arrays.asList(items));
856
    }
857
 
73 ilm 858
    public static <T> IdentitySet<T> createIdentitySet(T... items) {
67 ilm 859
        return new IdentityHashSet<T>(Arrays.asList(items));
860
    }
861
 
862
    /**
863
     * Return an {@link IdentitySet} consisting of <code>items</code>.
864
     *
865
     * @param items the collection whose elements are to be in the result.
866
     * @return a set, possibly <code>items</code> if it's already an identity set.
867
     */
868
    public static <T> Set<T> toIdentitySet(Collection<T> items) {
65 ilm 869
        if (items instanceof IdentitySet)
870
            return (Set<T>) items;
871
        else
872
            return new IdentityHashSet<T>(items);
873
    }
874
 
73 ilm 875
    @SuppressWarnings("rawtypes")
876
    private static final IdentitySet EMPTY_SET = new EmptyIdentitySet();
877
 
878
    @SuppressWarnings("unchecked")
879
    public static <T> IdentitySet<T> emptyIdentitySet() {
83 ilm 880
        return EMPTY_SET;
73 ilm 881
    }
882
 
883
    private static final class EmptyIdentitySet extends AbstractSet<Object> implements IdentitySet<Object>, Serializable {
884
        @Override
885
        public Iterator<Object> iterator() {
886
            return emptyIterator();
887
        }
888
 
889
        @Override
890
        public int size() {
891
            return 0;
892
        }
893
 
894
        @Override
895
        public boolean contains(Object obj) {
896
            return false;
897
        }
898
 
899
        // Preserves singleton property
900
        private Object readResolve() {
901
            return EMPTY_SET;
902
        }
903
    }
904
 
17 ilm 905
    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2) {
80 ilm 906
        // arguments are ordered, so should the result
907
        final Map<K, V> res = new LinkedHashMap<K, V>();
17 ilm 908
        res.put(key, val);
909
        res.put(key2, val2);
910
        return res;
911
    }
912
 
913
    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2, K key3, V val3) {
914
        final Map<K, V> res = createMap(key, val, key2, val2);
915
        res.put(key3, val3);
916
        return res;
917
    }
918
 
149 ilm 919
    @SafeVarargs
920
    public static <T> Map<T, T> createMapFromList(final T... keyAndVal) {
921
        return createMapFromList(Arrays.asList(keyAndVal));
922
    }
923
 
924
    public static <T> Map<T, T> createMapFromList(final List<T> keyAndVal) {
925
        final int size = keyAndVal.size();
926
        if (size % 2 != 0)
927
            throw new IllegalArgumentException(size + " is not an even number of values : " + keyAndVal);
928
        // arguments are ordered, so should the result
929
        final Map<T, T> res = new LinkedHashMap<>(size);
930
        for (int i = 0; i < size; i += 2) {
931
            res.put(keyAndVal.get(i), keyAndVal.get(i + 1));
932
        }
933
        return res;
934
    }
935
 
17 ilm 936
    /**
937
     * Creates a map with null values.
938
     *
939
     * @param <K> type of key.
940
     * @param <V> type of value.
941
     * @param keys the keys of the map.
174 ilm 942
     * @return a new ordered map.
17 ilm 943
     */
944
    public static <K, V> Map<K, V> createMap(Collection<? extends K> keys) {
174 ilm 945
        // there's no way to tell if a Collection is ordered, so always use ordered map.
946
        return fillMap(new LinkedHashMap<K, V>(keys.size()), keys);
17 ilm 947
    }
948
 
949
    /**
950
     * Fills a map with null values.
951
     *
952
     * @param <K> type of key.
953
     * @param <V> type of value.
954
     * @param <M> type of map.
955
     * @param m the map to fill.
956
     * @param keys the keys to add.
957
     * @return the passed map.
958
     */
959
    public static <K, V, M extends Map<K, V>> M fillMap(final M m, Collection<? extends K> keys) {
80 ilm 960
        return fillMap(m, keys, null);
961
    }
962
 
963
    /**
964
     * Fills a map with the same value.
965
     *
966
     * @param <K> type of key.
967
     * @param <V> type of value.
968
     * @param <M> type of map.
969
     * @param m the map to fill.
970
     * @param keys the keys to add.
83 ilm 971
     * @param val the value to put.
80 ilm 972
     * @return the passed map.
973
     */
974
    public static <K, V, M extends Map<K, V>> M fillMap(final M m, final Collection<? extends K> keys, final V val) {
17 ilm 975
        for (final K key : keys)
80 ilm 976
            m.put(key, val);
17 ilm 977
        return m;
978
    }
132 ilm 979
 
980
    public static <K, V, M extends Map<K, V>> M invertMap(final M m, final Map<? extends V, ? extends K> source) {
981
        for (final Entry<? extends V, ? extends K> e : source.entrySet()) {
982
            m.put(e.getValue(), e.getKey());
983
        }
984
        return m;
985
    }
986
 
987
    public static <K, V, M extends CollectionMap2Itf<K, ?, V>> M invertMap(final M m, final Map<? extends V, ? extends K> source) {
988
        for (final Entry<? extends V, ? extends K> e : source.entrySet()) {
989
            m.add(e.getValue(), e.getKey());
990
        }
991
        return m;
992
    }
17 ilm 993
}