/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 * 
 * Copyright 2008 jOpenDocument, by ILM Informatique. All rights reserved.
 * 
 * The contents of this file are subject to the terms of the GNU
 * General Public License Version 3 only ("GPL").  
 * You may not use this file except in compliance with the License. 
 * You can obtain a copy of the License at http://www.gnu.org/licenses/gpl-3.0.html
 * See the License for the specific language governing permissions and limitations under the License.
 * 
 * When distributing the software, include this License Header Notice in each file.
 * 
 */

package org.jopendocument.util;

import org.jopendocument.util.cc.ITransformer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.RandomAccess;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.regex.Pattern;

import org.apache.commons.collections.Transformer;
import org.apache.commons.collections.TransformerUtils;

/**
 * Une classe regroupant des méthodes utilitaires pour les collections.
 * 
 * @author ILM Informatique 30 sept. 2004
 */
public class CollectionUtils extends org.apache.commons.collections.CollectionUtils {

    /**
     * Concatene une collection. Cette méthode va appliquer un transformation sur chaque élément
     * avant d'appeler toString(). join([-1, 3, 0], " ,", doubleTransformer) == "-2, 6, 0"
     * 
     * @param <E> type of items
     * @param c la collection a concaténer.
     * @param sep le séparateur entre chaque élément.
     * @param tf la transformation à appliquer à chaque élément.
     * @return la chaine composée de chacun des éléments séparés par <code>sep</code>.
     */
    static public final <E> String join(final Collection<E> c, final String sep, final ITransformer<? super E, ?> tf) {
        if (c.size() == 0)
            return "";

        final StringBuffer res = new StringBuffer(c.size() * 4);
        if (c instanceof RandomAccess && c instanceof List) {
            final List<E> list = (List<E>) c;
            final int stop = c.size() - 1;
            for (int i = 0; i < stop; i++) {
                res.append(tf.transformChecked(list.get(i)));
                res.append(sep);

            }
            res.append(tf.transformChecked(list.get(stop)));
        } else {
            final Iterator<E> iter = c.iterator();
            while (iter.hasNext()) {
                final E elem = iter.next();
                res.append(tf.transformChecked(elem));
                if (iter.hasNext())
                    res.append(sep);
            }
        }
        return res.toString();
    }

    /**
     * Concatene une collection en appelant simplement toString() sur chaque élément.
     * 
     * @param <T> type of collection
     * @param c la collection a concaténer.
     * @param sep le séparateur entre chaque élément.
     * @return la chaine composée de chacun des éléments séparés par <code>sep</code>.
     * @see #join(Collection, String, ITransformer)
     */
    static public <T> String join(Collection<T> c, String sep) {
        return join(c, sep, org.jopendocument.util.cc.Transformer.<T> nopTransformer());
    }

    // *** split

    private static final Pattern COMMA = Pattern.compile("\\p{Space}*,\\p{Space}*");

    static public List<String> split(String s) {
        return split(s, COMMA);
    }

    static public List<String> split(String s, String sep) {
        return split(s, Pattern.compile(sep));
    }

    /**
     * Split a string into a list based on a pattern.
     * 
     * @param s the string to split.
     * @param pattern the pattern where to cut the string.
     * @return the splitted string, empty list if <code>s</code> is "".
     */
    static public List<String> split(String s, Pattern pattern) {
        return s.length() == 0 ? Collections.<String> emptyList() : Arrays.asList(pattern.split(s));
    }

    /**
     * Return an index between <code>0</code> and <code>l.size()</code> inclusive. If <code>i</code>
     * is negative, it is added to <code>l.size()</code> (but bounded to 0), ie for a list of 3
     * items, -1 is the index of the last item ; -3 and -4 are both the first. If <code>i</code> is
     * greater than <code>l.size()</code> then <code>l.size()</code> is returned.
     * 
     * <pre>
     *    a  b  c  a  b  c
     *   -3 -2 -1  0  1  2  3
     * </pre>
     * 
     * @param l the list, eg a list of 3 items.
     * @param i the virtual index, eg -1.
     * @return the real index, eg 2.
     */
    static public int getValidIndex(final List<?> l, final int i) {
        if (i > l.size()) {
            return l.size();
        } else if (i >= 0) {
            return i;
        } else if (l.size() + i <= 0)
            return 0;
        else
            return l.size() + i;
    }

