/*
 * QueueList.java
 *
 * ...
 * ...
 * @author Oystein Reigem
 */

package aksis.alignment;

import java.awt.Color;
import java.util.*;
import java.io.*;
import java.util.regex.*;
import javax.swing.*;
import java.awt.event.MouseEvent;
import java.lang.reflect.*;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.FactoryConfigurationError;
import javax.xml.parsers.ParserConfigurationException;
import org.w3c.dom.*;

class PathStep implements Cloneable {

	int[] increment = new int[Alignment.NUM_FILES];

	public PathStep() {
	}

	public PathStep(int[] inc) {
		increment = inc;
	}

	public boolean is11() {
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			if (increment[t] != 1) {
				return false;
			}
		}
		return true;
	}

	public String toString() {
		String temp = "{";
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			if (t>0) { temp += ","; }
			temp += Integer.toString(increment[t]);
		}
		temp += "}";
		return temp;
	}

    public Object clone() {

        try {
			// first make exact bitwise copy
			PathStep copy = (PathStep)super.clone();
			// a new array of int is created
			copy.increment = new int[Alignment.NUM_FILES];
			// then copy over the int values
			for (int t=0; t<Alignment.NUM_FILES; t++) {
				copy.increment[t] = increment[t];
			}
			return copy;
        } catch (CloneNotSupportedException e) {
            throw new Error("This should not occur since we implement Cloneable");
        }

	}

}

//class Path {
class Path implements Cloneable {

	// a list of PathStep objects...
	List<PathStep> steps = new ArrayList<PathStep>();
	// ...leading to this position
	// ############# 2005-11-02.
	// the position is meant to be absolute, i.e, the actual position in the texts.
	// but there seems to be some confusion. one or more places in the app treats position as relative.
	// tries to fix that now.
	// ############### false alarm!? but i though i saw relative values from println
	int[] position = new int[Alignment.NUM_FILES];
	// but path object contains no explicit info about which position the path starts

	// ### only meant to be used when we need a copy of a path.
	// clunky way to get a copy?
	public Path() {
		//System.out.println("Path() constructor");
	}

	public Path(int[] initialPosition) {
		//¤//System.out.println("Path(int[] initialPosition) constructor. initialPosition=" + initialPosition[0] + "," + initialPosition[1]);
		position = initialPosition;
	}

	public boolean equals(Path path) {
		// ####### dodgy?
		return (this.toString().equals(path.toString()));
	}

	public void extend(PathStep step) {
		//steps.add(step);
		//System.out.println("før steps.add(). steps.size() = " + steps.size());
		//System.out.println("skal adde steg " + step);
		steps.add((PathStep)step.clone());   // §§§ dette må vel være riktigere
		//System.out.println("etter steps.add(). steps.size() = " + steps.size());
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			position[t] += step.increment[t];
		}
	}

	public String toString() {
		String temp = "[";
		Iterator it = steps.iterator();
		boolean first = true;
		while (it.hasNext()) {
			if (!first) { temp += ", "; }
			PathStep step = (PathStep)it.next();
			temp += "{";
			for (int t=0; t<Alignment.NUM_FILES; t++) {
				if (t > 0) { temp += ","; }
				temp += Integer.toString(step.increment[t]);
			}
			temp += "}";
			first = false;
		}
		temp += "]->";
		temp += "{";
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			if (t > 0) { temp += ","; }
			temp += position[t];
		}
		temp += "}";
		return temp;
	}

	// ¤¤¤ brukes visst ikke av clone()
	public List getSteps(){
		return steps;
	}

	// brukes av clone()
	public void setSteps(List<PathStep> steps){
		this.steps = steps;
	}

    public Object clone() {

        try {
			// first make exact bitwise copy
			Path copy = (Path)super.clone();
			// a new arraylist of PathStep objects is created
			copy.steps = new ArrayList<PathStep>();
			// then copies of the original's PathStep objects are added
			Iterator it = steps.iterator();
			while (it.hasNext()) {
				PathStep stepCopy = (PathStep)((PathStep)it.next()).clone();   // PathStep has its own deep copy
				copy.steps.add(stepCopy);
			}
			// a new array of int is created
			copy.position = new int[Alignment.NUM_FILES];
			// then the int values are set
			for (int t=0; t<Alignment.NUM_FILES; t++) {
				copy.position[t] = position[t];
			}
			return copy;
        } catch (CloneNotSupportedException e) {
            throw new Error("This should not occur since we implement Cloneable");
        }

	}

    public int getLengthInSentences() {
		// the number of sentences in the path, counting in both texts
		int count = 0;
		Iterator it = steps.iterator();
		while (it.hasNext()) {
			PathStep step = (PathStep)it.next();
			for (int t=0; t<Alignment.NUM_FILES; t++) {
				count += step.increment[t];
			}
		}
		//System.out.println(">>> getLengthInSentences teller " + count + " setninger");
		return count;
	}

}

