// Path: src/jurbano/melodyshape/comparison/MelodyComparer.java
// public interface MelodyComparer
// {
// 	/**
// 	 * Gets the name of this {@code MelodyComparer}
// 	 * 
// 	 * @return the name of the melody comparer.
// 	 */
// 	public String getName();
// 	
// 	/**
// 	 * Computes a similarity score between two melodies.
// 	 * <p>
// 	 * The similarity score is proportional to the melodic similarity between
// 	 * the melodies, that is {@code compare(m1, m2) > compare(m1, m3)} means
// 	 * that melody {@code m2} is more similar to {@code m1} than {@code m3} is.
// 	 * 
// 	 * @param m1
// 	 *            the first melody to compare.
// 	 * @param m2
// 	 *            the second melody to compare.
// 	 * @return the similarity score.
// 	 */
// 	public double compare(Melody m1, Melody m2);
// }
// 
// Path: src/jurbano/melodyshape/model/Melody.java
// @SuppressWarnings("serial")
// public class Melody extends ArrayList<Note>
// {
// 	protected String id;
// 	
// 	/**
// 	 * Gets the unique ID of the melody.
// 	 * 
// 	 * @return the ID of the melody.
// 	 */
// 	public String getId() {
// 		return this.id;
// 	}
// 	
// 	/**
// 	 * Constructs a new and empty {@code Melody} object.
// 	 * 
// 	 * @param id
// 	 *            the unique ID of the melody.
// 	 */
// 	public Melody(String id) {
// 		this.id = id;
// 	}
// 	
// 	@Override
// 	public String toString() {
// 		return "Melody [id=" + id + ", size=" + this.size() + "]";
// 	}
// }


import java.util.Arrays;
import java.util.Comparator;
import jurbano.melodyshape.comparison.MelodyComparer;
import jurbano.melodyshape.model.Melody;

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

package jurbano.melodyshape.ranking;



/**
 * A ranking function that sorts by decreasing similarity score, then by
 * decreasing similarity according to a second {@link MelodyComparer}, then by
 * increasing difference in length with the query, and then by melody
 * identifier.
 * 
 * @author Julián Urbano
 * @see ResultRanker
 */
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())

// Path: src/jurbano/melodyshape/comparison/MelodyComparer.java
// public interface MelodyComparer
// {
// 	/**
// 	 * Gets the name of this {@code MelodyComparer}
// 	 * 
// 	 * @return the name of the melody comparer.
// 	 */
// 	public String getName();
// 	
// 	/**
// 	 * Computes a similarity score between two melodies.
// 	 * <p>
// 	 * The similarity score is proportional to the melodic similarity between
// 	 * the melodies, that is {@code compare(m1, m2) > compare(m1, m3)} means
// 	 * that melody {@code m2} is more similar to {@code m1} than {@code m3} is.
// 	 * 
// 	 * @param m1
// 	 *            the first melody to compare.
// 	 * @param m2
// 	 *            the second melody to compare.
// 	 * @return the similarity score.
// 	 */
// 	public double compare(Melody m1, Melody m2);
// }
// 
// Path: src/jurbano/melodyshape/model/Melody.java
// @SuppressWarnings("serial")
// public class Melody extends ArrayList<Note>
// {
// 	protected String id;
// 	
// 	/**
// 	 * Gets the unique ID of the melody.
// 	 * 
// 	 * @return the ID of the melody.
// 	 */
// 	public String getId() {
// 		return this.id;
// 	}
// 	
// 	/**
// 	 * Constructs a new and empty {@code Melody} object.
// 	 * 
// 	 * @param id
// 	 *            the unique ID of the melody.
// 	 */
// 	public Melody(String id) {
// 		this.id = id;
// 	}
// 	
// 	@Override
// 	public String toString() {
// 		return "Melody [id=" + id + ", size=" + this.size() + "]";
// 	}
// }


// Path: src/jurbano/melodyshape/ranking/UntieResultRanker.java
import java.util.Arrays;
import java.util.Comparator;
import jurbano.melodyshape.comparison.MelodyComparer;
import jurbano.melodyshape.model.Melody;

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

package jurbano.melodyshape.ranking;



/**
 * A ranking function that sorts by decreasing similarity score, then by
 * decreasing similarity according to a second {@link MelodyComparer}, then by
 * increasing difference in length with the query, and then by melody
 * identifier.
 * 
 * @author Julián Urbano
 * @see ResultRanker
 */
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()),
