Nicolas Goles

Code & Randomness

A Simple Trie Implementation in Swift

I’ve been on and off Apple’s Swift in the last few months. I like where the language is going, but I picked it up extremely early (basically on day 1). I got a bit tired of getting my code to fail on every Xcode update, so after a lot of that, I started taking things at a slower pace.

Swift is now much better than when the language first saw the light of day last year, things are not -that slow- anymore (still there’s enough of low hanging fruit waiting to be optimized). Also, the last time I updated Xcode, my code didn’t seem to break… so things are looking much better.

Anyway, I love the Trie data structure and it’s applications, so I decided to implement a really basic one in Swift.

This is the result, you can further customize it to fit more specific use cases.

Trie.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Pardon my n00b Swift

class TrieNode {
    var letter:Character
    var fullWord:Bool
    var child = [Character:TrieNode]()

    init (letter_:Character, fullWord_:Bool) {
        letter = letter_
        fullWord = fullWord_
    }
}

class Trie {
    var root:TrieNode = TrieNode(letter_: "\0", fullWord_: false)

    func insertWord(word:String) {
        let wordLength = countElements(word) - 1
        var currentNode:TrieNode? = root
        var letterCounter = 0

        for letter in word {
            var fulllWord = letterCounter == wordLength ? true : false
            letterCounter = letterCounter + 1

            if currentNode!.child[letter] == nil {
                currentNode!.child[letter] = TrieNode(letter_: letter, fullWord_: fulllWord)
            }

            currentNode = currentNode!.child[letter]
        }
    }

    func find(key:String) {
        let keyLength = countElements(key)

        var currentNode:TrieNode? = root
        var characterCount = 0

        for character in key {
            currentNode = currentNode!.child[character]

            if currentNode == nil {
                return
            }

            characterCount = characterCount + 1

            if characterCount == keyLength && currentNode!.fullWord == true { // we reached destination
                println("Key \(key) Found!")
                return
            }
        }
    }
}

// For some Playground fun!

var trie:Trie = Trie()
trie.insertWord("nicolas")
trie.insertWord("nighthawk")
trie.find("nicolas")
trie.find("nighthawk")

I wanted to implement serialization without using NSCoding, and ideally avoiding O(n) times when rebuilding the Trie. Apparently NSCoding, or other Cocoa APIs are the way to go right now, so I left it out.

An interesting thing to try, would be to implement a succint Trie, which is not as efficient in lookups as a regular trie, but can be easily serialized using a tiny amount of space. They can still be pretty fast depending on the required application, and because bit manipulation is a real thing in Swift, my guess is that you could get away with a pretty efficient implementation.

Building a succint trie in Swift is a challenge that I’ll leave for the future, anyway, I hope my simple Trie implementation is useful for someone new at Swift.

Exploring Auto Layout With a UITabBar Replacement

I’ve been experimenting with Apple’s Auto Layout for a while. I really like the technology. If you like Constraint Satisfaction Problems as I do, you will certainly dig Auto Layout too.

This post is a general overview about how I used Auto Layout to generalize constraint generation for the creation of a UITabBar View which is part of a custom UITabBarController. I could have just hard-coded the constraints to solve my own problem, but who doesn’t like a little challenge?

Note: If you wan’t to check the project out, GGTabBar is on Github. There’s a decent Example.xcodeproj that holds a couple of integration tests, and show how NGTabBar is used.

UITabBarController

A TabBar view has 5 evenly-separated UITabBarItems, each one matches a UIViewController. When you add more, the fifth item becomes a more tab, which you can tap to access a UITableView that can contain up to N rows (each row corresponding to a particular view controller).

I needed a custom replacement for a UITabBar, won’t go into the particular reasons , but I needed something were the actual TabBar Items were UIView based too. For the time being I decided to use UIButtons instead of a more sophisticated item abstraction.

Auto Layout

So, basically what I had to create was a view with N evenly separated Subviews (buttons).

When using Auto Layout, the best option that I found to make something like this is to use separator views. A separator view is a view (visible or invisible) located between two visible views.

So, if we had two UIButtons a separator would look like the blue box between Button 1 and Button 2 in the following figure.

You can easily deduce that for N buttons there will always be N - 1 separators.

There’s another thing that I did though, I added two more separators that I called marginSeparators.

