.. currentmodule:: Base

*********************************
 Collections and Data Structures
*********************************

.. _stdlib-collections-iteration:

Iteration
---------

Sequential iteration is implemented by the methods :func:`start`, :func:`done`, and
:func:`next`. The general ``for`` loop::

    for i = I   # or  "for i in I"
        # body
    end

is translated into::

    state = start(I)
    while !done(I, state)
        (i, state) = next(I, state)
        # body
    end

The ``state`` object may be anything, and should be chosen appropriately for
each iterable type. See the :ref:`manual section on the iteration interface
<man-interfaces-iteration>` for more details about defining a custom iterable
type.

.. function:: start(iter) -> state

   .. Docstring generated from Julia source

   Get initial iteration state for an iterable object.

.. function:: done(iter, state) -> Bool

   .. Docstring generated from Julia source

   Test whether we are done iterating.

.. function:: next(iter, state) -> item, state

   .. Docstring generated from Julia source

   For a given iterable object and iteration state, return the current item and the next iteration state.

.. function:: zip(iters...)

   .. Docstring generated from Julia source

   For a set of iterable objects, returns an iterable of tuples, where the ``i``\ th tuple contains the ``i``\ th component of each input iterable.

   Note that :func:`zip` is its own inverse: ``collect(zip(zip(a...)...)) == collect(a)``\ .

   .. doctest::

       julia> a = 1:5
       1:5

       julia> b = ["e","d","b","c","a"]
       5-element Array{String,1}:
        "e"
        "d"
        "b"
        "c"
        "a"

       julia> c = zip(a,b)
       Base.Zip2{UnitRange{Int64},Array{String,1}}(1:5,String["e","d","b","c","a"])

       julia> length(c)
       5

       julia> first(c)
       (1,"e")

.. function:: enumerate(iter)

   .. Docstring generated from Julia source

   An iterator that yields ``(i, x)`` where ``i`` is a counter starting at 1, and ``x`` is the ``i``\ th value from the given iterator. It's useful when you need not only the values ``x`` over which you are iterating, but also the number of iterations so far. Note that ``i`` may not be valid for indexing ``iter``\ ; it's also possible that ``x != iter[i]``\ , if ``iter`` has indices that do not start at 1.

   .. doctest::

       julia> a = ["a", "b", "c"];

       julia> for (index, value) in enumerate(a)
                  println("$index $value")
              end
       1 a
       2 b
       3 c

.. function:: rest(iter, state)

   .. Docstring generated from Julia source

   An iterator that yields the same elements as ``iter``\ , but starting at the given ``state``\ .

.. function:: countfrom(start=1, step=1)

   .. Docstring generated from Julia source

   An iterator that counts forever, starting at ``start`` and incrementing by ``step``\ .

.. function:: take(iter, n)

   .. Docstring generated from Julia source

   An iterator that generates at most the first ``n`` elements of ``iter``\ .

   .. doctest::

       julia> a = 1:2:11
       1:2:11

       julia> collect(a)
       6-element Array{Int64,1}:
         1
         3
         5
         7
         9
        11

       julia> collect(take(a,3))
       3-element Array{Int64,1}:
        1
        3
        5

.. function:: drop(iter, n)

   .. Docstring generated from Julia source

   An iterator that generates all but the first ``n`` elements of ``iter``\ .

   .. doctest::

       julia> a = 1:2:11
       1:2:11

       julia> collect(a)
       6-element Array{Int64,1}:
         1
         3
         5
         7
         9
        11

       julia> collect(drop(a,4))
       2-element Array{Int64,1}:
         9
        11

.. function:: cycle(iter)

   .. Docstring generated from Julia source

   An iterator that cycles through ``iter`` forever.

.. function:: repeated(x[, n::Int])

   .. Docstring generated from Julia source

   An iterator that generates the value ``x`` forever. If ``n`` is specified, generates ``x`` that many times (equivalent to ``take(repeated(x), n)``\ ).

.. function:: iteratorsize(itertype::Type) -> IteratorSize

   .. Docstring generated from Julia source

   Given the type of an iterator, returns one of the following values:

   * ``SizeUnknown()`` if the length (number of elements) cannot be determined in advance.
   * ``HasLength()`` if there is a fixed, finite length.
   * ``HasShape()`` if there is a known length plus a notion of multidimensional shape (as for an array). In this case the ``size`` function is valid for the iterator.
   * ``IsInfinite()`` if the iterator yields values forever.

   The default value (for iterators that do not define this function) is ``HasLength()``\ . This means that most iterators are assumed to implement ``length``\ .

   This trait is generally used to select between algorithms that pre-allocate space for their result, and algorithms that resize their result incrementally.

.. function:: iteratoreltype(itertype::Type) -> IteratorEltype

   .. Docstring generated from Julia source

   Given the type of an iterator, returns one of the following values:

   * ``EltypeUnknown()`` if the type of elements yielded by the iterator is not known in advance.
   * ``HasEltype()`` if the element type is known, and ``eltype`` would return a meaningful value.

   ``HasEltype()`` is the default, since iterators are assumed to implement ``eltype``\ .

   This trait is generally used to select between algorithms that pre-allocate a specific type of result, and algorithms that pick a result type based on the types of yielded values.

Fully implemented by:

- :obj:`Range`
- :obj:`UnitRange`
- :obj:`Tuple`
- :obj:`Number`
- :obj:`AbstractArray`
- :obj:`IntSet`
- :obj:`ObjectIdDict`
- :obj:`Dict`
- :obj:`WeakKeyDict`
- :obj:`EachLine`
- :obj:`AbstractString`
- :obj:`Set`
- :obj:`Task`

General Collections
-------------------

.. function:: isempty(collection) -> Bool

   .. Docstring generated from Julia source

   Determine whether a collection is empty (has no elements).

   .. doctest::

       julia> isempty([])
       true

       julia> isempty([1 2 3])
       false