//class QueueEntry {
class QueueEntry implements Cloneable {

	Path path;   // a path of steps leading to a position
	float score = 0.f;   // the score for the path
	////String scoreHistory = "";   // ¤¤¤ foreløpig
	boolean removed = false;   // ...
	boolean end = false;   // if the path reaches the end of (all) the texts

	/*
	 * make queue entry with initial path
	 * #### skal klassen heller selv vite hvordan det første steget skal se ut? dvs -1, -1, med score 0
	 */
	QueueEntry(int[] position, float score) {
		//¤//System.out.println("QueueEntry(position, score) constructor. position=" + position[0] + "," + position[1] + ". score=" + score);
		path = new Path(position);
		//System.out.println("position -> path = " + path);
		this.score = score;
		//System.out.println("score = " + score);
		////scoreHistory = "Initiell score " + Integer.toString(score) + ". ";
		removed = false;   // 2005-11-01 aner ikke om vits i
		end = false;
	}

    /*
    // ### shallow clone. useless
    public Object clone() {
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            throw new Error("This should not occur since we implement Cloneable");
        }
    }
    */

    /*
    // <http://www.jguru.com/faq/view.jsp?EID=20435>
    // Assuming everything is serializable,   §§§ men det er det ikke. arrays (og ArrayList's) er ikke serializable
    // the following should create a complete deep copy
    // of the current class instance:
    public Object clone() {
		try {
			System.out.println("1");
			ByteArrayOutputStream baos = new ByteArrayOutputStream();
			System.out.println("2");
			ObjectOutputStream oos = new ObjectOutputStream(baos);
			System.out.println("3");
			oos.writeObject(this);
			System.out.println("4");
			ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
			System.out.println("5");
			ObjectInputStream ois = new ObjectInputStream(bais);
			System.out.println("6");
			try {
				Object deepCopy = ois.readObject();
				return deepCopy;
			} catch (ClassNotFoundException e) {
				System.out.println("*** ClassNotFoundException in QueueEntry clone() method");
				return null;
			}
		} catch (IOException e) {
			System.out.println("*** IOException in QueueEntry clone() method");
			return null;
		}
	}
	*/

	// ¤¤¤ brukes visst ikke av clone()
	public Path getPath(){
		return path;
	}

	// brukes av clone()

	public void setPath(Path path){
		this.path = path;
	}

    public Object clone() {

        try {
			// first make exact bitwise copy
			QueueEntry copy = (QueueEntry)super.clone();
			// then copy the path
			copy.path = (Path)path.clone();   // Path has its own clone() method
			return copy;
        } catch (CloneNotSupportedException e) {
            throw new Error("This should not occur since we implement Cloneable");
        }

    }

