scala.collection.mutable

package mutable

Deprecated Value Members

object DoubleLinkedList extends SeqFactory[DoubleLinkedList] with Serializable

This object provides a set of operations to create DoubleLinkedList values.

object LinkedList extends SeqFactory[LinkedList] with Serializable

This object provides a set of operations to create LinkedList values.

Type Members

abstract class AbstractBuffer[A] extends AbstractSeq[A] with Buffer[A]

Explicit instantiation of the Buffer trait to reduce class file size in subclasses.

abstract class AbstractIterable[A] extends collection.AbstractIterable[A] with Iterable[A]

Explicit instantiation of the Iterable trait to reduce class file size in subclasses.

abstract class AbstractMap[A, B] extends collection.AbstractMap[A, B] with Map[A, B]

Explicit instantiation of the Map trait to reduce class file size in subclasses.

abstract class AbstractSeq[A] extends collection.AbstractSeq[A] with Seq[A]

Explicit instantiation of the Seq trait to reduce class file size in subclasses.

abstract class AbstractSet[A] extends AbstractIterable[A] with Set[A]

Explicit instantiation of the Set trait to reduce class file size in subclasses.

abstract class AbstractSortedMap[A, B] extends AbstractMap[A, B] with SortedMap[A, B]

Explicit instantiation of the SortedMap trait to reduce class file size in subclasses.

abstract class AbstractSortedSet[A] extends AbstractSet[A] with SortedSet[A]

Explicit instantiation of the SortedSet trait to reduce class file size in subclasses.

final class AnyRefMap[K <: AnyRef, V] extends AbstractMap[K, V] with Map[K, V] with MapLike[K, V, AnyRefMap[K, V]] with Serializable

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 29 entries (approximately 500 million). The maximum capacity is 2 30, but performance will degrade rapidly as 2 30 is approached.

class ArrayBuffer[A] extends AbstractBuffer[A] with Buffer[A] with GenericTraversableTemplate[A, ArrayBuffer] with BufferLike[A, ArrayBuffer[A]] with IndexedSeqOptimized[A, ArrayBuffer[A]] with Builder[A, ArrayBuffer[A]] with ResizableArray[A] with CustomParallelizable[A, ParArray[A]] with Serializable

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.

abstract class ArrayBuilder[T] extends ReusableBuilder[T, Array[T]] with Serializable

A builder class for arrays.

trait ArrayLike[A, +Repr] extends IndexedSeqOptimized[A, Repr]

A common supertrait of ArrayOps and WrappedArray that factors out the deep method for arrays and wrapped arrays and serves as a marker trait for array wrappers.

trait ArrayOps[T] extends ArrayLike[T, Array[T]] with CustomParallelizable[T, ParArray[T]]

This class serves as a wrapper for Array s with all the operations found in indexed sequences. Where needed, instances of arrays are implicitly converted into this class.

The difference between this class and WrappedArray is that calling transformer methods such as filter and map will yield an array, whereas a WrappedArray will remain a WrappedArray .

class ArraySeq[A] extends AbstractSeq[A] with IndexedSeq[A] with GenericTraversableTemplate[A, ArraySeq] with IndexedSeqOptimized[A, ArraySeq[A]] with CustomParallelizable[A, ParArray[A]] with Serializable

A class for polymorphic arrays of elements that’s represented internally by an array of objects. This means that elements of primitive types are boxed.

class ArrayStack[T] extends AbstractSeq[T] with IndexedSeq[T] with IndexedSeqLike[T, ArrayStack[T]] with GenericTraversableTemplate[T, ArrayStack] with IndexedSeqOptimized[T, ArrayStack[T]] with Cloneable[ArrayStack[T]] with Builder[T, ArrayStack[T]] with Serializable

Simple stack class backed by an array. Should be significantly faster than the standard mutable stack.

class BitSet extends AbstractSet[Int] with SortedSet[Int] with collection.BitSet with BitSetLike[BitSet] with SetLike[Int, BitSet] with Serializable

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 memory footprint of a bitset is determined by the largest number stored in it.

trait Buffer[A] extends Seq[A] with GenericTraversableTemplate[A, Buffer] with BufferLike[A, Buffer[A]] with scala.Cloneable

Buffers are used to create sequences of elements incrementally by appending, prepending, or inserting new elements. It is also possible to access and modify elements in a random access fashion via the index of the element in the current sequence.

trait BufferLike[A, +This <: BufferLike[A, This] with Buffer[A]] extends Growable[A] with Shrinkable[A] with Scriptable[A] with Subtractable[A, This] with SeqLike[A, This] with scala.Cloneable

A template trait for buffers of type Buffer[A] .

Buffers are used to create sequences of elements incrementally by appending, prepending, or inserting new elements. It is also possible to access and modify elements in a random access fashion via the index of the element in the current sequence.

  • A
    • the type of the elements of the buffer
  • This
    • the type of the buffer itself.
  • Self Type
    • This
  • Source
  • Version
    • 2.8
  • Since
    • 2.8
  • Note
    • This trait provides most of the operations of a Buffer independently of its representation. It is typically inherited by concrete implementations of buffers. To implement a concrete buffer, you need to provide implementations of the following methods:
    def apply(idx: Int): A
    def update(idx: Int, elem: A)
    def length: Int
    def clear()
    def +=(elem: A): this.type
    def +=:(elem: A): this.type
    def insertAll(n: Int, iter: Traversable[A])
    def remove(n: Int): A
    

