Smart Pagination Algorithm

Smart pagination algorithm

Here is some code based on original code from this very old link. It uses markup compatible with Bootstrap's pagination component, and outputs page links like this:

[1] 2 3 4 5 6 ... 100
1 [2] 3 4 5 6 ... 100
...
1 2 ... 14 15 [16] 17 18 ... 100
...
1 2 ... 97 [98] 99 100

<?php

// How many adjacent pages should be shown on each side?
$adjacents = 3;

//how many items to show per page
$limit = 5;

// if no page var is given, default to 1.
$page = (int)$_GET["page"] ?? 1;

//first item to display on this page
$start = ($page - 1) * $limit;

/* Get data. */
$data = $db
    ->query("SELECT * FROM mytable LIMIT $start, $limit")
    ->fetchAll();

$total_pages = count($data);

/* Setup page vars for display. */
$prev = $page - 1;
$next = $page + 1;
$lastpage = ceil($total_pages / $limit);
//last page minus 1
$lpm1 = $lastpage - 1;

$first_pages = "<li class='page-item'><a class='page-link' href='?page=1'>1</a></li>" .
    "<li class='page-item'><a class='page-link' href='?page=2'>2</a>";

$ellipsis = "<li class='page-item disabled'><span class='page-link'>...</span></li>";

$last_pages = "<li class='page-item'><a class='page-link' href='?page=$lpm1'>$lpm1</a></li>" .
    "<li class='page-item'><a class='page-link' href='?page=$lastpage'>$lastpage</a>";

$pagination = "<nav aria-label='page navigation'>";
$pagincation .= "<ul class='pagination'>";

//previous button

$disabled = ($page === 1) ? "disabled" : "";
$pagination.= "<li class='page-item $disabled'><a class='page-link' href='?page=$prev'>« previous</a></li>";

//pages 
//not enough pages to bother breaking it up
if ($lastpage < 7 + ($adjacents * 2)) { 
    for ($i = 1; $i <= $lastpage; $i++) {
        $active = $i === $page ? "active" : "";
        $pagination .= "<li class='page-item $active'><a class='page-link' href='?page=$i'>$i</a></li>";
    }
} elseif($lastpage > 5 + ($adjacents * 2)) {
    //enough pages to hide some
    //close to beginning; only hide later pages
    if($page < 1 + ($adjacents * 2)) {
        for ($i = 1; $i < 4 + ($adjacents * 2); $i++) {
            $active = $i === $page ? "active" : "";
            $pagination .= "<li class='page-item $active'><a class='page-link' href='?page=$i'>$i</a></li>";
        }
        $pagination .= $ellipsis;
        $pagination .= $last_pages;
    } elseif($lastpage - ($adjacents * 2) > $page && $page > ($adjacents * 2)) {
        //in middle; hide some front and some back
        $pagination .= $first_pages;
        $pagination .= $ellipsis
        for ($i = $page - $adjacents; $i <= $page + $adjacents; $i++) {
            $active = $i === $page ? "active" : "";
            $pagination .= "<li class='page-item $active'><a class='page-link' href='?page=$i'>$i</a></li>";
        }
        $pagination .= $ellipsis;
        $pagination .= $last_pages;
    } else {
        //close to end; only hide early pages
        $pagination .= $first_pages;
        $pagination .= $ellipsis;
        $pagination .= "<li class='page-item disabled'><span class='page-link'>...</span></li>";
        for ($i = $lastpage - (2 + ($adjacents * 2)); $i <= $lastpage; $i++) {
            $active = $i === $page ? "active" : "";
            $pagination .= "<li class='page-item $active'><a class='page-link' href='?page=$i'>$i</a></li>";
        }
    }
}

//next button
$disabled = ($page === $last) ? "disabled" : "";
$pagination.= "<li class='page-item $disabled'><a class='page-link' href='?page=$next'>next »</a></li>";

$pagination .= "</ul></nav>";

if($lastpage <= 1) {
    $pagination = "";
}

echo $pagination;

foreach ($data as $row) {
    // display your data
}

echo $pagination;

Smart pagination algorithm that works with local data cache

