Thursday, June 30, 2016

Swift 3 - Selection Sort Challenge

Erica Sadun has an interesting post on the Make it Swifter Challenge for a functional implementation of a selection sort.  The original challenge was posted by Adriano Ferreira on the Swift Users email list.

While the selection sort doesn't scale well with O(n^2), it does do well at performing in tight memory constraints.  It's also very easy to implement.  However,  most of the solutions submitted ended up doing a lot of memory/array copying.

Here is my attempt at solving the problem in functional way with minimal memory allocation / array copying.  Note this does request Swift-3:

func selectionSort(_ array: inout [Int]) {
    for index in 0..<array.count {
        let minIndex = array
                       .indices
                       .clamped(to: index..<array.count)
                       .min(isOrderedBefore: { array[$0] < array[$1] })
        if index != minIndex {
            swap(&array[index], &array[minIndex!])
        }
    }
}


Here is a non-mutating version of the above:


func selectionSorted(_ originalArray: [Int]) -> [Int] {
    var array = originalArray
    for index in 0..<array.count {
        let minIndex = array
                       .indices
                       .clamped(to: index..<array.count)
                       .min(isOrderedBefore: { array[$0] < array[$1] })
        if index != minIndex {
            swap(&array[index], &array[minIndex!])
        }
    }
    return array
}

As an extension to Array:

extension Array {
    
    func selectionSorted(isOrderedBefore: (Element, Element) -> Bool) -> [Element] {
        var arrayCopy = self
        for index in 0..<arrayCopy.count {
            let minIndex = arrayCopy
                .indices
                .clamped(to: index..<arrayCopy.count)
                .min(isOrderedBefore: { 
                     isOrderedBefore(arrayCopy[$0], arrayCopy[$1]) } )
            if index != minIndex {
                swap(&arrayCopy[index], &arrayCopy[minIndex!])
            }
        }
        return arrayCopy
    }

}

Example:


let x = [1, 3, 5, 2, 4, 9, 8, -5, 6, 4]
let minSort = x.selectionSorted(isOrderedBefore: { $0 < $1 })


That was my stab at making a functional version of SelectionSorted.  Please feel to leave your comments below.




Monday, November 2, 2015

Swift NSTimer and Blocks (Closures)

Introduction


I'm always a bit surprised to discover that NSTimer doesn't have support, out of the box, for blocks or closures.  So I decided to put together this simple extension to NSTimer that supports swift closures.

The NSTimer Classic Way


NSTimer has been around for a long time.  It uses the objective-c runtime to invoke some code after a period of time. The invocation can be done by either an objective-c NSInvocation object or via selectors.  Let's look at a simple example of invoking a selector in swift using a NSTimer.

class SimpleTimerTest
{
    var timer : NSTimer?
    
    func someTask( timeout:NSTimeInterval )
    {
        self.timer = NSTimer.scheduledTimerWithTimeInterval( timeout,
            target:self,
            selector:"timerCallback:",
            userInfo:nil,
            repeats:false )
    }
    
    @objc func timerCallback( timer:NSTimer ) {
        FLLog.info( "*** Timer Fired ***" )
    }    
}

It's fairly easy to invoke the selector.  One important detail is that the method invoked must be defined with @objc.  This allows the objective-c runtime access to the method. However, there is no compile time check for this, if you forget the @objc modifier then you will get an "Unrecognized selector" runtime error when the selector is invoked.

There is also no spell checking for the selector in swift so if you mess up the selector string you will also get a runtime error. Objective-c has a @selector compiler directive which will validate the selector exists at compile time, but there is no equivalent to this in swift.

Another point to consider with this approach is that the target instance of the selector will be retained by the timer. This means for the above example that SimpleTimerTest will be retained until the timer is done with it.

These basic tools can be used to implement our own extension to NSTimer that allows a block to be invoked when the timer fires.

NSTimer Block


A simple NSTimer extension can be created that allows blocks or closures to be used.  Here is an implementation that does this:

public typealias FLTimerBlock = (timeinterval:NSTimeInterval) -> Void

extension NSTimer
{
    private class TimerBlockContainer {
        private(set) var timerBlock:FLTimerBlock
         
        init( timerBlock:FLTimerBlock ) {
            self.timerBlock = timerBlock;
        }
    }
    
    public class func scheduledTimerWithTimeInterval(timeInterval:NSTimeInterval,
                                                     repeats:Bool = false,
                                                     block:FLTimerBlock) -> NSTimer
    {
        return self.scheduledTimerWithTimeInterval(timeInterval,
            target: self,
            selector:"_executeBlockFromTimer:",
            userInfo:TimerBlockContainer(timerBlock:block),
            repeats:repeats)
    }
    
    @objc class func _executeBlockFromTimer( timer:NSTimer ) {
        if let timerBlockContainer = timer.userInfo as? TimerBlockContainer {
            timerBlockContainer.timerBlock(timeinterval:timer.timeInterval)
        }
    }
}

The timer extension does a couple of nice things:
  1. The @objc time method is contained in the extension
  2. No selector spelling mistakes outside the extension
  3. The NSTimer will retain the contained TimerBlockContainer as opposed to the class using the NSTimer.  If the block needs to retain references, it will do so according to the normal block rules.