    /**
     * Deletes a slice of a list. Pass indexes to {@link #getValidIndex(List, int)} to allow
     * delete(l, 0, -1) to clear l or delete(l, -2, -2) to remove the penultimate item.
     * 
     * @param l the list to delete from.
     * @param from the first index to be removed (inclusive).
     * @param to the last index to be removed (inclusive).
     */
    static public void delete(List<?> l, int from, int to) {
        if (!l.isEmpty())
            l.subList(getValidIndex(l, from), getValidIndex(l, to) + 1).clear();
    }

    /**
     * Deletes the tail of a list. The resulting list will have a size of <code>from</code>.
     * 
     * @param l the list to delete from.
     * @param from the first index to be removed (inclusive).
     */
    static public void delete(List<?> l, int from) {
        delete(l, from, -1);
    }

    /**
     * Permet d'organiser une collection en une hiérarchie à l'aide de Map. Avec <code>
     * Col = [
     * Obs1(bat=BAT A, local=A1, num=1),
     * Obs2(bat=BAT B, local=B1, num=2),
     * Obs3(bat=BAT B, local=B2, num=3),
     * Obs4(bat=BAT B, local=B2, num=4)
     * ]
     * <code>
     * ainsi que deux extracteurs pour trouver le batiment et le local, et enfin itemOrdering suivant le numero, on a
     * { BAT A => {A1 => {Obs1}}, {BAT B => {B1 => {Obs2}, B2 => {Obs3, Obs4}}}}.
     * 
     * @param col la collection à organiser.
     * @param propExtractors les extracteurs de propriétes.
     * @param propComp les Comparator pour les propriétés renvoyées par les extracteurs, peut être
     *        <code>null</code> si les propriétés sont des Comparable.
     * @param itemOrdering comment ordonner les éléments dans la dernière tranche, peut être
     *        <code>null</code> si les éléments sont des Comparable.
     * @return une hiérarchie de SortedMap et en dernier un SortedSet.
     */
    static public final SortedMap organize(Collection col, List<? extends Transformer> propExtractors, List<? extends Comparator> propComp, Comparator itemOrdering) {
        if (propExtractors.size() == 0)
            throw new IllegalArgumentException("Empty property extractors");

        if (propComp == null)
            propComp = Collections.nCopies(propExtractors.size(), null);
        else if (propExtractors.size() != propComp.size())
            throw new IllegalArgumentException("Size mismatch between " + propExtractors + " and " + propComp);

        final SortedMap res = new TreeMap(propComp.get(0));

        Iterator iter = col.iterator();
        while (iter.hasNext()) {
            final Object item = iter.next();
            Map m = res;

            for (int i = 0; i < propExtractors.size() - 1; i++) {
                final Transformer extractor = propExtractors.get(i);
                final Object property = extractor.transform(item);
                Map newM = (Map) m.get(property);
                if (newM == null) {
                    newM = new TreeMap(propComp.get(i + 1));
                    m.put(property, newM);
                }
                m = newM;
            }
            final Object property = propExtractors.get(propExtractors.size() - 1).transform(item);
            SortedSet s = (SortedSet) m.get(property);
            if (s == null) {
                s = new TreeSet(itemOrdering);
                m.put(property, s);
            }
            s.add(item);
        }

        return res;
    }

    /**
     * Permet d'aplatir une hiérarchie. Exemple :
     * 
     * <pre>
     *   A-
     *      A1
     *      A2
     *   B-
     *      B1
     *         B11
     *         B12
     * </pre>
     * 
     * devient <code>[A, A1, A2, B, B1, B11, B12]</code>.
     * 
     * @param hierarchy la hiérarchie à aplatir.
     * @param itemTransf la transformation à faire sur les feuilles.
     * @return la liste correspondante.
     */
    static public final List flatten(Map hierarchy, Transformer itemTransf) {
        final List res = new ArrayList();

        final Iterator iter = hierarchy.keySet().iterator();
        while (iter.hasNext()) {
            final Object obj = iter.next();
            res.add(obj);
            final Object value = hierarchy.get(obj);
            if (value instanceof Map)
                res.addAll(flatten((Map) value, itemTransf));
            else if (value instanceof Collection) {
                final Collection items = (Collection) value;
                final Iterator itemIter = items.iterator();
                while (itemIter.hasNext()) {
                    final Object item = itemIter.next();
                    res.add(itemTransf.transform(item));
                }
            } else
                throw new IllegalArgumentException("Illegal value: " + value);
        }
        return res;
    }

