Archive for the 'Iterator' Category

PHP Skip Lists 2: Implementing Skip Lists in PHP

GunMoll250The 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

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:
PlayDownload

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

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.)
Continue reading ‘PHP Skip Lists 2: Implementing Skip Lists in PHP’

Share

PHP Iterator Design Pattern III: Linked Lists

chrouslineWhy Linked Lists?

Up to this point, the discussion of iteration has been limited to one kind of data storage—the array. You will find advantages and disadvantages to linked lists versus arrays, but my purpose here is not to convert you to linked lists away from arrays. Rather, linked lists are required for skip lists, and to understand skip lists, you must first understand both the binary search and linked lists. Future posts in the Iterator series will show how an Iterator pattern can be used in both an iteration through a skip list and an array. (The example in Design Patterns: Elements of Reusable Objet-Oriented Software by Gamma, et al [Gang of Four] uses skip lists to show the utility of the Iterator design pattern.)

PHP has a built-in linked list class (SplDoublyLinkedList), but before discussing that class, linked list built from scratch in PHP will help understand exactly what a linked list is. To get started play the two PHP linked list examples and download the files:
PlayAPlayBDownload

What is a Linked List?

A linked list is made up of a number of nodes connected by reference to one another. Each node contains two fields: a “data” field and a “next” field. The data field can contain any kind of data you want and the the “next” field is a pointer to the next linked node. A doubly linked list has pointers to both the next and previous nodes. Take a look at Figure 1 that shows the basic make-up of a linked list:

Figure 1: Basic linked list

Figure 1: Basic linked list

One way to think about linked lists is as self-linking lists. Content can be anything you want, including other objects, numbers or strings. It is important to understand that linked lists are not necessarily ordered lists but rather each node controls the next and/or previous link.

Implementing the Linked List in PHP

If you search on the Internet, you can find several different kinds of linked list examples in PHP. The one in this post is most likely different because each node is a separate object (class). Figure 2 shows the class diagram for this particular implementation of a linked list:

Figure 2: Class diagram for implementation of a linked list.

Figure 2: Class diagram for implementation of a linked list.

The LinkedList interface includes the two basic requirements for a linked list: content (data) and a pointer to the next node. Like all interface methods, they are abstract by default (without the ‘abstract’ label.)

< ?php
interface LinkedList
{
    function contents();
    function nextUp();
}
?>

With the kind of interface used, the implementations are pretty wide open. Like an array, you can add any kind of data that you want, but you can also include calculated fields returning the results. The nodes for the linked list can easily return different kinds of “cargo” from simple strings as is shown in this example, to numbers, calculated results or just about anything else you might want to throw in. In this particular list, I used different strings with characteristics of OOP programming and languages.

< ?php
class AlphaNode implements LinkedList
{
    function contents()
    {
        return "Dynamic dispatch";
    }
 
    function nextUp()
    {
        return new BetaNode();
    }
}
?>

All of the other nodes are pretty much the same as AlphaNode. Their methods return content or a pointer to the next node. However, on the last node, known as the “terminal node” or the “tail,” you must return a null value. You can have a separate null node that returns null for content and the next node, but all your really need is a termination “next” returning a null value as shown in the “tail” node in this example:

< ?php
class ZetaNode implements LinkedList
{
    function contents()
    {
        return "Loose binding";
    }
    function nextUp()
    {
        return null;
    }
}
?>

Usually you’ll see a “null node” in most implementations, and if you want you can add a separate null node after ZetaNode.
Continue reading ‘PHP Iterator Design Pattern III: Linked Lists’

Share

PHP Iterator Design Pattern II: Binary Search

fastBinaryList Searches

To move ahead with implementations of the Iterator design pattern that help illustrate the value of polymorphic iterations, understanding how different list searches work is essential. In their Iterator illustration, Gamma et al provide an example of a program that has concrete iterators for both standard lists and for skip lists. Skip lists are made up of linked lists and use a binary search algorithm to quickly iterate through the skip list. So to understand skip lists you need to first understand both linked lists and binary searches. This post is dedicated to the latter—binary searches. A future post examines linked lists with skip lists.

