public class GlobalAligner implements MelodyAligner
{
	protected NGramComparer comparer;
	
	/**
	 * Constructs a new {@code GlobalAligner} with the specified
	 * {@link NGramComparer}.
	 * 
	 * @param comparer
	 *            the n-gram comparer to use.
	 */
	public GlobalAligner(NGramComparer comparer) {
		this.comparer = comparer;
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "Global(comparer)"}, where
	 *         {@code comparer} is the name of the underlying
	 *         {@link NGramComparer}.
	 */
	@Override
	public String getName() {
		return "Global("+this.comparer.getName()+")";
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public double align(ArrayList<NGram> s1, ArrayList<NGram> s2) {
		
		double[][] matrix = new double[s1.size() + 1][s2.size() + 1];
		
		for (int i = 1; i <= s1.size(); i++)
			matrix[i][0] = matrix[i - 1][0] + this.comparer.compare(s1.get(i - 1), null);
		for (int j = 1; j <= s2.size(); j++)
			matrix[0][j] = matrix[0][j - 1] + this.comparer.compare(null, s2.get(j - 1));
		
		for (int i = 1; i <= s1.size(); i++) {
			for (int j = 1; j <= s2.size(); j++) {
				double left = matrix[i - 1][j] + this.comparer.compare(s1.get(i - 1), null);
				double up = matrix[i][j - 1] + this.comparer.compare(null, s2.get(j - 1));
				double diag = matrix[i - 1][j - 1] + this.comparer.compare(s1.get(i - 1), s2.get(j - 1));
				matrix[i][j] = Math.max(left, Math.max(up, diag));
			}
		}
		
		return matrix[s1.size()][s2.size()];
	}	
}
 public class HybridAligner implements MelodyAligner
{
	protected NGramComparer comparer;
	
	/**
	 * Constructs a new {@code HybridAligner} with the specified
	 * {@link NGramComparer}.
	 * 
	 * @param comparer
	 *            the n-gram comparer to use.
	 */
	public HybridAligner(NGramComparer comparer) {
		this.comparer = comparer;
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "Hybrid(comparer)"}, where
	 *         {@code comparer} is the name of the underlying
	 *         {@link NGramComparer}.
	 */
	@Override
	public String getName() {
		return "Hybrid("+this.comparer.getName()+")";
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public double align(ArrayList<NGram> s1, ArrayList<NGram> s2) {
		double[][] matrix = new double[s1.size() + 1][s2.size() + 1];
		
		for (int i = 1; i <= s1.size(); i++)
			matrix[i][0] = matrix[i - 1][0] + this.comparer.compare(s1.get(i - 1), null);
		for (int j = 1; j <= s2.size(); j++)
			matrix[0][j] = matrix[0][j - 1] + this.comparer.compare(null, s2.get(j - 1));
		
		double max = Double.NEGATIVE_INFINITY;
		for (int i = 1; i <= s1.size(); i++) {
			for (int j = 1; j <= s2.size(); j++) {
				double left = matrix[i - 1][j] + this.comparer.compare(s1.get(i - 1), null);
				double up = matrix[i][j - 1] + this.comparer.compare(null, s2.get(j - 1));
				double diag = matrix[i - 1][j - 1] + this.comparer.compare(s1.get(i - 1), s2.get(j - 1));
				matrix[i][j] = Math.max(left, Math.max(up, diag));
				if (max < matrix[i][j])
					max = matrix[i][j];
			}
		}
		
		return max / Math.min(s1.size(), s2.size()); // TODO: move normalization to algorithm?
	}
}
 public class LocalAligner implements MelodyAligner
{	
	protected NGramComparer comparer;
		
