.. default-domain:: chpl

.. module:: List
   :synopsis: This module contains the implementation of Chapel's standard 'list' type.

List
====
**Usage**

.. code-block:: chapel

   use List;


or

.. code-block:: chapel

   import List;


This module contains the implementation of Chapel's standard 'list' type.

A list is a lightweight container similar to an array that is suitable for
building up and iterating over a collection of elements in a structured
manner.

The highly parallel nature of Chapel means that great care should be taken
when performing operations that may invalidate references to list elements.
Inserts and removals into the middle of a list are example operations that
may invalidate references. Appending an element to the end of a list will
never invalidate references to elements contained in the list.

The following operations may invalidate references to elements contained in
a list:

    - insert
    - remove
    - pop
    - clear
    - sort

Additionally, all references to list elements are invalidated when the list
is deinitialized.

Lists are not parallel safe by default, but can be made parallel safe by
setting the param formal `parSafe` to true in any list constructor. When
constructed from another list, the new list will inherit the parallel safety
mode of its originating list. Note that the ``parSafe`` mode is currently
unstable and will eventually be replaced by a standalone parallel-safe list
type.

Inserts and removals into a list are O(n) worst case and should be performed
with care. Appends into a list have an amortized speed of O(1). Indexing
into a list is O(1).

.. record:: list : serializable

   
   A list is a lightweight container suitable for building up and iterating
   over a collection of elements in a structured manner. Unlike a stack, the
   list type also supports inserts or removals into the middle of the list.
   The list type is close in spirit to its Python counterpart, with fast O(1)
   random access and append operations.
   
   The list type is not parallel safe by default. For situations in which
   such protections are desirable, parallel safety can be enabled by setting
   `parSafe = true` in any list constructor.
   
   Unlike an array, the set of indices of a list is always `0..<size`.
   

   .. attribute:: type eltType

      The type of the elements contained in this list. 

   .. attribute:: param parSafe = false

      .. warning::

         'list.parSafe' is unstable and is expected to be replaced by a separate list type in the future

   .. method:: proc init(type eltType)

      
      Initializes an empty list.
      
      :arg eltType: The type of the elements of this list.
      

   .. method:: proc init(type eltType, param parSafe = false)

      .. warning::

         'list.parSafe' is unstable and is expected to be replaced by a separate list type in the future

      
      Initializes an empty list.
      
      :arg eltType: The type of the elements of this list.
      
      :arg parSafe: If `true`, this list will use parallel safe operations.
      :type parSafe: `param bool`
      

   .. method:: proc init(other: list(?t))

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in another list.
      
      Used in new expressions.
      
      :arg other: The list to initialize from.
      

   .. method:: proc init(other: list(?t), param parSafe = other.parSafe)

      .. warning::

         'list.parSafe' is unstable and is expected to be replaced by a separate list type in the future

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in another list.
      
      Used in new expressions.
      
      :arg other: The list to initialize from.
      
      :arg parSafe: If `true`, this list will use parallel safe operations.
      :type parSafe: `param bool`
      

   .. method:: proc init(other: [?d] ?t)

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in an array.
      
      Used in new expressions.
      
      :arg other: The array to initialize from.
      

   .. method:: proc init(other: [?d] ?t, param parSafe = false)

      .. warning::

         'list.parSafe' is unstable and is expected to be replaced by a separate list type in the future

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in an array.
      
      Used in new expressions.
      
      :arg other: The array to initialize from.
      
      :arg parSafe: If `true`, this list will use parallel safe operations.
      :type parSafe: `param bool`
      

   .. method:: proc init(other: range(?t))

      
      Initializes a list containing elements that are copy initialized from
      the elements yielded by a range.
      
      Used in new expressions.
      
      .. note::
      
        Attempting to initialize a list from an unbounded range will trigger
        a compiler error.
      
      :arg other: The range to initialize from.
      

   .. method:: proc init(other: range(?t), param parSafe = false)

      .. warning::

         'list.parSafe' is unstable and is expected to be replaced by a separate list type in the future

      
      Initializes a list containing elements that are copy initialized from
      the elements yielded by a range.
      
      Used in new expressions.
      
      .. note::
      
        Attempting to initialize a list from an unbounded range will trigger
        a compiler error.
      
      :arg other: The range to initialize from.
      
      :arg parSafe: If `true`, this list will use parallel safe operations.
      :type parSafe: `param bool`
      

   .. method:: proc init=(other: list)

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in another list.
      
      ``this.parSafe`` will default to ``false`` if it is not yet set.
      
      :arg other: The list to initialize from.
      

   .. method:: proc init=(other: [])

      
      Initializes a list containing elements that are copy initialized from
      the elements contained in an array.
      
      ``this.parSafe`` will default to ``false`` if it is not yet set.
      
      :arg other: The array to initialize from.
      

   .. method:: proc init=(other: range(?))

      
      Initializes a list containing elements that are copy initialized from
      the elements yielded by a range.
      
      ``this.parSafe`` will default to ``false`` if it is not yet set.
      
      .. note::
      
        Attempting to initialize a list from an unbounded range will trigger
        a compiler error.
      
      :arg other: The range to initialize from.
      

   .. method:: proc ref pushBack(in x: this.eltType): int

      
      Add an element to the end of this list.
      
      :arg x: An element to append.
      :type x: `eltType`
      
      :return: List index where element was inserted.
      :rtype: `int`
      

   .. method:: proc ref pushBack(other: list(eltType, ?p))

      
      Push a copy of each element contained in another list to the end of this
      list.
      
      :arg other: A list containing elements of the same type as those
        contained in this list.
      :type other: `list(eltType)`
      
      :return: List indices where elements were inserted.
      :rtype: `range`
      

   .. method:: proc ref pushBack(other: [?d] eltType)

      
      Push a copy of each element contained in an array to the end of this
      list.
      
      :arg other: An array containing elements of the same type as those
        contained in this list.
      :type other: `[?d] eltType`
      
      :return: List indices where elements were inserted.
      :rtype: `range`
      

   .. method:: proc ref pushBack(other: range(eltType, ?b, ?d))

      
      Push a copy of each element yielded by a range to the end of this list.
      
      .. note::
      
        Attempting to initialize a list from an unbounded range will trigger
        a compiler error.
      
      :arg other: The range to initialize from.
      :type other: `range(eltType)`
      
      :return: List indices where elements were inserted.
      :rtype: `range`
      

   .. method:: proc contains(x: eltType): bool

      
      Returns `true` if this list contains an element equal to the value of
      `x`, and `false` otherwise.
      
      :arg x: An element to search for.
      :type x: `eltType`
      
      :return: `true` if this list contains `x`.
      :rtype: `bool`
      

   .. method:: proc ref first ref

      
      Returns a reference to the first item in this list.
      
      .. warning::
      
        Calling this method on an empty list will cause the currently running
        program to halt. If the `--fast` flag is used, no safety checks will
        be performed.
      
      :return: A reference to the first item in this list.
      :rtype: `ref eltType`
      

   .. method:: proc ref last ref

      
      Returns a reference to the last item in this list.
      
      .. warning::
      
        Calling this method on an empty list will cause the currently running
        program to halt. If the `--fast` flag is used, no safety checks will
        be performed.
      
      :return: A reference to the last item in this list.
      :rtype: `ref eltType`
      

   .. method:: proc ref insert(idx: int, in x: eltType): bool

      
      Insert an element at a given position in this list, shifting all elements
      currently at and following that index one to the right. The call
      ``a.insert(0, x)`` inserts an element at the front of the list `a`, and
      ``a.insert((a.size), x)`` is equivalent to ``a.pushBack(x)``.
      
      If the insertion is successful, this method returns `true`. If the given
      index is out of bounds, this method does nothing and returns `false`.
      
      .. warning::
      
        Inserting an element into this list may invalidate existing references
        to the elements contained in this list.
      
      :arg idx: The index into this list at which to insert.
      :type idx: `int`
      
      :arg x: The element to insert.
      :type x: `eltType`
      
      :return: `true` if `x` was inserted, `false` otherwise.
      :rtype: `bool`
      

   .. method:: proc ref insert(idx: int, arr: [?d] eltType): bool

      
      Insert an array of elements `arr` into this list at index `idx`,
      shifting all elements at and following the index `arr.size` positions
      to the right.
      
      If the insertion is successful, this method returns `true`. If the given
      index is out of bounds, this method does nothing and returns `false`.
      
      .. warning::
      
        Inserting elements into this list may invalidate existing references
        to the elements contained in this list.
      
      :arg idx: The index into this list at which to insert.
      :type idx: `int`
      
      :arg arr: An array of elements to insert.
      :type x: `[] eltType`
      
      :return: `true` if `arr` was inserted, `false` otherwise.
      :rtype: `bool`
      

   .. method:: proc ref insert(idx: int, lst: list(eltType)): bool

      
      Insert a list of elements `lst` into this list at index `idx`, shifting
      all elements at and following the index `lst.size` positions to the
      right.
      
      If the insertion is successful, this method returns `true`. If the given
      index is out of bounds, this method does nothing and returns `false`.
      
      .. warning::
      
        Inserting elements into this list may invalidate existing references
        to the elements contained in this list.
      
      :arg idx: The index into this list at which to insert.
      :type idx: `int`
      
      :arg lst: A list of elements to insert.
      :type lst: `list(eltType)`
      
      :return: `true` if `lst` was inserted, `false` otherwise.
      :rtype: `bool`
      

   .. method:: proc ref remove(x: eltType, count: int = 1): int

      
      Remove the first `count` elements from this list with values equal to
      `x`, shifting all elements following the removed item left.
      
      If the count of elements to remove is less than or equal to zero, then
      all elements from this list equal to the value of `x` will be removed.
      
      .. warning::
      
        Removing elements from this list may invalidate existing references
        to the elements contained in this list.
      
      :arg x: The value of the element to remove.
      :type x: `eltType`
      
      :arg count: The number of elements to remove.
      :type count: `int`
      
      :return: The number of elements removed.
      :rtype: `int`
      

   .. method:: proc ref popBack(): eltType

      
      Remove the element at the end of this list and return it.
      
      .. warning::
      
        Popping an element from this list will invalidate any reference to
        the element taken while it was contained in this list.
      
      .. warning::
      
        Calling this method on an empty list will cause the currently running
        program to halt. If the `--fast` flag is used, no safety checks will
        be performed.
      
      :return: The element popped.
      :rtype: `eltType`
      

   .. method:: proc ref getAndRemove(idx: int): eltType

      
      Remove the element at the index `idx` from this list and return it. The
      elements at indices after `idx` are shifted one to the left in memory,
      making this operation O(n).
      
      .. warning::
      
        Removing an element from this list will invalidate any reference to
        the element taken while it was contained in this list.
      
      .. warning::
      
        Calling this method on an empty list or with values of `idx` that
        are out of bounds will cause the currently running program to halt.
        If the `--fast` flag is used, no safety checks will be performed.
      
      :arg idx: The index of the element to remove.
      :type idx: `int`
      
      :return: The element popped.
      :rtype: `eltType`
      

   .. method:: proc ref clear()

      
      Clear the contents of this list.
      
      .. warning::
      
        Clearing the contents of this list will invalidate all existing
        references to the elements contained in this list.
      

   .. method:: proc find(x: eltType, start: int = 0, end: int = -1): int

      
      Return a zero-based index into this list of the first item whose value
      is equal to `x`. If no such element can be found or if the list is empty,
      this method returns the value `-1`.
      
      .. warning::
      
        Calling this method with values of `start` or `end` that are out of bounds
        will cause the currently running program to halt. If the `--fast` flag is
        used, no safety checks will be performed.
      
      :arg x: An element to search for.
      :type x: `eltType`
      
      :arg start: The start index to start searching from.
      :type start: `int`
      
      :arg end: The end index to stop searching at. A value less than
                `0` will search the entire list.
      :type end: `int`
      
      :return: The index of the element to search for, or `-1` on error.
      :rtype: `int`
      

   .. method:: proc count(x: eltType): int

      
      Return the number of times a given element is found in this list.
      
      :arg x: An element to count.
      :type x: `eltType`
      
      :return: The number of times a given element is found in this list.
      :rtype: `int`
      

   .. method:: proc ref sort(comparator: ?rec = Sort.defaultComparator)

      .. warning::

         'list.sort' is unstable and may be replaced or modified in a future release

      
      Sort the items of this list in place using a comparator. If no comparator
      is provided, sort this list using the default sort order of its elements.
      
      .. warning::
      
        Sorting the elements of this list may invalidate existing references
        to the elements contained in this list.
      
      :arg comparator: A comparator used to sort this list.
      

   .. method:: proc getValue(i: int): eltType

      
      Return a copy of the element at a given index in this list.
      
      :arg i: The index of the element to get.
      
      .. warning::
      
        Use of the `getValue` method with an out of bounds index (while
        bounds checking is on) will cause the currently running program
        to halt.
      
      :return: A copy of an element from this list.
      

   .. method:: proc getBorrowed(i: int) where isClass(eltType)

      
      Return a borrow of the element at a given index in this list. This
      method can only be called when this list's element type is a class
      type.
      
      :arg i: The index of the element to borrow.
      :type i: `int`
      
      :return: A borrow of an element from this list.
      

   .. method:: proc ref replace(i: int, in x: eltType): bool

      
      Replaces the value at a given index with a new value. This method returns
      `false` if the index is out of bounds.
      
      :arg i: The index of the element to replace
      :type i: int
      
      :arg x: The value to set at index `i`
      
      :return: `true` if `i` is a valid index that has been set to `x`,
               and `false` otherwise.
      :rtype: bool
      

   .. method:: proc update(i: int, updater) throws

      
      Update a value in this list in a parallel safe manner via an updater
      object.
      
      The updater object passed to the `update()` method must
      define a `this()` method that takes two arguments: an integer index,
      and a second argument of this list's `valType`. The updater object's
      `this()` method must return some sort of value. Updater objects that
      do not need to return anything may return `none`.
      
      If the updater object's `this()` method throws, the thrown error will
      be propagated out of `update()`.
      
      :arg i: The index to update
      :type i: `int`
      
      :arg updater: A class or record used to update the value at `i`
      :return: What the updater object returns
      

   .. method:: proc ref this(i: int) ref

      
      Index this list via subscript. Returns a reference to the element at a
      given index in this list.
      
      :arg i: The index of the element to access
      
      .. warning::
      
        Use of the `this()` method with an out of bounds index (while bounds
        checking is on) will cause the currently running program to
        halt.
      
      .. note::
      
        The `this()` method cannot be used with lists instantiated with a
        `parSafe` value of `true`. Attempting to do so will trigger
        a compiler error.
      
      :return: A reference to an element in this list
      

   .. itermethod:: iter these() ref

      
      Iterate over the elements of this list.
      
      :yields: A reference to one of the elements contained in this list.
      

   .. method:: proc serialize(writer: fileWriter(?), ref serializer) throws

      
      Write the contents of this list to a ``fileWriter``.
      

   .. method:: proc ref deserialize(reader: fileReader, ref deserializer) throws

      
      Read the contents of this list from a ``fileReader``.
      

   .. method:: proc isEmpty(): bool

      
      Returns `true` if this list contains zero elements.
      
      :return: `true` if this list is empty.
      :rtype: `bool`
      

   .. method:: proc size

      
      The current number of elements contained in this list.
      

   .. method:: proc indices

      
      Returns the list's legal indices as the range ``0..<this.size``.
      
      :return: ``0..<this.size``
      :rtype: `range`
      

   .. method:: proc toArray(): [] eltType

      
      Returns a new DefaultRectangular array containing a copy of each of the
      elements contained in this list.
      
      :return: A new DefaultRectangular array.
      

