.. currentmodule:: Base

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

Iteration
---------

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

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

is translated to::

    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.

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

   Get initial iteration state for an iterable object

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

   Test whether we are done iterating

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

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

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

   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 ``zip`` is its own inverse: ``[zip(zip(a...)...)...] == [a...]``.

.. function:: enumerate(iter)

   Return an iterator that yields ``(i, x)`` where ``i`` is an index 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 index ``i`` of the iterations.

   .. doctest::

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

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


Fully implemented by: ``Range``, ``UnitRange``, ``NDRange``, ``Tuple``, ``Real``, ``AbstractArray``, ``IntSet``, ``ObjectIdDict``, ``Dict``, ``WeakKeyDict``, ``EachLine``, ``String``, ``Set``, ``Task``.

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

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

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

   .. doctest::

       julia> isempty([])
       true

       julia> isempty([1 2 3])
       false

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

   Remove all elements from a ``collection``.

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

   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

   Returns the last index of the collection.

   .. doctest::

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

Fully implemented by: ``Range``, ``UnitRange``, ``Tuple``, ``Number``, ``AbstractArray``, ``IntSet``, ``Dict``, ``WeakKeyDict``, ``String``, ``Set``.

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

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

   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 Sets
   check whether the item is ``isequal`` to one of the elements. Dicts look for
   ``(key,value)`` pairs, and the key is compared using ``isequal``. To test
   for the presence of a key in a dictionary, use ``haskey`` or
   ``k in keys(dict)``.

.. function:: eltype(collection)

   Determine the type of the elements generated by iterating ``collection``.
   For associative collections, this will be a ``(key,value)`` tuple type.

.. function:: indexin(a, b)

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

.. function:: findin(a, b)

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

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

   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:: reduce(op, v0, itr)

   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)

   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)

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

.. function:: foldl(op, itr)

   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)

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

.. function:: foldr(op, itr)

   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)

   Returns the largest element in a collection.

.. function:: maximum(A, dims)

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

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

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

.. function:: minimum(itr)

   Returns the smallest element in a collection.

.. function:: minimum(A, dims)

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

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

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

.. function:: extrema(itr)

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

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

   Returns the index of the maximum element in a collection.

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

   Returns the index of the minimum element in a collection.

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

   Returns the maximum element and its index.

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

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

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

   Returns the minimum element and its index.

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

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

.. function:: maxabs(itr)

   Compute the maximum absolute value of a collection of values.

.. function:: maxabs(A, dims)

   Compute the maximum absolute values over given dimensions.

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

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

.. function:: minabs(itr)

   Compute the minimum absolute value of a collection of values.

.. function:: minabs(A, dims)

   Compute the minimum absolute values over given dimensions.

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

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

.. function:: sum(itr)

   Returns the sum of all elements in a collection.

.. function:: sum(A, dims)

   Sum elements of an array over the given dimensions.

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

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

.. function:: sum(f, itr)

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

.. function:: sumabs(itr)

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

.. function:: sumabs(A, dims)

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

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

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

.. function:: sumabs2(itr)

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

.. function:: sumabs2(A, dims)

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

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

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

.. function:: prod(itr)

   Returns the product of all elements of a collection.

.. function:: prod(A, dims)

   Multiply elements of an array over the given dimensions.

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

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

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

   Test whether any elements of a boolean collection are true.

.. function:: any(A, dims)

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

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

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

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

   Test whether all elements of a boolean collection are true.

.. function:: all(A, dims)

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

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

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

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

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

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

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

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

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

   .. doctest::

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

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

   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)

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

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

   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)

   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.

   ``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
   ``reduce`` and ``map``.

   .. doctest::

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

   The associativity of the reduction is implementation-dependent. Use
   :func:`mapfoldl` or :func:`mapfoldr` instead for guaranteed left or
   right associativity.

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

   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)

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

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

   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)

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

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

   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)

   Get the first element of an iterable collection.

.. function:: last(coll)

   Get the last element of an ordered collection, if it can be computed in O(1) time.
   This is accomplished by calling ``endof`` to get the last index.

.. function:: step(r)

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

.. function:: collect(collection)

   Return an array of all items in a collection. For associative collections, returns (key, value) tuples.

