TweetFollow Us on Twitter

Foundation's Tool

Volume Number: 20 (2004)
Issue Number: 5
Column Tag: Programming

Getting Started

by Dave Mark

Foundation's Tool

When I was in college (long ago, boys and girls), one of my all-time favorite classes was Professor Forest's data structures course. We used Knuth's Sorting and Searching Algorithms text as our bible and explored all kinds of data structures. My favorite exercise was building a binary tree dictionary implementation using tree balancing techniques to keep the dictionary from leaning too far to one side.

Before we dig into this month's program, I wanted to take a few minutes to explore the thinking behind a simple binary tree dictionary. Even though this doesn't apply directly to our program, I think this is some valuable food for thought, especially if you've never played with binary trees before.

The Binary Tree Dictionary

Figure 1 shows a simple binary tree diagram. The structure that is common to all nodes of the tree features a text string and two pointers, one to the left child and one to the right child. In Figure 1, the node holds the text string cat and both child pointers are set to null. Note that there is a root pointer that points to the first node in the tree.


Figure 1. A binary tree dictionary containing the word cat and two null pointers.

One way to implement a dictionary is to build a node every time the user enters a new word, then place the node in the tree. A simple method is to insert the first word at the root of the tree, as we did with cat in Figure 1. Then, place the next word entered using the left pointer if the word is before cat in the dictionary and using the right pointer if the word is after cat in the dictionary.

As an example, Figure 2 shows what happens when I insert the word apple into the dictionary structure. Note that the cat node's left child points to the apple node and its right node remains null, while both of the apple nodes are set to null.


Figure 2. Adding apple to the dictionary.

Figure 3 shows what happens when you add the word egg to the tree, followed by the word dog and then zebra. Note that dog occurs after cat, but egg is already there. So dog is placed as the left child of egg. When zebra is added to the tree, it goes to the right of cat, then to the right of egg.


Figure 3. More words in the dictionary.

You can see how you'd add words to the dictionary. To look up a word, you'd start at the root node, then work your way down into the tree. To look up dog, you'd start by comparing dog to cat. Since it is not a match, you'd see that dog comes after cat and follow the right child pointer. When you get to egg, you'd follow the left child pointer (cause dog comes before egg) and you'd find the dog node.

So what happens when you find the dog node? Well, for this to be useful, the dog node would likely have more info in it than just the key value used for lookup. You'd either have an extra pointer to a data block or the data you are looking up would be embedded in the node along with the left and right child pointers.

For example, you might have a pointer to an object containing the definition of the node's word, along with a list of pointers to synonyms of the word. This gives you a structure that serves as both a dictionary and a thesaurus.

One pitfall of this approach is the lack of balance that can occur. For example, imagine what would happen if the very first word entered into the dictionary was aardvark. Chances are very good that the left child node would never get used and that the entire dictionary would hang off the right child of the root node. Can you see this?

One solution to this problem is called tree-balancing. After the dictionary is built, it is passed through a tree balancing routine. This function walks the entire tree looking for the key value that belongs exactly in the middle. The tree is then rebuilt with that value as the root node. Again, this is a simple example, but you can see how this would create a more balanced tree. And this turns out to speed up the average search time for the tree. Why? When the tree is more balanced, each level is filled in and the average number or comparisons needed to find a match in the tree goes down. One way to convince yourself of this is to imagine a completely unbalanced, right-leaning tree where every single entry hangs off of a right child. If there are 200 entries in the dictionary, the average search depth will be 100, since the tree will be 200 nodes deep.

In a perfectly balanced tree. You'll have 1 root node, then 2 level 2 nodes, 4 level 3 nodes, 8 level 4 nodes, etc. In that balanced tree, you'll be able to fit 200 nodes quite comfortably in 8 levels of the tree. The worst case search of that tree will require 8 comparisons. Much better than the worst case of 200 comparisons in the extremely unbalanced tree.

I love this stuff. Do you find this interesting? If so, let me know and I'd be more than happy to do more in future columns. For now, you might check out these pages:

http://www.semaphorecorp.com/btp/algo.html

http://whatis.techtarget.com/definition/0,289893,sid9_gci508442,00.html

for a nice discussion of b-trees. Note that the second URL has three commas interspersed towards the end.

In the meantime, let's get back to our regularly scheduled Cocoa program.

The Lottery

For this month's program, we're going to continue on our journey through Aaron Hillegass' excellent Cocoa Programming for Mac OS X. I am fortunate to have in my hot little hands a draft copy of the second edition, which should be hitting bookstores about the time you are reading this.

We'll be building a Foundation Tool project, basically an Objective C program that uses Cocoa but confines its user interface to the command line. The program uses the NSMutableArray class to create a list of lottery entries. Aaron claims this will make us fabulously wealthy. We shall see.