	/**
	 * Constructs a new {@code LocalAligner} with the specified {@link NGramComparer}. 
	 * 
	 * @param comparer the n-gram comparer to use.
	 */
	public LocalAligner(NGramComparer comparer) {
		this.comparer = comparer;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "Local(comparer)"}, where
	 *         {@code comparer} is the name of the underlying
	 *         {@link NGramComparer}.
	 */
	@Override
	public String getName() {
		return "Local("+this.comparer.getName()+")";
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public double align(ArrayList<NGram> s1, ArrayList<NGram> s2) {
		double[][] matrix = new double[s1.size() + 1][s2.size() + 1];
		
		double max = Double.NEGATIVE_INFINITY;
		for (int i = 1; i <= s1.size(); i++) {
			for (int j = 1; j <= s2.size(); j++) {
				double left = matrix[i - 1][j] + this.comparer.compare(s1.get(i - 1), null);
				double up = matrix[i][j - 1] + this.comparer.compare(null, s2.get(j - 1));
				double diag = matrix[i - 1][j - 1] + this.comparer.compare(s1.get(i - 1), s2.get(j - 1));
				matrix[i][j] = Math.max(0, Math.max(left, Math.max(up, diag)));
				if (max < matrix[i][j])
					max = matrix[i][j];
			}
		}
		
		return max / Math.min(s1.size(), s2.size());  // TODO: move normalization to algorithm?
	}
	
}
 public class BSplinePitchNGramComparer implements NGramComparer
{
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "BSplinePitch"}.
	 */
	@Override
	public String getName() {
		return "BSplinePitch";
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return 0 if both {@link NGram}s are equivalent or the area between the
	 *         first derivatives of their corresponding Uniform B-Splines.
	 */
	@Override
	public double compare(NGram g1, NGram g2) {
		if (g1 == null)
			g1 = g2.getNullSpan();
		if (g2 == null)
			g2 = g1.getNullSpan();
		if (g1.size() < 2 || g1.size() > UniformBSpline.BASIS_FUNCTIONS.length)
			throw new IllegalArgumentException(this.getName() + " only supports n-grams with 2 to " + UniformBSpline.BASIS_FUNCTIONS.length
					+ " notes.");
		if (this.getNGramId(g1).equals(this.getNGramId(g2)))
			return 0;
		
		PolynomialFunction p1p = new PolynomialFunction(new double[] { 0 });
		PolynomialFunction p2p = new PolynomialFunction(new double[] { 0 });
		for (int i = 1; i < g1.size(); i++) {
			PolynomialFunction basis = UniformBSpline.BASIS_FUNCTIONS[g1.size() - 1][i - 1];
			p1p = p1p.add(basis.multiply(new PolynomialFunction(new double[] { g1.get(g1.size() - i).getPitch() - g1.get(0).getPitch() })));
			p2p = p2p.add(basis.multiply(new PolynomialFunction(new double[] { g2.get(g2.size() - i).getPitch() - g2.get(0).getPitch() })));
		}
		PolynomialFunction pp = p1p.polynomialDerivative().subtract(p2p.polynomialDerivative());
		
		Laguerre laguerre = new Laguerre();
		ArrayList<Double> realRoots = laguerre.findRoots(pp);
		return -laguerre.computeAreaBetweenDerivatives(p1p, p2p, realRoots);
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return a {@link String} with the format
	 *         <code>{p2-p1, p3-p1, ..., p(n-1)-p1}</code>, where {@code pi}
	 *         corresponds to the pitch of the i-th note inside the n-gram. The
	 *         {@link String} {@code "null"} is returned if the n-gram is
	 *         {@code null}.
	 */
	@Override
	public String getNGramId(NGram g) {
		if (g == null)
			return "null";
		
		String res = "{";
		for (int i = 1; i < g.size(); i++)
			res += (g.get(i).getPitch() - g.get(0).getPitch()) + " ";
		return res.trim() + "}";
	}
}
 public class BSplineShapeNGramComparer implements NGramComparer
{
	static final double DEFAULT_MAX_PENALIZATION = 8;
	static final double DEFAULT_AVG_PENALIZATION = 1;
	static final double DEFAULT_MIN_PENALIZATION = 0.5;
	
	protected double dMax;
	protected double dMed;
	protected double dMin;
	
	/**
	 * Constructs a {@code BSplineShapeNGramComparer} with the default maximum,
	 * medium and minimum penalizations (8, 1 and 0.5).
	 */
	public BSplineShapeNGramComparer() {
		this(BSplineShapeNGramComparer.DEFAULT_MAX_PENALIZATION, BSplineShapeNGramComparer.DEFAULT_AVG_PENALIZATION,
				BSplineShapeNGramComparer.DEFAULT_MIN_PENALIZATION);
	}
	
	/**
	 * Constructs a {@code BSplineShapeNGramComparer} with the specified
	 * maximum, medium and minimum penalizations.
	 * 
	 * @param dMax
	 *            the maximum penalization.
	 * @param dMed
	 *            the medium penalization.
	 * @param dMin
	 *            the minimum penalization.
	 */
	public BSplineShapeNGramComparer(double dMax, double dMed, double dMin) {
		this.dMax = dMax;
		this.dMed = dMed;
		this.dMin = dMin;
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "BSplineShape(dMax,dMed,dMin)"}.
	 */
	@Override
	public String getName() {
		return "BSplineShape(" + this.dMax + "," + this.dMed + "," + this.dMin + ")";
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public double compare(NGram g1, NGram g2) {
		if (g1 == null)
			g1 = g2.getNullSpan();
		if (g2 == null)
			g2 = g1.getNullSpan();
		if (g1.size() != 3)
			throw new IllegalArgumentException(this.getName() + " only supports n-grams with 3 notes.");
		if (this.getNGramId(g1).equals(this.getNGramId(g2)))
			return 0;
		
		PolynomialFunction p1 = new PolynomialFunction(new double[] { 0 });
		PolynomialFunction p2 = new PolynomialFunction(new double[] { 0 });
		for (int i = 1; i < g1.size(); i++) {
			PolynomialFunction basis = UniformBSpline.BASIS_FUNCTIONS[g1.size() - 1][i - 1];
			p1 = p1.add(basis.multiply(new PolynomialFunction(new double[] { g1.get(g1.size() - i).getPitch() - g1.get(0).getPitch() })));
			p2 = p2.add(basis.multiply(new PolynomialFunction(new double[] { g2.get(g2.size() - i).getPitch() - g2.get(0).getPitch() })));
		}
		PolynomialFunction p1_ = p1.polynomialDerivative();
		PolynomialFunction p2_ = p2.polynomialDerivative();
		
		/*
		double p1_0 = Math.signum(p1_.value(0));
		double p1_1 = Math.signum(p1_.value(1));
		double p2_0 = Math.signum(p2_.value(0));
		double p2_1 = Math.signum(p2_.value(1));
		
		if(p1_0 == p2_0){ // same at 0
			if(p1_1 == p2_1) // same at 1
				return -this.dMin;
			else if(p1_1*p2_1<0) // opposite at 1
				return -this.dMed;
			else // some flat at 1
				return -this.dMed;
		}else if(p1_0*p2_0 < 0) { // opposite at 0
			if(p1_1 == p2_1) // same at 1
				return -this.dMed;
			else if(p1_1*p2_1<0) // opposite at 1
				return -this.dMax;
			else // some flat at 1
				return -this.dMax;
		}else { // some flat at 0
			if(p1_1 == p2_1) // same at 1
				return -this.dMed;
			else if(p1_1*p2_1<0) // opposite at 1
				return -this.dMax;
			else // some flat at 1
				return -this.dMax;
		}*/		
		
		double p1_0 = p1_.value(0);
		double p1_1 = p1_.value(1);
		double p2_0 = p2_.value(0);
		double p2_1 = p2_.value(1);
		
		// TODO: this similarity function is not symmetric
		if (p1_0 <= 0 && p1_1 >= 0) { // p1 is \/
			if (p2_0 <= 0 && p2_1 >= 0) // p2 is \/
				return -this.dMin;
			else if (p2_0 >= 0 && p2_1 <= 0) // p2 is /\
				return -this.dMax;
			else
				return -this.dMed;
		}
		if (p1_0 >= 0 && p1_1 <= 0) { // p1 is /\
			if (p2_0 >= 0 && p2_1 <= 0) // p2 is /\
				return -this.dMin;
			else if (p2_0 <= 0 && p2_1 >= 0) // p2 is \/
				return -this.dMax;
			else
				return -this.dMed;
		}
		if (p1_0 >= 0 && p1_1 >= 0) { // p1 is /
			if (p2_0 >= 0 && p2_1 >= 0) // p2 is /
				return -this.dMin;
			else if (p2_0 <= 0 && p2_1 <= 0) // p2 is \
				return -this.dMax;
			else
				return -this.dMed;
		}
		if (p1_0 <= 0 && p1_1 <= 0) { // p1 is \
			if (p2_0 <= 0 && p2_1 <= 0) // p2 is \
				return -this.dMin;
			else if (p2_0 >= 0 && p2_1 >= 0) // p2 is /
				return -this.dMax;
			else
				return -this.dMed;
		}
		
		return -this.dMin;
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return a {@link String} with the format
	 *         <code>{p2-p1, p3-p1, ..., p(n-1)-p1}</code>, where {@code pi}
	 *         corresponds to the pitch of the i-th note inside the n-gram. The
	 *         {@link String} {@code "null"} is returned if the n-gram is
	 *         {@code null}.
	 */
	@Override
	public String getNGramId(NGram g) {
		if (g == null)
			return "null";
		
		String res = "{";
		for (int i = 1; i < g.size(); i++)
			res += (g.get(i).getPitch() - g.get(0).getPitch()) + " ";
		return res.trim() + "}";
	}
}
 public class BSplineTimeNGramComparer implements NGramComparer
{
	protected final DecimalFormat format = new DecimalFormat("#.###");
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "BSplineTime"}.
	 */
	@Override
	public String getName() {
		return "BSplineTime";
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return 0 if both {@link NGram}s are equivalent or the area between the
	 *         first derivatives of their corresponding Uniform B-Splines.
	 */
	@Override
	public double compare(NGram g1, NGram g2) {
		if (g1 == null)
			g1 = g2.getNullSpan();
		if (g2 == null)
			g2 = g1.getNullSpan();
		if (g1.size() < 2 || g1.size() > UniformBSpline.BASIS_FUNCTIONS.length)
			throw new IllegalArgumentException(this.getName() + " only supports n-grams with 2 to " + UniformBSpline.BASIS_FUNCTIONS.length
					+ " notes.");
		if (this.getNGramId(g1).equals(this.getNGramId(g2)))
			return 0;
		
		PolynomialFunction p1t = new PolynomialFunction(new double[] { 0 });
		PolynomialFunction p2t = new PolynomialFunction(new double[] { 0 });
		for (int i = 0; i < g1.size(); i++) {
			PolynomialFunction basis = UniformBSpline.BASIS_FUNCTIONS[g1.size() - 1][i];
			p1t = p1t.add(basis.multiply(new PolynomialFunction(new double[] { g1.get(g1.size() - i - 1).getDuration()
					/ (double) g1.get(0).getDuration() })));
			p2t = p2t.add(basis.multiply(new PolynomialFunction(new double[] { g2.get(g2.size() - i - 1).getDuration()
					/ (double) g2.get(0).getDuration() })));
		}
		PolynomialFunction pt = p1t.polynomialDerivative().subtract(p2t.polynomialDerivative());
		
		Laguerre laguerre = new Laguerre();
		ArrayList<Double> realRoots = laguerre.findRoots(pt);
		return -laguerre.computeAreaBetweenDerivatives(p1t, p2t, realRoots);
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return a {@link String} with the format
	 *         <code>{d2/d1, d3/d1, ..., d(n-1)/d1}</code>, where {@code di}
	 *         corresponds to the duration of the i-th note inside the n-gram.
	 *         The {@link String} {@code "null"} is returned if the n-gram is
	 *         {@code null}.
	 */
	@Override
	public String getNGramId(NGram g) {
		if (g == null)
			return "null";
		
		String res = "{";
		for (int i = 1; i < g.size(); i++)
			res += this.format.format(g.get(i).getDuration() / (double) g.get(0).getDuration()) + " ";
		return res.trim() + "}";
	}
}
 public class Result
{
	protected Melody melody;
	protected double score;
	
	/**
	 * Gets the {@link Melody} to which this result refers.
	 * 
	 * @return the melody.
	 */
	public Melody getMelody() {
		return melody;
	}
	
	/**
	 * Gets the similarity score of this result.
	 * 
	 * @return the similarity score.
	 */
	public double getScore() {
		return score;
	}
	
	/**
	 * Constructs a new {@link Result} for the specified melody with the
	 * specified similarity score.
	 * 
	 * @param melody
	 *            the melody.
	 * @param score
	 *            the similarity score.
	 */
	public Result(Melody melody, double score) {
		this.melody = melody;
		this.score = score;
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public String toString() {
		return "Result [melody=" + melody.getId() + ", score=" + score + "]";
	}
}
 public interface ResultRanker
{
	/**
	 * Gets the name of this {@code ResultRanker}.
	 * 
	 * @return the name of this result ranker.
	 */
	public String getName();
	
	/**
	 * Ranks the top {@code k} {@link Result}s for the specified query
	 * {@link Melody}. Results are ranked in decreasing order of similarity to
	 * the query.
	 * 
	 * @param query
	 *            the query that originated the results.
	 * @param results
	 *            the unranked list of results.
	 * @param k
	 *            the cutoff.
	 */
	public void rank(Melody query, Result[] results, int k);
}
 public class UntieResultRanker implements ResultRanker
{
	protected MelodyComparer comparer;
	
	/**
	 * Constructs a new {@code UntieResultRanker} with the specified
	 * {@link MelodyComparer}.
	 * 
	 * @param comparer
	 *            the n-gram comparer to use.
	 */
	public UntieResultRanker(MelodyComparer comparer) {
		this.comparer = comparer;
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public void rank(final Melody query, Result[] results, int k) {
		// first sort by score
		Arrays.sort(results, new Comparator<Result>() {
			@Override
			public int compare(Result r1, Result r2) {
				return Double.compare(r2.getScore(), r1.getScore());
			}
		});
		// now traverse and sort groups with the same score
		for (int i = 1, top = 0; i < results.length; i++) {
			if (results[i].getScore() < results[top].getScore()) {
				// re-sort from top to i-1
				Arrays.sort(results, top, i, new Comparator<Result>() {
					@Override
					public int compare(Result r1, Result r2) {
						// sort by new comparer
						double score1 = UntieResultRanker.this.comparer.compare(query, r1.getMelody());
						double score2 = UntieResultRanker.this.comparer.compare(query, r2.getMelody());
						if (score1 != score2)
							return Double.compare(score2, score1);
						// then by length
						if (r1.getMelody().size() != r2.getMelody().size())
							return Integer.compare(Math.abs(r1.getMelody().size() - query.size()),
									Math.abs(r2.getMelody().size() - query.size()));
						// then by doc id
						return r1.getMelody().getId().compareTo(r2.getMelody().getId());
					}
				});
				top = i;
				if (top >= k)
					break; // no need to re-sort beyond the top k
			}
		}
	}
	
	/**
	 * {@inheritDoc}
	 * 
	 * @return the {@link String} {@code "Untie(comparer)"}.
	 */
	@Override
	public String getName() {
		return "Untie(" + this.comparer.getName() + ")";
	}
}
 public class ConsoleUIObserver implements UIObserver {
	protected String[] args;
	protected Options options;

	protected File qOpt;
	protected File cOpt;
	protected String aOpt;
	protected boolean lOpt;
	protected boolean hOpt;
	protected int tOpt;
	protected int kOpt;
	protected int vOpt;

	/**
	 * Constructs a new {@code ConsoleUIObserver} according to some command line
	 * arguments.
	 * 
	 * @param args
	 *            the command line arguments to configure the algorithm.
	 */
	@SuppressWarnings("static-access")
	public ConsoleUIObserver(String[] args) {
		this.args = args;

		this.qOpt = null;
		this.cOpt = null;
		this.aOpt = null;
		this.lOpt = false;
		this.hOpt = false;
		this.tOpt = Runtime.getRuntime().availableProcessors();
		this.kOpt = Integer.MAX_VALUE;
		this.vOpt = 0;

		this.options = new Options();
		// required arguments
		this.options.addOption(Option.builder("q").required().hasArg().argName("file/dir")
				.desc("path to the query melody or melodies.").build());
		this.options.addOption(Option.builder("c").required().hasArg().argName("dir")
				.desc("path to the collection of documents.").build());
		this.options.addOption(Option.builder("a").required().hasArg().argName("name")
				.desc("algorithm to run:" + "\n- 2010-domain, 2010-pitchderiv, 2010-shape"
								+ "\n- 2011-shape, 2011-pitch, 2011-time"
								+ "\n- 2012-shapeh, 2012-shapel, 2012-shapeg, 2012-time, 2012-shapetime"
								+ "\n- 2013-shapeh, 2013-time, 2013-shapetime"
								+ "\n- 2014-shapeh, 2014-time, 2014-shapetime"
								+ "\n- 2015-shapeh, 2015-time, 2015-shapetime").build());
		// optional arguments
		this.options.addOption(Option.builder("l").desc("show results in a single line (omits similarity scores).").build());
		this.options.addOption(Option.builder("t").hasArg().argName("num").desc("run a fixed number of threads.").build());
		this.options.addOption(Option.builder("k").hasArg().argName("cutoff").desc("number of documents to retrieve.").build());
		this.options.addOption(Option.builder("v").desc("verbose, to stderr.").build());
		this.options.addOption(Option.builder("vv").desc("verbose a lot, to stderr.").build());
		this.options.addOption(Option.builder("h").desc("show this help message.").build());
		this.options.addOption(Option.builder("gui").desc("run with graphical user interface.").build());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void start() {
		/**
		 * Parse Command Line Options
		 */
		boolean parsed = this.parseArguments();
		if (!parsed)
			System.exit(1);

		if (this.hOpt) {
			this.printUsage(this.options);
			return;
		}

		// queries
		ArrayList<Melody> queries = null;
		try {
			this.verbose(2, "Reading queries...");
			queries = MelodyShape.readQueries(this.qOpt);
			this.verbose(2, "done (" + queries.size() + " melodies).\n");
		} catch (IllegalArgumentException ex) {
			System.err.println("Error: " + ex.getMessage());
			System.exit(1);
		}
		// documents
		MelodyCollection coll = null;
		try {
			this.verbose(2, "Reading collection...");
			coll = MelodyShape.readCollection(this.cOpt);
			this.verbose(2, "done (" + coll.size() + " melodies).\n");
		} catch (IllegalArgumentException ex) {
			System.err.println("Error: " + ex.getMessage());
			System.exit(1);
		}
		// algorithm
		this.verbose(2, "Instantiating algorithm...");
		MelodyComparer comparer = MelodyShape.getMainComparer(this.aOpt, coll);
		ResultRanker ranker = MelodyShape.getMainRanker(this.aOpt, coll);
		MelodyComparer comparerRerank = MelodyShape.getRerankComparer(this.aOpt, coll); // for 201x-shapetime
		ResultRanker rankerRerank = MelodyShape.getRerankRanker(this.aOpt, coll); // for 201x-shapetime

		this.verbose(2, "done.\n\n");
		this.verbose(2, "  Comparer: " + comparer.getName() + "\n");
		if (this.aOpt.equals("2012-shapetime") || this.aOpt.equals("2013-shapetime") || this.aOpt.equals("2014-shapetime")
				 || this.aOpt.equals("2015-shapetime"))
			this.verbose(2, "    Ranker: " + comparerRerank.getName() + "\n");
		else
			this.verbose(2, "    Ranker: " + ranker.getName() + "\n");
		this.verbose(2, "   Threads: " + this.tOpt + "\n");

		/**
		 * Run Algorithm
		 **/
		for (int queryNum = 0; queryNum < queries.size(); queryNum++) {
			Melody query = queries.get(queryNum);

			this.verbose(1, "(" + (queryNum + 1) + "/" + queries.size() + ") " + query.getId() + "...");
			this.verbose(2, "(" + (queryNum + 1) + "/" + queries.size() + ") " + query.getId() + ":");

			long before = System.currentTimeMillis();
			Result[] results = MelodyShape.runAlgorithm(comparer, comparerRerank, ranker, rankerRerank, this.kOpt,
					queries, queryNum, coll, this.tOpt, this);
			long after = System.currentTimeMillis();

			this.verbose(1, "done.\n");
			this.verbose(2, "done (" + (after - before) / 1000 + " sec).\n");

			this.printResults(queries, queryNum, results);
		}
	}

	protected boolean parseArguments() {
		CommandLineParser parser = new DefaultParser();

		// help? Cannot wait to parse args because it will throw exception
		// before
		for (String arg : this.args)
			if (arg.equals("-h")) {
				this.hOpt = true;
				return true;
			}
		try {
			CommandLine cmd = parser.parse(options, args);

			// query
			this.qOpt = new File(cmd.getOptionValue("q"));
			if (!this.qOpt.exists()) {
				System.err.println("Error: query file does not exist: '" + cmd.getOptionValue("q") + "'");
				return false;
			}
			// documents
			this.cOpt = new File(cmd.getOptionValue("c"));
			if (!this.cOpt.exists() || !this.cOpt.isDirectory()) {
				System.err.println("Error: documents directory does not exist: '" + cmd.getOptionValue("c") + "'");
				return false;
			}
			// algorithm
			this.aOpt = cmd.getOptionValue("a");
			if (!MelodyShape.ALGORITHMS.contains(this.aOpt)) {
				System.err.println("Error: invalid algorithm name: '" + cmd.getOptionValue("a") + "'");
				return false;
			}
			// single-line
			if (cmd.hasOption("l"))
				this.lOpt = true;
			// threads
			if (cmd.hasOption("t")) {
				try {
					int tOptArg = Integer.parseInt(cmd.getOptionValue("t"));
					if (tOptArg < 1) {
						System.err.println("Error: invalid number ot threads: '" + cmd.getOptionValue("t") + "'");
						return false;
					}
					this.tOpt = tOptArg;
				} catch (NumberFormatException ex) {
					System.err.println("Error: invalid number ot threads: '" + cmd.getOptionValue("t") + "'");
					return false;
				}
			}
			// cutoff
			if (cmd.hasOption("k")) {
				try {
					this.kOpt = Integer.parseInt(cmd.getOptionValue("k"));
					if (this.kOpt < 1) {
						System.err.println("Error: invalid cutoff k: '" + kOpt + "'");
						return false;
					}
				} catch (NumberFormatException ex) {
					System.err.println("Error: invalid cutoff k: '" + cmd.getOptionValue("k") + "'");
					return false;
				}
			}
			// verbose
			if (cmd.hasOption("v"))
				this.vOpt = 1;
			if (cmd.hasOption("vv"))
				this.vOpt = 2;

			return true;
		} catch (ParseException e) {
			System.err.println(e.getMessage());
			this.printUsage(options);
			return false;
		}
	}

	protected void printResults(ArrayList<Melody> queries, int queryIndex, Result[] results) {
		for (int k = 0; k < this.kOpt && k < results.length; k++) {
			Result res = results[k];
			if (queries.size() == 1) {
				// just one query, don't output query ID
				if (this.lOpt)
					if (k + 1 < this.kOpt && k + 1 < results.length)
						System.out.print(res.getMelody().getId() + "\t");
					else
						System.out.println(res.getMelody().getId());
				else
					System.out.println(res.getMelody().getId() + "\t"
							+ String.format(Locale.ENGLISH, "%.8f", res.getScore()));
			} else {
				// several queries, output query IDs
				if (this.lOpt) {
					if (k == 0)
						System.out.print(queries.get(queryIndex).getId() + "\t");
					if (k + 1 < this.kOpt && k + 1 < results.length)
						System.out.print(res.getMelody().getId() + "\t");
					else
						System.out.println(res.getMelody().getId());
				} else
					System.out.println(queries.get(queryIndex).getId() + "\t" + res.getMelody().getId() + "\t"
							+ String.format(Locale.ENGLISH, "%.8f", res.getScore()));
			}
		}
	}

	protected void verbose(int level, String msg) {
		if (this.vOpt == level)
			System.err.print(msg);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void updateProgressComparer(Melody query, int numQuery, int totalQueries, double progress) {
		int width = 40;
		StringBuilder sb = new StringBuilder("\r");
		sb.append("(" + (numQuery + 1) + "/" + totalQueries + ") " + query.getId() + ": [");
		int done = (int) (width * progress);
		int pending = width - done;
		for (int i = 0; i < done; i++)
			sb.append("=");
		if (pending > 0)
			sb.append(">");
		for (int i = 1; i < pending; i++)
			sb.append(" ");
		sb.append("] " + String.format("%3s", (int) (100 * progress)) + "% comparing...");
		this.verbose(2, sb.toString());
	}

	/**
	 * {@inheritDoc}
	 */

	@Override
	public void updateStartRanker(Melody query, int numQuery, int totalQueries) {
		this.verbose(2, "ranking...");
	}

	/**
	 * Prints the usage message to stderr.
	 * 
	 * @param options
	 *            the command line options.
	 */
	protected void printUsage(Options options) {
		HelpFormatter formatter = new HelpFormatter();
		formatter.setOptionComparator(new Comparator<Option>() {
			public int compare(Option o1, Option o2) {
				List<String> options = Arrays.asList("q", "c", "a", "k", "l", "t", "v", "vv", "gui", "h");

				return Integer.compare(options.indexOf(o1.getOpt()), options.indexOf(o2.getOpt()));
			}
		});
		formatter.printHelp(new PrintWriter(System.err, true), Integer.MAX_VALUE, "melodyshape-" + MelodyShape.VERSION,
				null, options, 0, 2, "\n" + MelodyShape.COPYRIGHT_NOTICE, true);
	}
}
 @SuppressWarnings("serial")
public class GraphicalUIObserver extends JFrame implements UIObserver {
	protected JTextField textFieldCutoff;
	protected JTextField textFieldQueries;
	protected JTextField textFieldCollection;
	protected JButton btnRun;
	protected JProgressBar progressBarQuery;
	protected JProgressBar progressBarOverall;
	protected JButton btnBrowseQueries;
	protected JButton btnBrowseCollection;
	protected JComboBox<String> comboBoxAlgorithms;
	protected JComboBox<Integer> comboBoxThreads;
	protected JCheckBox chckbxCutoff;
	protected JCheckBox chckbxSingleLineMode;

	protected JFileChooser chooser;
	protected boolean running;
	protected Thread thread;
	protected ArrayList<Melody> queries;
	protected MelodyCollection coll;
	protected JLabel lblStatus;
	protected JTextArea textAreaResults;
	protected JScrollPane scrollPane;
	protected JPopupMenu popupMenu;
	protected JMenuItem mntmCopyAll;
	protected JMenuItem mntmNewMenuItem;

	/**
	 * Constructs a new {@code GraphicalUIObserver}.
	 */
	public GraphicalUIObserver() {
		setResizable(false);
		setTitle("MelodyShape v" + MelodyShape.VERSION);
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

		btnRun = new JButton("Run");
		this.btnRun.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				synchronized (btnRun) {
					if (running) {
						thread.interrupt();
						thread = null;

						lblStatus.setText("Execution interrupted");
						btnRun.setText("Run");
						// enable gui
						btnBrowseQueries.setEnabled(true);
						textFieldQueries.setEnabled(true);
						btnBrowseCollection.setEnabled(true);
						textFieldCollection.setEnabled(true);
						comboBoxAlgorithms.setEnabled(true);
						comboBoxThreads.setEnabled(true);
						chckbxCutoff.setEnabled(true);
						textFieldCutoff.setEnabled(chckbxCutoff.isSelected());
						chckbxCutoff.setEnabled(true);
						chckbxSingleLineMode.setEnabled(true);
						running = false;
					} else {
						textAreaResults.setText("");
						progressBarQuery.setValue(0);
						progressBarOverall.setValue(0);

						btnRun.setText("Stop");

						running = true;
						// disable gui
						btnBrowseQueries.setEnabled(false);
						textFieldQueries.setEnabled(false);
						btnBrowseCollection.setEnabled(false);
						textFieldCollection.setEnabled(false);
						comboBoxAlgorithms.setEnabled(false);
						comboBoxThreads.setEnabled(false);
						chckbxCutoff.setEnabled(false);
						textFieldCutoff.setEnabled(false);
						chckbxCutoff.setEnabled(false);
						chckbxSingleLineMode.setEnabled(false);

						thread = new Thread() {
							@Override
							public void run() {								
								int kOpt = chckbxCutoff.isSelected() ? Integer.parseInt(textFieldCutoff.getText())
										: Integer.MAX_VALUE;
								
								String aOpt = comboBoxAlgorithms.getSelectedItem().toString();
								MelodyComparer comparer = MelodyShape.getMainComparer(aOpt, coll);
								ResultRanker ranker = MelodyShape.getMainRanker(aOpt, coll);
								MelodyComparer comparerRerank = MelodyShape.getRerankComparer(aOpt, coll); // for 201x-shapetime
								ResultRanker rankerRerank = MelodyShape.getRerankRanker(aOpt, coll); // for 201x-shapetime
								
								try {
									for (int queryNum = 0; queryNum < queries.size(); queryNum++) {
										Melody query = queries.get(queryNum);
										// run
										lblStatus.setText("(" + (queryNum + 1) + "/" + queries.size() + ") "
												+ query.getId() + "...");
										Result[] results = MelodyShape.runAlgorithm(comparer, comparerRerank, ranker,
												rankerRerank, kOpt, queries, queryNum, coll,
												comboBoxThreads.getSelectedIndex() + 1, GraphicalUIObserver.this);
										lblStatus.setText("(" + (queryNum + 1) + "/" + queries.size() + ") "
												+ query.getId() + "...done.");
										// print results
										StringBuffer text = new StringBuffer();
										for (int k = 0; k < kOpt && k < results.length; k++) {
											Result res = results[k];
											if (queries.size() == 1) {
												// just one query, don't output
												// query ID
												if (chckbxSingleLineMode.isSelected())
													if (k + 1 < kOpt && k + 1 < results.length)
														text.append(res.getMelody().getId() + "\t");
													else
														text.append(res.getMelody().getId() + "\n");
												else
													text.append(res.getMelody().getId() + "\t"
															+ String.format(Locale.ENGLISH, "%.8f", res.getScore())
															+ "\n");
											} else {
												// several queries, output query
												// IDs
												if (chckbxSingleLineMode.isSelected()) {
													if (k == 0)
														text.append(queries.get(queryNum).getId() + "\t");
													if (k + 1 < kOpt && k + 1 < results.length)
														text.append(res.getMelody().getId() + "\t");
													else
														text.append(res.getMelody().getId() + "\n");
												} else
													text.append(queries.get(queryNum).getId() + "\t"
															+ res.getMelody().getId() + "\t"
															+ String.format(Locale.ENGLISH, "%.8f", res.getScore())
															+ "\n");
											}
										}
										textAreaResults.setText(textAreaResults.getText() + text.toString());
									}
								} catch (Exception ex) {
									lblStatus.setText("Execution interrupted");
								} finally {
									synchronized (btnRun) {
										thread = null;

										// enable gui
										btnBrowseQueries.setEnabled(true);
										textFieldQueries.setEnabled(true);
										btnBrowseCollection.setEnabled(true);
										textFieldCollection.setEnabled(true);
										comboBoxAlgorithms.setEnabled(true);
										comboBoxThreads.setEnabled(true);
										chckbxCutoff.setEnabled(true);
										textFieldCutoff.setEnabled(chckbxCutoff.isSelected());
										chckbxCutoff.setEnabled(true);
										chckbxSingleLineMode.setEnabled(true);
										btnRun.setText("Run");
										running = false;
									}
								}
							}
						};
						thread.start();
					}
				}
			}
		});
		btnRun.setEnabled(false);
		btnRun.setBounds(335, 148, 89, 47);
		getContentPane().setLayout(null);

		JLabel lblQueryProgress = new JLabel("Query progress:");
		lblQueryProgress.setBounds(12, 151, 98, 14);
		lblQueryProgress.setHorizontalAlignment(SwingConstants.RIGHT);
		getContentPane().add(lblQueryProgress);

		progressBarQuery = new JProgressBar();
		progressBarQuery.setStringPainted(true);
		progressBarQuery.setBounds(120, 148, 203, 21);
		getContentPane().add(progressBarQuery);
		getContentPane().add(btnRun);

		JLabel lblOverallProgress = new JLabel("Overall progress:");
		lblOverallProgress.setBounds(12, 176, 98, 16);
		lblOverallProgress.setHorizontalAlignment(SwingConstants.RIGHT);
		getContentPane().add(lblOverallProgress);

		progressBarOverall = new JProgressBar();
		progressBarOverall.setStringPainted(true);
		progressBarOverall.setBounds(120, 174, 203, 21);
		getContentPane().add(progressBarOverall);

		textFieldQueries = new JTextField();
		textFieldQueries.setEditable(false);
		textFieldQueries.setEnabled(false);
		textFieldQueries.setBounds(80, 13, 250, 20);
		getContentPane().add(textFieldQueries);
		textFieldQueries.setColumns(10);

		JLabel lblQueryFile = new JLabel("Queries:");
		lblQueryFile.setHorizontalAlignment(SwingConstants.RIGHT);
		lblQueryFile.setBounds(12, 16, 59, 14);
		getContentPane().add(lblQueryFile);

		JLabel lblCollection = new JLabel("Collection:");
		lblCollection.setHorizontalAlignment(SwingConstants.RIGHT);
		lblCollection.setBounds(12, 43, 59, 16);
		getContentPane().add(lblCollection);

		textFieldCollection = new JTextField();
		textFieldCollection.setEnabled(false);
		textFieldCollection.setEditable(false);
		textFieldCollection.setBounds(80, 41, 250, 20);
		getContentPane().add(textFieldCollection);
		textFieldCollection.setColumns(10);

		btnBrowseQueries = new JButton("Browse...");
		btnBrowseQueries.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				chooser.setMultiSelectionEnabled(true);
				chooser.setFileSelectionMode(JFileChooser.FILES_ONLY);
				chooser.setFileFilter(new FileFilter() {
					@Override
					public String getDescription() {
						return "MIDI files (*.mid;*.midi)";
					}

					@Override
					public boolean accept(File f) {
						if (f.isDirectory())
							return true;
						return f.getName().toLowerCase().endsWith(".mid")
								|| f.getName().toLowerCase().endsWith(".midi");
					}
				});
				int ret = chooser.showOpenDialog(GraphicalUIObserver.this);
				if (ret == JFileChooser.APPROVE_OPTION) {
					File[] files = chooser.getSelectedFiles();

					try {
						lblStatus.setText("Reading queries...");
						ArrayList<Melody> newqueries = new ArrayList<Melody>();
						StringBuffer text = new StringBuffer();
						for (File file : files) {
							text.append(";");
							text.append(file.getName());
							Melody query = MelodyShape.readQueries(file).get(0);
							newqueries.add(query);
						}
						lblStatus.setText("Reading queries... " + newqueries.size() + " read.");

						textFieldQueries.setText(text.deleteCharAt(0).toString());
						queries = newqueries;

						textFieldQueries.setEnabled(true);
						btnBrowseCollection.setEnabled(true);
					} catch (IllegalArgumentException ex) {
						if (queries == null) {
							textFieldQueries.setEnabled(false);
							btnBrowseCollection.setEnabled(false);
						}
						lblStatus.setText("Error reading queries.");
						JOptionPane.showMessageDialog(GraphicalUIObserver.this, ex.getMessage(), "Invalid query file",
								JOptionPane.ERROR_MESSAGE);
					}
				}
			}
		});
		btnBrowseQueries.setEnabled(false);
		btnBrowseQueries.setBounds(335, 12, 89, 23);
		getContentPane().add(btnBrowseQueries);

		btnBrowseCollection = new JButton("Browse...");
		this.btnBrowseCollection.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				chooser.setMultiSelectionEnabled(false);
				chooser.setFileFilter(null);
				chooser.setFileSelectionMode(JFileChooser.DIRECTORIES_ONLY);
				int ret = chooser.showOpenDialog(GraphicalUIObserver.this);
				if (ret == JFileChooser.APPROVE_OPTION) {
					try {
						lblStatus.setText("Reading documents...");
						MelodyCollection newcoll = MelodyShape.readCollection(chooser.getSelectedFile());
						if (newcoll.size() == 0)
							throw new IllegalArgumentException("No MIDI files in the directory.");
						lblStatus.setText("Reading documents... " + newcoll.size() + " read.");

						textFieldCollection.setText(chooser.getSelectedFile().getName());
						coll = newcoll;

						textFieldCollection.setEnabled(true);
						comboBoxAlgorithms.setEnabled(true);
						comboBoxThreads.setEnabled(true);
						chckbxCutoff.setEnabled(true);
						textFieldCutoff.setEditable(chckbxCutoff.isSelected());
						chckbxSingleLineMode.setEnabled(true);
						btnRun.setEnabled(true);
					} catch (IllegalArgumentException ex) {
						lblStatus.setText("Error reading documents.");
						if (coll == null) {
							textFieldCollection.setEnabled(false);
							comboBoxAlgorithms.setEnabled(false);
							comboBoxThreads.setEnabled(false);
							chckbxCutoff.setEnabled(false);
							textFieldCutoff.setEditable(false);
							chckbxSingleLineMode.setEnabled(false);
							btnRun.setEnabled(false);
						}
						JOptionPane.showMessageDialog(GraphicalUIObserver.this, ex.getMessage(),
								"Invalid collection directory", JOptionPane.ERROR_MESSAGE);
					}
				}
			}
		});
		btnBrowseCollection.setEnabled(false);
		btnBrowseCollection.setBounds(335, 40, 89, 23);
		getContentPane().add(btnBrowseCollection);

		JPanel panelOptions = new JPanel();
		panelOptions.setBorder(new TitledBorder(null, "Options", TitledBorder.LEADING, TitledBorder.TOP, null, null));
		panelOptions.setBounds(12, 65, 412, 75);
		getContentPane().add(panelOptions);
		panelOptions.setLayout(null);

		JLabel lblAlgorithm = new JLabel("Algorithm:");
		lblAlgorithm.setBounds(10, 22, 58, 16);
		panelOptions.add(lblAlgorithm);
		lblAlgorithm.setHorizontalAlignment(SwingConstants.RIGHT);

		comboBoxAlgorithms = new JComboBox<String>();
		comboBoxAlgorithms.setEnabled(false);
		comboBoxAlgorithms.setBounds(73, 20, 127, 20);
		panelOptions.add(comboBoxAlgorithms);

		JLabel lblThreads = new JLabel("Threads:");
		lblThreads.setHorizontalAlignment(SwingConstants.RIGHT);
		lblThreads.setBounds(10, 50, 58, 14);
		panelOptions.add(lblThreads);

		comboBoxThreads = new JComboBox<Integer>();
		comboBoxThreads.setEnabled(false);
		comboBoxThreads.setBounds(73, 47, 127, 20);
		panelOptions.add(comboBoxThreads);

		chckbxCutoff = new JCheckBox("Cutoff:");
		this.chckbxCutoff.setSelected(true);
		chckbxCutoff.setEnabled(false);
		chckbxCutoff.addChangeListener(new ChangeListener() {
			public void stateChanged(ChangeEvent arg0) {
				JCheckBox cb = (JCheckBox) arg0.getSource();
				if (cb.isSelected()) {
					textFieldCutoff.setEnabled(true);
				} else {
					textFieldCutoff.setEnabled(false);
				}
			}
		});
		chckbxCutoff.setHorizontalAlignment(SwingConstants.LEFT);
		chckbxCutoff.setBounds(208, 18, 62, 24);
		panelOptions.add(chckbxCutoff);

		textFieldCutoff = new JTextField();
		this.textFieldCutoff.setEnabled(false);
		this.textFieldCutoff.setText("10");
		textFieldCutoff.setBounds(275, 19, 125, 20);
		textFieldCutoff.getDocument().addDocumentListener(new DocumentListener() {
			@Override
			public void removeUpdate(DocumentEvent arg0) {
				check();
			}

			@Override
			public void insertUpdate(DocumentEvent arg0) {
				check();
			}

			@Override
			public void changedUpdate(DocumentEvent arg0) {
				check();
			}

			protected void check() {
				String text = textFieldCutoff.getText();
				try {
					int k = Integer.parseInt(text);
					if (k > 0) {
						btnRun.setEnabled(true);
					} else {
						Toolkit.getDefaultToolkit().beep();
						btnRun.setEnabled(false);
					}
				} catch (NumberFormatException ex) {
					Toolkit.getDefaultToolkit().beep();
					btnRun.setEnabled(false);
				}
			}
		});
		panelOptions.add(textFieldCutoff);

		chckbxSingleLineMode = new JCheckBox("Single line mode");
		chckbxSingleLineMode.setEnabled(false);
		chckbxSingleLineMode.setBounds(208, 43, 118, 24);
		panelOptions.add(chckbxSingleLineMode);

		JPanel panelResults = new JPanel();
		panelResults.setBorder(new TitledBorder(null, "Results", TitledBorder.LEADING, TitledBorder.TOP, null, null));
		panelResults.setBounds(12, 201, 412, 244);
		getContentPane().add(panelResults);
		panelResults.setLayout(null);

		this.scrollPane = new JScrollPane();
		this.scrollPane.setBounds(12, 22, 388, 210);
		panelResults.add(this.scrollPane);

		this.textAreaResults = new JTextArea();
		this.scrollPane.setViewportView(this.textAreaResults);
		this.textAreaResults.setFont(new Font("Courier New", Font.PLAIN, 12));
		this.textAreaResults.setTabSize(4);
		this.textAreaResults.setEditable(false);

		this.popupMenu = new JPopupMenu();
		addPopup(this.textAreaResults, this.popupMenu);

		this.mntmCopyAll = new JMenuItem("Copy All");
		this.mntmCopyAll.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				Toolkit.getDefaultToolkit().getSystemClipboard()
						.setContents(new StringSelection(textAreaResults.getText()), null);
			}
		});
		this.popupMenu.add(this.mntmCopyAll);