.. function:: collect(element_type, collection)

   Return an array of type ``Array{element_type,1}`` of all items in a collection.

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

   Determine whether every element of ``a`` is also in ``b``, using the
   ``in`` function.

.. function:: filter(function, collection)

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

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

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

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

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

Fully implemented by: ``Array``, ``DArray``, ``BitArray``, ``AbstractArray``, ``SubArray``, ``ObjectIdDict``, ``Dict``, ``WeakKeyDict``, ``String``.

Partially implemented by: ``Range``, ``UnitRange``, ``Tuple``.

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

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

``ObjectIdDict`` is a special hash table where the keys are always object identities. ``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.

Dicts can be created using a literal syntax: ``{"A"=>1, "B"=>2}``. Use of curly brackets will create a ``Dict`` of type ``Dict{Any,Any}``. Use of square brackets will attempt to infer type information from the keys and values (i.e. ``["A"=>1, "B"=>2]`` creates a ``Dict{ASCIIString, Int64}``). To explicitly specify types use the syntax: ``(KeyType=>ValueType)[...]``. For example, ``(ASCIIString=>Int32)["A"=>1, "B"=>2]``.

As with arrays, ``Dicts`` may be created with comprehensions. For example,
``{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()

   ``Dict{K,V}()`` constructs a hash



   table with keys of type K and values of type V.
   The literal syntax is ``{"A"=>1, "B"=>2}`` for a ``Dict{Any,Any}``, or
   ``["A"=>1, "B"=>2]`` for a ``Dict`` of inferred type.

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

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

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

   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)

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

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

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

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

   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)

   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::

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

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

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

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

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

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

   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)

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

.. function:: values(collection)

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

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

   Construct a merged collection from the given collections.

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

   Update collection with pairs from the other collections

.. function:: sizehint(s, n)

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

Fully implemented by: ``ObjectIdDict``, ``Dict``, ``WeakKeyDict``.

Partially implemented by: ``IntSet``, ``Set``, ``EnvHash``, ``Array``, ``BitArray``.

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

.. function:: Set([itr])

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

.. function:: IntSet([itr])

   Construct a sorted set of the integers generated by the given iterable object, or an empty set. Implemented as a bit string, and therefore designed for dense integer sets. Only non-negative integers can be stored. If the set will be sparse (for example holding a single very large integer), use ``Set`` instead.

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

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

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

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

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

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

.. function:: setdiff(s1,s2)

   Construct the set of elements in ``s1`` but not ``s2``. 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.

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

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

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

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

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

   IntSet s is destructively modified to toggle the inclusion of integer ``n``.

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

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

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

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

.. function:: complement(s)

   Returns the set-complement of IntSet ``s``.

.. function:: complement!(s)

   Mutates IntSet ``s`` into its set-complement.

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

   Intersects IntSets ``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

   True if A is a subset of or equal to S.

Fully implemented by: ``IntSet``, ``Set``.

Partially implemented by: ``Array``.

Dequeues
--------

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

   Insert items at the end of a collection.

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

   Remove the last item in a collection and return it.

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

   Insert items at the beginning of a collection.

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

   Remove the first item in a collection.

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

   Insert an item at the given index.

.. function:: deleteat!(collection, index)

   Remove the item at the given index, and return the modified collection. Subsequent items
   are shifted to fill the resulting gap.

.. function:: deleteat!(collection, itr)

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

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

   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.

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

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

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

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

   Resize collection to contain ``n`` elements.

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

   Add the elements of ``items`` to the end of a collection.

   .. doctest::

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

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

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

   .. doctest::

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

Fully implemented by: ``Vector`` (aka 1-d ``Array``), ``BitVector`` (aka 1-d ``BitArray``).


.. module:: Base.Collections

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

The ``PriorityQueue`` type is available from the ``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])

   Construct a new 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``.

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

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

.. function:: dequeue!(pq)

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

.. function:: peek(pq)

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

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

  # Julia code
  pq = Collections.PriorityQueue()

  # Insert keys with associated priorities
  pq["a"] = 10
  pq["b"] = 5
  pq["c"] = 15

  # Change the priority of an existing key
  pq["a"] = 0


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

Along with the ``PriorityQueue`` type, the ``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])

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

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

   In-place heapify.

.. function:: isheap(v, [ord])

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

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

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

   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.