List¶
Usage
use List;
or
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.
- type eltType¶
The type of the elements contained in this list.
- param parSafe = false¶
Warning
‘list.parSafe’ is unstable and is expected to be replaced by a separate list type in the future
- proc init(type eltType)¶
Initializes an empty list.
- Arguments
eltType – The type of the elements of this list.
- 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.
- Arguments
eltType – The type of the elements of this list.
parSafe : param bool – If true, this list will use parallel safe operations.
- 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.
- Arguments
other – The list to initialize from.
- 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.
- Arguments
other – The list to initialize from.
parSafe : param bool – If true, this list will use parallel safe operations.
- 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.
- Arguments
other – The array to initialize from.
- 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.
- Arguments
other – The array to initialize from.
parSafe : param bool – If true, this list will use parallel safe operations.
- 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.
- Arguments
other – The range to initialize from.
- 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.
- Arguments
other – The range to initialize from.
parSafe : param bool – If true, this list will use parallel safe operations.
- proc init=(other: list)¶
Initializes a list containing elements that are copy initialized from the elements contained in another list.
this.parSafe
will default tofalse
if it is not yet set.- Arguments
other – The list to initialize from.
- proc init=(other: [])
Initializes a list containing elements that are copy initialized from the elements contained in an array.
this.parSafe
will default tofalse
if it is not yet set.- Arguments
other – The array to initialize from.
- proc init=(other: range(?))
Initializes a list containing elements that are copy initialized from the elements yielded by a range.
this.parSafe
will default tofalse
if it is not yet set.Note
Attempting to initialize a list from an unbounded range will trigger a compiler error.
- Arguments
other – The range to initialize from.
- proc ref pushBack(in x: this.eltType): int¶
Add an element to the end of this list.
- Arguments
x : eltType – An element to append.
- Returns
List index where element was inserted.
- Return type
int
- proc ref pushBack(other: list(eltType, ?p))
Push a copy of each element contained in another list to the end of this list.
- Arguments
other : list(eltType) – A list containing elements of the same type as those contained in this list.
- Returns
List indices where elements were inserted.
- Return type
range
- proc ref pushBack(other: [?d] eltType)
Push a copy of each element contained in an array to the end of this list.
- Arguments
other : [?d] eltType – An array containing elements of the same type as those contained in this list.
- Returns
List indices where elements were inserted.
- Return type
range
- 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.
- Arguments
other : range(eltType) – The range to initialize from.
- Returns
List indices where elements were inserted.
- Return type
range
- proc contains(x: eltType): bool¶
Returns true if this list contains an element equal to the value of x, and false otherwise.
- Arguments
x : eltType – An element to search for.
- Returns
true if this list contains x.
- Return type
bool
- 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.
- Returns
A reference to the first item in this list.
- Return type
ref eltType
- 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.
- Returns
A reference to the last item in this list.
- Return type
ref eltType
- 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, anda.insert((a.size), x)
is equivalent toa.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.
- Arguments
idx : int – The index into this list at which to insert.
x : eltType – The element to insert.
- Returns
true if x was inserted, false otherwise.
- Return type
bool
- 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.
- Arguments
idx : int – The index into this list at which to insert.
arr – An array of elements to insert.
- Returns
true if arr was inserted, false otherwise.
- Return type
bool
- 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.
- Arguments
idx : int – The index into this list at which to insert.
lst : list(eltType) – A list of elements to insert.
- Returns
true if lst was inserted, false otherwise.
- Return type
bool
- 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.
- Arguments
x : eltType – The value of the element to remove.
count : int – The number of elements to remove.
- Returns
The number of elements removed.
- Return type
int
- 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.
- Returns
The element popped.
- Return type
eltType
- 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.
- Arguments
idx : int – The index of the element to remove.
- Returns
The element popped.
- Return type
eltType
- 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.
- 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.
- Arguments
x : eltType – An element to search for.
start : int – The start index to start searching from.
end : int – The end index to stop searching at. A value less than 0 will search the entire list.
- Returns
The index of the element to search for, or -1 on error.
- Return type
int
- proc count(x: eltType): int¶
Return the number of times a given element is found in this list.
- Arguments
x : eltType – An element to count.
- Returns
The number of times a given element is found in this list.
- Return type
int
- 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.
- Arguments
comparator – A comparator used to sort this list.
- proc getValue(i: int): eltType¶
Return a copy of the element at a given index in this list.
- Arguments
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.
- Returns
A copy of an element from this list.
- 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.
- Arguments
i : int – The index of the element to borrow.
- Returns
A borrow of an element from this list.
- 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.
- Arguments
i :
int
– The index of the element to replacex – The value to set at index i
- Returns
true if i is a valid index that has been set to x, and false otherwise.
- Return type
bool
- 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().
- Arguments
i : int – The index to update
updater – A class or record used to update the value at i
- Returns
What the updater object returns
- proc ref this(i: int) ref¶
Index this list via subscript. Returns a reference to the element at a given index in this list.
- Arguments
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.
- Returns
A reference to an element in this list
- iter these() ref¶
Iterate over the elements of this list.
- Yields
A reference to one of the elements contained in this list.
- proc writeThis(ch: fileWriter) throws¶
Write the contents of this list to a channel.
- Arguments
ch – A channel to write to.
- proc ref readThis(ch: fileReader) throws¶
Read the contents of this list from a channel.
- Arguments
ch – A channel to read from.
- proc isEmpty(): bool¶
Returns true if this list contains zero elements.
- Returns
true if this list is empty.
- Return type
bool
- proc size¶
The current number of elements contained in this list.
- proc indices¶
Returns the list’s legal indices as the range
0..<this.size
.- Returns
0..<this.size
- Return type
range
- proc toArray(): [] eltType¶
Returns a new DefaultRectangular array containing a copy of each of the elements contained in this list.
- Returns
A new DefaultRectangular array.
- 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.
- Arguments
lhs – The list to assign to.
rhs – The list to assign from.
- operator list.==(a: list(?t, ?), b: list(t, ?)): bool¶
Returns true if the contents of two lists are the same.
- Arguments
a – A list to compare.
b – A list to compare.
- Returns
true if the contents of two lists are equal.
- Return type
bool
- operator list.!=(a: list(?t, ?), b: list(t, ?)): bool¶
Return true if the contents of two lists are not the same.
- Arguments
a – A list to compare.
b – A list to compare.
- Returns
true if the contents of two lists are not equal.
- Return type
bool
- operator :(rhs: list, type t: list)¶
Initializes a list containing elements that are copy initialized from the elements contained in another list.
See
init=
- operator :(rhs: [], type t: list)
Initializes a list containing elements that are copy initialized from the elements contained in an array.
See
init=
- operator :(rhs: range(?), type t: list)
Initializes a list containing elements that are copy initialized from the elements yielded by a range.
See
init=