Advertisement
ismaeil

Trie in Dart

Jul 17th, 2021
999
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Dart 4.63 KB | None | 0 0
  1. /// --- Vertex File --- ///
  2.  
  3. /* * * * * * * * * * *  Vertex  * * * * * * * * * * * *
  4. *                                                     *
  5. * The Vertex has 52 pointers to a Vertex such that:   *
  6. *   - The first  26 idx to the upper case letters     *
  7. *   - The second 26 idx to the lower case letters     *
  8. *                                                     *
  9. * * * * * * * * * * * * * ** * * * * * * * * * * * * */
  10.  
  11. class Vertex{
  12.   Map<String , Vertex> child;
  13.   final size = 26 * 2;
  14.   String alphabet;
  15.   bool exist;
  16.  
  17.   Vertex(String alphabet){
  18.     this.exist    = false;
  19.     this.alphabet = alphabet;
  20.     this.child    = new Map();
  21.   }
  22. }
  23.  
  24. /// --- Trie File --- ///
  25.  
  26. /* * * * * * * * * * *  Trie  * * * * * * * * * * * * *
  27. * Data Structure that allow inserting words inside it *
  28. * and it can get all words that start with specific   *
  29. * Prefix in linear time complexity = O(n + m), where: *
  30. *     n = length of the prefix string                 *
  31. *     m = number of nodes of prefix's subtree         *
  32. * * * * * * * * * * * * * ** * * * * * * * * * * * * */
  33.  
  34. import 'Vertex.dart';
  35.  
  36. class Trie {
  37.   /// ===================================================================== ///
  38.   /// ============================== Private ============================== ///
  39.   /// ===================================================================== ///
  40.   List< String > _queryRes;
  41.   String _word;
  42.   Vertex _root;
  43.  
  44.   // recursively insert function
  45.   void _insert(Vertex cur ,int i){
  46.     if( i == this._word.length ){
  47.       cur.exist = true;
  48.       return;
  49.     }
  50.     String char = this._word[i];
  51.     if( cur.child[char] == null ){
  52.       cur.child[char] = new Vertex(char);
  53.     }
  54.     _insert(cur.child[char] ,i + 1);
  55.   }
  56.  
  57.   // recursively get all words function
  58.   void _getAll(Vertex cur ,String s){
  59.     if( cur.exist == true ){
  60.       this._queryRes.add(s);
  61.     }
  62.     if( cur.child.isNotEmpty ) {
  63.       cur.child.forEach((key, value) {
  64.         _getAll(value, s + value.alphabet);
  65.       });
  66.     }
  67.   }
  68.  
  69.   // recursively get all words with common prefix function
  70.   void _getAllWithPrefix(Vertex cur ,String s ,int i ,String prefix){
  71.     if( i == prefix.length ){
  72.       if( cur.exist == true ){
  73.         _queryRes.add(s);
  74.       }
  75.       if( cur.child.isNotEmpty ){
  76.         cur.child.forEach((key, value) {
  77.           _getAllWithPrefix(value, s + value.alphabet, i, prefix);
  78.         });
  79.       }
  80.     }
  81.     else {
  82.       String char = prefix[i];
  83.       if( cur.child[char] != null ){
  84.         _getAllWithPrefix(cur.child[char], s + char, i + 1, prefix);
  85.       }
  86.     }
  87.   }
  88.  
  89.   // recursively print all words function
  90.   void _printALl(Vertex cur ,String s){
  91.     if( cur.exist == true ){
  92.       print(s);
  93.     }
  94.     if( cur.child.isNotEmpty ) {
  95.       cur.child.forEach((key, value) {
  96.         _printALl(value, s + value.alphabet);
  97.       });
  98.     }
  99.   }
  100.  
  101.   /// ==================================================================== ///
  102.   /// ============================== Public ============================== ///
  103.   /// ==================================================================== ///
  104.  
  105.   // constructor
  106.   Trie(){
  107.     _root = new Vertex('#');
  108.   }
  109.  
  110.   // Function to insert one word into the Trie
  111.   // The function call another Recursively Function
  112.   void insert(String word){
  113.     this._word = word;
  114.     _insert(_root ,0);
  115.   }
  116.  
  117.   // Function to get all words from the Trie
  118.   // The function call another Recursively Function
  119.   List<String> getAll(){
  120.     this._queryRes = new List();
  121.  
  122.     _getAll(_root, "");
  123.     return this._queryRes;
  124.   }
  125.  
  126.   // Function to get words that has a common Prefix
  127.   // The function call another Recursively Function
  128.   List<String> getAllWithPrefix(String prefix){
  129.     this._queryRes = new List();
  130.  
  131.     _getAllWithPrefix(_root, "" ,0 ,prefix);
  132.     return this._queryRes;
  133.   }
  134.  
  135.   // Function to print all words from the Trie
  136.   // The function call another Recursively Function
  137.   void printAll(){
  138.     _printALl(_root, "");
  139.   }
  140. }
  141.  
  142. /// --- Main File --- ///
  143.  
  144. import 'Trie/Trie.dart';
  145.  
  146. void main() {
  147.   Trie trie = new Trie();
  148.   trie.insert("ismail Ref");
  149.   trie.insert("ishmael Al");
  150.   trie.insert("israel Pl");
  151.  
  152.   print('-------------------------------------------------');
  153.  
  154.   String prefix = "ism";
  155.   List<String> list1 = trie.getAllWithPrefix(prefix);
  156.   for (var word in list1) print(word);
  157.  
  158.   print('-------------------------------------------------');
  159.  
  160.   List<String> list2 = trie.getAll();
  161.   for (var word in list2) print(word);
  162.  
  163.   print('-------------------------------------------------');
  164.  
  165.   trie.printAll();
  166.  
  167.   print('-------------------------------------------------');
  168. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement