One of my tasks at work was to prototype and then create a quality e-books reader for all mobile platforms. I must say that the end result is even better than I thought. Generally, a great challenge in an e-books reader, which is not obvious at first glance, is to provide the smoothest experience possible. There are many functionalities, which seem initially trivial, but are definitely complex if we want to keep the smooth experience. Such functionalities are pages browsing (especially on a chapter edge), changing the font size or changing the device orientation. It is the best if a user doesn’t even notice them. It is definitely bad if a progress bar appears for many seconds when a user increases the font size or accidentally switches the device orientation. It is even worse if a user looses a context within the book (e.g. the first sentence of a page disappears or moves to the bottom of a page) by changing orientation or font. We can group readers by how well they preserve a context during such operations.
Most reader apps are based on an internal mobile device browser for rendering chapters and pages (e.g. UIWebView for Apple and WebView for Android). The least precise readers (e.g. Monocle and probably Google Books) would move the first sentence of a page around. Those readers are usually based on CSS3 multi-column layout. Although it is the easiest way, it introduces many problems such as the delay (even few seconds) imposed by columnizing all content within a chapter whenever the orientation or the font changes.
The more advanced readers (I think Kindle app does that) would most likely render an entire chapter as a one big vertical page and then scroll to a y position of the beginning of a current page. They would also clip a content on the bottom of a page that does not fit entirely on the page. This approach should be faster since CSS3 multi-column is quite slow. Those readers have a single line accuracy which means that the first word of a page should still be visible in the first line of the page after the orientation or the font changes. The drawback of this approach is that special algorithms which compute where the page begins or ends must be implemented.
The most advanced solution (e.g. our solution and also Kindle on some devices) would always keep the first word of a page preserved whenever the font or the orientation changes. This way the user doesn’t get confused and has the best experience. However this requires implementing additional algorithms for accurate pages displaying. The big advantage of such fine grain control over pages rendering is that the performance of such reader is stunning. I think that we have managed to create one of the best and fastest readers in the market. You can see screencast from the app below (with comparison to Google Books):
or you can try using it yourself by installing Audioteka app.
For my warm up post I would like to present a small and simple (hopefully) red-black tree implementation. In my other project: AdblockTV, which I will also describe in future posts, I required an extensible balanced tree implementation that would support data structure enrichment. I checked open source libraries like guava, but I found it to be an overkill to include an entire library for just a single functionality in a relatively compact project (also guava didn’t had RangeMap class by that time). Additionally, I wanted to have a swiss knife tree implementation that I could easily enrich whenever required and writing one would be fun too. Therefore I ended up creating RedBackTree and IntervalTreeMultiSet classes. Sources can be downloaded from here.
The idea of RedBlackTree class is that it provides basic tree methods:
which operate on a tree composed of Node objects. Classes providing tree functionality must derive from the RedBlackTree class and implement own access methods. For example add(K elem) method in RedBlackTreeSet is coded below:
They return Nil and Root nodes of the tree respectively.
Now, if one wants to enrich a standard red-black tree with additional data, one must derive from the RedBlackTree class. In addition, one has to define an embedded class (e.g EnrichedNode class), which derives from the RedBlackTree.Node class. Having those, one can write own access methods, which would take advantage of a balanced tree structure just like it has been done in the IntervalTreeMultiSet class. However, there are few RedBlackTree.Node methods that may need to be implemented in the example EnrichedNode class:
Those methods should update enriched node data based on data from child nodes. Additionally, updatePath() should also call updateSingle() on parent nodes up to a root. Those methods are called whenever a tree structure changes and do nothing by default since we don’t want to waste CPU cycles. The reason why there are three update methods is that in a red-black tree it is not always necessary to update an entire path up to a tree root. Depending on enriched node data and operation type (e.g. nodes rotation) it might be sufficient to update just a single node and not the entire path upwards. For example, when in an IntervalTreeMultiSet instance a node is rotated with its parent, it is enough to update just that node min and max values (and not top nodes), because total min and max values in a subtree do not change. For more references, I recommend checking the IntervalTreeMultiSet itself (it is well documented). A nice feature of that class is that it supports both inclusive and exclusive intervals.
Hi everyone, I have finally started my own tech blog. I have decided that the things that I have done in the past as well as the things that I am doing currently are, in fact, very interesting. In my opinion it would be a waste to just have this experience and not share it with anyone. Additionally, I will feel more comfortable knowing that I can always peek here to check out challenges and ideas that I have been dealing with in the past. Hope that readers will enjoy it too!