SortedSet maxBefore / minAfter break for reversed orderings

[swaldman]

Hi!

I observed this behavior first in Scala 3.2.1, then checked 2.13.10. The (mis)behavior is the same.

Here's a standalone for scala-cli:

//> using scala "2.13.10"

import scala.collection._

object Test {
  val orderingNormal  = implicitly[Ordering[String]]
  val orderingReverse = orderingNormal.reverse

  def main( args : Array[String] ) : Unit = {
    val ssn = immutable.SortedSet("a","b")( orderingNormal )
    println("normal max-before-a  (expect None):    " + ssn.maxBefore("a") )
    println("normal min-after-a   (expect Some(b)): " + ssn.minAfter("a") )

    val ssr = immutable.SortedSet("a","b")( orderingReverse )
    println("reverse max-before-a (expect Some(b)): " + ssr.maxBefore("a") )
    println("reverse min-after-a  (expect None):    " + ssr.minAfter("a") )
  }
}  

Here is the output:

normal max-before-a  (expect None):    None
normal min-after-a   (expect Some(b)): Some(a)
reverse max-before-a (expect Some(b)): Some(b)
reverse min-after-a  (expect None):    Some(a)

My expectation is that with a normal ordering, max-before "a" from sorted set ("a","b") would be None, and min-after "a" would be Some(b). And, hooray! That's what happens.

My expectation with a reverse ordering is that max-before "a" would be Some(b), and min-after "a" would be None. Alas, that's not what happens. min-after "a" is Some(a) rather than None.

min-after "a" itself yielding "a" strikes me as violating an invariant that these functions should never return their own input (at least for orderings that are complete).

Thank you for all of your work!

[odd]

If you check the documentation of minAfter it states that it returns an option containing the smallest element larger than or equal to a given key (or None if there is no such element). One way to avoid the equal to constraint is to make sure you always adjust the keys to be one step larger. For strings this can be done by always appending Char.MinValue to the key before usage:

set.minAfter(key + Char.MinValue)

I agree that the current behavior is surprising and would prefer a non-inclusive comparison for the minAfter (as is the case for maxBefore).

[swaldman]

Thank you for the reply!

I do find this behavior surprising. Unfortunately, in my real case I'm working with more complexly ordered entities than Strings, so there's not so convenient an epsilon-above to work with.

I have an item, which I know is in the set. I wish to get the item before and after my item. This looked like the right API to use, but now maybe not. Probably something like rangeFrom(...).tail.headOption is my best bet?

Anyway, thank you again for the quick reply! Probably I should close this issue. A documented API, however surprising, doesn't qualify as a bug.

[SethTisue]

fyi @scala/collections

[som-snytt]

This came up somewhere not very long ago (I haven't found it yet), so it may warrant special documentation intervention.

Because my car requires me to dismiss a "disclaimer" popup on the console on every (re-)start, or just not use the radio for a minute, I was going to joke that scalac could display a modal "Have you read the CoC?" before continuing.

sbt could detect first compilation of minAfter usage and ask "Have you read the Scaladoc?" or even, "Are you aware and agree that the Scaladoc says...".

Note that if the radio was previously on, even the physical knob does not work to turn off the audio until the disclaimer is dismissed.

[odd]

Perhaps an overload with an extra boolean parameter signaling whether to use inclusive or exclusive comparison could be added to SortedSet:

def minAfter(key: T): Option[T] = minAfter(key, false)
def minAfter(key: T, exclusive: Boolean): Option[T] = ...

and analogous for maxBefore (inverted since the current behavior is exclusive):

def maxBefore(key: T): Option[T] = maxBefore(key, false)
def maxBefore(key: T, inclusive: Boolean): Option[T] = ...

But I fear such a change will not fly past MiMa (I really should read up on the rules of the game).