String-Based Trie Example with Word Suggestion GUI

DoublyChainedTrie.java

package trie;

import java.util.ArrayList;
import java.util.List;

/**
 * Doubly Chained String/Character based-Trie
 * @author /u/Philboyd_Studge on 1/13/2016.
 */
public class DoublyChainedTrie implements STrie {

    final Node root = new Node();
    int size;

    /**
     * Constructor from List
     * @param list List of Strings
     */
    public DoublyChainedTrie(List<String> list) {
        add(list);
    }

    /**
     * Constructor from Array
     * @param words String array
     */
    public DoublyChainedTrie(String[] words) {
        add(words);
    }

    /**
     * Adds word to Trie, value will default to 0
     * @param word String value to load into trie. If word already exists, value will be updated.
     */
    @Override
    public void add(String word) {
        add(word, 0);
    }

    /**
     * Add String Array to trie, with default value of 0;
     * @param words String Array
     */
    @Override
    public void add(String[] words) {
        if (words == null) {
            throw new IllegalArgumentException("Null array passed to Trie.");
        }
        for (String each : words) {
            add(each);
        }
    }

    /**
     * Add List of strings, with default value of 0
     * @param list List of Strings
     */
    @Override
    public void add(List<String> list) {
        if (list == null) {
            throw new IllegalArgumentException("Null list passed to Trie.");
        }
        add(list.toArray(new String[]{""}));

    }

    /**
     * Add individual string to trie, with specified value
     * @param word String to add
     * @param value Value to associate with string
     */
    @Override
    public void add(String word, int value) {
        if (word == null || word.length() == 0 || value < 0) {
            throw new IllegalArgumentException("Invalid data values.");
        }
        Node current = root;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Node found = null;
            if (!current.hasChild()) {
                current.child = new Node(c);
                current = current.child;
            }
            else {
                current = current.child;
                while (true) {
                    if (current.key == c) {
                        found = current;
                        break;
                    }
                    if (!current.hasNext()) break;
                    current = current.next;
                }
                if (found == null) {
                    current.next = new Node(c);
                    current = current.next;
                }
            }
        }
        current.value = value;
        size++;
    }

    /**
     * search trie for prefix/word
     * @param key String prefix or word to search for
     * @return true if found
     */
    @Override
    public boolean contains(String key) {
        return search(key) != null;
    }

    /**
     * Search trie for given complete word
     * @param key word to search for
     * @return true if found and has a value associated with
     */
    @Override
    public boolean containsCompleteWord(String key) {
        Node found = search(key);
        return found != null && found.value >= 0;
    }

    /**
     * get value associated with key
     * @param key string word
     * @return integer value or -1
     */
    @Override
    public int get(String key) {
        Node found = search(key);
        return found == null ? -1 : found.value;

    }

    private Node search(String key) {
        Node current = root;

        for (int i = 0; i < key.length(); i++) {
            Node found = null;
            current = current.child;
            if (current == null) return null;
            if (current.key != key.charAt(i)) {
                while (current.hasNext()) {
                    current = current.next;
                    if (current.key == key.charAt(i)) {
                        found = current;
                        break;
                    }
                }
                if (found == null) return null;
            }
        }
        return current;

    }

    /**
     * Creates a List of Strings of all the words in the trie that begin with the specified prefix
     * or null if none found
     * @param prefix string to start search with
     * @return list of strings
     */
    @Override
    public List<String> findWordsFromPrefix(String prefix) {
        Node found = search(prefix);
        if (found == null) return null;
        List<String> list = new ArrayList<>();
        preOrderTraversal(list, found, prefix);
        return list;
    }

    /**
     * Performs a complete pre-order traversal of the trie
     * recursive, so very large structures may cause
     * stack overflow
     * @return list of strings
     */
    @Override
    public List<String> preOrderTraversal() {
        List<String> list = new ArrayList<>();
        preOrderTraversal(list, root, "");
        return list;
    }

    private void preOrderTraversal(List<String> list, Node current, String prefix) {
        if (current.hasChild()) {
            current = current.child;
            char temp = current.key;
            preOrderTraversal(list, current, prefix + temp);
            if(current.value >= 0) {
                list.add(prefix + temp);
            }
            //prefix += current.key;
            while (current.hasNext()) {
                current = current.next;
                temp = current.key;
                preOrderTraversal(list, current, prefix + temp);
                if (current.value >= 0) {
                    list.add(prefix + temp);
                }
            }


        }
    }

    /**
     * size of trie
     * @return integer
     */
    @Override
    public int size() {
        return size;
    }

    private class Node {
        final char key;
        int value;
        Node next;
        Node child;

        public Node() {
            this('\u0000');
        }

        public Node(char key) {
            this.key = key;
            this.value = -1;
        }

        public Node(char key, int value) {
            this.key = key;
            this.value = value;
        }

        public boolean hasChild() {
            return this.child != null;
        }

        public boolean hasNext() {
            return this.next != null;
        }
    }

}

