package jp.crestmuse.cmx.misc;

import jp.crestmuse.cmx.filewrappers.*;
import jp.crestmuse.cmx.handlers.*;
import javax.xml.transform.*;
import java.util.*;
import java.io.*;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import javax.xml.parsers.*;
import javax.xml.transform.*;
import org.xml.sax.*;


public class PerformanceMatcher {

  private static final int N_BANDS = 128;

  private static void matchtest(TimeFreqRepresentation score, 
                                TimeFreqRepresentation pfm) {
    AandD result= globalMatch(score, pfm, 0, 1000, 0.25, 4);
    System.out.println(result.a + " " + result.d);
/*
    int length = Math.min(score.length(), pfm.length());
    int dist = 0;
    for (int i = 0; i < length; i++) {
      dist += TimeFreqRepresentation.dist(score.get(i), pfm.get(i));
    }
    System.out.println(dist);
    System.out.println(dist(score, pfm, 0, 1));
    System.out.println("10,1:\t\t" + dist(score, pfm, 10, 1));
    System.out.println("20,1:\t\t" + dist(score, pfm, 20, 1));
    System.out.println("30,1:\t\t" + dist(score, pfm, 30, 1));
    System.out.println("40,1:\t\t" + dist(score, pfm, 40, 1));
//    System.out.println("50,1:\t" + dist(score, pfm, 50, 1));
//    System.out.println("60,1:\t" + dist(score, pfm, 60, 1));
//    System.out.println("70,1:\t" + dist(score, pfm, 70, 1));
    System.out.println("40,1.1:\t" + dist(score, pfm, 40, 1.1));
    System.out.println("40,1.2:\t" + dist(score, pfm, 40, 1.2));
    System.out.println("40,1.3:\t" + dist(score, pfm, 40, 1.3));
    System.out.println("40,1.4:\t" + dist(score, pfm, 40, 1.4));
    System.out.println("30,2:\t" + dist(score, pfm, 30, 2));
    System.out.println("40,2:\t" + dist(score, pfm, 40, 2));
    System.out.println("50,2:\t" + dist(score, pfm, 50, 2));
    System.out.println("60,2:\t" + dist(score, pfm, 60, 2));
    System.out.println("70,2:\t" + dist(score, pfm, 70, 2));
    System.out.println("70,1.5:\t" + dist(score, pfm, 70, 1.5));
    System.out.println("100,2:\t" + dist(score, pfm, 100,2));
    System.out.println("70,1.5:\t" + dist(score, pfm, 70, 1.5));
    System.out.println("70,1.5:\t" + dist(score, pfm, 70, 1.5));
    System.out.println("40,2.1:\t" + dist(score, pfm, 40, 2.1));
*/
  }

  private static class AandD {
    private int a;
    private double d;
    private AandD(int a, double d) {
      this.a = a;
      this.d = d;
    }
  }

  private static int[] makeArithmeticSeries(int a, double d, int n) {
    int[] x = new int[n];
    for (int i = 0; i < n; i++)
      x[i] = a + (int)(d * i);
    return x;
  }

  private static AandD globalMatch(TimeFreqRepresentation score, 
                                   TimeFreqRepresentation pfm, 
                                   int a_min, int a_max, 
                                   double d_min, double d_max) {
    return globalMatch(score, pfm, a_min, a_max, d_min, d_max, 
                       new AandD(-1, 0.0));
  }

