Swift 3 Migration

[chris-pilcher]

And... we're done!

Thanks everyone for pitching in!

---

Xcode 8 and Swift 3 will be formally released soon and we need to migrate everything to Swift 3.

Want to help out with the migration? Awesome! :]

Please follow this process for migrating to Swift 3

• Download the Xcode 8.X
• Create a pull request to "claim" an algorithm or data structure you'd like to migrate. Just so multiple people don't work on the same thing.
• Migrate the algorithm/data structure project, playground, tests and readme to Swift 3
  • Uncomment test project in .travis.yml so it will run on our Xcode 8 Travis CI build server
• Comment in the pull request when the changes are ready to be merged

Suggestions and feedback is welcome!

List of algorithms to be migrated to Swift 3

nil

Completed Migrations

• AVL Tree Migrating AVL tree to Swift 3 #183
• All-Pairs Shortest Paths Migrates All-Pairs Shortest Paths to Swift3 syntax #347
• Array2D Array 2D #189
• B-Tree Updating B-Tree to Swift 3 #203
• Binary Search Tree
• Binary Search Migrating Binary Search to Swift 3 #184
• Binary Tree Converted playground and fixed README for swift 3. #213
• Bit Set Updating Bit Set to Swift 3 #194
• Bloom Filter Updating Bloom Filter to Swift 3 #195
• Bounded Priority Queue Swift3 bounded priority queue #218
• Boyer-Moore Boyer moore swift3 #248
• Breadth-First migrating bfs to swift3 #237
• Brute-Force String Search Migrating Brute Force String Search to Swift3 #239
• Bubble Sort (no code)
• Bucket Sort Bucket sort migration to swift 3 #281
• Comb Sort Migrate Combsort to Swift 3 syntax #350
• Combinatorics migrate combinatorics to swift3 #270
• Count Occurrences Update Count Occurrences to Swift 3 #201
• Counting Sort Convert to Swift 3 syntax to get rid of Xcode 8 errors #235
• Depth-First Search migrating dfs to swift3 #238
• Deque update Array2D, Deque to swift3.0 #303
• Fixed Size Array migrate fixedsizearray to swift3 #271
• Fizz Buzz updated fizzBuzz to swift3 #229
• GCD GCD #219
• Graph Migrate Graph to swift 3 #267
• Hash Set Hashset migrate to swift3 #276
• Hash Table Update hash table for Swift 3.0 #216
• Heap Sort Updating Heap Sort to Swift 3 #334
• Heap 3945383
• Huffman Coding Migrated Huffman Coding to Swift 3 syntax #344
• Insertion Sort Updating Insertion Sort to Swift 3 #198
• K-Means Migrate K-Means to Swift 3 Syntax #349
• Kth Largest Element Update to Swift3 #228
• Linear Regression Swift 3 Migration: Linear Regression #283
• Linear Search Updating Linear Search to Swift 3 #200
• Linked List Migrate Linked List to Swift 3.0 #250
• Longest Common Subsequence Migrate LCS to Swift 3.0 #243
• Merge Sort Updating Merge Sort to Swift 3 #199
• Minimum Edit Distance Swift 3 Migration: Minimum Edit Distance #302
• Minimum Spanning Tree (Unweighted) Update Minimum Spanning Tree (Unweighted Graph) to Swift 3 syntax  #345
• Monty Hall Problem migrating montyhall to swift 3 #241
• Ordered Array Update Ordered Array to Swift 3 #232
• Ordered Set Updated Ordered Set to swift 3 #234
• Palindromes migrate palindromes to Swift 3 string #187
• Priority Queue Updated priority queue to swift 3 #233
• Queue Updating Queue to Swift 3 #197
• Quicksort Swift3 migration for QuickSort #217
• Radix Sort Migrates All-Pairs Shortest Paths to Swift3 syntax #347
• Radix Tree migrating radix-tree to swift3 #242
• Red-Black Tree Red Black Tree 2 #214
• Ring Buffer Ring buffer swift3 migrate #265
• Run-Length Encoding Run-Length Encoding to Swift 3 #364
• Segment Tree Segment Tree #220
• Selection Sampling (no changes necessary)
• Select Minimum Maximum Updating Select Minimum Maximum to Swift 3 #333
• Selection Sort
• Set Cover (Unweighted) Set Cover migrated to swift 3 #366
• Shell Sort Update to Swift 3.0 #260
• Shortest Path (Unweighted) Updating Shortest Path (Unweighted) to Swift 3 #343
• Shuffle fix for Swift 3 #273 fix for Swift 3 #274
• Shunting Yard Migrate Shunting Yard to Swift 3 #365
• Single-Source Shortest Paths (Weighted) migrates Single-Source Shortest Paths to Swift 3 syntax #356
• Stack Updating Stack to Swift 3 #196
• Ternary Search Tree
• Topological Sort Migrated Topological Sort to Swift 3 #259
• Treap Migrate treap to swift 3 #251
• Threaded Binary Tree Migrate Threaded Binary Tree to Swift 3 #367
• Tree Updating Tree to Swift 3 #193
• Trie Swift 3 Trie #208
• Two-Sum Problem Two sum migrate swift3 #266
• Union-Find Updating Union-Find to Swift 3 #192

