Iterate over the reverse of a sorted set in Scala?

Question

I have a mutable SortedSet and I can iterate over it by doing for (item <- nameOfMySortedSet). However I would like to be able to do the same thing, but over the reverse of nameOfMySortedSet. I do not seem to see a reverse() option for this datatype? Is there another way to do this?

Answer 1

A solution,

val sSet = SortedSet(4,3,5)
sSet.foldLeft(List[Int]())((x,y)=>y::x)

If you have to do this too often, you may have to save Set in the reverse order. Use a different Ordering.

Answer 2

You can try building a new SortedSet with the ordering reversed:

scala> val mySet = collection.mutable.SortedSet("1", "2", "3")
mySet: scala.collection.mutable.SortedSet[String] = TreeSet(1, 2, 3)

scala> collection.mutable.SortedSet(mySet.toSeq:_*)(mySet.ordering.reverse)
res0: scala.collection.mutable.SortedSet[String] = TreeSet(3, 2, 1)

Or you can just convert it to a list or seq and run the reverse:

scala> mySet.toSeq.reverse
res1: Seq[String] = ArrayBuffer(3, 2, 1)

Answer 3

The following works, but I would not want to defend it as efficient:

  val s = collection.SortedSet(1,3,4)
  for (i <- s.to[List].reverse)
    println(i)

Answer 4

Most of the times we need just the last few elements, that's what iterators are for. There's another way without folding over all the elements or constructing a new SortedSet instance altogether.

We can have a reverse iterator, that goes over from the last picking each element one by one with log(n) complexity every next invocation.

The following is an optimised implementation for the same.

object SortedSetExtras {

  implicit class ReverseIterator[A](val set: mutable.SortedSet[A]) extends AnyVal {

    def reverseIterator: Iterator[A] = new Iterator[A] {
      var upNext: Option[A] = None
      var upNextComputed: Boolean = false

      private def recompute(): Unit = {
        if (!upNextComputed) {
          upNext = upNext match {
            case Some(value) => set.until(value).lastOption
            case None => set.lastOption
          }
          upNextComputed = true
        }
      }

      override def hasNext: Boolean = if (upNextComputed) upNext.nonEmpty else {
        recompute()
        hasNext
      }

      override def next: A = {
        if (upNextComputed) {
          upNext.foreach(_ => upNextComputed = false)
          upNext.get
        } else {
          recompute()
          next()
        }
      }
    }
  }
}

Actual usage-

import SortedSetExtras._

val ts = mutable.TreeSet[Int](1, 2, 3, 8, 9)

println(ts.reverseIterator.mkString(", ")) // 9, 8, 3, 2, 1

Note: the above implementation is not thread safe.