WordCompleter.java

package local.john;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;
import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.TreeMap;

class LinkedString {
    private LinkedString next;
    private char value;

    public LinkedString(char k) { this.value = k; }
    public LinkedString() { this('\0'); }
    public static LinkedString of(String s) {
        LinkedString head = new LinkedString();
        if (s.isEmpty()) return head;
        LinkedString current = head;
        for (int i=0; i < s.length(); i++) {
            current = current.append(new LinkedString(s.charAt(i)));
        }
        return head.next();
    }
    public LinkedString append(LinkedString next) {
        this.next = next;
        return next;
    }
    public LinkedString next() { return this.next; }
    public char value() { return this.value; }
    private void _build(StringBuilder sb) {
        sb.append(value);
        if (next != null) next._build(sb);
    }
    public LinkedString last() {
        LinkedString current = this;
        while (current.next() != null) {
            current = current.next();
        }
        return current;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        _build(sb);
        return sb.toString();
    }
}

// Using `extends` like a typedef:
class PrefixTree extends TreeMap<Character, PrefixTree> {}

public class WordCompleter {
    private PrefixTree prefix_tree = new PrefixTree();

    public static void main(String[] args) throws Exception {
        WordCompleter wc = new WordCompleter(
            /* specify a file or a URL: */

                "/home/john/Desktop/linuxwords.txt"
                //"http://lamp.epfl.ch/files/content/sites/lamp/files/teaching/progfun/linuxwords.txt"
        );

        for (String arg: args) {
            wc.query(arg).forEach(System.out::println);
            System.out.println();
        }
    }

    public WordCompleter(String file_url) throws Exception {
        BufferedReader br;
        if (file_url.startsWith("http")) {
            URL url = new URL(file_url);
            HttpURLConnection conn = (HttpURLConnection)url.openConnection();
            conn.setRequestMethod("GET");
            br = new BufferedReader(
                    new InputStreamReader(conn.getInputStream()));
        } else {
            File file = new File(file_url);
            br = new BufferedReader(new FileReader(file));
        }
        String thisLine;
        while ((thisLine = br.readLine()) != null) {
            LinkedString word_chars = LinkedString.of(thisLine.toLowerCase());
            add_word(word_chars, prefix_tree);
        }
    }

    private void add_word(LinkedString word_chars, PrefixTree tree) {
        if (word_chars == null) {
            tree.put('\0', null);
        } else {
            PrefixTree next_tree = tree.computeIfAbsent(word_chars.value(),
                    k -> new PrefixTree());
            add_word(word_chars.next(), next_tree);
        }
    }

    private PrefixTree get_subtree(LinkedString prefix_chars, PrefixTree tree) {
        if (prefix_chars == null) {
            return tree;
        } else {
            char k = prefix_chars.value();
            if (tree.containsKey(k)) {
                return get_subtree(prefix_chars.next(), tree.get(k));
            } else {
                return null;
            }
        }
    }

    public Iterable<String> query(String prefix_string) {
        class StackFrame {
            PrefixTree tree;
            LinkedString linked_string;
            char value;

            public StackFrame(PrefixTree tree, LinkedString linked_string, char value) {
                this.tree = tree;
                this.linked_string = linked_string;
                this.value = value;
            }
        }
        class ExecutionStack extends ArrayDeque<StackFrame> {}

        LinkedString accumulator = LinkedString.of(prefix_string);
        PrefixTree starting_tree = get_subtree(accumulator, prefix_tree);
        ExecutionStack stack = new ExecutionStack();
        if (starting_tree != null) {
            for (char k: starting_tree.descendingKeySet()) {
                stack.push(new StackFrame(starting_tree.get(k), accumulator.last(), k));
            }
        }

        // Iterable is a functional interface, therefore query() can return a
        // lambda.  The lambda is the implementation of iterator() in Iterable,
        // which returns an Iterator:
        return () -> new Iterator<String>() {
            public String next() {
                StackFrame current_frame = stack.pop();
                char value = current_frame.value;
                if (value == '\0') {
                    return accumulator.toString();
                } else {
                    PrefixTree tree = current_frame.tree;
                    LinkedString current = current_frame.linked_string;
                    LinkedString next = current.append(new LinkedString(value));
                    for (char k: tree.descendingKeySet()) {
                        stack.push(new StackFrame(tree.get(k), next, k));
                    }
                    return next();
                }
            }
            public boolean hasNext() { return !stack.isEmpty(); }
        };
    }
}