import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.TreeSet;

public class SeatRandomizer {
	static final String VERSION = "1.08";
	static final String LAST_UPDATED = "20080411.08";
	static final int DISPLAY_WIDTH = 32; // characters
	static final int MAX_PERMUTATION_TRIES = 100; // how many times the program will attempt to generate a permutation of seat assignments that matches the constraints

	public static void displayHeader() {
		System.out.println("You're running SeatRandomizer, version "+VERSION+", last updated on "+LAST_UPDATED+".");
		System.out.println("This software was designed and developed by Philip M. White <pmw@qnan.org>.");
		System.out.println("You can retrieve the latest version from <http://www.qnan.org/~pmw/software>.");
		System.out.println();
	}

	private static String removeLineComment(String s) {
		return s.replaceFirst("\\s*#.*", "");
	}

	/*
	 * This method finds Workstation objects that are equal to a string array of workstations.
	 * This is for when we read students from a file and want to associate each student with
	 * a set of workstation objects based on the list of workstations that's next to each name
	 * in the input file.
	 */
	private static HashSet<Workstation> findWorkstationObjs(HashSet<Workstation> workstations, String wkststr[]) {
		Iterator<Workstation> iter;
		Workstation w = null;
		HashSet<Workstation> wkstlist = new HashSet<Workstation>();

		if (wkststr == null)
			return wkstlist;
		for (int stri=0; stri < wkststr.length; stri++) {
			boolean found = false;
			iter = workstations.iterator();
			while (iter.hasNext() && !found) {
				w = iter.next();
				if (w.equals(new Workstation(wkststr[stri])))
					found = true;
			}
			if (found)
				wkstlist.add(w);
			// else no problem; this means that the workstation the student is supposedly using is not available for this assignment.
		}
		return wkstlist;
	}

	/*
	 * Preconditions:
	 * 1) The 'workstations' ListArray must be finalized.
	 */
	public static TreeSet<Student> readStudents(String filename, HashSet<Workstation> workstations) throws java.io.FileNotFoundException {
		TreeSet<Student> students = new TreeSet<Student>();
		int linecount = 0;
		String studentInfo[], line, workstationsStr[];
		Scanner sc = new Scanner(new FileReader(filename));

		while (sc.hasNextLine()) {
			linecount++;
			line = removeLineComment(sc.nextLine());
			studentInfo = line.split("\\|");
			if (studentInfo.length < 2 || studentInfo.length > 3) {
				System.err.println("Warning: line "+linecount+" of the students file is mis-formatted, so skipping it.");
				continue;
			}
			if (studentInfo.length == 3)
				workstationsStr = studentInfo[2].split(",");
			else
				workstationsStr = null;
			students.add(new Student(studentInfo[0], studentInfo[1], findWorkstationObjs(workstations, workstationsStr)));
		}
		return students;
	}

	public static HashSet<Workstation> readWorkstations(String filename) throws java.io.FileNotFoundException {
		HashSet<Workstation> workstations = new HashSet<Workstation>();
		Scanner sc = new Scanner(new FileReader(filename));
		String line;
		Workstation w;
		int linecount = 0;
		while (sc.hasNextLine()) {
			linecount++;
			line = removeLineComment(sc.nextLine());
			if (line.length() == 0) {
				continue;
			}
			w = new Workstation(line);
			workstations.add(w);
		}
		return workstations;
	}

	public static String produceSeparatedString(String s1, String s2, int width) {
		int i;
		String result;
		int spacing = width - (s1.length()+s2.length()+1); // the constant is how many spaces we add besides dot-space characters
		result = s1+" ";
		// align the dots between lines of differing s1.length()s
		if (s1.length() % 2 == 0) {
			result += " ";
			spacing--;
		}
		for (i=0; i+1 < spacing; i+=2) {
			result += ". ";
		}
		if (i < spacing)
			result += " ";
		return result+s2;
	}