		for (String alg : MelodyShape.ALGORITHMS)
			comboBoxAlgorithms.addItem(alg);
		comboBoxAlgorithms.setSelectedIndex(0);
		int maxThreads = Runtime.getRuntime().availableProcessors();
		for (int i = 1; i <= maxThreads; i++)
			comboBoxThreads.addItem(i);
		comboBoxThreads.setSelectedIndex(maxThreads - 1);

		this.lblStatus = new JLabel("Select query files first");
		this.lblStatus.setEnabled(false);
		this.lblStatus.setBounds(12, 450, 353, 14);
		getContentPane().add(this.lblStatus);

		this.mntmNewMenuItem = new JMenuItem("About...");
		this.mntmNewMenuItem.setBounds(370, 449, 54, 21);
		getContentPane().add(this.mntmNewMenuItem);
		this.mntmNewMenuItem.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				JOptionPane.showMessageDialog(GraphicalUIObserver.this, MelodyShape.COPYRIGHT_NOTICE);
			}
		});
	}

	@Override
	public void start() {
		this.queries = null;
		this.coll = null;
		this.chooser = new JFileChooser();
		this.thread = null;
		this.running = false;

		this.setSize(440, 498);
		this.btnBrowseQueries.setEnabled(true);
		this.setVisible(true);
	}

	@Override
	public void updateProgressComparer(Melody query, int numQuery, int totalQueries, double progress) {
		this.progressBarQuery.setValue((int) (progress * 100));
		double overall = ((double) numQuery) / totalQueries;
		overall += progress / totalQueries;
		this.progressBarOverall.setValue((int) (overall * 100));
	}

	@Override
	public void updateStartRanker(Melody query, int numQuery, int totalQueries) {
		// TODO Auto-generated method stub

	}

	private static void addPopup(Component component, final JPopupMenu popup) {
		component.addMouseListener(new MouseAdapter() {
			public void mousePressed(MouseEvent e) {
				if (e.isPopupTrigger()) {
					showMenu(e);
				}
			}

			public void mouseReleased(MouseEvent e) {
				if (e.isPopupTrigger()) {
					showMenu(e);
				}
			}

			private void showMenu(MouseEvent e) {
				popup.show(e.getComponent(), e.getX(), e.getY());
			}
		});
	}
}
 public interface UIObserver {
	/**
	 * Starts execution of the algorithm.
	 */
	public void start();

	/**
	 * Used to notify this {@code UIObserver} of the progress in executing a
	 * {@link MelodyComparer} with a particular query.
	 * 
	 * @param query
	 *            the query running.
	 * @param numQuery
	 *            the number of query running.
	 * @param totalQueries
	 *            the total number of queries to run.
	 * @param progress
	 *            a number indicating the execution progress from 0 (just
	 *            started) to 1 (completed).
	 */
	public void updateProgressComparer(Melody query, int numQuery, int totalQueries, double progress);

	/**
	 * Used to notify this {@code UIObserver} that the {@link MelodyComparer}
	 * just finished and a {@link ResultRanker} is about to start running with a
	 * particular query.
	 * 
	 * @param query
	 *            the query running.
	 * @param numQuery
	 *            the number of query running.
	 * @param totalQueries
	 *            the total number of queries to run.
	 */
	public void updateStartRanker(Melody query, int numQuery, int totalQueries);
}

