This class implements mutable maps with AnyRef keys based on a hash table with open addressing.

Basic map operations on single entries, including contains and get, are typically significantly faster with AnyRefMap than HashMap. Note that numbers and characters are not handled specially in AnyRefMap; only plain equals and hashCode are used in comparisons.

Methods that traverse or regenerate the map, including foreach and map, are not in general faster than with HashMap. The methods foreachKey, foreachValue, mapValuesNow, and transformValues are, however, faster than alternative ways to achieve the same functionality.

Maps with open addressing may become less efficient at lookup after repeated addition/removal of elements. Although AnyRefMap makes a decent attempt to remain efficient regardless, calling repack on a map that will no longer have elements removed but will be used heavily may save both time and storage space.

This map is not intended to contain more than 2²⁹ entries (approximately 500 million). The maximum capacity is 2³⁰, but performance will degrade rapidly as 2³⁰ is approached.

An implementation of the Buffer class using an array to represent the assembled sequence internally. Append, update and random access take constant time (amortized time). Prepends and removes are linear in the buffer size.

A builder class for arrays.

An implementation of a double-ended queue that internally uses a resizable circular buffer.

Append, prepend, removeFirst, removeLast and random-access (indexed-lookup and indexed-replacement) take amortized constant time. In general, removals and insertions at i-th index are O(min(i, n-i)) and thus insertions and removals from end/beginning are fast.

A collection representing Array[T]. Unlike ArrayBuffer it is always backed by the same underlying Array, therefore it is not growable or shrinkable.

A class for mutable bitsets.

Bitsets are sets of non-negative integers which are represented as variable-size arrays of bits packed into 64-bit words. The lower bound of memory footprint of a bitset is determined by the largest number stored in it.

Base trait for collection builders.

After calling result() the behavior of a Builder (which is not also a scala.collection.mutable.ReusableBuilder) is undefined. No further methods should be called. It is common for mutable collections to be their own non-reusable Builder, in which case result() simply returns this.

A trait for cloneable collections.

This class implements mutable maps using a hashtable with red-black trees in the buckets for good worst-case performance on hash collisions. An Ordering is required for the element type. Equality as determined by the Ordering has to be consistent with equals and hashCode. Universal equality of numeric types is not supported (similar to AnyRefMap).

The canonical builder for collections that are growable, i.e. that support an efficient += method which adds an element to the collection.

GrowableBuilders can produce only a single instance of the collection they are growing.

This class implements mutable maps using a hashtable.

This class implements mutable sets using a hashtable.

This class implements mutable maps using a hashtable. The iterator and all traversal methods of this class visit elements in the order they were inserted.

This class implements mutable sets using a hashtable. The iterator and all traversal methods of this class visit elements in the order they were inserted.

A Buffer implementation backed by a list. It provides constant time prepend and append. Most other operations are linear.

This class implements mutable maps with Long keys based on a hash table with open addressing.

Basic map operations on single entries, including contains and get, are typically substantially faster with LongMap than HashMap. Methods that act on the whole map, including foreach and map are not in general expected to be faster than with a generic map, save for those that take particular advantage of the internal structure of the map: foreachKey, foreachValue, mapValuesNow, and transformValues.

Maps with open addressing may become less efficient at lookup after repeated addition/removal of elements. Although LongMap makes a decent attempt to remain efficient regardless, calling repack on a map that will no longer have elements removed but will be used heavily may save both time and storage space.

This map is not intended to contain more than 2^{29 entries (approximately 500 million). The maximum capacity is 2}30, but performance will degrade rapidly as 2^30 is approached.

A heap-based priority queue.

To prioritize elements of type A there must be an implicit Ordering[A] available at creation. Elements are retrieved in priority order by using dequeue or dequeueAll.

If multiple elements have the same priority as determined by the ordering for this PriorityQueue, no guarantees are made regarding the order in which those elements are returned by dequeue or dequeueAll. In particular, that means this class does not guarantee first-in-first-out behavior, as may be incorrectly inferred from the fact that this data structure is called a "queue".

Only the dequeue and dequeueAll methods will return elements in priority order (while removing elements from the heap). Standard collection methods such as drop, iterator, toList and toString use an arbitrary iteration order: they will traverse the heap or remove elements in whichever order seems most convenient.

Therefore, printing a PriorityQueue will not show elements in priority order, though the highest-priority element will be printed first. To print the elements in order, it's necessary to dequeue them. To do this non-destructively, duplicate the PriorityQueue first; the clone method is a suitable way to obtain a disposable copy.

Client keys are assumed to be immutable. Mutating keys may violate the invariant of the underlying heap-ordered tree. Note that clone does not rebuild the underlying tree.

scala> val pq = collection.mutable.PriorityQueue(1, 2, 5, 3, 7)
val pq: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue(7, 3, 5, 1, 2)

scala> pq.toList              // also not in order
val res0: List[Int] = List(7, 3, 5, 1, 2)

scala> pq.clone.dequeueAll
val res1: Seq[Int] = ArraySeq(7, 5, 3, 2, 1)

ReusableBuilder is a marker trait that indicates that a Builder can be reused to build more than one instance of a collection. In particular, calling result() followed by clear() will produce a collection and reset the builder to begin building a new collection of the same type.

In general no method other than clear() may be called after result(). It is up to subclasses to implement and to document other allowed sequences of operations (e.g. calling other methods after result() in order to obtain different snapshots of a collection under construction).

A generic trait for ordered mutable maps. Concrete classes have to provide functionality for the abstract methods in SeqMap.

Note that when checking for equality SeqMap does not take into account ordering.

A stack implements a data structure which allows to store and retrieve objects in a last-in-first-out (LIFO) fashion.

Note that operations which consume and produce iterables preserve order, rather than reversing it (as would be expected from building a new stack by pushing an element at a time).

A builder for mutable sequence of characters. This class provides an API mostly compatible with java.lang.StringBuilder, except where there are conflicts with the Scala collections API (such as the reverse method.)

This Builder can be reused after calling result() without an intermediate call to clear() in order to build multiple related results.

A mutable sorted map implemented using a mutable red-black tree as underlying data structure.

A mutable sorted set implemented using a mutable red-black tree as underlying data structure.

A buffer that stores elements in an unrolled linked list.

Unrolled linked lists store elements in linked fixed size arrays.

Unrolled buffers retain locality and low memory overhead properties of array buffers, but offer much more efficient element addition, since they never reallocate and copy the internal array.

However, they provide O(n/m) complexity random access, where n is the number of elements, and m the size of internal array chunks.

Ideal to use when:

• elements are added to the buffer and then all of the elements are traversed sequentially
• two unrolled buffers need to be concatenated (see concat)

Better than singly linked lists for random access, but should still be avoided for such a purpose.

A hash map with references to entries which are weakly reachable. Entries are removed from this map when the key is no longer (strongly) referenced. This class wraps java.util.WeakHashMap.

A simple mutable map backed by a list, so it preserves insertion order.

A trait for mutable maps with multiple values assigned to a key.

This class is typically used as a mixin. It turns maps which map K to Set[V] objects into multimaps that map K to V objects.

A mutable hash map based on an open addressing method. The precise scheme is undefined, but it should make a reasonable effort to ensure that an insert with consecutive hash codes is not unnecessarily penalised. In particular, mappings of consecutive integer keys should work without significant performance loss.