SHARE
TWEET

Untitled

a guest May 19th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Trie {
  2.     private TrieNode root;
  3.  
  4.     Trie() {
  5.         this.root = new TrieNode();
  6.     }
  7.  
  8.     public TrieNode getRoot() {
  9.         return this.root;
  10.     }
  11.  
  12.     public boolean search(String s) {
  13.         s += "*";
  14.         TrieNode temp = this.root; // set a temp node to the root for searching
  15.         int j = 0; // loops through string index
  16.         while(!temp.getChildren().IsEmpty()) { // runs till it reaches a node with no children
  17.             int nextCounter = 0;
  18.             temp.getChildren().First(); // moves to the first element
  19.             for(int i = 0; i < temp.getChildren().GetSize(); i++) { // loops through the children of the list
  20.                 if (s.charAt(j) == temp.getChildren().GetValue().getLetter()) { // checks if the string at index j is equal to the children
  21.                     temp = temp.getChildren().GetValue(); // moves temp down to its child at the right value
  22.                     j++;
  23.                     if(j == s.length()) { // if finished going through the list
  24.                         return true;
  25.                     }
  26.                 }
  27.                 else {
  28.                     temp.getChildren().Next(); // moves to the next element in the list
  29.                     nextCounter++;
  30.                     if(nextCounter > temp.getChildren().GetSize()-1) { // if moves next to the end of the word without finding
  31.                         return false; // anything return false
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.  
  37.         return false;
  38.     }
  39.  
  40.     /**
  41.      * This function inserts strings into the trie
  42.      *
  43.      * @param value a string to be inserted
  44.      * @param node  a node to move through the tree
  45.      */
  46.     public void insert(String value, TrieNode node) {
  47.         value += "*"; // this is going to be the null character
  48.         if(!search(value)) {
  49.             if (this.root.getChildren().IsEmpty()) {
  50.                 node = this.root; // set node to the root
  51.                 for (int i = 0; i < value.length(); i++) { // loops through the word to insert it into the list
  52.                     List<TrieNode> temp = node.getChildren(); // create a temp List to store the node
  53.                     temp.InsertAfter(new TrieNode(value.charAt(i))); // inserts the character at the start of the string into the list
  54.  
  55.                     node.setChildren(temp); // sets the temp list as the children of the
  56.                     node.getChildren().First(); // moves to the first node since its the first insert we know it will be at the right child
  57.  
  58.                     node = node.getChildren().GetValue(); // move the node to the first element in its children
  59.                 }
  60.             }
  61.             else {
  62.                 node = this.root; // set the node to the root
  63.                 int j = 0; // iterates through loop index
  64.                 while(j < value.length()) { // goes through the length of the value
  65.                     node.getChildren().First();
  66.                     boolean letterFound = false;
  67.                     for(int i = 0; i < node.getChildren().GetSize(); i++) { // loops through the children of the node
  68.                         if(value.charAt(j) == node.getChildren().GetValue().getLetter()) { // checks if string index is equal to trie node char
  69.                             node = node.getChildren().GetValue(); // if so set node to that value
  70.                             j++; // increment j
  71.                             letterFound = true;
  72.                         }
  73.                         else { // if they are not equal
  74.                             node.getChildren().Next(); // move to the next element in the linked list
  75.                             letterFound = false;
  76.                         }
  77.                     }
  78.                     if(!letterFound) { // if the letter is not found
  79.                         node.getChildren().First();
  80.                         node.getChildren().InsertAfter(new TrieNode(value.charAt(j))); // insert it
  81.                     }
  82.                 }
  83.  
  84.             }
  85.         }
  86.     }
  87.  
  88.     public TrieNode getParentNode(TrieNode node, String s) {
  89.         TrieNode temp = this.root; // start at the root
  90.         int j = 0; // starts at the first index
  91.         while(temp.getChildren().contains(node) == null) { // while the node hasnt been found
  92.             int nextCounter = 0; // counts how many times the .Next function is called
  93.             temp.getChildren().First();
  94.             for(int i = 0; i < temp.getChildren().GetSize(); i++) { // goes through the children of temp
  95.                 if(s.charAt(j) == temp.getChildren().GetValue().getLetter()) {
  96.                     temp = temp.getChildren().GetValue(); // move temp
  97.                     j++; // move char index
  98.                     break; // leave the loop
  99.                 }
  100.                 else {
  101.                     temp.getChildren().Next(); // go to the next child
  102.                     nextCounter++;
  103.                     if(nextCounter > temp.getChildren().GetSize()-1)
  104.                         return null;
  105.                 }
  106.             }
  107.         }
  108.         return temp;
  109.     }
  110.  
  111.     /**
  112.      * This method deletes a string from the trie
  113.      * @param s string to be deleted
  114.      */
  115.     public void delete(String s) {
  116.         if(search(s)) { // if the string is in the list
  117.             // This section of code will move to the last node of the string
  118.             TrieNode temp  = this.root; // start at the root
  119.             int j = 0; // s index
  120.             boolean lastNodeFound = false;
  121.             while(!temp.getChildren().IsEmpty() && !lastNodeFound) { // while the children  is not empty
  122.                 int nextCounter = 0;
  123.                 temp.getChildren().First(); // go to the first child
  124.                 for(int i = 0; i < temp.getChildren().GetSize(); i++) { // loops through the children
  125.                     if(s.charAt(j) == temp.getChildren().GetValue().getLetter()) { // until string index is found
  126.                         temp = temp.getChildren().GetValue(); // set temp to child
  127.                         j++;
  128.                         if(j == s.length()) { // if j gets to the end the last node is found
  129.                             lastNodeFound = true;
  130.                             break;
  131.                         }
  132.                     }
  133.                     else {
  134.                         temp.getChildren().Next(); // move to the next child
  135.                         nextCounter++;
  136.                         if(nextCounter > temp.getChildren().GetSize() -1) {
  137.                             break;
  138.                         }
  139.                     }
  140.                 }
  141.             }
  142.             // The rest of the code deletes the word
  143.             boolean deleted = false; // to check if its deleted
  144.             while(!deleted) { // while the word hasnt been deleted
  145.                 TrieNode parent = getParentNode(temp, s); // stores parent
  146.                 if(parent.getChildren().GetSize() <= 1) { // if parent has less than two children move up
  147.                     temp = getParentNode(temp,s);
  148.                 }
  149.                 else {
  150.                     temp.setLetter('\0'); // set letter to null
  151.                     temp = null; // set the node to null
  152.                     deleted = true; // set deleted to true
  153.                 }
  154.             }
  155.  
  156.         }
  157.     }
  158.  
  159.     /*
  160.      * Devon showed me his code for this and I applied a similar strategy to my code
  161.      */
  162.     public void print(String prefix, int length) {
  163.         TrieNode temp = this.root;
  164.         char[] primChars = prefix.toCharArray();
  165.  
  166.         for(int i = 0; i < primChars.length; i++) {
  167.             if(!temp.getChildren().IsEmpty())
  168.                 temp.getChildren().First();
  169.             for(int j = 0; j < temp.getChildren().GetSize(); j++) {
  170.                 if(primChars[i] == temp.getChildren().GetValue().getLetter()) {
  171.                     temp = temp.getChildren().GetValue();
  172.                     break;
  173.                 }
  174.                 temp.getChildren().Next();
  175.             }
  176.         }
  177.         int lengthLeft = length - primChars.length;
  178.         Stack<Character> suffix = new Stack<>();
  179.         printPossibleWords(prefix, lengthLeft,0,  suffix, temp);
  180.     }
  181.  
  182.     /*
  183.      * Devon showed me his code and I used a similar strategy to his.
  184.      */
  185.     private void printPossibleWords(String prefix, int lengthLeft, int suffixLength, Stack<Character> suffix, TrieNode temp) {
  186.         if (suffixLength == lengthLeft) {
  187.             String word = prefix;
  188.             Character[] suffixCopy = new Character[lengthLeft];
  189.  
  190.             for (int i = lengthLeft - 1; i >= 0; i--) {
  191.                 suffixCopy[i] = suffix.pop();
  192.             }
  193.             for (Character c : suffixCopy) {
  194.                 suffix.push(c);
  195.             }
  196.  
  197.             for (int i = 0; i < temp.getChildren().GetSize(); i++) {
  198.                 temp.getChildren().SetPos(i);
  199.                 if (temp.getChildren().GetValue().getLetter() == '*') {
  200.                     for (int j = 0; j < lengthLeft; j++) {
  201.                         word += suffixCopy[j];
  202.                     }
  203.                     System.out.println(word);
  204.                 }
  205.  
  206.             }
  207.             suffix.pop();
  208.             return;
  209.         }
  210.             int n = 0;
  211.             while(suffixLength < lengthLeft) {
  212.                 temp.getChildren().SetPos(n);
  213.                 if(n != temp.getChildren().GetSize() && temp.getChildren().GetValue().getLetter() != '*')
  214.                 {
  215.                     suffix.push(temp.getChildren().GetValue().getLetter());
  216.                     suffixLength++;
  217.                     printPossibleWords(prefix, lengthLeft, suffixLength, suffix, temp.getChildren().GetValue());
  218.                 }
  219.                 else {
  220.                     suffix.pop();
  221.                     return;
  222.                 }
  223.                 suffixLength--;
  224.                 n++;
  225.             }
  226.         }
  227.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top