trait BufferProxy[A] extends Buffer[A] with Proxy

This is a simple proxy class for scala.collection.mutable.Buffer. It is most useful for assembling customized set abstractions dynamically using object composition and forwarding.

  • A
    • type of the elements the buffer proxy contains.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Proxying is deprecated due to lack of use and compiler-level support.
  • Source
  • Version
    • 1.0, 16/04/2004
  • Since
    • 1

trait Builder[-Elem, +To] extends Growable[Elem]

The base trait of all builders. A builder lets one construct a collection incrementally, by adding elements to the builder with += and then converting to the required collection type with result .

One cannot assume that a single Builder can build more than one instance of the desired collection. Particular subclasses may allow such behavior. Otherwise, result should be treated as a terminal operation: after it is called, no further methods should be called on the builder. Extend the collection.mutable.ReusableBuilder trait instead of Builder for builders that may be reused to build multiple instances.

trait Cloneable[+A <: AnyRef] extends scala.Cloneable

A trait for cloneable collections.

final class DefaultEntry[A, B] extends HashEntry[A, DefaultEntry[A, B]] with Serializable

Class used internally for default map model.

trait DefaultMapModel[A, B] extends Map[A, B]

This class is used internally. It implements the mutable Map class in terms of three functions: findEntry , addEntry , and entries .

class DoubleLinkedList[A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, DoubleLinkedList] with DoubleLinkedListLike[A, DoubleLinkedList[A]] with Serializable

This class implements double linked lists where both the head ( elem ), the tail ( next ) and a reference to the previous node ( prev ) are mutable.

trait DoubleLinkedListLike[A, This <: Seq[A] with DoubleLinkedListLike[A, This]] extends SeqLike[A, This] with LinkedListLike[A, This]

This extensible class may be used as a basis for implementing double linked lists. Type variable A refers to the element type of the list, type variable This is used to model self types of linked lists.

The invariant of this data structure is that prev is always a reference to the previous node in the list. If this is the first node of the list, prev will be null . Field next is set to this iff the list is empty.

Examples (right arrow represents next , left arrow represents prev , _ represents no value):

```scala Empty:

null <– [ _ ] –, [ ] <-`

Single element:

null <– [ x ] –> [ _ ] –, [ ] <– [ ] <-`

More elements:

null <– [ x ] –> [ y ] –> [ z ] –> [ _ ] –, [ ] <– [ ] <– [ ] <– [ ] <- ``

  • A
    • type of the elements contained in the double linked list
  • This
    • the type of the actual linked list holding the elements
  • Self Type
    • DoubleLinkedListLike [A, This]
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Low-level linked lists are deprecated due to idiosyncrasies in interface and incomplete features.
  • Source
  • Version
    • 1.0, 08/07/2003
  • Since
    • 2.8

trait FlatHashTable[A] extends HashUtils[A]

An implementation class backing a HashSet .

This trait is used internally. It can be mixed in with various collections relying on hash table as an implementation.

class GrowingBuilder[Elem, To <: Growable[Elem]] extends Builder[Elem, To]

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.

trait HashEntry[A, E] extends AnyRef

Class used internally.

class HashMap[A, B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, HashMap[A, B]] with HashTable[A, DefaultEntry[A, B]] with CustomParallelizable[(A, B), ParHashMap[A, B]] with Serializable

This class implements mutable maps using a hashtable.

class HashSet[A] extends AbstractSet[A] with Set[A] with GenericSetTemplate[A, HashSet] with SetLike[A, HashSet[A]] with FlatHashTable[A] with CustomParallelizable[A, ParHashSet[A]] with Serializable

This class implements mutable sets using a hashtable.

trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashUtils[A]

This class can be used to construct data structures that are based on hashtables. Class HashTable[A] implements a hashtable that maps keys of type A to values of the fully abstract member type Entry . Classes that make use of HashTable have to provide an implementation for Entry .

There are mainly two parameters that affect the performance of a hashtable: the initial size and the load factor . The size refers to the number of _ buckets_ in the hashtable, and the load factor is a measure of how full the hashtable is allowed to get before its size is automatically doubled. Both parameters may be changed by overriding the corresponding values in class HashTable .

class History[Evt, Pub] extends AbstractIterable[(Pub, Evt)] with Subscriber[Evt, Pub] with Iterable[(Pub, Evt)] with Serializable

History[A, B] objects may subscribe to events of type A published by an object of type B . The history subscriber object records all published events up to maximum number of maxHistory events.

class ImmutableMapAdaptor[A, B] extends AbstractMap[A, B] with Map[A, B] with Serializable

This class can be used as an adaptor to create mutable maps from immutable map implementations. Only method empty has to be redefined if the immutable map on which this mutable map is originally based is not empty. empty is supposed to return the representation of an empty map.

class ImmutableSetAdaptor[A] extends AbstractSet[A] with Set[A] with Serializable

This class can be used as an adaptor to create mutable sets from immutable set implementations. Only method empty has to be redefined if the immutable set on which this mutable set is originally based is not empty. empty is supposed to return the representation of an empty set.

trait IndexedSeq[A] extends Seq[A] with collection.IndexedSeq[A] with GenericTraversableTemplate[A, IndexedSeq] with IndexedSeqLike[A, IndexedSeq[A]]

A subtrait of collection.IndexedSeq which represents sequences that can be mutated.

trait IndexedSeqLike[A, +Repr] extends collection.IndexedSeqLike[A, Repr]

A subtrait of scala.collection.IndexedSeq which represents sequences that can be mutated.

It declares a method update which allows updating an element at a specific index in the sequence.

This trait just implements iterator in terms of apply and length . However, see IndexedSeqOptimized for an implementation trait that overrides operations to make them run faster under the assumption of fast random access with apply .

trait IndexedSeqOptimized[A, +Repr] extends IndexedSeqLike[A, Repr] with collection.IndexedSeqOptimized[A, Repr]

A subtrait of scala.collection.IndexedSeq which represents sequences that can be mutated.

trait IndexedSeqView[A, +Coll] extends IndexedSeq[A] with IndexedSeqOptimized[A, IndexedSeqView[A, Coll]] with SeqView[A, Coll] with SeqViewLike[A, Coll, IndexedSeqView[A, Coll]]

A non-strict view of a mutable IndexedSeq .

A view is a lazy version of some collection. Collection transformers such as map or filter or ++ do not traverse any elements when applied on a view. Instead they create a new view which simply records that fact that the operation needs to be applied. The collection elements are accessed, and the view operations are applied, when a non-view result is needed, or when the force method is called on a view. Some of the operations of this class will yield again a mutable indexed sequence, others will just yield a plain indexed sequence of type collection.IndexedSeq . Because this is a leaf class there is no associated Like class.

trait Iterable[A] extends Traversable[A] with collection.Iterable[A] with GenericTraversableTemplate[A, Iterable] with IterableLike[A, Iterable[A]] with Parallelizable[A, ParIterable[A]]

A base trait for iterable collections that can be mutated.

This is a base trait for all mutable Scala collections that define an iterator method to step through one-by-one the collection’s elements. Implementations of this trait need to provide a concrete method with signature:

def iterator: Iterator[A]

They also need to provide a method newBuilder which creates a builder for collections of the same kind.

This trait implements Iterable ‘s foreach method by stepping through all elements using iterator . Subclasses should re-implement foreach with something more efficient, if possible.

This trait adds methods iterator , sameElements , takeRight , dropRight to the methods inherited from trait Traversable.

Note: This trait replaces every method that uses break in TraversableLike by an iterator version.

abstract class LazyBuilder[Elem, +To] extends ReusableBuilder[Elem, To]

A builder that constructs its result lazily. Iterators or iterables to be added to this builder with ++= are not evaluated until result is called.

This builder can be reused.

trait LinearSeq[A] extends Seq[A] with collection.LinearSeq[A] with GenericTraversableTemplate[A, LinearSeq] with LinearSeqLike[A, LinearSeq[A]]

A subtrait of collection.LinearSeq which represents sequences that can be mutated.

Linear sequences have reasonably efficient head , tail , and isEmpty methods. If these methods provide the fastest way to traverse the collection, a collection Coll that extends this trait should also extend LinearSeqOptimized[A, Coll[A]] .

final class LinkedEntry[A, B] extends HashEntry[A, LinkedEntry[A, B]] with Serializable

Class for the linked hash map entry, used internally.

class LinkedHashMap[A, B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, LinkedHashMap[A, B]] with HashTable[A, LinkedEntry[A, B]] with Serializable

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.

class LinkedHashSet[A] extends AbstractSet[A] with Set[A] with GenericSetTemplate[A, LinkedHashSet] with SetLike[A, LinkedHashSet[A]] with HashTable[A, Entry[A]] with Serializable

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.

class LinkedList[A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, LinkedList] with LinkedListLike[A, LinkedList[A]] with Serializable

A more traditional/primitive style of linked list where the “list” is also the “head” link. Links can be manually created and manipulated, though the use of the API, when possible, is recommended.

The danger of directly manipulating next:

scala> val b = LinkedList(1)
b: scala.collection.mutable.LinkedList[Int] = LinkedList(1)

scala> b.next = null

scala> println(b)
java.lang.NullPointerException

If the list is empty next must be set to this . The last node in every mutable linked list is empty.

Examples ( _ represents no value):

```scala Empty:

[ _ ] –, [ ] <-`

Single element:

[ x ] –> [ _ ] –, [ ] <-`

More elements:

[ x ] –> [ y ] –> [ z ] –> [ _ ] –, [ ] <- ``

trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends SeqLike[A, This]

This extensible class may be used as a basis for implementing linked list. Type variable A refers to the element type of the list, type variable This is used to model self types of linked lists.

If the list is empty next must be set to this . The last node in every mutable linked list is empty.

Examples ( _ represents no value):

```scala Empty:

[ _ ] –, [ ] <-`

Single element:

[ x ] –> [ _ ] –, [ ] <-`

More elements:

[ x ] –> [ y ] –> [ z ] –> [ _ ] –, [ ] <- ``

  • A
    • type of the elements contained in the linked list
  • This
    • the type of the actual linked list holding the elements
  • Self Type
    • LinkedListLike [A, This]
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Low-level linked lists are deprecated due to idiosyncrasies in interface and incomplete features.
  • Source
  • Version
    • 1.0, 08/07/2003
  • Since
    • 2.8

final class ListBuffer[A] extends AbstractBuffer[A] with Buffer[A] with GenericTraversableTemplate[A, ListBuffer] with BufferLike[A, ListBuffer[A]] with ReusableBuilder[A, immutable.List[A]] with SeqForwarder[A] with Serializable

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

class ListMap[A, B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, ListMap[A, B]] with Serializable

A simple mutable map backed by a list.

final class LongMap[V] extends AbstractMap[Long, V] with Map[Long, V] with MapLike[Long, V, LongMap[V]] with Serializable

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.

trait Map[A, B] extends Iterable[(A, B)] with collection.Map[A, B] with MapLike[A, B, Map[A, B]]

A base trait for maps that can be mutated.

Implementation note: This trait provides most of the operations of a mutable Map independently of its representation. It is typically inherited by concrete implementations of maps.

To implement a concrete mutable map, you need to provide implementations of the following methods:

def get(key: A): Option[B]
def iterator: Iterator[(A, B)]
def += (kv: (A, B)): This
def -= (key: A): This

If you wish that methods like take , drop , filter also return the same kind of map you should also override:

def empty: This

It is also good idea to override methods foreach and size for efficiency.

class MapBuilder[A, B, Coll <: GenMap[A, B] with GenMapLike[A, B, Coll]] extends ReusableBuilder[(A, B), Coll]

The canonical builder for immutable maps, working with the map’s + method to add new elements. Collections are built from their empty element using this + method.

trait MapLike[A, B, +This <: MapLike[A, B, This] with Map[A, B]] extends collection.MapLike[A, B, This] with Builder[(A, B), This] with Growable[(A, B)] with Shrinkable[A] with Cloneable[This] with Parallelizable[(A, B), ParMap[A, B]]

A template trait for mutable maps.

Implementation note: This trait provides most of the operations of a mutable Map independently of its representation. It is typically inherited by concrete implementations of maps.

To implement a concrete mutable map, you need to provide implementations of the following methods:

def get(key: A): Option[B]
def iterator: Iterator[(A, B)]
def += (kv: (A, B)): This
def -= (key: A): This

If you wish that methods like take , drop , filter also return the same kind of map you should also override:

def empty: This

It is also good idea to override methods foreach and size for efficiency.

trait MapProxy[A, B] extends Map[A, B] with MapProxyLike[A, B, Map[A, B]]

This trait implements a proxy for scala.collection.mutable.Map.

It is most useful for assembling customized map abstractions dynamically using object composition and forwarding.

trait MultiMap[A, B] extends Map[A, Set[B]]

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 A to Set[B] objects into multimaps that map A to B objects.

Example:

scala // first import all necessary types from package `collection.mutable` import collection.mutable.{ HashMap, MultiMap, Set } // to create a `MultiMap` the easiest way is to mixin it into a normal // `Map` instance val mm = new HashMap[Int, Set[String]] with MultiMap[Int, String] // to add key-value pairs to a multimap it is important to use // the method `addBinding` because standard methods like `+` will // overwrite the complete key-value pair instead of adding the // value to the existing key mm.addBinding(1, "a") mm.addBinding(2, "b") mm.addBinding(1, "c") // mm now contains `Map(2 -> Set(b), 1 -> Set(c, a))` // to check if the multimap contains a value there is method // `entryExists`, which allows to traverse the including set mm.entryExists(1, _ == "a") == true mm.entryExists(1, _ == "b") == false mm.entryExists(2, _ == "b") == true // to remove a previous added value there is the method `removeBinding` mm.removeBinding(1, "a") mm.entryExists(1, _ == "a") == false

class MutableList[A] extends AbstractSeq[A] with LinearSeq[A] with LinearSeqOptimized[A, MutableList[A]] with GenericTraversableTemplate[A, MutableList] with Builder[A, MutableList[A]] with Serializable

This class is used internally to represent mutable lists. It is the basis for the implementation of the class Queue .

trait ObservableBuffer[A] extends Buffer[A] with Publisher[Message[A] with Undoable]

This class is typically used as a mixin. It adds a subscription mechanism to the Buffer class into which this abstract class is mixed in. Class ObservableBuffer publishes events of the type Message .

trait ObservableMap[A, B] extends Map[A, B] with Publisher[Message[(A, B)] with Undoable]

This class is typically used as a mixin. It adds a subscription mechanism to the Map class into which this abstract class is mixed in. Class ObservableMap publishes events of the type Message .

trait ObservableSet[A] extends Set[A] with Publisher[Message[A] with Undoable]

This class is typically used as a mixin. It adds a subscription mechanism to the Set class into which this abstract class is mixed in. Class ObservableSet publishes events of the type Message .

class OpenHashMap[Key, Value] extends AbstractMap[Key, Value] with Map[Key, Value] with MapLike[Key, Value, OpenHashMap[Key, Value]]

A mutable hash map based on an open hashing scheme. 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.

class PriorityQueue[A] extends AbstractIterable[A] with Iterable[A] with GenericOrderedTraversableTemplate[A, PriorityQueue] with IterableLike[A, PriorityQueue[A]] with Growable[A] with Builder[A, PriorityQueue[A]] with Serializable with scala.Cloneable

This class implements priority queues using a heap. To prioritize elements of type A there must be an implicit Ordering[A] available at creation.

Only the dequeue and dequeueAll methods will return elements in priority order (while removing elements from the heap). Standard collection methods including drop , iterator , and toString will remove or traverse the heap in whichever order seems most convenient.

Therefore, printing a PriorityQueue will not reveal the priority order of the elements, though the highest-priority element will be printed first. To print the elements in order, one must duplicate the PriorityQueue (by using clone , for instance) and then dequeue them:

Example:

val pq = collection.mutable.PriorityQueue(1, 2, 5, 3, 7)
println(pq)                  // elements probably not in order
println(pq.clone.dequeueAll) // prints Vector(7, 5, 3, 2, 1)

abstract class PriorityQueueProxy[A] extends PriorityQueue[A] with Proxy

This class servers as a proxy for priority queues. The elements of the queue have to be ordered in terms of the Ordered[T] class.

trait Publisher[Evt] extends AnyRef

Publisher[A,This] objects publish events of type A to all registered subscribers. When subscribing, a subscriber may specify a filter which can be used to constrain the number of events sent to the subscriber. Subscribers may suspend their subscription, or reactivate a suspended subscription. Class Publisher is typically used as a mixin. The abstract type Pub models the type of the publisher itself.

class Queue[A] extends MutableList[A] with LinearSeqOptimized[A, Queue[A]] with GenericTraversableTemplate[A, Queue] with Cloneable[Queue[A]] with Serializable

Queue objects implement data structures that allow to insert and retrieve elements in a first-in-first-out (FIFO) manner.

trait QueueProxy[A] extends Queue[A] with Proxy

Queue objects implement data structures that allow to insert and retrieve elements in a first-in-first-out (FIFO) manner.

  • A
    • type of the elements in this queue proxy.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Proxying is deprecated due to lack of use and compiler-level support.
  • Source
  • Version
    • 1.1, 03/05/2004
  • Since
    • 1

trait ResizableArray[A] extends IndexedSeq[A] with GenericTraversableTemplate[A, ResizableArray] with IndexedSeqOptimized[A, ResizableArray[A]]

This class is used internally to implement data structures that are based on resizable arrays.

trait ReusableBuilder[-Elem, +To] extends Builder[Elem, To]

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.

It is up to subclasses to implement this behavior, and to document any other behavior that varies from standard ReusableBuilder usage (e.g. operations being well-defined after a call to result , or allowing multiple calls to result to obtain different snapshots of a collection under construction).

class RevertibleHistory[Evt <: Undoable, Pub] extends History[Evt, Pub] with Undoable with Serializable

A revertible history is a History object which supports an undo operation. Type variable Evt refers to the type of the published events, Pub denotes the publisher type. Type Pub is typically a subtype of Publisher .

trait Seq[A] extends Iterable[A] with collection.Seq[A] with GenericTraversableTemplate[A, Seq] with SeqLike[A, Seq[A]]

A subtrait of collection.Seq which represents sequences that can be mutated.

Sequences are special cases of iterable collections of class Iterable . Unlike iterables, sequences always have a defined order of elements. Sequences provide a method apply for indexing. Indices range from 0 up to the length of a sequence. Sequences support a number of methods to find occurrences of elements or subsequences, including segmentLength , prefixLength , indexWhere , indexOf , lastIndexWhere , lastIndexOf , startsWith , endsWith , indexOfSlice .

Another way to see a sequence is as a PartialFunction from Int values to the element type of the sequence. The isDefinedAt method of a sequence returns true for the interval from 0 until length .

Sequences can be accessed in reverse order of their elements, using methods reverse and reverseIterator .

Sequences have two principal subtraits, IndexedSeq and LinearSeq , which give different guarantees for performance. An IndexedSeq provides fast random-access of elements and a fast length operation. A LinearSeq provides fast access only to the first element via head , but also has a fast tail operation.

The class adds an update method to collection.Seq .

trait SeqLike[A, +This <: SeqLike[A, This] with Seq[A]] extends collection.SeqLike[A, This] with Cloneable[This] with Parallelizable[A, ParSeq[A]]

A template trait for mutable sequences of type mutable.Seq[A] .

trait Set[A] extends Iterable[A] with collection.Set[A] with GenericSetTemplate[A, Set] with SetLike[A, Set[A]]

A generic trait for mutable sets.

To implement a concrete mutable set, you need to provide implementations of the following methods:

def contains(elem: A): Boolean
def iterator: Iterator[A]
def += (elem: A): this.type
def -= (elem: A): this.type

If you wish that methods like take , drop , filter return the same kind of set, you should also override:

def empty: This

It is also good idea to override methods foreach and size for efficiency.

class SetBuilder[A, Coll <: collection.Set[A] with collection.SetLike[A, Coll]] extends ReusableBuilder[A, Coll]

The canonical builder for mutable Sets.

trait SetLike[A, +This <: SetLike[A, This] with Set[A]] extends collection.SetLike[A, This] with Scriptable[A] with Builder[A, This] with Growable[A] with Shrinkable[A] with Cloneable[Set[A]] with Parallelizable[A, ParSet[A]]

A template trait for mutable sets of type mutable.Set[A] .

This trait provides most of the operations of a mutable.Set independently of its representation. It is typically inherited by concrete implementations of sets.

To implement a concrete mutable set, you need to provide implementations of the following methods:

def contains(elem: A): Boolean
def iterator: Iterator[A]
def += (elem: A): this.type
def -= (elem: A): this.type

If you wish that methods like take , drop , filter return the same kind of set, you should also override:

def empty: This

It is also good idea to override methods foreach and size for efficiency.

trait SetProxy[A] extends Set[A] with SetProxyLike[A, Set[A]]

This is a simple wrapper class for scala.collection.mutable.Set. It is most useful for assembling customized set abstractions dynamically using object composition and forwarding.

trait SortedMap[A, B] extends Map[A, B] with collection.SortedMap[A, B] with MapLike[A, B, SortedMap[A, B]] with SortedMapLike[A, B, SortedMap[A, B]]

A mutable map whose keys are sorted.

trait SortedSet[A] extends collection.SortedSet[A] with SortedSetLike[A, SortedSet[A]] with Set[A] with SetLike[A, SortedSet[A]]

Base trait for mutable sorted set.

class Stack[A] extends AbstractSeq[A] with Seq[A] with SeqLike[A, Stack[A]] with GenericTraversableTemplate[A, Stack] with Cloneable[Stack[A]] with Serializable

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

trait StackProxy[A] extends Stack[A] with Proxy

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

  • A
    • type of the elements in this stack proxy.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Proxying is deprecated due to lack of use and compiler-level support.
  • Source
  • Version
    • 1.0, 10/05/2004
  • Since
    • 1

final class StringBuilder extends AbstractSeq[Char] with CharSequence with IndexedSeq[Char] with StringLike[StringBuilder] with ReusableBuilder[Char, String] with Serializable

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.)

trait Subscriber[-Evt, -Pub] extends AnyRef

Subscriber[A, B] objects may subscribe to events of type A published by an object of type B . B is typically a subtype of scala.collection.mutable.Publisher.

trait SynchronizedBuffer[A] extends Buffer[A]

This class should be used as a mixin. It synchronizes the Buffer methods of the class into which it is mixed in.

  • A
    • type of the elements contained in this buffer.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Synchronization via traits is deprecated as it is inherently unreliable. Consider java.util.concurrent.ConcurrentLinkedQueue as an alternative.
  • Source
  • Version
    • 1.0, 08/07/2003
  • Since
    • 1

trait SynchronizedMap[A, B] extends Map[A, B]

This class should be used as a mixin. It synchronizes the Map functions of the class into which it is mixed in.

  • A
    • type of the keys contained in this map.
  • B
    • type of the values associated with keys.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Synchronization via traits is deprecated as it is inherently unreliable. Consider java.util.concurrent.ConcurrentHashMap as an alternative.
  • Source
  • Version
    • 2.0, 31/12/2006
  • Since
    • 1

class SynchronizedPriorityQueue[A] extends PriorityQueue[A]

This class implements synchronized priority queues using a binary heap. The elements of the queue have to be ordered in terms of the Ordered[T] class.

  • A
    • type of the elements contained in this synchronized priority queue
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Comprehensive synchronization via selective overriding of methods is inherently unreliable. Consider java.util.concurrent.ConcurrentSkipListSet as an alternative.
  • Source
  • Version
    • 1.0, 03/05/2004
  • Since
    • 1

class SynchronizedQueue[A] extends Queue[A]

This is a synchronized version of the Queue[T] class. It implements a data structure that allows one to insert and retrieve elements in a first-in-first-out (FIFO) manner.

  • A
    • type of elements contained in this synchronized queue.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Synchronization via selective overriding of methods is inherently unreliable. Consider java.util.concurrent.ConcurrentLinkedQueue as an alternative.
  • Source
  • Version
    • 1.0, 03/05/2004
  • Since
    • 1

trait SynchronizedSet[A] extends Set[A]

This class should be used as a mixin. It synchronizes the Set functions of the class into which it is mixed in.

  • A
    • type of the elements contained in this synchronized set.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Synchronization via traits is deprecated as it is inherently unreliable. Consider java.util.concurrent.ConcurrentHashMap[A,Unit] as an alternative.
  • Source
  • Version
    • 1.0, 08/07/2003
  • Since
    • 1

class SynchronizedStack[A] extends Stack[A]

This is a synchronized version of the Stack[T] class. It implements a data structure which allows to store and retrieve objects in a last-in-first-out (LIFO) fashion.

  • A
    • type of the elements contained in this stack.
  • Annotations
    • @ deprecated
  • Deprecated
    • (Since version 2.11.0) Synchronization via selective overriding of methods is inherently unreliable. Consider java.util.concurrent.LinkedBlockingDequeue instead.
  • Source
  • Version
    • 1.0, 03/05/2004
  • Since
    • 1

trait Traversable[A] extends collection.Traversable[A] with GenericTraversableTemplate[A, Traversable] with TraversableLike[A, Traversable[A]] with Mutable

A trait for traversable collections that can be mutated.

This is a base trait of all kinds of mutable Scala collections. It implements the behavior common to all collections, in terms of a method foreach with signature:

def foreach[U](f: Elem => U): Unit

Collection classes mixing in this trait provide a concrete foreach method which traverses all the elements contained in the collection, applying a given function to each. They also need to provide a method newBuilder which creates a builder for collections of the same kind.

A traversable class might or might not have two properties: strictness and orderedness. Neither is represented as a type.

The instances of a strict collection class have all their elements computed before they can be used as values. By contrast, instances of a non-strict collection class may defer computation of some of their elements until after the instance is available as a value. A typical example of a non-strict collection class is a scala.collection.immutable.Stream. A more general class of examples are TraversableViews .

If a collection is an instance of an ordered collection class, traversing its elements with foreach will always visit elements in the same order, even for different runs of the program. If the class is not ordered, foreach can visit elements in different orders for different runs (but it will keep the same order in the same run).’

A typical example of a collection class which is not ordered is a HashMap of objects. The traversal order for hash maps will depend on the hash codes of its elements, and these hash codes might differ from one run to the next. By contrast, a LinkedHashMap is ordered because its foreach method visits elements in the order they were inserted into the HashMap .

sealed class TreeMap[A, B] extends AbstractSortedMap[A, B] with SortedMap[A, B] with MapLike[A, B, TreeMap[A, B]] with SortedMapLike[A, B, TreeMap[A, B]] with Serializable

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

sealed class TreeSet[A] extends AbstractSortedSet[A] with SortedSet[A] with SetLike[A, TreeSet[A]] with SortedSetLike[A, TreeSet[A]] with Serializable

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

trait Undoable extends AnyRef

Classes that mix in the Undoable class provide an operation undo which can be used to undo the last operation.

class UnrolledBuffer[T] extends AbstractBuffer[T] with Buffer[T] with BufferLike[T, UnrolledBuffer[T]] with GenericClassTagTraversableTemplate[T, UnrolledBuffer] with Builder[T, UnrolledBuffer[T]] with Serializable

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.

class WeakHashMap[A, B] extends convert.Wrappers.JMapWrapper[A, B] with convert.Wrappers.JMapWrapperLike[A, B, WeakHashMap[A, B]]

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 .

abstract class WrappedArray[T] extends AbstractSeq[T] with IndexedSeq[T] with ArrayLike[T, WrappedArray[T]] with CustomParallelizable[T, ParArray[T]]

A class representing Array[T] .

class WrappedArrayBuilder[A] extends ReusableBuilder[A, WrappedArray[A]]

A builder class for arrays.

This builder can be reused.

Value Members

object AnyRefMap extends Serializable

object ArrayBuffer extends SeqFactory[ArrayBuffer] with Serializable

Factory object for the ArrayBuffer class.

This object provides a set of operations to create ArrayBuffer values.

object ArrayBuilder extends Serializable

A companion object for array builders.

object ArrayOps

A companion object for ArrayOps .

object ArraySeq extends SeqFactory[ArraySeq] with Serializable

This object provides a set of operations to create ArraySeq values.

object ArrayStack extends SeqFactory[ArrayStack] with Serializable

Factory object for the ArrayStack class.

This object provides a set of operations to create ArrayStack values.

object BitSet extends BitSetFactory[BitSet] with Serializable

This object provides a set of operations to create BitSet values.

object Buffer extends SeqFactory[Buffer]

This object provides a set of operations to create Buffer values.

object HashMap extends MutableMapFactory[HashMap] with Serializable

This object provides a set of operations needed to create mutable.HashMap values.

object HashSet extends MutableSetFactory[HashSet] with Serializable

This object provides a set of operations needed to create mutable.HashSet values.

object IndexedSeq extends SeqFactory[IndexedSeq]

This object provides a set of operations to create mutable.IndexedSeq values. The current default implementation of a mutable.IndexedSeq is an ArrayBuffer .

object IndexedSeqView

An object containing the necessary implicit definitions to make SeqView s work. Its definitions are generally not accessed directly by clients.

Note that the canBuildFrom factories yield SeqView s, not IndexedSeqView s. This is intentional, because not all operations yield again a mutable.IndexedSeqView . For instance, map just gives a SeqView , which reflects the fact that map cannot do its work and maintain a pointer into the original indexed sequence.

object Iterable extends GenTraversableFactory[Iterable] with TraversableFactory[Iterable]

This object provides a set of operations to create mutable.Iterable values. The current default implementation of a mutable.Iterable is an ArrayBuffer .

object LinearSeq extends SeqFactory[LinearSeq]

This object provides a set of operations to create mutable.LinearSeq values. The current default implementation of a mutable.LinearSeq is a MutableList .

object LinkedHashMap extends MutableMapFactory[LinkedHashMap] with Serializable

This object provides a set of operations needed to create LinkedHashMap values.

object LinkedHashSet extends MutableSetFactory[LinkedHashSet] with Serializable

This object provides a set of operations needed to create LinkedHashSet values.

object ListBuffer extends SeqFactory[ListBuffer] with Serializable

This object provides a set of operations to create ListBuffer values.

object ListMap extends MutableMapFactory[ListMap] with Serializable

This object provides a set of operations needed to create mutable.ListMap values.

object LongMap extends Serializable

object Map extends MutableMapFactory[Map]

This object provides a set of operations needed to create mutable.Map values. The current default implementation of a mutable.Map is a HashMap .

object MutableList extends SeqFactory[MutableList] with Serializable

object OpenHashMap

object PriorityQueue extends OrderedTraversableFactory[PriorityQueue] with Serializable

object Queue extends SeqFactory[Queue] with Serializable

object ResizableArray extends SeqFactory[ResizableArray]

object Seq extends SeqFactory[Seq]

This object provides a set of operations to create mutable.Seq values. The current default implementation of a mutable.Seq is an ArrayBuffer .

object Set extends MutableSetFactory[Set]

This object provides a set of operations needed to create mutable.Set values. The current default implementation of a mutable.Set is a HashSet .

object SortedMap extends MutableSortedMapFactory[SortedMap]

This object provides a set of operations needed to create sorted maps of type mutable.SortedMap .

object SortedSet extends MutableSortedSetFactory[SortedSet]

A template for mutable sorted set companion objects.

object Stack extends SeqFactory[Stack] with Serializable

Factory object for the mutable.Stack class.

This object provides a set of operations to create mutable.Stack values.

object StringBuilder extends Serializable

object Traversable extends GenTraversableFactory[Traversable] with TraversableFactory[Traversable]

This object provides a set of operations to create mutable.Traversable values. The current default implementation of a mutable.Traversable is an ArrayBuffer .

object TreeMap extends MutableSortedMapFactory[TreeMap] with Serializable

This object provides a set of operations needed to create sorted maps of type mutable.TreeMap .

object TreeSet extends MutableSortedSetFactory[TreeSet] with Serializable

object UnrolledBuffer extends ClassTagTraversableFactory[UnrolledBuffer] with Serializable

object WeakHashMap extends MutableMapFactory[WeakHashMap] with Serializable

This object provides a set of operations needed to create WeakHashMap values.

object WrappedArray

A companion object used to create instances of WrappedArray .

Full Source:

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */



package scala
package collection
package mutable

import generic._

/** This class implements double linked lists where both the head (`elem`),
 *  the tail (`next`) and a reference to the previous node (`prev`) are mutable.
 *
 *  @author Matthias Zenger
 *  @author Martin Odersky
 *  @version 2.8
 *  @since   1
 *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-mutable-collection-classes.html#double_linked_lists "Scala's Collection Library overview"]]
 *  section on `Double Linked Lists` for more information.

 *
 *  @tparam A     the type of the elements contained in this double linked list.
 *
 *  @define Coll `DoubleLinkedList`
 *  @define coll double linked list
 *  @define thatinfo the class of the returned collection. In the standard library configuration,
 *    `That` is always `DoubleLinkedList[B]` because an implicit of type `CanBuildFrom[DoubleLinkedList, B, DoubleLinkedList[B]]`
 *    is defined in object `DoubleLinkedList`.
 *  @define bfinfo an implicit value of class `CanBuildFrom` which determines the
 *    result class `That` from the current representation type `Repr`
 *    and the new element type `B`. This is usually the `canBuildFrom` value
 *    defined in object `DoubleLinkedList`.
 *  @define orderDependent
 *  @define orderDependentFold
 *  @define mayNotTerminateInf
 *  @define willNotTerminateInf
 */
@deprecated("Low-level linked lists are deprecated due to idiosyncrasies in interface and incomplete features.", "2.11.0")
@SerialVersionUID(-8144992287952814767L)
class DoubleLinkedList[A]() extends AbstractSeq[A]
                            with LinearSeq[A]
                            with GenericTraversableTemplate[A, DoubleLinkedList]
                            with DoubleLinkedListLike[A, DoubleLinkedList[A]]
                            with Serializable {
  next = this

  /** Creates a node for the double linked list.
   *
   *  @param elem    the element this node contains.
   *  @param next    the next node in the double linked list.
   */
  def this(elem: A, next: DoubleLinkedList[A]) {
    this()
    if (next != null) {
      this.elem = elem
      this.next = next
      this.next.prev = this
    }
  }

  override def companion: GenericCompanion[DoubleLinkedList] = DoubleLinkedList

  // Accurately clone this collection.  See SI-6296
  override def clone(): DoubleLinkedList[A] = {
    val builder = newBuilder
    builder ++= this
    builder.result()
  }
}

/** $factoryInfo
 *  @define coll double linked list
 *  @define Coll `DoubleLinkedList`
 */
@deprecated("Low-level linked lists are deprecated.", "2.11.0")
object DoubleLinkedList extends SeqFactory[DoubleLinkedList] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, DoubleLinkedList[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, DoubleLinkedList[A]] =
    new Builder[A, DoubleLinkedList[A]] {
      def emptyList() = new DoubleLinkedList[A]()
      var current = emptyList()

      def +=(elem: A): this.type = {
        if (current.isEmpty)
          current = new DoubleLinkedList(elem, emptyList())
        else
          current append new DoubleLinkedList(elem, emptyList())

        this
      }

      def clear(): Unit = current = emptyList()
      def result() = current
    }
}