Swift - Binary Search Tree

bst.swift

import UIKit

class Thing {
    var value : Int
    init(v: Int) {
        value = v
    }
}

class ThingBST {
    var parent : ThingBST? = nil
    var index : Thing? = nil
    var left : ThingBST? = nil
    var right : ThingBST? = nil
    
    func addThing(thing: Thing) {
        
        // If the node is empty thing is initial value
        
        if index == nil {
            index = thing
            return
        }
            
        // If thing value is less than value then split left
        
        if thing.value < index?.value {
            if left == nil {
                left = ThingBST()
                left?.parent = self
            }
            left!.addThing(thing)
            return
        }
        
        // If thing value is greater than value then split right
        
        if thing.value > index?.value {
            if right == nil {
                right = ThingBST()
                right?.parent = self
            }
            right!.addThing(thing)
            return
        }
        
    }
    
    // Take a child BST and add elements to root BST
    
    private func processBST(bst: ThingBST) {
        addThing(bst.index!)
        if bst.left  != nil { processBST(bst.left!) }
        if bst.right != nil { processBST(bst.right!) }
    }
    
    private func deleteThing(thing: Thing, bst: ThingBST) {
        
        // if thing is root of tree
        if parent == nil {
            if bst.right? != nil {
                var leftTemp = bst.left?
                var childLeft = bst.right?.left
                bst.index = bst.right?.index
                bst.right = bst.right?.right
                bst.left = childLeft
                processBST(leftTemp!)
            }
        }
        
        // if thing value is on left side of parent
        if parent?.index?.value > thing.value {
            if bst.right? != nil {
                parent?.left = bst.right!
            }
            if bst.left? != nil {
                parent?.left?.processBST(bst.left!)
            }
            if bst.right? == nil && bst.left? == nil {
                parent?.left = nil
            }
        }
        
        // if thing value is on right side of parent
        if parent?.index?.value < thing.value {
            if bst.right? != nil {
                parent?.right = bst.right!
            }
            if bst.left? != nil {
                parent?.right?.processBST(bst.left!)
            }
            if bst.left? == nil && bst.right? == nil {
                parent?.right = nil
            }
            
        }
    }
    
    func deleteThingbyValue(value: Int) -> Bool? {
        if value == index?.value {
            deleteThing(index!, bst: self)
            return true
        } else if value < index?.value {
            return left?.deleteThingbyValue(value)
        } else if value > index?.value {
            return right?.deleteThingbyValue(value)
        }
        return false
    }
    
    func findThingbyValue(value: Int) -> Thing? {
        
        if value == index?.value {
            return index
        } else if (value < index?.value) {
            return left?.findThingbyValue(value)
        } else if  (value > index?.value) {
            return right?.findThingbyValue(value)
        } else {
            return nil
        }
        
    }
    
    func printTree() -> [Int]{
        var arr = [Int]()
        if let a = index?.value {
            println(a)
            arr.append(a)
        }
        if let l = left? {
            arr += l.printTree()
        }
        
        if let r = right? {
            arr += r.printTree()
        }
        return arr
    }
    
    func print() {
        println("Index: \(index?.value)")
        if parent != nil {
            println("\(index?.value) parent is \(parent?.index?.value)")
        }
        if left != nil {
            println("Left for \(index!.value): \(left?.print())")
        }
        if right != nil {
            println("Right for \(index!.value): \(right?.print())")
        }
    }
    
}


//BST Tests

class BstTest {
    var result = [Int: Bool]()
    
    func assert(value: Int, inBst: ThingBST) -> Bool {
        return value == inBst.findThingbyValue(value)?.value
    }
    
    func assert(arrayOfThings: [Thing], inBst: ThingBST) -> Bool {
        for thing in arrayOfThings {
            let num = thing.value
            if num != inBst.findThingbyValue(num)?.value {
                return false
            }
        }
        return true
    }
    
    func assert(eachIndexValue: [Int], inBst: ThingBST) -> [Int: Bool]{

        for num in eachIndexValue {
            if num != inBst.findThingbyValue(num)?.value {
                println("\(num) is not in BST")
                result[num] = false
            } else {
                result[num] = true
            }
        }
        return result
    }
    
    func assertNot(eachIndexValue: [Int], inBst: ThingBST) -> Bool {
        for num in eachIndexValue {
            if num == inBst.findThingbyValue(num)?.value {
                return false
            }
        }
        return true
    }
}

//***************************TESTS*******************************

println("***************************************")

extension Array{
    func contains<T: Comparable>(val: T) -> Bool{
        for x in self {
            if val == x as T { return true }
        }
        return false
    }
}

let y : [Int] = [1,2,3]
y.contains(1)

func uniqueItemsInArrays<T: Comparable>(left: [T], right: [T]) -> [T] {
    var result = [T]()
    for item in left {
        if !right.contains(item) {
            result.append(item)
        }
    }
    for item in right {
        if !left.contains(item) {
            result.append(item)
        }
    }
    return result
}

let x = uniqueItemsInArrays([1,2,3], [3,4,5])

let arr = [21,10,35,50,101,121,130,2,15,19,36,22,23]
var thingBST = ThingBST()
var things = [Thing]()
for num in arr {
    let t = Thing(v: num)
    things.append(t)
    thingBST.addThing(t)
}

//Check to see if all things are findable in thingBST

BstTest().assert(101, inBst: thingBST)
BstTest().assert(things, inBst: thingBST)
BstTest().assert(arr, inBst: thingBST)

//Check delete thing

let arr2 = [10,50,101,130,2,15,19,36,23]

thingBST.deleteThingbyValue(22)
thingBST.deleteThingbyValue(35)
thingBST.deleteThingbyValue(21)
thingBST.deleteThingbyValue(121)

BstTest().assert(arr2, inBst: thingBST)
BstTest().assertNot(uniqueItemsInArrays(arr, arr2), inBst: thingBST)

thingBST.addThing(Thing(v: 1234))
BstTest().assert(1234, inBst: thingBST)

thingBST.addThing(Thing(v: 1234))
BstTest().assert(1234, inBst: thingBST)
thingBST.deleteThingbyValue(1234)
BstTest().assert(1234, inBst: thingBST)

thingBST.printTree()