import java.awt.Frame;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Panel;
import java.lang.Math;
import java.text.NumberFormat;
import java.util.Random;

import xanthian_kpd.MersenneTwister;

public class MovieSchedule extends Object
{

  // tuning parameters; make into a valuator package someday
  private static int             POP_SIZE          = 200;
  private static int             NUM_MISSES        = 5000;
  private static int             TOURNEY_SIZE      = 10;
  private static double          MUTATION_RATE     = 0.05D;
  private static boolean         FITNESS_BARRIER   = false;
  private static boolean         FITNESS_SELECTION = true;

  private static NumberFormat    m_nf           = null;
  private static MersenneTwister m_mt           = null;
  private static Random          m_rand         = null;
  private static Schedule        m_population[] = null;
  private static Frame           m_frame        = null;
  private static String          m_windowTitle  = "2002/10/05 Movie Schedule";
  private static Panel           m_panel        = null;
  private static Movie           m_movies[]     = null;
  private static Schedule        m_bestSeen     = null;
  private static double          m_bestFitness  = Double.MAX_VALUE;
  private static int             m_highMisses   = 0;
  private static long            m_fitnessCalls = 0L;

  public static String names[] =
  {
    "VeggieTales Movie",
    "Moonlight Mile",
    "Sweet Home Alabama",
//    "The Tuxedo",
    "Barbershop",
    "One Hour Photo",
  };

  public static int rawSchedule[][][] =
  {
    { // "VeggieTales Movie",
      { 11, 30, 13, 45, },
      { 13, 45, 16, 00, },
      { 16, 00, 18, 15, },
      { 18, 15, 20, 30, },
      { 20, 20, 22, 20, },
      { 22, 20, 24, 35, },
    },
    { // "Moonlight Mile",
      { 12, 30, 15, 30, },
      { 15, 30, 18, 30, },
      { 18, 30, 21, 30, },
      { 21, 30, 24, 30, },
    },
    { // "Sweet Home Alabama",
      { 11, 30, 14, 00, },
      { 12, 00, 14, 30, },
      { 13, 00, 15, 30, },
      { 14, 00, 16, 30, },
      { 14, 30, 17, 00, },
      { 15, 30, 18, 00, },
      { 16, 30, 19, 00, },
      { 17, 00, 19, 30, },
      { 18, 00, 20, 30, },
      { 19, 00, 21, 30, },
      { 19, 30, 22, 00, },
      { 20, 30, 23, 00, },
      { 21, 30, 24, 00, },
      { 22, 00, 24, 30, },
    },
//    { // "The Tuxedo",
//      { 11, 40, 14, 10, },
//      { 12, 10, 14, 40, },
//      { 14, 10, 16, 40, },
//      { 14, 40, 17, 10, },
//      { 16, 40, 19, 10, },
//      { 17, 10, 19, 40, },
//      { 19, 10, 21, 40, },
//      { 19, 40, 22, 10, },
//      { 21, 40, 24, 10, },
//      { 22, 10, 24, 40, },
//    },
    { // "Barbershop",
      { 11, 30, 14, 00, },
      { 14, 00, 16, 30, },
      { 16, 30, 19, 00, },
      { 19, 00, 21, 30, },
      { 20, 15, 22, 45, },
      { 21, 30, 24, 00, },
      { 22, 30, 24, 00, },
    },
    { // "One Hour Photo",
      { 13, 00, 15, 15, },
      { 15, 15, 17, 30, },
      { 17, 30, 19, 45, },
      { 19, 45, 22, 00, },
      { 22, 00, 24, 15, },
    },
  };

  public MovieSchedule()
  {
    super();
  }

  static class MovieInstance extends Object
  {
    int m_start  = 0;
    int m_end    = 0;
    int m_span[] = null;

    public MovieInstance( int HHMMHHMM[] )
    {
      super();
      m_start = HHMMHHMM[0] * 60 + HHMMHHMM[1];
      m_end   = HHMMHHMM[2] * 60 + HHMMHHMM[3];
      int temp[]  = { HHMMHHMM[0], HHMMHHMM[1], HHMMHHMM[2], HHMMHHMM[3], };
      m_span = temp;
    }