import jurbano.melodyshape.comparison.*;
import jurbano.melodyshape.comparison.alignment.GlobalAligner;
import jurbano.melodyshape.comparison.alignment.HybridAligner;
import jurbano.melodyshape.comparison.alignment.LocalAligner;
import jurbano.melodyshape.comparison.bspline.BSplinePitchNGramComparer;
import jurbano.melodyshape.comparison.bspline.BSplineShapeNGramComparer;
import jurbano.melodyshape.comparison.bspline.BSplineTimeNGramComparer;
import jurbano.melodyshape.model.*;
import jurbano.melodyshape.ranking.Result;
import jurbano.melodyshape.ranking.ResultRanker;
import jurbano.melodyshape.ranking.UntieResultRanker;
import jurbano.melodyshape.ui.ConsoleUIObserver;
import jurbano.melodyshape.ui.GraphicalUIObserver;
import jurbano.melodyshape.ui.UIObserver;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;

// Copyright (C) 2013, 2015-2016  Julián Urbano <urbano.julian@gmail.com>
// Distributed under the terms of the MIT License.

package jurbano.melodyshape;



/**
 * Main class of the tool. Contains all the logic to read MIDI collections,
 * instantiate and run algorithms. Delegates presentation logic in
 * {@code UIObserver}s.
 * 
 * @author Julián Urbano
 */