	/*
	 * make a new queue entry with equal content to an existing entry,
	 * but with path extended with a particular step.
	 * ¤¤¤ used to be a constructor. not any more
	 */
	//QueueEntry(AlignmentModel model, QueueEntry queueEntry, PathStep newStep) {
	public QueueEntry makeLongerPath(AlignmentModel model, PathStep newStep) throws EndOfAllTextsException, EndOfTextException, BlockedException {

		//¤//System.out.println(">>>QueueEntry constructor 2. path som skal utvides = " + queueEntry);
		//¤//System.out.println(">>>QueueEntry constructor 2. newStep = " + newStep);
		//System.out.println(">>>enter makeLongerPath. score = " + score);
		//System.out.println(">>>enter makeLongerPath. path = " + path);
		//System.out.println(">>>enter makeLongerPath. newStep = " + newStep);

		// clone and extend path with new step.
		/*
		// ¤¤¤ clunky? not oop?
		// ¤¤¤### burde laget og brukt en clone()-metode
		path = new Path();
		path.position = new int[Alignment.NUM_FILES];
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			//path.position[t] = queueEntry.path.position[t];
			path.position[t] = this.path.position[t];
		}
		//Iterator it = queueEntry.path.steps.iterator();
		Iterator it = this.path.steps.iterator();
		PathStep step;
		PathStep stepCopy;
		while (it.hasNext()) {
			step = (PathStep)it.next();
			stepCopy = new PathStep();
			for (int t=0; t<Alignment.NUM_FILES; t++) {
				stepCopy.increment[t] = step.increment[t];
			}
			path.steps.add(stepCopy);
		}
		*/
		QueueEntry retQueueEntry = (QueueEntry)this.clone();
		//System.out.println(">>>makeLongerPath. har klonet. retQueueEntry sin score = " + retQueueEntry.score);
		//System.out.println(">>>makeLongerPath. har klonet. retQueueEntry sin path = " + retQueueEntry.path);

		// but calculate new score before extending
		//System.out.println("QueueEntry constructor 2. newStep = " + newStep);
		//float stepScore;
		float newScore;
		try {
			//stepScore = tryStep(model, newStep);
			//System.out.println("før tryStep()");
			newScore = tryStep(model, newStep);
			//System.out.println("tryStep() returnerer ny sti-skåre " + newScore);
		} catch (EndOfAllTextsException e) {
			//System.out.println("makeLongerPath() throws EndOfAllTextsException");
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		} catch (EndOfTextException e) {
			//System.out.println("makeLongerPath() throws EndOfTextException");
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		} catch (BlockedException e) {
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		}
		//score = queueEntry.score + stepScore;
		//retQueueEntry.score = this.score + stepScore;
		retQueueEntry.score = newScore;
		//System.out.println(">>>makeLongerPath. klonen retQueueEntry sin score økt med " + stepScore + " til " + retQueueEntry.score);
		//System.out.println(">>>makeLongerPath. klonen retQueueEntry sin score økt til " + retQueueEntry.score);
		////System.out.println("score øker med " + stepScore + " til " + score + " når vi tar steg " + newStep);
		//System.out.println("score øker med " + stepScore + " til " + retQueueEntry.score + " når vi tar steg " + newStep);
		////scoreHistory += "Score øker med " + stepScore + " til " + score + " når vi tar steg " + newStep.toString() + ". ";

		// extend.
		//System.out.println("path før extend = " + retQueueEntry.path);
		//System.out.println("skal utvide med steg " + newStep);
		//path.extend(newStep);
		retQueueEntry.path.extend(newStep);
		//System.out.println("path etter extend = " + retQueueEntry.path);

		//Object[] temp = {position, increment};
		//for (int t=0; t<Alignment.NUM_FILES; t++) {
		//	position[t] = queueEntry.position[t] + increments[t];   this
		//	System.out.println("position["+t+"]" + position[t]);
		//}

		// compare with old score for this position
		//System.out.println("compare with old score for this position. old score  = " + model.compare.getScore(model, path.position));
		//System.out.println("compare new score " + retQueueEntry.score + " with old score for this position. old score  = " + model.compare.getScore(model, this.path.position));
		//System.out.println("compare new score " + retQueueEntry.score + " with old score for this position. old score  = " + model.compare.getScore(model, retQueueEntry.path.position));
		//System.out.println("\n");
		//if (score > model.compare.getScore(model, path.position)) {
		if (retQueueEntry.score > model.compare.getScore(model, retQueueEntry.path.position)) {
			//System.out.println("new score beats old score");
			// new score beats old score.
			// update score and return the new QueueEntry object
			//System.out.println("position = " + path.position[0] + "," + path.position[1] + ". new score " + score + " beats old score " + model.compare.getScore(model, path.position));
			//model.compare.setScore(path.position, score);
			/*
			if ((retQueueEntry.path.position[0] > 73) && ((retQueueEntry.score == 13.0f) || (retQueueEntry.score == 14.0f) || (retQueueEntry.score == 15.0f))) {
				System.out.println("skal sette ny skåre 13 eller 14 eller 18: " + retQueueEntry.score + ". compare er nå\n" + model.compare);
			}
			*/
			model.compare.setScore(retQueueEntry.path.position, retQueueEntry.score);
			/*
			if ((retQueueEntry.path.position[0] > 73) && ((retQueueEntry.score == 13.0f) || (retQueueEntry.score == 14.0f) || (retQueueEntry.score == 15.0f))) {
				System.out.println("satte ny skåre 13 eller 14 eller 18. compare er nå\n" + model.compare);
			}
			*/
			//System.out.println("ny skåre satt. compare er nå\n" + model.compare);
			//¤//System.out.println(">>>QueueEntry constructor 2. ny og bedre skåre satt. utvidet path = " + this.path);
			//return;
			return retQueueEntry;
		} else {
			//System.out.println("new score not better than old score. returnerer med path = null");
			// new score not better than old score.
			// keep old score.
			// scrap the new QueueEntry object
			//¤//System.out.println("position = " + path.position[0] + "," + path.position[1] + ". new score " + score + " not better than old score " + model.compare.getScore(model, path.position));
			// ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤ krøkkete
			//this = null;
			//this.path = null;
			retQueueEntry.path = null;
			//return;
			return retQueueEntry;
		}

	}

