package edu.mioib.qaplocalsearch.algorithm;

import java.util.Comparator;
import java.util.List;

import lombok.EqualsAndHashCode;
import lombok.Value;

import com.google.common.collect.FluentIterable;
import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;

import edu.mioib.qaplocalsearch.AlgorithmRunMeasurer;
import edu.mioib.qaplocalsearch.Evaluator;
import edu.mioib.qaplocalsearch.algorithm.neighboursgenerator.TwoOptStateHolder;
import edu.mioib.qaplocalsearch.helper.ArraysUtil;

@Value
@EqualsAndHashCode(callSuper = false)
public class TabuSearchAlgorithm extends AbstractAlgorithm {
	@Override
	public int[] resolveProblem(int[] startState, Evaluator evaluator, AlgorithmRunMeasurer measurer) {
		int problemSize = startState.length;
		int tabuSize = problemSize / 4;
		int eliteCandidatesNumber = problemSize / 10;
		long[][] tabu = new long[problemSize][problemSize];
		
		long currentIteration = 0;
		long lastIterationWithImprovement = 0;
		int markowChainLength = problemSize;
		
		int[] currentState = startState;
		int[] bestState = currentState.clone();
		long bestEval = evaluateStateAndRecordEvaluation(evaluator, measurer, currentState);

		List<Move> candidates = null;
		
		while (!checkIfInterrupt(measurer) && (currentIteration - lastIterationWithImprovement) < (markowChainLength)) {
			if (candidates == null) {
				candidates = generateCandidates(currentState, evaluator, measurer, eliteCandidatesNumber);
			}

			Move minTabuCandIndex = null;
			Move chosenMove = null;
			for (Move cand : candidates) {
				int currCandIdx1 = cand.getIdx1();
				int currCandIdx2 = cand.getIdx2();
				if (cand.getEval() < bestEval
						|| !constainsMoveInTabu(tabu, tabuSize, currentIteration, currCandIdx1, currCandIdx2)) {
					ArraysUtil.swap(currentState, currCandIdx1, currCandIdx2);
					chosenMove = cand;
					break;
				}

				if (minTabuCandIndex == null
						|| tabu[currCandIdx1][currCandIdx2] < tabu[minTabuCandIndex.getIdx1()][minTabuCandIndex
								.getIdx2()]) {
					minTabuCandIndex = cand;
				}
			}

			if (chosenMove == null) {
				ArraysUtil.swap(currentState, minTabuCandIndex.getIdx1(), minTabuCandIndex.getIdx2());
				chosenMove = minTabuCandIndex;
				candidates = null;
			}

			addMoveToTabu(tabu, currentIteration, chosenMove.getIdx1(), chosenMove.getIdx2());

			long currentStateEval = evaluateStateAndRecordEvaluation(evaluator, measurer, currentState);
			if (currentStateEval < bestEval) {
				bestState = currentState.clone();
				bestEval = currentStateEval;
				
				lastIterationWithImprovement = currentIteration;
			}

			currentIteration++;
			measurer.recordStep();
		}
		
		return bestState;
	}

	private List<Move> generateCandidates(int[] currentState, Evaluator evaluator, AlgorithmRunMeasurer measurer,
			int eliteCandidatesNumber) {
		List<Move> candidates = Lists.newLinkedList();

		TwoOptStateHolder neighbourIterator = new TwoOptStateHolder(currentState);
		while (neighbourIterator.hasNextNeighbour()) {
			neighbourIterator.nextNeighbour();
			int idx1 = neighbourIterator.getIdx1();
			int idx2 = neighbourIterator.getIdx2();
			long stateEval = evaluateStateAndRecordEvaluation(evaluator, measurer, currentState);
			candidates.add(new Move(idx1, idx2, stateEval));
		}
		neighbourIterator.switchToOriginalState();
		
		return Ordering.from(new MoveComparator()).leastOf(FluentIterable.from(candidates), eliteCandidatesNumber);
	}

	@Override
	public String getName() {
		return "Tabu search";
	}

	private void addMoveToTabu(long[][] tabu, long currentIteration, int idx1, int idx2) {
		tabu[idx1][idx2] = currentIteration;
	}

	private boolean constainsMoveInTabu(long[][] tabu, int tabuSize, long currentIteration, int idx1, int idx2) {
		return tabu[idx1][idx2] + tabuSize > currentIteration;
	}

	@Value
	private static class Move {
		int idx1;
		int idx2;
		long eval;
	}

	private static class MoveComparator implements Comparator<Move> {

		@Override
		public int compare(Move move1, Move move2) {
			if (move1.eval < move2.eval) {
				return -1;
			}
			if (move1.eval > move2.eval) {
				return 1;
			}

			return 0;
		}

	}
}

@@ -870,30 +870,17 @@
 u = 
-new long%5BproblemSize%5D%5B
+initTabu(
 prob
@@ -886,17 +886,17 @@
 blemSize
-%5D
+)
 ;%0A%09%09%0A%09%09l
@@ -2665,24 +2665,271 @@
 tState;%0A%09%7D%0A%0A
+%09private long%5B%5D%5B%5D initTabu(int problemSize) %7B%0A%09%09long%5B%5D%5B%5D result = new long%5BproblemSize%5D%5BproblemSize%5D;%0A%09%09for (int i = 0; i %3C result.length; i++) %7B%0A%09%09%09for (int j = 0; j %3C result%5Bi%5D.length; j++) %7B%0A%09%09%09%09result%5Bi%5D%5Bj%5D = -1;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return result;%0A%09%7D%0A%0A
 %09private Lis
@@ -3970,24 +3970,56 @@
 int idx2) %7B%0A
+%09%09if (tabu%5Bidx1%5D%5Bidx2%5D %3E= 0) %7B%0A%09
 %09%09return tab
@@ -4059,24 +4059,44 @@
 tIteration;%0A
+%09%09%7D%0A%09%09return false;%0A
 %09%7D%0A%0A%09@Value%0A

Fix checking that move is in tabu