A Funny Thing Happened on the way to Skip Lists: The ActionScript 3.0 Binary Search Algorithm

binarySearch A while back a comment by Timo Hannelin suggested that I use a skip list in one of the design patterns. (I looked but couldn’t find the comment, but I remember it was a good idea.) Anyway, I read the original article on skip lists by William Pugh. After reading the article and a few more articles on skip lists, I saw Timo’s point. However, since I’ve got my hands full with design patterns, and I dislike design pattern discussions degenerating into a chat about algorithms, I didn’t bring it up.

Algorithms in Participants

Having a little time right now, I thought I’d return to skip lists and see where they’d be valuable for participants in one of the design patterns. So, to warm up for working with skip lists I thought I’d whip up a Binary Search algorithm in ActionScript 3.0. Further, I wanted to entertain myself, and so I decided not to peek at any solutions on the Web.

After a few hours of trying to strong arm a solution I gave up and decided to peek. This is what I found:

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… — Professor Donald Knuth (Professor emeritus, Stanford University)

Further, I learned that only five out of twenty textbooks had accurate code for a binary search! Well, at least I didn’t feel like an idiot, but still, the concept is pretty simple, and it’s easy to do in your head. It’s just difficult (or tricky) to whip one up in code.

The Binary Search

The concept behind the binary search is to search by dividing an ordered list in consecutive halves. If the search guess is higher (in the ordered list) than the one being searched for, the bottom of a range is the search guess. If the search guess is lower; then the top of the range is the search guess. Each consecutive search is the halfway point between the top and bottom of the range. The solution is found by closing in like a vice taking chunks in halves rather than iterating through an entire list. It’s very fast and efficient for searches.

To get started, I created a function to generate a quick and dirty ordered array with 100 random numbers. (The variables were declared elsewhere in the class.)

?View Code ACTIONSCRIPT
1
2
3
4
5
6
7
8
9
10
11
12
13
private function generate():Array
{
	//Generates 100 numbers 
	//Places them in a sorted array
	while (pack < 100)
	{
		ranInt=Math.random()*100;
		arrayPack.push(ranInt);
		pack++;
	}
	arrayPack.sort();
	return arrayPack;
}

Then I started writing the algorithm for the binary search. After locking up my computer with infinite loops a couple of times and rerouting the power grid of Bloomfield, Connecticut to Timbuktu, I gave up. Using numbers, I kept mixing up array numeric keys with the search values.

Your Turn to Have Some Fun

Anyway, since a lot of our readers like algorithms, I thought this might be a fun one for you to solve. You can find a lot of discussions of the binary search concept online as well as solutions (in the form of code and generic algorithms). However, see what you can come up with before you give up and peek (like I did). I can tell you this, though. One general solution uses recursive coding and the other uses iterative. Remember, though—only about a quarter of the computer science textbooks had it right. So, give it a go on your own knowing that if you come up with a solution, you’re smarter than 75% of the CS textbooks! We’ll use the Comments Section of this post for your solutions and look at skip lists in a future post.

ActionScript 3.0 Developers Caught in the Middle

The Pincers

The Pincers

Why Me?

When two companies that are intertwined with my fate get into a spat, I get itchy. Because we are all linked to ActionScript 3.0 in one way or another, and Adobe is linked to ActionScript 3.0 through Flex and Flash this sad state of affairs may have consequences for us all. However, those of us who do our primary development using Apple computers (Macs), our fates are doubly impacted.

Until now, I’ve always considered ActionScript 3.0 to be a friend of the world. A large proportion of Apple’s success can be traced to the applications produced by Adobe, and yet this current parting of the ways seems to be more than a hiccup in a long symbiotic relationship between these two high technology giants.

Many of this group were primed to begin writing applications for the iPhone and iPad (and some may have), but now that seems out of the question. In a strongly worded broadside against Adobe, Steven Jobs, Apple’s Boss. Now, look what we’ve got…

With Ate by his side come hot from hell,
Shall in these confines with a monarch’s voice
Cry ‘Havoc,’ and let slip the dogs of war;
That this foul deed shall smell above the earth
With carrion men, groaning for burial.

So Adobe responded to Jobs rant.

Anyway, here are my comments, and we’d like to hear from you as well:

1. He rightfully acknowledges that Apple was one of Adobe’s initial customers. However, Apple needed Adobe’s fonts as well as the PostScript language that made their initial laser printer more than really good dot-matrix printer.

2. Also, while Jobs is probably correct in noting that about half of Adobe’s products are purchased by Apple owners; most of the Apple upgrades we purchase are because of the improvements Adobe makes in its CS5 suite. I’d still have my old iMac GooseNeck were it not for the fact that Adobe’s new products required new Apple hardware.

3. In looking at the apps in my Dock, the ones I use the most are by Adobe. Were it not for iTunes, I would not use Apple software (aside from the OS) all that often. The second most-used is Microsoft Office. It’s down the line when I find Apple software not related to iTunes that I find using a good deal. QT is sometimes used, but rarely anymore because Adobe Media Player is more responsive.

4. Several software developers have argued that, “It’s just not worth it to create Macintosh versions.” Adobe was always there for Apple when a lot of other software developers threw in with PCs only.

Being a fan of both camps, I truly hope that Apple and Adobe find a common ground. Even the Mafia knows it’s more profitable to cooperate than bicker.

What do you all think?

Design Patterns with Missing Pieces

