package scheduling_algorithm;

import java.util.ArrayList;
import java.util.Random;

import input.Participant;
import input.ScheduleInformation;
import main.Ants;
import schedule_structure.Schedule;
import schedule_structure.ScheduleEvent;

/**
 * 
 * Uses a backtracking algorithm to generate a schedule that satisfies as many
 * of the user-specified constraints as possible in a limited amount of time
 * 
 * @author Triton Pitassi
 * @author Jordan White
 */
public class SchedulingAlgorithm {

	/** An empty schedule to start the backtracking */
	private final Schedule emptySchedule;

	/** The information the algorithm is to use in scheduling */
	private final ScheduleInformation scheduleInformation;

	/** A random number generator */
	private Random random;

	/** A boolean telling whether an acceptable schedule has been found */
	private boolean acceptableScheduleFound;

	/** The best completed schedule that has been found */
	private Schedule currentBestSchedule = null;

	/** The scores to be used by the backtracking evaluation */
	public ArrayList<Integer> scores = new ArrayList<Integer>();

	/**
	 * Score threshold variable to be updated when the time threshold is reached
	 */
	private double scoreThreshold = 0;

	/** The previous score of the schedule */
	private int previousScore = Integer.MAX_VALUE;

	/**
	 * A backtracking threshold related to the number of children attempted from
	 * this specific schedule
	 */
	private static final int NUM_PASSES_THRESHOLD = 10;

	/** A backtracking threshold that forces backtracking if reached */
	private static final int MAX_PASSES_THRESHOLD = 100;

	/** Keeps track of the number of schedule nodes visited */
	private int scheduleCounter = 0;

	/** Not mine, must be Jordan's */
	public String tempSchedFileName;

	/**
	 * The constructor
	 * 
	 * @param info
	 *            The information from the input file
	 * @param tempSchedFileName
	 *            Whatever this is...
	 */
	public SchedulingAlgorithm(ScheduleInformation info, String tempSchedFileName) {
		this.emptySchedule = this.makeEmptySchedule(info);
		this.scheduleInformation = info;
		this.tempSchedFileName = tempSchedFileName;

		// Initialize the random number generator
		this.random = new Random();

		acceptableScheduleFound = false;
	}

	/**
	 * Starts the algorithm and runs until an acceptable schedule is found
	 */
	public void startBacktracking() {
		// start the ThresholdHandler
		ThresholdHandler thresholdHandler = new ThresholdHandler(this, scoreThreshold, 1);

		// record start time
		double start = System.currentTimeMillis();
		System.out.println("Start: " + start);

		while (currentBestSchedule == null || currentBestSchedule.getScore() > (int) scoreThreshold) {
			// Reset variable so that backtracking can find a new schedule
			acceptableScheduleFound = false;
			backtracking(this.emptySchedule);
		}

		// algorithm is finished, stop updating score threshold
		thresholdHandler.stop();

		System.out.println("Schedule " + this.scheduleCounter);

		double end = System.currentTimeMillis();
		System.out.println("End " + end);
		System.out.println("Duration " + (end - start) / 1000);
		System.out.println("Chosen Score: " + currentBestSchedule.getScore());
	}

	/**
	 * Starts the algorithm and runs for the specified time
	 * 
	 * @param timeToRun
	 *            the amount of time (in seconds) to run the algorithm
	 */
	public void startBacktracking(int timeToRun) {
		new ThresholdHandler(this, scoreThreshold, timeToRun);

		// Set up timer
		long start = System.currentTimeMillis();
		long end = start + timeToRun * 1000; // 1000 ms/sec

		while (System.currentTimeMillis() < end) {
			// Reset variable so that backtracking can find a new schedule
			acceptableScheduleFound = false;
			backtracking(this.emptySchedule);
		}

		if (currentBestSchedule != null) {
			System.out.println("Chosen Score: " + currentBestSchedule.getScore());
		} else {
			System.err.println("ERROR: Failed to find a schedule");
		}
	}

