Thursday, January 28, 2010

Auto-formatting phone number UITextField on the iPhone

In this post, we'll use our PhoneNumberFormatter to implement an auto-formatting phone number text field in an attempt to mimic the behavior of iPhone's native apps, like Phone and Contacts.

So, let's call the text field in question myTextField. We start by calling addTarget on the text field to make it call the autoFormatTextField method in our view controller whenever it gets updated, either by the user or some other piece of code. If your view is ready, you should declare the handler as an IBAction and bind through IB. The method would then update the contents of the text fields to the formatted string returned by the formatter. If we do it that way, we'll also need to use a semaphore to prevent the method from being called endlessly.

The implementation outline would be:

// declarations

UITextField *myTextField;
int myTextFieldSemaphore;
PhoneNumberFormatter *myPhoneNumberFormatter;
NSString *myLocale; //@"us"

// init semaphore
myTextFieldSemaphore = 0;

// bind events programatically, skip when using IB.
[myTextField addTarget:self
action:@selector(autoFormatTextField:)
forControlEvents:UIControlEventValueChanged
];

// handle events
- (void)autoFormatTextField:(id)sender {
if(myTextFieldSemaphore) return;
myTextFieldSemaphore = 1;
myTextField.text = [phoneNumberFormatter format:myTextField.text withLocale:myLocale];
myTextFieldSemaphore = 0;
}
Update: As pointed out in the comments, for newer SDKs you may need to bind to UIControlEventEditingChanged. Thanks for your feedback!
//bind events

[myTextField addTarget:self
action:@selector(autoFormatTextField:)
forControlEvents:UIControlEventEditingChanged
];

Saturday, January 23, 2010

On the Fairness of Reservoir Sampling

Reservoir sampling is a family of randomized algorithms for randomly choosing K samples from a list of S items, where S is either a very large or unknown number.

A very elegant algorithm titled Algorithm R by Alan G. Waterman, is summarized as follows:

Fill up the 'reservoir' with the first k items from S
For every item S[j] where j > K
Choose an integer r between 0 and j
If r < K then replace element r in the reservoir with S[j]
One very interesting discussion with a friend led me to this problem. In this post we are going to prove that at all times, the probability of each processed item to be in the reservoir is the same for all items. In other words, after each iteration and when the algorithms terminates, all processed items will have the same probability of being included.

To initialize the reservoir, the first K items are included. At this point of time, each item is included by a probability of 1.

Later on, to process item number A, where A > K, we include it by a probability of K / A. (1)

For any of the K items in the reservoir, it will remain in the reservoir after item A is processed only in 2 cases:
1) Item A does not get included. This has a probability of ( A - K ) / A = 1 - K / A
2) Item A gets included but it does not replace the item in question, i.e. it can replace any of the other ( K - 1 ) items in the reservoir. This has a probability of ( K / A ) * [ ( K - 1 ) / K ] = ( K - 1 ) / A

So each of the K items remains in the reservoir by a probability of 1 - K / A + ( K - 1 ) / A = 1 - 1 / A

This is the same as the probability of A not replacing our item. Since the probability of A replacing any one item is 1 / A. The complement is directly found as 1 - 1 / A

Now, let P( A, B ) be the probability of item A still being included in the reservoir after item B is processed, where B >= A. Without loss of generality, we may assume that B is the next item to be processed.

For item A to remain in the reservoir after item B is processed, item A must have been included up to the point where B is to be processed. Equivalently, item A was still included after item (B - 1) was processed. In addition, for A to remain in the reservoir B must not replace it

From the discussion above, it follows that:
P( A, B ) = [ 1 - 1 / B ] * P( A, B - 1 )

Which can be expanded as:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ 1 - 1 / ( A + 1 ) ] * p( A, A )

But from (1):
P( A, A ) = K / A

As a result:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ 1 - 1 / ( A + 1 ) ] * K / A

But,
[ 1 - 1 / ( A + 1 ) ] = A / ( A + 1 )

Therefore:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ A / ( A + 1 ) ] * K / A
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * K / ( A + 1 )

Again:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * K / ( A + 2 )

We can see that this recurrence reduces to:
P( A, B ) = K / B

This is the same as the probability of item B being included. In addition, P( A, B ) is not a function of A, it only depends on B, which is the number of elements processed so far.

