ActionScript 3.0 Design Patterns

Lazy Initialization

Just be careful not to call factory methods in the Creator’s constructor—the factory method in the ConcreteCreator won’t be available yet. (page 112)

The comment was directed at some issues in C++ which may or may not have any bearing on ActionScript 3.0, but just in case it did, I continued reading. The point being made was you can avoid these problems by accessing products only through accessor operations that create products on demand. So what are accessor operations? Generally these are public methods that you can call to initiate creation of a product.

Time Out! Before we get too far ahead of ourselves, you can download all of the .as files for the Factory Method example by clicking the following button:

The example is a simple one that creates three different shapes—ellipse, rectangle and triangle. Figure 1 shows how the Client arranged them to display a house in front a a pond with a cloud overhead:

Figure 1:Triangle, Ellipse and Rectangle Products

The program uses concrete creators to fetch shapes. The Client makes requests that size, color, and position the shapes.

Don’t Enslave Your Constructor Functions

This issue of the constructor functions reminded me of a post by Miško Hevery, the guy at Google who helps set Google’s programming standards. One of the key flaws in a program is where the constructor does real work. Besides violating the single responsibility rule, Miško goes on to explain the tell-tale signs that one has used his constructor function with outrageous disregard for both agile programming and loose coupling. As a result of reading Hevery’s work, a year or so ago, I began to seriously gear back on using a class’ constructor function; primarily by not including one in most of my classes. (My Client class is a glaring exception to the rule.) I’d usually have just the properties and operations (methods, functions) that I needed. The properties would initialize themselves—sort of. They’d be given an ID and then typed and that was all. The child classes could then use them in operations. Whenever I needed something, the Client would type a request to the interface (including abstract classes) and then make a request through concrete method in an operation. With the Factory Method, I make requests to the ConcreteCreator through the abstract Creator class.

In returning to GoF, they point out,

Instead of creating the concrete product in the constructor, the constructor merely initializes it to 0. (Page 112)

In this discussion, they note that Factory methods in C++ are always virtual functions. WTF?! (What’s That Function?!) Simply stated, any function that can be overridden in the child classes is a virtual one. Well, we can do that in ActionScript 3.0. In fact, that’s what we do in creating Abstract classes. (Why we can override and yet not have real Abstract classes is still a mystery to me.)

Read more…

Repeated operations are handled either by recursion or loops (iteration). One of the fundamental structures of programming is loops, and we programmers tend to think, If I need to repeat an operation, I use a loop. Loops are built-in structures of most languages, and ActionScript 3.0 has multiple options when it comes to loops. ActionScript 3.0 has the standard for (and variations), while, and do statements as well as looping methods for arrays and vectors. So if we need to repeat a set of operations, we have several iterative statements that will get the job done for us.

Why Bother With Recursion?

In most (but certainly not all) situations, iteration is faster than recursion, and so why should we even consider recursion? Recursion is nothing more than a method that can call itself that uses more memory than iteration and fills up the stack quickly. You’ll get a stack overflow with recursion both with big numbers and with infinite loops. Loops can handle big numbers better, and while they eventually blow a gasket with an infinite loop, they take longer to do so because iterations are not stored on the stack.

Despite what some programmers would see as the end of the conversation comparing iteration with recursion, I was able to find two good reasons to consider recursion over iteration.

1. The code can be clearer and simpler
2. Recursion offers more elegant solutions

With the caveat that the following is not a call to abandon loops, let’s take a look at the reasons you should consider recursion the next time you come across a task that requires repeating operations.

Clear and Simple

Sometimes we come to a problem where we want to lay out all of the options to better see what’s going on. With loops, especially with complex ones that involve nesting, we can quickly find ourselves spinning our wheels. On the other hand with recursion, we can lay out the steps in a series of statements that clearly show the options we have to consider.

For example in the previous post on this blog examining the construction and use of skip lists, the search algorithm uses recursion. In the stripped down version of the search method, we can clearly see the repeated steps taken in the search routine:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public function searchList(searchKey:uint,layNum:int):int
		{
			this.searchKey=searchKey;
 
			if (initial)
			{
				layNum=4;
				searchNode=headNode;
				initial=false;
			}
 
			if (searchNode.contents==searchKey)
			{
				trace("success");
				return searchNode.contents;
			}
\
			if (layNum<0)
			{
				trace("Number not found");
				return -1;
			}
 
			if (searchNode["skip"+layNum].contents< =searchKey)
			{
				searchNode=searchNode["skip"+layNum];
			}
 
			else
			{
				layNum--;
			}
			return searchList(this.searchKey,layNum);
		}

The steps are clear to see how the search works its way through the skip list to find whether a given value were included:

1. If it’s the first time through, begin at the top level in the head node.
2. If the search key matches the node contents end the search and return the found contents.
3. If the layer is below 0; end the search and inform the user that the value was not found.
4. If the next node is greater than or equal to the search key, the search node becomes the next node
5. If the next node is less than the search key, move down a layer
6. Run function again if nothing is returned

