/* BSD 2-Clause License - see OPAL/LICENSE for details. */ package org.opalj.collection package immutable import scala.annotation.switch import java.lang.{Long => JLong} import java.lang.{Integer => JInt} /** * An effectively immutable trie set of long values where the elements are sorted based on the * insertion order. * * All traversing operations are defined based on the insertion order. The latest added elements * will be iterated over first. * * The trie set is specialized for sizes up to three elements. * * @author Michael Eichberg */ sealed abstract class LongLinkedTrieSet extends LongLinkedSet { final type ThisSet = LongLinkedTrieSet } object LongLinkedTrieSet { def empty: LongLinkedTrieSet = LongLinkedTrieSet0 def apply(v: Long): LongLinkedTrieSet = new LongLinkedTrieSet1(v) def apply(head: Long, last: Long): LongLinkedTrieSet = { if (head == last) new LongLinkedTrieSet1(head) else new LongLinkedTrieSet2(head, last) } } case object LongLinkedTrieSet0 extends LongLinkedTrieSet { final override def size: Int = 0 final override def isEmpty: Boolean = true final override def isSingletonSet: Boolean = false final override def head: Long = throw new UnsupportedOperationException final override def contains(v: Long): Boolean = false final override def foreach[U](f: Long => U): Unit = { /*nothing to do*/ } final override def foldLeft[T](op: T)(f: (T, Long) => T): T = op final override def forall(f: Long => Boolean): Boolean = true final override def forFirstN[U](n: Int)(f: Long => U): Unit = { /*nothing to do*/ } final override def iterator: LongIterator = LongIterator.empty final override def +(v: Long): LongLinkedTrieSet = LongLinkedTrieSet1(v) } final case class LongLinkedTrieSet1(v1: Long) extends LongLinkedTrieSet { final override def size: Int = 1 final override def isEmpty: Boolean = false final override def isSingletonSet: Boolean = true final override def head: Long = v1 final override def contains(v: Long): Boolean = v == v1 final override def foreach[U](f: Long => U): Unit = f(v1) final override def foldLeft[T](op: T)(f: (T, Long) => T): T = f(op, v1) final override def forall(f: Long => Boolean): Boolean = f(v1) final override def forFirstN[U](n: Int)(f: Long => U): Unit = if (n > 0) f(v1) final override def iterator: LongIterator = LongIterator(v1) final override def +(v: Long): LongLinkedTrieSet = { if (v != v1) new LongLinkedTrieSet2(v, v1) else this } } final private[immutable] case class LongLinkedTrieSet2( v1: Long, v2: Long ) extends LongLinkedTrieSet { final override def size: Int = 2 final override def isEmpty: Boolean = false final override def isSingletonSet: Boolean = false final override def head: Long = v1 final override def contains(v: Long): Boolean = v == v1 || v == v2 final override def foreach[U](f: Long => U): Unit = { f(v1); f(v2) } final override def forall(f: Long => Boolean): Boolean = f(v1) && f(v2) final override def foldLeft[T](z: T)(f: (T, Long) => T): T = f(f(z, v1), v2) final override def forFirstN[U](n: Int)(f: Long => U): Unit = { if (n == 0) return ; f(v1) if (n == 1) return ; f(v2) } final override def iterator: LongIterator = LongIterator(v1, v2) final override def +(v: Long): LongLinkedTrieSet = { if (v != v1 && v != v2) new LongLinkedTrieSet3(v, v1, v2) else this } } final private[immutable] case class LongLinkedTrieSet3( v1: Long, v2: Long, v3: Long ) extends LongLinkedTrieSet { final override def size: Int = 3 final override def isEmpty: Boolean = false final override def isSingletonSet: Boolean = false final override def head: Long = v1 final override def contains(v: Long): Boolean = v == v1 || v == v2 || v == v3 final override def foreach[U](f: Long => U): Unit = { f(v1); f(v2); f(v3) } final override def forall(f: Long => Boolean): Boolean = f(v1) && f(v2) && f(v3) final override def foldLeft[T](z: T)(f: (T, Long) => T): T = f(f(f(z, v1), v2), v3) final override def forFirstN[U](n: Int)(f: Long => U): Unit = { if (n == 0) return ; f(v1) if (n == 1) return ; f(v2) if (n == 2) return ; f(v3) } final override def iterator: LongIterator = LongIterator(v1, v2, v3) final override def +(v: Long): LongLinkedTrieSet = { if (v != v1 && v != v2 && v != v3) { // We have to ensure that we keep the order! val set = new LargeLongLinkedTrieSet() set += v3 set += v2 set += v1 set += v set } else { this } } } /** The super type of the nodes of the trie set. */ private[immutable] sealed abstract class LongLinkedTrieSetNode { /** `true` if this is an inner node. */ def isN: Boolean def isN4: Boolean /** `true` if this is a leaf node. */ def isL: Boolean def asL: LongLinkedTrieSetL def contains(v: Long, key: Long): Boolean /** * Returns the node at the next trie level if the bit at the current level is 0. * * The top node in the trie has level "0". */ def split_0(level: Int): LongLinkedTrieSetNode /** * Returns the node at the next trie level if the bit at the current level is 1. * * The top node in the trie has level "0". */ def split_1(level: Int): LongLinkedTrieSetNode def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode def toString(level: Int): String } /** The leaves of the trie set. */ final private[immutable] class LongLinkedTrieSetL( final val value: Long, final val next: LongLinkedTrieSetL = null // `null` if this leaf is the first element that was added to the set. ) extends LongLinkedTrieSetNode { override def isN: Boolean = false override def isN4: Boolean = false override def isL: Boolean = true override def asL: LongLinkedTrieSetL = this override def contains(v: Long, key: Long): Boolean = v == value override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val thisValue = this.value val lValue = l.value if (thisValue == lValue) return this; // Let's check if there is some sharing and if so, let's use it. val thisValueShifted = thisValue >> level val lValueShifted = lValue >> level JLong.numberOfTrailingZeros(thisValueShifted ^ lValueShifted) match { case 0 => if ((thisValueShifted & 1L) == 0L) { new LongLinkedTrieSetN2(this, l) } else { new LongLinkedTrieSetN2(l, this) } case 1 => if ((thisValueShifted & 1L) == 0L) { if ((thisValueShifted & 2L) == 0L) { new LongLinkedTrieSetN4_0_2(this, l) } else { new LongLinkedTrieSetN4_0_2(l, this) } } else { if ((thisValueShifted & 2L) == 0L) { new LongLinkedTrieSetN4_1_3(this, l) } else { new LongLinkedTrieSetN4_1_3(l, this) } } case length => val sharedBits = thisValueShifted & LongSet.BitMasks(length) val n = if (((thisValueShifted >> length) & 1L) == 0L) new LongLinkedTrieSetN2(this, l) else new LongLinkedTrieSetN2(l, this) LongLinkedTrieSetNShared(sharedBits, length, n) } } final override def split_0(level: Int): LongLinkedTrieSetNode = { if ((((value >> level) & 1L) == 0L)) { this } else { null } } final override def split_1(level: Int): LongLinkedTrieSetNode = { if ((((value >> level) & 1L) == 1L)) { this } else { null } } final override def toString(level: Int): String = s"L(${value.toBinaryString}=$value)" } /** The inner nodes of the trie set. */ private[immutable] sealed abstract class LongLinkedTrieSetInnerNode extends LongLinkedTrieSetNode { final override def isN: Boolean = true final override def isL: Boolean = false final override def asL: LongLinkedTrieSetL = throw new ClassCastException() } private[immutable] sealed abstract class LongLinkedTrieSetNShared extends LongLinkedTrieSetInnerNode { final override def isN4: Boolean = false def sharedBits: Long def length: Int // at least "1" def n: LongLinkedTrieSetNode /* Adds one bit to this sequence of shared bits with the given value. */ def prependBit(bit: Int): LongLinkedTrieSetNShared def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val length = this.length val sharedBits = this.sharedBits val lValue = l.value val lValueShifted = lValue >> level if ((lValueShifted & LongSet.BitMasks(length)) == sharedBits) { val oldN = this.n val newN = oldN.add(l, level + length) if (oldN ne newN) { LongLinkedTrieSetNShared(sharedBits, length, newN) } else { this } } else { // `length` is at least 1 and the number of shared bits is smaller than the current // length; i.e., lengthOfTail is at least 1 val lengthOfLead = JLong.numberOfTrailingZeros(sharedBits ^ lValueShifted) val lengthOfTail = length - lengthOfLead - 1 /* -1 for the differing bit */ // Potential optimizations: // We can fold the tail if the number of shared remaining bits is one // We can fold the lead if the number of shared initial bits is one // 1. Create new tail (if required): val newT = if (lengthOfTail == 0) n else LongLinkedTrieSetNShared(sharedBits >> lengthOfLead + 1, lengthOfTail, n) // 2. Create new node where we have the difference val newM = if (((sharedBits >> lengthOfLead) & 1L) == 0L) { LongLinkedTrieSetN2(level + lengthOfLead, newT, l) } else { LongLinkedTrieSetN2(level + lengthOfLead, l, newT) } // 3. Create new lead node (if required) if (lengthOfLead == 0) { newM } else { LongLinkedTrieSetNShared(sharedBits & LongSet.BitMasks(lengthOfLead), lengthOfLead, newM) } } } def toString(level: Int): String = { val lP2 = level + length + 2 s"NShared(_${sharedBits.toBinaryString}(#$length)=>${n.toString(lP2)}" } } private[immutable] object LongLinkedTrieSetNShared { def apply(sharedBits: Long, length: Int, n: LongLinkedTrieSetNode): LongLinkedTrieSetNode = { assert(length >= 1) length match { case 1 => // if (sharedBits == 0L /*test the last bit...*/ ) // new LongLinkedTrieSetNShared_0(n) // else // new LongLinkedTrieSetNShared_1(n) (n: @unchecked) match { case l: LongLinkedTrieSetN2 => if (sharedBits == 0L /*test the last bit...*/ ) { new LongLinkedTrieSetN4_0_2(l._0, l._1) } else { new LongLinkedTrieSetN4_1_3(l._0, l._1) } case l: LongLinkedTrieSetN4 => if (sharedBits == 0L /*test the last bit...*/ ) new LongLinkedTrieSetNShared_0(n) else new LongLinkedTrieSetNShared_1(n) // won't occur: case _: LongLinkedTrieSetL || _: LongLinkedTrieSetNShared } case 2 => (sharedBits.toInt: @switch) match { case 0 => new LongLinkedTrieSetNShared_00(n) case 1 => new LongLinkedTrieSetNShared_01(n) case 2 => new LongLinkedTrieSetNShared_10(n) case 3 => new LongLinkedTrieSetNShared_11(n) } case _ => new LongLinkedTrieSetNShared_X(sharedBits, length, n) } } } final private[immutable] class LongLinkedTrieSetNShared_0( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { override def sharedBits: Long = 0 override def length: Int = 1 override def split_0(level: Int): LongLinkedTrieSetNode = n override def split_1(level: Int): LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { ((key & 1L) == 0L) && n.contains(v, key >> 1) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { if (bit == 0) new LongLinkedTrieSetNShared_00(n) else new LongLinkedTrieSetNShared_01(n) } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val lValue = l.value val lValueShifted = lValue >> level if ((lValueShifted & 1L) == 0L) { val oldN = this.n val newN = oldN.add(l, level + length) if (oldN ne newN) { new LongLinkedTrieSetNShared_0(newN) } else { this } } else { LongLinkedTrieSetN2(level, n, l) } } } final private[immutable] class LongLinkedTrieSetNShared_1( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { override def sharedBits: Long = 1 override def length: Int = 1 override def split_0(level: Int): LongLinkedTrieSetNode = null override def split_1(level: Int): LongLinkedTrieSetNode = n override def contains(v: Long, key: Long): Boolean = { ((key & 1L) == 1L) && n.contains(v, key >> 1) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { if (bit == 0) new LongLinkedTrieSetNShared_10(n) else new LongLinkedTrieSetNShared_11(n) } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val lValue = l.value val lValueShifted = lValue >> level if ((lValueShifted & 1L) == 1L) { val oldN = this.n val newN = oldN.add(l, level + length) if (oldN ne newN) { new LongLinkedTrieSetNShared_1(newN) } else { this } } else { LongLinkedTrieSetN2(level, l, n) } } } final private[immutable] class LongLinkedTrieSetNShared_00( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { override def sharedBits: Long = 0 override def length: Int = 2 override def split_0(level: Int): LongLinkedTrieSetNode = new LongLinkedTrieSetNShared_0(n) override def split_1(level: Int): LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { ((key & 3L) == 0L) && n.contains(v, key >> 2) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { new LongLinkedTrieSetNShared_X(if (bit == 0) 0L else 1L, 3, n) } } final private[immutable] class LongLinkedTrieSetNShared_01( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { def sharedBits: Long = 1 def length: Int = 2 override def split_0(level: Int): LongLinkedTrieSetNode = null override def split_1(level: Int): LongLinkedTrieSetNode = new LongLinkedTrieSetNShared_0(n) override def contains(v: Long, key: Long): Boolean = { ((key & 3L) == 1L) && n.contains(v, key >> 2) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { new LongLinkedTrieSetNShared_X(if (bit == 0) 2L else 3L, 3, n) } } final private[immutable] class LongLinkedTrieSetNShared_10( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { def sharedBits: Long = 2 def length: Int = 2 override def split_0(level: Int): LongLinkedTrieSetNode = new LongLinkedTrieSetNShared_1(n) override def split_1(level: Int): LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { ((key & 3L) == 2L) && n.contains(v, key >> 2) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { new LongLinkedTrieSetNShared_X(if (bit == 0) 4L else 5L, 3, n) } } final private[immutable] class LongLinkedTrieSetNShared_11( final val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { def sharedBits: Long = 3 def length: Int = 2 override def split_0(level: Int): LongLinkedTrieSetNode = null override def split_1(level: Int): LongLinkedTrieSetNode = new LongLinkedTrieSetNShared_1(n) override def contains(v: Long, key: Long): Boolean = { ((key & 3L) == 3L) && n.contains(v, key >> 2) } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { new LongLinkedTrieSetNShared_X(if (bit == 0) 6L else 7L, 3, n) } } final private[immutable] class LongLinkedTrieSetNShared_X( val sharedBits: Long, val length: Int, val n: LongLinkedTrieSetNode ) extends LongLinkedTrieSetNShared { override def split_0(level: Int): LongLinkedTrieSetNode = { if ((sharedBits & 1L) == 0L) { LongLinkedTrieSetNShared(sharedBits >> 1, length - 1, n) } else { null } } override def split_1(level: Int): LongLinkedTrieSetNode = { if ((sharedBits & 1L) == 1L) { LongLinkedTrieSetNShared(sharedBits >> 1, length - 1, n) } else { null } } override def prependBit(bit: Int): LongLinkedTrieSetNShared = { new LongLinkedTrieSetNShared_X( if (bit == 0) sharedBits << 1 else (sharedBits << 1) | 1L, length + 1, n ) } override def contains(v: Long, key: Long): Boolean = { val length = this.length ((key & LongSet.BitMasks(length)) == sharedBits) && n.contains(v, key >> length) } } /** The inner nodes of the trie set. */ final private[immutable] class LongLinkedTrieSetN2( final val _0: LongLinkedTrieSetNode, final val _1: LongLinkedTrieSetNode ) extends LongLinkedTrieSetInnerNode { override def isN4: Boolean = false override def contains(v: Long, key: Long): Boolean = { if ((key & 1L) == 0L) _0.contains(v, key >> 1) else _1.contains(v, key >> 1) } def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val _0 = this._0 val _1 = this._1 val lValue = l.value val lLSB = ((lValue >> level) & 1L) // lsb == bit at index `level` if (_0.isN || _1.isN) { // We can't get rid of this N2 node... a successor node is an inner node and we // do not want to perform "large" changes to the overall trie. return { if (lLSB == 0) { val new_0 = _0.add(l, level + 1) if (_0 ne new_0) { new LongLinkedTrieSetN2(new_0, this._1) } else { this } } else { val new_1 = _1.add(l, level + 1) if (_1 ne new_1) { new LongLinkedTrieSetN2(this._0, new_1) } else { this } } }; } if (lLSB == 0) { val _0Value = _0.asL.value if (_0Value == lValue) return this; if (((lValue >> level + 1) & 1L) == 0L) { // l = ...00 if (((_0Value >> level + 1) & 1L) == 0L) { val newN = _0.add(l, level + 2) if (((_1.asL.value >> level + 1) & 1L) == 0L) { new LongLinkedTrieSetN4_0_1(newN, _1) } else { new LongLinkedTrieSetN4_0_3(newN, _1) } } else { if (((_1.asL.value >> level + 1) & 1L) == 0L) { LongLinkedTrieSetN4(l, _1, _0, null) } else { LongLinkedTrieSetN4(l, null, _0, _1) } } } else { // l = ...10 if (((_0Value >> level + 1) & 1) == 0L) { // l = ...10, _0 = ...00 if (((_1.asL.value >> level + 1) & 1L) == 0L) { LongLinkedTrieSetN4(_0, _1, l, null) } else { LongLinkedTrieSetN4(_0, null, l, _1) } } else { // l = ...10, _0 =...10 val newN = _0.add(l, level + 2) if (((_1.asL.value >> level + 1) & 1L) == 0L) { new LongLinkedTrieSetN4_1_2(_1, newN) } else { new LongLinkedTrieSetN4_2_3(newN, _1) } } } } else { val _1Value = _1.asL.value if (_1Value == lValue) return this; if (((lValue >> level + 1) & 1L) == 0L) { // l = ...01 if (((_1Value >> level + 1) & 1L) == 0L) { // l = ...01, _1 = ...01 val newN = _1.add(l, level + 2) if (((_0.asL.value >> level + 1) & 1L) == 0) { new LongLinkedTrieSetN4_0_1(_0, newN) } else { new LongLinkedTrieSetN4_1_2(newN, _0) } } else { // l = ...01,_1 = ...11 if (((_0.asL.value >> level + 1) & 1L) == 0L) { LongLinkedTrieSetN4(_0, l, null, _1) } else { LongLinkedTrieSetN4(null, l, _0, _1) } } } else { // l = ...11 if (((_1Value >> level + 1) & 1L) == 0L) { // l = ...11, _1 = ...01 if (((_0.asL.value >> level + 1) & 1L) == 0L) { LongLinkedTrieSetN4(_0, _1, null, l) } else { LongLinkedTrieSetN4(null, _1, _0, l) } } else { // l = ...11, _1 = ...11 val newN = _1.add(l, level + 2) if (((_0.asL.value >> level + 1) & 1L) == 0L) { new LongLinkedTrieSetN4_0_3(_0, newN) } else { new LongLinkedTrieSetN4_2_3(_0, newN) } } } } } override def split_0(level: Int): LongLinkedTrieSetNode = _0 override def split_1(level: Int): LongLinkedTrieSetNode = _1 override def toString(level: Int): String = { val indent = " " * level val lP2 = level + 2 s"N2(\n$indent 0=>${_0.toString(lP2)}\n$indent 1=>${_1.toString(lP2)})" } } private[immutable] object LongLinkedTrieSetN2 { def apply( level: Int, // the level at which this LongLinkedTrieSetNode will be added to the trie _0: LongLinkedTrieSetNode, _1: LongLinkedTrieSetNode ): LongLinkedTrieSetNode = { if (_0.isN4 || _1.isN4) return new LongLinkedTrieSetN2(_0, _1); val newLevel = level + 1 LongLinkedTrieSetN4( _0.split_0(newLevel), _1.split_0(newLevel), _0.split_1(newLevel), _1.split_1(newLevel) ) } } object LongLinkedTrieSetN4 { def apply( _0: LongLinkedTrieSetNode, _1: LongLinkedTrieSetNode, _2: LongLinkedTrieSetNode, _3: LongLinkedTrieSetNode ): LongLinkedTrieSetN4 = { if (_0 eq null) { if (_1 eq null) { //(0,0,?,?) new LongLinkedTrieSetN4_2_3(_2, _3) } else { //(0,1,?,?) if (_2 eq null) { //(0,1,0,?) new LongLinkedTrieSetN4_1_3(_1, _3) } else { //(0,1,1,?) if (_3 eq null) { //(0,1,1,0) new LongLinkedTrieSetN4_1_2(_1, _2) } else { //(0,1,1,1) new LongLinkedTrieSetN4_0_1_2_3(null, _1, _2, _3) } } } } else { if (_1 eq null) { //(1,0,?,?) if (_2 eq null) { //(1,0,0,?) new LongLinkedTrieSetN4_0_3(_0, _3) } else { //(1,0,1,?) if (_3 eq null) { //(1,0,1,0) new LongLinkedTrieSetN4_0_2(_0, _2) } else { //(1,0,1,1) new LongLinkedTrieSetN4_0_1_2_3(_0, null, _2, _3) } } } else { //(1,1,?,?) if (_2 eq null) { //(1,1,0,?) if (_3 eq null) { //(1,1,0,0) new LongLinkedTrieSetN4_0_1(_0, _1) } else { //(1,1,0,1) new LongLinkedTrieSetN4_0_1_2_3(_0, _1, null, _3) } } else { //(1,1,1,?) new LongLinkedTrieSetN4_0_1_2_3(_0, _1, _2, _3) } } } } } /** The inner nodes of the trie set. */ private[immutable] abstract class LongLinkedTrieSetN4 extends LongLinkedTrieSetInnerNode { protected def _0: LongLinkedTrieSetNode protected def _1: LongLinkedTrieSetNode protected def _2: LongLinkedTrieSetNode protected def _3: LongLinkedTrieSetNode final override def isN4: Boolean = true final override def split_0(level: Int): LongLinkedTrieSetNode = { // We keep 00 and 10... i.e. we extract 0 and 2 if (_0 eq null) { if (_2 eq null) null else _2 match { case n: LongLinkedTrieSetL => n case n: LongLinkedTrieSetN2 => new LongLinkedTrieSetN4_1_3(n._0, n._1) case n: LongLinkedTrieSetN4 => new LongLinkedTrieSetNShared_1(n) case n: LongLinkedTrieSetNShared => n.prependBit(1) } } else if (_2 eq null) { _0 match { case n: LongLinkedTrieSetL => n case n: LongLinkedTrieSetN2 => new LongLinkedTrieSetN4_0_2(n._0, n._1) case n: LongLinkedTrieSetN4 => new LongLinkedTrieSetNShared_0(n) case n: LongLinkedTrieSetNShared => n.prependBit(0) } } else { LongLinkedTrieSetN2(level + 1, _0, _2) } } final override def split_1(level: Int): LongLinkedTrieSetNode = { // We keep 01 and 11... i.e. we extract 1 and 3 if (_1 eq null) { if (_3 eq null) null else _3 match { case n: LongLinkedTrieSetL => n case n: LongLinkedTrieSetN2 => new LongLinkedTrieSetN4_1_3(n._0, n._1) case n: LongLinkedTrieSetN4 => new LongLinkedTrieSetNShared_1(n) case n: LongLinkedTrieSetNShared => n.prependBit(1) } } else if (_3 eq null) { _1 match { case n: LongLinkedTrieSetL => n case n: LongLinkedTrieSetN2 => new LongLinkedTrieSetN4_0_2(n._0, n._1) case n: LongLinkedTrieSetN4 => new LongLinkedTrieSetNShared_0(n) case n: LongLinkedTrieSetNShared => n.prependBit(0) } } else { LongLinkedTrieSetN2(level + 1, _1, _3) } } final override def toString(level: Int): String = { val indent = " " * level val lP2 = level + 4 var s = "N4(" if (_0 ne null) s += s"\n$indent 00=>${_0.toString(lP2)}" if (_1 ne null) s += s"\n$indent 01=>${_1.toString(lP2)}" if (_2 ne null) s += s"\n$indent 10=>${_2.toString(lP2)}" if (_3 ne null) s += s"\n$indent 11=>${_3.toString(lP2)}" s+")" } } final private[immutable] class LongLinkedTrieSetN4_0_1( final val _0: LongLinkedTrieSetNode, final val _1: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _2: LongLinkedTrieSetNode = null final override protected def _3: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 0L => _0.contains(v, key >> 2) case 1L => _1.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => val new0 = _0.add(l, level + 2) if (_0 ne new0) { new LongLinkedTrieSetN4_0_1(new0, this._1) } else { this } case 1 => val new1 = _1.add(l, level + 2) if (_1 ne new1) { new LongLinkedTrieSetN4_0_1(this._0, new1) } else { this } case 2 => new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, l, null) case 3 => new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, null, l) } } } final private[immutable] class LongLinkedTrieSetN4_0_2( final val _0: LongLinkedTrieSetNode, final val _2: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _1: LongLinkedTrieSetNode = null final override protected def _3: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 0L => _0.contains(v, key >> 2) case 2L => _2.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => val new0 = _0.add(l, level + 2) if (_0 ne new0) { new LongLinkedTrieSetN4_0_2(new0, this._2) } else { this } case 1 => new LongLinkedTrieSetN4_0_1_2_3(this._0, l, this._2, null) case 2 => val new2 = _2.add(l, level + 2) if (_2 ne new2) { new LongLinkedTrieSetN4_0_2(this._0, new2) } else { this } case 3 => new LongLinkedTrieSetN4_0_1_2_3(this._0, null, this._2, l) } } } final private[immutable] class LongLinkedTrieSetN4_0_3( final val _0: LongLinkedTrieSetNode, final val _3: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _1: LongLinkedTrieSetNode = null final override protected def _2: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 0L => _0.contains(v, key >> 2) case 3L => _3.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => val new0 = _0.add(l, level + 2) if (_0 ne new0) { new LongLinkedTrieSetN4_0_3(new0, this._3) } else { this } case 1 => new LongLinkedTrieSetN4_0_1_2_3(this._0, l, null, this._3) case 2 => new LongLinkedTrieSetN4_0_1_2_3(this._0, null, l, this._3) case 3 => val new3 = _3.add(l, level + 2) if (_3 ne new3) { new LongLinkedTrieSetN4_0_3(this._0, new3) } else { this } } } } final private[immutable] class LongLinkedTrieSetN4_1_2( final val _1: LongLinkedTrieSetNode, final val _2: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _0: LongLinkedTrieSetNode = null final override protected def _3: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 1L => _1.contains(v, key >> 2) case 2L => _2.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => new LongLinkedTrieSetN4_0_1_2_3(l, this._1, this._2, null) case 1 => val new1 = _1.add(l, level + 2) if (_1 ne new1) { new LongLinkedTrieSetN4_1_2(new1, this._2) } else { this } case 2 => val new2 = _2.add(l, level + 2) if (_2 ne new2) { new LongLinkedTrieSetN4_1_2(this._1, new2) } else { this } case 3 => new LongLinkedTrieSetN4_0_1_2_3(null, this._1, this._2, l) } } } final private[immutable] class LongLinkedTrieSetN4_1_3( final val _1: LongLinkedTrieSetNode, final val _3: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _0: LongLinkedTrieSetNode = null final override protected def _2: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 1L => _1.contains(v, key >> 2) case 3L => _3.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => new LongLinkedTrieSetN4_0_1_2_3(l, this._1, null, this._3) case 1 => val new1 = _1.add(l, level + 2) if (_1 ne new1) { new LongLinkedTrieSetN4_1_3(new1, this._3) } else { this } case 2 => new LongLinkedTrieSetN4_0_1_2_3(null, this._1, l, this._3) case 3 => val new3 = _3.add(l, level + 2) if (_3 ne new3) { new LongLinkedTrieSetN4_1_3(this._1, new3) } else { this } } } } final private[immutable] class LongLinkedTrieSetN4_2_3( final val _2: LongLinkedTrieSetNode, final val _3: LongLinkedTrieSetNode ) extends LongLinkedTrieSetN4 { final override protected def _0: LongLinkedTrieSetNode = null final override protected def _1: LongLinkedTrieSetNode = null override def contains(v: Long, key: Long): Boolean = { (key & 3L) match { case 2L => _2.contains(v, key >> 2) case 3L => _3.contains(v, key >> 2) case _ => false } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => new LongLinkedTrieSetN4_0_1_2_3(l, null, this._2, this._3) case 1 => new LongLinkedTrieSetN4_0_1_2_3(null, l, this._2, this._3) case 2 => val new2 = _2.add(l, level + 2) if (_2 ne new2) { new LongLinkedTrieSetN4_2_3(new2, this._3) } else { this } case 3 => val new3 = _3.add(l, level + 2) if (_3 ne new3) { new LongLinkedTrieSetN4_2_3(this._2, new3) } else { this } } } } final private[immutable] class LongLinkedTrieSetN4_0_1_2_3( // least significant bits _ (current) second most important bit _ (current) most important bit final val _0: LongLinkedTrieSetNode, // a tree node, a leaf node or null final val _1: LongLinkedTrieSetNode, // a tree node, a leaf node or null final val _2: LongLinkedTrieSetNode, // a tree node, a leaf node or null final val _3: LongLinkedTrieSetNode // a tree node, a leaf node or null ) extends LongLinkedTrieSetN4 { override def contains(v: Long, key: Long): Boolean = { (key & 3L).toInt match { case 0 => _0 != null && _0.contains(v, key >> 2) case 1 => _1 != null && _1.contains(v, key >> 2) case 2 => _2 != null && _2.contains(v, key >> 2) case 3 => _3 != null && _3.contains(v, key >> 2) } } override def add(l: LongLinkedTrieSetL, level: Int): LongLinkedTrieSetNode = { // Basic assumption: the trie is nearly balanced... val consideredBits = ((l.value >> level) & 3L).toInt (consideredBits: @switch) match { case 0 => val _0 = this._0 if (_0 == null) { new LongLinkedTrieSetN4_0_1_2_3(l, this._1, this._2, this._3) } else { val new0 = _0.add(l, level + 2) if (_0 ne new0) { new LongLinkedTrieSetN4_0_1_2_3(new0, this._1, this._2, this._3) } else { this } } case 1 => val _1 = this._1 if (_1 == null) { new LongLinkedTrieSetN4_0_1_2_3(this._0, l, this._2, this._3) } else { val new1 = _1.add(l, level + 2) if (_1 ne new1) { new LongLinkedTrieSetN4_0_1_2_3(this._0, new1, this._2, this._3) } else { this } } case 2 => val _2 = this._2 if (_2 == null) { new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, l, this._3) } else { val new2 = _2.add(l, level + 2) if (_2 ne new2) { new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, new2, this._3) } else { this } } case 3 => val _3 = this._3 if (_3 == null) { new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, this._2, l) } else { val new3 = _3.add(l, level + 2) if (_3 ne new3) { new LongLinkedTrieSetN4_0_1_2_3(this._0, this._1, this._2, new3) } else { this } } } } } object LargeLongLinkedTrieSet { final val InitialBucketsCount = 8 def initialBucketsCount: Int = InitialBucketsCount } private[immutable] class LargeLongLinkedTrieSet( var size: Int = 0, // the length of the array must be a power of 2! val tries: Array[LongLinkedTrieSetNode] = new Array(LargeLongLinkedTrieSet.InitialBucketsCount), var l: LongLinkedTrieSetL = null // points to the latest element that was added... ) extends LongLinkedTrieSet { set => final override def +(v: Long): LargeLongLinkedTrieSet = { def split( newSize: Int, newL: LongLinkedTrieSetL, oldTrieId: Int, newTrie: LongLinkedTrieSetNode, bucketsCount: Int ): LargeLongLinkedTrieSet = { val thisTries = this.tries val lastOldTrieId = bucketsCount / 2 val targetTries = new Array[LongLinkedTrieSetNode](bucketsCount) val level = JInt.numberOfTrailingZeros(lastOldTrieId) var i = 0 while (i < lastOldTrieId) { val trie = if (i == oldTrieId) newTrie else thisTries(i) if (trie ne null) { targetTries(i) = trie.split_0(level) targetTries(i + lastOldTrieId) = trie.split_1(level) } i += 1 } new LargeLongLinkedTrieSet(newSize, targetTries, newL) } val tries = this.tries val triesLength = tries.length val trieId = v.toInt & (triesLength - 1) val oldTrie = tries(trieId) if (oldTrie == null) { val newSize = size + 1 val newL = new LongLinkedTrieSetL(v, this.l) newSize match { // 6 20 40 80 case 5 => split(newSize, newL, trieId, newL, 16) case 15 => split(newSize, newL, trieId, newL, 32) case 25 => split(newSize, newL, trieId, newL, 64) case 55 => split(newSize, newL, trieId, newL, 128) case _ => val newTries = tries.clone() newTries(trieId) = newL new LargeLongLinkedTrieSet(newSize, newTries, newL) } } else { val newL = new LongLinkedTrieSetL(v, this.l) val level = JInt.numberOfTrailingZeros(triesLength) val newTrie = oldTrie.add(newL, level) if (oldTrie ne newTrie) { val newSize = size + 1 newSize match { // IMPROVE: 5, 10, 20, 40, 80.... ? case 5 => //println(this) val updatedTrie = split(newSize, newL, trieId, newTrie, 16) //println("after split: "+updatedTrie) updatedTrie case 15 => //println(this) val updatedTrie = split(newSize, newL, trieId, newTrie, 32) //println("after split: "+updatedTrie) updatedTrie case 25 => //println(this) val updatedTrie = split(newSize, newL, trieId, newTrie, 64) //println("after split: "+updatedTrie) updatedTrie case 55 => split(newSize, newL, trieId, newTrie, 128) case _ => val newTries = tries.clone() newTries(trieId) = newTrie new LargeLongLinkedTrieSet(newSize, newTries, newL) } } else { this } } } final private[immutable] def +=(v: Long): Unit = { val tries = this.tries val triesLength = tries.length val trieId = v.toInt & (triesLength - 1) val oldTrie = tries(trieId) if (oldTrie == null) { val newL = new LongLinkedTrieSetL(v, this.l) tries(trieId) = newL this.l = newL size += 1 } else { val newL = new LongLinkedTrieSetL(v, this.l) val level = JInt.numberOfTrailingZeros(triesLength) val newTrie = oldTrie.add(newL, level) if (oldTrie ne newTrie) { tries(trieId) = newTrie this.l = newL size += 1 } } } final override def isEmpty: Boolean = size == 0 final override def isSingletonSet: Boolean = size == 1 final override def contains(v: Long): Boolean = { val tries = this.tries val triesLength = tries.length val trie = tries(v.toInt & (triesLength - 1)) if (trie == null) return false; trie.contains(v, key = v >> JInt.numberOfTrailingZeros(triesLength)) } final override def head: Long = { val thisL = this.l if (thisL eq null) throw new IllegalStateException("the set is empty"); this.l.value } final override def foreach[U](f: Long => U): Unit = { var currentL = set.l while (currentL ne null) { val v = currentL.value currentL = currentL.next f(v) } } final override def forall(p: Long => Boolean): Boolean = { var currentL = set.l while (currentL ne null) { val v = currentL.value currentL = currentL.next if (!p(v)) return false; } true } final override def foldLeft[T](op: T)(f: (T, Long) => T): T = { var r = op var currentL = set.l while (currentL ne null) { val v = currentL.value currentL = currentL.next r = f(r, v) } r } final override def forFirstN[U](n: Int)(f: Long => U): Unit = { var i = 0 var currentL = set.l while (i < n && (currentL ne null)) { val v = currentL.value currentL = currentL.next f(v) i += 1 } } final override def iterator: LongIterator = new LongIterator { private[this] var currentL = set.l override def hasNext: Boolean = currentL ne null override def next(): Long = { val v = currentL.value currentL = currentL.next v } } final override def equals(other: Any): Boolean = { other match { case that: LargeLongLinkedTrieSet => (this eq that) || { this.size == that.size && this.iterator.sameValues(that.iterator) } case _ => false } } final override def hashCode: Int = { iterator.foldLeft(0)((hashCode, v) => (hashCode * 31) + java.lang.Long.hashCode(v)) } final override def toString: String = { val tries = this.tries val triesLength = tries.length val bitsCount = JInt.numberOfTrailingZeros(triesLength) val triesString = tries. zipWithIndex. map { e => val (trie, index) = e s"[${index.toBinaryString.reverse.padTo(bitsCount, '0').reverse}] "+(if (trie ne null) trie.toString(0) else "N/A") }. mkString("\n") s"LongLinkedTrieSet(#$size,tries=\n$triesString\n)" } }