package Combinatorics;

import java.util.Hashtable;
import java.util.Enumeration;
import java.io.PrintStream;
import java.io.IOException;

import Combinatorics.Permutation;

/**
 * This class defines the permutation groupo objects.
 *
 * The current implementation uses full enumeration but
 * the interface should be transparent to a later switch to
 * right coset representatives.
 */
public class PermGroup
{
   RepresentationMatrix M;    // right coset representative representation

   /**
    * Constructs a permutation group based on generator.
    * The result is a cyclic group. The group can later be extended
    * by adding more generators.
    */
   public PermGroup(Permutation generator)
   {
      M = new RepresentationMatrix(generator.n);
      M.addGenerator(generator);
   }

   /**
    * Add a generator to this permutation group.
    */
   public void addGenerator(Permutation generator)
   {
      M.addGenerator(generator);
   }

   /**
    * Print permutation group to a PrintStream.
    * toString() will be implemented once right cosets are available.
    */
   public void print(PrintStream ps)
   {
      M.print(ps);
   }

   /**
    * Test driver program.
    */
   public static void main(String []argv) throws IOException
   {
      Permutation p;
      PermGroup pg = null;

      if (argv.length >= 1)
      {
         for (int i=0; i<argv.length; i++)
         {
            System.out.println(argv[i]);
            System.out.println("");
            p = new Permutation(argv[i]);
            System.out.println(p);
            System.out.println("");
            if (pg == null)
               pg = new PermGroup(p);
            else
               pg.addGenerator(p);
            pg.print(System.out);
         }
      }
      else
         System.out.println("sample usage: java PermGroup '1 2 3'");
      System.in.read();
   }
}

/**
 * This private class implements representations of permutation groups
 * that are more succinct than mere enumeration of all elements.
 * It is polynomial time constructable from a set of generators <K>.
 * See C. M. Hoffmann, Lecture Notes in Computer Science, Vol. 136.
 * The time bound proven there is O(|K|*n^2+n^6) where n is the group
 * order and |K| is the size of the generating set.
 */
class RepresentationMatrix
{
   Permutation[][] M;   // matrix of right coset representatives
                        // row and column 0 are created but ignored!!

   int n;               // current order of representation. n can
                        // grow if permutations with order > n are sifted.

   /**
    * Creates the trivial nxn matrix of right coset reps. with
    * diagonal elements = () and all other elements == null.
    */
   RepresentationMatrix(int n)
   {
      this.n = n;

      M = new Permutation[n+1][];
      for (int i=1; i<=n; i++)
      {
         M[i] = new Permutation[n+1];
         M[i][i] = Permutation.identity;
      }
   }

   /**
    * Utility method to extend the size of the representation matrix M
    * as needed by new generators.
    */
   private void extendOrder(int n)
   {
      Permutation[][] tmpM;

      if (n <= this.n) return;

      tmpM = new Permutation[n+1][];
      for (int i=1; i<=this.n; i++)
      {
         tmpM[i] = new Permutation[n+1];
         for (int j=1; j<=this.n; j++) tmpM[i][j] = M[i][j];
      }

      for (int i=this.n+1; i<=n; i++)
      {
         tmpM[i] = new Permutation[n+1];
         tmpM[i][i] = Permutation.identity;
      }

      M = tmpM; this.n = n;
   }

   /**
    * Sift generator into the current representation matrix.
    * See C. M. Hoffmann, Lecture Notes in Computer Science, Vol. 136, p.38
    * Returns the new permutation added to the representation matrix
    * or null if the permutation is representable by the current matrix.
    */
   private Permutation sift(Permutation generator)
   {
      if (generator.equals(Permutation.identity)) return (null);

      if (generator.n > n)  extendOrder(generator.n);

      int i = 0;
      int j;

      while (i<n)
      {
         i++;
         j = generator.perm[i];
         if (M[i][j] != null)
            generator = generator.times(M[i][j].inverse());
         else
         {
            M[i][j] = generator;
            return (generator);
         }
      }

      return (null);
   }

   /**
    * Update representation matrix to include generator and restore
    * representation matrix properties.
    * See C. M. Hoffmann, Lecture Notes in Computer Science, Vol. 136, p.39
    */
   void addGenerator(Permutation generator)
   {
      Hashtable   pending = new Hashtable();
      //Hashtable   tmp_pending = new Hashtable();

      Enumeration enum;
      Permutation added, p;

      pending.put(generator.toCycleString(), generator);

      while (pending.size() > 0)
      {
         enum = pending.elements();
         while (enum.hasMoreElements())
         {
            int i, j;

            p = (Permutation)enum.nextElement();
            pending.remove(p.toCycleString());

            added = sift(p);
            if (added == null) continue;

            System.err.println("Sifted in  " + p.toCycleString());
            System.err.println("Added to M " + added.toCycleString());
            for (i=1; i<=n; i++)
               for (j=i+1; j<=n; j++)
                  if (M[i][j] != null)
                  {
                     p = added.times(M[i][j]);
                     if (!pending.containsKey(p.toCycleString()))
                     {
                        pending.put(p.toCycleString(), p);
                     }
                     p = M[i][j].times(added);
                     if (!pending.containsKey(p.toCycleString()))
                     {
                        pending.put(p.toCycleString(), p);
                     }
                  }
         }
      }
   }

   /**
    * Returns the vector L[] of elements of M that represent p
    * as p = L[n]*L[n-1]*...*L[2]*L[1].
    * If p is not representable in the group defined by M,
    * then null is returned.
    */
   Permutation[] represent(Permutation p)
   {
      Permutation[] result = new Permutation[n];

      if (p.n > n)  extendOrder(p.n);

      int i = 0;
      int j;

      while (i<n)
      {
         i++;
         j = p.perm[i];
         if (M[i][j] != null)
         {
            result[i] = M[i][j];
            p = p.times(M[i][j].inverse());
         }
         else
         {
            return (null);
         }
      }

      return (result);
   }

   /**
     * Print this representation matrix to ps.
     */
   void print(PrintStream ps)
   {
      int size=1;
      int k;

      for (int i=1; i<=n; i++)
      {
         k=0;
         for (int j=1; j<=n; j++)
         {
            if (j!=1) ps.print("\t");
            if (M[i][j] == null)
               ps.print("--");
            else
            {
               ps.print(M[i][j].toCycleString());
               k++;
            }
         }
         ps.println();
         size *= k;
      }
      ps.println(size + " elements");
   }

}