.. function:: empty!(collection) -> collection

   .. Docstring generated from Julia source

   Remove all elements from a ``collection``\ .

.. function:: length(collection) -> Integer

   .. Docstring generated from Julia source

   For ordered, indexable collections, the maximum index ``i`` for which ``getindex(collection, i)`` is valid. For unordered collections, the number of elements.

.. function:: endof(collection) -> Integer

   .. Docstring generated from Julia source

   Returns the last index of the collection.

   .. doctest::

       julia> endof([1,2,4])
       3

Fully implemented by:

- :obj:`Range`
- :obj:`UnitRange`
- :obj:`Tuple`
- :obj:`Number`
- :obj:`AbstractArray`
- :obj:`IntSet`
- :obj:`Dict`
- :obj:`WeakKeyDict`
- :obj:`AbstractString`
- :obj:`Set`

Iterable Collections
--------------------

.. function:: in(item, collection) -> Bool
              ∈(item,collection) -> Bool
              ∋(collection,item) -> Bool
              ∉(item,collection) -> Bool
              ∌(collection,item) -> Bool

   .. Docstring generated from Julia source

   Determine whether an item is in the given collection, in the sense that it is ``==`` to one of the values generated by iterating over the collection. Some collections need a slightly different definition; for example :obj:`Set`\ s check whether the item :func:`isequal` to one of the elements. :obj:`Dict`\ s look for ``(key,value)`` pairs, and the key is compared using :func:`isequal`\ . To test for the presence of a key in a dictionary, use :func:`haskey` or ``k in keys(dict)``\ .

.. function:: eltype(type)

   .. Docstring generated from Julia source

   Determine the type of the elements generated by iterating a collection of the given ``type``\ . For associative collection types, this will be a ``Pair{KeyType,ValType}``\ . The definition ``eltype(x) = eltype(typeof(x))`` is provided for convenience so that instances can be passed instead of types. However the form that accepts a type argument should be defined for new types.

.. function:: indexin(a, b)

   .. Docstring generated from Julia source

   Returns a vector containing the highest index in ``b`` for each value in ``a`` that is a member of ``b`` . The output vector contains 0 wherever ``a`` is not a member of ``b``\ .

   .. doctest::

       julia> a = ['a', 'b', 'c', 'b', 'd', 'a'];

       julia> b = ['a','b','c'];

       julia> indexin(a,b)
       6-element Array{Int64,1}:
        1
        2
        3
        2
        0
        1

       julia> indexin(b,a)
       3-element Array{Int64,1}:
        6
        4
        3

.. function:: findin(a, b)

   .. Docstring generated from Julia source

   Returns the indices of elements in collection ``a`` that appear in collection ``b``\ .

   .. doctest::

       julia> a = collect(1:3:15)
       5-element Array{Int64,1}:
         1
         4
         7
        10
        13

       julia> b = collect(2:4:10)
       3-element Array{Int64,1}:
         2
         6
        10

       julia> findin(a,b) # 10 is the only common element
       1-element Array{Int64,1}:
        4

.. function:: unique(itr[, dim])

   .. Docstring generated from Julia source

   Returns an array containing only the unique elements of the iterable ``itr``\ , in the order that the first of each set of equivalent elements originally appears. If ``dim`` is specified, returns unique regions of the array ``itr`` along ``dim``\ .

.. function:: unique(itr)

   .. Docstring generated from Julia source

   Returns an array containing one value from ``itr`` for each unique value, as determined by ``isequal``\ .

.. function:: unique(f, itr)

   .. Docstring generated from Julia source

   Returns an array containing one value from ``itr`` for each unique value produced by ``f`` applied to elements of ``itr``\ .

.. function:: allunique(itr)

   .. Docstring generated from Julia source

   Return ``true`` if all values from ``itr`` are distinct when compared with ``isequal``\ .

.. function:: reduce(op, v0, itr)

   .. Docstring generated from Julia source

   Reduce the given collection ``ìtr`` with the given binary operator ``op``\ . ``v0`` must be a neutral element for ``op`` that will be returned for empty collections. It is unspecified whether ``v0`` is used for non-empty collections.

   Reductions for certain commonly-used operators have special implementations which should be used instead: ``maximum(itr)``\ , ``minimum(itr)``\ , ``sum(itr)``\ , ``prod(itr)``\ , ``any(itr)``\ , ``all(itr)``\ .

   The associativity of the reduction is implementation dependent. This means that you can't use non-associative operations like ``-`` because it is undefined whether ``reduce(-,[1,2,3])`` should be evaluated as ``(1-2)-3`` or ``1-(2-3)``\ . Use ``foldl`` or ``foldr`` instead for guaranteed left or right associativity.

   Some operations accumulate error, and parallelism will also be easier if the reduction can be executed in groups. Future versions of Julia might change the algorithm. Note that the elements are not reordered if you use an ordered collection.

.. function:: reduce(op, itr)

   .. Docstring generated from Julia source

   Like ``reduce(op, v0, itr)``\ . This cannot be used with empty collections, except for some special cases (e.g. when ``op`` is one of ``+``\ , ``*``\ , ``max``\ , ``min``\ , ``&``\ , ``|``\ ) when Julia can determine the neutral element of ``op``\ .

.. function:: foldl(op, v0, itr)

   .. Docstring generated from Julia source

   Like :func:`reduce`\ , but with guaranteed left associativity. ``v0`` will be used exactly once.

.. function:: foldl(op, itr)

   .. Docstring generated from Julia source

   Like ``foldl(op, v0, itr)``\ , but using the first element of ``itr`` as ``v0``\ . In general, this cannot be used with empty collections (see ``reduce(op, itr)``\ ).

