import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.FileReader;
import java.util.ArrayList;

/*
 * bsearch
 *
 * Run a binary search on each item listed in an input file.
 * Input items are of the form:
 * 
 *   [ ... ], value
 *
 * where "..." represents a list of floating-point numbers delimited by spaces
 * and "value" represents the number to find in the list
 *
 * Binary search requires the input to be sorted.  List items can be sorted
 * automatically using the -sort option.
 *
 * The -correct option executes the correct version of the binary search.
 * This way, the correct behavior can be tested even if the default version 
 * has been altered.
 *
 * Created: April 3, 2007 - Andrew Compton
 */
public class bsearch {
	public static void main(String[] args) {
		boolean foundFileName = false;
		boolean useCorrect = false;
		boolean autoSort = false;
		String fileName = "";
		String outfile = "";
		BufferedReader fin;
		BufferedWriter fout;
		
		// parse command line options
		if(args.length == 0) {
			System.out.println("A filename is required");
			System.out.println("Use -correct to use the unmodified binary search algorithm"); 
			System.out.println("Use -sort to automatically sort the lists in the input file"); 
			return;
		}

		for(int i = 0; i < args.length; i++) {
			if(args[i].equals("-correct")) {
				useCorrect = true;
			} else if(args[i].equals("-sort")) {
				autoSort = true;
			} else {
				if(!foundFileName) {
					fileName = args[i];
					foundFileName = true;
				}
			}
		}

		if(!foundFileName) {
			System.out.println("Error: a filename must be supplied");
			return;
		}

		// open the file for reading
		System.out.println("Attempting to read \"" + fileName + "\" for processing...");
		System.out.println("Using the " + (useCorrect ? "unmodified" : "default") + " binary search algorithm...");
		System.out.println((autoSort ? "Automatically" : "Not") + " sorting input lists...");

		try {
			fin = new BufferedReader(new FileReader(fileName));
		} catch(Exception e) {
			System.out.println("Error reading file \"" + fileName + "\"");
			return;
		}

		// open output file
		int dotIdx = fileName.indexOf('.');
		if(dotIdx != -1 ) {
			outfile = fileName.substring(0, dotIdx);
			outfile += "_result";
			outfile += fileName.substring(dotIdx);
		} else {
			outfile += "_result";
		}
		System.out.println("Output will be written to \"" + outfile + "\"...");

		try {
			fout = new BufferedWriter(new FileWriter(outfile));
		} catch(Exception e) {
			System.out.println("Error opening file \"" + outfile + "\" for writing");
			
			try {
				fin.close();
			} catch(Exception ex) {}
			return;
		}

		System.out.println();
		doSearches(fin, fout, useCorrect, autoSort);
		System.out.println();

		try {
			fin.close();
			fout.close();
		} catch(Exception ex) {	}
	}

