package com.hfg.math;

import com.hfg.util.collection.CollectionUtil;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

//------------------------------------------------------------------------------
/**
 * Iterator that steps through the possible combinations of a List of Lists.
 * @author J. Alex Taylor, hairyfatguy.com
 */
//------------------------------------------------------------------------------
// com.hfg Library
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// J. Alex Taylor, President, Founder, CEO, COO, CFO, OOPS hairyfatguy.com
// jataylor@hairyfatguy.com
//------------------------------------------------------------------------------

public class ListCombinationIterator<T>
{
   private List<List<T>>       mListOfLists;
   private Range<Integer>      mCombinationSizeRange;
   private Integer             mCurrentCombinationSize;
   private List<List<Integer>> mCurrentPositionIndexCombinations;
   private int                 mCurrentPositionIndexCombinationsIndex;
   private List<Integer>       mCurrentPositionIndices;
   private int[]               mCurrentIndices;
   private int                 mSize;

   //###########################################################################
   // CONSTRUCTORS
   //###########################################################################

   //---------------------------------------------------------------------------
   public ListCombinationIterator(List<? extends Collection<T>> inListOfLists)
   {
     this(inListOfLists, inListOfLists != null ? new Range<>(inListOfLists.size(), inListOfLists.size()) : null);
   }

   //---------------------------------------------------------------------------
   public ListCombinationIterator(List<? extends Collection<T>> inListOfLists, Range<Integer> inCombinationSizeRange)
   {
      if (inListOfLists.get(0) instanceof List)
      {
         mListOfLists = (List<List<T>>) inListOfLists;
      }
      else
      {
         mListOfLists = new ArrayList<>(inListOfLists.size());
         for (Collection<T> collection : inListOfLists)
         {
            mListOfLists.add(new ArrayList<>(collection));
         }
      }
      mCombinationSizeRange = inCombinationSizeRange;

      // Set the size - the total number of combinations
      if (CollectionUtil.hasValues(mListOfLists))
      {
         mSize = 0;

         Integer minSize = (inCombinationSizeRange != null && inCombinationSizeRange.getStart() != null ? inCombinationSizeRange.getStart() : 1);
         Integer maxSize = (inCombinationSizeRange != null && inCombinationSizeRange.getEnd() != null ? inCombinationSizeRange.getEnd() : mListOfLists.size());
         if (maxSize > mListOfLists.size())
         {
            maxSize = mListOfLists.size();
         }

         mCombinationSizeRange = new Range<>();
         mCombinationSizeRange.setStart(minSize).setEnd(maxSize);

         for (int combinationSize = minSize; combinationSize <= maxSize; combinationSize++)
         {
            List<Integer> indexList = new ArrayList<>(inListOfLists.size());
            for (int i = 0; i < inListOfLists.size(); i++)
            {
               indexList.add(i);
            }

            List<List<Integer>> indexCombinations = Combinations.combinations(indexList, combinationSize);

            for (List<Integer> indices : indexCombinations)
            {
               int size = 1;
               for (int index : indices)
               {
                  size *= inListOfLists.get(index).size();
               }

               mSize += size;
            }
         }
      }
   }

   //###########################################################################
   // PUBLIC METHODS
   //###########################################################################

   //---------------------------------------------------------------------------
   private List<List<Integer>> getPositionIndexCombinations()
   {
      List<Integer> indexList = new ArrayList<>(mListOfLists.size());
      for (int i = 0; i < mListOfLists.size(); i++)
      {
         indexList.add(i);
      }

      return Combinations.combinations(indexList, mCurrentCombinationSize);
   }

   //---------------------------------------------------------------------------
   public boolean hasNext()
   {
      boolean hasNext = false;
      if (CollectionUtil.hasValues(mListOfLists))
      {
         if (null == mCurrentCombinationSize)
         {
            mCurrentCombinationSize = mCombinationSizeRange.getStart();
            hasNext = true;
         }
         else
         {
            while (! hasNext
                   && mCurrentCombinationSize <= mCombinationSizeRange.getEnd()
                   && mCurrentPositionIndexCombinationsIndex < mCurrentPositionIndexCombinations.size())
            {
               if (null == mCurrentPositionIndexCombinations
                     || mCurrentPositionIndexCombinationsIndex < mCurrentPositionIndexCombinations.size() - 1
                     || null == mCurrentIndices)
               {
                  hasNext = true;
               }
               else
               {
                  for (int i = 0; i < mCurrentIndices.length; i++)
                  {
                     if (mCurrentIndices[i] < mListOfLists.get(mCurrentPositionIndices.get(i)).size() - 1)
                     {
                        hasNext = true;
                        break;
                     }
                  }

                  if (! hasNext)
                  {
                     // We've hit the end of combinations for this combination size.
                     mCurrentCombinationSize++;
                     if (mCurrentCombinationSize <= mCombinationSizeRange.getEnd())
                     {
                        mCurrentPositionIndexCombinations = getPositionIndexCombinations();
                        mCurrentPositionIndexCombinationsIndex = 0;
                        mCurrentPositionIndices = mCurrentPositionIndexCombinations.get(mCurrentPositionIndexCombinationsIndex);
                        mCurrentIndices = null;
                     }
                  }
               }
            }
         }
      }

      return hasNext;
   }

