ActionScript 3.0 Design Patterns

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.

Figure 2: The Route that Skips the Most Stops

From Train Lines to Linked Lists

To go to the next step, you need to understand Linked Lists which we discussed in a recent post. What I’d like to do is to transform our train lines into a linked list. The first step is to change the different towns on the lines to nodes in a linked list. Figure 3 shows the first step in this transformation:

Figure 3: From Train Stops to Nodes in a Linked List

My hunch is that if I asked you what was the quickest route to find the value “30″ you’d know just what to do. However, the diagram still looks like a train dispatcher’s chart, and so we’ll update it a bit to look more like a linked list. Figure 4 shows this new diagram.

Figure 4: Linked list with multiple pointers

Figure 5: Node with multiple pointers

In code, we can imagine the first node having the following structure:

1
2
3
4

nodeOne.contents=7;
nodeOne.nextUp=nodeTwo;
nodeOne.skip1=nodeFive;
nodeOne.skip2=nodeThree;

Now we’re ready to deal with coding skip lists in ActionScript 3.0. We’ll have to work out the algorithms, and in the next post on skip lists we should be able to conclude this series with a working example of skip list searches.

Related posts:

1. ActionScript 3.0 Linked Lists: The Road to Skip Lists
2. A Funny Thing Happened on the way to Skip Lists: The ActionScript 3.0 Binary Search Algorithm