Lists come in two basic flavors: ordered and unordered. Searches depend on finding a specific item in a list, and most algorithms are designed for ordered lists. For PHP developers, this can mean anything from searching for an item in a list from a database to an associative array. To get started, consider an associative array and finding a key using the built-in array_search($item, $list) method. The array_search(($item, $list) iterates through an array until it finds the element specified in $item in the array, $list and returns the key. To see a simple example, click the Play button and to download the file, click the Download button.QuizbinaryBtnDownload
All examples were tested on single core (e.g., Raspberry Pi) and multi-core (e.g., Dell, Macintosh) systems.

Using the array_search() method, you can use the key in the key-value pairs as information resources because the search returns the key instead of the value. You can see that in the following class:

< ?php
ERROR_REPORTING( E_ALL | E_STRICT );
ini_set("display_errors", 1);
//ArraySearch.php
class ArraySearch
{
    private $country;
    public function __construct($nation)
    {
         $this->country=$nation;
         //Generate list
         $currency=array('rupiah' => 'Indonesia','peso' => 'Uruguay', 'real' => 'Brazil', 'rupee' => 'India',
                         'dollar' => 'Liberia', 'euro' => 'Luxembourg', 'yen' => 'Japan', 'pound' => 'Egypt',
                         'yuan'  => 'China', 'dinar' => 'Serbia', 'shekel' => 'Israel', 'krone' => 'Norway',
                         'ringgit'  => 'Malasia', 'rial' => 'Iran', 'shilling' => 'Kenya', 'rand' => 'South Africa',
                         'ruble' => 'Belarus','dong' => 'Vietnam');
         echo "$this->country's currency is the " . array_search($this->country,$currency) . ". <p></p>";
    }
}
$tour=$_POST['tour'];
$worker = new ArraySearch($tour);
?>

For relatively short lists, the array_search() method works fine, and you don’t have to write (or remember!) a lot of code to work with it.

The Binary Search

binarySearchTo get a sense of how the binary search works, take a piece of paper (a discarded joke-a-day calendar page works well) and fold it into two equal halves. Keep folding it in half until you have 6 folds. After six folds I could not get a seventh fold—the paper was too fat by that point.

Instead of doubling something, if you halve a value, even very big numbers quickly are reduced to zero. For example, how many times do you think that it would take to half the number 1 million (1,000,000), rounding all halves down, before it became zero? Would it take 1000 halves? 10,000? 100,000? The following class loops through an operation that cuts the value in half with each iteration. It starts with a value of 1 million.

< ?php
//BinaryCut.php
class BinaryCut
{
    public function __construct()
    {
        $bignum=1000000;//1 million
        $count = 0;
        while($bignum > 0)
        {
            $bignum= floor($bignum / 2);
            ++$count;
            echo "iteration# $count : Number=$bignum <br />";
        }
    }
}
$worker=new BinaryCut();
?>

When you run the program, you can see how quickly 1 million is reduced to zero. That same principle is used in a binary search.
Continue reading ‘PHP Iterator Design Pattern II: Binary Search’

Share

PHP Iterator Design Pattern I: Access to Aggregates

iteratorSetting the Table

I tend to think in structural terms to address a given task. I need an object to do “X” and another object to do “Y.” This is in contrast to sequential and procedural thinking; first I’ll do this, and then I’ll do that, and then another thing. Structural thinking is easier on my brain, and it’s a lot easier to make changes and add updates. When it comes to the process of sequentially accessing the elements of an aggregate object (some kind of list), I don’t think of a sequential process, I think of an Iterator design pattern. The Iterator contains both aggregate and iterator objects. That makes it much clearer. Common PHP tasks include iterating through a MySql table. Sometimes MySql table elements are passed to PHP arrays or even XML files. Further, some lists are optimized for searching, such as linked lists and skip lists. We’ll get to those in future posts regarding the Iterator design pattern. However, in PHP, sequential storage outside of a MySql table is typically a numeric or associative array. At this point the focus is on plain vanilla lists stored in aggregate objects we call arrays. Before getting further into this topic, Play the sample and Download the code for an overview:
PlayDownload

According to the Gang of Four, the key idea in the Iterator

is to take the responsibility for access and traversal out of the list object and put it into an iterator object.

Typically, iterating through a list involves something like the following:

< ?php
class StandardIteration
{
    public function __construct()
    {
        $bigList=array('rupiah','peso', 'real', 'rupee',
                       'dollar', 'euro', 'yen', 'pound',
                       'yuan', 'dinar', 'shekel', 'krone',
                       'ringgit', 'rial', 'shilling', 'rand',
                       'ruble', 'dong');
        $counter=0;
        echo "World Currency List <br />";
        foreach ($bigList as $currency) 
        {
            echo $counter . ". " . $currency . "<br />";
            $counter++;
        }
    }
}
$worker=new StandardIteration();
?>

The “list” of elements reside in an array, and using a looping structure, programs can sequentially access all or some of the elements.

Access

Figure 1: Access through a Sequence

Figure 1: Access through a Sequence

When we think of access in PHP OOP, we typically think in terms visibility—private, protected and public. That is certainly an aspect of access, but in looking at lists, even simple one-dimensional ones residing in arrays, access is part of an order. As soon as we get to even slightly more sophisticated lists, we can see the difference in access. Beginning with Figure 1, you can see that when lists are arranged in sequences, the access is based on the position of the element in the order as shown in Figure 1. Above, in the class StandardIteration, you can see such an ordered sequence. The first currency in the list is the rupiah, and the last is the dong. They are in no order other than the one they were placed in the array. To access the Chinese yuan, for example, requires going through 8 iterations before reaching the yuan.

Figure 2: Binary tree access

Figure 2: Binary tree access

Suppose that instead of a sequence (or sequential list), we had used a binary tree as shown in Figure 2. The “7 element” is only three step 1-5-7. Binary trees are used a good deal in programming because the access paths are more efficient. Instead of going through a sequence, you program through the nodes. The quickest route to “7 element” is through the root node (1) then to the 5-node (5) and finally to the 7-element (7). So it should be no surprise that working with different types of lists is important.
Continue reading ‘PHP Iterator Design Pattern I: Access to Aggregates’

Share