OpenConcerto

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

svn://code.openconcerto.org/openconcerto

Rev

Rev 149 | 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
 
420
        final List<E> result = new ArrayList<E>();
421
        for (int i = 0; i < list.size(); i++) {
422
            result.add(c.cast(list.get(i)));
423
        }
424
        return result;
425
    }
426
 
427
    /**
428
     * Cast Map
429
     *
430
     * @param <E> type of key
431
     * @param <F> type of value
432
     * @param map the map to convert
433
     * @param cKey the class of key
434
     * @param cValue the class of value
435
     * @return a new HashMap create from the <code>map</code> or null if <code>map</code> is null
436
     * @throws ClassCastException if some item of <code>map</code> have a key which the type is not
437
     *         a <code>E</code> or a value which the type is not a <code>F</code>.
438
     */
439
    public static <E, F> Map<E, F> castMap(final Map<?, ?> map, Class<E> cKey, Class<F> cValue) throws ClassCastException {
440
        if (map == null) {
441
            return null;
442
        }
443
 
444
        final Map<E, F> result = new HashMap<E, F>();
445
        for (final Entry<?, ?> mapEntry : map.entrySet()) {
446
            final E key;
447
            try {
448
                key = cKey.cast(mapEntry.getKey());
449
            } catch (final ClassCastException ex) {
450
                throw new ClassCastException("Key " + mapEntry.getKey().toString() + " is not valid: " + ex.getMessage());
451
            }
452
            final F value;
453
            try {
454
                value = cValue.cast(mapEntry.getValue());
455
            } catch (final ClassCastException ex) {
456
                throw new ClassCastException("Value " + mapEntry.getKey().toString() + " is not valid: " + ex.getMessage());
457
            }
458
            result.put(key, value);
459
        }
460
        return result;
461
    }
462
 
463
    /**
17 ilm 464
     * The number of equals item between a and b, starting from the end.
465
     *
466
     * @param <T> type of items.
467
     * @param a the first list, eg [a, b, c].
468
     * @param b the second list, eg [a, null, z, c].
469
     * @return the number of common items, eg 1.
470
     */
471
    public static <T> int equalsFromEnd(final List<T> a, final List<T> b) {
472
        return equals(a, b, true, null);
473
    }
474
 
475
    public static <T> int equalsFromStart(final List<T> a, final List<T> b) {
476
        return equals(a, b, false, null);
477
    }
478
 
479
    /**
480
     * The number of equals item between a and b, starting from the choosen end.
481
     *
482
     * @param <A> type of the first list.
483
     * @param <B> type of the second list.
484
     * @param a the first list, eg [a, b, c].
485
     * @param b the second list, eg [a, null, z, c].
486
     * @param fromEnd whether search from the start or the end, <code>true</code>.
487
     * @param transf how items of <code>a</code> should be transformed before being compared, can be
488
     *        <code>null</code>.
489
     * @return the number of common items, eg 1.
490
     */
491
    public final static <A, B> int equals(final List<A> a, final List<B> b, boolean fromEnd, ITransformer<A, B> transf) {
492
        final int sizeA = a.size();
493
        final int sizeB = b.size();
494
        final int lastI = Math.min(sizeA, sizeB);
495
        for (int i = 0; i < lastI; i++) {
496
            final A itemA = a.get(fromEnd ? sizeA - 1 - i : i);
497
            final B itemB = b.get(fromEnd ? sizeB - 1 - i : i);
498
            if (!CompareUtils.equals(transf == null ? itemA : transf.transformChecked(itemA), itemB))
499
                return i;
500
        }
501
        return lastI;
502
    }
503
 
83 ilm 504
    public final static <T> int getEqualsCount(final Iterator<? extends T> a, final Iterator<? extends T> b) {
505
        return getEqualsCount(a, b, null);
506
    }
507
 
508
    public final static <A, B> int getEqualsCount(final Iterator<A> a, final Iterator<B> b, final ITransformer<A, B> transf) {
509
        int res = 0;
510
        while (a.hasNext() && b.hasNext()) {
511
            final A itemA = a.next();
512
            final B itemB = b.next();
513
            if (!CompareUtils.equals(transf == null ? itemA : transf.transformChecked(itemA), itemB))
514
                break;
515
            res++;
516
        }
517
        return res;
518
    }
519
 
