package com.hfg.util.collection;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.hfg.util.CompareUtil;
import com.hfg.util.StringUtil;


//------------------------------------------------------------------------------
/**
 Base matrix class.
 <div>
  @author J. Alex Taylor, hairyfatguy.com
 </div>
 */
//------------------------------------------------------------------------------
// 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 abstract class AbstractSparseMatrix<RK extends Comparable, CK extends Comparable, V extends Comparable> implements Cloneable
{

   private LinkedHashSet<RK> mOrderedRowKeySet;
   private LinkedHashSet<CK> mOrderedColKeySet;
   private Map<RK, Map<CK, V>> mMatrixMap;

   private int     mInitialColCapacity;

   private static int sDefaultInitialCapacity = 99;

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


   //--------------------------------------------------------------------------
   public AbstractSparseMatrix()
   {
      this(sDefaultInitialCapacity, sDefaultInitialCapacity);
   }

   //--------------------------------------------------------------------------
   public AbstractSparseMatrix(int inInitialRowCapacity, int inInitialColCapacity)
   {
      mOrderedRowKeySet = new LinkedHashSet<>(inInitialRowCapacity);
      mOrderedColKeySet = new LinkedHashSet<>(inInitialColCapacity);
      mMatrixMap        = new HashMap<>(inInitialRowCapacity);
      mInitialColCapacity = inInitialColCapacity;
   }

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


   //--------------------------------------------------------------------------
   public void addRow(RK inRowKey)
   {
      mOrderedRowKeySet.add(inRowKey);
   }

   //--------------------------------------------------------------------------
   public void addCol(CK inColKey)
   {
      mOrderedColKeySet.add(inColKey);
   }

   //--------------------------------------------------------------------------
   public void put(RK inRowKey, CK inColKey, V inValue)
   {
      mOrderedRowKeySet.add(inRowKey);
      mOrderedColKeySet.add(inColKey);

      Map<CK, V> colMap = mMatrixMap.get(inRowKey);
      if (null == colMap)
      {
         colMap = new HashMap<>(mInitialColCapacity);
         mMatrixMap.put(inRowKey, colMap);
      }
      colMap.put(inColKey, inValue);
   }

   //--------------------------------------------------------------------------
   public void putRow(RK inRowKey, Map<CK, V> inColMap)
   {
      if (CollectionUtil.hasValues(inColMap))
      {
         for (CK colKey : inColMap.keySet())
         {
            put(inRowKey, colKey, inColMap.get(colKey));
         }
      }
   }

   //--------------------------------------------------------------------------
   public void putCol(CK inColKey, Map<RK, V> inRowMap)
   {
      if (CollectionUtil.hasValues(inRowMap))
      {
         for (RK rowKey : inRowMap.keySet())
         {
            put(rowKey, inColKey, inRowMap.get(rowKey));
         }
      }
   }

   //--------------------------------------------------------------------------
   public V get(RK inRowKey, CK inColKey)
   {
      V value = null;

      Map<CK, V> colMap = mMatrixMap.get(inRowKey);
      if (colMap != null)
      {
         value = colMap.get(inColKey);
      }

      return value;
   }

   //--------------------------------------------------------------------------
   public V remove(RK inRowKey, CK inColKey)
   {
      V removedValue = null;

      Map<CK, V> colMap = mMatrixMap.get(inRowKey);
      if (colMap != null)
      {
         removedValue = colMap.remove(inColKey);
      }

      return removedValue;
   }

   //--------------------------------------------------------------------------
   public void clearRow(RK inRowKey)
   {
      if (containsRow(inRowKey))
      {
         for (CK colKey : colKeySet())
         {
            remove(inRowKey, colKey);
         }
      }
   }

   //--------------------------------------------------------------------------
   public void clearCol(CK inColKey)
   {
      if (containsCol(inColKey))
      {
         for (RK rowKey : rowKeySet())
         {
            remove(rowKey, inColKey);
         }
      }
   }

   //--------------------------------------------------------------------------
   public void trimToSize()
   {
      LinkedHashSet orderedColKeySet = new LinkedHashSet<>(mOrderedColKeySet.size(), 1.0f);
      orderedColKeySet.addAll(mOrderedColKeySet);
      mOrderedColKeySet = orderedColKeySet;

      LinkedHashSet orderedRowKeySet = new LinkedHashSet<>(mOrderedRowKeySet.size(), 1.0f);
      orderedRowKeySet.addAll(mOrderedRowKeySet);
      mOrderedRowKeySet = orderedRowKeySet;

      // Not sure how this transfer can be done more efficiently
      Map<RK, Map<CK, V>> compactedMap = new HashMap<>(mMatrixMap.size(), 1.0f);
      compactedMap.putAll(mMatrixMap);
      mMatrixMap = compactedMap;

      for (RK rowKey : mMatrixMap.keySet())
      {
         Map<CK, V> uncompactedValueMap = mMatrixMap.get(rowKey);
         if (uncompactedValueMap != null)
         {
            Map<CK, V> compactedValueMap = new HashMap<>(uncompactedValueMap.size(), 1.0f);
            compactedValueMap.putAll(uncompactedValueMap);
            mMatrixMap.put(rowKey, compactedValueMap);
         }
      }
   }

   //--------------------------------------------------------------------------
   @Override
   public AbstractSparseMatrix<RK, CK, V> clone()
   {
      AbstractSparseMatrix<RK, CK, V> clone;
      try
      {
         clone = (AbstractSparseMatrix<RK, CK, V>) super.clone();
      }
      catch (CloneNotSupportedException e)
      {
         throw new RuntimeException(e);
      }

      clone.mOrderedRowKeySet = new LinkedHashSet<>(mOrderedRowKeySet);
      clone.mOrderedColKeySet = new LinkedHashSet<>(mOrderedColKeySet);

      clone.mMatrixMap = new HashMap<>(mMatrixMap.size());
      for (RK rowKey : mMatrixMap.keySet())
      {
         Map<CK, V> colMap = mMatrixMap.get(rowKey);
         if (colMap != null)
         {
            Map<CK, V> clonedColMap = new HashMap<>(colMap.size());
            for (CK colKey : colMap.keySet())
            {
               clonedColMap.put(colKey, colMap.get(colKey));
            }

            clone.mMatrixMap.put(rowKey, clonedColMap);
         }
         else
         {
            clone.mMatrixMap.put(rowKey, null);
         }

      }

      return clone;
   }

   //--------------------------------------------------------------------------
   public int size()
   {
      int size = 0;
      for (Map<CK, V> colMap : mMatrixMap.values())
      {
         if (colMap != null)
         {
            size += colMap.size();
         }
      }

      return size;
   }

   //--------------------------------------------------------------------------
   public MatrixCell<RK, CK, V> getCellWithSmallestValue()
   {
      return getCellWithSmallestValue(true);
   }

   //--------------------------------------------------------------------------
   public MatrixCell<RK, CK, V> getNonIdentityCellWithSmallestValue()
   {
      return getCellWithSmallestValue(false);
   }

   //--------------------------------------------------------------------------
   @Override
   public String toString()
   {
      String outString;
      try
      {
         ByteArrayOutputStream outStream = new ByteArrayOutputStream();
         toString(outStream);
         outStream.close();
         outString = outStream.toString();
      }
      catch (IOException e)
      {
         throw new RuntimeException(e);
      }

      return outString;
   }

   //--------------------------------------------------------------------------
   public void toString(OutputStream inStream)
      throws IOException
   {
      Writer writer = new PrintWriter(inStream);

      int maxRowKeyLength = getMaxRowKeyLength();

      // Build a map of columm string lengths
      Map<CK, Integer> maxColValueLengthMap = new HashMap<>(colKeySet().size());
      for (CK colKey : colKeySet())
      {
         Integer maxColValueLength = null;
         for (RK rowKey : rowKeySet())
         {
            V value = get(rowKey, colKey);
            if (value != null)
            {
               String stringValue = getValueString(value);
               if (null == maxColValueLength
                     || stringValue.length() > maxColValueLength)
               {
                   maxColValueLength = stringValue.length();
               }
            }
         }

         maxColValueLengthMap.put(colKey, maxColValueLength);
      }

      // Header line
      writer.write(StringUtil.polyChar(' ', maxRowKeyLength) + "  ");
      for (CK colKey : colKeySet())
      {
         int colKeyLength = colKey.toString().length();
         Integer maxColValueLength = maxColValueLengthMap.get(colKey);
         if (null == maxColValueLength
             || colKeyLength > maxColValueLength)
         {
            maxColValueLength = colKeyLength;
         }

         writer.write(String.format("%" + maxColValueLength + "." + maxColValueLength + "s  ", colKey.toString()));
      }
      writer.write("\n");


      for (RK rowKey : rowKeySet())
      {
         writer.write(String.format("%" + maxRowKeyLength + "." + maxRowKeyLength + "s  ", rowKey.toString()));

         for (CK colKey : colKeySet())
         {
            int colKeyLength = colKey.toString().length();
            Integer maxColValueLength = maxColValueLengthMap.get(colKey);
            if (null == maxColValueLength
                  || colKeyLength > maxColValueLength)
            {
               maxColValueLength = colKeyLength;
            }

            V value = get(rowKey, colKey);
            if (value != null)
            {
               String stringValue = getValueString(value);

               writer.write(String.format("%" + maxColValueLength + "." + maxColValueLength + "s  ", stringValue));
            }
            else
            {
               writer.write(StringUtil.polyChar(' ', maxColValueLength) + "  ");
            }

         }
         writer.write("\n");
      }

      writer.flush();
   }

   //--------------------------------------------------------------------------
   private String getValueString(V inValue)
   {
      String stringValue;
      if (inValue instanceof Double
          || inValue instanceof Float)
      {
         stringValue = String.format("%.2f", inValue);
      }
      else
      {
         stringValue = inValue.toString();
      }

      return stringValue;
   }

   //##########################################################################
   // PROTECTED METHODS
   //##########################################################################

   //--------------------------------------------------------------------------
   protected Set<RK> rowKeySet()
   {
      return Collections.unmodifiableSet(mOrderedRowKeySet);
   }

   //--------------------------------------------------------------------------
   protected boolean containsRow(RK inRowKey)
   {
      return mOrderedRowKeySet.contains(inRowKey);
   }

   //--------------------------------------------------------------------------
   protected Map<CK, V> removeRow(RK inRowKey)
   {
      mOrderedRowKeySet.remove(inRowKey);
      return mMatrixMap.remove(inRowKey);
   }

   //--------------------------------------------------------------------------
   /**
    Changes the rowkey inOldKey to inNewKey.
    */
   protected void changeRowKey(RK inOldKey, RK inNewKey)
   {
      if (mOrderedRowKeySet != null)
      {
         List<RK> rowKeyList = new ArrayList<>(mOrderedRowKeySet);
         int index = rowKeyList.indexOf(inOldKey);
         if (index >= 0)
         {
            rowKeyList.remove(inOldKey);
            rowKeyList.add(index, inNewKey);
            mOrderedRowKeySet = new LinkedHashSet<>(rowKeyList);

            mMatrixMap.put(inNewKey, mMatrixMap.remove(inOldKey));
         }
      }
   }

   //--------------------------------------------------------------------------
   protected Set<CK> colKeySet()
   {
      return Collections.unmodifiableSet(mOrderedColKeySet);
   }

   //--------------------------------------------------------------------------
   protected Map<CK, V> getRow(RK inRowKey)
   {
      Map<CK, V> colMap = mMatrixMap.get(inRowKey);
      return (colMap != null ? Collections.unmodifiableMap(colMap) :  null);
   }

   //--------------------------------------------------------------------------
   protected Map<RK, V> getCol(CK inColKey)
   {
      Map<RK, V> rowMap = new OrderedMap<>(rowKeySet().size());
      for (RK rowKey : rowKeySet())
      {
         rowMap.put(rowKey, mMatrixMap.get(rowKey).get(inColKey));
      }

      return rowMap;
   }

   //--------------------------------------------------------------------------
   protected boolean containsCol(CK inColKey)
   {
      return mOrderedColKeySet.contains(inColKey);
   }

   //--------------------------------------------------------------------------
   protected void removeCol(CK inColKey)
   {
      if (mOrderedColKeySet.remove(inColKey))
      {
         for (Map<CK, V> colMap : mMatrixMap.values())
         {
            colMap.remove(inColKey);
         }
      }
   }

   //--------------------------------------------------------------------------
   protected void removeCols(Set<CK> inColKeys)
   {
      if (inColKeys != null
          && mOrderedColKeySet.removeAll(inColKeys))
      {
         for (Map<CK, V> colMap : mMatrixMap.values())
         {
            for (CK colKey : inColKeys)
            {
               colMap.remove(colKey);
            }
         }
      }
   }

   //--------------------------------------------------------------------------
   /**
    Changes the colkey inOldKey to inNewKey.
    */
   protected void changeColKey(CK inOldKey, CK inNewKey)
   {
      if (mOrderedColKeySet != null)
      {
         List<CK> colKeyList = new ArrayList<>(mOrderedColKeySet);
         int index = colKeyList.indexOf(inOldKey);
         if (index >= 0)
         {
            colKeyList.remove(inOldKey);
            colKeyList.add(index, inNewKey);
            mOrderedColKeySet = new LinkedHashSet<>(colKeyList);

            for (RK rowKey : mMatrixMap.keySet())
            {
               Map<CK, V> colMap = mMatrixMap.get(rowKey);
               if (colMap != null)
               {
                  if (colMap.containsKey(inOldKey))
                  {
                     colMap.put(inNewKey, colMap.remove(inOldKey));
                  }
               }
            }
         }
      }
   }


   //--------------------------------------------------------------------------
   private int getMaxRowKeyLength()
   {
      int maxLength = 0;
      if (CollectionUtil.hasValues(mOrderedRowKeySet))
      {
         for (RK key : mOrderedRowKeySet)
         {
            if (key != null)
            {
               int keyLength = key.toString().length();
               if (keyLength > maxLength)
               {
                  maxLength = keyLength;
               }
            }
         }
      }

      return maxLength;
   }

   //--------------------------------------------------------------------------
   private int getMaxColKeyLength()
   {
      int maxLength = 0;
      if (CollectionUtil.hasValues(mOrderedColKeySet))
      {
         for (CK key : mOrderedColKeySet)
         {
            if (key != null)
            {
               int keyLength = key.toString().length();
               if (keyLength > maxLength)
               {
                  maxLength = keyLength;
               }
            }
         }
      }

      return maxLength;
   }

   //--------------------------------------------------------------------------
   private MatrixCell<RK, CK, V> getCellWithSmallestValue(boolean inIncludeIdentityCells)
   {
     V smallestValue = null;
      RK targetRow = null;
      CK targetCol = null;

      for (RK rowKey : mMatrixMap.keySet())
      {
         Map<CK, V> colMap = mMatrixMap.get(rowKey);
         if (colMap != null)
         {
            for (CK colKey : colMap.keySet())
            {
               if (inIncludeIdentityCells
                   || ! rowKey.equals(colKey))
               {
                  V value = colMap.get(colKey);
                  if (value != null)
                  {
                     int comparison = 0;
                     if (null == smallestValue)
                     {
                        comparison = 1;
                     }
                     else
                     {
                        comparison = CompareUtil.compare(smallestValue, value);

                        if (0 == comparison)
                        {
                           comparison = CompareUtil.compare(targetCol.toString(), colKey.toString());
                        }

                        if (0 == comparison)
                        {
                           comparison = CompareUtil.compare(targetRow.toString(), rowKey.toString());
                        }
                     }

                     if (1 == comparison)
                     {
                        smallestValue = value;
                        targetRow = rowKey;
                        targetCol = colKey;
                     }
                  }
               }
            }
         }
      }
//      System.out.println(smallestValue + " ( " + targetRow + " " + targetCol);

      return smallestValue != null ? new MatrixCell<>(targetRow, targetCol, smallestValue) : null;
   }

}