8000 Refactored implementation of Trie. Leaving the old implementation in … · lency/swift-algorithm-club@1da1118 · GitHub
[go: up one dir, main page]
Skip to content

Commit 1da1118

Browse files
Kelvin LauKelvin Lau
Kelvin Lau
authored and
Kelvin Lau
committed
Refactored implementation of Trie. Leaving the old implementation in a folder for future reference.
1 parent 8a679ff commit 1da1118

File tree

5 files changed

+80
-267
lines changed

5 files changed

+80
-267
lines changed

‎Trie/trie.swift renamed to ‎Trie/Old Implementation/trie.swift

File renamed without changes.

‎Trie/Trie.playground/Contents.swift

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
let trie = Trie()
2+
3+
trie.insert(word: "apple")
4+
trie.insert(word: "ap")
5+
trie.insert(word: "a")
6+
7+
trie.contains(word: "apple")
8+
trie.contains(word: "ap")
9+
trie.contains(word: "a")
10+
11+
trie.remove(word: "apple")
12+
trie.contains(word: "a")
13+
trie.contains(word: "apple")
14+
15+
trie.insert(word: "apple")
16+
trie.contains(word: "apple")

‎Trie/Trie.playground/Sources/Node.swift

Lines changed: 14 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -1,64 +1,21 @@
1-
/// A Trie (prefix tree)
2-
///
3-
/// Some of the functionality of the trie makes use of the Queue implementation for this project
4-
///
5-
/// Every node in the Trie stores a bit of information pertaining to what it references:
6-
/// -Character (letter of an inserted word)
7-
/// -Parent (Letter that comes before the current letter in some word)
8-
/// -Children (Words that have more letters than available in the prefix)
9-
/// -isAWord (Does the current letter mark the end of a known inserted word?)
10-
/// -visited (Mainly for the findPrefix() function)
11-
public class Node {
12-
public var character: String
13-
public var parent: Node?
14-
public var children: [String: Node]
15-
public var isAWord: Bool
16-
public var visited: Bool // only for findPrefix
1+
public final class TrieNode<T: Hashable> {
2+
public var value: T?
3+
public weak var parent: TrieNode?
4+
public var children: [T: TrieNode] = [:]
5+
public var isTerminating = false
176

18-
init(character: String, parent: Node?) {
19-
self.character = character
20-
self.children = [:]
21-
self.isAWord = false
22-
self.parent = parent
23-
self.visited = false
24-
}
25-
26-
/// Returns `true` if the node is a leaf node, false otherwise.
27-
var isLeaf: Bool {
28-
return children.count == 0
29-
}
30-
31-
/// Changes the parent of the current node to the passed in node.
32-
///
33-
/// - parameter node: A `Node` object.
34-
func setParent(node: Node) {
35-
parent = node
36-
}
7+
init() {}
378

38-
/// Returns the child node that holds the specific passed letter.
39-
///
40-
/// - parameter character: A `String`
41-
///
42-
/// - returns: The `Node` object that contains the `character`.
43-
func getChildAt(character: String) -> Node {
44-
return children[character]!
45-
}
46-
47-
/// Returns whether or not the current node marks the end of a valid word.
48-
var isValidWord: Bool {
49-
return isAWord
50-
}
51-
52-
53-
/// Returns whether or not the current node is the root of the trie.
54-
var isRoot: Bool {
55-
return character == ""
9+
init(value: T, parent: TrieNode? = nil) {
10+
self.value = value
11+
self.parent = parent
5612
}
5713
}
5814

59-
// MARK: - CustomStringConvertible
60-
extension Node: CustomStringConvertible {
61-
public var description: String {
62-
return ""
15+
// MARK: - Insertion
16+
public extension TrieNode {
17+
func add(child: T) {
18+
guard children[child] == nil else { return }
19+
children[child] = TrieNode(value: child, parent: self)
6320
}
6421
}

‎Trie/Trie.playground/Sources/Queue.swift

Lines changed: 0 additions & 31 deletions
This file was deleted.

‎Trie/Trie.playground/Sources/Trie.swift

Lines changed: 50 additions & 179 deletions
14
Original file line numberDiff line numberDiff line change
@@ -2,211 +2,82 @@
22
/// -root (the root of the trie)
33
/// -wordList (the words that currently exist in the trie)
44
/// -wordCount (the number of words in the trie)
5-
public class Trie {
6-
private var root = Node(character: "", parent: nil)
7-
private(set) var wordList: [String] = []
8-
private(set) var wordCount = 0
5+
public final class Trie {
6+
typealias Node = TrieNode<Character>
7+
fileprivate let root: Node
98

10-
init(words: Set<String>) {
11-
words.forEach { insert(word: $0) }
9+
public init() {
10+
root = TrieNode<Character>()
1211
}
13-
14-
/// Merge two `Trie` objects into one and returns the merged `Trie`
15-
///
16-
/// - parameter other: Another `Trie`
17-
///
18-
/// - returns: The newly unioned `Trie`.
19-
func merge(other: Trie) -> Trie {
20-
let newWordList = Set(wordList + other.wordList)
21-
return Trie(words: newWordList)
22-
}
23-
24-
/// Looks for a specific key and returns a tuple that has a reference to the node (if found) and true/false depending on if it was found.
25-
///
26-
/// - parameter key: A `String` that you would like to find.
27-
///
28-
/// - returns: A tuple containing the an optional `Node`. If the key is found, it will return a non-nil `Node`. The second part of the tuple contains a bool indicating whether it was found or not.
29-
func find(key: String) -> (node: Node?, found: Bool) {
12+
}
13+
+
// MARK: - Basic Methods
15+
public extension Trie {
16+
func insert(word: String) {
17+
guard !word.isEmpty else { return }
3018
var currentNode = root
3119

32-
for character in key.characters {
33-
if currentNode.children["\(character)"] == nil {
34-
return (nil, false)
35-
}
36-
currentNode = currentNode.children["\(character)"]!
37-
}
38-
return (currentNode, currentNode.isValidWord)
39-
}
40-
41-
/// Returns true if the `Trie` is empty, false otherwise.
42-
var isEmpty: Bool {
43-
return wordCount == 0
44-
}
45-
46-
/// Checks if the a word is currently in the `Trie`.
47-
///
48-
/// - parameter word: A `String` you want to check.
49-
///
50-
/// - returns: Returns `true` if the word exists in the `Trie`. False otherwise.
51-
func contains(word: String) -> Bool {
52-
return find(key: word.lowercased()).found
53-
}
54-
55-
func isPrefix(_ prefix: String) -> (node: Node?, found: Bool) {
56-
let prefix = prefix.lowercased()
57-
var currentNode = root
20+
var characters = Array(word.lowercased().characters)
21+
var currentIndex = 0
5822

59-
for character in prefix.characters {
60-
if currentNode.children["\(character)"] == nil {
61-
return (nil, false)
23+
while currentIndex < characters.count {
24+
let character = characters[currentIndex]
25+
if let child = currentNode.children[character] {
26+
currentNode = child
27+
} else {
28+
currentNode.add(child: character)
29+
currentNode = currentNode.children[character]!
6230
}
6331

64-
currentNode = currentNode.children["\(character)"]!
65-
}
66-
67-
if currentNode.children.count > 0 {
68-
return (currentNode, true)
32+
currentIndex += 1
33+
if currentIndex == characters.count {
34+
currentNode.isTerminating = true
35+
}
6936
}
70-
71-
return (nil, false)
7237
}
7338

74-
/// Inserts a word into the trie. Returns a tuple containing the word attempted to tbe added, and true/false depending on whether or not the insertion was successful.
75-
///
76-
/// - parameter word: A `String`.
77-
///
78-
/// - returns: A tuple containing the word attempted to be added, and whether it was successful.
79-
@discardableResult func insert(word: String) -> (word: String, inserted: Bool) {
80-
let word = word.lowercased()
81-
guard !contains(word: word), !word.isEmpty else { return (word, false) }
82-
39+
func contains(word: String) -> Bool {
40+
guard !word.isEmpty else { return false }
8341
var currentNode = root
84-
var length = word.characters.count
8542

86-
var index = 0
87-
var character = word.characters.first!
43+
var characters = Array(word.lowercased().characters)
44+
var currentIndex = 0
8845

89-
while let child = currentNode.children["\(character)"] {
46+
while currentIndex < characters.count, let child = currentNode.children[characters[currentIndex]] {
9047
currentNode = child
91-
length -= 1
92-
index += 1
93-
94-
if length == 0 {
95-
currentNode.isAWord = true
96-
wordList.append(word)
97-
wordCount += 1
98-
return (word, true)
99-
}
100-
101-
character = Array(word.characters)[index]
102-
}
103-
104-
let remainingCharacters = String(word.characters.suffix(length))
105-
for character in remainingCharacters.characters {
106-
currentNode.children["\(character)"] = Node(character: "\(character)", parent: currentNode)
107-
currentNode = currentNode.children["\(character)"]!
48+
currentIndex += 1
10849
}
10950

110-
currentNode.isAWord = true
111-
wordList.append(word)
112-
wordCount += 1
113-
return (word, true)
114-
}
115-
116-
/// Attempts to insert all words from input array. Returns a tuple containing the input array and true if some of the words were successfully added, false if none were added.
117-
///
118-
/// - parameter words: An array of `String` objects.
119-
///
120-
/// - returns: A tuple stating whether all the words were inserted.
121-
func insert(words: [String]) -> (wordList: [String], inserted: Bool) {
122-
var successful: Bool = false
123-
for word in wordList {
124-
successful = insert(word: word).inserted || successful
51+
if currentIndex == characters.count && currentNode.isTerminating {
52+
return true
53+
} else {
54+
return false
12555
}
126-
127-
return (wordList, successful)
12856
}
12957

130-
/// Removes the specified key from the `Trie` if it exists, returns tuple containing the word attempted to be removed and true/false if the removal was successful.
131-
///
132-
/// - parameter word: A `String` to be removed.
133-
///
134-
/// - returns: A tuple containing the word to be removed, and a `Bool` indicating whether removal was successful or not.
135-
@discardableResult func remove(word: String) -> (word: String, removed: Bool) {
136-
let word = word.lowercased()
137-
138-
guard contains(word: word) else { return (word, false) }
58+
func remove(word: String) {
59+
guard !word.isEmpty else { return }
13960
var currentNode = root
14061

141-
for character in word.characters {
142-
currentNode = currentNode.getChildAt(character: "\(character)")
62+
var characters = Array(word.lowercased().characters)
63+
var currentIndex = 0
64+
65+
while currentIndex < characters.count {
66+
let character = characters[currentIndex]
67+
guard let child = currentNode.children[character] else { return }
68+
currentNode = child
69+
currentIndex += 1
14370
}
14471

14572
if currentNode.children.count > 0 {
146-
currentNode.isAWord = false
73+
currentNode.isTerminating = false
14774
} else {
148-
var character = currentNode.character
149-
while currentNode.children.count == 0 && !currentNode.isRoot {
150-
currentNode = currentNode.parent!
151-
currentNode.children[character]!.parent = nil
152-
character = currentNode.character
153-
}
154-
}
155-
156-
wordCount -= 1
157-
158-
var index = 0
159-
for item in wordList {
160-
if item == word {
161-
wordList.remove(at: index)
162-
}
163-
index += 1
164-
}
165-
166-
return (word, true)
167-
}
168-
169-
func find(prefix: String) -> [String] {
170-
guard isPrefix(prefix).found else { return [] }
171-
var queue = Queue<Node>()
172-
let node = isPrefix(prefix).node!
173-
174-
var wordsWithPrefix: [String] = []
175-
let word = prefix
176-
var tmp = ""
177-
queue.enqueue(element: node)
178-
179-
while let current = queue.dequeue() {
180-
for (_, child) in current.children {
181-
if !child.visited {
182-
queue.enqueue(element: child)
183-
child.visited = true
184-
if child.isValidWord {
185-
var currentNode = child
186-
while currentNode !== node {
187-
tmp += currentNode.character
188-
currentNode = currentNode.parent!
189-
}
190-
tmp = "\(tmp.characters.reversed())"
191-
wordsWithPrefix.append(word + tmp)
192-
tmp = ""
193-
}
194-
}
75+
var character = currentNode.value
76+
while currentNode.children.count == 0, let parent = currentNode.parent, !parent.isTerminating {
77+
currentNode = parent
78+
currentNode.children[character!] = nil
79+
character = currentNode.value
19580
}
19681
}
197-
198-
return wordsWithPrefix
199-
}
200-
201-
func removeAll() {
202-
for word in wordList {
203-
remove(word: word)
204-
}
205-
}
206-
}
207-
208-
extension Trie: CustomStringConvertible {
209-
public var description: String {
210-
return ""
21182
}
21283
}

0 commit comments

Comments
 (0)
0