67 ilm 520
    public static <T> Collection<T> select(final Collection<T> a, final IPredicate<? super T> pred) {
521
        return select(a, pred, new ArrayList<T>());
65 ilm 522
    }
523
 
67 ilm 524
    public static <T, C extends Collection<? super T>> C select(final Collection<T> a, final IPredicate<? super T> pred, final C b) {
65 ilm 525
        for (final T item : a)
526
            if (pred.evaluateChecked(item))
527
                b.add(item);
528
        return b;
529
    }
530
 
17 ilm 531
    // avoid name collision causing eclipse bug https://bugs.eclipse.org/bugs/show_bug.cgi?id=319603
532
    @SuppressWarnings("unchecked")
533
    public static <T> Collection<T> intersection(final Collection<T> a, final Collection<T> b) {
534
        return org.apache.commons.collections.CollectionUtils.intersection(a, b);
535
    }
536
 
537
    /**
538
     * Compute the intersection of a and b. <code>null</code>s are ignored : x ∩ null = x.
539
     *
540
     * @param <T> type of collection.
541
     * @param a the first set, can be <code>null</code>.
542
     * @param b the second set, can be <code>null</code>.
543
     * @return the intersection.
544
     */
545
    @SuppressWarnings("unchecked")
546
    public static <T> Set<T> inter(final Set<T> a, final Set<T> b) {
547
        return (Set<T>) interSubtype(a, b);
548
    }
549
 
550
    public static <T> Set<? extends T> interSubtype(final Set<? extends T> a, final Set<? extends T> b) {
551
        if (a == b)
552
            return a;
553
        else if (a == null)
554
            return b;
555
        else if (b == null)
556
            return a;
557
        else if (a.size() > b.size()) {
558
            return interSubtype(b, a);
559
        }
560
 
561
        final Set<T> res = new HashSet<T>();
562
        for (final T item : a) {
563
            if (b.contains(item))
564
                res.add(item);
565
        }
566
        return res;
567
    }
568
 
569
    public static <T> Set<T> inter(final Set<T>... sets) {
570
        return inter(Arrays.asList(sets));
571
    }
572
 
573
    public static <T> Set<T> inter(final List<Set<T>> sets) {
574
        final List<Set<T>> mutable = new ArrayList<Set<T>>(sets.size());
575
        for (final Set<T> s : sets) {
576
            // ignore nulls
577
            if (s != null)
578
                mutable.add(s);
579
        }
580
 
581
        if (mutable.isEmpty())
582
            return null;
583
        else if (mutable.size() == 1)
584
            return mutable.get(0);
585
 
586
        final int indexMin = indexOfMinSize(mutable);
587
        if (indexMin != 0) {
588
            mutable.add(0, mutable.remove(indexMin));
589
            return inter(mutable);
590
        }
591
 
592
        if (mutable.get(0).isEmpty())
593
            return Collections.emptySet();
594
 
595
        // replace the first 2 by their intersection
596
        // (inter will swap as appropriate if java doesn't evalute args in source order)
597
        mutable.add(0, inter(mutable.remove(0), mutable.remove(0)));
598
        return inter(mutable);
599
    }
600
 
601
    private static final <T> int indexOfMinSize(final List<Set<T>> sets) {
602
        if (sets.isEmpty())
603
            throw new IllegalArgumentException("empty sets");
604
 
605
        int res = 0;
606
        for (int i = 1; i < sets.size(); i++) {
607
            if (sets.get(i).size() < sets.get(res).size())
608
                res = i;
609
        }
610
        return res;
611
    }
612
 
613
    /**
614
     * Returns a {@link Set} containing the union of the given {@link Set}s.
615
     *
616
     * @param <T> type of items.
617
     * @param a the first set, must not be <code>null</code>
618
     * @param b the second set, must not be <code>null</code>
619
     * @return the union of the two.
620
     */
621
    public static <T> Set<T> union(final Set<? extends T> a, final Set<? extends T> b) {
622
        final Set<T> res = new HashSet<T>(a);
623
        if (a != b)
624
            res.addAll(b);
625
        return res;
626
    }
627
 
132 ilm 628
    public static <T> Set<T> union(final Collection<? extends Collection<? extends T>> colls) {
629
        return union(new HashSet<T>(), colls);
630
    }
631
 