	// try to advance the current path one particular step
	// (i.e, increments of ¤¤¤)
	// and calculate new score for longer path

	float tryStep(AlignmentModel model, PathStep newStep) throws EndOfAllTextsException, EndOfTextException, BlockedException {

		//System.out.println("### tryStep. path = " + path);
		float stepScore = 0.f;
		try {
			stepScore = getStepScore(model, path.position, newStep);
		} catch (EndOfAllTextsException e) {
			//System.out.println("tryStep() throws EndOfAllTextsException");
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		} catch (EndOfTextException e) {
			//System.out.println("tryStep() throws EndOfTextException");
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		} catch (BlockedException e) {
			throw e;   // ¤¤¤ er dette måten å forwarde en exception på?
		}

		//System.out.println("### tryStep. score = " + score);
		//System.out.println("### tryStep. stepScore = " + stepScore);
		return score + stepScore;
	}

	/*
	float getStepScore(AlignmentModel model, int[] position, PathStep newStep) {

		float stepScore = (float)0.0;
		int t, u, x, y;
		//System.out.println("getStepScore. position = " + position[0] + "," + position[1] + ". newStep = " + newStep.increment[0] + "," + newStep.increment[1]);
		// look at all combinations of two files out of all files (hahaha) and add their scores
		for (t=0; t<Alignment.NUM_FILES; t++) {
			for (u=t+1; u<Alignment.NUM_FILES; u++) {
				// look at the particular combination of file t and file u.
				// there is a rectangle of cells ...
				// ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤ hmmm. men er ikke Combine NUM_FILES-dimensjonal? her trenger jeg noe 2-dimensjonalt. jeg trenger én 2-dim matrise pr kombinasjon av filer
				// study the rectangle of cells involved in the current step
				// and collect scores
				int score = 0;
				//int score = 1;   // prøver foreløpig (?) med 1 slik at lengdene skal gjøre et utslag dersom alt annet svikter
				for (x = position[t] + 1; x <= position[t] + newStep.increment[t]; x++) {
					for (y = position[u] + 1; y <= position[u] + newStep.increment[u]; y++) {
						//System.out.println("x,y=" + x + "," + y);
						// add cell score   // ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤ f.eks 2-2 får for mye poeng her. 2-1 og 1-2 ok. ¤¤¤¤¤¤¤¤¤¤¤¤¤¤
						CompareCell compareCell = model.compare.getCellValues(model, x, y);
						//System.out.println("compareCell.anchorWordScore=" + compareCell.anchorWordScore);
						§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§§
						score += compareCell.anchorWordScore;   // ¤¤¤ foreløpig bare poeng for ankerord...
						//System.out.println("compareCell.properNameScore=" + compareCell.properNameScore);
						score += compareCell.properNameScore;   // ¤¤¤ ...og egennavn
						//System.out.println("compareCell.diceScore=" + compareCell.diceScore);
						score += compareCell.diceScore;   // ¤¤¤ ...og dice
						////score += compareCell.numWordsScore;   // ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤ ...og...
					}
				}
				//
				//...
				stepScore += score;
			}
		}

		// also calculate total lengths of the elements we compare.
		// the lengths are stored in the matrix cells.
		// should have had objects at the matrix' edge instead
		// ### NUM_FILES must be 2 for this to work
		int[] totalLength = new int[Alignment.NUM_FILES];
		int[] totalNumWords = new int[Alignment.NUM_FILES];   // ### ikke brukt
		t = 0;
		u = 1;
		y = position[u] + 1;   // any y will do, but it's best to use a value for which cells do exist
		for (x = position[t] + 1; x <= position[t] + newStep.increment[t]; x++) {
			CompareCell compareCell = model.compare.getCellValues(model, x, y);
			totalLength[t] += compareCell.length[t];
			totalNumWords[t] += compareCell.numWords[t];   // ### ikke brukt
		}
		t = 1;
		u = 0;
		y = position[u] + 1;   // any y will do, but it's best to use a value for which cells do exist
		for (x = position[t] + 1; x <= position[t] + newStep.increment[t]; x++) {
			CompareCell compareCell = model.compare.getCellValues(model, x, y);
			totalLength[t] += compareCell.length[t];
			totalNumWords[t] += compareCell.numWords[t];   // ### ikke brukt
		}

		// adjust score according to how well the lengths of the elements correlate
		//System.out.println("stepScore før lengdejustering=" + stepScore);
		stepScore = SimilarityUtils.adjustForLengthCorrelation(stepScore, totalLength[0], totalLength[1]);
		//System.out.println("stepScore etter lengdejustering=" + stepScore);

		return stepScore;

	}
	*/