    public int overlap( MovieInstance that )
    {

      // handle non-overlaps

      if ( ( this.m_end <= that.m_start ) ) { return 0; }

      if ( ( this.m_start >= that.m_end ) ) { return 0; }

      // handle containments

      if
      (
        ( that.m_start <= this.m_end )
        &&
        ( that.m_start >= this.m_start )
        &&
        ( that.m_end <= this.m_end )
        &&
        ( that.m_end >= this.m_start )
      )
      {
        return that.m_end - that.m_start;
      }

      if
      (
        ( this.m_start <= that.m_end )
        &&
        ( this.m_start >= that.m_start )
        &&
        ( this.m_end <= that.m_end )
        &&
        ( this.m_end >= that.m_start )
      )
      {
        return this.m_end - this.m_start;
      }

      // handle end overlaps

      if
      (
        ( that.m_start <= this.m_end )
        &&
        ( that.m_start >= this.m_start )
        &&
        ( that.m_end >= this.m_end )
        &&
        ( that.m_end >= this.m_start )
      )
      {
        return this.m_end - that.m_start;
      }

      if
      (
        ( this.m_start <= that.m_end )
        &&
        ( this.m_start >= that.m_start )
        &&
        ( this.m_end >= that.m_end )
        &&
        ( this.m_end >= that.m_start )
      )
      {
        return that.m_end - this.m_start;
      }

      return 0; // impossible case, just to keep javac quiet.
    }

    public String toString()
    {
      return
      (
        "("
        + m_span[0]
        + ":"
        + m_span[1]
        + "-"
        + m_span[2]
        + ":"
        + m_span[3]
        + ")"
      );
    }
  }

  static class Movie extends Object
  {
    String m_title = null;
    MovieInstance m_showings[] = null;

    public Movie( String title, MovieInstance showings[] )
    {
      super();
      m_title = title;
      m_showings = showings;
    }

    public int numShowings()
    {
      if ( m_showings == null )
      {
        return 0;
      }
      else
      {
        return m_showings.length;
      }
    }

    public MovieInstance getShowing( int which )
    {
      return m_showings[which];
    }

    public String getTitle() { return m_title; }

  }

  static class Schedule extends Object  // this is our genome
  {

    private int m_choices[] = null;
    private Movie m_ms[] = null;

    // initial constructor
    public Schedule( int choices[], Movie masterSchedule[] )
    {
      super();
      m_ms = masterSchedule;
      m_choices = new int[choices.length];
      for ( int i = 0; i < choices.length; i++ ) { m_choices[i] = choices[i]; }
    }

    // copy constructor
    public Schedule( Schedule that )
    {
      this.m_ms = that.m_ms;
      this.m_choices = new int[that.m_choices.length];
      for ( int i = 0; i < that.m_choices.length; i++ )
      {
        this.m_choices[i] = that.m_choices[i];
      }
    }

    // mutate constructor
    public Schedule( Schedule that, int mutateWhere )
    {
      this.m_ms = that.m_ms;
      this.m_choices = new int[that.m_choices.length];
      for ( int i = 0; i < that.m_choices.length; i++ )
      {
        this.m_choices[i] = that.m_choices[i];
      }
      this.m_choices[mutateWhere] =
        m_mt.nextInt( that.m_ms[mutateWhere].numShowings() );
    }

    // crossover constructor
    public Schedule( Schedule mom, Schedule pop, int xoverWhere )
    {
      this.m_ms = mom.m_ms;
      this.m_choices = new int[mom.m_choices.length];
      for ( int i = 0; i < xoverWhere; i++ )
      {
        this.m_choices[i] = mom.m_choices[i];
      }
      for ( int i = xoverWhere; i < m_choices.length; i++ )
      {
        this.m_choices[i] = pop.m_choices[i];
      }

    }

    public String toString()
    {
      StringBuffer b = new StringBuffer();
      b.append( "[" );
      b.append( m_choices[0] );
      for ( int i = 1; i < m_choices.length; i++ )
      {
        b.append( "," );
        b.append( m_choices[i] );
      }
      b.append( "]" );
      return b.toString();
    }

