use std::fs::File;
use std::io::{self, BufRead, BufReader, Write};
use std::time::Instant;

// This function takes a query string, a slice of possible queries, and a maximum number of suggestions.
// It returns a vector of strings containing all the possible queries that start with the given query string, up to the maximum number of suggestions.
fn autocomplete_fast(query: &str, possible_queries: &[String], max_suggestions: usize) -> Vec<String> {
    // Convert the query string to lowercase.
    let query = query.to_lowercase();
    
    // Create an empty vector to store the matches.
    let mut matches = Vec::new();
    
    // Iterate over all possible queries.
    for possible_query in possible_queries {
        // If the possible query starts with the lowercase query string,
        if possible_query.to_lowercase().starts_with(&query) {
            // Add the possible query to the matches vector.
            matches.push(possible_query.to_string());
            
            // If we have reached the maximum number of suggestions,
            if matches.len() >= max_suggestions {
                break;
            }
        }
    }

    matches
}

// This function takes a filename and reads each line of the file as a string, adding it to a vector of strings.
// It returns the vector of strings containing all the lines of the file.
fn read_words_file(filename: &str) -> Vec<String> {
    // Create an empty vector to store the words.
    let mut words_list = Vec::new();
    
    // Open the file with the given filename and create a buffered reader.
    let file = File::open(filename).expect("failed to open file");
    let reader = BufReader::new(file);
    
    // Iterate over all lines of the file.
    for line in reader.lines() {
        // Read the line as a string and trim any leading or trailing whitespace.
        let word = line.expect("failed to read line").trim().to_string();

        words_list.push(word);
    }

    words_list
}

fn main() {
    let filename = "words.txt";
    let mut words_list = read_words_file(filename);
    
    // Sort the list of words
    words_list.sort();

    print!("query: ");
    io::stdout().flush().unwrap();
    let mut query = String::new();
    io::stdin().read_line(&mut query).expect("failed to read line");
    let query = query.trim();

    // You can set the desired number of suggestions here or ask the user for input.
    let max_suggestions = 10;

    let start_time = Instant::now();
    // Slice the words_list based on the first character of the query
    // This speeds up the search by preventing autocomplete_fast() from 
    // iterating the entire length of the list to get to the latter strings
    let first_char = query.chars().next().unwrap();
    let lower_bound = words_list.binary_search_by_key(&first_char.to_string(), |s| s.chars().next().unwrap().to_string()).unwrap_or_else(|x| x);
    let upper_bound = words_list.binary_search_by_key(&((first_char as u8 + 1) as char).to_string(), |s| s.chars().next().unwrap().to_string()).unwrap_or_else(|x| x);

    let sliced_words_list = &words_list[lower_bound..upper_bound];
    let suggestions = autocomplete_fast(query, sliced_words_list, max_suggestions);
    let end_time = Instant::now();

    println!("{:?}", suggestions);
    println!("Time taken: {:.4} seconds", (end_time - start_time).as_secs_f64());
}