package com.hfg.util.collection;


import java.io.IOException;
import java.io.Writer;
import java.util.*;

import com.hfg.exception.ProgrammingException;

//------------------------------------------------------------------------------
/**
 A symmetric matrix (a square matrix with values that are symmetric with respect to the diagonal).
 <div>
 Ex:<pre>
  1   5  -3
  5   2   9
 -3   9   8
 </pre>
 </div>
 <div>
 See <a href='http://en.wikipedia.org/wiki/Symmetric_matrix'>http://en.wikipedia.org/wiki/Symmetric_matrix</a>
 </div>
 * @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 SymmetricMatrix<K extends Comparable, V extends Comparable> implements Cloneable
{
   protected List<MatrixRow> mMatrix;

   private HashMap<K, MatrixRow> mKeyMap;

   // Cached values
   private Integer mSize;
   private SortedList<MatrixCell<K, K, V>> mSmallestValues;
   private boolean mSmallestValuesIncludeIdentity;

   private static int sDefaultInitialCapacity = 99;
   private static int sSmallestValuesCapacity = 1000;
   private static int sSmallestValuesRetentionSize = 750;


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

   //--------------------------------------------------------------------------
   public SymmetricMatrix()
   {
      this(sDefaultInitialCapacity);
   }

   //--------------------------------------------------------------------------
   public SymmetricMatrix(int inInitialCapacity)
   {
      mKeyMap = new HashMap<>(inInitialCapacity);
      mMatrix = new ArrayList<>(inInitialCapacity);
   }

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

   //--------------------------------------------------------------------------
   public void put(K inKey1, K inKey2, V inValue)
   {
      MatrixRow matrixRow1 = mKeyMap.get(inKey1);
      if (null == matrixRow1)
      {
         matrixRow1 = innerAddKey(inKey1);
      }

      MatrixRow matrixRow2 = mKeyMap.get(inKey2);
      if (null == matrixRow2)
      {
         matrixRow2 = innerAddKey(inKey2);
      }


      MatrixRow rowWithCell = (matrixRow1.getIndex() < matrixRow2.getIndex() ? matrixRow2 : matrixRow1);
      rowWithCell.getData().set((matrixRow1 == rowWithCell ? matrixRow2 : matrixRow1).getIndex(), inValue);

      // If there is a smallest value cache, see if the new value should be added
      if (mSmallestValues != null
          && inValue.compareTo(mSmallestValues.last().getValue()) <= 0
          && (mSmallestValuesIncludeIdentity || inKey1 != inKey2))
      {
         mSmallestValues.add(new MatrixCell<>(inKey1, inKey2, inValue));
         if (mSmallestValues.size() > sSmallestValuesCapacity - 2)
         {
            // Truncate the list
            mSmallestValues.truncate(sSmallestValuesRetentionSize);
         }
      }
   }

   //--------------------------------------------------------------------------
   public V get(K inKey1, K inKey2)
   {
      MatrixRow matrixRow1 = mKeyMap.get(inKey1);
      if (null == matrixRow1)
      {
         throw new RuntimeException("'" + inKey1 + "' is not a valid matrix key!");
      }

      MatrixRow matrixRow2 = mKeyMap.get(inKey2);
      if (null == matrixRow2)
      {
         throw new RuntimeException("'" + inKey2 + "' is not a valid matrix key!");
      }

      MatrixRow rowWithCell = (matrixRow1.getIndex() < matrixRow2.getIndex() ? matrixRow2 : matrixRow1);
      V value = rowWithCell.getData().get((matrixRow1 == rowWithCell ? matrixRow2 : matrixRow1).getIndex());

      return value;
   }

   //--------------------------------------------------------------------------
   // TODO:
   public void toString(Writer inWriter)
         throws IOException
   {
      int maxKeyLength = getMaxKeyLength();
      String keyFormat = "%-" + maxKeyLength + "." + maxKeyLength + "s";

      Set<K> orderedKeys = orderedKeySet();
      for (K key1 : orderedKeys)
      {
         inWriter.append(String.format(keyFormat, key1));
         for (K key2 : orderedKeys)
         {
            inWriter.append(String.format("  %.4f", get(key1, key2)));

            if (key1 == key2)
            {
               break;
            }
         }

         inWriter.append(System.getProperty("line.separator"));
      }
   }

   //--------------------------------------------------------------------------
   /**
    * Returns the keys in no guaranteed order.
    * @return a Set containing the matrix keys
    */
   public Set<K> keySet()
   {
      return mKeyMap.keySet();
   }

   //--------------------------------------------------------------------------
   /**
    * Returns the keys in addition order.
    * @return a Set containing the matrix keys in the order of addition
    */
   public Set<K> orderedKeySet()
   {
      OrderedSet<K> keySet = null;

      if (CollectionUtil.hasValues(mMatrix))
      {
         keySet = new OrderedSet<>(mMatrix.size());
         for (MatrixRow matrixRow : mMatrix)
         {
            keySet.add(matrixRow.getKey());
         }
      }

      return keySet;
   }

   //--------------------------------------------------------------------------
   public int numKeys()
   {
      return (mKeyMap != null ? mKeyMap.size() : 0);
   }

   //--------------------------------------------------------------------------
   public boolean addKey(K inKey)
   {
      boolean added = false;
      if (! mKeyMap.containsKey(inKey))
      {
         innerAddKey(inKey);

         added = true;
      }

      return added;
   }

   //--------------------------------------------------------------------------
   public boolean containsKey(K inKey)
   {
      return mKeyMap.containsKey(inKey);
   }

   //--------------------------------------------------------------------------
   // TODO: Should this return Map<K, V> ?
   public void removeKey(K inKey)
   {
      MatrixRow matrixRow = mKeyMap.get(inKey);
      if (matrixRow != null)
      {
         int removedIndex = matrixRow.getIndex();

         mKeyMap.remove(inKey);
         mMatrix.remove(removedIndex);
         for (int i = removedIndex; i < mMatrix.size(); i++)
         {
            MatrixRow matrixRowToAdjust = mMatrix.get(i);
            matrixRowToAdjust.decrementIndex();
            matrixRowToAdjust.getData().remove(removedIndex);
         }

         // If any of the cached smallest values are associated with the removed key, remove them
         if (mSmallestValues != null)
         {
            for (int i = 0; i < mSmallestValues.size(); i++)
            {
               MatrixCell<K, K, V> matrixCell = mSmallestValues.get(i);
               if (matrixCell.getRowKey().equals(inKey)
                   || matrixCell.getColKey().equals(inKey))
               {
                  mSmallestValues.remove(i--);
               }
            }
         }

         // Clear the cached matrix size
         mSize = null;
      }
   }

   //--------------------------------------------------------------------------
   public void removeKeys(Collection<K> inKeys)
   {
      if (CollectionUtil.hasValues(inKeys))
      {
         for (K key : inKeys)
         {
            removeKey(key);
         }
      }
   }

   //--------------------------------------------------------------------------
   public void changeKey(K inOldKey, K inNewKey)
   {
      MatrixRow matrixRow = mKeyMap.get(inOldKey);
      if (matrixRow != null)
      {
         matrixRow.setKey(inNewKey);
         mKeyMap.remove(inOldKey);
         mKeyMap.put(inNewKey, matrixRow);

         // If any of the cached smallest values are associated with the changed key, change them
         if (mSmallestValues != null)
         {
            for (int i = 0; i < mSmallestValues.size(); i++)
            {
               MatrixCell<K, K, V> matrixCell = mSmallestValues.get(i);
               if (matrixCell.getRowKey().equals(inOldKey))
               {
                  matrixCell.setRowKey(inNewKey);
               }
               else if (matrixCell.getColKey().equals(inOldKey))
               {
                  matrixCell.setColKey(inNewKey);
               }
            }
         }
      }
   }

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

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

   //--------------------------------------------------------------------------
   @Override
   public SymmetricMatrix<K, V> clone()
   {
      SymmetricMatrix<K, V> clone;
      try
      {
         clone = (SymmetricMatrix<K, V>) super.clone();
      }
      catch (CloneNotSupportedException e)
      {
         throw new ProgrammingException(e);
      }

      clone.mKeyMap = new HashMap<>(mKeyMap.size());
      clone.mMatrix = new ArrayList<>(mMatrix.size());
      for (MatrixRow matrixRow : mMatrix)
      {
         // The map values and the array values are the same
         // objects and we need to keep it that way
         matrixRow = matrixRow.clone();
         clone.mMatrix.add(matrixRow);
         clone.mKeyMap.put(matrixRow.getKey(), matrixRow);
      }

      return clone;
   }

   //--------------------------------------------------------------------------
   public int size()
   {
      if (null == mSize)
      {
         int size = 0;
         if (CollectionUtil.hasValues(mKeyMap))
         {
            int numKeys = numKeys();
            size = ((numKeys * numKeys - numKeys) / 2) + numKeys;
         }

         mSize = size;
      }

      return mSize;
   }

   //--------------------------------------------------------------------------
   protected int getIndexForKey(K inKey)
   {
      MatrixRow matrixRow = mKeyMap.get(inKey);
      return (matrixRow != null ? matrixRow.getIndex() : -1);
   }

   //##########################################################################
   // PRIVATE METHODS
   //##########################################################################

   //--------------------------------------------------------------------------
   private MatrixRow innerAddKey(K inKey)
   {
      // Create and initialize a matrix row
      MatrixRow matrixRow = new MatrixRow(inKey, mMatrix.size());
      mKeyMap.put(inKey, matrixRow);
      mMatrix.add(matrixRow);

      // Clear the cached size
      mSize = null;

      return matrixRow;
   }

   //--------------------------------------------------------------------------
   private int getMaxKeyLength()
   {
      int maxLength = 0;
      for (K key : mKeyMap.keySet())
      {
         if (key.toString().length() > maxLength)
         {
            maxLength = key.toString().length();
         }
      }

      return maxLength;
   }

   //--------------------------------------------------------------------------
   private MatrixCell<K, K, V> getCellWithSmallestValue(boolean inIncludeIdentityCells)
   {
      if (null == mSmallestValues
          || mSmallestValuesIncludeIdentity !=  inIncludeIdentityCells)
      {
         mSmallestValues = new SortedList<>(sSmallestValuesCapacity);
         mSmallestValuesIncludeIdentity = inIncludeIdentityCells;
      }

      if (0 == mSmallestValues.size())
      {
         for (MatrixRow matrixRow : mMatrix)
         {
            int numCells = matrixRow.getData().size();
            for (int colIndex = 0; colIndex < numCells; colIndex++)
            {
               if (inIncludeIdentityCells
                   || matrixRow.getIndex() != colIndex)
               {
                  V value = matrixRow.getData().get(colIndex);
                  if (value != null)
                  {
                     if (mSmallestValues.size() < sSmallestValuesRetentionSize
                         || value.compareTo(mSmallestValues.last().getValue()) <= 0)
                     {
                        K targetCol = mMatrix.get(colIndex).getKey();

                        mSmallestValues.add(new MatrixCell<>(matrixRow.getKey(), targetCol, value));

                        if (mSmallestValues.size() > sSmallestValuesCapacity - 2)
                        {
                           // Truncate the list
                           mSmallestValues.truncate(sSmallestValuesRetentionSize);
                        }
                     }
                  }
               }
            }
         }
      }

//      System.out.println(mSmallestValues.get(0).getValue() + " ( " + mSmallestValues.get(0).getRowKey() + " " + mSmallestValues.get(0).getColKey());
      return (CollectionUtil.hasValues(mSmallestValues) ? mSmallestValues.get(0) : null);
   }


   protected class MatrixRow implements Cloneable
   {
      private int mRowIndex;
      private K mKey;
      private List<V> mData;

      //-----------------------------------------------------------------------
      public MatrixRow(K inKey, int inIndex)
      {
         mKey = inKey;
         mRowIndex = inIndex;

         initializeData();
      }

      //-----------------------------------------------------------------------
      public void setKey(K inKey)
      {
         mKey = inKey;
      }

      //-----------------------------------------------------------------------
      public K getKey()
      {
         return mKey;
      }

      //-----------------------------------------------------------------------
      public void decrementIndex()
      {
         mRowIndex--;
      }

      //-----------------------------------------------------------------------
      public int getIndex()
      {
         return mRowIndex;
      }

      //-----------------------------------------------------------------------
      public void setData(List<V> inData)
      {
         mData = inData;
      }

      //-----------------------------------------------------------------------
      public List<V> getData()
      {
         return mData;
      }

      //-----------------------------------------------------------------------
      private void initializeData()
      {
         mData = new ArrayList<>(mRowIndex + 1);
         for (int i = 0; i < mRowIndex + 1; i++)
         {
            mData.add(null);
         }
      }

      //--------------------------------------------------------------------------
      @Override
      public MatrixRow clone()
      {
         MatrixRow clone;
         try
         {
            clone = (MatrixRow) super.clone();
         }
         catch (CloneNotSupportedException e)
         {
            throw new ProgrammingException(e);
         }

         clone.mData = new ArrayList<>(mData);

         return clone;
      }

   }

}