FileIO.java

package util;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.regex.PatternSyntaxException;

/**
 * FileIO.java is a set of static text file reading methods
 * for maximum simplicity. They are all for one-line use.
 * @author /u/Philboyd_Studge on 12/5/2015.
 */
public class FileIO {

    /**
     * Load file into one String
     * i.e. Day 1, Day 3
     * @param filename file in current working directory or full pathname
     * @return String
     */
    public static String getFileAsString(final String filename) {
        String test = "";
        try  {
            test = new String(Files.readAllBytes(Paths.get(filename)));
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
        return test;

    }

    /**
     * Performs given Function on file, one line at a time, and summing the results
     * @param filename file in current working directory or full pathname
     * @param func Function that takes a String as parameter and returns an int
     * @return int summed result
     */
    public static int performIntActionOnLine(final String filename, Function<String, Integer> func) {
        int result = 0;
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            String input;
            while ((input = br.readLine()) != null) {
                result += func.apply(input);
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
        return result;

    }

    /**
     * Loads entire file, one line at a time, into List
     * @param filename file in current working directory or full pathname
     * @return ArrayList of strings
     */
    public static List<String> getFileAsList(final String filename) {
        List<String> list = new ArrayList<>();
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            String input;
            while ((input = br.readLine()) != null) {
                list.add(input);
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
        return list;
    }

    /**
     * Return an ArrayList of String Arrays, split using the given delimiter
     * @param filename file in current working directory or full pathname
     * @param delimiter REGEX string delimiter. Catches PatternSyntaxException.
     * @return List of String Arrays
     */
    public static List<String[]> getFileLinesSplit(final String filename, String delimiter) {
        List<String[]> list = new ArrayList<>();
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            String input;
            while ((input = br.readLine()) != null) {
                try {
                    String[] s = input.split(delimiter);
                    list.add(s);
                } catch (PatternSyntaxException pse) {
                    System.out.println("Bad regex syntax. Delimiter \"" + delimiter + " \"");
                    return null;
                }
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }
        return list;

    }

    /**
     * Parse a String array into an int array
     * if parsing error occurs, inserts a value of -1
     * into array at that index
     * @param input String array
     * @return array of primitive integers
     */
    public static int[] StringArrayToInt(final String[] input) {
        return StringArrayToInt(input, -1);
    }

    /**
     * Parse a String array into int array
     * Catches conversion errors and puts given defaultValue at that index
     * @param input String array
     * @param defaultValue value to use when error is caught
     * @return array of primitive integers
     */
    public static int[] StringArrayToInt(final String[] input, final int defaultValue) {
        int[] output = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            try {
                output[i] = Integer.parseInt(input[i]);
            } catch (NumberFormatException nfe) {
                System.err.println("Not a valid integer at index: " + i);
                System.err.println("Replacing with: " + defaultValue);
                output[i] = defaultValue;
            }
        }
        return output;
    }

    /**
     * Parse a String array into an int array
     * if parsing error occurs, inserts a value of -1
     * into array at that index
     * @param input String array
     * @return array of primitive integers
     */
    public static Integer[] StringArrayToInteger(final String[] input) {
        return StringArrayToInteger(input, -1);
    }

    /**
     * Parse a String array into int array
     * Catches conversion errors and puts given defaultValue at that index
     * @param input String array
     * @param defaultValue value to use when error is caught
     * @return array of primitive integers
     */
    public static Integer[] StringArrayToInteger(final String[] input, final int defaultValue) {
        Integer[] output = new Integer[input.length];
        for (int i = 0; i < input.length; i++) {
            try {
                output[i] = Integer.parseInt(input[i]);
            } catch (NumberFormatException nfe) {
                System.err.println("Not a valid integer at index: " + i);
                System.err.println("Replacing with: " + defaultValue);
                output[i] = defaultValue;
            }
        }
        return output;
    }
}

STrie.java

package trie;

import java.util.List;

/**
 * @author /u/Philboyd_Studge on 1/14/2016.
 */
public interface STrie {
    void add(String key);
    void add(String key, int value);
    void add(String[] words);
    void add(List<String> list);
    boolean contains(String prefix);
    boolean containsCompleteWord(String word);
    List<String> preOrderTraversal();
    List<String> findWordsFromPrefix(String prefix);
    int get(String key);
    int size();
}

StringTrie.java

package trie;

import java.util.*;

/**
 * String/character based Trie
 * @author /u/Philboyd_Studge on 1/8/2016.
 */
public class StringTrie implements STrie{

    final Node root = new Node();
    int size;

    /**
     * Constructor from List
     * @param list List of Strings to add
     */
    public StringTrie(List<String> list) {
        add(list);
    }

    /**
     * Constructor from array
     * @param words Array of Strings to add
     */
    public StringTrie(String[] words) {
        if (words == null) throw new IllegalArgumentException("Null array.");
        add(words);
    }

    /**
     * Add individual word to trie, with default value of 0
     * @param key String to add
     */
    public void add(String key) {
        add(key, 0);
    }

    /**
     * Add array of strings to trie, with default value of 0
     * @param keys String array to add
     */
    @Override
    public void add(String[] keys) {
        for (String each : keys) {
            add(each);
        }
    }

    /**
     * Add ArrayList of Strings to trie
     * @param list List of Strings
     */
    @Override
    public void add(List<String> list) {
        if (list == null) throw new IllegalArgumentException("Null list.");
        add(list.toArray(new String[]{""}));
    }

    /**
     * Add individual string to trie, with specified value
     * @param key String to add
     * @param value Integer to associate with key word
     */
    @Override
    public void add(String key, int value) {
        Node current = root;
        key = key.toLowerCase();

        for (int i = 0; i < key.length(); i++) {
            Node found = current.children.getOrDefault(key.charAt(i), null);
            if (found == null) {
                found = new Node(key.charAt(i));
                current.children.put(key.charAt(i), found);
            }
            current = found;
        }
        current.value = value;
        size++;
    }

    /**
     * Search trie for prefix/word
     * @param key String prefix or word to search for
     * @return true is exists in trie
     */
    @Override
    public boolean contains(String key) {
        return search(key) != null;
    }

    /**
     * private method search used by get, contains, containsCompleteWord
     * @param key String key
     * @return Node last found node of word or null
     */
    private Node search(String key) {
        Node current = root;

        for (int i = 0; i < key.length(); i++) {
            Node found = current.children.getOrDefault(key.charAt(i), null);
            if (found == null) return null;
            current = found;
        }
        return current;
    }

    /**
     * Search trie if given word has a value attached to it
     * values are put at end of 'word'
     * otherwise nodes have an internal value of -1
     * @param key String word to search for
     * @return true if complete word found
     */
    @Override
    public boolean containsCompleteWord(String key) {
        Node found = search(key);
        return found != null && found.value >= 0;
    }

    /**
     * returns value for given key
     * @param key String key word to search for
     * @return integer value or -1 if not found
     */
    @Override
    public int get(String key) {
        Node found = search(key);
        return found == null ? -1 : found.value;
    }

    /**
     * Populates a List of all words in trie that start with given prefix
     * @param prefix String prefix
     * @return ArrayList of Strings or null
     */
    @Override
    public List<String> findWordsFromPrefix(String prefix) {
        Node found = search(prefix);
        if (found == null) return null;
        List<String> list = new ArrayList<>();
        preOrderTraversal(list, found, prefix);
        return list;
    }

    /**
     * Pre-Order Traversal of entire trie.
     * recursive, so large tries will cause stack overflow.
     * @return ArrayList of words contained in trie
     */
    @Override
    public List<String> preOrderTraversal() {
        List<String> list = new ArrayList<>();
        preOrderTraversal(list, root, "");
        return list;
    }


    private void preOrderTraversal(List<String> list, Node current, String prefix) {
        if (current.hasChildren()) {
            for (Map.Entry<Character, Node> each : current.children.entrySet()) {
                char temp = each.getKey();
                preOrderTraversal(list, each.getValue(), prefix + temp);
                current = each.getValue();
                if (current.value >=0) {
                    list.add(prefix + temp);
                }
            }
        }
    }

    @Override
    public int size() {
        return size;
    }

    private class Node {
        final char key;
        int value;
        Map<Character, Node> children;

        public Node() {
            // default null character
            this('\u0000');
        }

        public Node(char key) {
            // default value of -1
            this(key, -1);
        }

        public Node(char key, int value) {
            this.key = key;
            this.value = value;
            children = new HashMap<>(32);
        }

        public boolean hasChildren() {
            return children.size() > 0;
        }

    }

}

TypeSuggestionGUI.java

package trie;

import util.FileIO;

import javax.swing.*;
import javax.swing.event.DocumentEvent;
import javax.swing.event.DocumentListener;
import java.awt.*;
import java.util.*;

/**
 * Type Suggestion GUI example code
 *
 * @author /u/Philboyd_Studge on 1/14/2016.
 */
public class TypeSuggestionGUI extends JFrame {
    JPanel panel = new JPanel();
    JLabel label = new JLabel("Enter text here:");
    JTextField text = new JTextField();
    JList<String> listBox = new JList<>();
    JScrollPane scrollPane = new JScrollPane(listBox);
    JLabel word = new JLabel("word");

    STrie trie;

    public TypeSuggestionGUI() {
        super("Type Suggestion Tester");

        initTrie();
        initComponents();
        this.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        this.setLocationRelativeTo(null); // center window on screen
        this.setVisible(true);
    }

    private void initComponents() {
        this.setSize(400,300);

        // list box
        listBox.setForeground(Color.DARK_GRAY);
        listBox.addListSelectionListener((e) -> {
            // get user selection and change the word label
            String s = listBox.getSelectedValue();
            if (s != null && ! s.isEmpty()) {
                word.setText(listBox.getSelectedValue());
            }
        });

        // word display label
        word.setFont(new Font("arial", Font.BOLD | Font.ITALIC, 48));

        // text field
        text.setForeground(Color.RED);
        text.setFont(new Font("arial", Font.BOLD, 14));
        text.getDocument().addDocumentListener(new DocumentListener() {
            @Override
            public void insertUpdate(DocumentEvent e) {
                getAvailableWords(text.getText().toLowerCase());
            }

            @Override
            public void removeUpdate(DocumentEvent e) {
                getAvailableWords(text.getText().toLowerCase());
            }

            @Override
            public void changedUpdate(DocumentEvent e) {} // unused
        });

        // panel
        panel.setLayout(new BoxLayout(panel, BoxLayout.Y_AXIS));
        panel.setBorder(BorderFactory.createEmptyBorder(10,10,10,10));
        panel.add(label);
        panel.add(text);
        panel.add(scrollPane);
        panel.add(Box.createVerticalStrut(50));
        panel.add(word);

        this.add(panel, BorderLayout.CENTER);
    }

    /**
     * Create a lookup trie using the 'enable1.txt' file
     * of English words
     */
    private void initTrie() {
        trie = new DoublyChainedTrie(FileIO.getFileAsList("enable1.txt"));
    }

    /**
     * set the current listBox view to words found from prefix
     * @param list ArrayList of found words or null
     */
     private void setList(java.util.List<String> list) {
         if (list == null) {
             // if null, current text is not a word, highlight in red
             text.setForeground(Color.RED);
             return;
         }
         if (trie.containsCompleteWord(text.getText().toLowerCase())) {
             text.setForeground(Color.BLUE);
         } else {
             text.setForeground(Color.BLACK);
         }

         listBox.setListData(list.toArray(new String[]{""}));
    }

    /**
     * Use the trie to lookup words for the given prefix
     * if length of input string is 2 or greater
     * @param s input String
     */
    private void getAvailableWords(String s) {
        if (s.length() < 2) {
            text.setForeground(Color.RED);
            return;
        }
        java.util.List<String> list = trie.findWordsFromPrefix(s);
        if (list != null) Collections.sort(list);
        setList(list);
    }

    public static void main(String[] args) {
        try
        {
            for (UIManager.LookAndFeelInfo info : UIManager.getInstalledLookAndFeels())
            {
                if ("Nimbus".equals(info.getName()))
                {
                    UIManager.setLookAndFeel(info.getClassName());
                    break;
                }
            }
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }

        SwingUtilities.invokeLater(TypeSuggestionGUI::new);

    }
}