.. function:: foldr(op, v0, itr)

   .. Docstring generated from Julia source

   Like :func:`reduce`\ , but with guaranteed right associativity. ``v0`` will be used exactly once.

.. function:: foldr(op, itr)

   .. Docstring generated from Julia source

   Like ``foldr(op, v0, itr)``\ , but using the last element of ``itr`` as ``v0``\ . In general, this cannot be used with empty collections (see ``reduce(op, itr)``\ ).

.. function:: maximum(itr)

   .. Docstring generated from Julia source

   Returns the largest element in a collection.

   .. doctest::

       julia> maximum(-20.5:10)
       9.5

       julia> maximum([1,2,3])
       3

.. function:: maximum(A, dims)

   .. Docstring generated from Julia source

   Compute the maximum value of an array over the given dimensions.

.. function:: maximum!(r, A)

   .. Docstring generated from Julia source

   Compute the maximum value of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: minimum(itr)

   .. Docstring generated from Julia source

   Returns the smallest element in a collection.

   .. doctest::

       julia> minimum(-20.5:10)
       -20.5

       julia> minimum([1,2,3])
       1

.. function:: minimum(A, dims)

   .. Docstring generated from Julia source

   Compute the minimum value of an array over the given dimensions.

.. function:: minimum!(r, A)

   .. Docstring generated from Julia source

   Compute the minimum value of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: extrema(itr) -> Tuple

   .. Docstring generated from Julia source

   Compute both the minimum and maximum element in a single pass, and return them as a 2-tuple.

   .. doctest::

       julia> extrema(2:10)
       (2,10)

       julia> extrema([9,pi,4.5])
       (3.141592653589793,9.0)

.. function:: extrema(A,dims) -> Array{Tuple}

   .. Docstring generated from Julia source

   Compute the minimum and maximum elements of an array over the given dimensions.

.. function:: indmax(itr) -> Integer

   .. Docstring generated from Julia source

   Returns the index of the maximum element in a collection. The collection must not be empty.

   .. doctest::

       julia> indmax([8,0.1,-9,pi])
       1

.. function:: indmin(itr) -> Integer

   .. Docstring generated from Julia source

   Returns the index of the minimum element in a collection. The collection must not be empty.

   .. doctest::

       julia> indmin([8,0.1,-9,pi])
       3

.. function:: findmax(itr) -> (x, index)

   .. Docstring generated from Julia source

   Returns the maximum element and its index. The collection must not be empty.

   .. doctest::

       julia> findmax([8,0.1,-9,pi])
       (8.0,1)

.. function:: findmax(A, region) -> (maxval, index)

   .. Docstring generated from Julia source

   For an array input, returns the value and index of the maximum over the given region.

.. function:: findmin(itr) -> (x, index)

   .. Docstring generated from Julia source

   Returns the minimum element and its index. The collection must not be empty.

   .. doctest::

       julia> findmin([8,0.1,-9,pi])
       (-9.0,3)

.. function:: findmin(A, region) -> (minval, index)

   .. Docstring generated from Julia source

   For an array input, returns the value and index of the minimum over the given region.

.. function:: findmax!(rval, rind, A, [init=true]) -> (maxval, index)

   .. Docstring generated from Julia source

   Find the maximum of ``A`` and the corresponding linear index along singleton dimensions of ``rval`` and ``rind``\ , and store the results in ``rval`` and ``rind``\ .

.. function:: findmin!(rval, rind, A, [init=true]) -> (minval, index)

   .. Docstring generated from Julia source

   Find the minimum of ``A`` and the corresponding linear index along singleton dimensions of ``rval`` and ``rind``\ , and store the results in ``rval`` and ``rind``\ .

.. function:: maxabs(itr)

   .. Docstring generated from Julia source

   Compute the maximum absolute value of a collection of values.

   .. doctest::

       julia> maxabs([-1, 3, 4*im])
       4.0

.. function:: maxabs(A, dims)

   .. Docstring generated from Julia source

   Compute the maximum absolute values over given dimensions.

.. function:: maxabs!(r, A)

   .. Docstring generated from Julia source

   Compute the maximum absolute values over the singleton dimensions of ``r``\ , and write values to ``r``\ .

.. function:: minabs(itr)

   .. Docstring generated from Julia source

   Compute the minimum absolute value of a collection of values.

   .. doctest::

       julia> minabs([-1, 3, 4*im])
       1.0

.. function:: minabs(A, dims)

   .. Docstring generated from Julia source

   Compute the minimum absolute values over given dimensions.

.. function:: minabs!(r, A)

   .. Docstring generated from Julia source

   Compute the minimum absolute values over the singleton dimensions of ``r``\ , and write values to ``r``\ .

.. function:: sum(itr)

   .. Docstring generated from Julia source

   Returns the sum of all elements in a collection.

.. function:: sum(A, dims)

   .. Docstring generated from Julia source

   Sum elements of an array over the given dimensions.

.. function:: sum!(r, A)

   .. Docstring generated from Julia source

   Sum elements of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: sum(f, itr)

   .. Docstring generated from Julia source

   Sum the results of calling function ``f`` on each element of ``itr``\ .

.. function:: sumabs(itr)

   .. Docstring generated from Julia source

   Sum absolute values of all elements in a collection. This is equivalent to ``sum(abs(itr))`` but faster.

.. function:: sumabs(A, dims)

   .. Docstring generated from Julia source

   Sum absolute values of elements of an array over the given dimensions.

.. function:: sumabs!(r, A)

   .. Docstring generated from Julia source

   Sum absolute values of elements of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: sumabs2(itr)

   .. Docstring generated from Julia source

   Sum squared absolute values of all elements in a collection. This is equivalent to ``sum(abs2(itr))`` but faster.

.. function:: sumabs2(A, dims)

   .. Docstring generated from Julia source

   Sum squared absolute values of elements of an array over the given dimensions.