Why are Participants Missing? Note: Gentle reader, This article was written for our new PHP Design Pattern blog, but the points apply as well to ActionScript 3.0. As a result, I decided to include it here. The links in this post have been changed to go to the relevant ActionScript 3.0 posts, but otherwise, the article is the same. After writing design patterns in PHP for a while, I’ve come to appreciate the strongly typed structure of ActionScript 3.0. Programming to the interface in PHP is tricky, but possible. However, when you have strong typing as ActionScript 3.0 does, you really appreciate it more once you’ve worked with a dynamic language without strong data typing.

The Case of the Missing Participants

Recently I was working on a Decorator pattern and struggling through PHP’s way of doing things. So naturally I thought why not take a look at how others have solved these same problems. The Gang of Four refer to the different classes and interfaces that make up a design pattern, as participants, and when I look at a design pattern, the first thing I do is to see how the developer handles the different participants. What I found was surprising—they left out chunks of a design pattern in their examples. Alternatively, they just did some kind of workaround that effectively made it work (run), but it was no longer a design pattern or had the advantages of a design pattern.

The Strategy with the Missing Context

The Strategy pattern decouples the algorithms from the Client by using a Context class. All of the requests for the algorithms (found in concrete Strategy classes) go through the Context to the Strategy interface and on the the implemented strategies in the form of concrete classes. However, in many of the PHP examples, they leave out the Context class and Strategy interface and go directly from an Object to concrete Strategies. In several examples, the code authors chose to ignore the interfaces and even the abstract classes and have fairly direct connections between concrete strategies and some kind of object. Figure 1 shows the kinds of UMLs that accompany these kinds of PHP design pattern implementations—if indeed they are implementations.

Figure 1: Minimalist UML

You can see clearly that the UML in Figure 1 has little in common with the class diagram we used that was an exact replica of the Strategy pattern that the Gang of Four uses.

The authors of this kind of “explanation” of the Strategy pattern seem to think that the separation of the algorithms from the object is a matter of nothing more than taking the algorithms out of some object and using them independently of the main object. However, while that is an improvement on cramming everything into a single object (class), it is not a design pattern. Yes, it does add flexibility because more than one class can use the same concrete strategies. So, it’s a step away from single-class programming and even procedural programming. However, it is not a design pattern and it does not have the design pattern’s flexibility. The Context class uncouples the request from the strategy and without it, that concrete strategies are tightly linked to the “object”—whatever that may be.
Continue reading ‘Design Patterns with Missing Pieces’

How to Pick the Right Design Pattern: Fortune Favors the Prepared Mind

Deciding on a Design Pattern

Deciding on a Design Pattern

Which Design Pattern Should I Use?
One of the most difficult questions to answer is also the most often asked: How do you know what design pattern to use? My standard response to that query is,
Ask, “What varies?”

Of course, it seems that everything varies just when you need a nice clear answer to that question. The Gang of Four provides a list of design patterns and what varies in each pattern—such as states of an object, an algorithm, responsibilities of an object without subclassing and so on. However, determining the nature of the variation can be as difficult as deciding the design pattern to use as looking at class diagrams. (Download the AIR version of the Variation Table—also known as The Magic Table.)

Go To The Original Source

Chapter 1 in the Gang of Four’s book is the gateway to design pattern knowledge. I must have re-read it 50 times. Further, every time I re-read it, I get something new. You can download Chapter 1 of Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides—just click the download button to bring up the PDF file and then save it:
kilroy

Find the section, How to Select a Design Pattern and read it. Even if you don’t get it all the first time through, you’ll have a better idea of design pattern selection. Now you’re all set to continue with the rest of this post. Read on!
Continue reading ‘How to Pick the Right Design Pattern: Fortune Favors the Prepared Mind’

The ActionScript 3.0 Design Pattern Thrill Ride: Part II—Catalyst

Thrill I’ve been working on a project with Adobe Catalyst, and if I didn’t do something for a Design Pattern tour now, it would be put off until I don’t know when. So I put together a non-design pattern application incorporating video and code snippets from the Aid Game. I simply have not had time (given the work I’m doing with Catalyst) to put together a more generic design pattern “thrill ride” that I planned; so while I’m working with Catalyst, I thought I’d might as well do something with design patterns and came up with this more mild tour instead of my planned thrill ride. Figure 1 shows what it looks like:

<em><strong>Figure 1: </strong>Tour through State Design Pattern</em>

Figure 1: Tour through State Design Pattern

As you can see it’s pretty simple—sort of a PowerPoint chat. (Nowhere near as flexible as the one created with the Memento pattern.) So, if you’re interested in a mild tour, click the Play button and hop on:
play

By the way, the Catalyst project has made me far more aware of Flash Builder/Flex code. It uses Flex in its engine. If you’re interested in Catalyst, you can download the Beta at Adobe Labs. I tried importing programs (SWF files) made with design patterns, and it works great. About the only thing I didn’t do with this tour is to put the videos on Flash Media Server—sorry. I was in a hurry and wasn’t sure how to link up FMS to Catalyst. I could have written the code in Flash/Flex and created an SWF file to import into Catalyst, and that works fine, but I’m pretty pressed for time on this project.

As always, your comments and valuable feedback is encouraged. I’ll be back working on this blog as soon as I’m finished with the Catalyst project. Besides, Chandima has been writing knock-out posts to keep you interested!