8000 Updates readme to reference new class to handle encoding and decoding… · datengx/swift-algorithm-club@eeea202 · GitHub
[go: up one dir, main page]
Skip to content

Commit eeea202

Browse files
kelvinlauKLremlostime
kelvinlauKL
authored and
remlostime
committed
Updates readme to reference new class to handle encoding and decoding operations
1 parent 8bc6ab7 commit eeea202

File tree

1 file changed

+65
-38
lines changed

1 file changed

+65
-38
lines changed

‎Encode and Decode Tree/readme.md

Lines changed: 65 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ Encoding and decoding are synonyms to *serializing* and *deserializing* trees.
1313
As a reference, the following code represents the typical `Node` type of a binary tree:
1414

1515
```swift
16-
class BinaryNode<Element: Comparable> {
16+
class BinaryNode<Element: Comparable & Encodable> {
1717
var data: Element
1818
var leftChild: BinaryNode?
1919
var rightChild: BinaryNode?
@@ -22,6 +22,24 @@ class BinaryNode<Element: Comparable> {
2222
}
2323
```
2424

25+
Your encoding and decoding methods will reside in the `BinaryNodeEncoder` and `BinaryNodeDecoder` classes:
26+
27+
```swift
28+
class BinaryNodeCoder {
29+
30+
// transforms nodes into string representation
31+
func encode<T>(_ node: BinaryNode<T>) throws -> String where T: Encodable {
32+
33+
}
34+
35+
// transforms string into `BinaryNode` representation
36+
func decode<T>(_ node: BinaryNode<T>Type, from string: String)
37+
throws -> BinaryNode<T> where T: Decodable {
38+
39+
}
40+
}
41+
```
42+
2543
## Encoding
2644

2745
As mentioned before, there are different ways to do encoding. For no particular reason, you'll opt for the following rules:
@@ -32,27 +50,9 @@ As mentioned before, there are different ways to do encoding. For no particular
3250
Here's an example of this operation in code:
3351

3452
```swift
35-
extension BinaryNode {
36-
// 1
37-
fileprivate var separator: String { return "," }
38-
fileprivate var nilNode: String { return "X" }
39-
40-
// 2
41-
var encodedString: String {
42-
var str = ""
43-
preOrderTraversal { data in
44-
if let data = data {
45-
let string = String(describing: data)
46-
str.append(string)
47-
} else {
48-
str.append(nilNode)
49-
}
50-
str.append(separator)
51-
}
52-
return str
53-
}
53+
fileprivate extension BinaryNode {
5454

55-
// 3
55+
// 1
5656
func preOrderTraversal(visit: (Element?) throws -> ()) rethrows {
5757
try visit(data)
5858

@@ -69,15 +69,41 @@ extension BinaryNode {
6969
}
7070
}
7171
}
72+
73+
class BinaryNodeCoder {
74+
75+
// 2
76+
private var separator: String { return "," }
77+
78+
// 3
79+
private var nilNode: String { return "X" }
80+
81+
// 4
82+
func encode<T: Encodable>(_ node: BinaryNode<T>) -> String {
83+
var str = ""
84+
node.preOrderTraversal { data in
85+
if let data = data {
86+
let string = String(describing: data)
87+
str.append(string)
88+
} else {
89+
str.append(nilNode)
90+
}
91+
str.append(separator)
92+
}
93+
return str
94+
}
95+
96+
// ...
97+
}
7298
```
7399

74100
Here's a high level overview of the above code:
75101

76-
1. `separator` is a way to distinguish the nodes in a string. To illustrate its importance, consider the following encoded string "banana". How did the tree structure look like before encoding? Without the `separator`, you can't tell.
102+
2. `separator` is a way to distinguish the nodes in a string. To illustrate its importance, consider the following encoded string "banana". How did the tree structure look like before encoding? Without the `separator`, you can't tell.
77103

78-
2. `encodedString` is the result of the encoding process. Returns a string representation of the tree. For example: "ba,nana,nil" represents a tree with two nodes - "ba" and "nana" - in pre-order format.
104+
3. `nilNode` is used to identify empty children. This a necesssary piece of information to retain in order to rebuild the tree later.
79105

80-
3. It is interesting to note that this pre-order traversal implementation also emits `nil` values in place of absent children.
106+
4. `encode` returns a `String` representation of the `BinaryNode`. For example: "ba,nana,nil" represents a tree with two nodes - "ba" and "nana" - in pre-order format.
81107

82108
## Decoding
83109

@@ -96,28 +122,29 @@ The implementation also added a few important details:
96122
These details will shape your `decode` operation. Here's a possible implementation:
97123

98124
```swift
99-
extension BinaryNode {
100125

126+
class BinaryNodeCoder {
127+
128+
// ...
129+
101130
// 1
102-
public static func decode(from str: String) -> AVLNode<String>? {
131+
func decode<T: Decodable>(_ string: String) -> BinaryNode<T>? {
103132
let components = encoded.lazy.split(separator: separator).reversed().map(String.init)
104133
return decode(from: components)
105134
}
106-
107-
public static func decode(from array: inout [String])
108-
-> AVLNode<String>? {
135+
136+
// 2
137+
private func decode(from array: inout [String]) -> AVLNode<String>? {
138+
guard !array.isEmpty else { return nil }
139+
let value = array.removeLast()
140+
guard value != "\(nilNode)" else { return nil }
109141

110-
guard !array.isEmpty else { return nil }
111-
let value = array.removeLast()
112-
guard value != "\(nilNode)" else { return nil }
113-
114-
let node = AVLNode<String>(value: value)
115-
node.leftChild = decode(from: &array)
116-
node.rightChild = decode(from: &array)
117-
return node
142+
let node = AVLNode<String>(value: value)
143+
node.leftChild = decode(from: &array)
144+
node.rightChild = decode(from: &array)
145+
return node
118146
}
119147
}
120-
```
121148

122149
Here's a high level overview of the above code:
123150

0 commit comments

Comments
 (0)
0