    public double fitness()  // least squares style
    {

      m_fitnessCalls++;

      double work = 0.0D;

      for ( int i = 1; i < m_ms.length; i++ )
      {
        for ( int j = 0; j < i; j++ )
        {
          int howMuch =
            m_ms[i].getShowing( m_choices[i] )
            .overlap( m_ms[j].getShowing( m_choices[j] ) );
          work += (double) ( howMuch * howMuch );
        }
      }

      return Math.sqrt( work );

    }

    public int choice( int which ) { return m_choices[which]; }
  }

  public static void main( String args[] )
  {
    int misses = 0;
    setup();
    System.out.println
    (
      "misses: "
      + m_highMisses
      + ", fitnesses: "
      + m_fitnessCalls
      + ", best fitness: "
      + m_bestFitness
      + ", for genome: "
      + m_bestSeen.toString()
    );
    System.out.println( "Population is: \r\n" + dumpPopulation() );

    while ( misses < NUM_MISSES )
    {
      if ( churn() ) { misses = 0; } else { misses++; }
      if ( misses > m_highMisses )
      {
        m_highMisses = misses; 
        if ( false && ( ( m_highMisses % 100 ) == 0 ) )
        {
          System.out.println
          (
            "misses: "
            + m_highMisses
            + ", fitnesses: "
            + m_fitnessCalls
            + ", best fitness: "
            + m_bestFitness
            + ", for genome: "
            + m_bestSeen.toString()
          );
          // System.out.println( "Population is: \r\n" + dumpPopulation() );
        }
      }
    }

    System.out.println
    (
      "Schedule "
      + m_bestSeen.toString()
      + " has fitness "
      + m_bestFitness
      + " and looks like this:"
      + dumpBestSchedule()
    );
    System.out.println( "Population is: \r\n" + dumpPopulation() );
  }


  public static void setup()
  {

    m_rand = new Random();
    m_mt = MersenneTwister.getTwister( m_rand.nextInt() );
    m_nf = NumberFormat.getInstance();
    m_nf.setMaximumIntegerDigits( 2 );
    m_nf.setMinimumIntegerDigits( 2 );

    m_frame = new Frame( m_windowTitle );
    GridBagLayout gbl = new GridBagLayout();
    GridBagConstraints gbc = new GridBagConstraints();
    m_panel = new Panel( gbl );
    m_movies = new Movie[rawSchedule.length];

    for (int i = 0; i < rawSchedule.length; i++ )
    {
      MovieInstance mitemp[] = new MovieInstance[ rawSchedule[i].length ];
      for ( int j = 0; j < mitemp.length; j++ )
      {
        mitemp[j] = new MovieInstance( rawSchedule[i][j] );
      }
      m_movies[i] = new Movie( names[i], mitemp );
    }

    // create an initial population

    m_population = new Schedule[POP_SIZE];

    int numMovies = m_movies.length;

    for ( int i = 0; i < POP_SIZE; i++ )
    {
      int temp[] = new int[numMovies];
      
      for ( int j = 0; j < numMovies; j++ )
      {
        temp[j] = m_mt.nextInt( m_movies[j].numShowings() );
      }

      m_population[i] = new Schedule( temp, m_movies );
    }

    // find most fit genome of initial population

    m_bestSeen = new Schedule (m_population[0]); // arbitrarily
    m_bestFitness = m_bestSeen.fitness();

    for ( int i = 1; i < POP_SIZE; i++ )
    {
      double f = m_population[i].fitness();
      if ( f < m_bestFitness )
      {
        m_bestFitness = f;
        m_bestSeen = new Schedule( m_population[i] );
      }
    }

  }

  public static Schedule strongTourney()
  {

/*
** Return the best candidate found among TOURNEY_SIZE samples taken
** using a sample with replacement model to leave some small chance that
** even the worst population member could be selected.
*/

    Schedule bestSeen = m_population[ m_mt.nextInt( POP_SIZE ) ];
    double   bestFitness = bestSeen.fitness();
    for ( int i = 1; i < TOURNEY_SIZE; i++ )
    {
      Schedule candidate =  m_population[ m_mt.nextInt( POP_SIZE ) ];
      double   candidateFitness = candidate.fitness();
      if ( candidateFitness < bestFitness )
      {
        bestSeen = candidate;
        bestFitness = candidateFitness;
      }
    }
    return bestSeen;
  }