public class MelodyShape
{
	/**
	 * Update progress to user interface every so melodies compared.
	 */
	public static int VERBOSE_PERIOD = 50;
	/**
	 * The release version number.
	 */
	public static String VERSION = "1.4";
	/**
	 * The copyright notice, including date and version.
	 */
	public static String COPYRIGHT_NOTICE ="MelodyShape " + MelodyShape.VERSION
			+ "  Copyright (C) 2013-2016  Julian Urbano <urbano.julian@gmail.com>\n"
			+ "This program is distributed under the terms of the MIT License.";
	/**
	 * The list of algorithms available in the release.
	 */
	public static List<String> ALGORITHMS = Arrays.asList("2010-domain", "2010-pitchderiv", "2010-shape", "2011-pitch",
			"2011-time", "2011-shape", "2012-shapeh", "2012-shapel", "2012-shapeg", "2012-time", "2012-shapetime",
			"2013-shapeh", "2013-time", "2013-shapetime",
			"2014-shapeh", "2014-time", "2014-shapetime",
			"2015-shapeh", "2015-time", "2015-shapetime");

	/**
	 * Returns the list of queries found in a path.
	 * 
	 * @param path
	 *            the path to read queries from (a single file or a directory).
	 * @return the list of melodies read.
	 */
	public static ArrayList<Melody> readQueries(File path) {
		MelodyReader reader = new MidiReader();
		ArrayList<Melody> queries = new ArrayList<Melody>();
		if (path.isDirectory()) {
			// query path is a directory, read all files
			for (File qFile : path.listFiles())
				try {
					if (reader.accept(path, qFile.getName()))
						queries.add(reader.read(qFile.getName(), qFile.getAbsolutePath()));
				} catch (IOException ex) {
					throw new IllegalArgumentException("bad format in query file '" + qFile.getAbsolutePath() + "': "
							+ ex.getMessage(), ex);
				}
		} else {
			// query path is a single file
			try {
				queries.add(reader.read(path.getName(), path.getAbsolutePath()));
			} catch (IOException ex) {
				throw new IllegalArgumentException("bad format in query file '" + path.getAbsolutePath() + "': "
						+ ex.getMessage(), ex);
			}
		}
		return queries;
	}

