Archive for the 'Factory Method' Category

PHP OOP & Algorithms II: What to Use

Published on July 3, 2014 by Bill Sanders in Algorithms, Factory Method, Iterating through Objects, Object Communication, Recursion and Strategy. 0 Comments Tags: , , , , .

algorithm2What Are the Guidelines?

Like just about everything else in computing, there’s a certain amount of empirical testing. More importantly, however, are the general principles derived by both empirical and mathematical calculations. In the first post on algorithms and OOP, you saw an example that showed how many operations were necessary to find “Waldo,” a name near the end of an array of over 1,000 elements. One used a straight up loop and the other a binary search algorithm. Both were pretty quick; in fact it was hard to tell the difference in speed, and without seeing the little dots, you would not have seen the number of iterations required in each algorithm. You also saw that quadratic algorithms grew at rates that can quickly reach a point where processing comes to a crawl.

A Table Guide

Table 1 is derived from the 4th Edition of Algorithms (2011, p. 187) by Robert Sedgewick and Kevin Wayne. I’ve summarized it further. (Examples in the book are all in Java.) It is a rough but useful guide, and I have found it handy for a quick look-up.

Table 1: Algorithm Order of Growth

Name Order of Growth Description Example
 constant  1 statement    2 + 7
 logarithmic  log N divide in half    binary search
 linear  N loop    find max
 linearithmic  N log N divide & conquer    mergesort
quadratic  N² double loop    check all pairs
cubic  N³ triple loop    check all triples
exponential 2N exhaustive search    check all subsets

Fortunately, most of the time our algorithms are pretty simple statements, single loops or recursive calls. All of the models in green are algorithms we should try and stick with. You should avoid the reds ones if possible.

What About Recursive Algorithms?

Those who love to profess a little knowledge like to say that recursion is slower than a loop. As indicated, we really don’t want to end up paying attention to small costs. Recursion is important, and using recursive algorithms is cost effective, especially since the difference in running time is negligible.

We often use recursive implementations of methods because they can lead to compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion.
~Robert Sedgewick and Kevin Wayne

(A recursive example of a logarithmic algorithm is not included here, but you can find a recursive binary search in the post on binary searches.) What we need to pay attention to are the order-of-growth issues. For example, quadratic algorithms on the lower end of the scale are not really that bad, but when the N increases at a squaring rate, it’s easy to run into problems. So if you avoid quadratic algorithms, you’ll be better off when the N increases. On the other hand, whether you’re using a recursive method for a binary search, you’ll not see that much of a difference as the N increases compared to non-recursive methods.

A Strategy Design Pattern Handles Algorithms

This blog has lots of posts detailing the Strategy design patterns; so if you’re not familiar with a PHP implementation of the Strategy pattern, you might want to take a quick look at the code. To get started, play the example and download the code.
PlayDownload

In the last post on algorithms, the program used a Factory Method pattern to produce an array, and in this post, the same pattern is used and two additional array products have been added. However, instead of having the algorithm classes be more or less on their own, all of the algorithm classes have been organized into a Strategy design pattern. Figure 1 is a file diagram of the objects in the application:

Figure 1: Object groupings with Strategy and Factory Method patterns

Figure 1: Object groupings with Strategy and Factory Method patterns

If Figure 1 looks a bit daunting, it is only three object groupings. The HTML and PHP Client make a request for one of seven algorithm implementations through a Strategy pattern. The concrete strategy implementations all get their data from a “data factory.” Figure 2 provides an easier (and more accurate) way to understand what’s going on.

Figure 2: Overview of the main purposes of the objects.

Figure 2: Overview of the main purposes of the objects.

So instead of having a complex task, you only have three groupings of classes and interfaces: Those making a request (Clients), those executing operations on data (Algorithms) organized as a Strategy pattern and the data itself organized with a Factory Method (Data.)

Figure 2 shows a simplified version of what the program does. The Context class considerably eases the requesting process. The HTML UI passes the name of the requested concrete strategy to the Client, and the Client uses the name as a parameter in a Context method. The Client is not bound to any of the concrete strategies because the strategy classes are handled by a Context object and method. (Click continue to see the PHP implementations of the algorithms.)
Continue reading ‘PHP OOP & Algorithms II: What to Use’

