Package scala.collection

A common base class for mutable and immutable 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.

A template trait for 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.

This trait provides most of the operations of a BitSet independently of its representation. It is inherited by all concrete implementations of bitsets.

Buffered iterators are iterators which provide a method head that inspects the next element without discarding it.

A default map which implements the + and - methods of maps.

Instances that inherit from DefaultMap[A, B] still have to define:

def get(key: A): Option[B]
def iterator: Iterator[(A, B)]

It refers back to the original map.

It might also be advisable to override foreach or size if efficient implementations can be found.

A trait for all iterable collections which may possibly have their operations implemented in parallel.

A template trait for all iterable collections which may possibly have their operations implemented in parallel.

This trait contains abstract methods and methods that can be implemented directly in terms of other methods.

A trait for all traversable collections which may possibly have their operations implemented in parallel.

A trait for all sequences which may possibly have their operations implemented in parallel.

A trait for sets which may possibly have their operations implemented in parallel.

A trait for all traversable collections which may possibly have their operations implemented in parallel.

A template trait for all traversable-once objects which may be traversed in parallel.

Methods in this trait are either abstract or can be implemented in terms of other methods.

A base trait for indexed sequences.

Indexed sequences support constant-time or near constant-time element access and length computation. They are defined in terms of abstract methods apply for indexing and length.

Indexed sequences do not add any new methods to Seq, but promise efficient implementations of random access patterns.

A template trait for indexed sequences of type IndexedSeq[A].

Indexed sequences support constant-time or near constant-time element access and length computation. They are defined in terms of abstract methods apply for indexing and length.

Indexed sequences do not add any new methods to Seq, but promise efficient implementations of random access patterns.

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.

A template trait for indexed sequences of type IndexedSeq[A] which optimizes the implementation of several methods under the assumption of fast random access.

Indexed sequences support constant-time or near constant-time element access and length computation. They are defined in terms of abstract methods apply for indexing and length.

Indexed sequences do not add any new methods to Seq, but promise efficient implementations of random access patterns.

A base trait for iterable collections.

This is a base trait for all 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.

A template trait for iterable collections of type Iterable[A].

This is a base trait for all 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.

A base trait for non-strict views of Iterables.

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. All views for iterable collections are defined by re-interpreting the iterator method.

A template trait for non-strict views of iterable collections.

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. All views for iterable collections are defined by re-interpreting the iterator method.

Iterators are data structures that allow to iterate over a sequence of elements. They have a hasNext method for checking if there is a next element available, and a next method which returns the next element and advances the iterator.

An iterator is mutable: most operations on it change its state. While it is often used to iterate through the elements of a collection, it can also be used without being backed by any collection (see constructors on the companion object).

It is of particular importance to note that, unless stated otherwise, one should never use an iterator after calling a method on it. The two most important exceptions are also the sole abstract methods: next and hasNext.

Both these methods can be called any number of times without having to discard the iterator. Note that even hasNext may cause mutation -- such as when iterating from an input stream, where it will block until the stream is closed or some input becomes available.

Consider this example for safe and unsafe use:

def f[A](it: Iterator[A]) = {
  if (it.hasNext) {            // Safe to reuse "it" after "hasNext"
    it.next                    // Safe to reuse "it" after "next"
    val remainder = it.drop(2) // it is *not* safe to use "it" again after this line!
    remainder.take(2)          // it is *not* safe to use "remainder" after this line!
  } else it
}

A base trait for linear sequences.

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

A template trait for linear sequences of type LinearSeq[A].

This trait just implements iterator and corresponds in terms of isEmpty, head, and tail. However, see LinearSeqOptimized for an implementation trait that overrides many more operations to make them run faster under the assumption of fast linear access with head and tail.

Linear sequences do not add any new methods to Seq, but promise efficient implementations of linear access patterns.

A template trait for linear sequences of type LinearSeq[A] which optimizes the implementation of various methods under the assumption of fast linear access.

Linear-optimized sequences implement most operations in in terms of three methods, which are assumed to have efficient implementations. These are:

