In the first part of this series we looked at a number of ways of sorting the displayed elements without having to sort every item in a (possibly) large list. The final “pivot sort” kept the position of the currently selected element fixed on the display while the rest of the list sorted around it. The code was relatively simple – all of the heavy lifting was done by the standard library with one call to std::partition and two calls to std::partial_sort. There is only one problem – the function doesn’t work for a number of cases.

We can work out what these cases are in a number of ways. One is simply to run a large number of tests – always a good idea when dealing with code like this, however, without having thought through the problem and the special cases we can’t guarantee that we are testing all of the relevant cases. So, let’s look at the original problem statement and see what special cases we can find.

We never had an “official” statement of the problem, but this will do:

Keep the position of the currently selected element fixed on the display while the rest of the list sorts around it.

Are there any circumstances under which we cannot achieve this goal, or are there any circumstances where we can achieve this goal but it will lead to odd results? Here’s one problem case, we keep the selected element in its same place on the display but we end up with several blank spaces at the top of the display. We have achieved our goal, but we are not making the most of the display area (mouse over the image to see the before and after pictures):

We can also imagine a similar problem occurring at the end of the list. These “blanks” can occur for any length list if the selected element ends up close enough to the beginning or end of the list, however if the length of the list is smaller than the number of elements we display this problem is going to occur all of the time. There is also an implicit assumption I’ve been making all along that the selected element is actually on the display when we start to sort. If the element isn’t on display we can apply the same rules (the selected element remains in its same position relative to the display and everything else sorts around it) but it isn’t obvious to me that we’ll get useful results from doing that.

These are exactly the sort of cases we’d expect to need to test – values that are large or small or near some boundary. Several of these cases indicate areas where we need to make a decision – do we allow the list to display fewer elements than it can to keep the selected element in the correct place? What is the right behaviour if the selected element is off the display before the sort starts?

For the purposes of this post I am going to state the the algorithm must always display as many elements as possible (i.e. there will be no blanks on the display unless the total number of elements is less than the number we can display, and even then there must be as few blanks as possible). I will also state that if the selected element is off the top of the display it will end up in the top position on the display, and if the selected element is off the bottom of the display it will end up in the bottom position on the display.

There is another approach we can take that is helpful for this problem. Work our way through the code and see what places in the code might give us unexpected results.

void
sortAroundPivotElementBasic( 
    UInt nDisplayedElements, 
    UInt topElementIndex, 
    UInt pivotElementIndex, 
    Comparator const& comparator, 
    UInt& newTopElementIndex, 
    UInt& newPivotElementIndex,
    FMDVector& files )
{
    FileMetaData const pivotElement( 
        files[ pivotElementIndex ] );

    Iter pivotElementIterator( 
        std::partition( 
            std::begin( files ), 
            std::end( files ), 
            std::bind( comparator, _1, pivotElement ) ) );

The first couple of statements are good (I am assuming that nobody will call the code with pivotElementIndex outside the range of the file vector – if we want to guard against that we can easily add preconditions). Things start to get hairy with the next statement though:

UInt const pivotOffset( 
    pivotElementIndex - topElementIndex );

We are subtracting two unsigned integer values. If pivotElementIndex is smaller than topElementIndex, the result of the subtraction is a very large positive value that is almost certainly unexpected and unwanted. If pivotElementIndex is smaller than topElementIndex it means that the pivot element was above the top of the display – one of the problem cases we have just identified.

Iter displayBegin( pivotElementIterator - pivotOffset );

We know we can’t trust pivotOffset – it might be some extremely large number, however even if pivotOffset has a reasonable value, we do not know for certain that pivotElementIterator - pivotOffset will produce a legal iterator (i.e. one in the range files.begin() to files.end()). Notice that this matches another of the problem cases we identified above – the top element on the display actually comes before the first element in the vector leaving blank lines on the display.

Iter displayEnd( displayBegin + nDisplayedElements );

displayBegin is already suspect, and even if displayBegin is within range we have no guarantee that displayBegin + nDisplayedElements will be in range. displayEnd might end up being past the end of the vector – the “blanks at the end of the list” problem.

newTopElementIndex = displayBegin - std::begin( files );
newPivotElementIndex = 
    pivotElementIterator - std::begin( files );

There is nothing wrong with these two lines if displayBegin and pivotElementIterator are in range. pivotElementIterator is fine, however as we have just seen, displayBegin may well be out of range.

std::partial_sort( 
    pivotElementIterator, 
    displayEnd, 
    std::end( files ), 
    comparator );

We know that pivotElementIterator is good, but displayEnd is suspect.

    std::partial_sort( 
        ReverseIter( pivotElementIterator ), 
        ReverseIter( displayBegin ), 
        ReverseIter( std::begin( files ) ), 
        std::bind( comparator, _2, _1 ) );
}

