PHP Recursion Using Factory Method: Programming to the Interface

recurCoverRecursion as Client

Previous posts on this blog discussed Recursion and the Factory Method design pattern. In working with a recursive object to traverse a list of strings or numbers (or any other objects for that matter), PHP developers typically target an array. In developing a simple recursive object, I realized that it made more sense to set up an another class for the array object. Why bind the process or creating and populating an array to the object designed to transverse it? After all, what if you wanted to use the object to traverse any list; not just the one bound to the recursion operation?

The Factory Method for Handling Array Objects

From the not-too-difficult decision to separate the array creation and population process from the transversal process, it was a pretty quick leap to using the Factory Method. That would give me plenty of flexibility, and I would be able to use the factory implementations to do different things with the products—like sort or filter them before returning them to the requesting client.

In this case, the requesting client would be the Recursion object.

The Client class triggers the appropriate method in the Recursion object to select whatever list is available. The selection process would be handled by an HTML UI. The class diagram is integrated into the application. Click the Play button below first to see the operation and class diagram and then the Download button to get all of the files:
PlayDownload

When you Play the program, notice in the class diagram that the Recursion class includes a method, getArray(Factory). This method is an example of programming to the interface and not the implementation. The method expects an argument that is a Factory child, but it can be any Factory implementation. The type hint is the Factory interface and so any implementation of Factory works fine. As a result, you can add as many different Factory implementations as you want without having to worry about a train wreck like you can get easily by programming to implementations.

The Recursion Class Makes use of the Factory

As noted at the outset, the Recursion object is set up to use any Factory implementation. In this example, only three implementations use the Factory interface. The factory method itself is makeArray(), but it’s left to the implementations how the array to be returned to the requester—the Recursion class. The PeopleFactory and PetsFactory sort the list in alphabetical order before returning it to the requesting client. However, the ToolsFactory uses a reverse sort so that the highest Wrench element is first and the Awl is last. The recursive iterator in the Recursion object could care less; it just transverses whatever list it gets from the Factory implementation and prints it to the screen.

<?php
class Recursion
{
    //The Recursion class is the Client
    //in making a request from the Factory
    private $members;
    private $counter=0;
    private $size;
 
    public function getPeople()
    {
        //Makes request to Factory child
        $factoryNow=new PeopleFactory();
        $this->getArray($factoryNow);
    }
 
    public function getTools()
    {
        //Makes request to Factory child
        $factoryNow=new ToolFactory();
        $this->getArray($factoryNow);
    }
 
    public function getPets()
    {
        //Makes request to Factory child
        $factoryNow=new PetsFactory();
        $this->getArray($factoryNow);
    }
 
    //By programming to the interface (Factory)
    //you can use different implementations
    private function getArray(Factory $factoryBuild)
    {
        $this->members=$factoryBuild->makeArray();
        $this->size=count($this->members)-1;
        $this->recursive();
    }
 
    private function recursive()
    {  
        echo "<span style='color:white; font-family:Verdana,Arial,Helvetica,sans-serif'>" . $this->members[$this->counter] . "<br /> </span>";
        ++$this->counter;
        if($this->counter <= $this->size)
        {
            $this->recursive();
        }
    }
}
?>

As you can see, the recursive() method is pretty simple. It just keeps using echo to send the current element value to the screen, increments the counter by 1, and then if it hasn’t exceeded the length of the array, it calls itself to repeat the process. The Factory implementations already took care of the sorting arrangements–or anything else the developers wants the Factory implementations to do.

Each of the 3 public “getter” methods call the private getArray(Factory) method using a Factory implementation as an argument. The passed argument calls the factory method (makeArray()) to get the requested array which is stored in the $members property. Finally, getArray(Factory) calls the recursive() iteration method that traverses the $members property containing the array.

A Lot of Work for Iteration

If you’re thinking

…that’s a lot of work for a simple operation (displaying sorted lists on the screen)

I’d not disagree. The point of design patterns, though, is re-use on a much larger scale. As projects get bigger and bigger, you need tools to deal with them. The good news is that if you can use them on a small scale like the examples on this blog and in Learning PHP Design Patterns, you’re prepared to work on larger projects involving teams of programmers and some seriously good applications.

Share

OOP Principles: The Liskov Substitution Principle

liskovPrinciples Rule!
It’s been a while since OOP/Design Pattern principles have been a topic on this blog, and now is as good time as any. The 1987 OOPSLA keynote address by Barbara Liskov contained what has become known as the Liskov Substitution Principle. In that address and books and papers, the Liskov principle is an OOP one that is part of the more general OOP set of principles. In languages like C++ and Java where you have strongly typed languages, you can declare a variable (property) by the parent data type. Since PHP is flexibly typed, the data type can change, and while that practice [changing data types for a variable] is not recommended, it is certainly possible. As a result, it’s not as easy to explain and illustrate the principle with PHP.

Essentially, the principle holds that,

If a Client is using a reference to a base class it should be able to substitute a derived class for it without affecting the program’s operation