	/**
	 * The backtracking algorithm. Makes use of methods to control the process.
	 * Decides if a finished schedule has been found, if backtracking should
	 * occur, and picks a random child to recurse on using the given input
	 * schedule
	 * 
	 * @param s
	 *            The schedule to find a child for
	 * @return A better schedule or the same schedule to indicate backtracking
	 */
	private Schedule backtracking(Schedule s) {

		// Evaluate schedule and add score to ArrayList
		int currentScore = evaluateSchedule(s);
		// System.out.println(currentScore);
		scores.add(new Integer(currentScore));

		this.scheduleCounter++;

		// If we've met the score threshold with a finished schedule, we're done
		if (s.allParticipantsScheduled()) {
			acceptableScheduleFound = true;
			if ((currentBestSchedule == null) || (s.getScore() < currentBestSchedule.getScore())) {
				currentBestSchedule = s;
				writeCurrentBestScheduleToFile();
			}
			backtrackHelper();
			return currentBestSchedule;
		}

		// Get the previous score for possible backtracking
		if (scores.size() > 1) {
			previousScore = scores.get(scores.size() - 2);
		}

		// If backtracking should occur, undo the changes to this schedule and
		// backtrack
		if (this.backtrackingShouldOccur(currentScore, previousScore)) {
			backtrackHelper();
			return s;
		}

		// Initializes variables to determine if we should backtrack
		int numPasses = 0;
		int totalScore = 0;

		// Loop until we find an acceptable schedule
		while (!acceptableScheduleFound) {

			// Choose a random child of this schedule and recurse
			Schedule randChild = chooseRandChild(s);

			if (randChild.beyondSalvation) {
				backtrackHelper();
				return s;
			}

			backtracking(randChild);

			// Increment the pass counter
			numPasses++;

			// Record unusually large scores and ignore them
			if (totalScore > 0 && randChild.getScore() > 4 * (totalScore / numPasses)) {
				totalScore += totalScore / numPasses;
			} else {
				// Calculate the total score for the children of this schedule
				// totalScore += randChild.getScore();
			}

			totalScore += randChild.getScore();

			// If we have tried a number of child schedules and the average is
			// higher (worse) than the current schedule's score, then backtrack
			if (s != this.emptySchedule && !acceptableScheduleFound) {
				if (numPasses > MAX_PASSES_THRESHOLD
						|| numPasses > NUM_PASSES_THRESHOLD && (totalScore / numPasses > currentScore)) {
					backtrackHelper();
					return s;
				}
			}
		}

		// Return the current best schedule
		if (!s.equals(this.emptySchedule)) {
			backtrackHelper();
		}
		return currentBestSchedule;
	}

	private void writeCurrentBestScheduleToFile() {
		if (currentBestSchedule == null)
			return;
		Ants.writeScheduleToFile(currentBestSchedule, tempSchedFileName, false, true);
	}

	/**
	 * A method that will undo the last change to instance variables. Currently
	 * only needs to delete the last score put into the scores list.
	 */
	private void backtrackHelper() {
		this.scores.remove(this.scores.size() - 1);
	}

	/**
	 * Determines if backtracking should occur based on the progression of
	 * scores.
	 * 
	 * @param currentScore
	 *            The score of the given schedule
	 * @param backtrackScore
	 *            The score of the previous schedule
	 * @return A boolean indicating if backtracking should occur
	 */
	private boolean backtrackingShouldOccur(int currentScore, int backtrackScore) {
		if (currentScore > backtrackScore + this.scoreThreshold) {
			return true;
		}

		return false;
	}