Create the Project

Start up Xcode and create a new Foundation Tool project. Call it lottery. One of the first things you'll notice is Xcode indexing your project, making searches much faster.

In the Groups & Files pane, open the lottery group and the Source subgroup. Now select the file main.m. When you click on the file, the contents of main.m should appear in the editing pane of the project window. If the editing pane does not appear, click on the Show Editor icon in the toolbar. It's the fourth icon, just to the right of the stop sign icon.

Here's the default code in main.m:

#import <Foundation/Foundation.h>
int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    // insert code here...
    NSLog(@"Hello, World!");
    [pool release];
    return 0;
}

Replace the existing code with the following:

#import <Foundation/Foundation.h>
int main (int argc, const char * argv[])
{
   NSMutableArray *array;
   int i;
   NSNumber *newNumber;
   NSNumber *numberToPrint;
   
   NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
   array = [[NSMutableArray alloc] init];
   for ( i=0; i<10;i++) {
      newNumber = [[NSNumber alloc] initWithInt:(i*3)];
      [array addObject:newNumber];
   }
   
   for ( i=0; i<10; i++ ) {
      numberToPrint = [array objectAtIndex:i];
      NSLog( @"The number at index %d is %@", i,
            numberToPrint );
   }
   
   [array release];
   [pool release];
   return 0;
}

    Danger, Will Robinson!!! There is a memory leak in the program you've just entered. If you have a bit of Cocoa experience, see if you can figure out what we did wrong here. Not to worry, though. We'll definitely fix the leak later on in the column.

Build and run the program. Something similar to the following should appear in your Run window:

2004-03-29 20:26:52.491 lottery[553] The number at index 0 is 0
2004-03-29 20:26:52.520 lottery[553] The number at index 1 is 3
2004-03-29 20:26:52.532 lottery[553] The number at index 2 is 6
2004-03-29 20:26:52.554 lottery[553] The number at index 3 is 9
2004-03-29 20:26:52.561 lottery[553] The number at index 4 is 12
2004-03-29 20:26:52.567 lottery[553] The number at index 5 is 15
2004-03-29 20:26:52.574 lottery[553] The number at index 6 is 18
2004-03-29 20:26:52.581 lottery[553] The number at index 7 is 21
2004-03-29 20:26:52.589 lottery[553] The number at index 8 is 24
2004-03-29 20:26:52.596 lottery[553] The number at index 9 is 27
lottery has exited with status 0. 

In a nutshell, this code builds a modifiable (i.e., mutable) array of objects, then stores a pointer to an NSNumber object in each array element.

Whenever I encounter a Cocoa class I haven't seen before, I like to use Xcode to look the class up in the documentation. Hold down the option key and double-click on the word NSMutableArray in the source code. After a bit of searching, Xcode will bring up the Developer Documentation window (see Figure 4) containing a detailed description of the NSMutableArray class. You'll see that it inherits from the NSArray class, that it conforms to a variety of protocols (guarantees to offer a specific set of methods laid out in each protocol declaration), and find out where its headers are declared.


Figure 4. The Developer Documentation window that appears when you OPTION double-click on NSMutableArray.

Here are a few lines from the doc that are definitely worth their weight in code:

    The NSMutableArray class declares the programmatic interface to objects that manage a modifiable array of objects. This class adds insertion and deletion operations to the basic array-handling behavior inherited from NSArray.

    NSMutableArray methods are conceptually based on these primitive methods:

    addObject:

    insertObject:atIndex:

    removeLastObject

    removeObjectAtIndex:

    replaceObjectAtIndex:withObject:

    The other methods in its interface provide convenient ways of inserting an object into a specific slot in the array and removing an object based on its identity or position in the array.

    When an object is removed from a mutable array, it receives a release message. If there are no further references to the object, the object is deallocated. Note that if your program keeps a reference to such an object, the reference will become invalid unless you remember to send the object a retain message before it's removed from the array. For example, if anObject isn't retained before removing it from the array, the third statement below could result in a runtime error:

id anObject = [[anArray objectAtIndex:0] retain];
[anArray removeObjectAtIndex:0];
[anObject someMessage];

Note that the primitive methods listed are links to the detailed description of those methods found later in the same window. Think of NSMutableArray as a linked list of objects where you can add objects to the list at a specific index and replace an object in the list with a different object that you specify.

The term mutable means changeable. An NSMutableArray is something you can change. An NSArray is immutable, meaning once you specify it, you are stuck with it. Why would you ever want an NSArray? One classic use is when you want to read in the contents of a file (perhaps a series of records) and store it into a data structure for reference. You don't want to change the data, you just need to access it. NSArray will do the trick.

Let's take a look at the code...