  private static AandD globalMatch(TimeFreqRepresentation score, 
                                   TimeFreqRepresentation pfm, 
                                   int a_min, int a_max, 
                                   double d_min, double d_max, AandD result) {
//    System.err.print(".");
    if (a_max == a_min || d_max - d_min < 0.0001) {
      result.a = a_max; 
      result.d = d_max;
      return result;
    }
    int[] aa = new int[5];
    aa[0] = a_min;
    aa[4] = a_max;
    aa[2] = (a_min + a_max) / 2;
    aa[1] = (a_min + aa[2]) / 2;
    aa[3] = (a_max + aa[2]) / 2;
    double[] dd = new double[5];
    dd[0] = d_min;
    dd[4] = d_max;
    dd[2] = Math.sqrt(d_min * d_max);
    dd[1] = Math.sqrt(d_min * dd[2]);
    dd[3] = Math.sqrt(d_max * dd[2]);
    int e_min = -1;
    int i_argmin = -1, j_argmin = -1;
    for (int j = 0; j < dd.length; j++) {
//      System.out.println(dd[j]);
      for (int i = 0; i < aa.length; i++) {
        int e = dist(score, pfm, aa[i], dd[j]);
//        System.out.print(aa[i] + ":" + e + "\t");
        if (e < e_min || e_min < 0) {
          e_min = e;
          i_argmin = i;
          j_argmin = j;
        }
      }
//      System.out.println();
    }
    System.err.println("("+aa[i_argmin]+ ","+dd[j_argmin]+") -> "+e_min);
    if (aa[i_argmin] == result.a && abs(dd[j_argmin] - result.d) < 0.0001)
      return result;
    else {
      result.a = aa[i_argmin];
      result.d = dd[j_argmin];
      return 
        globalMatch(score, pfm, 
                    aa[max(0, i_argmin-1)], aa[min(4, i_argmin+1)],
                    dd[max(0, j_argmin-1)], dd[min(4, j_argmin+1)], result);
/*      result.a = aa[i_argmin];
      result.d = dd[j_argmin];
      int a_newmin, a_newmax;
      if (i_argmin == 0) {
        a_newmin = 2 * aa[i_argmin] - aa[i_argmin + 1];
        a_newmax = aa[i_argmin + 1];
      } else if (i_argmin == 4) {
        a_newmin = aa[i_argmin - 1];
        a_newmax = 2 * aa[i_argmin] - aa[i_argmin - 1];
      } else {
        a_newmin = aa[i_argmin - 1];
        a_newmax = aa[i_argmin + 1];
      }
      if (a_newmin < 0) a_newmin = 0;
      double d_newmin, d_newmax;
      if (j_argmin == 0) {
        d_newmin = (dd[j_argmin] * dd[j_argmin]) / dd[j_argmin + 1];
        d_newmax = dd[j_argmin + 1];
      } else if (j_argmin == 4) {
        d_newmin = dd[j_argmin - 1];
        d_newmax = dd[j_argmin] * dd[j_argmin] / dd[j_argmin - 1];
      } else {
        d_newmin = dd[j_argmin - 1];
        d_newmax = dd[j_argmin + 1];
      }
      return globalMatch(score,pfm,a_newmin,a_newmax,d_newmin,d_newmax,result);
*/
    }
  }

  private static int dist(TimeFreqRepresentation score, 
                          TimeFreqRepresentation pfm, 
                          int a, double d) {
    int I = score.length();
    int J = pfm.length();
//    int length = Math.max(I, (int)(a + d * I));
    int dist = 0;
    for (int i = 0; ; i++) {
      int j = (int)(a + d * i);
      if (i >= I && j >= J)
        break;
      else if (i >= I)
        dist += pfm.get(j).distFromZero();
      else if (j >= J)
        dist += score.get(i).distFromZero();
      else dist += TimeFreqRepresentation.dist(score.get(i), pfm.get(j));
    }
    return dist;
//    return (double)dist / (double)length;
  }

  private static void 
  searchNotes(int[] path, TimeFreqRepresentation score,
              TimeFreqRepresentation pfm, int width) {
    int length = path.length;
    for (int t = 0; t < length; t++) {
//      System.out.println(t + ":" + path[t]);
      TimeFreqRepresentation.TimeFreqElement e1 = score.get(t);
      NoteCompatible[] data1 = e1.data();
      TimeFreqRepresentation.TimeFreqElement e2 = pfm.get(path[t]);
      NoteCompatible[] data2 = e2.data();
      for (int i = 0; i < data1.length; i++) {
        if (data1[i] != null) {
          System.out.println("Scr:" + t + ":" + i + ":" + data1[i]);
          for (int t2 = Math.max(path[t]-width,0); t2 < Math.min(path[t]+width,pfm.length()); t2++) {
            NoteCompatible note = pfm.get(t2).data()[i];
            if (note != null) 
              System.out.println("Pfm:" + t2 + ":" + i + ":" + note);
          }
        }
      }
    }
  }
          

  private static double[] calcTempo(int[] path, TimeFreqRepresentation score,
                                    int ticksPerBeat, double pfmtempo) {
    int length = path.length;
    for (int i = 0; i < length; i++) 
      score.changeTime(i, (double)(path[i]*60)/(double)ticksPerBeat/pfmtempo);
    double[] tempi = new double[length / ticksPerBeat];
    for (int i = 0; i < tempi.length; i++) {
      double t0 = score.get(i).time();
      double t1 = score.get(i+ticksPerBeat).time();
      tempi[i] = 60.0 / (t1 - t0);
    }
    return tempi;
  }