.. function:: sumabs2!(r, A)

   .. Docstring generated from Julia source

   Sum squared absolute values of elements of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: prod(itr)

   .. Docstring generated from Julia source

   Returns the product of all elements of a collection.

.. function:: prod(A, dims)

   .. Docstring generated from Julia source

   Multiply elements of an array over the given dimensions.

.. function:: prod!(r, A)

   .. Docstring generated from Julia source

   Multiply elements of ``A`` over the singleton dimensions of ``r``\ , and write results to ``r``\ .

.. function:: any(itr) -> Bool

   .. Docstring generated from Julia source

   Test whether any elements of a boolean collection are ``true``\ .

.. function:: any(A, dims)

   .. Docstring generated from Julia source

   Test whether any values along the given dimensions of an array are ``true``\ .

.. function:: any!(r, A)

   .. Docstring generated from Julia source

   Test whether any values in ``A`` along the singleton dimensions of ``r`` are ``true``\ , and write results to ``r``\ .

.. function:: all(itr) -> Bool

   .. Docstring generated from Julia source

   Test whether all elements of a boolean collection are ``true``\ .

.. function:: all(A, dims)

   .. Docstring generated from Julia source

   Test whether all values along the given dimensions of an array are ``true``\ .

.. function:: all!(r, A)

   .. Docstring generated from Julia source

   Test whether all values in ``A`` along the singleton dimensions of ``r`` are ``true``\ , and write results to ``r``\ .

.. function:: count(p, itr) -> Integer

   .. Docstring generated from Julia source

   Count the number of elements in ``itr`` for which predicate ``p`` returns ``true``\ .

   .. doctest::

       julia> count(i->(4<=i<=6), [2,3,4,5,6])
       3

.. function:: any(p, itr) -> Bool

   .. Docstring generated from Julia source

   Determine whether predicate ``p`` returns ``true`` for any elements of ``itr``\ .

   .. doctest::

       julia> any(i->(4<=i<=6), [3,5,7])
       true

.. function:: all(p, itr) -> Bool

   .. Docstring generated from Julia source

   Determine whether predicate ``p`` returns ``true`` for all elements of ``itr``\ .

   .. doctest::

       julia> all(i->(4<=i<=6), [4,5,6])
       true

.. function:: foreach(f, c...) -> Void

   .. Docstring generated from Julia source

   Call function ``f`` on each element of iterable ``c``\ . For multiple iterable arguments, ``f`` is called elementwise. ``foreach`` should be used instead of ``map`` when the results of ``f`` are not needed, for example in ``foreach(println, array)``\ .

   .. doctest::

       julia> a = 1:3:7;

       julia> foreach(x->println(x^2),a)
       1
       16
       49

.. function:: map(f, c...) -> collection

   .. Docstring generated from Julia source

   Transform collection ``c`` by applying ``f`` to each element. For multiple collection arguments, apply ``f`` elementwise.

   .. doctest::

       julia> map((x) -> x * 2, [1, 2, 3])
       3-element Array{Int64,1}:
        2
        4
        6

       julia> map(+, [1, 2, 3], [10, 20, 30])
       3-element Array{Int64,1}:
        11
        22
        33

.. function:: map!(function, collection)

   .. Docstring generated from Julia source

   In-place version of :func:`map`\ .

.. function:: map!(function, destination, collection...)

   .. Docstring generated from Julia source

   Like :func:`map`\ , but stores the result in ``destination`` rather than a new collection. ``destination`` must be at least as large as the first collection.

.. function:: mapreduce(f, op, v0, itr)

   .. Docstring generated from Julia source

   Apply function ``f`` to each element in ``itr``\ , and then reduce the result using the binary function ``op``\ . ``v0`` must be a neutral element for ``op`` that will be returned for empty collections. It is unspecified whether ``v0`` is used for non-empty collections.

   :func:`mapreduce` is functionally equivalent to calling ``reduce(op, v0, map(f, itr))``\ , but will in general execute faster since no intermediate collection needs to be created. See documentation for :func:`reduce` and :func:`map`\ .

   .. doctest::

       julia> mapreduce(x->x^2, +, [1:3;]) # == 1 + 4 + 9
       14

   The associativity of the reduction is implementation-dependent. Additionally, some implementations may reuse the return value of ``f`` for elements that appear multiple times in ``itr``\ . Use :func:`mapfoldl` or :func:`mapfoldr` instead for guaranteed left or right associativity and invocation of ``f`` for every value.

.. function:: mapreduce(f, op, itr)

   .. Docstring generated from Julia source

   Like ``mapreduce(f, op, v0, itr)``\ . In general, this cannot be used with empty collections (see ``reduce(op, itr)``\ ).

.. function:: mapfoldl(f, op, v0, itr)

   .. Docstring generated from Julia source

   Like :func:`mapreduce`\ , but with guaranteed left associativity. ``v0`` will be used exactly once.

.. function:: mapfoldl(f, op, itr)

   .. Docstring generated from Julia source

   Like ``mapfoldl(f, op, v0, itr)``\ , but using the first element of ``itr`` as ``v0``\ . In general, this cannot be used with empty collections (see ``reduce(op, itr)``\ ).

.. function:: mapfoldr(f, op, v0, itr)

   .. Docstring generated from Julia source

   Like :func:`mapreduce`\ , but with guaranteed right associativity. ``v0`` will be used exactly once.

.. function:: mapfoldr(f, op, itr)

   .. Docstring generated from Julia source

   Like ``mapfoldr(f, op, v0, itr)``\ , but using the first element of ``itr`` as ``v0``\ . In general, this cannot be used with empty collections (see ``reduce(op, itr)``\ ).

