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:

Programming Skip Lists

Most of what you need to know about programming skip lists can be found in the post on Linked Lists. Basically, what I did for this example was to iterate through a series of numbers to create the nodes. Each node was given a number (data) value and a reference (pointer) to the next node. Once the base layer (level 0) had been created using loops, I laid out the others using literals in hopes of better clarity.

By using number references for both the nodes (node0 through node15) and the pointers (skip0 to skip4—a pointer set for each layer) I was able to use numeric references that could be used to decrement the layer level and loop through the 15 nodes located between the head and tail nodes.

Moving like a Knight: The Skip List Search

While working out the algorithm to search for a value in a skip list, I was reminded on the movement of the knight in a chess game. Unlike other pieces, the knight does not move in straight lines but instead moves in two different directions when it makes a move. In the same way, the search routine in a skip list is a series of moves to the right across nodes or down through levels. If the node to the right is greater than (or equal to) the current node, you move right. Otherwise, you move down a level.

As simple as that seems, it took me way too long to work out a recursive search routine to efficiently work through a perfect skip list. It’s one of those things, like a binary search. Easy once you’re finished.

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

package
{
	import flash.display.Sprite;
 
	public class MakeSkipList extends Sprite
	{
		private var headNode:Object=new Object();
		private var node1:Object=new Object();
		private var node2:Object=new Object();
		private var node3:Object=new Object();
		private var node4:Object=new Object();
		private var node5:Object=new Object();
		private var node6:Object=new Object();
		private var node7:Object=new Object();
		private var node8:Object=new Object();
		private var node9:Object=new Object();
		private var node10:Object=new Object();
		private var node11:Object=new Object();
		private var node12:Object=new Object();
		private var node13:Object=new Object();
		private var node14:Object=new Object();
		private var node15:Object=new Object();
		private var tailNode:Object=new Object();
		private var searchNode:Object=new Object();
		private var holdNode:Object=new Object();
		private var layNum:int;
		private var initial:Boolean=true;
		private var searchKey:uint;
		private var counter:uint=0;
 
		public function MakeSkipList()
		{
			setList();
		}
		private function setList():void
		{
			headNode.contents=Number.NEGATIVE_INFINITY;
			tailNode.contents=Number.POSITIVE_INFINITY;
 
			//Generate values and level0 pointers
			for (var nodeNum:uint=1; nodeNum<16; nodeNum++)
			{
				this["node"+nodeNum].contents=nodeNum*5;
				if (nodeNum<15)
				{
					this["node"+nodeNum].skip0=this["node"+(nodeNum+1)];
				}
			}
			node15.skip0=tailNode;
			//HeadNode
			headNode.skip4=tailNode;
			headNode.skip3=node8;
			headNode.skip2=node4;
			headNode.skip1=node2;
			headNode.skip0=node1;
			//Level 3
			node8.skip3=tailNode;
			//Level 2
			node4.skip2=node8;
			node8.skip2=node12;
			node12.skip2=tailNode;
			//Level 1
			node2.skip1=node4;
			node4.skip1=node6;
			node6.skip1=node8;
			node8.skip1=node10;
			node10.skip1=node12;
			node12.skip1=node14;
			node14.skip1=tailNode;
		}
 
		public function searchList(searchKey:uint,layNum:int):int
		{
			counter++;
			this.searchKey=searchKey;
 
			if (initial)
			{
				layNum=4;
				searchNode=headNode;
				initial=false;
			}
			trace("1. "+searchNode.contents);
			trace("2. Call #"+counter);
			trace("3. Search on: " + layNum);
 
			if (searchNode.contents==searchKey)
			{
				trace("success");
				return searchNode.contents;
			}
 
			if (layNum<0)
			{
				trace("Number not found");
				return -1;
			}
 
			if (searchNode["skip"+layNum].contents<=searchKey)
			{
				trace("4. "+searchNode.contents + " :less than");
				trace("---------------------------");
				trace("");
				searchNode=searchNode["skip"+layNum];
 
			}
			//Search value is greater than key
			else
			{
				trace("4. "+searchNode.contents + " :greater than");
				trace("---------------------------");
				trace("");
 
				layNum--;
			}
 
			return searchList(this.searchKey,layNum);
		}
	}
}

I probably should have worked out two separate classes; one to create the skip list and another to search through it. That would be a great reader project and shouldn’t take long. So, if you’d like, knock yourself out, and send in your solution in a comment. Also, I considered working up a Template Method pattern to either generate the skip list or do the search, but again, it is something that I didn’t have time for right now. You’re encouraged to take charge and create one and send it to us in a comment.

The Client

The Client class that requests a search for a number is, well, humble. It is static and offers yet another opportunity for you to make it better. In the meantime, the following will do the trick if you’d like to get started with skip list creation and searches:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

package
{
	import flash.display.Sprite;
 
	public class Client extends Sprite
	{
		private var skipList:MakeSkipList=new MakeSkipList();
 
		public function Client()
		{
			skipList.searchList(65,0);
		}
	}
}

On Line 11, change the first value from 65 to any number between 5 and 75 for a “find” or another number in that range (or beyond) for a “not found” outcome. The trace statements help you see what’s going on.

By looking at the Client class, you can see how easy it would be to create separate classes for skip lists and a search method. The constructor function searches using two parameters: the search value and the level. It doesn’t matter what value you put in the second parameter because it is automatically changed in the first recursive call, but it leaves the door open for larger skip lists and more flexibility. The second parameter is absolutely necessary for the dynamic calls where its value changes as the search moves down through the levels of the skip list.

As always you comments, insights and wisdom are most welcome.

Related posts:

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