Incremental Update Challenge

IncrementalUpdateTests.swift

//
//  IncrementalUpdateTests.swift
//
//  Copyright (c) 2015 Swift Studies. All rights reserved.
//

import Foundation
import XCTest


// MARK: -
// MARK: Your Implementation Here
public func candidateImplementation<T : Hashable>(
    oldList old:[T],
    newList new:[T],
    insertion insertBlock : (insert:T,at:Int)->(),
    removal removeBlock : (remove:T,from:Int)->(),
    move moveBlock   : (move:T,from:Int, to:Int)->())
{
    //
    //This implementation is intentionally left blank... so you can add your own
    //
}

// MARK: -
// MARK: >>>>>>>>>>Don't change anything below here<<<<<<<<<

// MARK: -
// MARK: SwiftStudies Implementation
public func swiftStudiesImplementation<T : Hashable>(
    oldList old:[T],
    newList new:[T],
    insertion insertBlock : (insert:T,at:Int)->(),
    removal removeBlock : (remove:T,from:Int)->(),
    move moveBlock   : (move:T,from:Int, to:Int)->())
{
    //Build an index of new positions
    var newPositions = [ T : Int]()
    for index in 0..<new.count {
        newPositions[new[index]]=index
    }
    
    //Items in here should be deleted at the end
    var deletePositions = [T : Int]()
    
    for oldPosition in 0..<old.count{
        let item = old[oldPosition]
        
        if let newPosition = newPositions[item] {
            if oldPosition != newPosition{
                moveBlock(move: item,from: oldPosition, to: newPosition)
            }
            newPositions.removeValueForKey(item)
        } else {
            removeBlock(remove: item, from: oldPosition)
        }
    }
    
    
    for (item,position) in newPositions{
        insertBlock(insert: item, at: position)
    }
}
// MARK: -

// MARK: -
// MARK: My First Attempt at an Implementation
public func slowImplementation<T : Hashable>(
    oldList old:[T],
    newList new:[T],
    insertion insertBlock : (insert:T,at:Int)->(),
    removal removeBlock : (remove:T,from:Int)->(),
    move moveBlock   : (move:T,from:Int, to:Int)->())
{
    func newIndex(old:T,newResults:[T])->Int?{
        var index = 0
        for newItem in newResults{
            if newItem == old {
                return index
            }
            index++
        }
        
        return nil
    }
    
    var index = 0
    for oldItem in old{
        if let newLocation = newIndex(oldItem,new){
            moveBlock(move: oldItem, from: index, to: newLocation)
        } else {
            removeBlock(remove: oldItem, from: index)
        }
        
        index++
    }
    
    index = 0
    for newItem in new {
        if newIndex(newItem,old) == nil {
            insertBlock(insert: newItem, at: index)
        }
        index++
    }
    
    
}
// MARK: -


// MARK: -
// MARK: Test Data Variables
let numberOfKeys = 1000
var originalKeys : [String]?
var changedKeys : [String]?



class IncrementalUpdateTests: XCTestCase {
    // MARK: -
    // MARK: Captures a change for testing results of implementations
    enum Delta {
        case Delete(fromIndex:Int)
        case Insert(item:String,atIndex:Int)
        case Move(fromIndex:Int,toIndex:Int)
    }
    
    // MARK: -
    // MARK: Captures all of the results from an implementation
    struct ChangeSet{
        var deltas = [Delta]()
        var inserts = 0
        var deletes = 0
    }
    
    // MARK: -
    // MARK: Create test data
    func createKeys(limit:Int)->[String]{
        var newKeys = [String]()
        for i in 0..<limit{
            newKeys.append(NSUUID().UUIDString)
        }

        return newKeys
    }
    
    typealias StringSpecialisedUpdater = ([String],[String],(String,Int)->(),(String,Int)->(),(String,Int,Int)->())->()
    