This means that for the next item to be processed it will have the same probability of being included as all the items that were processed before it. By maintaining this property, when the algorithm terminates, all items will have the same probability of being included in the reservoir, regardless of the size of the list.

Friday, January 22, 2010

Locale-aware phone number formatting on the iPhone

iPhone developers often find themselves trying to stick to the standards set by Apple. Most of the time, doing so is facilitated by the SDK and the results are better. Sometimes though, it's not easy at all, mainly because some APIs are not open.

One example is phone number formatting. The Contacts application utilizes an auto-formatting UITextField for phone number entry. Many business applications would make use of such functionality but it's not provided by the current SDK.

I've been through that and was not happy about the task. After procrastinating for a while, I thought of a solution and later on, I actually implemented it, and it worked well for me. I wished I could make it into the sought after NSPhoneNumberFormatter, but I was done with the task. I thought I should share it with fellow iPhone developers. I hope many will be able to use it right away as-is, and it would be great if someone could finish the job and make the formatter.

I acquired the predefined localized phone formats from the UIPhoneFormats.plist. I was mainly interested in the us locale, but I kept the implementation generic. The main idea is to build some sort of a finite state machine (FSM) for the phone format and use it to process the input string. The FSM will both validate and add formatting characters to the string as needed. If the whole input could be processed successfully, then it is a valid format and the output is returned.

The problem that I didn't solve yet, is when the string can be matched to more than one format. I had to manually sort the formats from the most restrictive to the least restrictive, so the one that comes first is always selected. This hack was okay for US formats, but there was nothing I could do with the last 3 UK formats since, to me, they are essentially the same. I guess this can be worked around somehow.

I'll post the code here, and will try to add more comments later. Please feel free to add your comments or ask for clarifications.

Update 02/14/2010: I'm so glad to have habermann24 join in and create his phoney ruby lib. If your Ruby/Rails application deals with phone numbers, you got to check it out!

Update 09/08/2010: Check out libphonenumber: Google's common Java, C++ and Javascript library for parsing, formatting, storing and validating international phone numbers. The Java version is optimized for running on smartphones. You'll need to look for the AsYouTypeFormatter.java. Update++, check out the comment below by +SpoofApp.

Update 08/15/2011: Updates on libphonenumber: New development of the library will be presented in the 35th Internationalization and Unicode Conference in a session titled: libphonenumber - The Swiss Army Knife of International Telephone Number Handling. See session description for details.

Update 02/06/2015: libphonenumber on Github by Google Internationalization (i18n).

PhoneNumberFormatter.h

//  Created by Ahmed Abdelkader on 1/22/10.

// This work is licensed under a Creative Commons Attribution 3.0 License.

#import <Foundation/Foundation.h>

@interface PhoneNumberFormatter : NSObject {
//stores predefiend formats for each locale
NSDictionary *predefinedFormats;
}

/*
Loads predefined formats for each locale.

The formats should be sorted so as more restrictive formats should come first.

This is necessary as the formatting code processes the formats in order and
selects the first one that matches the whole input string.
*/
- (id)init;

/*
Attemps to format the phone number to the specified locale.
*/
- (NSString *)format:(NSString *)phoneNumber withLocale:(NSString *)locale;

/*
Strips the input string from characters added by the formatter.
Namely, it removes any character that couldn't have been entered by the user.
*/
- (NSString *)strip:(NSString *)phoneNumber;

/*
Returns true if the character comes from a phone pad.
*/
- (BOOL)canBeInputByPhonePad:(char)c;

@end

PhoneNumberFormatter.m
//  Created by Ahmed Abdelkader on 1/22/10.

// This work is licensed under a Creative Commons Attribution 3.0 License.

#import "PhoneNumberFormatter.h"

@implementation PhoneNumberFormatter

