Generating pagination links

Question

I recently had an interview for a programming job and after the interview I was then asked to create a function with the following brief:

The Task:

Relating to pagination links: given a page number, a total number of pages, and an amount of 'context' pages, generate the appropriate pagination links. For example, with 9 pages in total and a context of 1 page, you would get the following results for pages 1 to 9:

For page 1: 1 2 ... 8 9

For page 2: 1 2 3 ... 8 9

For page 3: 1 2 3 4 ... 8 9

For page 4: 1 2 3 4 5 ... 8 9

For page 5: 1 2 ... 4 5 6 ... 8 9

For page 6: 1 2 ... 5 6 7 8 9

For page 7: 1 2 ... 6 7 8 9

For page 8: 1 2 ... 7 8 9

For page 9: 1 2 ... 8 9

I would like you to write a PHP function with the following signature to solve this task:

function outputLinks($page, $numberOfPages, $context)

The code below is what I submitted and I've now been asked to complete another task which is good news in my eyes, so I can only assume that my code for this task was at least good enough. But I was just wondering how good my submission really was! Is there an easier (or simpler) way to achieve the same results? Could I shorten my code at all?

<?php

    // Global Variables

        $p = $_GET['p']; // Current Page
        $t = 9;          // Total Pages
        $c = 1;          // Context Pages

    // Pagination Function

        function outputLinks($page, $numberOfPages, $context) {

            // Correct page variable

                if (!$page || $p < 1) { $page = 1; }
                if ($page > $numberOfPages) { $page = $numberOfPages; }

            // Set array variables

                $leftArray = $midArray = $rightArray = array();

            // Left Array

                for ($x = 1; $x <= (1 + $context) && $x <= $numberOfPages; $x++) {
                    array_push($leftArray, $x);
                }

            // Right Array

                for ($x = $numberOfPages - $context; $x <= $numberOfPages && $x > 0; $x++) {
                    if (!in_array($x, $leftArray)) {
                        array_push($rightArray, $x);
                    }
                }

            // Left/Right Array First/Last values to variables

                $firstInLeftArray  = current($leftArray);
                $lastInLeftArray   = end($leftArray);
                $firstInRightArray = current($rightArray);
                $lastInRightArray  = end($rightArray);

            // Middle Array

                if ($page == $firstInLeftArray || $page == $lastInRightArray) {

                    if (($firstInRightArray - $lastInLeftArray) > 1) {
                        array_push($midArray, ' ... ');
                    }

                } else {

                    if (in_array($page, $leftArray)) {
                        for ($x = $page; $x <= ($page + $context) && $x <= $numberOfPages; $x++) {
                            if (!in_array($x, $leftArray) && !in_array($x, $rightArray)) {
                                array_push($midArray, $x);
                            }
                        }
                    } else if (in_array($page, $rightArray)) {
                        for ($x = ($page - $context); $x < $firstInRightArray && $x > $lastInLeftArray; $x++) {
                            array_push($midArray, $x);
                        }
                    } else {
                        for ($x = ($page - $context); $x <= ($page + $context) && $x > 0; $x++) {
                            if (!in_array($x, $leftArray) && !in_array($x, $rightArray)) {
                                array_push($midArray, $x);
                            }
                        }
                    }

                    // Middle Array First/Last values to variables

                        $firstInmidArray = current($midArray);
                        $lastInmidArray  = end($midArray);

                    // Ellipses for omitted numbers

                        if (($firstInmidArray - $lastInLeftArray) > 1) {
                            array_push($leftArray, ' ... ');
                        }

                        if (!empty($midArray) && ($firstInRightArray - $lastInmidArray) > 1) {
                            array_push($midArray, ' ... ');
                        }

                }

                // Display Arrays

                    echo 'Page '.$page.' of '.$numberOfPages.': ';

                    foreach ($leftArray as $value) {
                        if ($value == ' ... ') { echo $value; } else { echo ' <a href="?p='.$value.'" target="_self">'.$value.'</a> '; }
                    }

                    foreach ($midArray as $value) {
                        if ($value == ' ... ') { echo $value; } else { echo ' <a href="?p='.$value.'" target="_self">'.$value.'</a> '; }
                    }

                    foreach ($rightArray as $value) {
                        echo ' <a href="?p='.$value.'" target="_self">'.$value.'</a> ';
                    }

        }

    // Initialize document

        print('<!DOCTYPE HTML><html><head><title>Pagination Function</title></head><body>');

    // Generate Pagination through the outputLinks function

        outputLinks($p, $t, $c);

    // Close the document

        print('</body></html>');

?>

Answer 1

Yes, I would have written this completely differently (so I decided to do just that). I'll follow my solution with a hopefully scientific analysis of both solutions. Finally I'll give some personal recommendations.

