A straightforward BST based Iterable immutable persistent data structure. Useful if the need for duplicates prevents use of scala.collection.immutable.SortedSet

OrderedIterable.scala

import cats.Show

import scala.collection.immutable._
import scala.collection.AbstractIterator
import OrderedIterable.{Nill, Node}

sealed abstract class OrderedIterable[+A] extends Iterable[A] {

  def apply(i: Int): A

  def +[B >: A](element: B)(implicit ordering: Ordering[B]) = insert(element)
  def insert[B >: A](element: B)(implicit ordering: Ordering[B]): OrderedIterable[B]

  def insertAll[B >: A](elements: IterableOnce[B])(
      implicit ordering: Ordering[B]) = {
    var result: OrderedIterable[B] = this
    val it = elements.iterator
    while (it.hasNext) {
      result = result.insert(it.next())
    }
    result
  }

  def remove(i: Int): OrderedIterable[A]

  def iterator: Iterator[A] = new AbstractIterator[A] {
    private[this] var current: Iterable[A] = toIterable
    def hasNext = current.nonEmpty

    def next() = {
      val n = current.head
      current = current.tail
      n
    }
  }

  override def isEmpty = this.length == 0

  override def head = this match {
    case Node(v, Nill, _) => v
    case Node(_, l, _)    => l.head
    case Nill             => ???
  }

  override def tail: OrderedIterable[A] = this match {
    case Node(v, Node(_, Nill, r2), r) => Node(v, r2, r)
    case Node(_, Nill, r)              => r
    case Node(v, l, r)                 => Node(v, l.tail, r)
    case Nill                          => Nill
  }

  override def last = this match {
    case Node(v, _, Nill) => v
    case Node(_, _, r)    => r.last
    case Nill             => ???
  }

  def length: Int

  override def knownSize = length

  def pretty(level: Int = 0): String
}

object OrderedIterable {

  implicit def show[A: Show] = new Show[OrderedIterable[A]] {
    def show(t: OrderedIterable[A]) =
      t.map(Show[A].show(_)).mkString("OrderedSeq(", ", ", ")")
  }

  case class Node[+A](value: A, left: OrderedIterable[A], right: OrderedIterable[A])
      extends OrderedIterable[A] {

    def apply(i: Int): A =
      if (i < left.length) left(i)
      else if (i == left.length) value
      else right(i - left.length - 1)

    val length = left.length + right.length + 1

    def insert[B >: A](element: B)(implicit ordering: Ordering[B]) = {
      def insl = Node(value, left.insert(element), right)
      def insr = Node(value, left, right.insert(element))
      if (ordering.lt(element, value)) insl
      else if (ordering.gt(element, value)) insr
      else if (left.length <= right.length) insl
      else insr
    }

    def remove(i: Int) =
      if (i < left.length) Node(value, left.remove(i), right)
      else if (i > left.length)
        Node(value, left, right.remove(i - left.length - 1))
      else
        this match {
          case Node(_, Nill, Nill) => Nill
          case Node(_, l, Nill)    => l
          case Node(_, Nill, r)    => r
          case Node(_, l, r) if left.length > right.length =>
            Node(l.last, l.remove(l.length), r)
          case Node(_, l, r) => Node(r.head, l, r.tail)
        }

    def pretty(level: Int) =
      (left.pretty(level + 1) +: "\n" +: List.fill(level)("-") :+ value.toString :+ "\n" :+ right
        .pretty(level + 1)).mkString
  }

  case object Nill extends OrderedIterable[Nothing] {
    override val iterator = Iterator.empty

    def apply(i: Int) = ???
    val length = 0

    def insert[B >: Nothing](element: B)(implicit ordering: Ordering[B]) =
      Node(element, Nill, Nill)

    def pretty(level: Int) = (List.fill(level)("-") :+ "Nill").mkString

    def remove(i: Int) = Nill
  }
}