- (id)init {
NSArray *usPhoneFormats = [NSArray arrayWithObjects:
@"+1 (###) ###-####",
@"1 (###) ###-####",
@"011 $",
@"###-####",
@"(###) ###-####", nil];

NSArray *ukPhoneFormats = [NSArray arrayWithObjects:
@"+44 ##########",
@"00 $",
@"0### - ### ####",
@"0## - #### ####",
@"0#### - ######", nil];

NSArray *jpPhoneFormats = [NSArray arrayWithObjects:
@"+81 ############",
@"001 $",
@"(0#) #######",
@"(0#) #### ####", nil];

predefinedFormats = [[NSDictionary alloc] initWithObjectsAndKeys:
usPhoneFormats, @"us",
ukPhoneFormats, @"uk",
jpPhoneFormats, @"jp",
nil];
return self;
}

- (NSString *)format:(NSString *)phoneNumber withLocale:(NSString *)locale {
NSArray *localeFormats = [predefinedFormats objectForKey:locale];
if(localeFormats == nil) return phoneNumber;
NSString *input = [self strip:phoneNumber];
for(NSString *phoneFormat in localeFormats) {
int i = 0;
NSMutableString *temp = [[[NSMutableString alloc] init] autorelease];
for(int p = 0; temp != nil && i < [input length] && p < [phoneFormat length]; p++) {
char c = [phoneFormat characterAtIndex:p];
BOOL required = [self canBeInputByPhonePad:c];
char next = [input characterAtIndex:i];
switch(c) {
case '$':
p--;
[temp appendFormat:@"%c", next]; i++;
break;
case '#':
if(next < '0' || next > '9') {
temp = nil;
break;
}
[temp appendFormat:@"%c", next]; i++;
break;
default:
if(required) {
if(next != c) {
temp = nil;
break;
}
[temp appendFormat:@"%c", next]; i++;
} else {
[temp appendFormat:@"%c", c];
if(next == c) i++;
}
break;
}
}
if(i == [input length]) {
return temp;
}
}
return input;
}

- (NSString *)strip:(NSString *)phoneNumber {
NSMutableString *res = [[[NSMutableString alloc] init] autorelease];
for(int i = 0; i < [phoneNumber length]; i++) {
char next = [phoneNumber characterAtIndex:i];
if([self canBeInputByPhonePad:next])
[res appendFormat:@"%c", next];
}
return res;
}

- (BOOL)canBeInputByPhonePad:(char)c {
if(c == '+' || c == '*' || c == '#') return YES;
if(c >= '0' && c <= '9') return YES;
return NO;
}

- (void)dealloc {
[predefinedFormats release];
[super dealloc];
}

@end

Testing against a web server that doesn't respond, aka infinite delay

I wanted to simulate the situation when the server doesn't respond, without changing much. A friend of mine suggested I use any of the unassigned IPs on our LAN. Exactly what I was looking for! The request timed-out and I was able to see how my application would act in this case. We may also add an entry in the hosts file to name this black-hole-server, so it can be used later as needed. The hosts file will also enable us to override the DNS look-up and route the requests to the black hole, in case the host name was hard-coded/fixed in a binary, and we don't want to/can't modify the code.

Thursday, January 14, 2010

Daniel Pink on the surprising science of motivation - TEDTalks

A friend of mine recommended this video and I liked it so much I shared it immediately with other friends. As some of them were very busy to watch the whole thing, they asked for a summary. And since the topic was still active on my mind, I decided to do it for them and later I decided to make it available to everybody on this blog.

I have to emphasize that this text is based entirely and solely on this great talk. It is a mere attempt to provide a text version and summarize the main ideas, and I have to say it doesn't come close to the quality of the talk or the performance of the speaker.



A case for rethinking how we run our businesses.

Scientists of human behavior questioned the power of incentives. These contingent motivators: If-you-do-this then you-get-that, work in some circumstances but for a lot of tasks they actually either don't work or often do harm. This is one of the most robust findings in social science and also one of the most ignored.

There's a mismatch between what science knows and what business does.

Our business operating systems, the set of assumptions and protocols beneath our businesses, how we motivate people, how we apply our human resources. It's built entirely on these extrinsic motivators. Around carrots and sticks. This is actually fine for many 20th century's tasks. But for 21st century's tasks, that mechanistic, reward-and-punishment approach often doesn't work, and often does harm.

If-then rewards work really well for unsophisticated tasks, where there's a simple set of rules and a clear destination. Rewards by their very nature, narrow our focus. Concentrate the mind. That's why they work in so many cases. But for real problems, we don't want to narrow our focus and restrict our possibilities. For example, to overcome what is called functional fixedness.

