Calculating the contents of fixed size pagination controls
Sunday, February 7 ★ 21:36 ★ Category Programming ★ Permanent url
When a web application needs to display many items, e.g. search results or large lists of records, it is often desirable to chunk the total list of items into equal-sized pages for easy navigation. This process is called pagination. Alternative techniques like continuous scrolling might also be worth considering, but this blog article is just about pagination.
If multiple pages of results are available, navigation links should be displayed on the output pages so that users can browse to other result pages. The list of links is what I call a pagination control. A pagination control could look something like this, where each item is a link to the corresponding page.
previous 1 … 5 6 [7] 8 9 … 15 next
In my examples the active page is shown in square brackets. I also set the display width to 9 (see below). For all examples the total number of pages is assumed to be 15, unless stated otherwise.
Controls like these are quite intuitive to use, and many websites (e.g. search engines) use pagination controls similar to this one, with subtle differences in their implementations. For example, some have ‘first’ and ‘last’ links, some don’t. There are many other choices to make.
Implementing pagination controls like the above seems trivial at first sight, but there are a few corner cases to consider, and it takes some thinking to get all cases right.
Display width
In my implementation, I assume a fixed number of links, so that the resulting output is always has more or less the same size, which I find very useful since the control would look roughly the same on all pages. I use the term display width to denote this value. In the example above the display width is set to 9. The gaps (shown with an ellipsis) are also considered, since those take roughly the same space as the links to the pages. (Optional ‘previous’ and ‘next’ links are not counted.)
A small exception to the fixed display width is that if there are less pages than the display width of the control, the complete list of pages is shown. For example, if there are only 8 pages in total, it looks like this:
previous 1 2 3 4 5 6 [7] 8 next
Note that the display width should be set to an uneven number to ensure a nicely balanced output. (For even display widths, the algorithm favours showing one extra link after the active page, since if a user is making its way through many pages, it is much more likely the user navigates in forward order.)
Which links to show?
The control should always show the active, first and last pages, which make for three items in the list. In the remaining space, the control should show as as much context around the current page as space (defined by the display width) permits.
Gaps within the range of page numbers should be easy to spot to make it clear there are more pages available than the visible links. Gaps should be avoided if possible, so when the active page is close to the first or the last page, the control should try to align the numbers so that only one side of the control has a gap. The example below should clarify this:
[1] 2 3 4 5 6 7 … 15 1 [2] 3 4 5 6 7 … 15 1 2 [3] 4 5 6 7 … 15 1 2 3 [4] 5 6 7 … 15 1 2 3 4 [5] 6 7 … 15 1 … 4 5 [6] 7 8 … 15 1 … 5 6 [7] 8 9 … 15 1 … 6 7 [8] 9 10 … 15 1 … 7 8 [9] 10 11 … 15 1 … 8 9 [10] 11 12 … 15 1 … 9 10 [11] 12 13 14 15 1 … 9 10 11 [12] 13 14 15 1 … 9 10 11 12 [13] 14 15 1 … 9 10 11 12 13 [14] 15 1 … 9 10 11 12 13 14 [15]
So, given these requirements, how to decide which links to show in the pagination control? The problem at hand is defined by three variables: the display width, the total number of pages, and of course the active page.
I wrote an algorithm that (as far as I can see) satisfies all constraints expressed above for all display widths of at least 7, since a display width of less than 7 items does not make any sense — the reason why is left as an exercise to the reader. (Hint: pagination controls are designed for navigating to other pages.) A quite clean Python implementation, which I hereby put in the public domain, can be obtained here:
Download pagination.py
Just run the script to see some example output. Porting this code to other languages should be trivial. Rendering nice XHTML out of the resulting list of numbers is very application-specific and hence left as an exercise to the reader.
With this approach showing back and forward buttons only if appropriate is trivial. If the current page is larger than 1, a ‘previous’ link should be included. Similarly, if the current page is smaller than the number of pages, a ‘next’ link should be shown. ‘First’ and ‘last’ links should not be rendered, since page 1 and the last page are always included in the output and extra links would not offer the user anything that the other links already offer.
Guadec 2010 Call for Volunteers
Tuesday, February 2 ★ 20:15 ★ Category Gnome ★ Permanent url
GUADEC (pronounced GWAH-DECK) is an acronym for the GNOME Users’ And Developers’ European Conference. Held annually in cities around Europe, GUADEC is the largest gettogether of GNOME users, developers, foundation leaders, individuals, governments and businesses in the world. Gnome is the Free and open source software stack that drives the user interface of many Linux-based devices, from smartphones to your home pc.
GUADEC 2010, the eleventh edition, will be in The Hague, The Netherlands and takes place on July 24 – July 30.
The organisation team calls you to arms! A community conference like GUADEC only happens when the community puts its weight behind it.
This is your chance to be part of this event. Whether you are a conference rookie or a seasoned GUADEC veteran, your help is much appreciated.
As a volunteer at the conference, you may enjoy special benefits such as a free and limited edition volunteer shirt and free food and drinks during your volunteering hours.
Weltschmerz and Whisky
Sunday, November 22, 2009 ★ 21:35 ★ Category Photography ★ Permanent url
Self-portrait titled Weltschmerz und whisky, © Wouter Bolsterlee, 2009 (click for large version)
Fascinated by cemeteries
Tuesday, September 15, 2009 ★ 20:41 ★ Category Photography ★ Permanent url
It occurred to me that I have a somewhat morbid obsession: I can’t help but visit each cemetery I encounter when I’m abroad. For instance, a few weeks back I was in Edinburgh and visited three different graveyards in only four days.
By the way, this is where the great empiricist thinker David Hume rests in peace (Calton Hill). Personally, I’m more of a rationalism-oriented Spinozist though.
For some reason I can’t explain burying grounds attract me (especially at night), even though I’m not at all fascinated by death. No, I don’t I have any other morbid hobbies either. I don’t even like horror movies.
Slightly creepy…
Afraid?
Saturday, July 11, 2009 ★ 00:11 ★ Category Gnome ★ Permanent url
Many similar posts are appearing on Planet Gnome. Philip, Jürg, Ryan and others are not afraid of people writing code. But people writing code are scary since they are geeks who do magic things with computers! So…
(Wrt. the Mono discussion this seems to be about: I agree with the other Gnome people who think Mono is not a problem by definition, as some people seem to think.)
The Story of the Wallet
Friday, May 1, 2009 ★ 01:04 ★ Category Misc ★ Permanent url
Please sit back, this is quite a long post.
This afternoon, I got into a train that was about to depart and found myself a quiet place to sit, when I noticed a wallet in the chair right next to me. I was quite sure the owner of the wallet was long gone, since this location was the final destination of that train when it arrived at this terminus station, so everyone had left the train when it arrived. Moreover, the train had been waiting there (mostly empty) for some time already.
This left me with a few options. The worst of all would be to silently pick up the wallet, take out any money and dump it into a garbage bin. People who know me immediately know I wouldn’t even consider acting in such a criminal way. Instead, I committed myself to getting the wallet returned to its owner.
So, I opened the wallet hoping to find a business card or something else containing contact details of the owner. I found an official credit-card sized identity card and some other bank and membership cards. None of the cards or other pieces of paper I found in the wallet contained any phone numbers or addresses though, so I couldn’t phone the owner or someone who might know the owner right away using my cell phone to sort things out.
The wallet also contained a valid two-way train ticket, so I figured the owner would likely live near the departure location. Thinking some more about the train routes and transfers, I also reasoned that it was very likely the owner had lost it a little less than an hour before.
Since I found an ID card, the owner’s identity could be easily established. Delivering the wallet to a police office and having them return it to the owner would have been an excellent choice at this point.
While perfectly acceptable, that would be the easy way. The boring way. No fun for me! So I decided I would try to sort it out myself. If that failed, I could always fall back to delivering the wallet at a police office. (That would take longer for sure, so the owner would likely have blocked all bank accounts and have the id card made invalid. That would be much more hassle for the owner.)
So I took the wallet home, which was in the direction of the departure location of the train ticket I found anyway, so I could only take it closer to the owner. I continued my quest from the comfort of my home, or, more specifically, from the comfort of my home where I could use my internet connection.
Unfortunately, both the owner’s first and last names were very common. The phone book did not yield any useful results: the name is way too common in the area around the departure location printed on the train ticket. I really didn’t feel like calling fifty people. A web search also returned way too much noise to be useful.
Next, I looked through some more cards, all with the same name, but eventually found one that had a completely different name on it. The particular type of card is specific for a certain age group, and it roughly matched the age of the owner of the wallet (identity cards contain the date of birth). So this name was likely the name of a friend of the owner.
This time the full name was very uncommon, so this opened up new possibilities. Using the almighty internet search engines, I quickly arrived at a guest book page on which that name was referenced. From the actual contents I inferred it was highly likely the owner of the website was a family member of the commenter.
Now this was getting me somewhere! Next step: a domain name lookup on the containing website resulted in a phone number, which I promptly called. I mentioned the name and found out the website owner was indeed a family member of the friend of the owner of the wallet (still following, aren’t you?). I explained the situation and was given a mobile phone number… which turned out to be wrong. I called the website owner again and was given the phone number of another family member of the wallet owner’s friend. That family member turned out to know the owner of the wallet as well and could even give me a mobile phone number!
It took me a while, but now I was almost there. Just one phone call to go and I would likely make someone very, very happy. The wallet’s owner picked up the phone, and without introducing myself (well, first name only, read on for why) I explained the situation and how I found him/her. The person had indeed lost a wallet, but seemed slightly surprised to hear a complete stranger offering to return it. I established the person’s identity by asking about full names, date of birth, and color of the bank card. The owner was eager to meet me, so I suggested to meet right away (“that would be great!”). I asked where he/she currently was, and while still on the phone, I checked the train schedules (long live the internet, again) and instructed the wallet’s owner to catch a particular train and meet me at a particular location inside a train station close to my house.
Some time later I was waiting at the meeting point when a train arrived. I recognized the person right away (ID cards feature a photo as well), handed over the wallet to its rightful owner, then suggested him/her to run to catch a particular train back to where he/she was coming from (yes, I also looked that one up in advance). I was given a big, big “thank you so much for everything and all”, said goodbye, and travelled back home with my ego slightly boosted, ehm, well, okay, heavily boosted.
That’s the story. That’s what happened.
Now, a strange observation. The wallet, as I found it at least, did not contain any money, except for some small coins. As I stated before, I inferred that the wallet had likely been left unattended inside that train for almost an hour before I found it. Perhaps there was just no money inside. But it could just as well be that someone else found the wallet in the mean time, took the money, and left it behind. And you know what’s strange? Even though I made a substantial effort to return the wallet to its owner, and I suspect not every person on this earth would do this, I actually felt guilty for a brief moment. Guilty that there was almost no money inside. Guilty for giving back a wallet with no money inside. Guilty for something that I couldn’t possibly know about. Afraid of being falsely accused of taking money out before returning the wallet. (Perhaps I should put some paper money in, just to be sure?)
But immediately after that short moment of completely ungrounded guilty feelings I realised that that would be completely ridiculous. I mean, seriously, what kind of thief would spend a considerable amount of time on returning a lost (not stolen!) wallet to its rightful owner after taking the money from it? Thinking some more about it, I decided it would be wiser not to know at all. So I didn’t ask whether there was supposed to be any money in the wallet when I returned it, and I made sure my encounter with the wallet’s owner was very brief, so that there was no way of bringing this topic up in our little conversation.
Another noteworthy observation. While searching so thoroughly through a stranger’s belongings and personal details, I realised how horribly privacy invading this actually is: identity, age, memberships, bank account details, receipts including time and locations, (secret?) lover’s notes… and it turned out that my two-sentence explanation of the situation prompted people to immediately give out details about their family structure, names, phone numbers, and so on. What if there was no found wallet at all? What if I just made up the story? The virtues of social engineering…
Anyway, that is why I deliberately chose to remain completely anonymous after reading the pieces of paper inside the wallet when scanning for phone numbers or other contact details (which I didn’t find). I didn’t make myself known at all: I only used my first name and turned off caller identification for all phone calls I made.
When the wallet’s owner asked for my mobile phone number so that he/she could call me in case he/she could not find me at the location I specified or if something went wrong with the trains, I simply told him/her not to worry (“trust me, I call you for a reason, I will be there, and I will recognize you”) and that I was certain I would find him/her, and otherwise _I_ would call.
Also note that I do not include any personal details of the wallet’s owner, so nobody will ever find out know who it was. Everything is safely hidden inside my head, and since I do trust myself, I know everything is alright. But in general, perhaps it’s better to leave these things to the police, may I ever get into a situation like this in the future. Think about it. Is it right how I handled this? Is it ethical? I don’t know. I suppose it is. Sort of.
Why write about this in such length, I hear you ask?
I don’t know. I just feel like sharing this with the world. Perhaps I’m just an arrogant person looking for confirmation. Perhaps I am. But then, at least I’m a decent one.
But the real reason is that it gave me a really noble feeling while doing all these things, knowing that someone I didn’t even know would be very happy about it. It cost me quite some time (searching and looking this up on the web, getting to the station and back) and also some money (for the phone calls, though this is negligible), and I got absolutely nothing in return, as intended. Happiness is in the doing good itself, and not a result of it. As my hero Baruch de Spinoza puts it: beatitudo non est virtutis praemium, sed ipsa virtus, but let’s not get too philosophical here… this post is already way too long.
Enough pondering for now. Nothing is ever simple. If you made it this far, thanks for reading.
Greyscale Xorg
Tuesday, March 10, 2009 ★ 02:06 ★ Category Linux ★ Permanent url
Colour is highly overrated, so let’s get rid of that new-fashioned nonsense and return to the good old days of greyscale computer screens!
It’s really easy: in your xorg.conf, add DefaultDepth 8 to the Screen section, and within that section, add Visual "StaticGray" to SubSection "Display".
Now, after restarting X, you will not be distracted by colours anymore: everything will be neatly desaturated.
Bashing Bazaar again?
Wednesday, February 25, 2009 ★ 21:49 ★ Category Gnome ★ Permanent url
Dear Lennart,
It’s not my intention to start another flame war, but your blog post about bzr clearly shows that your real intention was not to obtain source code, but to bash bzr. I’ll explain why.
Simply visiting the the url http://www.mega-nerd.com/Bzr/libsndfile-pub/ with your web browser gives a 404 Not Found error message. That’s quite clear, so it’s not very likely there will be a branch there, right?
Spending a complete flame on your experiments with many different Bazaar commands, while the instruction page you linked to exactly tells you how to proceed, is not justified in my opinion. Especially not if you’re looking for help, and the very top of the bzr man page contains this:
SYNOPSIS
bzr command [ command_options ]
bzr help
bzr help command
Yes, there’s help in there. And you also mention that in your own blog post, so there is no point in complaining about man pages, or trying the totally non-obvious man bzr-get and concluding that there is no help at all.
So, given that the url is dead (well, not found to be precise), how would you proceed from here? You’re tech-savvy, and you know how file systems work, and you probably know how the web works. So you could’ve tried visiting the parent url by cutting off the trailing part of the address. You would’ve ended up on http://www.mega-nerd.com/Bzr/, whichs contains a link to the right address that happens to work flawlessly:
$ bzr branch http://www.mega-nerd.com/Bzr/libsndfile-cue/ Branched 1046 revision(s).
The way you’ve written your blog post is highly insinuating and not helpful to anybody at all. You’ve written many very good blog posts in the past, so please keep it like that and refrain from spreading uninformed nonsense in the future. Thank you.
No love (well, not until you fix libsndfile…),
— Wouter
P.S. I’ll leave it to you to make the author of the instruction page aware of the incorrect url. You’re a good net citizen after all, aren’t you?
P.P.S. The in mano in your web page title should be in manu, since that is how manus is inflected in Latin.
MySQL last insert id performance issues
Wednesday, February 25, 2009 ★ 17:39 ★ Category Programming ★ Permanent url
After suffering from severe performance problems for a rather data intensive application (which was explicitly designed with scalability in mind), the culprit was found: a often executed piece of code did not execute SELECT LAST_INSERT_ID(), but SELECT LAST_INSERT_ID() FROM some_table. Hard to spot, but very important.
The problem? Well, the LAST_INSERT_ID (see the MySQL manual on LAST_INSERT_ID) function just returns the resulting primary key value from the last INSERT statement in the current MySQL connection thread, regardless of the table into which the row was inserted. Erroneously appending FROM some_table to this statement will result in a query that returns rows from a table, and these rows only contain the same constant value over and over again, once for each row in the table. However, if you only retrieve one row from the result set, you won’t initially notice the bug… at least not until your application mysteriously gets slower. If the table grows significantly over time, which was clearly the case here, since many records are inserted every day, executing this very simple query will become slower and slower, since it returns as many rows as are in the table, and each subsequent row yields exactly the same information as the previous one. How much slower? Well, up to the point that multiple quad core machines with plenty of memory were constantly suffering from such a high load that they became almost unresponsive. Yes, we were running this piece of code many times in parallel since it is supposed to be not CPU bound, but network latency bound.
The solution? Well, a very easy fix: after dropping the FROM some_table part from the query the load on the machines instantly dropped back to almost 0, which was how this applications was designed since it’s mostly network latency bound, which does not use much resources other than occupying some file descriptors for open sockets.
The lesson learnt here? A speed-up of many orders of magnitude, just by removing two words in the code… yes, sometimes performance optimization is completely in the nitty-gritty details. Unfortunately we had to find out the hard way.
(Yay for the person who found this. You know who you are.)
Fishy audio metadata
Saturday, February 14, 2009 ★ 19:48 ★ Category Misc ★ Permanent url
I’m delighted to find out that both FLAC and ID3v2 explicitly have support for the only picture type that really matters, namely that of a bright(ly) coloured fish. Both the ID3v2 specification (section 4.14) and the FLAC format specification (see METADATA_BLOCK_PICTURE) reserve picture type 0x11 for a picture of a fish. Though one can also embed pictures in Ogg/Vorbis, the Ogg Vorbis Comments specification does not explicitly list it, but to make up for this omission that page displays a colored fish (the Xiph logo) on the top of the page.
Is it just me, or is something fishy going on here?
Update: One of my gentle readers pointed out that it’s probably a red herring...
Want more? Feel free to browse my archives (see right column) or use the category labels for more posts on similar topics.
Random photo from Turkey (May, 2005)
Who wrote all this?
Wouter Bolsterlee, also known as uws, a postmodern geek living in the Netherlands. Read more about me…
Stay informed
Blog archives
Copyright
Unless stated otherwise, all material on this site is available under a Creative Commons Share-Alike license.