Walking Through the Lottery Code.

Though this source code is quite short, it touches on a number of important concepts. You've already learned a bit about the NSMutableArray. Be sure to read the NSMutableArray doc and look ever the set of methods available to create and modify them.

The source code starts off in typical fashion, with the #import of the Foundation.h header file and the definition of main().

#import <Foundation/Foundation.h>

int main (int argc, const char * argv[])
{

Next up are declarations of an NSMutableArray object pointer, a counter, and a pair of NSNumber pointers.

   NSMutableArray *array;
   int i;
   NSNumber *newNumber;
   NSNumber *numberToPrint;

Any idea what an NSAutoReleasePool does? Option-double-click on the class name and Xcode will bring up a doc window that describes the class. Note the link to Memory Management toward the middle of the page. Clicking on this link will bring up an intro to memory management as well as an index to a terrific series of articles on Objective C memory management. Take some time to read the intro and, at the very least, scan the other articles to get a sense of the available information. To truly master Cocoa, you must understand Cocoa's unusual memory management techniques.

Here's the short version. Every object has a retain count. When an object is created, its retain count is set to 1. If the retain count goes to 0, the object is deallocated. When a chunk of code wants an object to stick around, it sends the object a retain message. This increases the retain count by 1. When the chunk of code is done with the object, it sends the object a release message. This decrements the retain count by 1. This scheme is well worth understanding and enables many objects to share a common object. When the last object is done using the shared object, the last release message is sent to the shared object and it is deallocated.

The NSAutoReleasePool helps solve a knotty problem common to many frameworks. It is easy to allocate an object at the beginning of a function, then release it at the end of the function. The same object allocs the object and deallocs the object, making it easy to manage. But what if you write a function that creates an object then returns that object to another method? Who deallocates the object?

Java solves this problem by automated garbage collection. Cocoa uses the NSAutoReleasePool. When you send an autorelease message to an object, it is added to the autorelease pool. When the pool is deallocated, it sends a release message to all objects in the pool.

We'll talk more about NSAutoreleasePool in future columns. For now, just know that it exists.

   NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

The real key to this column is the NSMutableArray named array. We start by creating array, sending it the alloc message and then the init message. As we've discussed, sending a message to an object is similar to calling an object's method, but without the binding. The actual method called to process the alloc method for the NSMutableArray array is not decided until runtime.

Also worth noting is that messages can be nested. This code sends the alloc message first, then sends the init message. This is a typical way of creating an object.

   array = [[NSMutableArray alloc] init];

Remember, an NSMutableArray is an array of pointers to objects. So if we want to store objects in the array, we need to create them first. Here's a loop that creates a series of 10 NSNumber objects. For each one, we send the message initWithInt: instead of just plain init: when we create the object.

Once the object is created, we add the object to array by sending it the addObject: message. Hmmm. When we add the object to the array, the array no doubt sends a retain message increasing the retain count for each NSNumber to 2. And when we release the array down below, the objects in the array are sent a release message, giving each NSNumber a retain count of 1. But the retain count never gets to 0. Hmmm.

   for ( i=0; i<10;i++) {
      newNumber = [[NSNumber alloc] initWithInt:(i*3)];
      [array addObject:newNumber];
   }

What we should have done was add this line of code to the bottom of the for loop, just below the addObject message. Once the NSNumber is added to the array, its retain count is bumped to 2. The release would drop it back down to 1. Then, when array is released and all its NSNumber objects are sent their own release messages, they will be deallocated. See how this works?

      [newNumber release];

Next, we step through the array, using NSLog() to print each of the objects in the array. NSLog() behaves much like printf(), using format descriptors embedded in the string to print the objects that follow the string. While %d should be familiar to you C programmers, %@ is a new beast. Basically, it tells NSLog() to send a description message to the object and the object returns a string describing itself. In this case, NSNumber sends a string consisting of its number.

   for ( i=0; i<10; i++ ) {
      numberToPrint = [array objectAtIndex:i];
      NSLog( @"The number at index %d is %@", i,
            numberToPrint );
   }

Finally, we release the array and then the autorelease pool.

   [array release];
   [pool release];
   return 0;
}

Till Next Month...

Cocoa is an incredibly rich, incredibly powerful framework. There are some things that take getting used to but, once you do, I think you'll find your coding time to be much more productive. I strongly recommend spending some time curled up with your favorite Cocoa book. Then go write some code.

Be sure to check out http://spiderworks.com and I'll see you next month...


