Skip to content

Instantly share code, notes, and snippets.

@SwiftStudies

SwiftStudies/IncrementalUpdateTests.swift

Last active August 29, 2015 14:21
Show Gist options
  • Save SwiftStudies/f2e07e882212a6406668 to your computer and use it in GitHub Desktop.
Save SwiftStudies/f2e07e882212a6406668 to your computer and use it in GitHub Desktop.
Download ZIP
Incremental Update Challenge
Raw
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)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment