package immutable
- Alphabetic
- Public
- Protected
Type Members
- sealed abstract class BitArraySet extends BitSet
An immutable bit set for storing positive int values.
An immutable bit set for storing positive int values.
An array is used to store the underlying values. The empty bit set and sets where the maximum value is 64 use optimized representations.
- final class FilteredIntTrieSet extends IntTrieSet
- final case class IdentityPair[+T1 <: AnyRef, +T2 <: AnyRef](_1: T1, _2: T2) extends Product2[T1, T2] with Product with Serializable
Encapsulates a pair of values that is intended to be used as a key in Maps.
Encapsulates a pair of values that is intended to be used as a key in Maps. Compared to a standard pair (Tuple2), however, comparison of two
IdentityPair
objects is done by doing a reference-based comparison of the stored values.- _1
A reference value (can be
null
).- _2
A reference value (can be
null
).
val a = new String("fooBar") val b = "foo"+"Bar" val p1 = new IdentityPair(a,b) // #1 val p2 = new IdentityPair(a,a) // #2 val p3 = new IdentityPair(a,b) // #3 p1 == p2 // => false (though (a,b) == (a,a) would be true p1 == p3 // => true
Example: - sealed trait Int2List extends Serializable
A growable, immutable linked list based data store for int values except
Int.MinValue
.A growable, immutable linked list based data store for int values except
Int.MinValue
. 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 primitiveint
values which makes this list far more efficient when used for storing lists ofint
values. - final case class Int2ListNode(h: Int, t: Int, rest: Int2List = Int2ListEnd) extends Int2List with Product with Serializable
An container for a list element.
- sealed abstract class IntArraySet extends (Int) => Int with IntSet[IntArraySet] with IntCollectionWithStableOrdering[IntArraySet]
A sorted set of integer values backed by an ordered array to store the values; this guarantees log2(n) lookup.
- case class IntArraySet1(i: Int) extends IntArraySet with Product with Serializable
- class IntArraySetBuilder extends Builder[Int, IntArraySet]
- case class IntArraySetN extends IntArraySet with Product with Serializable
- final case class IntIntPair(_1: Int, _2: Int) extends Product with Serializable
An immutable pair of int values.
- sealed trait IntList extends Serializable
An immutable linked list for storing int values.
An immutable linked list for storing int 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 usewhile
loops for maximum efficiency. - final case class IntListNode(head: Int, rest: IntList = EmptyIntList) extends IntList with Product with Serializable
An container for a list element.
- final case class IntRefPair[+T](_1: Int, _2: T) extends Product2[Int, T] with Product with Serializable
A simple pairing of an int value and a reference value.
A simple pairing of an int value and a reference value.
- T
The type of the reference value.
- _1
The first value.
- _2
The second value.
- sealed abstract class IntTrieSet extends IntSet[IntTrieSet] with IntCollectionWithStableOrdering[IntTrieSet] with IntWorkSet[IntTrieSet]
An unordered set of integer values backed by a trie set.
An unordered set of integer values backed by a trie set. The branching is done using the least significant bit and values are only stored in leaf nodes. This ensure that we have a stable iteration order.
- final case class IntTrieSet1 extends IntTrieSetL with Product with Serializable
- class IntTrieSetBuilder extends Builder[Int, IntTrieSet]
- trait IntWorkSet[T <: IntWorkSet[T]] extends AnyRef
A set of integers which supports (reasonable) efficient
headAndTail
operations. - sealed abstract class Long2List extends Serializable
A growable, immutable linked list based data store for long values.
A growable, immutable linked list based data store for long values. 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 significantly and a simple foreach is also faster.
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 - trait LongLinkedSet extends LongSet
A set of long values.
- sealed abstract class LongLinkedTrieSet extends LongLinkedSet
An effectively immutable trie set of long values where the elements are sorted based on the insertion order.
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.
- final case class LongLinkedTrieSet1(v1: Long) extends LongLinkedTrieSet with Product with Serializable
- sealed trait LongList extends Serializable
An immutable linked list for storing long values.
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 usewhile
loops for maximum efficiency.- Note
In most cases a
LongList
can be used as a drop-in replacement for a standard Scala List.
- final case class LongListNode(head: Long, rest: LongList = LongList0) extends LongList with Product with Serializable
An container for a list element.
- final case class LongRefPair[+T](_1: Long, _2: T) extends Product with Serializable
A simple pairing of a long value and a reference value.
A simple pairing of a long value and a reference value.
- T
The type of the reference value.
- _1
The first value.
- _2
The second value.
- sealed abstract class LongTrieSet extends LongSet
- sealed abstract class LongTrieSetWithList extends LongLinkedSet
An immutable set of long values which maintains an additional list to enable an access of the values in insertion order (newest first).
An immutable set of long values which maintains an additional list to enable an access of the values in insertion order (newest first). Additionally, the list is used to provide more efficient iterate and foreach methods when compared to doing both on the underlying trie itself.
Compared to the LongLinkedTrieSet this implementation uses less memory and is faster to create; however, the LongLinkedTrieSet offers faster contains and foreach methods than this implementation. Hence, this representation is faster to create and requires significantly less memory. However, accessing the data structure is generally slower. (Internally every node in the trie uses a lookup table to determine the successor node w.r.t. the next bits of a value; this requires an indirection which costs time.)
- trait LongWorkSet[T <: LongWorkSet[T]] extends AnyRef
A set of longs which supports (reasonable) efficient
headAndTail
operations. - sealed abstract class NonEmptyUIDSet[T <: UID] extends UIDSet[T]
- sealed abstract class Ref2List[+T <: AnyRef] extends Serializable
A growable, immutable linked list based, data store for reference values except
null
.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 primitiveunsigned long
values which makes this list far more efficient when used for storing lists oflong
values. - final case class RefIntPair[+T](_1: T, _2: Int) extends Product2[T, Int] with Product with Serializable
A simple pairing of a reference value and an int value.
A simple pairing of a reference value and an int value.
- T
The type of the reference value.
- _1
The first value.
- _2
The second value.
- sealed abstract class UIDSet[T <: UID] extends Set[T] with StrictOptimizedSetOps[T, Set, UIDSet[T]]
An unordered trie-set based on the unique ids of the stored UID objects.
An unordered trie-set based on the unique ids of the stored UID objects. I.e., equality of two sets is defined in terms of the unique ids and not in terms of structural or reference equality of the stored elements.
Implementation
This trie set uses the least significant bit to decide whether the search is continued in the right or left branch.
Small sets are represented using a UIDSet0...3.
Compared to Scala's
Set
implementations in particular the tail and filter methods are much faster. - final case class UIDSet1[T <: UID](value: T) extends NonEmptyUIDSet[T] with Product with Serializable
- final class UIDSet2[T <: UID] extends NonEmptyUIDSet[T]
- final class UIDSet3[T <: UID] extends NonEmptyUIDSet[T]
- final class UIDSetInnerNode[T <: UID] extends UIDSetNodeLike[T]
- final class UIDSetLeaf[T <: UID] extends UIDSetNodeLike[T]
- sealed abstract class UIDTrieSet[T <: UID] extends AnyRef
A set of objects of type UID.
A set of objects of type UID. This set is defined over the ids of the objects and NOT over the objects themselves. I.e., at any given time no two different objects which have the same id, will be found in the set (provided that the ids are not changed after adding the object to this set, which is a pre-requisite.)
- Note
Though
equals
andhashCode
are implemented, comparing UID trie sets is still not efficient (n * log n) because the structure of the trie depends on the insertion order.
- final class UIDTrieSet1[T <: UID] extends UIDTrieSetLeaf[T]
- final class UShortPair extends AnyVal
A representation of a pair of unsigned short values.
A representation of a pair of unsigned short values.
scala> val p = org.opalj.collection.immutable.UShortPair(2323,332) p: org.opalj.collection.immutable.UShortPair = UShortPair(2323,332)
Example:
Value Members
- object BitArraySet
- case object EmptyIntArraySet extends IntArraySet with Product with Serializable
- case object EmptyIntList extends IntList with Product with Serializable
An empty IntList.
- case object EmptyIntTrieSet extends IntTrieSetL with Product with Serializable
- object Int2List extends Serializable
- case object Int2ListEnd extends Int2List with Product with Serializable
An empty Int2List.
- object IntArraySet
- object IntArraySetBuilder
- object IntList extends Serializable
- object IntTrieSet
Factory to create IntTrieSets.
- object IntTrieSet1 extends Serializable
- object LargeLongLinkedTrieSet
- object Long2List extends Serializable
- case object Long2List0 extends Long2List with Product with Serializable
An empty Long2List.
- object LongLinkedTrieSet
- case object LongLinkedTrieSet0 extends LongLinkedTrieSet with Product with Serializable
- object LongLinkedTrieSetN4
- object LongList extends Serializable
- case object LongList0 extends LongList with Product with Serializable
An empty LongList.
- object LongTrieSet
- object LongTrieSetWithList
- object Pair
- object Ref2List extends Serializable
- object UIDSet
- object UIDSet0 extends UIDSet[UID]
Represents the empty UIDSet.
- object UIDSet2
- object UIDTrieSet
Factory methods for creating UIDTrieSets.
- case object UIDTrieSet0 extends UIDTrieSetLeaf[UID] with Product with Serializable
- object UShortPair
Factory to create
UShortPair
objects.