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 using the PHP constant with a minus sign (-INF) and the node on the far right has a value of infinity, (INF). (I’m calling the far right node the tail node for the sake of symmetry. You’ll also see it labeled the “sentinel.”) 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 used in the previous post on skip lists, and if it helps to visualize the skip list as train lines 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. First, though, give it a quick play and download the files:
Programming Skip Lists with the SplDoublyLinkedList class
Most of what you need to know about programming linked lists can be found in the post on Linked Lists on this blog. Using the built-in PHP SplDoublyLinkedList class (PHP 5.3+), I generated five linked lists, naming them level4 to level0, reflecting those in Figure 1. The trick was in figuring out how to best iterate through the lists. Here’s the iteration process I was looking for:
- Start with level4 and check the first node to the right
- If less than move down one level; greater than move right
- Synch list nodes with levels
- Repeat until match found
Initially, I tried using the next() and prev() methods in the SplDoublyLinkedList class, but it was very difficult to synch all levels with those methods. Then I tried using the offsetGet(n) method, and it worked easily and well for both searching and synching levels.
The Skip List Product and Factory
A Factory Method design pattern serves to create the linked lists and final skip list. Figure 2 shows the class diagram in file format:
Figure 2: File Diagram of Skip List Factory Method pattern
The Client makes all requests through the factory for linked lists. The lists themselves have been configured as implemented products, and the Client puts them together as a skip list. An alternative design would have been to have a fully loaded SkipList class (an encapsulated skip list) and have the Client pass on search requests with the search methods in the SkipList class instead of the Client. Either way, the Factory Method has ensured loose binding, and so if you’d like to experiment with a separate skip list class, go ahead. (Click below to see how the different objects are implemented.)
The product participant in the design is a collection of linked lists for the different levels. Each linked list is instantiated with the required data for its level in a skip list. The ListProduct interface is a set of five methods, each representing a different level from 0 to 4. The Lists class implements the ListProduct interface. Each Lists method generates an instance of the SplDoublyLinkedList class, and sets the head and tail nodes along with the nodes in between required for the level. The following listings show the product participants:
First, as with most interfaces, all methods are simply abstract names with minimal signatures.
ListProduct.php
interface ListProduct
{
//Product Methods
function makeLevel4();
function makeLevel3();
function makeLevel2();
function makeLevel1();
function makeLevel0();
}
?>
|
The implementation of the different “products” (linked lists) has factory-like characteristics in that it is made up of different methods to create the required linked lists. However, each method is set up to return each product through a public visibility to a factory request that “builds” the product.
Lists.php
class Lists implements ListProduct
{
private $level4;
private $level3;
private $level2;
private $level1;
private $level0;
private $total=15;
public function makeLevel4()
{
$this->level4 = new SplDoublyLinkedList();
$this->level4->push(-INF);
$this->level4->push(INF);
$this->level4->rewind();
return $this->level4;
}
public function makeLevel3()
{
$this->level3 = new SplDoublyLinkedList();
$this->level3->push(-INF);
for($counter=8;$counter<= $this->total;$counter+=8)
{
$this->level3->push($counter);
}
$this->level3->push(INF);
$this->level3->rewind();
return $this->level3;
}
public function makeLevel2()
{
$this->level2 = new SplDoublyLinkedList();
$this->level2->push(-INF);
for($counter=4;$counter<= $this->total;$counter+=4)
{
$this->level2->push($counter);
}
$this->level2->push(INF);
$this->level2->rewind();
return $this->level2;
}
public function makeLevel1()
{
$this->level1 = new SplDoublyLinkedList();
$this->level1->push(-INF);
for($counter=2;$counter<= $this->total;$counter+=2)
{
$this->level1->push($counter);
}
$this->level1->push(INF);
$this->level1->rewind();
return $this->level1;
}
public function makeLevel0()
{
$this->level0 = new SplDoublyLinkedList();
$this->level0->push(-INF);
for($counter=1;$counter<= $this->total;$counter++)
{
$this->level0->push($counter);
}
$this->level0->push(INF);
$this->level0->rewind();
return $this->level0;
}
}
?>
|
The products are a series of linked lists with each level having double the number of nodes as the previous level. That defines the ingredients of a perfect skip list.
The factory elements begin with a creator interface in the form of an abstract class that includes a factory method, getLevel($levelNum), and properties for the factory and for each level.
SkipListCreator.php
abstract class SkipListCreator
{
//Factory method
abstract public function getLevel($levelNum);
//Properties
protected $factory;
protected $level0;
protected $level1;
protected $level2;
protected $level3;
protected $level4;
}
?>
|
Since the properties are made up of linked lists, all the factory has to do is to set up a way for each to be requested by a client. The switch statement returns the desired linked list to the client.
SkipListFactory.php
Class SkipListFactory extends SkipListCreator
{
public function __construct()
{
$this->factory = new Lists();
$this->level0 = $this->factory->makeLevel0();
$this->level1 = $this->factory->makeLevel1();
$this->level2 = $this->factory->makeLevel2();
$this->level3 = $this->factory->makeLevel3();
$this->level4 = $this->factory->makeLevel4();
}
public function getLevel($levelNum)
{
switch($levelNum)
{
case 0:
return $this->level0;
case 1:
return $this->level1;
case 2:
return $this->level2;
case 3:
return $this->level3;
case 4:
return $this->level4;
}
}
}
?>
|
For the most part, that’s it as far as putting a skip list together.
The Client Iterator
In this particular implementation, the Client does more than provide a search number–it also handles the search routine. In the initial discussions of the Iterator design pattern, the pattern was shown to have the possibility of more than a single type of iteration. What the Client class provides is that iteration for skip lists. So in future posts on this blog of the Iterator pattern, you can see how the original example by the Gang of Four can be implemented. For now, the Client is the portal through which a request is handled and used to search for a value in a skip list.
Client.php
error_reporting(E_ALL);
ini_set("display_errors", 1);
function __autoload($class_name)
{
include $class_name . '.php';
}
Class Client
{
private $search;
private $level=4;
private $levelNow;
private $skiplist;
private $match=false;
private $offset=1;
public function __construct()
{
$this->search = intval($_POST['searchvalue']);
$this->skiplist=new SkipListFactory();
$this->levelNow=$this->skiplist->getLevel($this->level);
while (!$this->match)
{
$this->checkMatch();
}
if($this->match)
{
echo "Found! {$this->levelNow->offsetGet($this->offset)} is in the skiplist";
}
}
//See if search node value and search value are the same
private function checkMatch()
{
if($this->levelNow->offsetGet($this->offset) == $this->search)
{
$this->match = true;
}
//If no match go adjust for greater or lesser value
elseif($this->levelNow->offsetGet($this->offset) > $this->search)
{
$this->greaterThan();
}
else
{
$this->lessThan();
}
}
//Move down a level if the node value is greater than search value
private function greaterThan()
{
$this->level--;
echo "Now at level $this->level
|
The search/iteration process works pretty much the way outlined at the beginning of this post. The iteration (while loop) first checks for a match, if no match is found it looks to see if the node value is greater than the search value. If it is, it moves down to the next level. In doing so, it must update the node to conform with the current position of the node above it. For example, in level 3, node 2 has a value of 8, but when the search moves to level 2, it must adjust the node to 4. With a perfect skip list, it’s simply a matter of multiplying the current offset by 2. It has to check to make sure that the level is not level 3 because the level 4 and level 3 have the same offset. (That can be fixed by eliminating level 4 whose node values are infinity and negative infinity.) If the node value is less than the search value, then a method increases the node value on the same level.
The HTML5 UI
The UI is simply a number wheel with values from 1 to 15 with the default value of 8 so that the user can go up or down from the middle. It is then passed to the PHP Client class for processing:
SkipList.html
|
The CSS is fairly simple, and you can use the one included or create your own.
SkipList.css
@charset "UTF-8"; /* CSS Document */ body { font-family:"Gill Sans", "Gill Sans MT", "Myriad Pro", "DejaVu Sans Condensed", Helvetica, Arial, sans-serif; background-color: #C5DB9E; color:#20383B; font-size: 18px; } iframe { background-color: #ffffbb; } h3 { font-family:Segoe, "Segoe UI", "DejaVu Sans", "Trebuchet MS", Verdana, sans-serif; background-color:#bd5351; color:#ffffbb; padding-left:1em; } |
Discussion
The skip list example used is about as simple as they get. Inserting, changing and deleting values in skip lists is a whole other topic, and if you’re interested, you can find lots of discussions online. For use with an Iterator design pattern, I seriously doubt that level 4 (or any level with only -INF and INF values in the nodes) is of much use. However, I included it in this example for the purpose of complete comparison with other examples of perfect skip lists used in developing this post.
In the next post on the Iterator pattern, we can see how two different kinds of iteration are made available for different kinds of searches in a single program design. You will find the binary and skip list searches encapsulated for re-use with different kinds of data sets.
Copyright © 2014 William Sanders. All Rights Reserved.
0 Responses to “PHP Skip Lists 2: Implementing Skip Lists in PHP”