.. method:: operator list. = (ref lhs: list(?t, ?), rhs: list(t, ?))

   
   Clear the contents of this list, then extend this now empty list with the
   elements contained in another list.
   
   .. warning::
   
     This will invalidate any references to elements previously contained in
     `lhs`.
   
   :arg lhs: The list to assign to.
   :arg rhs: The list to assign from.
   

.. method:: operator list.==(a: list(?t, ?), b: list(t, ?)): bool

   
   Returns `true` if the contents of two lists are the same.
   
   :arg a: A list to compare.
   :arg b: A list to compare.
   
   :return: `true` if the contents of two lists are equal.
   :rtype: `bool`
   

.. method:: operator list.!=(a: list(?t, ?), b: list(t, ?)): bool

   
   Return `true` if the contents of two lists are not the same.
   
   :arg a: A list to compare.
   :arg b: A list to compare.
   
   :return: `true` if the contents of two lists are not equal.
   :rtype: `bool`
   

.. function:: operator :(rhs: list, type t: list)

   
   Initializes a list containing elements that are copy initialized from
   the elements contained in another list.
   
   See :proc:`~list.init=`
   

.. function:: operator :(rhs: [], type t: list)

   
   Initializes a list containing elements that are copy initialized from
   the elements contained in an array.
   
   See :proc:`~list.init=`
   

.. function:: operator :(rhs: range(?), type t: list)

   
   Initializes a list containing elements that are copy initialized from
   the elements yielded by a range.
   
   See :proc:`~list.init=`