	// ### new version

	float getStepScore(AlignmentModel model, int[] position, PathStep newStep) throws EndOfAllTextsException, EndOfTextException, BlockedException {

		//System.out.println("getStepScore(). position = " + position[0] + "," + position[1] + " , newStep = " + newStep);
		try {

			CompareCells compareCells = model.compare.getCellValues(model, position, newStep);

			//System.out.println("getStepScore(). på slutten. kaller compareCells.elementInfoToBeCompared.getScore(), som gir " + compareCells.elementInfoToBeCompared.getScore());
			return compareCells.elementInfoToBeCompared.getScore();

		} catch (EndOfAllTextsException e) {
			//System.out.println("getStepScore() throws EndOfAllTextsException");
			throw e;   // ¤¤¤ er dette måten?
		} catch (EndOfTextException e) {
			//System.out.println("getStepScore() throws EndOfTextException");
			throw e;   // ¤¤¤ er dette måten?
		}

	}

	public void remove() {
		// mark as removed
		removed = true;
	}

	public void end() {
		// mark as path that reaches the end of the texts
		end = true;
	}

	public String toString() {
		String temp = "";
		if (removed) {
			temp += "(removed) ";
		}
		if (end) {
			temp += "(end) ";
		}
		temp += "position = {";
		for (int t=0; t<Alignment.NUM_FILES; t++) {
			if (t > 0) { temp += ","; }
			//System.out.println("QueueEntry sin toString(). path = " + path);
			temp += Integer.toString(path.position[t]);
		}
		temp += "}\n";
		temp += "path = " + path.toString();
		temp += ", score = " + Float.toString(score);
		////temp += "scoreHistory = " + scoreHistory + "\n";
		return temp;
	}

}

/*
 * list of QueueEntry objects
 */
class QueueList {