Versioning DB is the answer for resultsets consistency.
Each record has primary id, modification counter (version number) and timestamp of modification/creation. Instead of modification of record r you add new record with same id, version number+1 and sysdate for modification.

In fetch response you add DB request_time (do not use client timestamp due to possibly difference in time between client/server). First page is served normally, but you return sysdate as request_time. Other pages are served differently: you add condition like modification_time <= request_time for each versioned table.

Pagination algorithm that doesn't allow a page to be too big or small

My inclination would be to do something like this:

function paginate<T>(arr: T[], maxPerPage: number): T[][] {
    const numPages = Math.ceil(arr.length / maxPerPage);
    const minPerPage = Math.floor(arr.length / numPages);
    const numBigPages = arr.length % numPages;
    console.log(numPages, minPerPage, numBigPages)
    const ret: T[][] = [];
    for (let pageNum = 0, curElem = 0; pageNum < numPages; pageNum++) {
        const numOnThisPage = minPerPage + (pageNum < numBigPages ? 1 : 0);
        ret.push(arr.slice(curElem, curElem + numOnThisPage));
        curElem += numOnThisPage;
    }
    return ret;
}

The idea is to only ask for the maximum number of elements per page maxPerPage, and determine the number of pages numPages by dividing the array length by this maximum, rounding up to a whole number if necessary.

Then the task is to divide the elements into these pages. Again, you can divide the array length by number of pages (arr.length / numPages) and put that many elements into each page. If that's not a whole number, then some "small" pages will have the whole number less than this, minPerPage = Math.floor(arr.length / numPages), and some "big" pages will have one more, minPerPage + 1. You can calculate the number of big pages numBigPages by taking the remainder when dividing the array length by the number of pages. (If this is confusing, imagine distributing into numPages pages one element at a time; you'd end up putting in minPerPage into each page, and then you'd have some left over. You'd likely want no more than one of these leftovers per page, so the number of leftovers equals the number of big pages numBigPages.)

So, how do we distribute the leftovers into big pages? It sounds like you want all the big pages to come first and then all the small pages. So we just make sure that if the current page number is less than the number of big pages, we make it a big page, and otherwise it's small.

---

Let's see how it does on your examples:

const range = (n: number) => Array.from({ length: n }, (_, i) => i + 1);

console.log(JSON.stringify(paginate(range(2), 8))); // [[1,2]]
console.log(JSON.stringify(paginate(range(2), 2))); // [[1,2]]
console.log(JSON.stringify(paginate(range(6), 3))); // [[1,2,3],[4,5,6]]
console.log(JSON.stringify(paginate(range(6), 2))); // [[1,2],[3,4],[5,6]]

console.log(JSON.stringify(paginate(range(7), 4))); // [[1,2,3,4],[5,6,7]]
console.log(JSON.stringify(paginate(range(10), 4))); // [[1,2,3,4],[5,6,7],[8,9,10]]

console.log(JSON.stringify(paginate(range(11), 10))); // [[1,2,3,4,5,6],[7,8,9,10,11]]
console.log(JSON.stringify(paginate(range(21), 10)));
// [[1,2,3,4,5,6,7],[8,9,10,11,12,13,14],[15,16,17,18,19,20,21]]

That looks like what you wanted, right?

---

Obviously the exact implementation of that algorithm can change; if you want to use lodash or to make the array via purely functional methods instead of iterating and using push(), that's up to you. But the basic concept seems to match up with what you want. Anyway, hope this lets you proceed. Good luck!

Playground link to code

Algorithm / pseudo-code to create paging links?

There are several other answers already, but I'd like to show you the approach I took to solve it:
First, let's check out how Stack Overflow handles normal cases and edge cases. Each of my pages displays 10 results, so to find out what it does for 1 page, find a tag that has less than 11 entries: usability works today. We can see nothing is displayed, which makes sense.

How about 2 pages? Find a tag that has between 11 and 20 entries (emacs works today). We see: "1 2 Next" or "Prev 1 2", depending on which page we're on.

3 pages? "1 2 3 ... 3 Next", "Prev 1 2 3 Next", and "Prev 1 ... 2 3". Interestingly, we can see that Stack Overflow itself doesn't handle this edge case very well: it should display "1 2 ... 3 Next"