	/**
	 * Uses the given schedule and creates a child schedule by placing a
	 * participant that still needs to be placed
	 * 
	 * @param parent
	 *            The schedule to find a child for
	 * @return The child schedule
	 */
	private Schedule chooseRandChild(Schedule parent) {
		// clone the parent schedule
		Schedule s = parent.cloneSchedule();

		boolean needToAddParticipant = true;
		int failures = 0;

		while (needToAddParticipant) {
			// get a random event
			String eventName = (String) (s.uniformMap.keySet().toArray())[random.nextInt(s.uniformMap.keySet().size())];

			for (int i = 0; i < s.uniformMap.keySet().toArray().length; i++) {
				String name = (String) s.uniformMap.keySet().toArray()[i];
				if (!s.participantsRemaining.get(name).isEmpty()) {
					eventName = name;
					break;
				}
			}

			ScheduleEvent event = s.uniformMap.get(eventName).get(random.nextInt(s.uniformMap.get(eventName).size()));

			ArrayList<Participant> participants = s.participantsRemaining.get(event.getEventType().getEventName());

			if (participants == null || participants.isEmpty()) {
				continue;
			}

			if (s.uniformMap.get(eventName).size() > 1 && participants.size() == 1 && eventName.equals("Essay")) {
			}

			// sanity check
			if (event == null || event.getParticipants() == null || event.getLinkedEvent() != null) {
				continue;
			}

			if (participants.size() > 0) {
				int randNum = random.nextInt(participants.size());
				Participant randParticipant = participants.get(randNum);

				if (!event.addParticipant(randParticipant)) {
					failures++;
					if (failures > this.scheduleInformation.getParticipants().size() || participants.size() == 1) {
						s.beyondSalvation = true;
						return s;
					}
					continue;
				}
				participants.remove(randNum);

				s.uniformMap.get(eventName).remove(event);

				if (s.uniformMap.get(eventName).isEmpty()) {
					s.addAllUniformEventsByType(eventName);
				}

				needToAddParticipant = false;
			}
		}

		return s;
	}

	/**
	 * Updates the score threshold value
	 * 
	 * @param newThreshold
	 *            the new calculate offset value
	 */
	public void adjustScoreThreshold(double newThreshold) {
		scoreThreshold = newThreshold;
	}

	/**
	 * Evaluates the schedule and determines the score based on the number of
	 * constraints violated
	 * 
	 * @param schedule
	 *            The schedule to evaluate
	 * @return The score of the schedule
	 */
	private int evaluateSchedule(Schedule schedule) {
		return schedule.updateScheduleConstraintScore();
	}

	/**
	 * Makes an empty schedule based on the information from the input file
	 * 
	 * @param info
	 *            The information object
	 * @return An empty schedule
	 */
	public Schedule makeEmptySchedule(ScheduleInformation info) {
		return new Schedule(info);
	}

	/**
	 * Gets the current best schedule
	 * 
	 * @return The current best schedule
	 */
	public Schedule getSchedule() {
		return this.currentBestSchedule;
	}

	/**
	 * Testing main for checking the viability of constraints. Currently
	 * prevents John from being partnered with Jeff.
	 * 
	 * @return The schedule created
	 */
	public Schedule CreateScheduleTest() {
		return CreateScheduleTest(false);
	}

	/**
	 * Testing main for checking the viability of constraints. Currently
	 * prevents John from being partnered with Jeff.
	 * 
	 * @param verbose
	 *            Used for debugging
	 * @return The schedule created
	 */
	public Schedule CreateScheduleTest(boolean verbose) {
		int score = 1;
		Schedule testSched = null;

		int attempts = 0;
		while (score != 0) {
			attempts++;
			testSched = new Schedule(scheduleInformation);

			// The important one. essentially evaluates the schedule. If this is
			// 0, the schedule is as perfect as it can get.
			score = testSched.updateScheduleConstraintScore();
			if (verbose) {
				System.out.println("Schedule attempt:\t" + attempts);
				System.out.println("           score:\t" + score);
			}
		}
		System.out.println("Number of attempts: " + attempts);
		System.out.println("Final schedule score: " + score);

		testSched.printSchedule();

		return testSched;
	}

	/**
	 * Used by the threshold handler to force the algorithm to start over
	 * 
	 * @param maybe
	 *            The boolean value to set acceptableScheduleFound
	 */
	public void setAcceptableFound(boolean maybe) {
		this.acceptableScheduleFound = maybe;
	}
}