search

scala / bug

Scala 2 bug reports only. Please, no questions — proper bug reports only.
https://scala-lang.org
232 stars 21 forks source link

Efficient way to find the next smaller element than a given key in a TreeMap/TreeSet #8621

Open scabug opened 10 years ago

scabug commented 10 years ago

Given a Set with elements (10,20,30,40,...) we need to find the next smallest and next largest element (both inclusive), e.g. nextSmallest(25) = 20, nextLargest(25) = 30.

Given a TreeMap this can be quickly done by traversing the tree. Sadly to achieve this in Scala 2.11 you have to copy the code of the TreeMap and RedBlack-classes.

On the other hand the next largest element can now be efficiently found using iteratorFrom introduced by #6642.

There should be a simple way to find the next smallest element, for example by introducing a reverseIteratorFrom.

scabug commented 10 years ago

Imported From: https://issues.scala-lang.org/browse/SI-8621?orig=1 Reporter: Martin Großmann (mgrossmann) Affected Versions: 2.11.0 See #6642