632
    public static <T> List<T> cat(final Collection<? extends Collection<? extends T>> colls) {
633
        return union(new ArrayList<T>(), colls);
634
    }
635
 
636
    public static <T, C extends Collection<? super T>> C union(final C collector, final Collection<? extends Collection<? extends T>> colls) {
149 ilm 637
        return union(collector, colls, Transformer.<Collection<? extends T>> nopTransformer());
132 ilm 638
    }
639
 
640
    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) {
641
        for (final A coll : colls) {
642
            collector.addAll(transf.transformChecked(coll));
643
        }
644
        return collector;
645
    }
646
 
17 ilm 647
    public static <T> Collection<T> subtract(final Collection<T> a, final Collection<? extends T> b) {
174 ilm 648
        final Collection<T> res = a instanceof IdentitySet ? new LinkedIdentitySet<>(a) : new ArrayList<>(a);
649
        for (Iterator<? extends T> it = b.iterator(); it.hasNext();) {
650
            res.remove(it.next());
651
        }
652
        return res;
17 ilm 653
    }
654
 
655
    public static <T> Collection<T> substract(final Collection<T> a, final Collection<? extends T> b) {
174 ilm 656
        return subtract(a, b);
17 ilm 657
    }
658
 
83 ilm 659
    public static final <T> T coalesce(T o1, T o2) {
660
        return o1 != null ? o1 : o2;
661
    }
662
 
663
    public static final <T> T coalesce(T... objects) {
664
        for (T o : objects) {
665
            if (o != null)
666
                return o;
667
        }
668
        return null;
669
    }
670
 
17 ilm 671
    /**
132 ilm 672
     * Return the one and only item of <code>l</code>, otherwise <code>null</code>.
17 ilm 673
     *
674
     * @param <T> type of list.
675
     * @param l the list.
132 ilm 676
     * @param atMostOne <code>true</code> if the passed collection must not have more than one item.
677
     * @return the only item of <code>l</code>, <code>null</code> if there's not exactly one.
678
     * @throws IllegalArgumentException if <code>atMostOne</code> and <code>l.size() > 1</code>.
17 ilm 679
     */
132 ilm 680
    public static <T> T getSole(Collection<T> l, final boolean atMostOne) throws IllegalArgumentException {
681
        final int size = l.size();
682
        if (atMostOne && size > 1)
683
            throw new IllegalArgumentException("More than one");
684
        if (size != 1)
685
            return null;
686
        else if (l instanceof List)
687
            return ((List<T>) l).get(0);
688
        else
689
            return l.iterator().next();
17 ilm 690
    }
691
 
692
    public static <T> T getSole(Collection<T> l) {
132 ilm 693
        return getSole(l, false);
17 ilm 694
    }
695
 
696
    public static <T> T getFirst(Collection<T> l) {
697
        return l.size() > 0 ? l.iterator().next() : null;
698
    }
699
 
700
    /**
701
     * Return the first item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
702
     *
703
     * @param <T> type of list.
704
     * @param l the list.
705
     * @return the first item of <code>l</code> or <code>null</code>.
706
     */
707
    public static <T> T getFirst(List<T> l) {
708
        return getNoExn(l, 0);
709
    }
710
 
711
    /**
712
     * Return the last item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
713
     *
714
     * @param <T> type of list.
715
     * @param l the list.
716
     * @return the last item of <code>l</code> or <code>null</code>.
717
     */
718
    public static <T> T getLast(List<T> l) {
719
        return getNoExn(l, l.size() - 1);
720
    }
721
 
722
    /**
723
     * Return the item no <code>index</code> of <code>l</code> if it exists, otherwise
724
     * <code>null</code>.
725
     *
726
     * @param <T> type of list.
727
     * @param l the list.
728
     * @param index the wanted index.
729
     * @return the corresponding item of <code>l</code> or <code>null</code>.
730
     */
731
    public static <T> T getNoExn(List<T> l, int index) {
732
        return index >= 0 && index < l.size() ? l.get(index) : null;
733
    }
734
 
73 ilm 735
    @SuppressWarnings("rawtypes")
736
    private static final Iterator EMPTY_ITERATOR = new Iterator() {
737
        @Override
738
        public boolean hasNext() {
739
            return false;
740
        }
741
 
742
        @Override
743
        public Object next() {
744
            throw new NoSuchElementException();
745
        }
746
 
747
        @Override
748
        public void remove() {
749
            throw new UnsupportedOperationException();
750
        }
751
    };
