import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class ParagraphFormatter {

	/**
	 * YOU MUST IMPLEMENT THIS METHOD FOR THE HOMEWORK.
	 * 
	 * Takes an ArrayList of strings that represent the words in a paragraph and
	 * an integer maxLength representing the maximum number of characters
	 * allowed on a line. Returns the paragraph formatted with line breaks that
	 * optimizes the squared slack penalty function.
	 * 
	 * @param words
	 *            A list of the words in the paragraph. Must not be empty.
	 * @param maxLength
	 *            The maximum number of characters allowed on a line.
	 * @return A string containing the formatted paragraph.
	 */
	public String formatParagraph(ArrayList<String> words, final int maxLength) {
		// In your implementation, you will probably need to calculate the length
		// of a line of words beginning at index i and ending at index j, including
		// spaces.  The LineLengthCalculator class is provided to allow you to do
		// this in constant time.  After constructing the object with the list of
		// words, just use the method lengthCalculator.getLength(i, j).
		LineLengthCalculator lengthCalculator = new LineLengthCalculator(words);
		int numWords = words.size();
		
		// This will contain the list of line breaks.
		ArrayList<Integer> breakList = new ArrayList<Integer>();

		//////////////////// START YOUR CODE HERE ////////////////////

		
		
		
		
		
		
		
		//////////////////// END YOUR CODE HERE ////////////////////
		
		// Be sure to carefully read the documentation for printWordsWithBreaks()
		// so you know what to put in breakList.  Note that you should not put a
		// break for the first line.  (An empty list signifies that the paragraph
		// should be output on one line.)
		return printWordsWithBreaks(words, breakList);
	}

	// IMPLEMENT THIS METHOD FOR EXTRA CREDIT PROBLEM 1 
	public String formatParagraphLast(ArrayList<String> words, final int maxLength) {
		LineLengthCalculator lengthCalculator = new LineLengthCalculator(words);
		int numWords = words.size();
		ArrayList<Integer> breakList = new ArrayList<Integer>();
		
		//////////////////// START YOUR CODE FOR EC 1 HERE ////////////////////
		

		
		

		//////////////////// END YOUR CODE FOR EC 1 HERE ////////////////////
		
		return printWordsWithBreaks(words, breakList);
	}

	
	// IMPLEMENT THIS METHOD FOR EXTRA CREDIT PROBLEM 2 
	public String formatParagraphDecreasing(ArrayList<String> words, final int maxLength) {
		LineLengthCalculator lengthCalculator = new LineLengthCalculator(words);
		int numWords = words.size();
		ArrayList<Integer> breakList = new ArrayList<Integer>();

		//////////////////// START YOUR CODE FOR EC 2 HERE ////////////////////
	
		
		
		

		//////////////////// END YOUR CODE FOR EC 2 HERE ////////////////////
		
		return printWordsWithBreaks(words, breakList);
	}

	/**
	 * Computes the squared slack penalty for a single line.
	 * 
	 * @param lineLength
	 * @param maxLength
	 * @return
	 */
	private int computePenalty(final int lineLength, final int maxLength) {
		return (maxLength - lineLength) * (maxLength - lineLength);
	}
	
	/**
	 * Takes a list of words in a paragraph and a list of line breaks and
	 * returns a the paragraph formatted with the given line breaks.
	 * 
	 * Example:
	 * 
	 * If the input is
	 * 
	 * words = ["Now", "is", "the", "time."]
	 * breaks = [2, 3]
	 * 
	 * then the output would be
	 * 
	 * "Now is
	 *  the
	 *  time."
	 * 
	 * @param words
	 *            The list of words in the paragraph, in order. Must not be
	 *            empty.
	 * @param breaks
	 *            A list of indices into words. Each index i in this list
	 *            represents the fact that words.get(i) should start a new line.
	 *            The indices must be unique and must be legal indices into
	 *            words. An empty list indicates no line breaks (and thus the
	 *            paragraph will be returned on one line.  The indices do not
	 *            need to be in a particular order.
	 * @return A String containing the paragraph given by words with line breaks
	 *         given by breaks.
	 */
	private String printWordsWithBreaks(ArrayList<String> words,
			ArrayList<Integer> breaks) {
		String str = "";
		Collections.sort(breaks);
		checkBreakArrayForErrors(breaks, words.size());
		
		// Technically, the index 0 should never be in breaks, since we would never
		// start the second line with the first word.  We'll check for it and remove
		// it just in case.
		if (breaks.size() > 0 && breaks.get(0) == 0) {
			breaks.remove(0);
		}
		
		int nextBreakPos = 0;
		for (int i = 0; i < words.size(); ++i) {
			if (i == 0) {
				str += words.get(i);
			} else if (nextBreakPos >= breaks.size()
					|| i != breaks.get(nextBreakPos)) {
				str += " " + words.get(i);
			} else { // nextBreakPos < breaks.size() && i == breaks.get(NextBreakPos)
				str += "\n" + words.get(i);
				++nextBreakPos;
			}
		}
		return str;
	}

	/**
	 * Checks a sorted array of line break indices to ensure that it is
	 * well-formed, i.e., that every index is an integer in the range (0,
	 * numWords] and that no index is repeated.
	 */
	private void checkBreakArrayForErrors(ArrayList<Integer> breaks,
			final int numWords) {
		if (breaks.size() == 0) {
			return;
		}
		if (breaks.get(0) <= 0) {
			throw new IllegalArgumentException(
					"No line break may be less than 0.  line break = "
							+ breaks.get(0));
		}
		if (breaks.get(breaks.size() - 1) > numWords - 1) {
			throw new IllegalArgumentException(
					"No line break may be more than numWords - 1.  line break = "
							+ breaks.get(breaks.size() - 1));
		}
		for (int i = 0; i < breaks.size() - 1; ++i) {
			if (breaks.get(i) == breaks.get(i + 1)) {
				throw new IllegalArgumentException("Repeated line break: "
						+ breaks.get(i));
			}
		}
	}

	/**
	 * Reads the command-line arguments, loads the file, and writes the
	 * output.
	 * 
	 * YOU SHOULD NOT EDIT THIS FUNCTION.
	 */
	public static void main(String[] args) {
		ParagraphFormatter formatter = new ParagraphFormatter();
		FileTokenizer tokenizer = new FileTokenizer();
		String fileName = args[0];
		int maxLength = Integer.parseInt(args[1]);
		try {
			ArrayList<String> words = tokenizer.getWordArrayFromFile(fileName);
			String output;
			if (args.length >= 3 && args[2].equals("last")) {
				output = formatter.formatParagraphLast(words, maxLength);
			} else if (args.length >= 3 && args[2].equals("decreasing")) {
				output = formatter.formatParagraphDecreasing(words, maxLength);
			} else {
				output = formatter.formatParagraph(words,  maxLength);
			}
			System.out.println(output);
		} catch (FileNotFoundException e) {
			System.err.println(e);
			System.exit(1);
		}
	}
}