Right now the margin separators act in the exact same way that the regular separators with the sole exception of always being in the margins. This could allow me to expose ways to customize their width in the future to allow more flexibility. I could also decide to remove them and make them regular separators though…

Constraints

GGTabBar

There are two rather important sets of auto layout constraints acting on the GGTabBar Subviews. The first one is that all the separators and margin separators must be of equal width:

GGTabBar.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
- (NSArray *)separatorWidthConstraintsWithSeparators:(NSArray *)separators
{
    NSMutableArray *constraints = [[NSMutableArray alloc] init];

    [separators enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        UIView *separator = (UIView *)obj;
        UIView *targetSeparator;

        if ([obj isEqual:[separators lastObject]]) {
            targetSeparator = [separators firstObject];
        } else {
            targetSeparator = [separators objectAtIndex:(idx + 1)];
        }

        NSLayoutConstraint *constraint;
        constraint = [NSLayoutConstraint constraintWithItem:separator
                                                  attribute:NSLayoutAttributeWidth
                                                  relatedBy:NSLayoutRelationEqual
                                                     toItem:targetSeparator
                                                  attribute:NSLayoutAttributeWidth
                                                 multiplier:1.0
                                                   constant:0.0];
        [constraints addObject:constraint];
    }];

    return constraints;
}

The second important set of constraints, involves creating a horizontal constraint among all the Buttons, Separators and Margin Separators. I won’t go into the specifics here, but you can always check out the XCTest file to build the constraint in GGTabBarTests.m.

The resulting visual constraint string looks like this:

GGTabBar.m
1
@"H:|[marginSeparator1][button1][separator4][button2][separator5][button3][marginSeparator2]|"

Note The numbers correspond to the corresponding views ids.

GGTabBarController

There’s nothing extremely fancy going on in the actual controller. The only thing worthy to say is that there are two views (GGTabBar View and a Presentation View) that are also constrained using Auto Layout. The Presentation View contains the active tab bar item controller view.

You can check out how this simple constraints are created in GGTabBarController.m layoutTabBarView method.

Moving forward

This particular project meets my current App requirements quite well. I may extend it to allow more customization options like TabBar height, tints, colors, background image, etc.

Hope you liked it, and if you have any questions feel free to reach me on Twitter

Naive Snippets With Apple’s Swift Lang

I guess that if you’re into iOS/OS X development and watched WWDC 2014 Keynote, the whole new Swift Lang caught your attention. Been playing a bit with the lang in my spare time (not a lot this days).

Been really enjoying what I’ve done. Here are some little snippets

Sieve of Eratosthenes

Here is my naive implementation of the Sieve of Eratosthenes in Swift. It was my first little program (wrote it in a minute of idle office time). Try in a Playground.

eratosthenes.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//
// Sieve of Eratosthenes
//

let N = 1000;
var i = 2;
var array = Bool[](count:N, repeatedValue:true);

for i in 2..array.count {
    for var j = 2; j * i < array.count; ++j {
        if array[j * i] {
            array[j * i] = false
        }
    }
}

for i in 2..array.count {
    if array[i] {
        println(i);
    }
}

NSCoding

Here’s me playing around with NSCoding in Swift… it fails do decode the object when in a Playground (works fine in a .swift file). Filed a Radar on this one.

NSCoding.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import Foundation;

class Test : NSObject, NSCoding {
    var radius:Int = 0;

    init() {
        self.radius = 99
    }

    // NSCoding

    func encodeWithCoder(aCoder: NSCoder!) {
        aCoder.encodeInteger(radius, forKey: "radius");
    }

    init(coder aDecoder: NSCoder!) {
        super.init();
        self.radius = aDecoder.decodeIntegerForKey("radius")
    }

}

var t:Test = Test();
t.radius = 100;

NSKeyedArchiver.archiveRootObject(t, toFile: "a_file");
var y:Test = NSKeyedUnarchiver.unarchiveObjectWithFile("a_file") as Test;

So that has been my adventure so far. Sadly haven’t been able to write more code but I’m thinking about porting one personal ‘in progress’ project to Swift… it may never ship… but it should be fun enough.

Hoping to come back with more snippets!!

5 Months After Switching to Colemak

I started playing around with Colemak exactly 5 months ago.

What is Colemak

Quoting from the website, Colemak is a modern alternative to QWERTY and Dvorak keyboard layouts. It is designed for efficient and ergonomic touch-typing in English. According to their website, Colemak is now the third more popular keyboard layout for English typing after QWERTY and Dvorak.