752
 
753
    @SuppressWarnings("unchecked")
754
    public static <T> Iterator<T> emptyIterator() {
83 ilm 755
        return EMPTY_ITERATOR;
73 ilm 756
    }
757
 
758
    public static <T> LinkedList<T> toLinkedList(final Iterator<T> iter) {
759
        return addTo(iter, new LinkedList<T>());
760
    }
761
 
762
    public static <T> ArrayList<T> toArrayList(final Iterator<T> iter, final int estimatedSize) {
763
        return addTo(iter, new ArrayList<T>(estimatedSize));
764
    }
765
 
766
    public static <T, C extends Collection<? super T>> C addTo(final Iterator<T> iter, final C c) {
767
        while (iter.hasNext())
768
            c.add(iter.next());
769
        return c;
770
    }
771
 
772
    public static <T> ListIterator<T> getListIterator(final List<T> l, final boolean reversed) {
773
        if (!reversed)
774
            return l.listIterator();
775
 
776
        return reverseListIterator(l.listIterator(l.size()));
777
    }
778
 
779
    public static <T> ListIterator<T> reverseListIterator(final ListIterator<T> listIter) {
780
        if (listIter instanceof ReverseListIter)
781
            return ((ReverseListIter<T>) listIter).listIter;
782
        else
783
            return new ReverseListIter<T>(listIter);
784
    }
785
 
786
    private static final class ReverseListIter<T> implements ListIterator<T> {
787
        private final ListIterator<T> listIter;
788
 
789
        private ReverseListIter(ListIterator<T> listIter) {
790
            this.listIter = listIter;
791
        }
792
 
793
        @Override
794
        public boolean hasNext() {
795
            return this.listIter.hasPrevious();
796
        }
797
 
798
        @Override
799
        public T next() {
800
            return this.listIter.previous();
801
        }
802
 
803
        @Override
804
        public boolean hasPrevious() {
805
            return this.listIter.hasNext();
806
        }
807
 
808
        @Override
809
        public T previous() {
810
            return this.listIter.next();
811
        }
812
 
813
        @Override
814
        public int nextIndex() {
815
            return this.listIter.previousIndex();
816
        }
817
 
818
        @Override
819
        public int previousIndex() {
820
            return this.listIter.nextIndex();
821
        }
822
 
823
        @Override
824
        public void remove() {
825
            this.listIter.remove();
826
        }
827
 
828
        @Override
829
        public void set(T e) {
830
            this.listIter.set(e);
831
        }
832
 
833
        @Override
834
        public void add(T e) {
835
            throw new UnsupportedOperationException();
836
        }
837
    }
838
 
142 ilm 839
    public static <T> List<T> createList(T item1, T item2) {
840
        final List<T> res = new ArrayList<T>();
841
        res.add(item1);
842
        res.add(item2);
843
        return res;
844
    }
845
 
846
    // workaround for lack of @SafeVarargs in Java 6, TODO use Arrays.asList() in Java 7
847
    public static <T> List<T> createList(T item1, T item2, T item3) {
848
        final List<T> res = createList(item1, item2);
849
        res.add(item3);
850
        return res;
851
    }
852
 
17 ilm 853
    public static <T> Set<T> createSet(T... items) {
854
        return new HashSet<T>(Arrays.asList(items));
855
    }
856
 
73 ilm 857
    public static <T> IdentitySet<T> createIdentitySet(T... items) {
67 ilm 858
        return new IdentityHashSet<T>(Arrays.asList(items));
859
    }
860
 
861
    /**
862
     * Return an {@link IdentitySet} consisting of <code>items</code>.
863
     *
864
     * @param items the collection whose elements are to be in the result.
865
     * @return a set, possibly <code>items</code> if it's already an identity set.
866
     */
867
    public static <T> Set<T> toIdentitySet(Collection<T> items) {
65 ilm 868
        if (items instanceof IdentitySet)
869
            return (Set<T>) items;
870
        else
871
            return new IdentityHashSet<T>(items);
872
    }
873
 
73 ilm 874
    @SuppressWarnings("rawtypes")
875
    private static final IdentitySet EMPTY_SET = new EmptyIdentitySet();
876
 
877
    @SuppressWarnings("unchecked")