/**
 * For a list of n words, this class does O(n) work on construction to
 * preprocess those words so that it can calculate the distance between any two
 * pairs of words in O(1) time.
 * 
 */
class LineLengthCalculator {
	private int numWords;

	// Contains the position of the end of the i-th word, if all of the words
	// were laid out on one line.
	private ArrayList<Integer> wordEndPositions;

	public LineLengthCalculator(ArrayList<String> words) {
		numWords = words.size();
		wordEndPositions = new ArrayList<Integer>();
		int pos = 0;
		for (int i = 0; i < numWords; ++i) {
			pos += words.get(i).length();
			if (i > 0) {
				pos += 1;
			}
			wordEndPositions.add(pos);
		}
	}

	/**
	 * Returns the length of text between word i (inclusive) and word j
	 * (inclusive).
	 * 
	 * @param i
	 *            Position of start word (inclusive)
	 * @param j
	 *            Position of end word (inclusive)
	 */
	public int getLength(int i, int j) {
		if (i < 0 || i >= numWords || j < 0 || j >= numWords || i > j) {
			throw new IllegalArgumentException("Required: 0 <= i <= j < n.");
		}
		int start;
		if (i == 0) {
			start = 0;
		} else {
			start = wordEndPositions.get(i - 1) + 1;
		}
		int end = wordEndPositions.get(j);
		return end - start;
	}
}


/**
 * Class for tokenizing a text file and loading the words into an
 * ArrayList of Strings.
 * 
 */
class FileTokenizer {

	public ArrayList<String> getWordArrayFromFile(String fileName) throws FileNotFoundException {
		ArrayList<String> words = new ArrayList<String>();
		Scanner scanner = new Scanner(new File(fileName));
		while (scanner.hasNext())
			words.add(scanner.next());
		return words;
	}
	
}