Why did I make the switch

I’ve been a QWERTY user since I started playing around with my Macintosh 512k at home when I was 4 years old. I mention this just to illustrate that my brain was pretty wired to this layout. I’m also an amateur Piano Player, I currently enjoy struggling with Jazz and improvisation these days. I started playing when I was 7 years old, and I almost studied music for a living.

Playing a lot of piano made me very aware of how to avoid common playing injuries mostly due to bad technique, and I guess I apply that knowledge to everything else that I do, and a thing that I do a lot is writing (code or human languages) in my computer.

Piano playing made me develop some pretty serious strength with my fingers and I think this has been the reason of me being able to rapidly wear out the classic & cheap silicon membrane keyboards. I used to ran out (kill) several Apple Keyboards every year (2 on average), and in Chile they were quite expensive… often doubling the US price.

In the beginning what I did was to find some alternatives and in the year 2006 I got an early generation Das Keyboards with the Blue MX Cherry Switches. The Das is a mechanical keyboard, and it’s in fact on that same exact keyboard that I’m writing this post. I effortlessly used the Das for a long time, but when I finally got my Engineering degree and started working full time writing software I started developing some pain in my hands, mainly on the left wrist.

At the time I read a bit about ergonomics and keyboard layouts and took two main measures:

  1. Trying to avoid using the mouse at all (subject for a future post).
  2. Switching away from the non ergonomic QWERTY layout to something like Dvorak or Colemak.

Migrating to a Cheaper VPS

A couple of weeks ago I decided that I was spending way too much money on my VPS. I was using VPS.net, a service that around 3+ years ago made sense for me, but that I can’t stand to use anymore in it’s current state. I was spending around 43 USD/Month on it, automatic snapshots and a couple of CPU nodes.

It’s not 2010 anymore!

VPS servers have become extremely cheap, unless you’re running some serious services, you can reduce your costs by a considerable amount. I googled around and noticed that there are many vendors of cheap & solid VPS out there. The first that I found was Digital Ocean, but now I would advice you to take a look at RamNode first.

Both of these services cost around 5 USD/Month for ~512 MB Ram and ~10-20 GB of SSD storage (and my Digital Ocean Node is located in SFO).

Goal

I was still running around 6 websites in my old VPS, the biggest one was running Apache, Wordpress & MySQL. Horrible. It was an old Blog of mine that I haven’t updated in 2+ years but that had a solid base of technical posts and more than a few page views. My idea was to merge it’s content with the new personal blog, and to migrate the other websites.

The Plan

Avoid vendor lockdown. Prices are going down, if my VPS vendor goes to hell (or degrades it’s performance too much for my needs), I want to be able to migrate in a fast and timely fashion, and when I say migrate, I more or less mean git push new_vps master.

Strategy

  1. Serve pure static content, no DB, no Ruby, Python, PHP, etc.
  2. Nginx & Simple Virtual Hosts Config.

Why?

Because I can, I’m just serving some personal/not high priority services on this VPS, don’t need anything sophisticated.

VPS are getting cheaper, I want to completely avoid the need of a database, migrations are a PITA, they fail. I’m solely relying on git these days.

New Blog

I migrated the whole website of Gando Games to this octopress blog, I wansn’t updating Gando Games blog anymore, but some articles had a lot of visits per day so I recovered all the posts. The previous blog was an old Wordpress install that I didn’t want to manage anymore, the VPS was also quite expensive so I really wanted to drop it.

I redirected the requests to all the previous posts to their ported versions to this blog, if you find format errors, missing images, or other stuff that seems wrong, please report to me via twitter.

In the next days I’ll be posting how did I transition to octopress from wordpress. Migration scripts, nginx configuration, DNS redirection and some Vim tricks that where helpful in the process.

Happy New Year

It’s already 2013!

It’s amazing how time flies! 2012 was a great year in so many aspects. Met new people, spent some great moments with my friends, learned so much (both about engineering & about myself). I also got my engineer degree, which doesn’t hurt.

As you can see my blog also got a new face, I hope that it will help me to focus on the writing.