Read more…

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…

The Recursive Vice

After our post on the binary search algorithm, I found that no one had cooked up an example of a Recursive Binary Search. So, I did. In a recent post, we looked at linked lists and used a recursive algorithm to move through the list. The algorithm is simple, and I hope explains both binary search and how to use recursion with such a search. As with the other posts in this recent series, we’re working our way to skip lists, and I hope this will aid in understanding how skip lists work.

Divide and Conquer

The binary search algorithm uses a divide and conquer approach that works like a vice. With each division in half, the bottom range gets higher and the top range gets lower and the search object is either squeezed out or not found. This saves a lot of poking around an array (or other list) to find what you’re looking for.

When using recursion, the function containing the search algorithm keeps calling itself until a match occurs or it runs out of places to look. In order to provide a visual representation of what’s going on, I used trace statements with each call to a recursive function. As you will see, with each recursive call, the search function displays the call and the values. The first parameter is the search value (44 in this case) and the second two parameters represent the beginning and ending values of the search fields. When you run the program, you will see something like the following:

recursive call to: recursiveBinarySearch(44,0,49);
recursive call to: recursiveBinarySearch(44,25,49);
recursive call to: recursiveBinarySearch(44,38,49);
recursive call to: recursiveBinarySearch(44,38,42);
recursive call to: recursiveBinarySearch(44,41,42);
recursive call to: recursiveBinarySearch(44,42,42);
Your number is at position 42

The beginning search of 100 elements is 49 for the top and 0 for the bottom. It then moves up through the numeric elements of the array until it finally squeezes out the found item in array element 42. (The array is randomly populated from 1 to 100 and then sorted—binary searches require sorted lists.)

Normally in these posts I don’t use a lot of comments in the code because the text in the post is supposed to explain everything. (Also, comments often get in the way of the flow of the programming logic and good agile programming shouldn’t need comments.) However, for this algorithm, I found that it probably helps to see each step in detail so I put in quite a few comments.

I also put the algorithm in a class. Because,

…an algorithm without a class is like a child without a mother…

That reminds me, Happy Mothers Day to all of you mothers out there.

(I suppose a corollary would be,

…a class without a design pattern is like a child without a father…

but I’d never say that because people might get the wrong idea about the latter piece of wisdom.)

Okay, so let’s take a look at the class containing the algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

package
{
	import flash.display.Sprite;
 
	public class Binary extends Sprite
	{
		private var searchArray:Array=new Array();
		private var sizeNow:int;
		private var mid:int;
		private var poke:int;
		private var begin:int;
		private var end:int;
		private var flagUp:Boolean=true;
 
		public function Binary()
		{
			for (var stuff:int=0; stuff<100; stuff++)
			{
				searchArray.push(int(Math.random()*100));
			}
			searchArray.sort();
			sizeNow=searchArray.length;
		}
 
		public function recursiveBinarySearch(valueN:int,begin:int,end:int):int
		{
			/*Only on the first time through use the array
			length as the end value. The Algorithm keeps
			changing the end value so you don't want to use
			the array length more than once.    */
			if (flagUp)
			{
				end=sizeNow;
				flagUp=false;
			}
 
			/*If the end value is smaller than the begin value
			the search is over and item was not found.    */
			if (end<begin)
			{
				return -1;
			}
 
			/*Find the midway point between begin and end
			and use it as the numeric key for the current search
			value—guess (poke).     */
			mid=int((begin + end)/2);
			poke=searchArray[mid];
 
			/*If a match occurs return
			the value of the numeric key.  Search ends here.  */
			if (poke==valueN)
			{
				return mid;
			}
 
			/*If no match; guess larger than value; the end value
			becomes the midway value minus 1. Otherwise, the begin
			value becomes the midway value plus 1.     */
			else
			{
				if (poke>valueN)
				{
					end=mid-1;
				}
				else
				{
					if (poke<valueN)
					{
						begin=mid+1;
					}
				}
			}
 
			/* Keep making the recursive call until value is found
			or all possible values are searched */
			trace("recursive call to: recursiveBinarySearch("+valueN+","+begin+","+end+");");
			return recursiveBinarySearch(valueN,begin,end);
		}
	}
}

Like I said, there are a lot of comments there so that you can see the steps through the algorithm. Now, a second class acts like a client and calls the method in the Binary class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package
{
	import flash.display.Sprite;
	public class Searcher extends Sprite
	{
		private var searching:Binary=new Binary();
		private var searchElement:Number;
		private var searchNow:Number;
 
		public function Searcher()
		{
			searchNow=searching.recursiveBinarySearch(44,0,0);
			if (searchNow>=0 && searchNow != 4294967295)
			{
				trace("Your number is at position " + searchNow );
			}
			else
			{
				trace("Not found");
			}
		}
	}
}