   //---------------------------------------------------------------------------
   public List<T> next()
   {
      List<T> combination = null;

      if (null == mCurrentCombinationSize
            || mCurrentCombinationSize <= mCombinationSizeRange.getEnd())
      {
         boolean combinationFound = false;


         if (null == mCurrentCombinationSize)
         {
            mCurrentCombinationSize = mCombinationSizeRange.getStart();
         }

         if (null == mCurrentPositionIndexCombinations)
         {
            mCurrentPositionIndexCombinations = getPositionIndexCombinations();
            mCurrentPositionIndexCombinationsIndex = 0;
            mCurrentPositionIndices = mCurrentPositionIndexCombinations.get(mCurrentPositionIndexCombinationsIndex);
         }

         if (null == mCurrentIndices)
         {
            mCurrentIndices = new int[mCurrentCombinationSize];
            for (int i = 0; i < mCurrentCombinationSize; i++)
            {
               mCurrentIndices[i] = 0;
            }

            combinationFound = true;
         }
         else
         {
            // Iterate the indices
            int i;

            while (! combinationFound
                   && mCurrentCombinationSize <= mCombinationSizeRange.getEnd()
                   && mCurrentPositionIndexCombinationsIndex < mCurrentPositionIndexCombinations.size())
            {
               for (i = 0; i < mCurrentCombinationSize; i++)
               {
                  if (mCurrentIndices[i] < mListOfLists.get(mCurrentPositionIndices.get(i)).size() - 1)
                  {
                     mCurrentIndices[i]++;
                     break;
                  }
                  else
                  {
                     mCurrentIndices[i] = 0;
                  }
               }

               // Have we run out of combinations for this set of positions?
               if (i < mCurrentCombinationSize)
               {
                  combinationFound = true;
               }
               else
               {
                  mCurrentPositionIndexCombinationsIndex++;
                  if (mCurrentPositionIndexCombinationsIndex >= mCurrentPositionIndexCombinations.size())
                  {
                     mCurrentCombinationSize++;
                     if (mCurrentCombinationSize <= mCombinationSizeRange.getEnd())
                     {
                        mCurrentPositionIndexCombinations = getPositionIndexCombinations();
                        mCurrentPositionIndexCombinationsIndex = 0;
                        mCurrentPositionIndices = mCurrentPositionIndexCombinations.get(mCurrentPositionIndexCombinationsIndex);
                        mCurrentIndices = new int[mCurrentCombinationSize];
                        for (int index = 0; index < mCurrentCombinationSize; index++)
                        {
                           mCurrentIndices[index] = 0;
                        }

                        combinationFound = true;
                     }
                  }
                  else
                  {
                     mCurrentPositionIndices = mCurrentPositionIndexCombinations.get(mCurrentPositionIndexCombinationsIndex);
                     for (int index = 0; index < mCurrentCombinationSize; index++)
                     {
                        mCurrentIndices[index] = 0;
                     }

                     combinationFound = true;
                  }
               }
            }
         }

         if (combinationFound)
         {
            combination = new ArrayList<>(mCurrentCombinationSize);

            for (int i = 0; i < mCurrentCombinationSize; i++)
            {
               combination.add(mListOfLists.get(mCurrentPositionIndices.get(i)).get(mCurrentIndices[i]));
            }
         }
      }

      return combination;
   }

   //---------------------------------------------------------------------------
   public int size()
   {
      return mSize;
   }

   //---------------------------------------------------------------------------
   public List<List<T>> getAll()
   {
      mCurrentCombinationSize = null;
      mCurrentPositionIndexCombinations = null;
      mCurrentPositionIndices = null;
      mCurrentIndices = null;

      List<List<T>> combinations = new ArrayList<>(mSize);
      while (hasNext())
      {
         combinations.add(next());
      }

      return combinations;
   }
}