  private static void addTempoDeviations(double[] tempi, DeviationDataSet dds) 
    throws IOException, ParserConfigurationException, SAXException,
    TransformerException {
    int beats = 4, beatType = 4;
    double sum = 0;
    for (double tempo : tempi)
      sum += tempo;
    double mean = sum / tempi.length;
    MusicXMLWrapper musicxml = dds.getTargetWrapper().getTargetMusicXML();
    MusicXMLWrapper.Part[] partlist = musicxml.getPartList();
    MusicXMLWrapper.Measure[] measurelist = partlist[0].getMeasureList();
    dds.addNonPartwiseControl(measurelist[0].number(), 1, "tempo", mean);
    int k = 0;
    for (MusicXMLWrapper.Measure measure : measurelist) {
      MusicXMLWrapper.Attributes attr = measure.getAttributesNodeInterface();
      if (attr != null) {
        int beats_ = attr.beats();
        int beatType_ = attr.beatType();
        if (beats_ != 0 && beatType_ != 0) {
          beats = beats_;
          beatType = beatType_;
        }
      }
      for (int i = 0; i < beats * 4 / beatType; i++) {
        dds.addNonPartwiseControl(measure.number(), i+1, 
                                  "tempo-deviation", tempi[k] / mean);
        k++;
      }
    }
  }

  private static int[] getPath(DTWMatrix matrix) {
    int I = matrix.nrows;
    int J = matrix.ncols;
    int[] path = new int[I];
    int i = I - 1, j = J - 1;
    do {
      path[i] = j;
      DTWMatrix.DTWMatrixElement e = matrix.get(i, j);
      i = e.targetX;
      j = e.targetY;
    } while (i >= 0 || j >= 0);
    return path;
  }
      
  private static final int BEAM_WIDTH = 100;

  private HypothesisList[] hypolist;

  private class HypothesisList extends ArrayList<Hypothesis> {

  }

  private class Hypothesis {
    private int i;
    private int j;
    private int cost;
    private Hypothesis[] next = null;
    private Hypothesis previous = null;
    private int indexInPrevious = -1;
    public String toString() {
      return "[i=" + i + ",j=" + j + ",cost=" + cost + "]";
    }
  }

  private int findFirstOnset(TimeFreqRepresentation tf) {
    int length = tf.length();
    for (int i = 0; i < length; i++) 
      if (tf.get(i).distFromZero() > 0)
        return i;
    return -1;
  }

  private int findCompletelyMatchedFrame
  (TimeFreqRepresentation.TimeFreqElement key, 
   TimeFreqRepresentation target, int from) {
    int length = target.length();
    for (int i = from; i < length; i++)
      if (target.get(i).dist(key) == 0)
        return i;
    return -1;
  }

  private Hypothesis makeFirstHypothesis(int i, int j, int cost) {
    Hypothesis hypo = new Hypothesis();
    hypo.i = i;
    hypo.j = j;
    hypo.cost = cost;
    return hypo;
  }

  private Hypothesis makeFirstHypothesis
  (TimeFreqRepresentation score, TimeFreqRepresentation pfm) {
    int i0 = findFirstOnset(score);
    int j0 = findFirstOnset(pfm);
    int cost = TimeFreqRepresentation.dist(score.get(i0), pfm.get(j0));
    Hypothesis hypo = makeFirstHypothesis(i0, j0, cost);
    addHypothesisToList(i0, hypo);
    return hypo;
  }

  private void addHypothesisToList(int index, Hypothesis hypo) {
    if (hypolist[index] == null)
      hypolist[index] = new HypothesisList();
    hypolist[index].add(hypo);
  }

  private void makeNextHypotheses(Hypothesis hypo, 
                                  TimeFreqRepresentation score,
                                  TimeFreqRepresentation pfm, 
                                  int scale) {
    int i = hypo.i + 1;
    TimeFreqRepresentation.TimeFreqElement e1 = score.get(i);
    int J = pfm.length();
    int jc = hypo.j + scale;
    int jL = Math.max(hypo.j + 1, jc - BEAM_WIDTH / 2);
    int jR = Math.min(jc + BEAM_WIDTH / 2, J - 1);
    hypo.next = new Hypothesis[jR - jL + 1];
    for (int j = jL ; j <= jR; j++) {
      int dist = pfm.get(j).dist(e1);
      Hypothesis newhypo = new Hypothesis();
      newhypo.i = i;
      newhypo.j = j;
      newhypo.cost = hypo.cost + dist;
      newhypo.previous = hypo;
      newhypo.indexInPrevious = j - jL;
      hypo.next[j - jL] = newhypo;
      addHypothesisToList(i, newhypo);
    }
  }