	/**
	 * Returns a melody collection found in a path.
	 *
	 * @param path
	 *            the path to the directory containing all melodies.
	 * @return the melody collection.
	 */
	public static MelodyCollection readCollection(File path) {
		MelodyReader reader = new MidiReader();
		try {
			return new InMemoryMelodyCollection(path.getName(), path.getAbsolutePath(), reader);
		} catch (IOException ex) {
			throw new IllegalArgumentException(ex.getMessage());
		}
	}

	/**
	 * Returns a melody main comparer given its name.
	 * 
	 * @param name
	 *            the name of the melody main comparer.
	 * @param coll
	 *            the collection of melodies to use with the comparer.
	 * @return the melody main comparer.
	 */
	public static MelodyComparer getMainComparer(String name, MelodyCollection coll) {
		if (Arrays.asList("2010-domain").contains(name))
			return new NGramMelodyComparer(3, new HybridAligner(new FrequencyNGramComparer(coll, 3,
					new IntervalPitchNGramComparer()))); // faster without cache
		else if (Arrays.asList("2010-pitchderiv").contains(name))
			return new NGramMelodyComparer(3, new HybridAligner(new CachedNGramComparer(new FrequencyNGramComparer(
					coll, 3, new BSplinePitchNGramComparer()))));
		else if (Arrays.asList("2010-shape", "2011-shape", "2012-shapeh", "2013-shapeh", "2014-shapeh", "2015-shapeh",
				"2012-shapetime", "2013-shapetime", "2014-shapetime", "2015-shapetime").contains(name))
			return new NGramMelodyComparer(3, new HybridAligner(new CachedNGramComparer(new FrequencyNGramComparer(
					coll, 3, new BSplineShapeNGramComparer(8, 1, 0.5)))));
		else if (Arrays.asList("2011-pitch").contains(name))
			return new NGramMelodyComparer(4, new HybridAligner(new CachedNGramComparer(new CombinedNGramComparer(
					new BSplinePitchNGramComparer(), 1, 2.1838, new BSplineTimeNGramComparer(), 0, 0.4772))));
		else if (Arrays.asList("2011-time", "2012-time", "2013-time", "2014-time", "2015-time").contains(name))
			return new NGramMelodyComparer(4, new HybridAligner(new CachedNGramComparer(new CombinedNGramComparer(
					new BSplinePitchNGramComparer(), 1, 2.1838, new BSplineTimeNGramComparer(), 0.5, 0.4772))));
		else if (Arrays.asList("2012-shapel").contains(name))
			return new NGramMelodyComparer(3, new LocalAligner(new CachedNGramComparer(new FrequencyNGramComparer(coll,
					3, new BSplineShapeNGramComparer(8, 1, 0.5)))));
		else if (Arrays.asList("2012-shapeg").contains(name))
			return new NGramMelodyComparer(3, new GlobalAligner(new CachedNGramComparer(new FrequencyNGramComparer(
					coll, 3, new BSplineShapeNGramComparer(8, 1, 0.5)))));
		else
			throw new IllegalArgumentException("unrecognized algorithm name: '" + name + "'");
	}

