Samstag, 28. Februar 2015

Interval mapping / playing with intervals and functions in Swift

Playground (Gist)

Diverse approaches of mapping intervals to something. And learning a bit of Swift on the way.

For example, given a mapping of interval 0..<2 to a string "first interval" and 2..<4 to a string "second interval", we want to get the string for the value 3.4.

I started thinking about this because in my work I had to map rating intervals to certain background colors. If e.g. a user gives a 5.9 rating this would be in the range 4.5 - 6.0 which has to be displayed with a dark green background, etc. Sadly I had to do this using objc. I wondered how I would do it with Swift.

We start with the most primitive way:

let n = 3.4
let found1:String? = {if n < 2 {
    return "first"
} else if n < 4 {
    return "second"
} else {
    return nil
}}()

println("found: \(found1)") //found: Optional("second")

It's also possible to use a switch case. But I think switch case is not really meant to be used like this. Here I'm only exploring the possibilities of the language.

let found2:String? = {switch n {
    case _ where (0..<2) ~= n: return "first"
    case _ where (2..<4) ~= n: return "second"
    default: return nil
    }
}()

println("found: \(found2)") //found: Optional("second")

These approaches are a bit unflexible. And the worst: NOT FANCY! So we explore further.

Intro: get (first) containing range for a value
let result:HalfOpenInterval<Float>? = {
    for r:HalfOpenInterval<Float> in [(0..<1), (1..<2), (2..<3)] {
        if r ~= 2 {
            return r
        }
    }
    return nil
}()

Good! Now, we will make a helper struct that holds the range and the object:

struct RangedEntry<T> {
    let interval:HalfOpenInterval<Float>
    let obj:T
    
    init(_ interval:HalfOpenInterval<Float>, _ obj:T) {
        self.interval = interval
        self.obj = obj
    }
}

Now we can iterate through entries to find our match:

for re in [
    RangedEntry((0..<1), "a"),
    RangedEntry((1..<2), "b"),
    RangedEntry((2..<3), "c")
    ] {
        
        if re.interval ~= 1.9 {
            println("found: \(re.obj)") // found: b
            break;
        }
}

Alternatively, we can just use tuples:

for r:(HalfOpenInterval<Float>, String) in [
    ((0..<1), "a"),
    ((1..<2), "b"),
    ((2..<3), "c")
    ] {
        if r.0 ~= 1.9 {
            println("found: \(r.1)") // found: b
        }
}

What about more functional constructs?

Let's try out filter (we will continue using tuples):

let value:String? = [
    ((0..<1), "a"),
    ((1..<2), "b"),
    ((2..<3), "c")
    
    ].filter{(tuple:(HalfOpenInterval<Float>, String)) -> Bool in
        return tuple.0 ~= 1.9
        
}.first?.1

println("found: \(value)") // found: Optional("b")


This is O(n), since we will examine the whole array each time. Not so good. Coming back later to this. Also note we assume that the ranges don't overlap.

What if we want to generate the ranges dynamically, say, divide 1...7 in 16 equal parts?
Since in this case the intervals are continuos, we can represent them just as a succession of numbers.
We can use strides for this:

let start:Float = 1
let end:Float = 7
let sections = 16
let intervalLength:Float = (end - start) / Float(sections)


let s = stride(from: start, through: end, by: intervalLength)
Array(s) // see contents in playground

// generate tuples with dummy value objects. The start of the range represents the range, and we associate the value object with it.
let tuples:[(Float, String)] = Array(s).map {(val:Float) -> (Float, String) in
    return (val, "range starts:\(val) ends: \(val + intervalLength)")
}

Now let's try out an alternative approach to =~. Since in this case we know the ranges are sorted in increasing order, we can use this information to find the value.

The number we will search from now on:
let search:Float = 4.12

This is a simple filtering function with which we retrieve the ranges witch a start value smaller than our searched value:
let filtered = tuples.filter {
    return $0.0 < search
}

The range we are looking for is the range with the biggest starting value from result of above filtering. Since we know the ranges are sorted increasingly, we can just pick the last one from the filter results:
let val:String? = filtered.last?.1
println("found: \(val)") // found: Optional("range starts:4.0 ends: 4.375")
In this case we expect the ranges to be sorted, since we assumed this for the filtering. In an imaginary case that we didn't know that the values are sorted, we could get the range with the max. starting value using reduce:
let val1:String? = {
    filtered.isEmpty ? nil : filtered.reduce(filtered.first!, {
        return $0.0 > $1.0 ? $0 : $1
    }).1
}()

println("found: \(val1)") // found: Optional("range starts:4.0 ends: 4.375")

So far functions. But in order to avoid having to go through the whole array each time, we will use a loop, that exits when we find the range.
Since there's no filtering step, we have to add logic to look ahead in the next range. If there's no next, or if its starting value is bigger than searched value, we know we are in the searched range.

let myresult:String? = {
    for (index, tup) in enumerate(tuples) {
        if tup.0 <= search && (index + 1 == tuples.count || tuples[index + 1].0 > search) {
            return tup.1
        }
    }
    return nil
}()

println("found: \(myresult)") // found: Optional("range starts:4.0 ends: 4.375")

Talking about indices and look-ahead, here is a similar approach using filter (just demonstrative purpose - would not use it):
let val2:String? = Array(enumerate(tuples)).filter { (index:Int, element) -> Bool in
    return element.0 <= search && (index + 1 == tuples.count || tuples[index + 1].0 > search)
}.first?.1.1


println("found: \(val2)") // found: Optional("range starts:4.0 ends: 4.375")


So is there a way in which we use a functional construct with the performance of for loop?
We need something similar to a find function. This is an example of a find function:
(this is btw a nice to have in array extension)

func find<T>(arr:Array<T>, pred:(element:T)->Bool) -> T? {
    for i in 0..<arr.count {
        let element =  arr[i]
        
        if pred(element: element) {
            return element
        }
    }
    return nil
}

In our current case we need that the predicate, besides of the current element, considers also the next one (note nextElement is optional - when we are examining the last element, there's no next element), so we create a customized version of find:

func findWithNextElement<T>(arr:Array<T>, pred:(element:T, nextElement:T?)->Bool) -> T? {
    for i in 0..<arr.count {
        let element =  arr[i]
        let nextElement:T? = i + 1 < arr.count ? arr[i + 1] : nil
        
        if pred(element: element, nextElement: nextElement) {
            return element
        }
    }
    return nil
}

We would call it like this:

let val4:String? = findWithNextElement(tuples, { (element, nextElement:(Float, String)?) -> Bool in
    return (element.0 <= search) && (nextElement?.0 > search ?? true)
})?.1


println("found: \(val4)") // found: Optional("range starts:4.0 ends: 4.375")

Here is everything in a gist, which you can copy paste in a playground. This is much nicer to follow looking at the results pane on the right, and doing live changes. Have fun!