Keep in mind that all of the searches are searching the numeric element keys of the array—not the values. Therefore, you shouldn’t expect the found value to be the same as the numeric key value. Also, since the values are generated randomly, the value you place in the first parameter of the line:

searchNow=searching.recursiveBinarySearch(44,0,0);

may not be found at all. I put in 44 for the search value, but you can add any value you want between 1 and 100. Alternatively, you can fix it up so that you can dynamically enter different values or even change it to make it look for string values. However, the point is simply to demonstrate how to create and use a recursive binary search.

As always, your comments, corrections and wisdom are always welcomed.

Recursive Linked List

To understand Skip Lists we need to understand Linked Lists. Linked lists are nothing new to programming, dating back to the early days of digital computing in the 1950′s. I found an old Macromedia DevNet article by Branden Hall on creating linked lists in an earlier version of ActionScript. So while nothing new to programming, they are often overlooked.

Why Linked Lists?

Before we look closely at linked lists, we should briefly discuss their utility. After all, we’ve got Arrays (and Vectors) for storing data. Further, arrays are easy to sort, and ActionScript 3.0 structures are available to iterate through them.

One problem with arrays is that it’s difficult to insert elements between existing elements. Using linked lists, you can put the data in any order at all, including between existing nodes (elements). The linkage is not the order of the array because arrays have no linkage between elements.

In its most basic form, a linked list is a series of nodes with each node having a value and a reference to the next node. The value can be anything and the link must be to the next node using whatever sequence the programmer wants. Some linked lists have references to the previous and next node and some are even circular—the last node links to the first node. However, I’m going to stick with the singly-linked linear lists. First it is a recursive data structure, and second it is useful for what we’ll be doing with skip lists. Figure 1 shows this kind of list with its various parts:

Figure 1: Linked list and its components

In looking at the linked list, the most important aspect of such a list is the Next Field. The Next Field is a pointer to the linked node—the next node. Remember, a pointer is simply a reference to another object. With linked lists, that makes all the different in the world. Array elements are linked to nothing. (Numeric or string keys are not pointers so much as they are labels.)

Before going on to create an example of a linked list in ActionScript 3.0, we need to consider node insertion. As noted above, inserting an element in an array can be tricky. However, you may be wondering about how easy it is to insert a node between existing nodes. Wouldn’t the pointer from the node before the new node have to be changed? That is, if Node 5a is inserted between Nodes 5 and 6, wouldn’t we have to change the pointer in Node 5 to Node 5a? Yes. Node 5′s pointer would have to be changed from Node 6 to Node 5a. Node 5a would point to Node 6.

An ActionScript 3.0 Linked List

Without further ado, let’s whip up a linked list in ActionScirpt 3.0. The contents of the list (placed in the data field) can be anything, but I decided to use strings sequentially listing the first six letters of the Greek alphabet. (It rhymes with “Geek,” and I couldn’t resist.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package
{
	import flash.display.Sprite;
 
	public class LinkedList extends Sprite
	{
		private var alphaNode:Object=new Object();
		private var betaNode:Object=new Object();
		private var gammaNode:Object=new Object();
		private var deltaNode:Object=new Object();
		private var epsilonNode:Object=new Object();
		private var zetaNode:Object=new Object();
		private var nullNode:Object=new Object();
		private var recursiveNode:Object=new Object();
 
		public function LinkedList()
		{
			alphaNode.contents="alpha";
			betaNode.contents="beta";
			gammaNode.contents="gamma";
			deltaNode.contents="delta";
			epsilonNode.contents="epsilon";
			zetaNode.contents="zeta";
 
			alphaNode.nextUp=betaNode;
			betaNode.nextUp=gammaNode;
			gammaNode.nextUp=deltaNode;
			deltaNode.nextUp=epsilonNode;
			epsilonNode.nextUp=zetaNode;
			zetaNode.nextUp=nullNode;
 
			recursiveNode=alphaNode;
 
			while (recursiveNode != nullNode)
			{
				trace(recursiveNode.contents);
				recursiveNode=recursiveNode.nextUp;
			}
		}
	}
}

Your output will be:
alpha
beta
gamma
delta
epsilon
zeta

At first glance, it looks like we just iterated through a loop, and indeed we did. However, instead of using an iterative sequence, we used the linked list pointers to go from one node to the next. Each of the nodes was recursively linked to the next node. The sequence began with the Head Node, with an object (recursiveNode) referencing itself through the entire list using the nextUp property to traverse the list. (The loop just served as an engine.) Further, you can see that our output is not ordered alphabetically—at least in non-Greek.

Reader Challenge: Ordering the Linked List

The first task is to figure out where the output is unordered as far as ActionScirpt 3.0 is concerned. The next task to to change the pointers so that the output is ordered. Use the Comment section to show your solution. If you can do that, you will be better prepared to understand how linked lists are used in skip lists in an upcoming post.

If you are interested in linked lists, check out this Stanford University lecture on the topic. It served as a useful guide in preparing this post and has everything you’ll ever want to know about linked lists.

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.)

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.