.. function:: first(coll)

   .. Docstring generated from Julia source

   Get the first element of an iterable collection. Returns the start point of a :obj:`Range` even if it is empty.

.. function:: last(coll)

   .. Docstring generated from Julia source

   Get the last element of an ordered collection, if it can be computed in O(1) time. This is accomplished by calling :func:`endof` to get the last index. Returns the end point of a :obj:`Range` even if it is empty.

.. function:: step(r)

   .. Docstring generated from Julia source

   Get the step size of a :obj:`Range` object.

   .. doctest::

       julia> step(1:10)
       1

       julia> step(1:2:10)
       2

       julia> step(2.5:0.3:10.9)
       0.3

       julia> step(linspace(2.5,10.9,85))
       0.1

.. function:: collect(collection)

   .. Docstring generated from Julia source

   Return an ``Array`` of all items in a collection or iterator. For associative collections, returns ``Pair{KeyType, ValType}``\ . If the argument is array-like or is an iterator with the ``HasShape()`` trait, the result will have the same shape and number of dimensions as the argument.

.. function:: collect(element_type, collection)

   .. Docstring generated from Julia source

   Return an ``Array`` with the given element type of all items in a collection or iterable. The result has the same shape and number of dimensions as ``collection``\ .

.. function:: issubset(a, b)
              ⊆(a,b) -> Bool
              ⊈(a,b) -> Bool
              ⊊(a,b) -> Bool

   .. Docstring generated from Julia source

   Determine whether every element of ``a`` is also in ``b``\ , using :func:`in`\ .

.. function:: filter(function, collection)

   .. Docstring generated from Julia source

   Return a copy of ``collection``\ , removing elements for which ``function`` is ``false``\ . For associative collections, the function is passed two arguments (key and value).

   .. code-block:: julia

       julia> a = 1:10
       1:10

       julia> filter(isodd, a)
       5-element Array{Int64,1}:
        1
        3
        5
        7
        9

.. function:: filter!(function, collection)

   .. Docstring generated from Julia source

   Update ``collection``\ , removing elements for which ``function`` is ``false``\ . For associative collections, the function is passed two arguments (key and value).

Indexable Collections
---------------------

.. function:: getindex(collection, key...)

   .. Docstring generated from Julia source

   Retrieve the value(s) stored at the given key or index within a collection. The syntax ``a[i,j,...]`` is converted by the compiler to ``getindex(a, i, j, ...)``\ .

.. function:: setindex!(collection, value, key...)

   .. Docstring generated from Julia source

   Store the given value at the given key or index within a collection. The syntax ``a[i,j,...] = x`` is converted by the compiler to ``(setindex!(a, x, i, j, ...); x)``\ .

Fully implemented by:

- :obj:`Array`
- :obj:`BitArray`
- :obj:`AbstractArray`
- :obj:`SubArray`
- :obj:`ObjectIdDict`
- :obj:`Dict`
- :obj:`WeakKeyDict`
- :obj:`AbstractString`

Partially implemented by:

- :obj:`Range`
- :obj:`UnitRange`
- :obj:`Tuple`

Associative Collections
-----------------------

:obj:`Dict` is the standard associative collection. Its implementation uses :func:`hash` as the hashing function for the key, and :func:`isequal` to determine equality. Define these two functions for custom types to override how they are stored in a hash table.

:obj:`ObjectIdDict` is a special hash table where the keys are always object identities.

:obj:`WeakKeyDict` is a hash table implementation where the keys are weak references to objects, and thus may be garbage collected even when referenced in a hash table.

:obj:`Dict`\ s can be created by passing pair objects constructed with :func:`=>` to a :obj:`Dict` constructor: ``Dict("A"=>1, "B"=>2)``. This call will attempt to infer type information from the keys and values (i.e. this example creates a ``Dict{String, Int64}``).
To explicitly specify types use the syntax ``Dict{KeyType,ValueType}(...)``.
For example, ``Dict{String,Int32}("A"=>1, "B"=>2)``.

:obj:`Dict`\ s may also be created with generators. For example,
``Dict(i => f(i) for i = 1:10)``.

Given a dictionary ``D``, the syntax ``D[x]`` returns the value of key ``x`` (if it exists) or throws an error, and ``D[x] = y`` stores the key-value pair ``x => y`` in ``D`` (replacing any existing value for the key ``x``).  Multiple arguments to ``D[...]`` are converted to tuples; for example, the syntax ``D[x,y]``  is equivalent to ``D[(x,y)]``, i.e. it refers to the value keyed by the tuple ``(x,y)``.

.. function:: Dict([itr])

   .. Docstring generated from Julia source

   ``Dict{K,V}()`` constructs a hash table with keys of type ``K`` and values of type ``V``\ .

   Given a single iterable argument, constructs a :obj:`Dict` whose key-value pairs are taken from 2-tuples ``(key,value)`` generated by the argument.

   .. doctest::

       julia> Dict([("A", 1), ("B", 2)])
       Dict{String,Int64} with 2 entries:
         "B" => 2
         "A" => 1

   Alternatively, a sequence of pair arguments may be passed.

   .. doctest::

       julia> Dict("A"=>1, "B"=>2)
       Dict{String,Int64} with 2 entries:
         "B" => 2
         "A" => 1

.. function:: haskey(collection, key) -> Bool

   .. Docstring generated from Julia source

   Determine whether a collection has a mapping for a given key.

.. function:: get(collection, key, default)

   .. Docstring generated from Julia source

   Return the value stored for the given key, or the given default value if no mapping for the key is present.

.. function:: get(f::Function, collection, key)

   .. Docstring generated from Julia source

   Return the value stored for the given key, or if no mapping for the key is present, return ``f()``\ .  Use :func:`get!` to also store the default value in the dictionary.

   This is intended to be called using ``do`` block syntax

   .. code-block:: julia

       get(dict, key) do
           # default value calculated here
           time()
       end