	List<QueueEntry> entry = new ArrayList<QueueEntry>();   // ### heller hete entries?

	// ### only used when making copy. clunky?
	QueueList() {
		//System.out.println("QueueList() constructor");
	}

	QueueList(AlignmentModel model, int[] position) {
		//¤//System.out.println("QueueList(model, position) constructor. position=" + position[0] + "," + position[1]);
		entry.add(new QueueEntry(position, 0));
	}

	public boolean empty() {
		return (entry.size() == 0);
	}

	public void add(QueueEntry queueEntry) {
		entry.add(queueEntry);
	}

	public boolean contains(QueueEntry queueEntry) {
		// checks to see if there already is an entry with the same path
		Iterator it = entry.iterator();
		while (it.hasNext()) {
			QueueEntry nextQueueEntry = (QueueEntry)it.next();
			if (nextQueueEntry.path.equals(queueEntry.path)) {
				return true;
			}
		}
		return false;
	}

	public void remove(int[] pos) {
		// remove any paths leading to position pos
		// (there should be at most 1 such path,
		// but this method will work even if there are more than one).
		// ###(the queue list contains paths of the same length, i think.
		// sometimes this method will be called to remove a path of a different length,
		// and that path is not in the list. no problem).
		// note! doesn't remove for real.
		// just marks the relevant entry (entries) as removed.
		// done this way so it's possible to loop through the list with an iterator
		//
		// #### 2005-11-02
		// OOOOOOPS!!!!!!!!
		// must also remove paths PASSING THROUGH position pos.
		// example:
		// we're at the very beginning of the texts.
		// correct aligment is all 1-1's.
		// the program has considered all paths of length 2.
		// it has found 1-2 + 2-1 to be the best path leading to position {2,2}.
		// in the process of extending paths of length 2 to paths of length 3,
		// the program arrives at 1-1 + 1-1 + 1-1, which also leads to position {2,2}.
		// this latter path has a better score,
		// so 1-2 + 2-1 must be removed (marked for removal).
		// where is it we remove inferior paths from?
		// we remove them from the list of paths of length 3, which is under construction.
		// but is there any 1-2 + 2-1 in that list?
		// no, not as such.
		// but there might be paths 1-2 + 2-1 + x-y, that PASS THROUGH position {2,2}.
		// ALL THOSE PATHS MUST BE REMOVED.
		//
		// or perhaps the program hasn't tried to extend 1-2 + 2-1 yet.
		// IN THAT CASE IT MUST BE KEPT FROM DOING SO.
		// in the general case it must also be kept from extending
		// any path that PASSES THROUGH the current position.
		//
		//¤//System.out.println("QueueList sin remove()");
		//List toRemove = new ArrayList();
		//System.out.println("class QueueList sin remove() skal fjerne alle entries med path som leder til, eller passerer gjennom, pos {" + pos[0] + "," + pos[1] + "}");
		boolean debug = false;
		//if ((pos[0] == 4) && (pos[1] == 4)) { System.out.println(">>> pos er 4,4"); debug = true; }
		//if ((pos[0] == 2) && (pos[1] == 3)) { System.out.println(">>> pos er 2,3"); debug = true; }
		//if (debug) { System.out.println(">>>>>>>>>>>>>>>>>>>>>>> START remove()"); }
		int t;
		Iterator it = entry.iterator();
		while (it.hasNext()) {
			QueueEntry queueEntry = (QueueEntry)it.next();
			//if ((pos[0] == 4) && (pos[1] == 4)) {
			//	System.out.println(">>> pos er 4,4. queueEntry = " + queueEntry + "\n");
			//}
			//if (debug) { System.out.println(">>> queueEntry = " + queueEntry + "\n"); }
			//boolean eq = true;
			boolean hit = false;   // if the path ends at or passes through the position
			// search backwards through path for position
			int[] current = new int[Alignment.NUM_FILES];
			// start at the path's end position
			//current = queueEntry.path.position;
			System.arraycopy(queueEntry.path.position, 0, current, 0, queueEntry.path.position.length);
			int currentIx = queueEntry.path.steps.size() - 1;   // index for the current place in the path. start at end
			//if (debug) { System.out.println(">>> currentIx = " + currentIx); }
			boolean done = false;
			while (!done) {
				// still hope of finding the position in the path?
				//if (debug) { System.out.println(">>> still hope of finding the position in the path?"); }
				boolean hope = true;
				for (t=0; t<Alignment.NUM_FILES; t++) {
					if (current[t] < pos[t]) {
						// no. the current position in the path is situated to the left of, or above,
						// the position we search for. there is no point in following the path further back
						//if (debug) { System.out.println(">>> no. the current position in the path is situated to the left of, or above, the position we search for. there is no point in following the path further back"); }
						hope = false;
						break;
					}
				}
				if (hope) {
					// yes. compare the current position in the path with the position we're looking for
					//if (debug) { System.out.println(">>> yes. compare the current position in the path with the position we're looking for"); }
					boolean eq = true;
					for (t=0; t<Alignment.NUM_FILES; t++) {
						if (current[t] != pos[t]) {
							eq = false;
							break;
						}
					}
					if (eq) {
						// hit. the current position in the path is the one we're looking for
						//if (debug) { System.out.println(">>> hit. the current position in the path is the one we're looking for"); }
						hit = true;
						done = true;
					} else {
						// miss. move back one step in the path
						//if (debug) { System.out.println(">>> miss. move back one step in the path"); }
						if (currentIx >= 0) {
							for (t=0; t<Alignment.NUM_FILES; t++) {
								current[t] -= ((PathStep)(queueEntry.path.steps.get(currentIx))).increment[t];
							}
							currentIx--;
						} else {
							// not possible. path exhausted
							//if (debug) { System.out.println(">>> not possible. path exhausted"); }
							done = true;
						}
					}
				} else {
					// no
					//if (debug) { System.out.println(">>> no"); }
					done = true;
				}
			}

			//for (int t=0; t<Alignment.NUM_FILES; t++) {
			//	if (pos[t] != queueEntry.path.position[t]) {
			//		//eq = false;
			//		hit = false;
			//		break;
			//	}
			//}
			//if (eq) {
			if (hit) {
				//toRemove.add(queueEntry);
				//System.out.println("\nclass QueueList sin remove() merker entry " + queueEntry + " for fjerning\n");
				queueEntry.remove();   // i.e, mark it for removal. will be removed for real by the calling method, using method below
				//System.out.println("class QueueList sin remove() skal fjerne entry " + queueEntry);
				if (debug) { System.out.println(">>> hit. mark for removal entry " + queueEntry + "\n"); }
				//it.remove();
			}
		}
		//it = toRemove.iterator();
		//System.out.println("class QueueList skal fjerne " + it.size() + " entries");
		//while (it.hasNext()) {
		//	QueueEntry queueEntry = (QueueEntry)it.next();
		//	//¤//System.out.println("QueueList sin remove() fjerner en entry");
		//	System.out.println("class QueueList sin remove() skal fjerne entry " + queueEntry);
		//	entry.remove(queueEntry);
		//}

		if (debug) { System.out.println(">>>>>>>>>>>>>>>>>>>>>>> END remove()"); }
	}

	public void removeForReal() {
		// remove for real all entries marked as removed
		Iterator it = entry.iterator();
		List<QueueEntry> toRemove = new ArrayList<QueueEntry>();
		while (it.hasNext()) {
			QueueEntry queueEntry = (QueueEntry)it.next();
			if (queueEntry.removed) {
				toRemove.add(queueEntry);
			}
		}
		it = toRemove.iterator();
		while (it.hasNext()) {
			QueueEntry queueEntry = (QueueEntry)it.next();
			//System.out.println("QueueList sin removeForReal() fjerner entry " + queueEntry);
			entry.remove(queueEntry);
		}

	}

	public String toString() {
		String temp = "[\n";
		Iterator it = entry.iterator();
		while (it.hasNext()) {
			temp += it.next().toString();
			if (it.hasNext()) { temp += ",\n"; }
		}
		temp += "\n]";
		return temp;
	}

}