/* BSD 2-Clause License - see OPAL/LICENSE for details. */ package org.opalj package collection package immutable /** * A growable, immutable linked list based, data store for '''reference values''' except `null`. * Though this data store is backed by a linked list, it is not a classical linked list and it * does not offer (efficient) head and tail operations. However, compared to a classical linked * list the memory usage is reduced by ~33% and a simple foreach is also ~17% faster, the time * to create the list is comparable and iteration using an Iterator is marginally slower if at all. * The basic idea is to two store 2 values in each node of the linked list to reduce the overhead * incurred by the creation of the objects. * * This list does not perform any length related checks. I.e., it fails,e.g., in * case of `forFirstN` if the size of the list is smaller than expected. * * Furthermore, all directly implemented methods use `while` loops for maximum * efficiency and the list is also specialized for primitive `unsigned long` values which * makes this list far more efficient when used for storing lists of `long` values. * * @author Michael Eichberg */ sealed abstract class Ref2List[+T <: AnyRef] extends Serializable { self => private[immutable] def h: T private[immutable] def t: T private[immutable] def rest: Ref2List[T] def isEmpty: Boolean def isSingletonList: Boolean def nonEmpty: Boolean def foreach[U](f: T => U): Unit /** Iterates over the first N values. */ def forFirstN[U](n: Int)(f: T => U): Unit /** * @return An iterator over this list's values. In general, you should prefer using foreach or * the other specialized methods to avoid the overhead incurred by the generation of * the iterator. */ def iterator: Iterator[T] /** Prepends the given value to this list. E.g., `l = "x" +: l`. */ def +:[X >: T <: AnyRef](v: X): Ref2List[X] final override def equals(other: Any): Boolean = { other match { case l: Ref2List[AnyRef] => equals(l) case _ => false } } def equals(that: Ref2List[AnyRef]): Boolean override def hashCode: Int // just added to ensure that we have to override hashCode! } object Ref2List { def empty[T <: AnyRef]: Ref2List[T] = Ref2ListEnd def apply[T >: Null <: AnyRef](v: T): Ref2List[T] = { new Ref2ListNode[T](null, v, Ref2ListEnd) } def apply[T >: Null <: AnyRef](head: T, last: T): Ref2List[T] = { new Ref2ListNode[T](head, last, Ref2ListEnd) } } /** * An empty [[Ref2List]]. * * @author Michael Eichberg */ private[immutable] case object Ref2ListEnd extends Ref2List[Nothing] { override def isEmpty: Boolean = true override def isSingletonList: Boolean = false override def nonEmpty: Boolean = false override private[immutable] def h: Nothing = throw new UnsupportedOperationException override private[immutable] def t: Nothing = throw new UnsupportedOperationException override private[immutable] def rest: Ref2List[Nothing] = throw new UnsupportedOperationException override def foreach[U](f: Nothing => U): Unit = {} /** Iterates over the first N values. */ override def forFirstN[U](n: Int)(f: Nothing => U): Unit = {} override def iterator: Iterator[Nothing] = Iterator.empty /** Prepends the given value to this list. E.g., `l = 2l +: l`. */ override def +:[X <: AnyRef](v: X): Ref2List[X] = { new Ref2ListNode[AnyRef](null, v, this).asInstanceOf[Ref2List[X]] } override def equals(that: Ref2List[AnyRef]): Boolean = this eq that override def hashCode: Int = 37 } /** * An container for a list element. * * @author Michael Eichberg */ private[immutable] final case class Ref2ListNode[T >: Null <: AnyRef]( private[immutable] var h: T, private[immutable] var t: T, private[immutable] var rest: Ref2List[T] ) extends Ref2List[T] { list => override def isEmpty: Boolean = false override def isSingletonList: Boolean = h == null && (rest eq Ref2ListEnd) override def nonEmpty: Boolean = true override def foreach[U](f: T => U): Unit = { if (h != null) f(h) f(t) var list: Ref2List[T] = this.rest while (list.nonEmpty) { f(list.h) f(list.t) list = list.rest } } override def forFirstN[U](n: Int)(f: T => U): Unit = { n match { case 0 => return ; case 1 => if (h != null) f(h) else f(t) return ; case _ => // ... n >= 2 var i = n - 1 // <= -1 for the second element "t"... if (h != null) { f(h); i -= 1 } f(t) var list: Ref2List[T] = rest while (i > 0) { i -= 2 f(list.h) if (i >= 0) f(list.t) list = list.rest } } } override def iterator: Iterator[T] = { new Iterator[T] { private[this] var currentList: Ref2List[T] = list private[this] var head: Boolean = list.h != null def hasNext: Boolean = currentList ne Ref2ListEnd def next(): T = { if (head) { head = false currentList.h } else { head = true val v = currentList.t currentList = currentList.rest v } } } } override def +:[X >: T <: AnyRef](v: X): Ref2List[X] = { if (h != null) new Ref2ListNode(null, v, this) else new Ref2ListNode(v, t, this.rest) } override def equals(that: Ref2List[AnyRef]): Boolean = { (that eq this) || { var thisList: Ref2List[_] = this var thatList = that while ((thisList ne Ref2ListEnd) && (thatList ne Ref2ListEnd)) { if (thisList.h != thatList.h || thisList.t != thatList.t) return false; thisList = thisList.rest thatList = thatList.rest } thisList eq thatList //... <=> true iff both lists are empty } } override def hashCode: Int = { var h = 31 var list: Ref2List[_] = this while (list ne Ref2ListEnd) { if (list.h != null) h += list.h.hashCode * 31 h += list.t.hashCode * 31 list = list.rest } h } }