.. function:: get!(collection, key, default)

   .. Docstring generated from Julia source

   Return the value stored for the given key, or if no mapping for the key is present, store ``key => default``\ , and return ``default``\ .

.. function:: get!(f::Function, collection, key)

   .. Docstring generated from Julia source

   Return the value stored for the given key, or if no mapping for the key is present, store ``key => f()``\ , and return ``f()``\ .

   This is intended to be called using ``do`` block syntax:

   .. code-block:: julia

       get!(dict, key) do
           # default value calculated here
           time()
       end

.. function:: getkey(collection, key, default)

   .. Docstring generated from Julia source

   Return the key matching argument ``key`` if one exists in ``collection``\ , otherwise return ``default``\ .

.. function:: delete!(collection, key)

   .. Docstring generated from Julia source

   Delete the mapping for the given key in a collection, and return the collection.

.. function:: pop!(collection, key[, default])

   .. Docstring generated from Julia source

   Delete and return the mapping for ``key`` if it exists in ``collection``\ , otherwise return ``default``\ , or throw an error if default is not specified.

.. function:: keys(collection)

   .. Docstring generated from Julia source

   Return an iterator over all keys in a collection. ``collect(keys(d))`` returns an array of keys.

.. function:: values(collection)

   .. Docstring generated from Julia source

   Return an iterator over all values in a collection. ``collect(values(d))`` returns an array of values.

.. function:: merge(collection, others...)

   .. Docstring generated from Julia source

   Construct a merged collection from the given collections. If necessary, the types of the resulting collection will be promoted to accommodate the types of the merged collections. If the same key is present in another collection, the value for that key will be the value it has in the last collection listed.

   .. doctest::

       julia> a = Dict("foo" => 0.0, "bar" => 42.0)
       Dict{String,Float64} with 2 entries:
         "bar" => 42.0
         "foo" => 0.0

       julia> b = Dict("baz" => 17, "bar" => 4711)
       Dict{String,Int64} with 2 entries:
         "bar" => 4711
         "baz" => 17

       julia> merge(a, b)
       Dict{String,Float64} with 3 entries:
         "bar" => 4711.0
         "baz" => 17.0
         "foo" => 0.0

       julia> merge(b, a)
       Dict{String,Float64} with 3 entries:
         "bar" => 42.0
         "baz" => 17.0
         "foo" => 0.0

.. function:: merge!(collection, others...)

   .. Docstring generated from Julia source

   Update collection with pairs from the other collections.

.. function:: sizehint!(s, n)

   .. Docstring generated from Julia source

   Suggest that collection ``s`` reserve capacity for at least ``n`` elements. This can improve performance.

.. function:: keytype(type)

   .. Docstring generated from Julia source

   Get the key type of an associative collection type. Behaves similarly to ``eltype``\ .

.. function:: valtype(type)

   .. Docstring generated from Julia source

   Get the value type of an associative collection type. Behaves similarly to ``eltype``\ .

Fully implemented by:

- :obj:`ObjectIdDict`
- :obj:`Dict`
- :obj:`WeakKeyDict`

Partially implemented by:

- :obj:`IntSet`
- :obj:`Set`
- :obj:`EnvHash`
- :obj:`Array`
- :obj:`BitArray`

Set-Like Collections
--------------------

.. function:: Set([itr])

   .. Docstring generated from Julia source

   Construct a :obj:`Set` of the values generated by the given iterable object, or an empty set. Should be used instead of :obj:`IntSet` for sparse integer sets, or for sets of arbitrary objects.

.. function:: IntSet([itr])

   .. Docstring generated from Julia source

   Construct a sorted set of positive ``Int``\ s generated by the given iterable object, or an empty set. Implemented as a bit string, and therefore designed for dense integer sets. Only ``Int``\ s greater than 0 can be stored. If the set will be sparse (for example holding a few very large integers), use :obj:`Set` instead.

.. function:: union(s1,s2...)
              ∪(s1,s2...)

   .. Docstring generated from Julia source

   Construct the union of two or more sets. Maintains order with arrays.

.. function:: union!(s, iterable)

   .. Docstring generated from Julia source

   Union each element of ``iterable`` into set ``s`` in-place.

.. function:: intersect(s1,s2...)
              ∩(s1,s2)

   .. Docstring generated from Julia source

   Construct the intersection of two or more sets. Maintains order and multiplicity of the first argument for arrays and ranges.

.. function:: setdiff(a, b)

   .. Docstring generated from Julia source

   Construct the set of elements in ``a`` but not ``b``\ . Maintains order with arrays. Note that both arguments must be collections, and both will be iterated over. In particular, ``setdiff(set,element)`` where ``element`` is a potential member of ``set``\ , will not work in general.

   .. doctest::

       julia> setdiff([1,2,3],[3,4,5])
       2-element Array{Int64,1}:
        1
        2

.. function:: setdiff!(s, iterable)

   .. Docstring generated from Julia source

   Remove each element of ``iterable`` from set ``s`` in-place.

.. function:: symdiff(a, b, rest...)

   .. Docstring generated from Julia source

   Construct the symmetric difference of elements in the passed in sets or arrays. Maintains order with arrays.

   .. doctest::

       julia> symdiff([1,2,3],[3,4,5],[4,5,6])
       3-element Array{Int64,1}:
        1
        2
        6

.. function:: symdiff!(s, n)

   .. Docstring generated from Julia source

   The set ``s`` is destructively modified to toggle the inclusion of integer ``n``\ .

.. function:: symdiff!(s, itr)

   .. Docstring generated from Julia source

   For each element in ``itr``\ , destructively toggle its inclusion in set ``s``\ .

.. function:: symdiff!(s1, s2)

   .. Docstring generated from Julia source

   Construct the symmetric difference of sets ``s1`` and ``s2``\ , storing the result in ``s1``\ .

