ActionScript 3.0 Design Patterns

This post culminates what has amounted to a marathon of posts about skip lists. This whole project started because Timo had mentioned that one of the design patterns would benefit from the inclusion of skip lists, but he never said how or how to create them. Since I’d never head of skip lists I dug up William Pugh’s original article on them and took a look. Like binary searches, skip lists are elegantly simple but can be interesting to create in ActionScript 3.0 or any other language.

The History of the Skip List Saga on Our Blog

If you just happened upon this post, you may want to check out the posts that led up to this one.

1. A Funny Thing Happened on the way to Skip Lists: The ActionScript 3.0 Binary Algorithm. Here I discovered that simple elegance can be easy to understand but difficult to implement. Our readers provide solutions in the Comments.
2. ActionScript 3.0 Linked Lists: The Road to Skip Lists. To understand skip lists, you need to understand linked lists; so we had to discuss them.
3. ActionScript 3.0 Recursive Binary Search: The Vice! This post reflects the need to examine something other than iterative binary search implementations. So we look at an ActionScript 3.0 program that uses recursion for a binary search.
4. ActionScript 3.0 Skip Lists: The Quickest Route Home. This post begins with an analogy of taking different train lines and then shows how the same logic can be applied to skip lists.

While you don’t have to read all four articles, I’d strongly suggest that you read about the linked lists (2) if you’re not familiar with them and the logic behind skip list searches (4) for an introduction to the logic of skip lists.

The Perfect Skip List

I ran across the perfect skip list in a presentation by Eileen Kraemer a computer science professor at the University of Georgia. (You can find several academic papers on the perfect skip list if you do a Web search: key = perfect skip list.) In the most simple terms, the perfect skip list is one where each level has exactly double the nodes as the one above it. In a sense, it is arranged like a binary search. The head node (far left) has a value of minus infinity (Number.NEGATIVE_INFINITY) and the node on the far right has a value of infinity, (Number.POSITIVE_INFINITY). (I’m calling the far right node the tail node for the sake of symmetry.) By having the highest and lowest possible values bracketing the search values, it contains the search parameters so that you can enter any values you want in the skip list. Figure 1 shows the perfect skip list without values except for the tail node with a value of infinity.

Figure 1: Perfect skip list

That looks a lot like the train lines we used in the previous post on skip lists, and if it helps to visualize the skip list as trains to see what’s going on, you can think of them as such. Figure 1 also may remind you of a binary search pattern, and that’s because perfect skip lists and binary searches have a lot in common. All that’s left to do is to program it—click below to continue:

Read more…

Living in Bloomfield, Connecticut, I’m about halfway between Boston and New York City. Lately they’ve been talking about building a high speed rail to Hartford and on to Springfield, Massachusetts. Naturally, when thinking about such a rail system, I like to think that the really fast part of the trip would be between New York City, Hartford, and Boston. Of course they’d need an express to stop off in New Haven and Springfield. Further, lots of other towns, including Bloomfield, would need some kind of local line. Left to my own devices, I would build the following lines:

Bullet

1. New York
2. Hartford
3. Boston

Express

1. New York
2. New Haven
3. Hartford
4. Springfield
5. Boston

Local

1. New York
2. Stamford
3. New Haven
4. Middletown
5. Hartford
6. Bloomfield
7. Springfield
8. Boston

Given these choices, I know that I can easily get to Bloomfield by taking the Local at Grand Central Terminal in New York City. However, I’d really like to skip stops in Stamford, New Haven and Middletown. If I took the express, I’d have a stop in New Haven and then on to Hartford where I could get on the Local to Bloomfield. That would be faster, but it would not be the fastest route.

To determine the fastest route, assuming that I have to go in the same direction and cannot backtrack, I diagramed the three lines in Figure 1.

Figure 1: Three Lines between New York and Boston

Looking at Figure 1, it is not too difficult to determine the quickest route between NYC and Bloomfield.

The route that skips the most stops is the quickest route.

Trace your finger from NYC to Bloomfield in Figure 1 and you can determine that route. To see if you found it, click below to continue and look at Figure 2 to see the fastest route highlighted in yellow.
Read more…