It's really easy to put this in use, just call the timer method and give it a completion block:

        NSTimer.scheduledTimerWithTimeInterval(5.0, repeats: false)
        { (timeinterval) -> Void in
            FLLog.info( "*** Timer Fired ***" )
        }

One of the tricks of this implementation is that we are using the userInfo property of the NSTimer to store our block reference.  This allows it to exist for the duration of the lifetime of the NSTimer it's associated with.

NSTimer Block Weak


One of the advantages of using the NSTimer Block approach is that it doesn't force a retain.  So the following is possible:

class SimpleTimerTest
{
    var timer : NSTimer?
    var timeoutCount : Int = 0
    
    deinit
    {
        FLLog.info( "SimpleTimerTest deinit" )
        timer?.invalidate()
    }

    func someTask( timeout:NSTimeInterval )
    {
        self.timer = NSTimer.scheduledTimerWithTimeInterval(timeout, repeats:false)
        { [weak self] (timeinterval) -> Void in
            FLLog.info( "*** Timer Fired ***" )
            self?.timeoutCount += 1
        }
    }
}

Notice here that we mark the timer block as [weak self].  This means the block will not retain self, but then we are responsible for handling cases where the block might be called without self.  Also notice, that we go ahead and invalidate the timer when we deinit.  This will release the timer and the block won't be called after the instance goes away.  Because we are doing this in deinit, we can actually define the block as [unowned self]:

func someTask( timeout:NSTimeInterval )
{
   self.timer = NSTimer.scheduledTimerWithTimeInterval(timeout, repeats:false)
   { [unowned self] (timeinterval) -> Void in
      FLLog.info( "*** Timer Fired ***" )
      self.timeoutCount += 1
   }
}


We can safely do this because we guarantee that self won't be nil within the block as the block will never be called after deinit (because of the call to invalidate).

Conclusion


I hope you found this helpful and interesting.  If you see anything incorrect or if you have different thoughts please share.  If you are interested in swift or iOS development, be sure to follow this blog.

Thanks,
Tod Cunningham



Wednesday, October 14, 2015

Swift Optionals Questions (?) and Bangs (!)

I haven’t posted in awhile, but with the Swift 2.0 release, I figured it was time to dip my toe back into the swift waters.  I wanted to share my notes and commentary on optionals.

Optional Types


Optional types provide a way to indicate that a value may be nil as opposed to having a value of some given type.  An optional is represented in swift via a simple template enum:

enum Optional<T> : NilLiteralConvertible {
         case None
         case Some(T)
        ...
}
   
So you can declare and use an optional variable like any other enum:

var temperature : Optional<Float> = .None
if temperature == .None {
          temperature.Some = Optional<Float>(70.6)
}

Given how prevalent and useful optional values are the Swift compiler has built in support for special handling of optionals through the ? and ! operators (syntactic sugar).  In addition, swift features such as literal convertibles enable the Optional type to convert nil to/from Optional.None.  Thus we can write the above as follows:

var temperature : Float? = nil
if temperature == nil {
   temperature = 70.6
}

The swift ? operator is used to specify that the value is an Optional and the compiler will automatically represent or wrap that value in an optional.

The ? operator


The example above is using the ? operator.  The ? operator means the value/type is an Optional.  It’s really just some syntactic sugar to make code more readable.  When used on a variable type declaration, this tells swift to treat/convert the type to an Optional type.  Thus the following are 100% equivalent:

var temperature : Float? = .None 
var temperature : Optional<Float> = .None

In addition, because Optional types support NilLiteralConvertible the .None can be replaced with nil as well:

var temperature : Float? = nil 
var temperature : Optional<Float> = nil

Now let’s get to how we set and access Optional values. 

Wrapping and Unwrapping


Keeping with our same example, you can see where the value 70.6 is automatically wrapped (converted to an optional):
 
temperature = 70.6                  // Auto wrapped
temperature = Optional<Float>(70.6) // Explicitly wrapped

The swift compiler knows when we are assigning into a Optional and will automatically wrap the value into an Optional.  Note: This auto wrapping doesn’t work for other types.  It is special to the Optional type.

The question is how do we get the value back out of an optional?  If you try to just access the value, you will get a compiler error as the types don't match:

    let currentTemperature : Float = temperature  // ERROR, TYPE MISMATCH

We could do it like one does it for any enum by using a switch statement:

       let currentTemperature : Float
    switch( temperature )
    {
    case .None: throw someError
    case .Some(let value): currentTemperature=value
    }

However, this is a rather long winded way of getting access to the value and would destroy code readability if this had to be done every time an Optional’s value was needed.  So Swift has several ways to unwrap an optional value:

  1. The ! operator can be used to specify the value is an optional and thus may be nil, but the optional will be implicitly unwrapped automatically upon access.  With ! if you try to access the value and it’s nil you will get an exception/crash.
  2. The optional binding method uses an if let statement to safely unwrap an optional
  3. The guard statement is another form of optional binding that safely unwraps an optional
  4. The optional chaining method allows safe chaining of operations that return optionals

