Eliminating unnecessary data structures.

10 files changed, 13 insertions, 301 deletions

diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
index 5f2b5c76c8..71f8287a42 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
@@ -8,7 +8,8 @@
 
 package scala.tools.nsc.ast.parser
 
-import scala.tools.nsc.util.{ListBuffer, Position, OffsetPosition, NoPosition, BatchSourceFile}
+import scala.collection.mutable.ListBuffer
+import scala.tools.nsc.util.{Position, OffsetPosition, NoPosition, BatchSourceFile}
 import symtab.Flags
 import Tokens._
 
diff --git a/src/compiler/scala/tools/nsc/transform/Constructors.scala b/src/compiler/scala/tools/nsc/transform/Constructors.scala
index 9bccf5c95f..7e15e4f0e4 100644
--- a/src/compiler/scala/tools/nsc/transform/Constructors.scala
+++ b/src/compiler/scala/tools/nsc/transform/Constructors.scala
@@ -6,9 +6,8 @@
 
 package scala.tools.nsc.transform
 
-import scala.collection.mutable.ListBuffer
+import scala.collection.mutable.{HashSet, ListBuffer}
 import symtab.Flags._
-import util.TreeSet
 
 /** This phase converts classes with parameters into Java-like classes with
  *  fields, which are assigned to from constructors.
@@ -210,7 +209,7 @@ abstract class Constructors extends Transform {
       // ----------- avoid making fields for symbols that are not accessed --------------
 
       // A sorted set of symbols that are known to be accessed outside the primary constructor.
-      val accessedSyms = new TreeSet[Symbol]((x, y) => x isLess y)
+      val accessedSyms = new HashSet[Symbol]
 
       // a list of outer accessor symbols and their bodies
       var outerAccessors: List[(Symbol, Tree)] = List()
diff --git a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
index 38be297d4c..e62bdba3be 100644
--- a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
+++ b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
@@ -8,8 +8,7 @@ package scala.tools.nsc.transform
 
 import symtab._
 import Flags._
-import util.TreeSet
-import scala.collection.mutable.{HashMap, ListBuffer}
+import scala.collection.mutable.{HashSet, HashMap, ListBuffer}
 import scala.tools.nsc.util.{Position, NoPosition}
 
 abstract class LambdaLift extends InfoTransform {
@@ -62,9 +61,9 @@ abstract class LambdaLift extends InfoTransform {
     /** Buffers for lifted out classes and methods */
     private val liftedDefs = new HashMap[Symbol, ListBuffer[Tree]]
 
-    private type SymSet = TreeSet[Symbol]
+    private type SymSet = HashSet[Symbol]
 