878
    public static <T> IdentitySet<T> emptyIdentitySet() {
83 ilm 879
        return EMPTY_SET;
73 ilm 880
    }
881
 
882
    private static final class EmptyIdentitySet extends AbstractSet<Object> implements IdentitySet<Object>, Serializable {
883
        @Override
884
        public Iterator<Object> iterator() {
885
            return emptyIterator();
886
        }
887
 
888
        @Override
889
        public int size() {
890
            return 0;
891
        }
892
 
893
        @Override
894
        public boolean contains(Object obj) {
895
            return false;
896
        }
897
 
898
        // Preserves singleton property
899
        private Object readResolve() {
900
            return EMPTY_SET;
901
        }
902
    }
903
 
17 ilm 904
    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2) {
80 ilm 905
        // arguments are ordered, so should the result
906
        final Map<K, V> res = new LinkedHashMap<K, V>();
17 ilm 907
        res.put(key, val);
908
        res.put(key2, val2);
909
        return res;
910
    }
911
 
912
    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2, K key3, V val3) {
913
        final Map<K, V> res = createMap(key, val, key2, val2);
914
        res.put(key3, val3);
915
        return res;
916
    }
917
 
149 ilm 918
    @SafeVarargs
919
    public static <T> Map<T, T> createMapFromList(final T... keyAndVal) {
920
        return createMapFromList(Arrays.asList(keyAndVal));
921
    }
922
 
923
    public static <T> Map<T, T> createMapFromList(final List<T> keyAndVal) {
924
        final int size = keyAndVal.size();
925
        if (size % 2 != 0)
926
            throw new IllegalArgumentException(size + " is not an even number of values : " + keyAndVal);
927
        // arguments are ordered, so should the result
928
        final Map<T, T> res = new LinkedHashMap<>(size);
929
        for (int i = 0; i < size; i += 2) {
930
            res.put(keyAndVal.get(i), keyAndVal.get(i + 1));
931
        }
932
        return res;
933
    }
934
 
17 ilm 935
    /**
936
     * Creates a map with null values.
937
     *
938
     * @param <K> type of key.
939
     * @param <V> type of value.
940
     * @param keys the keys of the map.
174 ilm 941
     * @return a new ordered map.
17 ilm 942
     */
943
    public static <K, V> Map<K, V> createMap(Collection<? extends K> keys) {
174 ilm 944
        // there's no way to tell if a Collection is ordered, so always use ordered map.
945
        return fillMap(new LinkedHashMap<K, V>(keys.size()), keys);
17 ilm 946
    }
947
 
948
    /**
949
     * Fills a map with null values.
950
     *
951
     * @param <K> type of key.
952
     * @param <V> type of value.
953
     * @param <M> type of map.
954
     * @param m the map to fill.
955
     * @param keys the keys to add.
956
     * @return the passed map.
957
     */
958
    public static <K, V, M extends Map<K, V>> M fillMap(final M m, Collection<? extends K> keys) {
80 ilm 959
        return fillMap(m, keys, null);
960
    }
961
 
962
    /**
963
     * Fills a map with the same value.
964
     *
965
     * @param <K> type of key.
966
     * @param <V> type of value.
967
     * @param <M> type of map.
968
     * @param m the map to fill.
969
     * @param keys the keys to add.
83 ilm 970
     * @param val the value to put.
80 ilm 971
     * @return the passed map.
972
     */
973
    public static <K, V, M extends Map<K, V>> M fillMap(final M m, final Collection<? extends K> keys, final V val) {
17 ilm 974
        for (final K key : keys)
80 ilm 975
            m.put(key, val);
17 ilm 976
        return m;
977
    }
132 ilm 978
 
979
    public static <K, V, M extends Map<K, V>> M invertMap(final M m, final Map<? extends V, ? extends K> source) {
980
        for (final Entry<? extends V, ? extends K> e : source.entrySet()) {
981
            m.put(e.getValue(), e.getKey());
982
        }
983
        return m;
984
    }
985
 
986
    public static <K, V, M extends CollectionMap2Itf<K, ?, V>> M invertMap(final M m, final Map<? extends V, ? extends K> source) {
987
        for (final Entry<? extends V, ? extends K> e : source.entrySet()) {
988
            m.add(e.getValue(), e.getKey());
989
        }
990
        return m;
991
    }
17 ilm 992
}