[Jxrgxn]

I knew this day would come.

[lostatseajoshua]

@chris-pilcher Will the Swift 3 implementation override the current implementations? Can we add a folder for each algorithm to organize implementations into Swift 2 and Swift 3? They can share the sameREADME for describing the algorithm.

Example of folder structure

- Merge Sort
  - Swift 2
    - Implementation.swift
  - Swift 3
   - Implementation.swift
  - README

[chris-pilcher]

@lostatseajoshua Thanks for the suggestion! I'm keen to have a single version because of the complexity associated with keeping multiple versions. Potential complications/difficulties I can think of:

• Keeping multiple versions of the same project/playground/tests in sync
• Future contributions would require multiple implementations
• Build server would have to handle multiple versions
• Handling future versions of Swift

Overall, I think it would be best to overwrite the current Swift 2 implementations.

[lostatseajoshua]

@chris-pilcher Great points! I agree with the difficulties one version will be better. With that point I am going to make a couple PRs to claim some algorithms in Swift 3 👍

[tuliot]

@kelvinlauKL Linked List was updated with #212 . Can you check it off the todo?

[JaapWijnen]

The Red-Black tree has been updated with #214
#232 updates Ordered Array to swift 3
#233 updates Priority Queue to swift 3
#234 updates Ordered Set to swift 3

[JaapWijnen]

Red-Black tree can be checked on the list since #214

[ivanicspeter92]

#250 Linked List

[goingreen]

#251 Treap

[JaapWijnen]

Oh sorry didnt see #259 and did similar work in #264

[shashank3369]

Hello @chris-pilcher, I was wondering if the ones that don't have check marks are the ones that still need to be migrated. If so I would be happy to help.

[kelvinlauKL]

yep @shashank3369, you're correct.

[mattThousand]

#334 Heap Sort

[grosch]

I'm not familiar enough with github to know how to properly do the pull/push requests, but here's how I'd rewrite the "Comb Sort" algorithm. That 'while' loop that was in there confused the heck out of me. I think this one is much cleaner.

func combSort(input: [Int]) -> [Int] {
    let shrink = 1.3

    var copy = input
    var gap = copy.count

    while gap > 1 {
        gap = max(1, Int(Double(gap) / shrink))

        for i in 0 ..< copy.count - gap {
            if copy[i] > copy[i + gap] {
                swap(&copy[i], &copy[i + gap])
            }
        }
    }

    return copy
}

[gonini]

#343 Shortest Path (Unweighted)

[gonini]

#345 Minimum Spanning Tree (Unweighted Graph)

[pbodsk]

#344 Huffman Coding

[pbodsk]

#347 All-Pairs Shortest Paths

[taiheng]

#349 K-Means

[taiheng]

#350 Combsort.

[pbodsk]

#352 Ternary Search Tree

[taiheng]

#353 Radix Sort

[pbodsk]

All-Pairs Shortest Pairs has been upgraded and merged too (PR #347), so that should be checked of as well, can I do that myself?

[kelvinlauKL]

Thanks @pbodsk, updated.

[pbodsk]

#356 Single-Source Shortest Paths

[naeemshaikh90]

#270 Combinatorics is migrated to swift 3.

[naeemshaikh90]

What do we need to migrate in Images? 😀

[kelvinlauKL]

@naeemshaikh90 Good point, also marked combinatorics as migrated. Thanks 👍

[JaapWijnen]

@kelvinlauKL Just checked, I think Selection Sampling is already written in swift 3. Compiles just fine on my mac.

[kelvinlauKL]

@JaapWijnen Thanks for the heads up.

[JaapWijnen]

#364 Run Length Encoding migrated to Swift 3

[JaapWijnen]

#365 Shunting Yard migrated to Swift 3

[JaapWijnen]

#366 Set Cover (unweighted) migrated to Swift 3

[JaapWijnen]

And the last one! #367

[kelvinlauKL]

Wow @JaapWijnen, you're on a roll 👍

I'll review those later, but for now it seems like we're finally done.

Thanks everyone!