PHP OOP & Algorithms I: An Introduction

Published on June 23, 2014 by Bill Sanders in Algorithms, Beginning PHP OOP, Binary Searches, Factory Method, Introduction to Design Patterns, Iterating through Objects and Object Communication. 0 Comments Tags: , , , , , , .

quadAvoiding the Misinformed

Programmers often spend more time un-doing bad information than using good information. One of the comments that set me off recently was someone “explaining” to others on a blog why PHP was not an object oriented language. Then he continued to blather on about the difference between compiled and interpreted languages. Whether or not a language is compiled or not has nothing to do with whether or not it is an object oriented language. Having interfaces, classes and communication between objects are the key criteria of an OOP language, and certainly since PHP5 has been a full-fledged OOP language. (We PHPers should not feel singled out because I recently saw post where a Java programmer pronounced that neither Python nor Perl were OOP, and she was “informed” otherwise by irate Python programmers. Perl has been OOP since V5.) So here I am again wasting time grumbling about people who don’t know what they’re talking about.

Instead of frothing at the mouth over the misinformed, I decided to spent more time with the well-informed. To renew my acquaintance with algorithms I began reading Algorithms 4th Ed. (2011) by Sedgewick and Wayne. Quickly, I learned some very basic truths about algorithms that had been only vaguely floating around in my head. First and foremost are the following:

Bad programmers worry about the code.
Good programmers worry about data structures and their relationships.
—Linus Torvalds (Creator of Linux)

Since we’ve been spending time on this blog acting like good programmers, that was reassuring. In this post, I’d like to look at two things that are important for developing algorithms: 1) What to count as a “cost” in developing algorithms, and 2) Identifying good and bad algorithmic models. First, though, play and download the example. Using two different algorithms, a logarithmic and a linear (both pretty good ones), I’ve added “dots” to loop iterations to visually demonstrate the difference between a logarithmic algorithm (binary search) and a linear algorithm (loop). The “expense” of the algorithm can be seen in the number of dots generated.
PlayDownload

The example is a pretty simple one. However, since this blog is about PHP Design Patterns, I added a little Factory Method. The two algorithm classes act like clients making requests through the factory for a big string array with over 1,000 first names. Figure 1 shows the file diagram:

Figure 1: File diagram for use of Factory Method by two algorithm clients.

Figure 1: File diagram for use of Factory Method by two algorithm clients.

In looking at the file diagram, you may be thinking, “Why didn’t you use a Strategy pattern coupled with that Factory Method?” I thought about it, but then decided you could do it yourself. (Why should I have all the fun?)

Lesson 1: Leave the Bag of Pennies

The first lesson I learned in Bank Robbery 101 was to leave the bag of pennies. They’re just not worth it. Speed is everything in a bank robbery, and so you pay attention to how to get the most with the least time. The same thing applies to analyzing algorithms. For example, an object (as compared to an integer, boolean or string) has an overhead of 16 bytes. I have actually seen posts intoning, “objects are expensive…” Just to be clear,

Objects are not expensive. Iterations are expensive, quadratic algorithms are expensive.

In evaluating an algorithm you need to see how many operations must be completed or the size and nature of the N. An N made of up strings is different than an N made up of Booleans or integers. A quadratic (N²) and cubic (N³) algorithm are among the worst. They’re gobbling up kilo- or megabytes, and so that 16 bytes seems pretty silly to worry about. So instead of seeing an algorithm weight expressed as N² + 84 bytes, you’ll just see it expressed as ~N². (When you see a ~ (tilde) in an algorithm, it denotes ‘approximately.’) Another way of understanding the ~ is to note, They left the bag of pennies.

Lesson 2: Watch out for Nested Loops; they’re Quadratic!

I’ve never liked nested loops, and while I admit that I’ve used them before, I just didn’t like them. They were hard to unwind and refactor, and they always seemed to put a hiccup in the run-time. Now I know why I don’t like them; they’re quadratic.

Quadratic algorithms have the following feature: When the N doubles, the running time increases fourfold.