-    private def newSymSet = new TreeSet[Symbol]((x, y) => x.isLess(y))
+    private def newSymSet = new HashSet[Symbol]
 
     private def symSet(f: HashMap[Symbol, SymSet], sym: Symbol): SymSet = f.get(sym) match {
       case Some(ss) => ss
diff --git a/src/compiler/scala/tools/nsc/transform/LiftCode.scala b/src/compiler/scala/tools/nsc/transform/LiftCode.scala
index e3e9d70384..35bd1abaed 100644
--- a/src/compiler/scala/tools/nsc/transform/LiftCode.scala
+++ b/src/compiler/scala/tools/nsc/transform/LiftCode.scala
@@ -10,8 +10,8 @@ import symtab._
 import Flags._
 import symtab.Flags._
 import scala.collection.immutable.ListMap
-import scala.collection.mutable.{HashMap, ListBuffer}
-import scala.tools.nsc.util.{FreshNameCreator, TreeSet}
+import scala.collection.mutable.{HashSet, HashMap, ListBuffer}
+import scala.tools.nsc.util.{FreshNameCreator}
 
 /** Translate expressions of the form reflect.Code.lift(exp)
  *  to the lifted "reflect trees" representation of exp.
diff --git a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
index 4217cc32ce..c983717dc9 100644
--- a/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
+++ b/src/compiler/scala/tools/nsc/transform/OverridingPairs.scala
@@ -6,9 +6,8 @@
 
 package scala.tools.nsc.transform
 
-import collection.mutable.HashMap
+import collection.mutable.{HashSet, HashMap}
 import symtab.Flags._
-import util.HashSet
 
 /** This abstract class ...
  *
@@ -99,7 +98,8 @@ abstract class OverridingPairs {
       intersectionContainsElementLeq(subParents(index1), subParents(index2), minindex)
     }
 
-    private val visited = new HashSet[ScopeEntry](256)
+    private val visited =
+      new HashSet[ScopeEntry] { override def initialSize = 256 }
     private var curEntry = decls.elems
     private var nextEntry = curEntry
 
diff --git a/src/compiler/scala/tools/nsc/util/BitSet.scala b/src/compiler/scala/tools/nsc/util/BitSet.scala
deleted file mode 100644
index 08fe8098d1..0000000000
--- a/src/compiler/scala/tools/nsc/util/BitSet.scala
+++ /dev/null
@@ -1,158 +0,0 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2007 LAMP/EPFL
- * @author  Martin Odersky
- */
-// $Id: Set.scala 12005 2007-06-13 12:28:07Z michelou $
-
-package scala.tools.nsc.util
-
-object BitSet {
-
-  final val WordSize = 64
-  private final val WordMask = WordSize - 1
-
-  val empty: BitSet = new Single(0)
-  def apply(elems: Int*): BitSet = empty ++ elems
-
-  private def wordIterator(elems: Long, adjust: Int) = new Iterator[Int] {
-    private var rest = elems
-    private var i = 0
-    def hasNext = rest != 0
-    def next() = {
-      if (rest == 0)
-        throw new NoSuchElementException("next on empty iterator")
-      while ((rest & 1) == 0) {
-        rest >>>= 1
-        i += 1
-      }
-      rest >>>= 1
-      i += 1
-      i - 1 + adjust
-    }
-  }
-
-  private class Single(elems: Long) extends BitSet {
-
-    def contains(i: Int): Boolean =
-      0 <= i && i < WordSize && (elems & (1L << i)) != 0
-
-    def elements: Iterator[Int] =
-      wordIterator(elems, 0)
-
-    def +(i: Int): BitSet = {
-      require(0 <= i)
-      if (i < WordSize) new Single(elems | (1L << i))
-      else if (i < 2 * WordSize) new Double(elems, 1L << i)
-      else new Multiple(Array(elems)) + i
-    }
-
-    def -(i: Int): BitSet = {
-      require(0 <= i)
-      if (i < WordSize) new Single(elems & ~(1L << i))
-      else this
-    }
-  }
-
-  private class Double(elems1: Long, elems2: Long) extends BitSet {
-
-    def contains(i: Int): Boolean =
-      0 <= i &&
-      (i < WordSize && (elems1 & (1L << i)) != 0 ||
-       i < 2 * WordSize && (elems2 & (1L << i)) != 0)
-
-    def elements: Iterator[Int] =
-      wordIterator(elems1, 0) ++ wordIterator(elems2, WordSize)
-
-    def +(i: Int): BitSet = {
-      require(0 <= i)
-      if (i < WordSize) new Double(elems1 | (1L << i), elems2)
-      else if (i < 2 * WordSize) new Double(elems1, elems2 | (1L << i))
-      else new Multiple(Array(elems1, elems2)) + i
-    }
-
-    def -(i: Int): BitSet = {
-      require(0 <= i)
-      if (i < WordSize) new Double(elems1 & ~(1L << i), elems2)
-      else if (i < 2 * WordSize) new Double(elems1, elems2 & ~(1L << i))
-      else this
-    }
-  }
-
-  private class Multiple(elems: Array[Long]) extends BitSet {
-
-    def contains(i: Int): Boolean = {
-      val index = i / WordSize
-      0 <= i && index < elems.length  && (elems(index) & (1L << i)) != 0
-    }
-
-    def elements: Iterator[Int] =
-      Iterator.range(0, elems.length) flatMap (i => wordIterator(elems(i), i * WordSize))
-
-    def +(i: Int): BitSet = {
-      require(0 <= i)
-      val index = i / WordSize
-      val elems1 = new Array[Long](elems.length max (index + 1))
-      Array.copy(elems, 0, elems1, 0, elems.length)
-      elems1(index) = elems1(index) | (1L << i)
-      new Multiple(elems1)
-    }
-
-    def -(i: Int): BitSet = {
-      require(0 <= i)
-      val index = i / WordSize
-      if (index < elems.length && (elems(index) & (1L << i)) != 0) {
-        val elems1 = new Array[Long](elems.length)
-        Array.copy(elems, 0, elems1, 0, elems.length)
-        elems1(index) = elems1(index) & ~(1L << i)
-        new Multiple(elems1)
-      } else this
-    }
-  }
-}
-
-import BitSet._
-
-abstract class BitSet extends (Int => Boolean) {
-
-  def contains(i: Int): Boolean
-
-  def apply(i: Int): Boolean = contains(i)
-
-  def elements: Iterator[Int]
-
-  def +(i: Int): BitSet
-
-  def -(i: Int): BitSet
-
-  def + (elem1: Int, elem2: Int, elems: Int*): BitSet =
-    this + elem1 + elem2 ++ elems
-
-  def ++(elems: Iterator[Int]): BitSet =
-    (this /: elems) (_ + _)
-
-  def ++ (elems: Iterable[Int]): BitSet =
-    this ++ elems.elements
-
-  def - (elem1: Int, elem2: Int, elems: Int*): BitSet =
-    this - elem1 - elem2 -- elems
-
-  def -- (elems: Iterator[Int]): BitSet =
-    (this /: elems) (_ - _)
-
-  def -- (elems: Iterable[Int]): BitSet =
-    this -- elems.elements
-
-  def ** (that: BitSet): BitSet = filter(that.contains)
-
-  def map(f: Int => Int): BitSet =
-    (empty /: (elements map f)) (_ + _)
-
-  def flatMap(f: Int => Iterable[Int]): BitSet =
-    (empty /: (elements map f)) (_ ++ _)
-
-  def filter(p: Int => Boolean): BitSet =
-    (this /: elements) ((set, elem) => if (p(elem)) set else set - elem)
-
-  override def toString: String = elements.mkString("BitSet(", ", ", ")")
-}
-
diff --git a/src/compiler/scala/tools/nsc/util/ClassPath.scala b/src/compiler/scala/tools/nsc/util/ClassPath.scala
index 98135f6feb..6d981f8ee5 100644
--- a/src/compiler/scala/tools/nsc/util/ClassPath.scala
+++ b/src/compiler/scala/tools/nsc/util/ClassPath.scala
@@ -42,7 +42,7 @@ object ClassPath {
   /** Split path using platform-dependent path separator */
   def splitPath(path: String): List[String] = {
     val strtok = new StringTokenizer(path, File.pathSeparator)
-    val buf = new ListBuffer[String]
+    val buf = new collection.mutable.ListBuffer[String]
     while (strtok.hasMoreTokens()) {
       buf + strtok.nextToken()
     }
diff --git a/src/compiler/scala/tools/nsc/util/LinkedList.scala b/src/compiler/scala/tools/nsc/util/LinkedList.scala
deleted file mode 100644
index 15a4db5743..0000000000
--- a/src/compiler/scala/tools/nsc/util/LinkedList.scala
+++ /dev/null
@@ -1,12 +0,0 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2006 LAMP/EPFL
- * @author  Martin Odersky
- */
-// $Id$
-
-package scala.tools.nsc.util
-
-class LinkedList[T] {
-  var next: LinkedList[T] = null
-  var elem: T = _
-}
diff --git a/src/compiler/scala/tools/nsc/util/ListBuffer.scala b/src/compiler/scala/tools/nsc/util/ListBuffer.scala
deleted file mode 100644
index ac842782fd..0000000000
--- a/src/compiler/scala/tools/nsc/util/ListBuffer.scala
+++ /dev/null
@@ -1,61 +0,0 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2007 LAMP/EPFL
- * @author  Martin Odersky
- */
-// $Id$
-
-package scala.tools.nsc.util
-
-class ListBuffer[T] extends Iterator[T] {
-
-  private var first = new LinkedList[T]
-  private var limit = first
-
-  def +=(x: T) {
-    limit.elem = x
-    limit.next = new LinkedList[T]
-    limit = limit.next
-  }
-
-  def ++=(xs: Iterable[T]) {
-    for (x <- xs.elements) +=(x)
-  }
-
-  def +(x: T): ListBuffer[T] = { +=(x); this }
-  def ++(xs: Iterable[T]): ListBuffer[T] = { ++=(xs); this }
-
-  def hasNext: Boolean =
-    first != limit
-
-  def next: T = {
-    assert(hasNext)
-    val x = first.elem
-    first = first.next
-    x
-  }
-
-  def elements: Iterator[T] = new Iterator[T] {
-    var first = ListBuffer.this.first
-
-    def hasNext: Boolean =
-      first != limit
-
-    def next: T = {
-      assert(hasNext)
-      val x = first.elem
-      first = first.next
-      x
-    }
-  }
-
-  def clear { first = limit }
-
-  /** override for efficiency */
-  override def toList: List[T] = {
-    def mkList(p: LinkedList[T]): List[T] =
-      if (p == limit) List() else p.elem :: mkList(p.next)
-    mkList(first)
-  }
-
-  override def toString(): String = toList.mkString("", ",", "")
-}
diff --git a/src/compiler/scala/tools/nsc/util/TreeSet.scala b/src/compiler/scala/tools/nsc/util/TreeSet.scala
deleted file mode 100644
index 54ff5e2dd3..0000000000
--- a/src/compiler/scala/tools/nsc/util/TreeSet.scala
+++ /dev/null
@@ -1,56 +0,0 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2007 LAMP/EPFL
- * @author  Martin Odersky
- */
-// $Id$
-
-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 + "...)"
-  }
-}