4 pages? "1 2 3 ... 4 Next", "Prev 1 2 3 ... 4 Next", "Prev 1 ... 2 3 4 Next" and "Prev 1 ... 3 4"

Finally let's look at the general case, N pages: "1 2 3 ... N Next", "Prev 1 2 3 ... N Next", "Prev 1 ... 2 3 4 ... N Next", "Prev 1 ... 3 4 5 ... N Next", etc.

Let's generalize based on what we've seen:
The algorithm seems to have these traits in common:

• If we're not on the first page, display link to Prev
• Always display the first page number
• Always display the current page number
• Always display the page before this page, and the page after this page.
• Always display the last page number
• If we're not on the last page, display link to Next

Let's ignore the edge case of a single page and make a good first attempt at the algorithm: (As has been mentioned, the code to actually print out the links would be more complicated. Imagine each place we place a page number, Prev or Next as a function call that will return the correct URL.)

function printPageLinksFirstTry(num totalPages, num currentPage)
  if ( currentPage > 1 )
    print "Prev"
  print "1"
  print "..."
  print currentPage - 1
  print currentPage
  print currentPage + 1
  print "..."
  print totalPages
  if ( currentPage < totalPages )
    print "Next"
endFunction

This function works ok, but it doesn't take into account whether we're near the first or last page. Looking at the above examples, we only want to display the ... if the current page is two or more away.

function printPageLinksHandleCloseToEnds(num totalPages, num currentPage)
  if ( currentPage > 1 )
    print "Prev"
  print "1"
  if ( currentPage > 2 )
    print "..."
  if ( currentPage > 2 )
    print currentPage - 1
  print currentPage
  if ( currentPage < totalPages - 1 )
    print currentPage + 1
  if ( currentPage < totalPages - 1 )
    print "..."
  print totalPages
  if ( currentPage < totalPages )
    print "Next"
endFunction

As you can see, we have some duplication here. We can go ahead and clean that up for readibility:

function printPageLinksCleanedUp(num totalPages, num currentPage)
  if ( currentPage > 1 )
    print "Prev"
  print "1"
  if ( currentPage > 2 )
    print "..."
    print currentPage - 1
  print currentPage
  if ( currentPage < totalPages - 1 )
    print currentPage + 1
    print "..."
  print totalPages
  if ( currentPage < totalPages )
    print "Next"
endFunction

There are only two problems left. First, we don't print out correctly for one page, and secondly, we'll print out "1" twice if we're on the first or last page. Let's clean those both up in one go:

function printPageLinksFinal(num totalPages, num currentPage)
  if ( totalPages == 1 )
    return

  if ( currentPage > 1 )
    print "Prev"

  print "1"

  if ( currentPage > 2 )
    print "..."
    print currentPage - 1

  if ( currentPage != 1 and currentPage != totalPages )
    print currentPage

  if ( currentPage < totalPages - 1 )
    print currentPage + 1
    print "..."

  print totalPages

  if ( currentPage < totalPages )
    print "Next"

endFunction

Actually, I lied: We have one remaining issue. When you have at least 4 pages and are on the first or last page, you get an extra page in your display. Instead of "1 2 ... 10 Next" you get "1 2 3 ... 10 Next". To match what's going on at Stack Overflow exactly, you'll have to check for this situation:

function printPageLinksFinalReally(num totalPages, num currentPage)
  if ( totalPages == 1 )
    return

  if ( currentPage > 1 )
    print "Prev"

  print "1"

  if ( currentPage > 2 )
    print "..."
    if ( currentPage == totalPages and totalPages > 3 )
      print currentPage - 2
    print currentPage - 1

  if ( currentPage != 1 and currentPage != totalPages )
    print currentPage

  if ( currentPage < totalPages - 1 )
    print currentPage + 1
    if ( currentPage == 1 and totalPages > 3 )
      print currentPage + 2
    print "..."

  print totalPages

  if ( currentPage < totalPages )
    print "Next"

endFunction

I hope this helps!

---

Related Topics