/* NSC -- new Scala compiler * Copyright 2005-2007 LAMP/EPFL * @author  Martin Odersky */// $Id: TreeSet.scala 12005 2007-06-13 12:28:07Z michelou $package scala.tools.nsc.util/** Sets implemented as binary trees. * *  @author Martin Odersky *  @version 1.0 */class TreeSet[T >: Null <: AnyRef](less: (T, T) => Boolean) extends Set[T] {  private class Tree(val elem: T) {    var l: Tree = null    var r: Tree = null  }  private var tree: Tree = null  def findEntry(x: T): T = {    def find(t: Tree): T = {      if (t eq null) null      else if (less(x, t.elem)) find(t.l)      else if (less(t.elem, x)) find(t.r)      else t.elem    }    find(tree)  }  def addEntry(x: T) {    def add(t: Tree): Tree = {      if (t eq null) new Tree(x)      else if (less(x, t.elem)) { t.l = add(t.l); t }      else if (less(t.elem, x)) { t.r = add(t.r); t }      else t    }    tree = add(tree)  }  def elements = {    def elems(t: Tree): Iterator[T] = {      var it = Iterator.single(t.elem)      if (t.l ne null) it = elems(t.l) append it      if (t.r ne null) it = it append elems(t.r)      it    }    if (tree eq null) Iterator.empty else elems(tree)  }  override def toString(): String = {    if (tree eq null) "<empty>" else "(..." + tree.elem + "...)"  }}