-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree Collection.swift
66 lines (51 loc) · 2.33 KB
/
Tree Collection.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// RxPlus © 2019 Constantino Tsarouhas
import Foundation
import DepthKit
/// A bidirectional collection where elements are organised in a tree structure and accessible by index path in pre-order.
///
/// The root node of the underlying tree is represented by the empty index path but is not an element of the tree collection, i.e., `[]` is not a valid index of the tree collection. The first element of the root node is the first element of the tree collection. The last element of the tree collection is the right-most deepest node of the underlying tree.
///
/// - Invariant: `startIndex` is `[0]`; `endIndex` is `[count(in: [])]`.
/// - Invariant: For any valid index path `p` = `[a, b, …]`, every index path `[a, b, …, z]` with `z` an integer between 0 and `count(in: p) - 1` is also valid. In other words, the collection doesn't _skip_ over valid index paths.
///
/// Default implementations are provided for `startIndex`, `endIndex`, `index(before:)`, and `index(after:)` which respect these invariants.
public protocol TreeCollection : BidirectionalCollection where Index == IndexPath {
/// Returns the number of elements directly contained by the node with given index path.
///
/// - Requires: `path` is either the empty index path or a valid index in `self`.
///
/// - Parameter path: The index path of the parent.
///
/// - Returns: The number of elements directly contained by the node at `path`.
func count(in path: IndexPath) -> Int
}
extension TreeCollection {
public var startIndex: IndexPath {
return [0]
}
public var endIndex: IndexPath {
return [count(in: [])]
}
public var isEmpty: Bool {
return count(in: []) == 0
}
public func index(before path: IndexPath) -> IndexPath {
guard let (parent, leaf) = path.splittingLast() else { preconditionFailure("No index path precedes the empty path.") }
return leaf > 0 ? parent.appending(leaf - 1) : parent
}
public func index(after path: IndexPath) -> IndexPath {
// Go deeper if possible.
if count(in: path) > 0 {
return path.appending(0)
}
// Cannot go deeper: find first uncle node (pre-order traversal)
for (ancestry, parent) in path.unfoldingBackward() {
// parent is already visited; try parent's sibling
let uncle = parent + 1
if uncle < count(in: ancestry) {
return ancestry.appending(uncle)
}
}
return endIndex
}
}