	/**
	 * Returns a results main ranker given its name.
	 * 
	 * @param name
	 *            the name of the results main ranker.
	 * @param coll
	 *            the collection of melodies to compare.
	 * 
	 * @return the results main ranker.
	 */
	public static ResultRanker getMainRanker(String name, MelodyCollection coll) {
		if (Arrays.asList("2010-domain", "2010-pitchderiv", "2010-shape", "2011-shape", "2012-shapeh", "2012-shapel",
				"2012-shapeg", "2012-shapetime", "2013-shapeh", "2013-shapetime", "2014-shapeh", "2014-shapetime",
				"2015-shapeh", "2015-shapetime").contains(name))
			return new UntieResultRanker(new NGramMelodyComparer(3, new HybridAligner(new EqualPitchNGramComparer())));
		else if(Arrays.asList("2011-pitch", "2011-time", "2012-time", "2013-time", "2014-time", "2015-time").contains(name))
			return new UntieResultRanker(new NGramMelodyComparer(4, new HybridAligner(new EqualPitchNGramComparer())));
		else
			throw new IllegalArgumentException("unrecognized algorithm name: '" + name + "'");
	}
	
	/**
	 * Returns a melody re-rank comparer given its name (for 201x-shapetime algorithms).
	 * 
	 * @param name
	 *            the name of the melody re-rank comparer.
	 * @param coll
	 *            the collection of melodies to use with the comparer.
	 * @return the melody re-rank comparer or {@code null} if the comparer does not re-rank.
	 */
	public static MelodyComparer getRerankComparer(String name, MelodyCollection coll) {
		if (Arrays.asList("2012-shapetime", "2013-shapetime", "2014-shapetime", "2015-shapetime").contains(name))
			return new NGramMelodyComparer(4, new HybridAligner(new CachedNGramComparer(new CombinedNGramComparer(
					new BSplinePitchNGramComparer(), 1, 2.1838, new BSplineTimeNGramComparer(), 0.5, 0.4772))));
		else
			return null;
	}
	