  private void pruneHypotheses(int index) {
    Collections.sort(hypolist[index], new Comparator<Hypothesis>() {
                      public int compare(Hypothesis h1, Hypothesis h2) {
                        return h1.cost - h2.cost;
                      }
                    });
    int size = hypolist[index].size();
    for (int i = size - 1; i >= BEAM_WIDTH; i--) {
      Hypothesis hypo = hypolist[index].get(i);
      hypo.previous.next[hypo.indexInPrevious] = null;
      hypolist[index].remove(hypo);
    }
  }

  private void printHypotheses(int index) {
    System.out.println(hypolist[index]);
  }

  private static DTWMatrix
  dtw(TimeFreqRepresentation score, TimeFreqRepresentation pfm, int r) {
    int I = score.length();
    int J = pfm.length();
    double a = (double)J / (double)I;
    if (r <= 0)
      r = J;
    DTWMatrix matrix = new DTWMatrix(I, J);
    matrix.set(-1, -1, 0, -1, -1);
    for (int i = 0; i < I; i++) {
      System.err.print(".");
      TimeFreqRepresentation.TimeFreqElement e1 = score.get(i);
      int jc = (int)(a * i);
      int jR = Math.min(jc + r, J - 1);
      for (int j = Math.max(0, jc-r) ; j <= jR; j++) {
        TimeFreqRepresentation.TimeFreqElement e2 = pfm.get(j);
        int d = e1.dist(e2);
        int c1 = matrix.getValue(i-1, j) + d;
        int c2 = matrix.getValue(i-1, j-1) + 2 * d;
        int c3 = matrix.getValue(i, j-1) + d;
        int c_min = Math.min(c2, Math.min(c1, c3));
        if (c_min < 0) System.err.print("!");
        if (c_min == c2)
          matrix.set(i, j, c_min, i-1, j-1);
        else if (c_min == c3)
          matrix.set(i, j, c_min, i, j-1);
        else
          matrix.set(i, j, c_min, i-1, j);
      }
    }
    return matrix;
  }

  private static class DTWMatrix {
    private HashMap<IntPair,DTWMatrixElement> values;
    private int nrows, ncols;
    private final DTWMatrixElement DEFAULT_MATRIX_ELEMENT = 
      new DTWMatrixElement(Integer.MAX_VALUE / 2, -1, -1);
    private DTWMatrix(int nrows, int ncols) {
      this.nrows = nrows;
      this.ncols = ncols;
      values = new HashMap<IntPair,DTWMatrixElement>(Math.max(nrows,ncols));
    }
    private void set(int i, int j, int value, int targetX, int targetY) {
      values.put(new IntPair(i, j), 
                 new DTWMatrixElement(value, targetX, targetY));
    }
    private DTWMatrixElement get(int i, int j) {
      if (i >= nrows || j >= ncols || i < -1 || j < -1)
        throw new ArrayIndexOutOfBoundsException();
      if (values.containsKey(new IntPair(i, j)))
        return values.get(new IntPair(i, j));
      else
        return DEFAULT_MATRIX_ELEMENT;
    }
    private int getValue(int i, int j) {
      return get(i, j).value;
    }
    private class IntPair {
      private int i, j;
      private IntPair(int i, int j) {
        this.i = i;
        this.j = j;
      }
      public boolean equals(Object o) {
        IntPair another = (IntPair)o;
        return (i == another.i) && (j == another.j);
      }
      public int hashCode() {
        return i * nrows + j;
      }
    }
    private class DTWMatrixElement {
      private int value, targetX, targetY;
      private DTWMatrixElement(int value, int targetX, int targetY){
        this.value = value;
        this.targetX = targetX;
        this.targetY = targetY;
      }
    }
  }           

  private static 
    TimeFreqRepresentation getTimeFreqRepresentation(SCCXMLWrapper scc) 
    throws TransformerException {
    final int division = scc.getDivision();
    final TimeFreqRepresentation tfr = new TimeFreqRepresentation(N_BANDS);
    scc.processNotes(new SCCHandler() {
        public void beginHeader(SCCXMLWrapper w) { }
        public void endHeader(SCCXMLWrapper w) { }
        public void beginPart(SCCXMLWrapper.Part part, SCCXMLWrapper w) {}
        public void endPart(SCCXMLWrapper.Part part, SCCXMLWrapper w) {}
        public void processHeaderElement(int timestamp, String name, 
                                         String content, SCCXMLWrapper w) {}
        public void processNote(SCCXMLWrapper.Note note, SCCXMLWrapper w) {
          int onset = note.onset();
          int offset = note.offset();
          int notenum = note.notenum();
//          System.err.println(onset + " " + offset + " " + notenum);
          int length;
          while ((length = tfr.length()) <= offset)
            tfr.addTime(length * division);
          tfr.set(onset, notenum, note);
          for (int n = onset; n < offset; n++)
            tfr.set(n, notenum, (byte)(127 * (offset - n) / (offset - onset)));
        }
      });
    return tfr;
  }