def isEmpty: Boolean
def head: A
def tail: Repr

Here, A is the type of the sequence elements and Repr is the type of the sequence itself. Note that default implementations are provided via inheritance, but these should be overridden for performance.

A map from keys of type K to values of type V.

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

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

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def + [V1 >: V](kv: (K, V1)): This
def -(key: K): 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.

Note: If you do not have specific implementations for add and - in mind, you might consider inheriting from DefaultMap instead.

Note: If your additions and mutations return the same kind of map as the map you are defining, you should inherit from MapLike as well.

A template trait for maps, which associate keys with values.

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

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

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def + [V1 >: V](kv: (K, V1)): This
def -(key: K): 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.

A marker trait for collections which have their operations parallelised.

This trait describes collections which can be turned into parallel collections by invoking the method par. Parallelizable collections may be parameterized with a target type different than their own.

A base trait for sequences.

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.

A template trait for sequences of type Seq[A]

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.

A base trait for non-strict views of sequences.

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. All views for sequences are defined by re-interpreting the length and apply methods.

A template trait for non-strict views of sequences.

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. All views for sequences are defined by re-interpreting the length and apply methods.

A base trait for all sets, mutable as well as immutable.

A set is a collection that contains no duplicate elements.

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

def contains(key: A): Boolean
def iterator: Iterator[A]
def +(elem: A): This
def -(elem: A): This

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.

Implementation note: If your additions and mutations return the same kind of set as the set you are defining, you should inherit from SetLike as well.

A template trait for sets.

A set is a collection that contains no duplicate elements.

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

def contains(key: A): Boolean
def iterator: Iterator[A]
def +(elem: A): This
def -(elem: A): This

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.

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

A map whose keys are sorted.

A template for maps whose keys are sorted. To create a concrete sorted map, you need to implement the rangeImpl method, in addition to those of MapLike.

A sorted set.

A template for sets which are sorted.

A trait for traversable collections. All operations are guaranteed to be performed in a single-threaded manner.

This is a base trait of all kinds of 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.

A template trait for traversable collections of type Traversable[A].

This is a base trait of all kinds of 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.

A template trait for collections which can be traversed either once only or one or more times.

This trait exists primarily to eliminate code duplication between Iterator and Traversable, and thus implements some of the common methods that can be implemented solely in terms of foreach without access to a Builder. It also includes a number of abstract methods whose implementations are provided by Iterator, Traversable, etc. It contains implementations common to Iterators and Traversables, such as folds, conversions, and other operations which traverse some or all of the elements and return a derived value. Directly subclassing TraversableOnce is not recommended - instead, consider declaring an Iterator with a next and hasNext method or creating an Iterator with one of the methods on the Iterator object. Consider declaring a subclass of Traversable instead if the elements can be traversed repeatedly.

A base trait for non-strict views of traversable collections.

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.

All views for traversable collections are defined by creating a new foreach method.

A template trait for non-strict views of traversable collections.

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.

All views for traversable collections are defined by creating a new foreach method.

Implementation note: Methods such as map or flatMap on this view will not invoke the implicitly passed Builder factory, but will return a new view directly, to preserve by-name behavior. The new view is then cast to the factory's result type. This means that every CanBuildFrom that takes a View as its From type parameter must yield the same view (or a generic superclass of it) as its result parameter. If that assumption is broken, cast errors might result.

This trait implements a proxy for iterable objects. It forwards all calls to a different iterable object.

This trait implements a proxy for Iterable objects. It forwards all calls to a different Iterable object.

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

This trait implements a proxy for Map objects. It forwards all calls to a different Map object.

This trait implements a proxy for sequence objects. It forwards all calls to a different sequence object.

This trait implements a proxy for sequences. It forwards all calls to a different sequence.

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

This trait implements a proxy for sets. It forwards all calls to a different set.

This trait implements a proxy for traversable objects. It forwards all calls to a different traversable object

This trait implements a proxy for Traversable objects. It forwards all calls to a different Traversable object.