Maintaining Scrollbars in Document Editing Applications

Introduction 

When coding a document editor of any kind, programmers almost always face the problem of managing scrollbars. In general, we start with a data structure referred to as a document, which represents the contents of a document, rather than its visual representation on the screen. It is up to the application to convert that representation into visual elements and to draw them within the bounds of an appointed part of the screen.

In this article one specific class of visual representations of the document will be covered. As a matter of fact, it is a quite common class in practice. Most of the document editors work in that manner: text editors, graphics editors, many editors for mixed text with graphics, etc. Consequently, the solution presented in this article is generally useful and applicable to different editors that you might develop.

We will start with the document view which has a structure like the one shown in the next picture.



The document is presented as a vertical stream of row-like objects, each object being a line of text, an image, a table, etc. All objects are viewed as left-aligned - if indented, that indentation is performed within the bounding rectangle and the rectangle's width is increased by the indentation width. For example, if the image is centered, then it is treated as being indented by an amount which is calculated from the total width of the sheet and width of the image. Also, the sheet has four margins along the edges that must be taken into account when calculating its dimensions. If items (rows of text, etc.) have spacing above or below then that spacing is also included in the row's height.

With these considerations, most of the document editors imaginable can be implemented by cutting the document contents into objects called rows, and by specifying size (width and height) for every row. Once done, what we need to do next is to draw the document on the screen. Hence, the scrolling comes in, and the result is shown on the picture below.



Here in the center of the picture is the content shown on the application window. The rectangle containing the visible part of the document is accompanied by horizontal and vertical scrollbars that can be used to scroll other parts of the document into view.

Further on we will show how to control scrollbars, i.e. how to calculate their attribute values based on the actual document content and its screen representation. That task must be performed carefully in order to make the editor responsive and fast, in addition to being accurate.

Scrollbars Attributes

When looking at the scrollbar and the document being scrolled, we can notice the elements shown on the following picture.



What we are interested in are the values of these attributes:

• Maximum - total width of the document including left and right margin (D on the picture).
• Minimum - always set to zero as we have previously left-aligned all rows.
• LargeChange - equals width of the viewport (termed V on the picture).

Once these attributes are set, the scrollbar shown on the screen would have such proportions that thumb width (T) compares to scroll length (S) in the same proportion as viewport width (V) compares to total document width (D):

                                                    

So we just have to determine the width of the document and everything else is readily available. Exactly the same analysis stands for the vertical scrollbar - we only need to know the height of the document and the scrollbar will be drawn correctly.

At this point we are ready to present formulas that can be used to determine attribute values both for horizontal and for vertical scrollbar, as follows.

Attributes of the horizontal scrollbar are calculated as:

• Minimum - always zero.
• Maximum - sum of left and right margin, plus the maximum width of any row object.
• SmallChange - arbitrary decision; for example, we can make it equal to the average character width in the font used to draw text in the document presentation.
• LargeChange - equal to the width of the rectangle within which the document is drawn on the screen; typically the width of the client rectangle of the control used to draw the document (e.g. panel).
• Value - X coordinate of the point in the document which is drawn in the upper left corner of the viewport.
• Enabled (or Visible) - true if the viewport width is smaller than the document width (i.e. horizontal scrollbar's LargeChange is smaller than Maximum value); this ensures that the scrollbar is disabled (or hidden if Visible attribute is used) when the document is narrow enough to fit horizontally within the appointed viewport without need to scroll it.

Attributes of the vertical scrollbar are calculated as:

• Minimum - always zero.
• Maximum - sum of the top and bottom margin, plus the sum of heights of all row objects in the document.
• SmallChange - arbitrary decision; for example, height of one row of text drawn on screen.
• LargeChange - equal to the height of the rectangle within which the document is drawn on the screen; typically the height of the client rectangle of the control used to draw the document (e.g. panel).
• Value - Y coordinate of the point in the document which is drawn in the upper left corner of the viewport.
• Enabled (or Visible) - true if the viewport height is smaller than the document height (i.e. vertical scrollbar's LargeChange is smaller than Maximum value); this ensures that the scrollbar is disabled (or hidden if Visible attribute is used) when the document is short enough to fit vertically within the appointed viewport without need to scroll it.

Efficiency Considerations

Scrollbar attributes evaluation must be as fast as possible because those values may be frequently changed. It is easy to notice that horizontal scrollbar maximum attribute value is the bottleneck of all operations because it includes the maximum function. That is not an analytical function and cannot be calculated instantly, so this attribute might require a long time to calculate from an exceptionally large document (and the programmer must always keep in mind a possibility that the application will actually be used to edit an exceptionally large file). A typical case when this property calculation may be a source of a trouble is when the user places the caret at the end of the longest line in a huge document and then presses and holds the backspace key. With each new occurence of the key press event, one letter should be deleted from the back of the longest line. This means that several times per second we need to determine the next maximum length over all rows in the document. If the document contains millions of rows, then we are really in trouble; any of those rows may be the next maximum.

As a result, a more efficient way other than simple row traversal must be devised to calculate the maximum width of all rows in the document. One solution is, as always, caching. We can remember the widths of all rows in the document in a specific data structure. But that structure would not remember widths of rows directly, but it would rather group rows of the same width and count them. As a matter of simplicity, we can imagine an array of elements with indexes 0 thru N for rows that have at most N pixels in length. On every position W inside that array, a non-negative integer would be stored representing the total count of rows having a width equal to W pixels when drawn on the screen.

This structure must be efficient on the following operations:

• Add row with width W - if element with value W does not exist, then it is inserted with a count equal to one; if such an element exists, it is incremented by 1.
• Remove row with width W - find the element with a value W and decrease it; if equal to zero (after being decreased), the element is removed from the structure.
• Find maximum - structure must be somehow ordered so that finding the maximum value from it is fast.

The final solution proposed in this article is to use a SortedDictionary collection to count each row length. The key to the stored elements would be the negative width of the row. We must change the sign of the row width because SortedDictionary sorts data in ascending order; hence if we insert negative values as keys, then the values will effectively be sorted in descending order. Any stored value would be the total number of rows that have a width indicated by the corresponding key. Finding the maximum from this collection now means to pick the first key from its Keys collection and to negate it to recover the original row length.
Using SortedDictionary to help calculate the maximum function is very efficient. Adding and removing an element from it has O(logN) complexity. Reading the maximum row length by reading the first key from the Keys collection has O(1) complexity.

Retrieving the minimum key value from the SortedDictionary can be implemented using its GetEnumerator method like in the following piece of code.

SortedDictionary<int, int> lengthToCount= new SortedDictionary<int, int>();
...
int min = 0;
using (SortedDictionary<int, int>.Enumerator en = lengthToCount.GetEnumerator())
{
    if (en.MoveNext())
        min = en.Current.Key;
}

Conclusion
In this article we have shown that scrolling must be planned in full detail before coding complex applications. It is not a hard task, but analysis must anyway be performed in order to determine how and when the scrolling-related attributes will be reevaluated.

Another message emphasized by this article is that scrolling should be treated as a potential bottleneck in the application in the case where an underlying document grows large. The point at which many applications fail is when the user attempts to edit an unexpectedly large document using the application. In that case many bottlenecks become quite visible, and an inability to calculate scrolling ranges in real time may be one of them if scrolling is not treated correctly.

The problem of finding minimum and maximum values over the changing set of numerical values has been pushed further in next article titled Efficient Implementation of Minimum and Maximum Functions with Application in GUI Design. In that article we are giving complete workable solution to the problem, with examples in GUI design.