	/*
	 * Postconditions:
	 * 1) 'workstations' has only those workstations that have not been assigned to a student
	 */
	public static HashMap<Student, Workstation> generatePermutation(TreeSet<Student> students, HashSet<Workstation> workstations) {
		Random rand = new Random();
		HashMap<Student, Workstation> map = new HashMap<Student, Workstation>();
		HashSet<Workstation> wkstDifference;
		Workstation w;

		for (Student student: students) {
			if (workstations.isEmpty())
				break; // we have no more workstations to assign
			// We know we have at least one not-yet-assigned workstation.
			wkstDifference = new HashSet<Workstation>(workstations);
			wkstDifference.removeAll(student.wkstGetUsual());
			if (wkstDifference.size() == 0)
				return null;
			w = (wkstDifference.toArray(new Workstation[0]))[rand.nextInt(wkstDifference.size())];
			workstations.remove(w);
			map.put(student, w);
		}
		return map;
	}

	public static void displayPermutation(HashMap<Student, Workstation> map, Iterator<Student> iter_s, TreeSet<Workstation> wkst_unassigned) {
		int nowkst_count = 0;
		String wkststr;

		System.out.println("== SEATING PERMUTATION ==");
		while (iter_s.hasNext()) {
			Student student = iter_s.next();
			if (!map.containsKey(student)) {
				nowkst_count++;
				wkststr = "N/A";
			}
			else
				wkststr = String.format("%3s", map.get(student));
			System.out.println(produceSeparatedString(student.nameGetNatural(), wkststr, DISPLAY_WIDTH));
		}
		System.out.println("--- unassigned workstations: ---");
		// Display all the remaining workstations
		if (wkst_unassigned.size() == 0)
			System.out.println("All workstations are assigned.");
		else {
			Iterator<Workstation> iter_w = wkst_unassigned.iterator();
			Workstation w;
			while (iter_w.hasNext()) {
				w = iter_w.next();
				System.out.print(w);
				if (iter_w.hasNext())
					System.out.print(", ");
			}
			System.out.println();
		}
		if (nowkst_count > 0)
			System.err.println("=*=*= WARNING: "+nowkst_count+" student(s) do not have a workstation!");
	}

	public static HashMap<Student, Workstation> findAndDisplayPermutation(TreeSet<Student> students, HashSet<Workstation> workstations) {
		int numTries = 0;
		HashMap<Student, Workstation> map;

		do {
			map = generatePermutation(students, workstations);
			numTries++;
		} while (numTries < MAX_PERMUTATION_TRIES && map == null);
		if (map == null) {
			System.err.println("\n*** COULD NOT GENERATE A SUITABLE PERMUTATION! ***\n\nAfter "+MAX_PERMUTATION_TRIES+" attempts, this program could not generate a seating arrangement that ensures that no student uses his/her usual workstation(s).\n\nI am giving up.");
			return null;
		}
		return map;
	}

	public static void main(String args[]) {
		String fn_students, fn_workstations;
		TreeSet<Student> students;
		HashSet<Workstation> workstations;
		HashMap<Student, Workstation> map;

		displayHeader();
		/*
		 * Figure out from where to get information
		 */
		if (args.length != 2) {
			Scanner sc = new Scanner(System.in);
			System.out.println("You did not pass the two required filenames as the command-line arguments,\nso the program will prompt you interactively.");
			System.out.println("You can call the program like so:\n\tjava SeatRandomizer <fn-students> <fn-workstations>");
			System.out.print("Enter the filename with student information: ");
			fn_students = sc.nextLine();
			System.out.print("Enter the filename with workstation information: ");
			fn_workstations = sc.nextLine();
		}
		else {
			fn_students = args[0];
			fn_workstations = args[1];
		}
		/*
		 * Fill data structures with information about students and workstations
		 */
		System.out.println("Processing input files...");
		workstations = null;
		try {
			workstations = readWorkstations(fn_workstations);
		} catch (java.io.FileNotFoundException e) {
			System.err.println("ERROR: Could not find the file of workstations that you provided.");
			System.exit(1);
		}
		students = null;
		try {
			students = readStudents(fn_students, workstations);
		} catch (java.io.FileNotFoundException e) {
			System.err.println("ERROR: Could not find the file of students that you provided.");
			System.exit(1);
		}
		System.out.println("Accepted "+students.size()+" students and "+workstations.size()+" workstations.");

		/*
		 * Attempt to find a permutation that satisfies all constraints
		 */
		map = findAndDisplayPermutation(students, workstations);
		if (map != null)
			displayPermutation(map, students.iterator(), new TreeSet<Workstation>(workstations));
	}
}