Guards/Supremums in LoserTree

[manpen]

Insertion-related functions in the LoserTrees expect a pointer to the the key keyp to be inserted and a sep flag marking it as a supremum. Iff it's a supremum, the pointer has to be nullptr (enforced by a number of asserts)

This design is redundant and actually causes an error in the upcoming STXXL version (bingmann/stxxl@3cf9b69) where a pointer to an arbitrary element is passed. Also, in the unguarded tree variants (which are intended as a drop-in replacement for the guarded tree??), there is an assert(sup == (keyp == nullptr)); which will go through in case a sentinel/nullptr pair gets passed. The function then will continue to dereference the nullptr.

I see a few possible solutions:

• Introduce two variants of each insertion-related function; one for real values and one for sentinels. This might even allow for less runtime checks, but -of course- breaks compatibility with existing code. The user-code then has to explicitly decide which method to use, but in case of the STXXL, this is already the case, since there's an if testing whether nullptr/true or value/false gets passed. (In this case, we might want to remove the sep-inserts in the unguarded which will give compile-time checks that in fact the correct tree-design is used)
  The changes to the STXXL seem doable, is there other code we will break?

• Remove sup as sup = (keyp == nullptr)

• Be more verbose about the sup parameter, and improve assertions