Note: The reason for the in-depth analysis is that I was already interested in pagination and thinking about an implementation for a framework that I am writing.

Model

/** Model the data for pagination.
 */
class ModelPaginator
{
    /** Get the links for pagination.
     *  @param page \int The page number for the current page.
     *  @param numberOfPages \int The total number of paginated pages.
     *  @param context \int The number of context pages surrounding the current,
     *  first and last pages.
     *  @return \array An array with the ranges of pages for pagination.
     */
    public function getLinks($page, $numberOfPages, $context)
    {
        // Sanitize the inputs (I am trying to follow your example here, I would
        // throw exceptions if the values weren't as I expected).
        $numberOfPages = max($numberOfPages, 1);
        $context       = min(max($context, 0), $numberOfPages - 1);
        $page          = min(max($page, 1), $numberOfPages);

        return array_unique(
            array_merge(range(1, 1 + $context),
                        range(max($page - $context, 1),
                              min($page + $context, $numberOfPages)),
                        range($numberOfPages - $context, $numberOfPages)));
    }
}

View

/** A simple view for paginator links.
 */
class ViewPaginatorLinks
{
    protected $separator;

    /** Construct the paginator.
     *  @param separator \string Separator between gaps.
     */
    public function __construct($separator=' ... ')
    {
        $this->separator = $separator;
    }

    /** Write the pagination links.
     *  @param links \array The links array.
     *  @param currentPage \int The current page.
     */
    public function write($links, $currentPage)
    {
        $currentPage = min(max($currentPage, 1), end($links));

        echo 'Page ' . $currentPage . ' of ' . end($links) . ': ';
        $previousPage = 0;

        foreach ($links as $page) {
            if ($page !== $previousPage + 1) {
                $this->writeSeparator();
            }

            $this->writeLink($page);
            $previousPage = $page;
        }
    }

    /*******************/
    /* Private Methods */
    /*******************/

    /** Write the link to the paginated page.
     *  @param page \array The page that we are writing the link for.
     */
    private function writeLink($page)
    {
        echo '<a href="?p=' . $page . '" target="_self">' . $page . '</a>' .
            "\n";
    }

    /// Write the separator that bridges gaps in the pagination.
    private function writeSeparator()
    {
        echo '<span>' . $this->separator . '</span>' . "\n";
    }
}

Usage

$numberOfPages = 29;
$currentPage = 13;
$context = 1;

$Model = new ModelPaginator;
$View = new ViewPaginatorLinks;

$View->write($Model->getLinks($currentPage, $numberOfPages, $context),
             $currentPage);

Analysis

I'll be going through some metrics thanks to PHPLOC. I added the maximum line length to these metrics.

Your Solution

Lines of Code (LOC):                                117
  Cyclomatic Complexity / Lines of Code:           0.37
Comment Lines of Code (CLOC):                        34
Non-Comment Lines of Code (NCLOC):                   83

Maximum Line Length                                 120

My Solution

Lines of Code (LOC):                                 97
  Cyclomatic Complexity / Lines of Code:           0.03
Comment Lines of Code (CLOC):                        34
Non-Comment Lines of Code (NCLOC):                   63

Maximum Line Length                                  80

Lines of Code

My solution has 20 fewer lines. This could well be due to removing quite a few blank lines. However, measured in characters it is 2905 characters long against your 4089. So there is definitely a large difference in typing required.

Cyclomatic Complexity

This is a measure of how complex the code is (see wikipedia). Highly complex code is normally harder to maintain and contains more bugs. My code is a factor of 10 less complex. This is due to the flatness of my code. See Jeff Atwood's Flattening Arrow Code blog.

Comments

The number has remained the same according to PHPLOC, but it seems to be counting blank lines. Manually I can only count 14 in your code versus 27 in mine, even though the number of lines of code were reduced in my solution. Proportionally the commenting in my solution is much higher. At the highest level of abstraction (class, function definitions) I have comments where you have virtually none. My comments cover input parameters to functions and can be used in automatic documentation tools like Doxygen or PHPDocumentor.

Line Length

Firstly, I am unsure whether the formatting of your code here is exactly as it was. I'll assume the true maximum line length of your code is 120 characters. These days monitors can handle 120 characters wide. However when you are editing two or three files side by side they can't. You also end up with large blank areas for showing the long lines (unless you are ok with it wrapping).

Performance

I ran each code 100, 000 times with no output being echoed (the buffer was cleared after each iteration).

There were a few different configurations that I tested as far as object creation and usage:

• Creating objects within each loop: Your code was 21% faster.
• Creating the objects outside of the loop: Your code was 10% faster.
• Creating the objects outside the loop, getting the model data and running only the view code in the loop: Mine was 27% faster.