  public static void main(String[] args) {
    try {
      MIDIXMLWrapper midixml = MIDIXMLWrapper.readSMF(args[1]);
      SCCXMLWrapper scc1 = midixml.toSCCXML();
      TimeFreqRepresentation tfr1 = getTimeFreqRepresentation(scc1);
      MusicXMLWrapper musicxml = (MusicXMLWrapper)CMXFileWrapper.readfile(args[0]);
      SCCXMLWrapper scc0 = musicxml.makeDeadpanSCCXML(scc1.getDivision());
      TimeFreqRepresentation tfr0 = getTimeFreqRepresentation(scc0);
      System.err.println(tfr0.length());
      System.err.println(tfr1.length());

//     int i0 = findFirstOnset(tfr0);
//      int j0 = findFirstOnset(tfr1);
//
//      SearchHypothesis hypo = 
//        makeFirstHypothesis(i0, j0, TimeFreqRepresentation.dist(tfr0.get(i0), 
//                                                                tfr1.get(j0)));

      PerformanceMatcher pm = new PerformanceMatcher();

      pm.hypolist = new HypothesisList[tfr0.length()];
      Hypothesis hypo = pm.makeFirstHypothesis(tfr0, tfr1);
//      double ratio = (double)tfr1.length() / (double)tfr0.length();
      int scale = tfr1.length() / tfr0.length();
      pm.makeNextHypotheses(hypo, tfr0, tfr1, scale);
      pm.printHypotheses(1);
      pm.pruneHypotheses(1);
      pm.printHypotheses(1);
      for (Hypothesis h : hypo.next) {
        pm.makeNextHypotheses(h, tfr0, tfr1, scale);
      }
      pm.printHypotheses(2);
      pm.pruneHypotheses(2);
      pm.printHypotheses(2);



      if (true)
      return;


//      AandD result= globalMatch(tfr0, tfr1, 0, 1000, 0.25, 4);
//      int[] path2 = makeArithmeticSeries(result.a, result.d, tfr0.length());

//      for (int i = 0; i < tfr0.length(); i++)
//        System.out.println(tfr0.get(i).toString());

//      for (int i = 0; i < path2.length; i++)
//        System.out.println(tfr1.get(path2[i]).toString());


/*
      for (int i = 0; i < path2.length; i++) {
        TimeFreqRepresentation.TimeFreqElement e1 =  tfr0.get(i);
        System.out.println(i +":\t" + e1.toString2());
      }

      System.out.println();

      for (int i = 0; i < path2.length; i++) {
        TimeFreqRepresentation.TimeFreqElement e2 = tfr1.get(path2[i]);
        System.out.println(path2[i]+":\t" + e2.toString2());
      }
*/
        


//      searchNotes(path2, tfr0, tfr1, Integer.parseInt(args[3]));

      DTWMatrix matrix = dtw(tfr0, tfr1, Integer.parseInt(args[2]));
      int[] path = getPath(matrix);
      for (int i = 0; i < path.length; i++)
        System.out.println(tfr1.get(path[i]).toString());
//
//      for (int i = 0; i < path.length; i++) 
//        System.out.println(i + ": " + path[i] + ", " + 
//                           (int)(result.a + result.d * i));

/*
//      for (int a : path)
//        System.out.print(a + " ");
      double[] tempi = calcTempo(path, tfr0, scc1.getDivision(), 120);
      DeviationInstanceWrapper dev = 
        DeviationInstanceWrapper.createDeviationInstanceFor(musicxml);
      DeviationDataSet dds = dev.createDeviationDataSet();
      addTempoDeviations(tempi, dds);
//      dds.addElementsToWrapper();
//      dev.write(System.out);
*/
//      searchNotes(path, tfr0, tfr1, Integer.parseInt(args[3]));

    
    } catch (Exception e) {
      e.printStackTrace();
      System.exit(1);
    }
  }

}