	/**
	 * Returns a results re-rank ranker given its name (for 201x-shapetime algorithms).
	 * 
	 * @param name
	 *            the name of the results re-rank ranker.
	 * @param coll
	 *            the collection of melodies to compare.
	 * 
	 * @return the results re-rank ranker or {@code null} if the comparer does not re-rank.
	 */
	public static ResultRanker getRerankRanker(String name, MelodyCollection coll) {
		if (Arrays.asList("2012-shapetime", "2013-shapetime", "2014-shapetime", "2015-shapetime").contains(name))
			return new UntieResultRanker(new NGramMelodyComparer(3, new HybridAligner(new EqualPitchNGramComparer())));
		else
			return null;
	}

		
	/**
	 * Runs an algorithm (comparer and ranker) as specified.
	 * 
	 * @param melodyCmp
	 *            the base melody comparer.
	 * @param melodyCmpRerank
	 *            the melody comparer to rerank, or {@code null} if no reranking
	 *            is needed.
	 * @param ranker
	 *            the base results ranker.
	 * @param rankerRerank
	 *            the results ranker to rerank, or {@code null} if no reranking
	 *            is needed.
	 * @param kOpt
	 *            the cutoff.
	 * @param queries
	 *            the list of queries.
	 * @param numQuery
	 *            the index of the particular query to run.
	 * @param coll
	 *            the collection of melodies to compare with the query.
	 * @param tOpt
	 *            the number of threads to use.
	 * @param observer
	 *            the user interface observer to notify changes.
	 * @return the ranked list of results.
	 */
	public static Result[] runAlgorithm(MelodyComparer melodyCmp, MelodyComparer melodyCmpRerank, ResultRanker ranker,

			ResultRanker rankerRerank, int kOpt, ArrayList<Melody> queries, int numQuery, MelodyCollection coll, int tOpt, UIObserver observer){		