Your code has the better performance, but the 100, 000 iterations only took 5.8 4.2 seconds (see edit below) on my not very fast machine. I think the performance difference is probably due to my split of Model and View. I would only consider changing this split if the code was running on a site with enormous traffic and it was shown by profiling that real gains could be had from changing the pagination.

Edit: The performance gains from your solution were troubling me. With some profiling I was able to see that the View was wasting a lot of time dispatching the calls with $this->writeSeparator and $this->writeLink. Replacing these calls with their code (seeing as they were only 1 line anyway) led to a large performance gain. My code was faster by 10%, 18% and 59%. Worst case performance is 4.2s for 100 000 iterations (context = 1).

Real Recommendations

The following line should not have $p in it. Globals are bad practice and will only make you look bad.

if (!$page || $p < 1) { $page = 1; }

Comments belong with the code they are commenting on. A blank line after a comment only distances it from that.

I think your code was missing a '}' for the end of your function.

Mixed indentation for if/elseif removes the visual cues for grouping. Instead of:

if () {
} else if () {
}

Use:

if () {
}
elseif () { // elseif is equivalent to else if
}

Similarly I would avoid one line if and if/else statements

Answer 2

You can cut out some redundancy by just using one array to store the results, and you can cut down on the number of operations by doing simple checks against what we know will be the last and first members of the outer page groups instead of checking whether those numbers are in the right/left arrays. If you wanted to be super fancy, and save even more operations, you could store all those values in variables so you're not doing the arithmetic operations every iteration in the loops, but I didn't bother.

I'm not too well versed in php, but here's a version with some changes. I was able to cut about 40 lines.

<?php

    // Global Variables

        $p = $_GET['p']; // Current Page
        $t = 9;          // Total Pages
        $c = 1;          // Context Pages

    // Pagination Function
    function outputLinks($page, $numberOfPages, $context) 
    {
        $display = array();

        //Left-side pages
        for($i = 1; $i <= 1 + $context; $i++)
        {
            array_push($display, buildPageLink($i));
        }

        if(($page - $context) - (1 + $context) > 1)
            array_push($display, "...");

        //Middle pages
        for($i = ($page - $context); $i <= ($page + $context); $i++)
        {
            if($i > (1 + $context) && $i < ($numberOfPages - $context))     
                array_push($display, buildPageLink($i));
        }

        if($page + $context < $numberOfPages - $context)
            array_push($display, "...");

        //Right-side pages
        for($i = $numberOfPages - $context; $i <= $numberOfPages; $i++)
        {
            array_push($display, buildPageLink($i));
        }

        echo 'Page ' . $page . ' of ' .$numberOfPages . ': ';
        foreach($display as $val)
        {
            echo $val;
        }

    }

    function buildPageLink($pagenum)
    {
        return ' <a href="?p='.$pagenum.'" target="_self">'.$pagenum.'</a> ';
    }

    // Initialize document

    print('<!DOCTYPE HTML><html><head><title>Pagination Function</title></head><body>');

    // Generate Pagination through the outputLinks function

    outputLinks($p, $t, $c);

    // Close the document

    print('</body></html>');

?>

Answer 3

<?php
function outputLinks( $page, $numberOfPages, $context ) {
    # find the context pages
    $pages = array_filter( range( $page - $context, $page + $context ), function( $value ) use ($numberOfPages) {
        if ( $value <= 2 || $value >= ( $numberOfPages - 1 ) ) return false;
        return true;
    });

    # are there any gaps to fill with '...':
    if ( isset( $pages[0] ) ) {
        if ( $pages[0] > 2 ) array_unshift( $pages, '...' );
        if ( $pages[ count( $pages ) - 1 ] < ( $numberOfPages - 2 ) ) array_push( $pages, '...' );
    }

    # add the first and last links:
    array_push(  $pages, $numberOfPages - 1, $numberOfPages );
    array_unshift( $pages, 1, 2 );

    foreach ( $pages as $key => & $page ) {
    #   if ( is_int( $page ) ) $page = '<a href="?p=' . $page . '" />';
    }

    return $pages;
}
# your example with my impl:
for ( $i = 1; $i <= 9; $i++ ) echo implode(' ', outputLinks( $i, 9, 1 ), PHP_EOL;

I had to give this one a shot aiming for the least amount of lines logic as possible, so here's my solution. It's split in 4 "blocks": - find the context pages - fill in blanks between the beginning/ending and the context pages with '...' - add the first/last pages - lastly, loop through the results ( uncomment line 20 ) and make them into links.

I can't think of anything simpler, it's already down to 16 lines of code.

Cheers