    override func setUp() {
        super.setUp()
        // Put setup code here. This method is called before the invocation of each test method in the class.
        
        if originalKeys == nil {
            println("Creating original keys")
            originalKeys = createKeys(numberOfKeys)
            println("\tDone")
        }
        
        if changedKeys == nil {
            println("Creating changed keys")
            changedKeys = originalKeys

            println("\tRemove half of originals")
            //Remove half of them
            for _ in 0..<numberOfKeys/2{
                changedKeys?.removeLast()
            }

            println("\tAdding new half")
            //Add a new half
            for newKey in createKeys(numberOfKeys/2){
                changedKeys?.append(newKey)
            }
            
            //And mix them up
            println("\tRe-ordering")
            for _ in 0..<10{
                changedKeys?.sort{(_,_) in arc4random() < arc4random()}
            }
            println("\tDone")
            
        }
    }
    
    override func tearDown() {
        // Put teardown code here. This method is called after the invocation of each test method in the class.
        super.tearDown()
    }

    func applyIncrementalUpdater(updater : StringSpecialisedUpdater)->ChangeSet{
        if let originalKeys = originalKeys, changedKeys = changedKeys{
            var deltas = [Delta]()
            var deletes = 0
            var inserts = 0
            
            updater(originalKeys,changedKeys, { (insert, at) -> () in
                deltas.append(Delta.Insert(item: insert, atIndex: at))
                inserts++
                },  { (remove, from) -> () in
                    deltas.append(Delta.Delete(fromIndex: from))
                    deletes++
                }, { (move, from, to) -> () in
                    deltas.append(Delta.Move(fromIndex: from, toIndex: to))
            })
            
            var changeSet = ChangeSet(deltas: deltas, inserts: inserts, deletes: deletes)
            
            return changeSet
        } else {
            assert(false,"Keys not set-up")
            return ChangeSet()
        }
    }
    
    func doIncrementalUpdaterTest(updater : StringSpecialisedUpdater){
        if let originalKeys = originalKeys, changedKeys = changedKeys{
            
            let result = applyIncrementalUpdater(updater)
            
            
            var deltas = result.deltas
            var deletes = result.deletes
            var inserts = result.inserts
            
            updater(originalKeys,changedKeys, { (insert, at) -> () in
                deltas.append(Delta.Insert(item: insert, atIndex: at))
                inserts++
            },  { (remove, from) -> () in
                    deltas.append(Delta.Delete(fromIndex: from))
                    deletes++
            }, { (move, from, to) -> () in
                    deltas.append(Delta.Move(fromIndex: from, toIndex: to))
            })
            
            var ourChangedCopy = [String?]()
            
            for i in 0..<originalKeys.count+(inserts-deletes){
                ourChangedCopy.append(nil)
            }
            
            for delta in deltas{
                switch delta{
                case let .Delete(from):
                    break
                case let .Insert(item,into):
                    ourChangedCopy[into]=item
                case let .Move(from,to):
                    ourChangedCopy[to] = originalKeys[from]
                }
            }
            
            for index in 0..<ourChangedCopy.count{
                if ourChangedCopy[index] == nil{
                    ourChangedCopy[index] = originalKeys[index]
                }
            }
            
            var finalCopy = [String]()
            for item in ourChangedCopy{
                if (item == nil){
                    assert(false,"Blank space left in new array")
                    return
                }
                finalCopy.append(item!)
            }
            
            XCTAssert(finalCopy == changedKeys,"Arrays don't match")
        } else {
            XCTAssert(false, "Original and changed keys must be set-up")
        }
        
    }
    
    func testSlow() {
        doIncrementalUpdaterTest(slowImplementation)
    }
    
    func testSlowPerformance() {
        self.measureBlock() {
            self.doIncrementalUpdaterTest(slowImplementation)
        }
    }
    
    func testSwiftStudies() {
        doIncrementalUpdaterTest(swiftStudiesImplementation)
    }

    func testSwiftStudiesPerformance() {
        self.measureBlock() {
            self.doIncrementalUpdaterTest(swiftStudiesImplementation)
        }
    }

    func testChallenger() {
        doIncrementalUpdaterTest(candidateImplementation)
    }
    
    func testChallengerPerformance() {
        self.measureBlock() {
            self.doIncrementalUpdaterTest(candidateImplementation)
        }
    }
    
}