package DataStructures.Trees;

/**
 * Trie Data structure implementation without any libraries
 *
 * @author Dheeraj Kumar Barnwal (https://github.com/dheeraj92)
 */
import java.util.Scanner;

public class TrieImp {

 public class TrieNode {
 TrieNode[] child;
 boolean end;

 public TrieNode() {
 child = new TrieNode[26];
 end = false;
 }
 }

 private final TrieNode root;

 public TrieImp() {
 root = new TrieNode();
 }

 public void insert(String word) {
 TrieNode currentNode = root;
 for (int i = 0; i < word.length(); i++) {
 TrieNode node = currentNode.child[word.charAt(i) - 'a'];
 if (node == null) {
 node = new TrieNode();
 currentNode.child[word.charAt(i) - 'a'] = node;
 }
 currentNode = node;
 }
 currentNode.end = true;
 }

 public boolean search(String word) {
 TrieNode currentNode = root;
 for (int i = 0; i < word.length(); i++) {
 char ch = word.charAt(i);
 TrieNode node = currentNode.child[ch - 'a'];
 if (node == null) {
 return false;
 }
 currentNode = node;
 }
 return currentNode.end;
 }

 public boolean delete(String word) {
 TrieNode currentNode = root;
 for (int i = 0; i < word.length(); i++) {
 char ch = word.charAt(i);
 TrieNode node = currentNode.child[ch - 'a'];
 if (node == null) {
 return false;
 }
 currentNode = node;
 }
 if (currentNode.end == true) {
 currentNode.end = false;
 return true;
 }
 return false;
 }

 public static void sop(String print) {
 System.out.println(print);
 }

 /** Regex to check if word contains only a-z character */
 public static boolean isValid(String word) {
 return word.matches("^[a-z]+$");
 }

 public static void main(String[] args) {
 TrieImp obj = new TrieImp();
 String word;
 @SuppressWarnings("resource")
 Scanner scan = new Scanner(System.in);
 sop("string should contain only a-z character for all operation");
 while (true) {
 sop("1. Insert\n2. Search\n3. Delete\n4. Quit");
 try {
 int t = scan.nextInt();
 switch (t) {
 case 1:
 word = scan.next();
 if (isValid(word)) obj.insert(word);
 else sop("Invalid string: allowed only a-z");
 break;
 case 2:
 word = scan.next();
 boolean resS = false;
 if (isValid(word)) resS = obj.search(word);
 else sop("Invalid string: allowed only a-z");
 if (resS) sop("word found");
 else sop("word not found");
 break;
 case 3:
 word = scan.next();
 boolean resD = false;
 if (isValid(word)) resD = obj.delete(word);
 else sop("Invalid string: allowed only a-z");
 if (resD) {
 sop("word got deleted successfully");
 } else {
 sop("word not found");
 }
 break;
 case 4:
 sop("Quit successfully");
 System.exit(1);
 break;
 default:
 sop("Input int from 1-4");
 break;
 }
 } catch (Exception e) {
 String badInput = scan.next();
 sop("This is bad input: " + badInput);
 }
 }
 }
}