  public static Schedule weakTourney()
  {

/*
** Fill a TOURNEY_SIZE array with candidates using a cheesy insertion
** sort to keep the worst candidate in the rightmost occupied array
** position, then return _any_ candidate _except_ that worst one
** encountered.  This is deliberately a selection with replacement
** algorithm, so that even the worst member of the population has some
** small chance of being returned.
*/

    Schedule candidates[] = new Schedule[TOURNEY_SIZE];
    candidates[0] = m_population[ m_mt.nextInt( POP_SIZE ) ];
    for ( int i = 1; i < TOURNEY_SIZE; i++ )
    {

      candidates[i] =  m_population[ m_mt.nextInt( POP_SIZE ) ];
      for ( int j = i; j > 0; j-- )
      {
        if ( candidates[j].fitness() < candidates[j - 1].fitness() )
        {
          Schedule temp = candidates[j - 1];
          candidates[j - 1] = candidates[j];
          candidates[j] = temp;
        }
      }
    }

    // return any but the worst one
    return candidates[m_mt.nextInt(TOURNEY_SIZE - 1)];
  }

  public static boolean churn()
  {

/*
** Implement a steady-state genetic algorithm.
*/

     boolean improved = false;

     int candidateIndex = m_mt.nextInt( POP_SIZE );
     if ( MUTATION_RATE > m_mt.nextDouble() )
     {
       // pick an allel to mutate
       int target = m_mt.nextInt( m_movies.length );
       // use the mutation constructor
       Schedule child = 
         new Schedule( m_population[candidateIndex], target);
       // Notice that for mutation, we _always_ do the replacement,
       // regardless of fitness comparision, we just check to decide
       // what report to give our caller.
       if ( child.fitness() < m_bestFitness )
       {
         m_bestFitness = child.fitness();
         m_bestSeen = new Schedule( child );
         improved = true;
         System.out.println
         (
           "new best fitness: "
           + child.fitness()
           + " for genome "
           + child.toString()
           + " after checking "
           + m_fitnessCalls
           + " fitnesses."

         );
       }
       if ( child.fitness() < m_population[candidateIndex].fitness() )
       {
         m_population[candidateIndex] = child;
         return improved;
       }
       else
       {
         m_population[candidateIndex] = child;
         return improved;
       }
     }
     else
     {
       Schedule mom = weakTourney();
       Schedule pop = weakTourney();
       int crossoverPoint = 1 + m_mt.nextInt( m_movies.length - 1 );
       Schedule child = new Schedule( mom, pop, crossoverPoint );
       if ( child.fitness() < m_bestFitness )
       {
         m_bestFitness = child.fitness();
         m_bestSeen = new Schedule( child );
         improved = true;
         System.out.println
         (
           "new best fitness: "
           + child.fitness()
           + " for genome "
           + child.toString()
           + " after checking "
           + m_fitnessCalls
           + " fitnesses."
         );
       }
       if ( child.fitness() < m_population[candidateIndex].fitness() )
       {
         m_population[candidateIndex] = child;
         return improved;
       }
       else
       {
         return improved;
       }
     }
  }

  public static String dumpPopulation()
  {
    StringBuffer b = new StringBuffer();
    b.append( m_population[0].toString() );
    b.append( " " );
    b.append( m_population[0].fitness() );
    for ( int i = 1; i < POP_SIZE; i++ )
    {
      b.append( "\r\n" );
      b.append( m_population[i].toString() );
      b.append( " " );
      b.append( m_population[i].fitness() );
    }
    return b.toString();
  }

  public static String dumpBestSchedule()
  {
    StringBuffer b = new StringBuffer();

    for ( int i = 0; i < m_movies.length; i++ )
    {
      b.append( "\r\n" );
      b.append( m_movies[i].getTitle() );
      b.append( ": " );
      b.append( m_movies[i].getShowing( m_bestSeen.choice( i ) ).toString() );
    }
    return b.toString();
  }

}