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

/**
 * Class that searches a list of strings and returns a list of all
 * strings that start with a prefix.
 *
 * @author davereed
 * @version 8/28/10
 */
public class PrefixMatcher {
    private ArrayList<String> phrases;

    /**
     * Constructs a PrefixMatcher, reading phrases from the specified file.
     * @param phraseFile the name of the file containing the phrases to search
     */
    public PrefixMatcher(String phraseFile) {
        this.phrases = new ArrayList<String>();
        try {
            Scanner infile = new Scanner(new File(phraseFile));
            while (infile.hasNextLine()) {
                this.phrases.add(infile.nextLine().toLowerCase());
            }
            Collections.sort(this.phrases);
        }
        catch (java.io.FileNotFoundException e) {
            System.out.println("File not found");
        }
    }

    /**
     * Finds all phrases that have the specified prefix.
     * @param prefix the desired prefix
     * @return all matches in a single string
     */
    public String findMatches(String prefix) {
        int start = this.findFirst(prefix.toLowerCase());
        int end = this.findLast(prefix.toLowerCase());
        
        String matches = "";
        for (int i = start; i <= end; i++) {
            matches += this.phrases.get(i) + "\n";
        }
        return matches;
    }

    /**
     * Performs binary search to find the first phrase that matches the prefix
     * @param prefix the desired prefix
     * @return ths index of the first matching phrase
     */
    private int findFirst(String prefix) {
        int low = 0;
        int high = this.phrases.size()-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (this.phrases.get(mid).startsWith(prefix)) {
                if (mid == 0 || !this.phrases.get(mid-1).startsWith(prefix)) {
                    return mid;
                }
                else {
                    high = mid-1;
                }
            }
            else if (prefix.compareTo(this.phrases.get(mid)) > 0) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        return low;
    }

    /**
     * Performs binary search to find the last phrase that matches the prefix
     * @param prefix the desired prefix
     * @return ths index of the last matching phrase
     */
    private int findLast(String prefix) {
        int low = 0;
        int high = this.phrases.size()-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (this.phrases.get(mid).startsWith(prefix)) {
                if (mid == this.phrases.size()-1 || !this.phrases.get(mid+1).startsWith(prefix)) {
                    return mid;
                }
                else {
                    low = mid+1;
                }
            }
            else if (prefix.compareTo(this.phrases.get(mid)) > 0) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        return high;
    }
    
}