    /**
     * Permet d'aplatir une hiérarchie.
     * 
     * @param hierarchy la hiérarchie à aplatir.
     * @return la liste correspondante.
     */
    static public final List flatten(Map hierarchy) {
        return flatten(hierarchy, TransformerUtils.nopTransformer());
    }

    /**
     * Convertit une map en 2 listes, une pour les clefs, une pour les valeurs.
     * 
     * @param map la Map à convertir.
     * @return un tuple de 2 List, en 0 les clefs, en 1 les valeurs.
     * @param <K> type of key
     * @param <V> type of value
     */
    static public <K, V> Tuple2<List<K>, List<V>> mapToLists(Map<K, V> map) {
        final List<K> keys = new ArrayList<K>(map.size());
        final List<V> vals = new ArrayList<V>(map.size());
        for (final Map.Entry<K, V> e : map.entrySet()) {
            keys.add(e.getKey());
            vals.add(e.getValue());
        }

        return Tuple2.create(keys, vals);
    }

    /**
     * Add entries from <code>toAdd</code> into <code>map</code> only if the key is not already
     * present.
     * 
     * @param <K> type of keys.
     * @param <V> type of values.
     * @param map the map to fill.
     * @param toAdd the entries to add.
     * @return <code>map</code>.
     */
    static public <K, V> Map<K, V> addIfNotPresent(Map<K, V> map, Map<? extends K, ? extends V> toAdd) {
        for (final Map.Entry<? extends K, ? extends V> e : toAdd.entrySet()) {
            if (!map.containsKey(e.getKey()))
                map.put(e.getKey(), e.getValue());
        }
        return map;
    }

    /**
     * Compute the index that have changed (added or removed) between 2 lists. One of the lists MUST
     * be a sublist of the other, ie the to go from one to the other we just add or remove items but
     * we don't do both.
     * 
     * @param oldList the first list.
     * @param newList the second list.
     * @return a list of Integer.
     * @param <E> type of item
     * @throws IllegalStateException if one list is not a sublist of the other.
     */
    static public <E> List<Integer> getIndexesChanged(List<E> oldList, List<E> newList) {
        final List<E> longer;
        final List<E> shorter;
        if (newList.size() > oldList.size()) {
            longer = new ArrayList<E>(newList);
            shorter = new ArrayList<E>(oldList);
        } else {
            longer = new ArrayList<E>(oldList);
            shorter = new ArrayList<E>(newList);
        }

        final List<Integer> res = new ArrayList<Integer>();
        int offset = 0;
        while (shorter.size() > 0) {
            if (longer.size() < shorter.size())
                throw new IllegalStateException(shorter + " is not a sublist of " + longer);
            // compare nulls
            if (CompareUtils.equals(shorter.get(0), longer.get(0))) {
                shorter.remove(0);
                longer.remove(0);
            } else {
                longer.remove(0);
                res.add(offset);
            }
            offset++;
        }

        for (int i = 0; i < longer.size(); i++) {
            res.add(i + offset);
        }

        return res;
    }

    /**
     * Aggregate a list of ints into a list of intervals. Eg aggregate([-1,0,1,2,5]) returns
     * [[-1,2], [5,5]].
     * 
     * @param ints a list of Integer strictly increasing.
     * @return a list of int[2].
     */
    static public List<int[]> aggregate(Collection<? extends Number> ints) {
        final List<int[]> res = new ArrayList<int[]>();
        int[] currentInterval = null;
        for (final Number n : ints) {
            final int index = n.intValue();
            if (currentInterval == null || index != currentInterval[1] + 1) {
                currentInterval = new int[2];
                currentInterval[0] = index;
                currentInterval[1] = currentInterval[0];
                res.add(currentInterval);
            } else {
                currentInterval[1] = index;
            }
        }
        return res;
    }

    /**
     * Test whether col2 is contained in col1.
     * 
     * @param <T> type of collection
     * @param col1 the first collection
     * @param col2 the second collection
     * @return <code>null</code> if col1 contains all of col2, else return the extra items that col2
     *         have.
     */
    static public <T> Set<T> contains(final Set<T> col1, final Set<T> col2) {
        if (col1.containsAll(col2))
            return null;
        else {
            final Set<T> names = new HashSet<T>(col2);
            names.removeAll(col1);
            return names;
        }
    }

