10000 Adds a playground with the first step of refactoring the implementation. · lina1/swift-algorithm-club@8a679ff · GitHub
[go: up one dir, main page]
Skip to content

Commit 8a679ff

Browse files
Kelvin LauKelvin Lau
Kelvin Lau
authored and
Kelvin Lau
committed
Adds a playground with the first step of refactoring the implementation.
1 parent 7480ea4 commit 8a679ff

File tree

6 files changed

+318
-0
lines changed

6 files changed

+318
-0
lines changed

‎Trie/Trie.playground/Contents.swift

Whitespace-only changes.

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

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
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
17+
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+
}
37+
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 == ""
56+
}
57+
}
58+
59+
// MARK: - CustomStringConvertible
60+
extension Node: CustomStringConvertible {
61+
public var description: String {
62+
return ""
63+
}
64+
}

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

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/// Queue implementation taken from the repository.
2+
public struct Queue<T> {
3+
private var array: [T?] = []
4+
private var head = 0
5+
6+
public var isEmpty: Bool {
7+
return count == 0
8+
}
9+
10+
public var count: Int {
11+
return array.count - head
12+
}
13+
14+
public mutating func enqueue(element: T) {
15+
array.append(element)
16+
}
17+
18+
public mutating func dequeue() -> T? {
19+
guard head < array.count, let element = array[head] else { return nil }
20+
array[head] = nil
21+
head += 1
22+
23+
let percentage = Double(head) / Double(array.count)
24+
if array.count > 50 && percentage > 0.25 {
25+
array.removeFirst(head)
26+
head = 0
27+
}
28+
29+
return element
30+
}
31+
}

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

Lines changed: 212 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,212 @@
1+
/// The Trie class has the following attributes:
2+
/// -root (the root of the trie)
3+
/// -wordList (the words that currently exist in the trie)
4+
/// -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
9+
10+
init(words: Set<String>) {
11+
words.forEach { insert(word: $0) }
12+
}
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) {
30+
var currentNode = root
31+
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
58+
59+
for character in prefix.characters {
60+
if currentNode.children["\(character)"] == nil {
61+
return (nil, false)
62+
}
63+
64+
currentNode = currentNode.children["\(character)"]!
65+
}
66+
67+
if currentNode.children.count > 0 {
68+
return (currentNode, true)
69+
}
70+
71+
return (nil, false)
72+
}
73+
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+
83+
var currentNode = root
84+
var length = word.characters.count
85+
86+
var index = 0
87+
var character = word.characters.first!
88+
89+
while let child = currentNode.children["\(character)"] {
90+
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)"]!
108+
}
109+
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
741A 125+
}
126+
127+
return (wordList, successful)
128+
}
129+
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) }
139+
var currentNode = root
140+
141+
for character in word.characters {
142+
currentNode = currentNode.getChildAt(character: "\(character)")
143+
}
144+
145+
if currentNode.children.count > 0 {
146+
currentNode.isAWord = false
147+
} 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+
}
195+
}
196+
}
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 ""
211+
}
212+
}

‎Trie/Trie.playground/contents.xcplayground

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
2+
<playground version='5.0' target-platform='ios'>
3+
<timeline fileName='timeline.xctimeline'/>
4+
</playground>

‎Trie/Trie.playground/playground.xcworkspace/contents.xcworkspacedata

Lines changed: 7 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)
0