Again, pivotElementIterator is good, but displayBegin is suspect.

---

There are three iterators that we need to know to perform this sort:

• pivotElementIterator
• displayBegin
• displayEnd

We have seen that pivotElementIterator is easy to get correct, the problem is with the other two iterators. This is what I came up with to get correct values for displayBegin and displayEnd.

void
sortAroundPivotElement( 
    UInt nDisplayedElements, 
    UInt topElementIndex, 
    UInt pivotElementIndex, 
    Comparator const& comparator, 
    UInt& newTopElementIndex, 
    UInt& newPivotElementIndex,
    FMDVector& files )
{
    FileMetaData const pivotElement( 
        files[ pivotElementIndex ] );

    Iter const newPivotElementIterator( 
        std::partition( 
            std::begin( files ), 
            std::end( files ), 
            std::bind( comparator, _1, pivotElement ) ) );

The first two lines stay the same – the only possible errors here can be avoided by the caller.

newPivotElementIndex = 
    newPivotElementIterator - std::begin( files );

The calculation of newPivotElementIndex hasn’t changed, I have just moved it to earlier in the function because I am going to make use of it.

pivotElementIndex = boost::algorithm::clamp( 
    pivotElementIndex, 
    topElementIndex, 
    topElementIndex + nDisplayedElements - 1 );

We fix the problem of the pivot element being off the display by clamping the pivot element’s position to the limits of the display. We do this after we get the value of the pivot element. (Notice that since boost::algorithm::clamp is effectively a combination of std::min and std::max we have to use - 1 for our “end of range” calculation).

UInt pivotOffset( pivotElementIndex - topElementIndex );

Since we have clamped the value of pivotElementIndex we know that the subtraction will not overflow – pivotOffset has a legal value.

pivotOffset = std::min( pivotOffset, newPivotElementIndex );

We clamp pivotOffset to make sure that we won’t run off the beginning of the vector.

Iter displayBegin( 
    newPivotElementIterator - pivotOffset );
newTopElementIndex = displayBegin - std::begin( files );

We know for sure that displayBegin is a valid iterator since we know that pivotOffset is in a legal range.

nDisplayedElements = std::min( 
    nDisplayedElements, 
    files.size() );

Solves any problems caused by having a list shorter than the size of our display.

Iter const displayEnd( 
    files.begin() + 
    std::min( 
        newTopElementIndex + nDisplayedElements, 
        files.size() ) );

displayEnd is now in the correct place, and a legal iterator. Now we can use displayEnd to recalculate displayBegin (yes, we have to calculate displayBegin twice).

displayBegin = std::min( 
    displayEnd - nDisplayedElements, 
    displayBegin );
newTopElementIndex = displayBegin - std::begin( files );

Finally all of our iterators are correct and we can sort the elements.

    std::partial_sort( 
        newPivotElementIterator, 
        displayEnd, 
        std::end( files ), 
        comparator );

    std::partial_sort( 
        ReverseIter( newPivotElementIterator ), 
        ReverseIter( displayBegin ), 
        ReverseIter( std::begin( files ) ), 
        std::bind( comparator, _2, _1 ) );
}

Here’s the function in a single block for clarity:

void
sortAroundPivotElement( 
    UInt nDisplayedElements, 
    UInt topElementIndex, 
    UInt pivotElementIndex, 
    Comparator const& comparator, 
    UInt& newTopElementIndex, 
    UInt& newPivotElementIndex,
    FMDVector& files )
{
    FileMetaData const pivotElement( 
        files[ pivotElementIndex ] );

    Iter const newPivotElementIterator( 
        std::partition( 
            std::begin( files ), 
            std::end( files ), 
            std::bind( comparator, _1, pivotElement ) ) );

    newPivotElementIndex = 
        newPivotElementIterator - std::begin( files );

    pivotElementIndex = boost::algorithm::clamp( 
        pivotElementIndex, 
        topElementIndex, 
        topElementIndex + nDisplayedElements - 1 );

    UInt pivotOffset( pivotElementIndex - topElementIndex );
    pivotOffset = std::min( pivotOffset, newPivotElementIndex );

    Iter displayBegin( 
        newPivotElementIterator - pivotOffset );
    newTopElementIndex = displayBegin - std::begin( files );

    nDisplayedElements = std::min( 
        nDisplayedElements, 
        files.size() );

    Iter const displayEnd( 
        files.begin() + 
        std::min( 
            newTopElementIndex + nDisplayedElements, 
            files.size() ) );

    displayBegin = std::min( 
        displayEnd - nDisplayedElements, 
        displayBegin );
    newTopElementIndex = displayBegin - std::begin( files );

    std::partial_sort( 
        newPivotElementIterator, 
        displayEnd, 
        std::end( files ), 
        comparator );

    std::partial_sort( 
        ReverseIter( newPivotElementIterator ), 
        ReverseIter( displayBegin ), 
        ReverseIter( std::begin( files ) ), 
        std::bind( comparator, _2, _1 ) );
}

I quite like my original function – sortAroundPivotElementBasic. I don’t like the new function nearly as much. Of course, sortAroundPivotElement has the advantage that it works (not something to dismiss lightly) but it lacks Tony Hoare’s quality of being “so simple that there are obviously no deficiencies”. I believe that the code is correct. I have done extensive testing on the function. I worked my way through all of the places in the code where things might be incorrect and made sure that I was doing appropriate checks. Even with all of that I am not convinced of my ability to explain the code correctly (I have done my best with the explanation above but I don’t think that my explanation is perfect).

Of course one possibility is that I am not as good at reading, writing and explaining code as I should be, but even though that’s true, it’s still worth looking at ways to improve sortAroundPivotElement.

The function now obviously splits into three sections (that was always the case, it just wasn’t as clear with the basic version):

1. Calculate the new position of the pivot element
2. Calculate displayBegin and displayEnd.
3. Sort the elements on screen

The calculation of displayBegin and displayEnd is an obvious step to split out into its own function. That would at least keep the main function closer to the core parts of the algorithm, and keep all of the special case handling in a separate function.

I can think of various ways to handle the special cases separately (if the number of elements in the vector is smaller than the number we can display we might just as well sort the entire vector; if the new position of the pivot element is close enough to the beginning or end of the vector to cause a problem we could just use std::partial sort on the beginning or end) but they add the overhead of splitting out the special cases.

Maybe I’ll eventually come up with a better way of calculating displayBegin and displayEnd, in the meantime, we have a function that works.

---

Unsigned integer variables

I made a conscious decision when I wrote this code to avoid integer conversions (implicit or explicit) as much as possible. That lead to my basic integer type being an unsigned type:

typedef std::vector< FileMetaData > FMDVector;
typedef FMDVector::size_type        UInt;

I was able to achieve my goal – there are no implicit or explicit integer conversions. I have a working function where every integer in use is the same unsigned type. Surely this is a good thing?

The basic problem with unsigned integer types is that the model they provide breaks down when you try to set them to a negative value, whether directly or as the result of an operation (such as the subtraction in sortAroundPivotElementBasic) that could overflow.

This has been discussed more than once on comp.lang.c++.moderated:

Discussion 1
Discussion 2

I am opposed to using unsigned integers for arithmetic (rather than bit array) purposes. Every time I have tried to use unsigned integers for quantities that must always be positive (for example, the width and height of a rectangle in a 2D graphics system), I inevitably end up needing to subtract them, and all of a sudden I have overflow problems.

I managed to make an “all unsigned all the time” policy work with sortAroundPivotElement. I am slightly surprised about that because during development I had several problems with overflow. It took some time to come up with a solution where overflow was not a problem.

Even though I managed to get a working solution, I would still change the unsigned ints for signed ints if I was putting this into production code. The function as it stands is fragile. I managed to come up with a solution without overflow, however if someone (and this includes me) has to change the function at a later date (e.g. because we want the special cases to be handled differently) they will have to do a bunch more work to maintain that property (and might fail under circumstances that will, of course, elude all testing and only manifest themselves when a potential customer is evaluating the software).

C++11 makes this easy for us by giving us an easy way to make a signed type out of the corresponding unsigned type:

typedef std::make_signed< UInt >::type Int;

Of course then we will have to convert between integer types since std::vector::size returns an unsigned type. We can moan about this, but it isn’t going to change.