    /**
     * Convert an array to a list of a different type.
     * 
     * @param <U> type of array
     * @param <T> type of list
     * @param array the array to convert, eg new Object[]{"a", "b"}.
     * @param clazz the class of the list items, eg String.class.
     * @return all items of <code>array</code> into a list, eg ["a", "b"].
     * @throws ClassCastException if some item of <code>array</code> is not a <code>T</code>.
     */
    static public <U, T extends U> List<T> castToList(U[] array, Class<T> clazz) throws ClassCastException {
        final List<T> res = new ArrayList<T>(array.length);
        for (final U item : array) {
            res.add(clazz.cast(item));
        }
        return res;
    }

    /**
     * The number of equals item between a and b, starting from the end.
     * 
     * @param <T> type of items.
     * @param a the first list, eg [a, b, c].
     * @param b the second list, eg [a, null, z, c].
     * @return the number of common items, eg 1.
     */
    public static <T> int equalsFromEnd(final List<T> a, final List<T> b) {
        return equals(a, b, true, null);
    }

    public static <T> int equalsFromStart(final List<T> a, final List<T> b) {
        return equals(a, b, false, null);
    }

    /**
     * The number of equals item between a and b, starting from the choosen end.
     * 
     * @param <A> type of the first list.
     * @param <B> type of the second list.
     * @param a the first list, eg [a, b, c].
     * @param b the second list, eg [a, null, z, c].
     * @param fromEnd whether search from the start or the end, <code>true</code>.
     * @param transf how items of <code>a</code> should be transformed before being compared, can be
     *        <code>null</code>.
     * @return the number of common items, eg 1.
     */
    public final static <A, B> int equals(final List<A> a, final List<B> b, boolean fromEnd, ITransformer<A, B> transf) {
        final int sizeA = a.size();
        final int sizeB = b.size();
        final int lastI = Math.min(sizeA, sizeB);
        for (int i = 0; i < lastI; i++) {
            final A itemA = a.get(fromEnd ? sizeA - 1 - i : i);
            final B itemB = b.get(fromEnd ? sizeB - 1 - i : i);
            if (!CompareUtils.equals(transf == null ? itemA : transf.transformChecked(itemA), itemB))
                return i;
        }
        return lastI;
    }

    @SuppressWarnings("unchecked")
    public static <T> Collection<T> inter(final Collection<T> a, final Collection<T> b) {
        return org.apache.commons.collections.CollectionUtils.intersection(a, b);
    }

    /**
     * Compute the intersection of a and b. <code>null</code>s are ignored : x ∩ null = x.
     * 
     * @param <T> type of collection.
     * @param a the first set, can be <code>null</code>.
     * @param b the second set, can be <code>null</code>.
     * @return the intersection.
     */
    public static <T> Set<T> inter(final Set<T> a, final Set<T> b) {
        if (a == b)
            return a;
        else if (a == null)
            return b;
        else if (b == null)
            return a;
        else if (a.size() > b.size()) {
            return inter(b, a);
        }

        final Set<T> res = new HashSet<T>();
        for (final T item : a) {
            if (b.contains(item))
                res.add(item);
        }
        return res;
    }

    public static <T> Set<T> inter(final Set<T>... sets) {
        return inter(Arrays.asList(sets));
    }

    public static <T> Set<T> inter(final List<Set<T>> sets) {
        final List<Set<T>> mutable = new ArrayList<Set<T>>(sets.size());
        for (final Set<T> s : sets) {
            // ignore nulls
            if (s != null)
                mutable.add(s);
        }

        if (mutable.isEmpty())
            return null;
        else if (mutable.size() == 1)
            return mutable.get(0);

        final int indexMin = indexOfMinSize(mutable);
        if (indexMin != 0) {
            mutable.add(0, mutable.remove(indexMin));
            return inter(mutable);
        }

        if (mutable.get(0).isEmpty())
            return Collections.emptySet();

        // replace the first 2 by their intersection
        // (inter will swap as appropriate if java doesn't evalute args in source order)
        mutable.add(0, inter(mutable.remove(0), mutable.remove(0)));
        return inter(mutable);
    }