An easy way to understand the problem with quadradics is to consider a simple matrix or table. Suppose you start with a table of 5 rows and 5 columns. You would create 5² cells—25 cells. Now if you double the number to 10, 10² cells = 100. That’s 4 x 25. Double that 10 to 20 and your have 20² or 400. A nested loop has that same quality as your N increases. If both your inner and outer loop N increases, you’re heading for a massive slowdown.

Algorithms, OOP and Design Patterns are Mutually Exclusive

An important fact to remember is that good algorithms do not guarantee good OOP. Likewise, good OOP does not mean good algorithms. Good algorithms make your code execute more efficiently and effectively. Good OOP makes your programs easier to reuse, update, share and change. Using them together is the ultimate goal of a great program.

PHP Recursion Using Factory Method: Programming to the Interface

Published on April 5, 2014 by Bill Sanders in Design Patterns Principles, Factory Method, Iterating through Objects, Raspberry PI and Recursion. 0 Comments

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.

?View Code 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()
    {  
        if($this->counter <= $this->size)
        {
            echo "" . $this->members[$this->counter] . "
 ";
            ++$this->counter;
            return $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 developers want 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.

PHP Skip Lists 2: Implementing Skip Lists in PHP

Published on February 20, 2014 by Bill Sanders in Factory Method, Iterator, Linked List and Skip Lists. 0 Comments Tags: , , , , .

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’

PHP CMS Project Part V: The Factory Method

Published on July 10, 2013 by Bill Sanders in CMS, Factory Method, Loose Coupling and MySql Connection. 0 Comments

cms5A Simple Factory Method CMS

In deciding which design pattern to apply to this CMS, two came to mind. Because PHP is creating a Web page, creational patterns appeared to be the most appropriate. Both the Factory Method and the Abstract Factory were considered. The Factory Method is the simplest of the two and it can be expanded, and so I settled on it. The Abstract Factory would be more appropriate if the main goal was to select different Web page styles. This CMS is to update and use data from a MySQL table. Since a lot of files make up this CMS, it’s probably a good idea to download them first:
Download

To get started, take a look at Figure 1. In Part IV of this series you saw how to put data into and retrieve it from a database and use in a Web page. That is pretty much what has been done here except the request is through the Creator interface to insure loose coupling. The PageCreator implements the factoryMethod() method which creates a requested product specified by the Client. As a result the Client is only loosely bound to the concrete product it requests.

Figure 1: File Diagram for Factory Method CMS

Figure 1: File Diagram for Factory Method CMS

When the concrete creator object (PageCreator) passes the request for the concrete Product object (PageProduct1()), it does so through the deliverWeb() method—the method implemented through the Product interface.

Multiple Inheritance (Sort of)

Some languages like Java and Python support multiple inheritance. Strictly speaking, PHP does not, but you will find workarounds and you can combine inheritance and implementation in a single child class. In the declaration of the PageProduct1 class, you can see how this is done:

?View Code PHP 

include_once('UniversalConnect.php');
include_once('Product.php');
include_once('ProductTools.php');
class PageProduct1 extends ProductTools implements Product
{
    function deliverWeb()
    {      
        $this->tableMaster="blogette";
        $this->hookup=UniversalConnect::doConnect();
        $this->loadContent();
        $this->content = array("css" => $this->css,
                         "title" => $this->title,
                         "header1" => $this->header1,
                         "header2" => $this->header2,
                         "body1" => $this->body1,
                         "body2" => $this->body2,
                         "image1" => $this->image1,
                         "image2" => $this->image2,
                         "caption1" => $this->caption1,
                         "caption2" => $this->caption2
                         );   
        return $this->content;
    }
 
    private function loadContent()
    {
        //Create Query Statement
        $this->sql ="SELECT * FROM $this->tableMaster WHERE id = 1";
 
        if ($result = $this->hookup->query($this->sql))
        {
            while ($row = $result->fetch_assoc()) 
            {
                $this->css = $row['css'];
                $this->title = $row['title'];
                $this->header1 = $row['header1'];
                $this->header2 = $row['header2'];
                $this->body1 = $row['body1'] . "
";
                $this->body2 = $row['body2'] . "
";
                $this->image1 = "images/" . $row['image1'];
                $this->image2 = "images/" . $row['image2'];
                $this->caption1 = $row['caption1'];
                $this->caption2 = $row['caption2'];
            }
            $result->close();
        }
        $this->hookup->close(); 
    }
}
?>

The declaration line:

class PageProduct1 extends ProductTools implements Product

imbues PageProduct1 with both the properties of the ProductTools and the interface of the Product. By having the abstract class ProductTools provide the essential properties of a Product child, the properties need not be declared in the concrete product child classes and add some uniformity. At the same time the Product child implementations have the common Product interface. If you’re thinking that a single abstract class could have handled both the method and the properties, you’d be right. However, but having a separate class for properties, the same design could easily be adapted to include a whole new set of properties if need be.

You probably recognize PageProduct1 as the RetrieveBlog class from Part IV of the CMS series. About the only difference is that I created an abstract class ProductTools to store common product properties for use by any other product classes that the developer may care to add. It reduces clutter and makes it easier to make small changes. For example, one strategy considered is to create several different instances of PageProduct1, such as PageProduct2, PageProduct3 and so on. Each could simply identify a different table ID number to be called from the Client class. On the other hand, new data could be added simply by using an UPDATE SQL command to change the content of the record with an ID selected by the class.

Figure 2 shows an added page delivered as a concrete product upon a Client request, and as you can see, it looks just like the others in this series, but the content has changed:

Figure 2: Page created with Factory Method CMS

Figure 2: Page created with Factory Method CMS

The nature of the page has not changed, but the way in which it is requested has. The request is through the Creator interface; so next we’ll take a look at the concrete creator class and the new Client class.

Request to the Creator

The real “un-coupler” participant in the Factory Method design pattern is the Creator and its implementations. In this instance, the single concrete class passes on the request from the Client for a Product. In the following listing are both the Creator abstract class and its child class, PageCreator: (Note: Product type hinting is used so that additional concrete product implementations may be called through the same interface. This is an example of the design pattern principle of program to the interface (Product) and not the implementation (PageProduct1).

?View Code PHP 

//Creator.php
abstract class Creator
{
        protected $webProduct;
        abstract public function factoryMethod(Product $pageNow);
}
?>
 
?php
//ConcreteCreator.php
include_once('Creator.php');
 
class PageCreator extends Creator
{
        public function factoryMethod(Product $pageNow)
        {
                $this->webProduct=new $pageNow();
                return($this->webProduct->deliverWeb());
        }
}
?>

At this point, you may wonder where the content of the $pageNow parameter comes from. In this case, and all along in this series actually, the Web page has been the client. It is requesting content for the HEREDOC page. So, we might as well put it where it belongs—in the Client class as shown:

?View Code PHP
hd["image2"]}>
  CMSTEMPLATE;echo$this->document;}}$worker=new Client();?>