Dave Mark is a long-time Mac developer and author and has written a number of books on Macintosh development, including Learn C on the Macintosh, Learn C++ on the Macintosh, and The Macintosh Programming Primer series. Dave's been busy lately cooking up his next concoction. Want a peek? http://www.spiderworks.com.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.1.1 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
CrossOver 14.1.3 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
Little Snitch 3.5.3 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
OmniGraffle Pro 6.2.3 - Create diagrams,...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
OmniFocus 2.2 - GTD task manager with iO...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more
Cocktail 8.4 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
PDFKey Pro 4.3 - Edit and print password...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Kodi 15.0.beta1 - Powerful media center...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more

Moleskine Timepage – Calendar for iCloud...
Moleskine Timepage – Calendar for iCloud, Google & Exchange 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: The most elegant calendar for your pocket and wrist, Timepage is a... | Read more »
QuizUp Gets Social in its New Update
Plain Vanilla Corp has released a new and improved version of their popular trivia game, QuizUp. The app now emphasizes social play so you can challenge friends from all over the world. [Read more] | Read more »
The Deep (Games)
The Deep 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Swipe Controls Delve into the deep in this retro rogue-like! Swipe to move your diver around and keep away from the enemies as you... | Read more »
Battle of Gods: Ascension (Games)
Battle of Gods: Ascension 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: TURN-BASED TACTICAL COMBATFight tactical battles against the forces of Hades! In Battle of Gods: Ascension you play... | Read more »
Shadowmatic's Latest Update Adds a...
Shadowmatic's shadowy shadow-ness is getting a little shadowy-er thanks to a recent update that adds an Arcade Mode. [Read more] | Read more »
Sunrise Calendar and Slack Have Assimila...
Wunderlist is perhaps one of the most populat and beloved productivity apps on the App Store - and now it's gone and incorporated itself into other useful services like Sunrise Calendar and Slack. [Read more] | Read more »
Crossy Road Devs Hipster Whale are Bring...
Hipster Whale, the minds behind the rather popular (and rather great) Crossy Road, have teamed-up with Bandai Namco to create PAC-MAN 256: an absolutely bonkers looking maze runner chaser thing. | Read more »
Meet the New Spotify Music
Spotify Music  has a lot going on. They're introducing 3 new modes to serve all your musical needs, with the "Now" start page  gives you curated playlists based on your particular tastes. As you listen the app will learn more about your tastes and... | Read more »
What the Apple Watch Gets Right, and Wha...
| Read more »
Celebrate PAC-MAN's 35th Birthday W...
BANDAI NAMCO Entertainment America is celebrating PAC-MAN's 35th anniversary by releasing updates for PAC-MAN and PAC-MAN Lite for iOS. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
What Would the ideal Apple Productivity Platf...
For the past four years I’ve kept a foot in both the Mac and iPad camps respectively. my daily computing hours divided about 50/50 between the two devices with remarkable consistency. However, there’... Read more
PageMeUp 1.2.1 Ten Dollar Page Layout Applica...
Paris, France-based Softobe, an OS X software development company, has announced that their PageMeUp v. 1.2.1, is available on the Mac App Store for $9.99. The license can be installed on up to 5... Read more
Eight New Products For USB Type-C Application...
Fresco Logic, specialists in advanced connectivity technologies and ICs, has introduced two new product families targeting the Type-C connector recently introduced across a number of consumer... Read more
Scripps National Spelling Bee Launches Buzzwo...
Scripps National Spelling Bee fans can monitor the action at the 2015 Spelling Bee with the new Buzzworthy app for iOS, Android and Windows mobile devices. The free Buzzworthy app provides friendly... Read more
13-inch 2.5GHz MacBook Pro on sale for $120 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $979 including free shipping plus NY sales tax only. Their price is $120 off MSRP, and it’s the lowest price for this model (except for Apple’... Read more
27-inch 3.3GHz 5K iMac on sale for $1899, $10...
B&H Photo has the new 27″ 3.3GHz 5K iMac on sale for $1899.99 including free shipping plus NY tax only. Their price is $100 off MSRP. Read more
Save up to $50 on iPad Air 2, NY tax only, fr...
B&H Photo has iPad Air 2s on sale for up to $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469 $30 off - 64GB iPad Air 2 WiFi: $549.99 $50 off - 128GB iPad... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
New 13-inch 2.9GHz Retina MacBook Pro on sale...
B&H Photo has the 13″ 2.9GHz/512GB Retina MacBook Pro on sale for $1699.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price for this model from... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Watch SW Application Project Manager...
**Job Summary** The Apple Watch software team is looking for an Application Engineering Project Manager to work on new projects for Apple . The successful candidate Read more
Engineering Manager for *Apple* Maps on the...
…the Maps App Team get to take part in just about any new feature in Apple Maps, often contributing a majority of the feature work. In our day-to-day engineering work, we Read more
Senior Software Engineer - *Apple* SIM - Ap...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Lead *Apple* Solutions Consultant - Retail...
**Job Summary** Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.