    private static final <T> int indexOfMinSize(final List<Set<T>> sets) {
        if (sets.isEmpty())
            throw new IllegalArgumentException("empty sets");

        int res = 0;
        for (int i = 1; i < sets.size(); i++) {
            if (sets.get(i).size() < sets.get(res).size())
                res = i;
        }
        return res;
    }

    /**
     * Returns a {@link Set} containing the union of the given {@link Set}s.
     * 
     * @param <T> type of items.
     * @param a the first set, must not be <code>null</code>
     * @param b the second set, must not be <code>null</code>
     * @return the union of the two.
     */
    public static <T> Set<T> union(final Set<? extends T> a, final Set<? extends T> b) {
        final Set<T> res = new HashSet<T>(a);
        if (a != b)
            res.addAll(b);
        return res;
    }

    @SuppressWarnings("unchecked")
    public static <T> Collection<T> subtract(final Collection<T> a, final Collection<? extends T> b) {
        return org.apache.commons.collections.CollectionUtils.subtract(a, b);
    }

    @SuppressWarnings("unchecked")
    public static <T> Collection<T> substract(final Collection<T> a, final Collection<? extends T> b) {
        return org.apache.commons.collections.CollectionUtils.subtract(a, b);
    }

    /**
     * Return the first item of <code>l</code> if it's the only one, otherwise <code>null</code>.
     * 
     * @param <T> type of list.
     * @param l the list.
     * @return the first item of <code>l</code> or <code>null</code>.
     */
    public static <T> T getSole(List<T> l) {
        return l.size() == 1 ? l.get(0) : null;
    }

    public static <T> T getSole(Collection<T> l) {
        return l.size() == 1 ? l.iterator().next() : null;
    }

    public static <T> T getFirst(Collection<T> l) {
        return l.size() > 0 ? l.iterator().next() : null;
    }

    /**
     * Return the first item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
     * 
     * @param <T> type of list.
     * @param l the list.
     * @return the first item of <code>l</code> or <code>null</code>.
     */
    public static <T> T getFirst(List<T> l) {
        return getNoExn(l, 0);
    }

    /**
     * Return the last item of <code>l</code> if it isn't empty, otherwise <code>null</code>.
     * 
     * @param <T> type of list.
     * @param l the list.
     * @return the last item of <code>l</code> or <code>null</code>.
     */
    public static <T> T getLast(List<T> l) {
        return getNoExn(l, l.size() - 1);
    }

    /**
     * Return the item no <code>index</code> of <code>l</code> if it exists, otherwise
     * <code>null</code>.
     * 
     * @param <T> type of list.
     * @param l the list.
     * @param index the wanted index.
     * @return the corresponding item of <code>l</code> or <code>null</code>.
     */
    public static <T> T getNoExn(List<T> l, int index) {
        return index >= 0 && index < l.size() ? l.get(index) : null;
    }

    public static <T> Set<T> createSet(T... items) {
        return new HashSet<T>(Arrays.asList(items));
    }

    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2) {
        final HashMap<K, V> res = new HashMap<K, V>();
        res.put(key, val);
        res.put(key2, val2);
        return res;
    }

    public static <K, V> Map<K, V> createMap(K key, V val, K key2, V val2, K key3, V val3) {
        final Map<K, V> res = createMap(key, val, key2, val2);
        res.put(key3, val3);
        return res;
    }

    /**
     * Creates a map with null values.
     * 
     * @param <K> type of key.
     * @param <V> type of value.
     * @param keys the keys of the map.
     * @return a new map, if <code>keys</code> is a {@link List} it will be ordered.
     */
    public static <K, V> Map<K, V> createMap(Collection<? extends K> keys) {
        return fillMap(keys instanceof List ? new LinkedHashMap<K, V>(keys.size()) : new HashMap<K, V>(keys.size()), keys);
    }

    /**
     * Fills a map with null values.
     * 
     * @param <K> type of key.
     * @param <V> type of value.
     * @param <M> type of map.
     * @param m the map to fill.
     * @param keys the keys to add.
     * @return the passed map.
     */
    public static <K, V, M extends Map<K, V>> M fillMap(final M m, Collection<? extends K> keys) {
        for (final K key : keys)
            m.put(key, null);
        return m;
    }
}