include_once('PageProduct1.php');
include_once('PageCreator.php');
 
class Client
{
    private $content;
    private $document;
    private $hd;
 
    function __construct()
    {
        $this->content=new PageCreator();
        $this->hd = $this->content->factoryMethod(new PageProduct1());
        $this->document = <<
        
        
        hd["css"]}>
        
        {$this->hd["title"]}
        
        
        

            
{$this->hd["header1"]}

        

            

                

                
{$this->hd["header2"]}

                

                {$this->hd["body1"]}
                {$this->hd["body2"]}
                

                    hd["image1"]}>

{$this->hd["caption1"]}
{$this->hd["caption2"]}

The two lines in the Client that show it to be part of a Factory Method design pattern are:

$this->content=new PageCreator();
$this->hd = $this->content->factoryMethod(new PageProduct1());

The Client makes the request through the PageCreator class and then invokes the factoryMethod() to specify the product, PageProduct1. Now suppose later that you want to make more products—implementations of the Product interface. Because the request in the Creator specifies through type hinting is for the Product and not any specific implementation of the Product interface, it can handle any Product implementation.

You may want to review other implementations of the Factory Method on this blog for a review in understanding how everything works together. However, it comes down to Request -> Creator -> Product.

The CMS Co-Stars

In wrapping up this series on creating a CMS using a design pattern in PHP, you will find a folder full of some of the tools you’ll need for creating and maintaining the system in a folder named “Administrative.” At some point soon, I hope to implement it for the http://www.sandlight.com site, and I’d be very interested in what others have done or ideas for making it better. In the meantime enjoy exploring its possibilities.