Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Trie-generic-lowercase

a guest Feb 13th, 2017 82 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import Foundation
  2.  
  3. protocol Alphabet {
  4.     associatedtype AlphabetCharacter: Comparable, Hashable
  5.  
  6.     func allCharacters() -> [AlphabetCharacter]
  7.  
  8.     init()
  9.  
  10. }
  11.  
  12.  
  13. protocol CharacterSequence {
  14.     associatedtype SequenceCharacter: Comparable, Hashable
  15.     func toSequence() -> [SequenceCharacter]
  16.     init(characters: [SequenceCharacter])
  17. }
  18.  
  19. extension String: CharacterSequence {
  20.     typealias SequenceCharacter = Character
  21.  
  22.     func toSequence() -> [SequenceCharacter] {
  23.         return Array(characters)
  24.     }
  25.  
  26.     init(characters: [SequenceCharacter]) {
  27.         self.init(characters)
  28.     }
  29. }
  30.  
  31. extension Int: CharacterSequence {
  32.      typealias SequenceCharacter = Int8
  33.  
  34.      func toSequence() -> [SequenceCharacter] {
  35.          return String(self).characters.map { character in
  36.              let asString = "\(character)"
  37.              let asInt = Int(asString)!
  38.              let asInt8 = Int8(asInt)
  39.  
  40.              return asInt8
  41.          }
  42.      }
  43.  
  44.      init(characters: [SequenceCharacter]) {
  45.         var value = 0
  46.         var p = 1
  47.  
  48.         for char in characters.reversed() {
  49.             value += p * Int(char)
  50.  
  51.             p *= 10
  52.         }
  53.  
  54.         self.init(value)
  55.      }
  56.  }
  57.  
  58.  
  59. // This defines An alphabet with the latin leters from a to z
  60. class LowercaseLetters: Alphabet {
  61.     typealias AlphabetCharacter = Character
  62.  
  63.     func allCharacters() -> [AlphabetCharacter] {
  64.         return Array("abcdefghijklmnopqrstuvwxyz".characters)
  65.     }
  66.  
  67.     required init() {
  68.  
  69.     }
  70. }
  71.  
  72. class DigitsAlphabet: Alphabet {
  73.     typealias AlphabetCharacter = Int8
  74.  
  75.     func allCharacters() -> [AlphabetCharacter] {
  76.         return Array(0...9)
  77.     }
  78.  
  79.     required init() {
  80.  
  81.     }
  82. }
  83.  
  84.  
  85. class TrieNode<T> where T:Alphabet {
  86.     typealias character = T.AlphabetCharacter
  87.  
  88.     var children: [character:TrieNode<T>] = [:]
  89.     var prefixCount: Int = 0
  90.     var isFinal:Bool = false
  91.  
  92.     init() {
  93.  
  94.     }
  95.  
  96.     ///// called from a PARENT
  97.     func createChildFor(_ character: character) -> TrieNode<T> {
  98.         let node = TrieNode<T>()
  99.  
  100.         children[character] = node
  101.  
  102.         return node
  103.     }
  104.  
  105.     func getOrCreateChildFor(_ character: character) -> TrieNode<T> {
  106.         if let child = children[character] {
  107.             return child
  108.         } else {
  109.             return createChildFor(character)
  110.         }
  111.     }
  112. }
  113.  
  114. class Trie<T> where T:Alphabet {
  115.     typealias character = T.AlphabetCharacter
  116.     typealias Node = TrieNode<T>
  117.  
  118.     var root = Node()
  119.  
  120.     func validate(characters: [character]) -> Bool {
  121.         let allCharacters = T().allCharacters()
  122.         return characters.reduce(true) { result, char in
  123.             return result && allCharacters.contains(char)
  124.         }
  125.     }
  126.  
  127.     func insert<U:CharacterSequence>(_ word: U) where U.SequenceCharacter == character {
  128.         insert(characters: word.toSequence())
  129.     }
  130.  
  131.     func insert(characters: [character]) {
  132.         guard validate(characters: characters) else {
  133.             return
  134.         }
  135.  
  136.         var node = root
  137.         node.prefixCount += 1
  138.         for character in characters {
  139.             node = node.getOrCreateChildFor(character)
  140.             node.prefixCount += 1
  141.         }
  142.         node.isFinal = true
  143.     }
  144.  
  145.     func getNodeFor(characters: [character]) -> Node? {
  146.         var node: Node? = root
  147.         for character in characters {
  148.             node = node?.children[character]
  149.         }
  150.         return node
  151.     }
  152.  
  153.     func query<U:CharacterSequence>(_ word: U) -> Bool where U.SequenceCharacter == character {
  154.         return query(characters: word.toSequence())
  155.     }
  156.  
  157.     func query(characters: [character]) -> Bool {
  158.         guard validate(characters: characters) else {
  159.             return false
  160.         }
  161.         let node = getNodeFor(characters: characters)
  162.  
  163.         if node == nil {
  164.             return false
  165.         }
  166.         return node!.isFinal
  167.     }
  168.  
  169.  
  170.     func getNodeSequence(characters: [character]) -> [(char: character, node: Node)] {
  171.         var node: Node? = root
  172.         var nodes:[(character,Node)] = []
  173.  
  174.         let tup = (characters[0],node!)
  175.         nodes.append(tup)
  176.  
  177.         for character in characters {
  178.             node = node?.children[character]
  179.             if node == nil {
  180.                 return nodes
  181.             }
  182.             let tup = (character, node!)
  183.             nodes.append(tup)
  184.         }
  185.  
  186.         return nodes
  187.     }
  188.  
  189.  
  190.     func remove<U:CharacterSequence>(_ word: U) where U.SequenceCharacter == character {
  191.         remove(characters: word.toSequence())
  192.     }
  193.  
  194.     func remove(characters: [character]) {
  195.         guard validate(characters: characters) else {
  196.             return
  197.         }
  198.  
  199.         let charactersNodes = getNodeSequence(characters: characters)
  200.  
  201.         if charactersNodes.count != characters.count + 1 {
  202.             return
  203.         }
  204.  
  205.         var parent = root
  206.  
  207.         for (char, node) in charactersNodes {
  208.             node.prefixCount -= 1
  209.  
  210.             if node.prefixCount == 0 && node !== root {
  211.                 parent.children.removeValue(forKey: char)
  212.                 break // we deleted the reference to an entire sequence of nodes
  213.                 // swift will delete those nodes from memory
  214.             }
  215.             parent = node
  216.         }
  217.  
  218.         charactersNodes.last?.node.isFinal = false
  219.     }
  220.  
  221.  
  222.  
  223.     func removeWordsPrefix<U:CharacterSequence>(_ word: U) where U.SequenceCharacter == character {
  224.         removeWordsPrefix(characters: word.toSequence())
  225.     }
  226.  
  227.     func removeWordsPrefix(characters: [character]) {
  228.         guard validate(characters: characters) else {
  229.             return
  230.         }
  231.  
  232.         let charactersNodes = getNodeSequence(characters: characters)
  233.  
  234.         if charactersNodes.count != characters.count + 1 {
  235.             return
  236.         }
  237.  
  238.         let decreasePrefix = charactersNodes.last!.node.prefixCount
  239.  
  240.         var parent = root
  241.  
  242.         for (char, node) in charactersNodes {
  243.             node.prefixCount -= decreasePrefix
  244.             if node.prefixCount == 0 && node !== root {
  245.                 parent.children.removeValue(forKey: char)
  246.                 break // we deleted the reference to an entire sequence of nodes
  247.                     // swift will delete those nodes from memory
  248.             }
  249.             parent = node
  250.         }
  251.     }
  252.  
  253.     func kthWord<U:CharacterSequence>(atIndex index: Int, from node: Node? = nil, characters: [character] = []) -> U? where U.SequenceCharacter == character {
  254.         let node = node ?? root
  255.  
  256.         if index == 0 && node.isFinal {
  257.             return U(characters: characters)
  258.         }
  259.  
  260.         var skipped = 0
  261.         if node.isFinal {
  262.           skipped += 1
  263.         }
  264.  
  265.         for char in T().allCharacters() {
  266.             if let child = node.children[char] {
  267.                 if skipped + child.prefixCount > index {
  268.                     // find the word in the current child
  269.                     return kthWord(atIndex: index - skipped, from: child, characters: characters + [char])
  270.                 } else {
  271.                     // skip words from the current child
  272.                     skipped += child.prefixCount
  273.                 }
  274.             }
  275.  
  276.         }
  277.  
  278.         return nil
  279.     }
  280.  
  281.  
  282.     func wordsSamePrefix<U:CharacterSequence>(_ word: U) -> Int where U.SequenceCharacter == character {
  283.         return wordsSamePrefix(characters: word.toSequence())
  284.     }
  285.  
  286.     func wordsSamePrefix(characters: [character]) -> Int {
  287.         guard validate(characters: characters) else {
  288.             return 0
  289.         }
  290.  
  291.         if let node = getNodeFor(characters: characters) {
  292.             return node.prefixCount
  293.         } else {
  294.             return 0
  295.         }
  296.     }
  297.  
  298. }
  299.  
  300.  
  301.  
  302. let myTrie = Trie<LowercaseLetters>()
  303.  
  304. myTrie.insert("to");
  305. myTrie.insert("tour");
  306. myTrie.insert("tea");
  307. myTrie.insert("roll");
  308. myTrie.insert("round");
  309.  
  310. myTrie.remove("roLl")
  311. print (myTrie.query("roll"))      // true
  312.  
  313. myTrie.removeWordsPrefix("r")
  314. print (myTrie.query("roll"))      // false
  315. print(myTrie.wordsSamePrefix("t"))  // 3
  316.  
  317. // current words in our dictionary :tea, to, tour
  318. let word: String = myTrie.kthWord(atIndex: 2)!
  319. print(word) // tour
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