/* BSD 2-Clause License - see OPAL/LICENSE for details. */ package org.opalj package collection package immutable import java.lang.{Long => JLong} /** * An immutable linked list for storing long values. * 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. * * @note In most cases a `LongList` can be used as a drop-in replacement for a standard * Scala List. * * @author Michael Eichberg */ sealed trait LongList extends Serializable { self => def isEmpty: Boolean def nonEmpty: Boolean def head: Long def tail: LongList def foreach[U](f: Long => U): Unit /** Iterates over the first N values. */ def forFirstN[U](n: Int)(f: Long => U): Unit def iterator: LongIterator /** Prepends the given value to this list. E.g., `l = 2l +: l`. */ def +:(v: Long): LongList final override def equals(other: Any): Boolean = { other match { case l: LongList => equals(l) case _ => false } } def equals(that: LongList): Boolean override def hashCode(): Int // just added to ensure that we have to override hashCode! } object LongList { def empty: LongList = LongList0 def apply(v: Long): LongList = new LongListNode(v, LongList0) def apply(head: Long, last: Long): LongList = { new LongListNode(head, new LongListNode(last, LongList0)) } } /** * An empty [[LongList]]. * * @author Michael Eichberg */ case object LongList0 extends LongList { override def head: Long = throw new UnsupportedOperationException override def tail: LongList = throw new UnsupportedOperationException override def isEmpty: Boolean = true override def nonEmpty: Boolean = false override def foreach[U](f: Long => U): Unit = {} /** Iterates over the first N values. */ override def forFirstN[U](n: Int)(f: Long => U): Unit = {} override def iterator: LongIterator = LongIterator.empty /** Prepends the given value to this list. E.g., `l = 2l +: l`. */ override def +:(v: Long): LongList = new LongListNode(v, this) override def equals(that: LongList): Boolean = that eq this override def hashCode(): Int = 31 } /** * An container for a list element. * * @author Michael Eichberg */ final case class LongListNode( head: Long, private[immutable] var rest: LongList = LongList0 ) extends LongList { list => override def tail: LongList = rest override def isEmpty: Boolean = false override def nonEmpty: Boolean = true override def foreach[U](f: Long => U): Unit = { var list: LongList = this do { f(list.head) list = list.tail } while (list.nonEmpty) } override def forFirstN[U](n: Int)(f: Long => U): Unit = { if (n == 0) return ; var i = 0 var list: LongList = this do { f(list.head) list = list.tail i += 1 } while (list.nonEmpty && i < n) } override def iterator: LongIterator = { new LongIterator { private[this] var currentList: LongList = list def hasNext: Boolean = currentList.nonEmpty def next(): Long = { val v = currentList.head currentList = currentList.tail v } } } override def +:(v: Long): LongList = new LongListNode(v, this) override def equals(that: LongList): Boolean = { (that eq this) || { var thisList: LongList = this var thatList = that while ((thisList ne LongList0) && (thatList ne LongList0)) { if (thisList.head != thatList.head) return false; thisList = thisList.tail thatList = thatList.tail } thisList eq thatList //... <=> true iff both lists are empty } } override def hashCode(): Int = { var h = 31 var list: LongList = this while (list ne LongList0) { h = (h + JLong.hashCode(list.head)) * 31 list = list.tail } h } }