2013 Dream List

  1. Learn Functional, learn more than the surface of a functional language (Scheme would be a good candidate).
  2. Grow up my personal iOS Apps portfolio, I’m thinking on +1 game and +1 reading app.
  3. Go test driven on mobile, have been a bit lazy about it… given my days with Rails it should matter more to me.
  4. Level up my Vim, I will keep working on my Vim skills. VimGolf does really help in this department… learning techniques from other skilled Vimers is awesome.
  5. 100 wpm, A couple of months ago I made the switch from QWERTY to Colemak. Currently I’m typing at 70 wpm (words per minute) on average, that’s about 80% of my QWERTY speed. I would like to reach 120% of my previous speed, which would be 100 wpm.
  6. More Posts, I’ll try to make time for blogging a bit more than last year… I’ll try to post a minimum of one technical article each month and a couple of random rants about programming/engineering every month.
  7. Contribute to an Open Source project, depending of how things turn out this year (just graduated so haven’t even started to search for a job more seriously), I’ll try to contribute to one of the several Open Source projects that I use everyday… I’ll even try to blog a bit about it.

There are several more items which are more on the personal side than on the technical one, so I kept them away from the previous listing :^)

I think that would be it… looking forward for the new challenges that will arise this year, complemented by this sort of list it should be a very exciting 2013!

Lua Tutorial: C Bindings

Intro

In this blog post I want to make a rather short but straight to the point Lua Tutorial. The objective is to learn how to manipulate the Lua stack with the Lua C API in order to create Lua bindings.

Motivation

I wrote this tutorial to prove that it’s rather easy to manipulate the Lua stack and create Lua C bindings yourself without any sort of third-party frameworks.

It’s rather surprising how a lot of people seem to be looking for the holy grial of the Lua binding Frameworks.

They come in all flavors and styles, and all of them have their strengths and weaknesses, but it’s not a bad idea to think a bit before just picking one of this frameworks “blindly” or because of fear.

Myths

  1. Using the Lua C API is hard

    This one is a classic, I’ve heard about it a thousand times. Using the Lua C API is not hard at all, specially if you’re doing rather simple things like creating single function bindings which is what most of people want to do in the first place. While manipulating the Lua stack can get a bit more complex when doing very specific stuff, normally it’s not.

  2. Using the Lua C API is a waste of time

    Using the API is often a great excersise for several reasons, one of the most important ones is that it will reveal the real complexity of the Lua integration that you’re trying to achieve for your application thus allowing you to take a more informed decision if things get just too hard or time consuming and you need to pickup a Lua Binding Framework. If you really tried to make the integration yourself, you will get a good grasp of what features will be more important for your project.

    On the other side, maybe you’ll end-up creating a rather simple set of bindings which work wonders for your project and that you can extend on-demand instead of adding a huge framework just for binding a couple of function calls.

Continuous Integration With Jenkins

I don’t think I should go all over  the “Why is continuous integration important?” topic all over again!, there are many great articles about it ( I recommend you to read Build Server: The Hearbeat of The Project by Noel Llopis ). So, we know that continuous integration is great, it avoids several things that can slow us down, or can even degrade the quality of our products.

Some of this things are:

  • Making sure our project builds on all platforms.

  • Making sure the Unit Test and Integration Tests pass on all platforms.

  • Creating different build setups for Beta Testers / Production / Debugging

  • Letting the person that broke the build know where did it happen immediately.

This things are great when working alone as a “Single Man Team”, but I think continuous integration is a must when working on a 2+ persons team. Seriously, I can’t count the number of hours saved by using C.I, it’s just so great to be able to send the beta testers a URL address so that they can get the “goods” :D.

For this week iDevBlogADay post, I will talk about how I use Jenkins to build Xcode projects. Remember that you can always follow me on Twitter if you want to contact me directly :)

Automating Xcode 4 Template Generation

Hello again!,

It’s a nice day in the French Riviera ( or Côte d’azur )!, it’s been more work than pleasure here, but I guess life is good :D

In this iDevBlogADay post I will describe how we managed to automate our needs for Xcode 4 template generation. We wanted to automate it because we use a little Engine here at Gando Games (GG), and project templates where more or less a must for us. I have been reading everywhere about project templates in Xcode 4, and I must admit that it’s a rather obscure process. In order to understand a bit more, I followed the Boreal’s Kiss “A minimal project template for Xcode 4” article. After reading it, I realized that since our toolset was changing quite often, we where going to need to somehow automate the generation of Xcode 4 Templates for our internal engine, plus I thought it was a cool thing to do :)