.. function:: intersect!(s1, s2)

   .. Docstring generated from Julia source

   Intersects sets ``s1`` and ``s2`` and overwrites the set ``s1`` with the result. If needed, ``s1`` will be expanded to the size of ``s2``\ .

.. function:: issubset(A, S) -> Bool
              ⊆(A,S) -> Bool

   .. Docstring generated from Julia source

   Return ``true`` if ``A`` is a subset of or equal to ``S``\ .

Fully implemented by:

- :obj:`IntSet`
- :obj:`Set`

Partially implemented by:

- :obj:`Array`

Dequeues
--------

.. function:: push!(collection, items...) -> collection

   .. Docstring generated from Julia source

   Insert one or more ``items`` at the end of ``collection``\ .

   .. doctest::

       julia> push!([1, 2, 3], 4, 5, 6)
       6-element Array{Int64,1}:
        1
        2
        3
        4
        5
        6

   Use :func:`append!` to add all the elements of another collection to ``collection``\ . The result of the preceding example is equivalent to ``append!([1, 2, 3], [4, 5, 6])``\ .

.. function:: pop!(collection) -> item

   .. Docstring generated from Julia source

   Remove the last item in ``collection`` and return it.

   .. doctest::

       julia> A=[1, 2, 3, 4, 5, 6]
       6-element Array{Int64,1}:
        1
        2
        3
        4
        5
        6

       julia> pop!(A)
       6

       julia> A
       5-element Array{Int64,1}:
        1
        2
        3
        4
        5

.. function:: unshift!(collection, items...) -> collection

   .. Docstring generated from Julia source

   Insert one or more ``items`` at the beginning of ``collection``\ .

   .. doctest::

         julia> unshift!([1, 2, 3, 4], 5, 6)
         6-element Array{Int64,1}:
          5
          6
          1
          2
          3
          4

.. function:: shift!(collection) -> item

   .. Docstring generated from Julia source

   Remove the first ``item`` from ``collection``\ .

   .. doctest::

       julia> A = [1, 2, 3, 4, 5, 6]
       6-element Array{Int64,1}:
        1
        2
        3
        4
        5
        6

       julia> shift!(A)
       1

       julia> A
       5-element Array{Int64,1}:
        2
        3
        4
        5
        6

.. function:: insert!(collection, index, item)

   .. Docstring generated from Julia source

   Insert an ``item`` into ``collection`` at the given ``index``\ . ``index`` is the index of ``item`` in the resulting ``collection``\ .

   .. doctest::

       julia> insert!([6, 5, 4, 2, 1], 4, 3)
       6-element Array{Int64,1}:
        6
        5
        4
        3
        2
        1

.. function:: deleteat!(a::Vector, i::Integer)

   .. Docstring generated from Julia source

   Remove the item at the given ``i`` and return the modified ``a``\ . Subsequent items are shifted to fill the resulting gap.

   .. doctest::

       julia> deleteat!([6, 5, 4, 3, 2, 1], 2)
       5-element Array{Int64,1}:
        6
        4
        3
        2
        1

.. function:: deleteat!(a::Vector, inds)

   .. Docstring generated from Julia source

   Remove the items at the indices given by ``inds``\ , and return the modified ``a``\ . Subsequent items are shifted to fill the resulting gap. ``inds`` must be sorted and unique.

   .. doctest::

       julia> deleteat!([6, 5, 4, 3, 2, 1], 1:2:5)
       3-element Array{Int64,1}:
        5
        3
        1

       julia> deleteat!([6, 5, 4, 3, 2, 1], (2, 2))
       ERROR: ArgumentError: indices must be unique and sorted
        in deleteat!(::Array{Int64,1}, ::Tuple{Int64,Int64}) at ./array.jl:614
        ...

.. function:: splice!(collection, index, [replacement]) -> item

   .. Docstring generated from Julia source

   Remove the item at the given index, and return the removed item. Subsequent items are shifted down to fill the resulting gap. If specified, replacement values from an ordered collection will be spliced in place of the removed item.

   .. doctest::

       julia> A = [6, 5, 4, 3, 2, 1]; splice!(A, 5)
       2

       julia> A
       5-element Array{Int64,1}:
        6
        5
        4
        3
        1

       julia> splice!(A, 5, -1)
       1

       julia> A
       5-element Array{Int64,1}:
         6
         5
         4
         3
        -1

       julia> splice!(A, 1, [-1, -2, -3])
       6

       julia> A
       7-element Array{Int64,1}:
        -1
        -2
        -3
         5
         4
         3
        -1

   To insert ``replacement`` before an index ``n`` without removing any items, use ``splice!(collection, n:n-1, replacement)``\ .

.. function:: splice!(collection, range, [replacement]) -> items

   .. Docstring generated from Julia source

   Remove items in the specified index range, and return a collection containing the removed items. Subsequent items are shifted down to fill the resulting gap. If specified, replacement values from an ordered collection will be spliced in place of the removed items.

   To insert ``replacement`` before an index ``n`` without removing any items, use ``splice!(collection, n:n-1, replacement)``\ .

   .. doctest::

       julia> splice!(A, 4:3, 2)
       0-element Array{Int64,1}

       julia> A
       8-element Array{Int64,1}:
        -1
        -2
        -3
         2
         5
         4
         3
        -1

.. function:: resize!(collection, n) -> collection

   .. Docstring generated from Julia source

   Resize ``collection`` to contain ``n`` elements. If ``n`` is smaller than the current collection length, the first ``n`` elements will be retained. If ``n`` is larger, the new elements are not guaranteed to be initialized.

   .. doctest::

       julia> resize!([6, 5, 4, 3, 2, 1], 3)
       3-element Array{Int64,1}:
        6
        5
        4

   .. code-block:: julia

       julia> resize!([6, 5, 4, 3, 2, 1], 8)
       8-element Array{Int64,1}:
        6
        5
        4
        3
        2
        1
        0
        0