Implicitly Unwrapping (!)


The ! operator can be used to specify the value is an optional and thus may be nil, but the optional will be implicitly unwrapped automatically upon access.  With ! if you try to access the value and it’s nil you will get an exception/crash.  Because of this, you need to use ! carefully.

Keeping with our same example, you can force temperature to unwrap its operational by using the ! operator.  However, an exception will be thrown if the value is nil:

    let currentTemperature : Float = temperature!     // Exception thrown if nil

You can make this safer by checking against nil before you try and access the value:

if temperature != nil {
   let currentTemperature : Float = temperature!
   print( “\(currentTemperature )” )
}

You can also use a ! operator in the declaration of a variable such as:

    var temperature2 : Float! = 72.3

When used in the variable declaration or function parameter, the variable will be treated as an optional just let the ? operator.  However, it will be automatically unwrapped on access.  So the following will work:

    let currentTemperature : Float = temperature2  // temperature2 auto unwrapped

However, if temperature2 is nil an exception will be thrown so use this carefully.  Swift also has several ways to unwrap optionals safely.

Optional Binding (if let)


To help with unwrapping of optionals in a safe way, swift has a special if let operation that only succeeds when an optional isn’t nil.  So building on our example above, we can use if let to safely unwrap temperature to currentTemperature:

if let currentTemperature = temperature {
   // Only get here if temperature != nil
   // currentTemperature will have a value
   // currentTemperature’s scope is only this block
   print( “\(currentTemperature )” )
}

Extra conditions that have to be met can be added via the where operator:

if let currentTemperature = temperature where currentTemperature < 32.0  {
   // Only get here if temperature != nil
   // currentTemperature will have a value less than 32.0
   // currentTemperature’s scope is only this block
   print( “It’s freezing \(currentTemperature )” )
}

One of the issues with optional binding is you can end up with a fair amount of nesting (pyramid of doom).  Swift 1.2 helped this out a little bit by allowing you to specify multiple optionals:

       if let currentTemperature = temperature,
          let value2 = optional2 where currentTemperature < 32.0  {
   // Only get here if temperature != nil and optional2 != nil
   // currentTemperature will have a value less than 32.0
   // currentTemperature’s scope is only this block
   print( “It’s freezing \(currentTemperature )” )
}

However, since the unwrapped values (currentTemperature, value2), are only accessible within the scope of the if let block it can still force unwanted nesting.  Swift 2.0 introduced guards to help with this problem.

Guards


Swift 2.0 introduced the concept of guard statements.  Guards can be looked at in some ways as the opposite of if let optional binding.  Guard statements execute only if the optional’s value is nil as opposed to if let executing only if the optional isn’t nil.  Guards also allow the assigned unwrapped non-nil value to be used after the guard statement.    

guard let currentTemperature = temperature else {
   print( “Unknown temperature” )
   return   // Must exit calling scope of guard
}

// currentTemperature exists and is non-nil after the guard!
print( “\(currentTemperature )” )

The code executed by the guard when the optional is nil must exit the calling context of the guard statement.  If the guard statement is in a loop then continue or break may be used.  If the guard is in a function then return is typically used.  Basically, execution within the context of the block of code containing the guard isn’t allowed to continue beyond the guard statement when the guarded optional is nil.

Optional Chaining


Optional chaining allows you to place a ? operator after the optional value on which you wish to call a property, method, etc.  This will force an optional result to be returned, and if the unwrapped optional is nil then the chain stops and nil is returned.  For example:

    let optionalValue = anOptional?.aProperty  // somevalue would be an optional
    if let value = optionalValue {
       print( “aProperty = \(value)” )
    }
   
As this is called optional chaining, these can be chained as needed.  For example:

    let optionalValue = optional?.optionalProp1?.nonOptionalProp.optionalProp2

If optional, optionalProp1, or optionalProp2 is nil then nil will be returned as the optionalValue.

Of course these can also be intermixed with the ! operator when you want to force an unwrap.  However, if the implicit unwrapped value is nil an exception/crash will happen.  For example:

    let optionalValue = optional!.optionalProp1?.nonOptionalProp.optionalProp2!

In the above example if optional is nil then as exception/crash will happen.  If optionalProp1 is nil then nil will be returned and optionalProp2 won’t get evaluated. If optionalProp2 isn’t nil but optionalProp2 is nil then it will exception/crash.

If the ? operator isn’t used in the chain then the actual value will be returned as opposed to an optional value.  For example.

    let value = optional!.optionalProp1!.nonOptionalProp.optionalProp2!

In the above example value will be the value of optionalProp2, unless one of the optionals is nil in which case you will get an exception/crash so this is very much unsafe and would be of bad practice!

Quick Summary: Questions (?) and Bang (!)


When you see the ? operator it means the value is an optional and thus may be nil.  When you see ! it also means the value is an optional and thus may be nil, but the optional will be implicitly unwrapped automatically upon access.  With ! if you try to access the value and it’s nil you will get an exception/crash.

Conclusion


I hope you found this helpful and interesting.  If you see anything incorrect or if you have different thoughts please share.

Thanks,
Tod Cunningham

References: