Skip to content

Instantly share code, notes, and snippets.

@snarkbait
Last active April 25, 2017 13:13
Show Gist options
  • Save snarkbait/5f1360a890399a85ec4c to your computer and use it in GitHub Desktop.
Save snarkbait/5f1360a890399a85ec4c to your computer and use it in GitHub Desktop.
String-Based Trie Example with Word Suggestion GUI
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;
}
}
}
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;
}
}
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();
}
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;
}
}
}
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment