8000 Merge pull request #152 from raywenderlich/swift-lint-branch · rubonz/swift-algorithm-club@00ae153 · GitHub
[go: up one dir, main page]
Skip to content

Commit 00ae153

Browse files
kelvinlauKLkelvinlauKL
authored
Merge pull request kodecocodes#152 from raywenderlich/swift-lint-branch
Swift lint branch
2 parents 4e672f8 + 6c06dbd commit 00ae153

File tree

157 files changed

+1275
-1231
lines changed
  • TopologicalSort1.swift
  • TopologicalSort3.swift
  • TopologicalSort1.swift
  • TopologicalSort3.swift
  • Treap
  • Tree
  • Trie
  • Two-Sum Problem
  • Union-Find
  • install_swiftlint.sh

    • Some content is hidden

    Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

    157 files changed

    +1275
    -1231
    lines changed

    ‎.swiftlint.yml

    Lines changed: 25 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -0,0 +1,25 @@
    1+
    cyclomatic_complexity: 12
    2+
    file_length: 550
    3+
    function_body_length: 80
    4+
    function_parameter_count: 8
    5+
    line_length: 150
    6+
    type_body_length: 300
    7+
    variable_name:
    8+
    min_length:
    9+
    error: 1
    10+
    warning: 1
    11+
    excluded:
    12+
    - N
    13+
    14+
    disabled_rules:
    15+
    - valid_docs
    16+
    17+
    custom_rules:
    18+
    smiley_face:
    19+
    name: "Smiley Face"
    20+
    regex: "(\:\))"
    21+
    match_kinds:
    22+
    - comment
    23+
    - string
    24+
    message: "A closing parenthesis smiley :) creates a half-hearted smile, and thus is not preferred. Use :]"
    25+
    severity: warning

    ‎.travis.yml

    Lines changed: 4 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -2,6 +2,10 @@ language: objective-c
    22
    osx_image: xcode7.3
    33
    sudo: false
    44

    5+
    install:
    6+
    7+
    - ./install_swiftlint.sh
    8+
    59
    script:
    610

    711
    - xctool test -project ./All-Pairs\ Shortest\ Paths/APSP/APSP.xcodeproj -scheme APSPTests

    ‎AVL Tree/AVLTree.playground/Contents.swift

    Lines changed: 1 addition & 1 deletion
    Original file line numberDiff line numberDiff line change
    @@ -24,4 +24,4 @@ tree.delete(5)
    2424
    tree.delete(2)
    2525
    tree.delete(1)
    2626
    tree.delete(4)
    27-
    tree.delete(3)
    27+
    tree.delete(3)

    ‎AVL Tree/Tests/AVLTreeTests.swift

    Lines changed: 19 additions & 21 deletions
    Original file line numberDiff line numberDiff line change
    @@ -9,15 +9,15 @@
    99
    import XCTest
    1010

    1111
    class AVLTreeTests: XCTestCase {
    12-
    13-
    var tree : AVLTree<Int, String>?
    12+
    13+
    var tree: AVLTree<Int, String>?
    1414

    1515
    override func setUp() {
    1616
    super.setUp()
    17-
    17+
    1818
    tree = AVLTree()
    1919
    }
    20-
    20+
    2121
    override func tearDown() {
    2222
    // Put teardown code here. This method is called after the invocation of each test method in the class.
    2323
    super.tearDown()
    @@ -60,8 +60,8 @@ class AVLTreeTests: XCTestCase {
    6060
    }
    6161

    6262
    func testEmptyInitialization() {
    63-
    let tree = AVLTree<Int,String>()
    64-
    63+
    let tree = AVLTree<Int, String>()
    64+
    6565
    XCTAssertEqual(tree.size, 0)
    6666
    XCTAssertNil(tree.root)
    6767
    }
    @@ -71,45 +71,45 @@ class AVLTreeTests: XCTestCase {
    7171
    self.tree?.insert(5, "E")
    7272
    }
    7373
    }
    74-
    74+
    7575
    func testMultipleInsertionsPerformance() {
    7676
    self.measureBlock {
    7777
    self.tree?.autopopulateWithNodes(50)
    7878
    }
    7979
    }
    80-
    80+
    8181
    func testSearchExistentOnSmallTreePerformance() {
    8282
    self.measureBlock {
    8383
    self.tree?.search(2)
    8484
    }
    8585
    }
    86-
    86+
    8787
    func testSearchExistentElementOnLargeTreePerformance() {
    8888
    self.measureBlock {
    8989
    self.tree?.autopopulateWithNodes(500)
    9090
    self.tree?.search(400)
    9191
    }
    9292
    }
    93-
    93+
    9494
    func testMinimumOnPopulatedTree() {
    9595
    self.tree?.autopopulateWithNodes(500)
    9696
    let min = self.tree?.root?.minimum()
    9797
    XCTAssertNotNil(min, "Minimum function not working")
    9898
    }
    99-
    99+
    100100
    func testMinimumOnSingleTreeNode() {
    101101
    let treeNode = TreeNode(key: 1, payload: "A")
    102102
    let min = treeNode.minimum()
    103-
    103+
    104104
    XCTAssertNotNil(min, "Minimum on single node should be returned")
    105-
    XCTAssertEqual(min?.payload,treeNode.payload)
    105+
    XCTAssertEqual(min?.payload, treeNode.payload)
    106106
    }
    107-
    107+
    108108
    func testDeleteExistentKey() {
    109109
    self.tree?.delete(1)
    110110
    XCTAssertNil(self.tree?.search(1), "Key should not exist anymore")
    111111
    }
    112-
    112+
    113113
    func testDeleteNotExistentKey() {
    114114
    self.tree?.delete(1056)
    115115
    XCTAssertNil(self.tree?.search(1056), "Key should not exist")
    @@ -122,15 +122,15 @@ class AVLTreeTests: XCTestCase {
    122122
    XCTAssertEqual(tree.size, i + 1, "Insert didn't update size correctly!")
    123123
    }
    124124
    }
    125-
    125+
    126126
    func testDelete() {
    127127
    let permutations = [
    128128
    [5, 1, 4, 2, 3],
    129129
    [2, 3, 1, 5, 4],
    130130
    [4, 5, 3, 2, 1],
    131131
    [3, 2, 5, 4, 1],
    132132
    ]
    133-
    133+
    134134
    for p in permutations {
    135135
    let tree = AVLTree<Int, String>()
    136136

    @@ -151,8 +151,8 @@ class AVLTreeTests: XCTestCase {
    151151
    }
    152152

    153153
    extension AVLTree where Key : SignedIntegerType {
    154-
    func autopopulateWithNodes(count : Int) {
    155-
    var k : Key = 1
    154+
    func autopopulateWithNodes(count: Int) {
    155+
    var k: Key = 1
    156156
    for _ in 0...count {
    157157
    self.insert(k)
    158158
    k = k + 1
    @@ -185,5 +185,3 @@ extension AVLTree where Key : SignedIntegerType {
    185185
    }
    186186
    }
    187187
    }
    188-
    189-

    ‎AVL Tree/Tests/TreeNodeTests.swift

    Lines changed: 23 additions & 23 deletions
    Original file line numberDiff line numberDiff line change
    @@ -9,50 +9,50 @@
    99
    import XCTest
    1010

    1111
    class TreeNodeTests: XCTestCase {
    12-
    13-
    var root : TreeNode<String,String>?
    14-
    var left : TreeNode<String,String>?
    15-
    var right : TreeNode<String,String>?
    16-
    12+
    13+
    var root: TreeNode<String, String>?
    14+
    var left: TreeNode<String, String>?
    15+
    var right: TreeNode<String, String>?
    16+
    1717
    override func setUp() {
    1818
    super.setUp()
    1919

    20-
    left = TreeNode<String,String>(key: "Name", payload: "Left")
    21-
    right = TreeNode<String,String>(key: "Name", payload: "Right")
    22-
    root = TreeNode<String,String>(key: "Name", payload: "Root", leftChild: left, rightChild: right, parent: nil, height: 0)
    20+
    left = TreeNode<String, String>(key: "Name", payload: "Left")
    21+
    right = TreeNode<String, String>(key: "Name", payload: "Right")
    22+
    root = TreeNode<String, String>(key: "Name", payload: "Root", leftChild: left, rightChild: right, parent: nil, height: 0)
    2323
    }
    24-
    24+
    2525
    override func tearDown() {
    2626
    // Put teardown code here. This method is called after the invocation of each test method in the class.
    2727
    super.tearDown()
    2828
    }
    29-
    10000
    30-
    29+
    30+
    3131
    func testSingleNodeCreationNOPayload() {
    32-
    let treeNode = TreeNode<String,String>(key: "Building")
    32+
    let treeNode = TreeNode<String, String>(key: "Building")
    3333
    XCTAssertNil(treeNode.payload, "Payload for this case should be nil")
    3434
    }
    35-
    35+
    3636
    func testSingleNodeCreationWithPayload() {
    3737
    XCTAssertNotNil(self.root!, "Payload for this case should not be nil")
    3838
    }
    39-
    39+
    4040
    func testIsRoot() {
    4141
    XCTAssertTrue(self.root!.isRoot)
    4242
    }
    43-
    43+
    4444
    func testNotIsLeaf() {
    4545
    XCTAssertFalse(self.root!.isLeaf, "root node is not leaf")
    4646
    }
    47-
    47+
    4848
    func testNotIsLeftChild() {
    4949
    XCTAssertFalse(self.root!.isLeftChild, "root node is not left child")
    5050
    }
    51-
    51+
    5252
    func testNotIsRightChild() {
    5353
    XCTAssertFalse(self.root!.isRightChild, "root node is not right child")
    5454
    }
    55-
    55+
    5656
    func testIsLeftChild() {
    5757
    XCTAssertTrue(self.left!.isLeftChild)
    5858
    }
    @@ -64,21 +64,21 @@ class TreeNodeTests: XCTestCase {
    6464
    func isLeaf() {
    6565
    XCTAssertTrue(self.left!.isLeaf)
    6666
    }
    67-
    67+
    6868
    func testHasAnyChild() {
    6969
    XCTAssertTrue(self.root!.hasAnyChild)
    7070
    }
    71-
    71+
    7272
    func testNotHasAnyChild() {
    7373
    XCTAssertFalse(self.left!.hasAnyChild)
    7474
    }
    75-
    75+
    7676
    func testHasBothChildren() {
    7777
    XCTAssertTrue(self.root!.hasBothChildren)
    7878
    }
    79-
    79+
    8080
    func testNotHasBothChildren() {
    8181
    XCTAssertFalse(self.left!.hasBothChildren)
    8282
    }
    83-
    83+
    8484
    }

    ‎All-Pairs Shortest Paths/APSP/APSP/APSP.swift

    Lines changed: 5 additions & 2 deletions
    Original file line numberDiff line numberDiff line change
    @@ -9,7 +9,9 @@ import Foundation
    99
    import Graph
    1010

    1111
    /**
    12-
    `APSPAlgorithm` is a protocol for encapsulating an All-Pairs Shortest Paths algorithm. It provides a single function `apply` that accepts a subclass of `AbstractGraph` and returns an object conforming to `APSPResult`.
    12+
    `APSPAlgorithm` is a protocol for encapsulating an All-Pairs Shortest Paths algorithm.
    13+
    It provides a single function `apply` that accepts a subclass of `AbstractGraph` and
    14+
    returns an object conforming to `APSPResult`.
    1315
    */
    1416
    public protocol APSPAlgorithm {
    1517

    @@ -21,7 +23,8 @@ public protocol APSPAlgorithm {
    2123
    }
    2224

    2325
    /**
    24-
    `APSPResult` is a protocol defining functions `distance` and `path`, allowing for opaque queries into the actual data structures that represent the APSP solution according to the algorithm used.
    26+
    `APSPResult` is a protocol defining functions `distance` and `path`, allowing for opaque
    27+
    queries into the actual data structures that represent the APSP solution according to the algorithm used.
    2528
    */
    2629
    public protocol APSPResult {
    2730

    ‎All-Pairs Shortest Paths/APSP/APSP/FloydWarshall.swift

    Lines changed: 26 additions & 15 deletions
    Original file line numberDiff line numberDiff line change
    @@ -51,12 +51,16 @@ public struct FloydWarshall<T where T: Hashable>: APSPAlgorithm {
    5151
    }
    5252

    5353
    /**
    54-
    For each iteration of `intermediateIdx`, perform the comparison for the dynamic algorith, checking for each pair of start/end vertices, whether a path taken through another vertex produces a shorter path.
    54+
    For each iteration of `intermediateIdx`, perform the comparison for the dynamic algorith,
    55+
    checking for each pair of start/end vertices, whether a path taken through another vertex
    56+
    produces a shorter path.
    5557

    5658
    - complexity: `Θ(V^2)` time/space
    57-
    - returns: a tuple containing the next distance matrix with weights of currently known shortest paths and the corresponding predecessor matrix
    59+
    - returns: a tuple containing the next distance matrix with weights of currently known
    60+
    shortest paths and the corresponding predecessor matrix
    5861
    */
    59-
    static private func nextStep<T>(intermediateIdx: Int, previousDistances: Distances, previousPredecessors: Predecessors, graph: AbstractGraph<T>) -> StepResult {
    62+
    static private func nextStep<T>(intermediateIdx: Int, previousDistances: Distances,
    63+
    previousPredecessors: Predecessors, graph: AbstractGraph<T>) -> StepResult {
    6064

    6165
    let vertexCount = graph.vertices.count
    6266
    var nextDistances = Array(count: vertexCount, repeatedValue: Array(count: vertexCount, repeatedValue: Double.infinity))
    @@ -85,9 +89,11 @@ public struct FloydWarshall<T where T: Hashable>: APSPAlgorithm {
    8589

    8690
    }
    8791

    88-
    /**
    89-
    We need to map the graph's weight domain onto the one required by the algorithm: the graph stores either a weight as a `Double` or `nil` if no edge exists between two vertices, but the algorithm needs a lack of an edge represented as ∞ for the `min` comparison to work correctly.
    90-
    92+
    /**
    93+
    We need to map the graph's weight domain onto the one required by the algorithm: the graph
    94+
    stores either a weight as a `Double` or `nil` if no edge exists between two vertices, but
    95+
    the algorithm needs a lack of an edge represented as ∞ for the `min` comparison to work correctly.
    96+
    9197
    - complexity: `Θ(V^2)` time/space
    9298
    - returns: weighted adjacency matrix in form ready for processing with Floyd-Warshall
    9399
    */
    @@ -116,7 +122,7 @@ public struct FloydWarshall<T where T: Hashable>: APSPAlgorithm {
    116122

    117123
    /**
    118124
    Make the initial predecessor index matrix. Initially each value is equal to it's row index, it's "from" index when querying into it.
    119-
    125+
    120126
    - complexity: `Θ(V^2)` time/space
    121127
    */
    122128
    static private func constructInitialPredecessorMatrix(distances: Distances) -> Predecessors {
    @@ -139,17 +145,20 @@ public struct FloydWarshall<T where T: Hashable>: APSPAlgorithm {
    139145
    }
    140146

    141147
    /**
    142-
    `FloydWarshallResult` encapsulates the result of the computation, namely the minimized distance adjacency matrix, and the matrix of predecessor indices.
    143-
    144-
    It conforms to the `APSPResult` procotol which provides methods to retrieve distances and paths between given pairs of start and end nodes.
    148+
    `FloydWarshallResult` encapsulates the result of the computation, namely the
    149+
    minimized distance adjacency matrix, and the matrix of predecessor indices.
    150+
    151+
    It conforms to the `APSPResult` procotol which provides methods to retrieve
    152+
    distances and paths between given pairs of start and end nodes.
    145153
    */
    146154
    public struct FloydWarshallResult<T where T: Hashable>: APSPResult {
    147155

    148156
    private var weights: Distances
    149157
    private var predecessors: Predecessors
    150158

    151159
    /**
    152-
    - returns: the total weight of the path from a starting vertex to a destination. This value is the minimal connected weight between the two vertices, or `nil` if no path exists
    160+
    - returns: the total weight of the path from a starting vertex to a destination.
    161+
    This value is the minimal connected weight between the two vertices, or `nil` if no path exists
    153162
    - complexity: `Θ(1)` time/space
    154163
    */
    155164
    public func distance(fromVertex from: Vertex<T>, toVertex to: Vertex<T>) -> Double? {
    @@ -159,7 +168,8 @@ public struct FloydWarshallResult<T where T: Hashable>: APSPResult {
    159168
    }
    160169

    161170
    /**
    162-
    - returns: the reconstructed path from a starting vertex to a destination, as an array containing the data property of each vertex, or `nil` if no path exists
    171+
    - returns: the reconstructed path from a starting vertex to a destination,
    172+
    as an array containing the data property of each vertex, or `nil` if no path exists
    163173
    - complexity: `Θ(V)` time, `Θ(V^2)` space
    164174
    */
    165175
    public func path(fromVertex from: Vertex<T>, toVertex to: Vertex<T>, inGraph graph: AbstractGraph<T>) -> [T]? {
    @@ -175,11 +185,13 @@ public struct FloydWarshallResult<T where T: Hashable>: APSPResult {
    175185
    }
    176186

    177187
    /**
    178-
    The recursive component to rebuilding the shortest path between two vertices using the predecessor matrix.
    188+
    The recursive component to rebuilding the shortest path between
    189+
    two vertices using the predecessor matrix.
    179190

    180191
    - returns: the list of predecessors discovered so far
    181192
    */
    182-
    private func recursePathFrom(fromVertex from: Vertex<T>, toVertex to: Vertex<T>, path: [Vertex<T>], inGraph graph: AbstractGraph<T>) -> [Vertex<T>]? {
    193+
    private func recursePathFrom(fromVertex from: Vertex<T>, toVertex to: Vertex<T>, path: [Vertex<T>],
    194+
    inGraph graph: AbstractGraph<T>) -> [Vertex<T>]? {
    183195

    184196
    if from.index == to.index {
    185197
    return [ from, to ]
    @@ -198,7 +210,6 @@ public struct FloydWarshallResult<T where T: Hashable>: APSPResult {
    198210
    }
    199211

    200212
    return nil
    201-
    202213
    }
    203214

    204215
    }

    0 commit comments

    Comments
     (0)
    0