raw math

I have already devoted two articles to the topic of Pagination, one for the jQuery Pagination plugin and the other one on how to optimize MySQL queries for pagination. I'd like to add another one for the mathematical derivation, I used there.

Calculating the number of pages \(l\) needed for \(n\) elements is quite simple, given the number of elements \(p\) which can be displayed on every page:

\[l = \left\lceil\frac{n}{p}\right\rceil\]

I wanted a bit more. When I display the first, say, \(p=10\) elements on the first page, I wanted to add an option to say "show the last element and 9 more elements" on the second page. On the third page this would be the last element of the second page and 9 other elements and so on. I generalized this principle and called it "lapping". The lapping offset \(o\) is the number of elements to show on the current page, which were visible on the previous page already. Of course it must hold that \(o<p\). Let's analyze the whole thing a bit:

PageLast element on page
\(1\)\(p\)
\(2\)\(2p-o\)
\(3\)\(3p-2o\)
......
\(k\)\(kp-(k-1)o\)
\(k+1\)\((k+1)p-ko\)

Page \(k+1\) is the last page and page \(k\) the second last. With this information it's possible to construct a requirement for the number of elements \(n\):

\[\begin{array}{rl} & kp-(k-1)o<n\leq(k+1)p-ko\\ \Leftrightarrow & k(p-o)+o<n\leq k(p-o)+p\\ \Leftrightarrow & \frac{n-p}{p-o}\leq k<\frac{n-o}{p-o}\\ \end{array}\]

It follows that

\[k = \left\lceil\frac{n-p}{p-o}\right\rceil\]

The first element of page \(k+1\) is \(kp-ko+1\) and the i-th element is therefore \(kp-ko+i\). From the condition \(kp-ko+i=n\) follows that the number of elements \(i\) on the last page is

\[i=n-k(p-o)\]

Finally, for the number of pages including lapping follows

\[l=1+k = 1+\left\lceil\frac{n-p}{p-o}\right\rceil\]

It's astonishing that the equation with lapping differs only slightly, compared to the simple number-of-pages calculation from the beginning.

We know everything to print a paginator. We could simply loop from 1 to \(p\) and highlight the current page \(m\). However, when serving thousands of pages, it would blow the website. More practical is the definition of a fixed width \(w\) of paginator elements to be displayed. Another addition I wanted is being able to say what the central element \(c\) is on the paginator. Click through these three examples generated by the jQuery plugin to get a feeling for what I mean with central element:

All have a different center. Printing the paginator with these requirements is then looping from \(s\) to \(t\):

\[\begin{array}{rl} s &= max(1, min(m - c, l - w) + 1)\\ t &= min(s + w, 1 + l) \end{array}\]

As I wanted the configuration of jQuery Paging to be more intuitive, I defined a format-string, like "< nncnn>", meaning "print prev- and next-buttons as well as a block of 5 numbers with the central element at place 3". Parameter \(w\) is the length of the "nncnn" block and \(c\) the position of the "c" character in the block.