Routine, rule-based, left-brained work, certain kinds of accounting, certain kinds of computer programming has become fairly easy to outsource, fairly easy to automate. Software can do it faster, low-cost providers around the world can do it cheaper. So what really matters, are the more right-brained, creative, conceptual kinds of abilities.

Think about your work. Are the problems you face the kind of problems with a clear set of rules and a single solution? No. The rules are mystifying. The solution, if it exists at all, is surprising and not obvious. If-then rewards, don't work in that case. This is not a feeling. This is not a philosophy. This is a fact, a true fact.

Too many organization are making their decisions, their policies about talents and people., based on assumptions that are out-dated, unexamined and rooted more in folklore than in science. If we really want high performance on the definitional tasks of the 21st century the solution is not to do more of the wrong thing: to entice people with the sweet carrot or threaten them with the sharper stick. We need a whole new approach.

The good news about all this is that the scientists who've been studying human motivation have given us this new approach. It's an approach built much more around intrinsic motivation. Around the desire to do things because they matter, because we like it, because they're interesting, because they're part of something important.

That new operating system for our businesses revolves around 3 elements: autonomy, mastery and purpose.
Autonomy: the urge to direct our own lives.
Mastery: the desire to get better and better at something that matters.
Purpose: the yearning to do what we do in the service of something larger than ourselves.

Today, we're going to talk only about autonomy.

In the 20th century, we came up with this idea about management. Management didn't emanate from nature, it's like: it's not a tree, it's a television set. Somebody invented it. And it doesn't mean it's going to work forever. Traditional notions of management is great if you want compliance. But if you want engagement, self-direction works better.

Let me give you an example of some kinds of radical notions of self-directions. You don't see a lot of it, but you see the first stirrings of something really interesting. Because what it means is: paying people adequately and fairly, absolutely, getting the issue of money out of the table, and then giving people much of autonomy. The 20% time, done famously at Google, where engineers can work 20% of their time on anything they want. They have autonomy over their time, their tasks, their teams, their techniques: radical amounts of autonomy. And at Google, as many of you know, about half the new products in a typical years are burst during that 20% time like: Gmail, Orkut and News.

Another more radical example of autonomy: something called the results only work environment or ROWE. In a ROWE people don't have schedules. They show up when they want, they don't have to be at the office at a certain time or any time. They just have to get the work done. How they do it, when they do it, where they do it is totally up to them. Meetings in these kinds of environments are optional. What happens? almost across the board: productivity goes up, worker-enga worker-satis turn-over goes down.

Autonomy, master, and purpose. These are the building blocks of a new way of doing things.

Now, some of you might look at this and say: mmm, that sounds nice but it's Utopian. And I say nope. I have proof. In mid 1990's Microsoft started an encyclopedia called Encarta. They deployed all the right incentives. They payed professionals to write and edit thousands of articles. Well compensated managers oversaw the whole thing to make sure it came on-budget and on-time. Few years later, a new encyclopedia get started. A different model. Do it for fun. No one gets payed a cent, or a euro or a yen. Do it because you like to do it. Now if you had, just 10 years ago, if you had gone to an economist, any where, and said: hey, I have these 2 different models for creating an encyclopedia, if they went head to head, who'd win? 10 years ago, you couldn't not find a single sober economist on planet earth who'd predicted the Wikipedia model.

Intrinsic motivators vs. extrinsic motivators. Autonomy, mastery and purpose vs. carrots and sticks. And who wins?

To wrap-up (17:20)

There's a mismatch between what science knows and what business does. And here's what science knows:
1) Those 20th century's rewards, those motivators, we think are the natural part of business: Do work, but only in a surprisingly narrow band of circumstances.
2) Those if-then rewards, often destroy creativity.
3) The secret to high performance isn't rewards and punishments, but this unseen intrinsic drive. The drive to do things for their own sake. The drive to do things because they matter.

And here's the best part. We already know this. The science confirms what we know in our hearts. So, if we repair this mismatch between what science knows and what business does. If we bring our notions of motivation into the 21st century. If we get past this lazy, dangerous, ideology of carrots and sticks, we can strengthen our businesses, we can solve a lot of our real problems and maybe, maybe we can change the world.