package org.codehaus.plexus.util;
   
   /*
    * Copyright The Codehaus Foundation.
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.NoSuchElementException;
  import java.util.Set;
  
  /**
   * @author <a href="mailto:olamy@codehaus.org">olamy</a>
   *
   */
  public class CollectionUtils {
      // ----------------------------------------------------------------------
      // Static methods that can probably be moved to a real util class.
      // ----------------------------------------------------------------------
  
      /**
       * Take a dominant and recessive Map and merge the key:value pairs where the recessive Map may add key:value pairs
       * to the dominant Map but may not override any existing key:value pairs. If we have two Maps, a dominant and
       * recessive, and their respective keys are as follows: dominantMapKeys = { a, b, c, d, e, f } recessiveMapKeys = {
       * a, b, c, x, y, z } Then the result should be the following: resultantKeys = { a, b, c, d, e, f, x, y, z }
       *
       * @param dominantMap Dominant Map.
       * @param recessiveMap Recessive Map.
       * @param <K> type
       * @param <V> type
       * @return The result map with combined dominant and recessive values.
       */
      public static <K, V> Map<K, V> mergeMaps(Map<K, V> dominantMap, Map<K, V> recessiveMap) {
  
          if (dominantMap == null && recessiveMap == null) {
              return null;
          }
  
          if (dominantMap != null && recessiveMap == null) {
              return dominantMap;
          }
  
          if (dominantMap == null) {
              return recessiveMap;
          }
  
          Map<K, V> result = new HashMap<>();
  
          // Grab the keys from the dominant and recessive maps.
          Set<K> dominantMapKeys = dominantMap.keySet();
          Set<K> recessiveMapKeys = recessiveMap.keySet();
  
          // Create the set of keys that will be contributed by the
          // recessive Map by subtracting the intersection of keys
          // from the recessive Map's keys.
          Collection<K> contributingRecessiveKeys = CollectionUtils.subtract(
                  recessiveMapKeys, CollectionUtils.intersection(dominantMapKeys, recessiveMapKeys));
  
          result.putAll(dominantMap);
  
          // Now take the keys we just found and extract the values from
          // the recessiveMap and put the key:value pairs into the dominantMap.
          for (K key : contributingRecessiveKeys) {
              result.put(key, recessiveMap.get(key));
          }
  
          return result;
      }
  
      /**
       * Take a series of <code>Map</code>s and merge them where the ordering of the array from 0..n is the dominant
       * order.
       *
       * @param maps An array of Maps to merge.
       * @param <K> type
       * @param <V> type
       * @return Map The result Map produced after the merging process.
       */
      public static <K, V> Map<K, V> mergeMaps(Map<K, V>[] maps) {
          Map<K, V> result;
  
          if (maps.length == 0) {
             result = null;
         } else if (maps.length == 1) {
             result = maps[0];
         } else {
             result = mergeMaps(maps[0], maps[1]);
 
             for (int i = 2; i < maps.length; i++) {
                 result = mergeMaps(result, maps[i]);
             }
         }
 
         return result;
     }
 
     /**
      * <p>
      * Returns a {@link Collection} containing the intersection of the given {@link Collection}s.
      * </p>
      * The cardinality of each element in the returned {@link Collection} will be equal to the minimum of the
      * cardinality of that element in the two given {@link Collection}s.
      *
      * @param a The first collection
      * @param b The second collection
      * @param <E> the type
      * @see Collection#retainAll
      * @return The intersection of a and b, never null
      */
     public static <E> Collection<E> intersection(final Collection<E> a, final Collection<E> b) {
         ArrayList<E> list = new ArrayList<>();
         Map<E, Integer> mapa = getCardinalityMap(a);
         Map<E, Integer> mapb = getCardinalityMap(b);
         Set<E> elts = new HashSet<>(a);
         elts.addAll(b);
         for (E obj : elts) {
             for (int i = 0, m = Math.min(getFreq(obj, mapa), getFreq(obj, mapb)); i < m; i++) {
                 list.add(obj);
             }
         }
         return list;
     }
 
     /**
      * Returns a {@link Collection} containing <code>a - b</code>. The cardinality of each element <i>e</i> in
      * the returned {@link Collection} will be the cardinality of <i>e</i> in <i>a</i> minus the cardinality of <i>e</i>
      * in <i>b</i>, or zero, whichever is greater.
      *
      * @param a The start collection
      * @param b The collection that will be subtracted
      * @param <T> the type
      * @see Collection#removeAll
      * @return The result of the subtraction
      */
     public static <T> Collection<T> subtract(final Collection<T> a, final Collection<T> b) {
         ArrayList<T> list = new ArrayList<>(a);
         for (T aB : b) {
             list.remove(aB);
         }
         return list;
     }
 
     /**
      * Returns a {@link Map} mapping each unique element in the given {@link Collection} to an {@link Integer}
      * representing the number of occurrences of that element in the {@link Collection}. An entry that maps to
      * <code>null</code> indicates that the element does not appear in the given {@link Collection}.
      *
      * @param col The collection to count cardinalities for
      * @param <E> the type
      * @return A map of counts, indexed on each element in the collection
      */
     public static <E> Map<E, Integer> getCardinalityMap(final Collection<E> col) {
         HashMap<E, Integer> count = new HashMap<>();
         for (E obj : col) {
             Integer c = count.get(obj);
             if (null == c) {
                 count.put(obj, 1);
             } else {
                 count.put(obj, c + 1);
             }
         }
         return count;
     }
 
     public static <E> List<E> iteratorToList(Iterator<E> it) {
         if (it == null) {
             throw new NullPointerException("it cannot be null.");
         }
 
         List<E> list = new ArrayList<E>();
 
         while (it.hasNext()) {
             list.add(it.next());
         }
 
         return list;
     }
 
     // ----------------------------------------------------------------------
     //
     // ----------------------------------------------------------------------
 
     private static <E> int getFreq(final E obj, final Map<E, Integer> freqMap) {
         try {
             Integer o = freqMap.get(obj);
             if (o != null) // minimize NullPointerExceptions
             {
                 return o;
             }
         } catch (NullPointerException | NoSuchElementException ignore) {
         }
         return 0;
     }
 }