Skip to content

tech

BST

A binary search tree is a data structure that stores information in a logical hierarchy.

A binary search tree is comprised of a key and two indicators. The key represents the data you would like to store, such as string or scalar value. Typically represented with pointers, the indicators store the location (also called the address) of its two children. The left child contains a value that is smaller than its parent. Conversely, the right child contains a value greater than its parent.

The same list (example below) visualized as a balanced BST. It does not matter that the values are unsorted. Rules governing the BST will place each node in its “correct” position accordingly.

Implementation below:

import Cocoa

/*
 A binary search tree is a data structure that stores information in a logical hierarchy.
 
 A binary search tree is comprised of a key and two indicators. The key represents
 the data you would like to store, such as string or scalar value. Typically represented with pointers,
 the indicators store the location (also called the address) of its two children.
 The left child contains a value that is smaller than its parent.
 Conversely, the right child contains a value greater than its parent.
 */


public class AVLTree <T: Comparable> {
    var key: T?
    var left: AVLTree?
    var right: AVLTree?
    
    var height: Int = 0
    
    // Add item
    func append(element key: T) {
        // Check root
        guard self.key != nil else {
            self.key = key
            self.height = 0
            return
        }
        
        // Check left side
        if key < self.key! {
            if self.left != nil {
                left?.append(element: key)
            } else {
                // New element
                let leftElement = AVLTree()
                leftElement.key = key
                leftElement.height = 0
                self.left = leftElement
            }
        }
        
        // Check right side
        if key > self.key! {
            if self.right != nil {
                right?.append(element: key)
            } else {
                // New element
                let rightElement = AVLTree()
                rightElement.key = key
                rightElement.height = 0
                self.right = rightElement
            }
        }
    }
}

// A simple array of unsorted integers
let numbers: Array<Int> = [8, 2, 10, 9, 11, 1, 7]

// Create a new BST instance
var root = AVLTree<Int>()

// Sort each item in the list
for number in numbers {
    root.append(element: number)
}

print(root)

<Example from Swift Algorithms & Data Structures by Wayne Bishop>

Literal Regex in Swift

Okay, straight to the point 🙃

import Cocoa

// StringLiteralConvertible with Regular Expressions
// Example of using Swift literal convertible to provide convenient shorthand initializers for custom objects

// Create a Swift wrapper around NSRegularExpression
struct Regex {
    let pattern: String
    let options: NSRegularExpression.Options
    
    private var matcher: NSRegularExpression {
        do {
            let response = try NSRegularExpression(pattern: self.pattern, options: self.options)
            return response
        } catch {
            fatalError()
        }
    }
    
    init(pattern: String, options: NSRegularExpression.Options = []) {
        self.pattern = pattern
        self.options = options
    }
    
    func match(string: String, options: NSRegularExpression.MatchingOptions = []) -> Bool {
        return self.matcher.numberOfMatches(in: string, options: options, range: NSMakeRange(0, string.utf16.count)) != 0
    }
}

// Extend Regex to support regular expression literal
extension Regex: ExpressibleByStringLiteral {
    init(unicodeScalarLiteral value: String) {
        self.pattern = "(value)"
        self.options = []
    }
    
    init(extendedGraphemeClusterLiteral value: String) {
        self.pattern = value
        self.options = []
    }
    
    init(stringLiteral value: String) {
        self.pattern = value
        self.options = []
    }
}

// Now we can do this
let string: String = "foo bar baz"
let regex: Regex = "bar"
print(regex.match(string: "bar"))

 

√ and ±

Even though these two operators are not see in day-to-day use (in programming world lah), but let’s see how to create  them in Swift 😁

import Cocoa

// Square root operator

prefix operator √

prefix func √(number: Double) -> Double {
    return sqrt(number)
}

print(√(9)) // 3.0
print(√(2)) // 1.4142135623731

// Plus-Minus operator

precedencegroup PlusMinusPrecedence {
    associativity: left
    higherThan: AdditionPrecedence
}

infix operator ±: PlusMinusPrecedence

func ±<T: BinaryInteger>(lhs: T, rhs: T) -> (T, T) {
    return (lhs + rhs, lhs - rhs)
}

print(1±2) // (2, 4)

prefix operator ±

prefix func ±<T: BinaryInteger>(number: T) -> (T, T) {
    return 0 ± number
}

print(±3) // (3, -3)