.. function:: append!(collection, collection2) -> collection.

   .. Docstring generated from Julia source

   Add the elements of ``collection2`` to the end of ``collection``\ .

   .. doctest::

       julia> append!([1],[2,3])
       3-element Array{Int64,1}:
        1
        2
        3

   .. doctest::

       julia> append!([1, 2, 3], [4, 5, 6])
       6-element Array{Int64,1}:
        1
        2
        3
        4
        5
        6

   Use :func:`push!` to add individual items to ``collection`` which are not already themselves in another collection. The result is of the preceding example is equivalent to ``push!([1, 2, 3], 4, 5, 6)``\ .

.. function:: prepend!(collection, items) -> collection

   .. Docstring generated from Julia source

   Insert the elements of ``items`` to the beginning of ``collection``\ .

   .. doctest::

       julia> prepend!([3],[1,2])
       3-element Array{Int64,1}:
        1
        2
        3

Fully implemented by:

- :obj:`Vector` (a.k.a. 1-dimensional :obj:`Array`)
- :obj:`BitVector` (a.k.a. 1-dimensional :obj:`BitArray`)

.. module:: Base.Collections

PriorityQueue
-------------

The :obj:`PriorityQueue` type is available from the :mod:`Collections` module. It provides
a basic priority queue implementation allowing for arbitrary key and priority types.
Multiple identical keys are not permitted, but the priority of existing keys can be
changed efficiently.

.. function:: PriorityQueue(K, V, [ord])

   .. Docstring generated from Julia source

   Construct a new :obj:`PriorityQueue`\ , with keys of type ``K`` and values/priorites of type ``V``\ . If an order is not given, the priority queue is min-ordered using the default comparison for ``V``\ .

   A ``PriorityQueue`` acts like a ``Dict``\ , mapping values to their priorities, with the addition of a ``dequeue!`` function to remove the lowest priority element.

   .. doctest::

       julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
       Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
         "c" => 1
         "b" => 3
         "a" => 2

.. function:: enqueue!(pq, k, v)

   .. Docstring generated from Julia source

   Insert the a key ``k`` into a priority queue ``pq`` with priority ``v``\ .

   .. doctest::

       julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
       Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
         "c" => 1
         "b" => 3
         "a" => 2

       julia> Base.Collections.enqueue!(a, "d", 4)
       Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 4 entries:
         "c" => 1
         "b" => 3
         "a" => 2
         "d" => 4

.. function:: dequeue!(pq)

   .. Docstring generated from Julia source

   Remove and return the lowest priority key from a priority queue.

   .. doctest::

       julia> a = Base.Collections.PriorityQueue(["a","b","c"],[2,3,1],Base.Order.Forward)
       Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 3 entries:
         "c" => 1
         "b" => 3
         "a" => 2

       julia> Base.Collections.dequeue!(a)
       "c"

       julia> a
       Base.Collections.PriorityQueue{String,Int64,Base.Order.ForwardOrdering} with 2 entries:
         "b" => 3
         "a" => 2

.. function:: peek(pq)

   .. Docstring generated from Julia source

   Return the lowest priority key from a priority queue without removing that key from the queue.

:obj:`PriorityQueue` also behaves similarly to a :obj:`Dict` in that keys can be
inserted and priorities accessed or changed using indexing notation.

.. doctest::

    julia> # Julia code
           pq = Collections.PriorityQueue();

    julia> # Insert keys with associated priorities
           pq["a"] = 10; pq["b"] = 5; pq["c"] = 15; pq
    Base.Collections.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
      "c" => 15
      "b" => 5
      "a" => 10

    julia> # Change the priority of an existing key
           pq["a"] = 0; pq
    Base.Collections.PriorityQueue{Any,Any,Base.Order.ForwardOrdering} with 3 entries:
      "c" => 15
      "b" => 5
      "a" => 0

Heap Functions
--------------

Along with the :obj:`PriorityQueue` type, the :mod:`Collections` module provides
lower level functions for performing binary heap operations on arrays. Each
function takes an optional ordering argument. If not given, default ordering
is used, so that elements popped from the heap are given in ascending order.

.. function:: heapify(v, ord::Ordering=Forward)

   .. Docstring generated from Julia source

   Returns a new vector in binary heap order, optionally using the given ordering.

   .. doctest::

       julia> a = [1,3,4,5,2];

       julia> Base.Collections.heapify(a)
       5-element Array{Int64,1}:
        1
        2
        4
        5
        3

       julia> Base.Collections.heapify(a, Base.Order.Reverse)
       5-element Array{Int64,1}:
        5
        3
        4
        1
        2

.. function:: heapify!(v, ord::Ordering=Forward)

   .. Docstring generated from Julia source

   In-place :func:`heapify`\ .

.. function:: isheap(v, ord::Ordering=Forward)

   .. Docstring generated from Julia source

   Return ``true`` if an array is heap-ordered according to the given order.

   .. doctest::

       julia> a = [1,2,3]
       3-element Array{Int64,1}:
        1
        2
        3

       julia> Base.Collections.isheap(a,Base.Order.Forward)
       true

       julia> Base.Collections.isheap(a,Base.Order.Reverse)
       false

.. function:: heappush!(v, x, [ord])

   .. Docstring generated from Julia source

   Given a binary heap-ordered array, push a new element ``x``\ , preserving the heap property. For efficiency, this function does not check that the array is indeed heap-ordered.

.. function:: heappop!(v, [ord])

   .. Docstring generated from Julia source

   Given a binary heap-ordered array, remove and return the lowest ordered element. For efficiency, this function does not check that the array is indeed heap-ordered.