Actually Dr. Liskov said,:

If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2 then S is a subtype of T.

and I was trying to put it in less technical terms.

Why is the Liskov Substitution Principle Important?

You can easily see three reasons that the principle is important:

  1. If substitutions cannot be made then class hierarchies would be a mess. Whenever a subclass instance is passed as parameter to any method, surprises might occur.
  2. Without the possibility of Liskov type substitutions unit tests for the superclass would never succeed for the subclass.
  3. Changes are easier and more predictable because you know what to expect from the superclass.

No doubt you can find more, but for now, the Liskov substitution principle is another way to keep your code loose and reusable and subject to change.

If the Client has an object of a certain type, it should be able to substitute a derived object of the same type. For example, suppose you have an abstract class named Automobile and from that class you have subclasses of Ford, Toyota, and Peugeot. Your Client has an object, $myAuto. The $myAuto object can be any of the subclasses, and if a substitution is made for any one of them everything keeps on working without a problem and the change is unknown to the Client class. So if you substitute a Ford for a Toyota, the Client can work with the objects without having to adjust for the change. What’s more, if you want to add a Fiat or Mercedes Benz class as a subclass of Automobile, the $myAuto object handles it with nary a whimper.

The one caveat is that the subclasses must all honor the contractual conditions of the parent class. So, any methods in the parent class must be functioning in the subclass (aka, derived class.)

Now you may be thinking, So what? If you’re at all familiar with other principles of OOP and Design Patterns, this principle may sound vaguely familiar, but what is the importance of this concept/principle/idea? It is this: Because the Client is unaware of the concrete class that the object may implement, the structure is far more resilient. Not only can the same structure be reused, it can be changed, updated and generally fiddled with without easily breaking anything. (Think of adding more car manufacturers to the Automobile class.) As far as the Client is concerned, as long as the interface rules are followed with the object, everything is hunky-dory. To get started Play the example and Download the source code:
PlayDownload

A Simple Practice for PHP Programmers

As a principle, the Liskov Substitution Principle is easy to use. The problem is in demonstrating it in PHP because of the lack of assigned data types to properties. However, using PHP type hinting, you will see how it works using at a classic example where the Liskov substitution principle (LSP) is used.

Explanations of how LSP works often use a rectangle/square example. Typically most programmers see two alternatives to illustrate LSP programming a rectangle and a square; with LSP and without LSP.

Beginning with the geometric observation, all squares are also rectangles, we’re likely to create a structure like that shown in Figure 1:

Figure 1: Square is a child of Rectangle

Figure 1: Square is a child of Rectangle

After all, we can envision a square as nothing more than a rectangle with equal sides. So an operation such as,

makeRectangle(w,h);

is an effective way to make either a square or rectangle. We add the Square class simply to examine the LS Principle; otherwise creating rectangles or squares would be accomplished using the makeRectangle(w,h) method making sure that w and h are equal when making squares. The inheritance path clearly indicates that a Square object IS A Rectangle. (That is, the two have an IS A relationship.) However, because Rectangle is a concrete class if I substitute Rectangle for Square, I’m going to have to change the type. I cannot substitute an instance of Rectangle for an instance of Square. This violates the Liskov Substitution Principle.
Continue reading ‘OOP Principles: The Liskov Substitution Principle’

Share

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 Skip Lists 1: The Quickest Route Home

skiptownA few years ago I created a post on Skip Lists (different blog), and several people told me that it clarified the concept of skip lists for them; so I’m reproducing it here for PHP developers. Using the analogy of rail travel in the New York-Hartford-Boston area, I show how the skip list can work in the world apart from programming. 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 train lines between NYC and Boston

Figure 1: Three train lines between NYC 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, look at Figure 2 to see the fastest route highlighted in yellow.

Figure 2: The Route that Skips the Most Stops

Figure 2: The Route that Skips the Most Stops


If you traced the route highlighted in yellow in Figure 2; then you understand how skip lists work. In a similar way, the Binary Search discussed here does not start at the beginning and iterate through an entire ordered list. Rather it splits the list determining the quickest way to the search item.

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

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 4: Linked list with multiple pointers<


Figure 5: Node with multiple pointers

Figure 5: Node with multiple pointers

The arrows now have balls on their tails and look like pointers—and we know that pointers hold a reference to the next node. If we have multiple pointers with some of our nodes, we can have a single linked list that includes pointers that skip certain nodes. Figure 5 shows how that might look in the first node:

Keeping in mind that the linked lists are ordered (sorted) our search for the value “30″ would look something like this:

  • Starting point would be on the shortest linked list: 30 is > 25 but < 53.
  • Drop to next level down to the second shortest list: 30 is < 43.
  • Drop to next level down to the third shortest list: 30 == 30. Your search is over.

Now we’re ready to deal with coding skip lists in PHP5. We’ll have to work out the algorithms, and in the next post on skip lists we should be able to have a working skip list that we can use with an iterator pattern.

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