	/**
	 * Perform the binary search on each line of an input file.
	 * @param fin The input file.
	 * @param fout The output file.
	 * @param useCorrect Whether to use the default or correct version of the search.
	 * @param autoSort Whether to sort search arrays automatically.
	 */
	private static void doSearches(BufferedReader fin, BufferedWriter fout, boolean useCorrect, boolean autoSort) {
		String strInput = "";
		String strList;
		String strVal;
		
		float searchVal = 0;
		ArrayList<Float> inputList = new ArrayList<Float>();

		int lineNumber = 0;
				
		// process the entire file
		while( (strInput = readNextLine(fin)) != null) {			
			lineNumber++;
			
			// preserve line breaks and full-line comments
			if(strInput.length() == 0 || strInput.charAt(0) == '#') {
				try {
					fout.write(strInput);
					fout.newLine();
				} catch (Exception ex) {
					System.out.println("Error: can't write to output file.");
					return;
				}
				continue;
			}
			
			// parse out any comments
			if(strInput.indexOf('#') != -1) {
				strInput = strInput.substring(0,strInput.indexOf('#'));
			}
			
			// process each input line
			// the location of the comma will let us find the components
			String[] pieces = strInput.split(",");

			if(pieces.length == 1) {
				printError(fout, "No search value found", lineNumber);
				continue;
			}
			
			strList = pieces[0];
			strVal = pieces[1];

			// read the value we're looking to find
			try {
				searchVal = Float.parseFloat(strVal);
			} catch(Exception ex) {
				printError(fout, "Bad search value", lineNumber);
				continue;
			}

			// get rid of the brackets around the list
			if(strList.length() == 2) {
				printError(fout, "Empty list", lineNumber);
				continue;
			} else {
				strList = strList.replace('[', ' ').replace(']', ' ');
			}

			// finally, read the list
			String[] listItems = strList.split(" ");
			
			for(int i = 0; i < listItems.length; i++) {
				if(listItems[i].equals("")) {
					continue;
				}
				
				try {
					inputList.add(Float.parseFloat(listItems[i]));
				} catch(Exception ex) {
					printError(fout, "Bad list item", lineNumber);
					continue;
				}
			}

			// sort the list, if desired
			if(autoSort) {
				java.util.Collections.sort(inputList);
			}

			// do the search
			int result = -1;
			if(useCorrect) {
				result = BinSearch_correct(inputList, searchVal);
			} else {
				result = BinSearch(inputList, searchVal);
			}

			// record the results
			StringBuilder sb = new StringBuilder();
			sb.append(result);
			sb.append("\t --> [");
			
			for(int i = 0; i < inputList.size(); i++) {
				sb.append(inputList.get(i));
				
				if(i != inputList.size() - 1) {
					sb.append(' ');
				}
			}
			
			sb.append("], ");
			sb.append(searchVal);

			System.out.println(sb.toString());
			
			try {
				fout.write(sb.toString());
				fout.newLine();
			} catch (Exception ex) {
				System.out.println("Error: can't write to output file.");
				return;
			}			
			
			inputList.clear();
		}
	}

	/**
	 * Get the next line from the input file.
	 * @param fin The input file stream to read. 
	 * @return The next line in the file.
	 */
	private static String readNextLine(BufferedReader fin) {
		// read the next line from the input file
		String strInput = null;
		try {
			strInput = fin.readLine();
		} catch (Exception ex) {
			System.out.println("Error: can't read input file.");
		}
		
		return strInput;
	}

	/**
	 * The default implementation of binary search, with errors.
	 * @param list The list of numbers to search.
	 * @param item The number to find.
	 * @return If the item is found, its index in the input list.  If it is not found, -1.
	 */
	private static int BinSearch(ArrayList<Float> list, float item) {
		// Searches list for item, returning its index
		int first;          // Lower bound on list
		int last;           // Upper bound on list
		int middle;         // Middle index
		boolean found;		// Flag for loop exit

		found = false;
		first = 0;
		last  = list.size() - 2; // - 1;

		do
		{
			middle = (first + last) / 2;
			if (item < list.get(middle))
				last = middle - 1;
			else if (item > list.get(middle))
				first = middle + 1;
			else found = true;
		}
		while ((last >= first) && !found);
		
		if(found) {
			return middle;
		} else {
			return -1;
		}
	}

	/**
	 * The unmodified version of binary search.
	 * @param list The list of numbers to search
	 * @param item The number to find
	 * @return If the item is found, its index in the input list.  If it is not found, -1.
	 */
	private static int BinSearch_correct(ArrayList<Float> list, float item) {
		// Searches list for item, returning its index
		int first;          // Lower bound on list
		int last;           // Upper bound on list
		int middle;         // Middle index
		boolean found;		// Flag for loop exit

		found = false;
		first = 0;
		last  = list.size() - 1;

		do
		{
			middle = (first + last) / 2;
			if (item < list.get(middle))
				last = middle - 1;
			else if (item > list.get(middle))
				first = middle + 1;
			else found = true;
		}
		while ((last >= first) && !found);
		
		if(found) {
			return middle;
		} else {
			return -1;
		}
	}

	/**
	 * Direct error messages both to standard output and to the output file.
	 * @param fout The file writer for the output file.
	 * @param msg The error message to write.
	 * @param line The line where the error occurred.
	 */
	public static void printError(BufferedWriter fout, String msg, int line) {
		System.out.println(msg + " (" + line + ") ");
		try {
			fout.write(msg + " (" + line + ") ");
			fout.newLine();
		} catch (Exception ex) {}
	}
}
