A Pattern in Swift - Change Algorithms Dependency with A Wrapper Type

Swift, which as known as a Protocol-Oriented programming language, allows you to create algorithms which depend on restrictions with protocols. Typically, once a type is Comparable, you can sort it with merge sort or quick sort, because merge sort and quick sort utilizes comparison computational model to do the work; once a type is Hashable, you can find the duplicate from a bunch of those objects with algorithms utilizing counting computational model because Hashable ensures the uniqueness of each object.

But how to hash or how to compare is fixed for practical types, you cannot control the computational complexity of the hashing/comparing procedure.

For example, for a bunch of NSString values, since NSString is Hashable, you may count a counting-computational-model-based algorithm to help you find the duplicate in time upper bound to O(n), and it works. But you cannot improve the performance of this procedure if you know the contents of each NSString value are different and the only difference among them is the hash value -- because NSString is out-of-box Hashable.

To improve the performance in this case, we actually can define a wrapper type.

struct NSStringHashValueContainer: Hashable {  
    let nsString: NSString

    static func == (lhs: NSStringHashValueContainer, rhs: NSStringHashValueContainer) -> Bool {
        return ObjectIdentifier(lhs.nsString) == ObjectIdentifier(rhs.nsString)
    }

    var hashValue: Int {
        return ObjectIdentifier(self.nsString).hashValue
    }
}

Since a counting-computational-model algorithm shall only relies on the guarantee of uniqueness, which is the Hashable protocol here, this type shall work with such an algorithm.

Even more, for some cases, you might know that this procedure only runs locally inside a function, since all the NSString values lifetime are guaranteed by the containing function, you can optimize the wrapper type to:

struct NSStringHashValueContainer: Hashable {  
    unowned let nsString: NSString

    ...

This wrapper is more memory efficient than the previous one.

If you know something about Design Patterns, you might know this is the Decorator pattern.

WeZZard

Independent iOS developer, World of Warcraft add-on developer. Interested in Computer Graphics and Machine Learning.

People's Republic of China https://github.com/WeZZard