Class Deque
extends List implements Collection
A double-ended queue.
A collection of items, where new items can be added at the end. They can be removed at the beginning and the end. These operations are efficient and use an amortized time of O(1).
A deque is a generalization of a stack and a queue, and can be used for both purposes.
Constructors
Constructs an empty Deque.
Statics
Constructs a new Deque that initially contains the elements of the collection.
Methods
Adds the given element to the end of this instance.
Adds all elements of the given collection to this instance.
Inserts the given element at the beginning of this instance.
Removes all elements.
Iterates over the elements of this collection in reverse order.
Whether this instance is equal to other, using element-equals to compare the elements.
Equality only returns true when both operands are of the same type.
Returns false, if this instance and other are not of the same size, or if the contained elements are not equal themselves (using element-equals).
It is an error to compare self-recursive data-structures, if the element-equals block is not ensuring that the comparison leads to infinite loops.
Inheritance
Collections do *not* need to ensure that recursive data structures don't lead to infinite loops.
Fills values, computed by evaluating block, into list elements [from..to[.
Filters this instance using the given predicate.
Returns this instance if in-place is true. In this case replaces the elements in this list with the filtered elements.
Returns a new list if in-place is false (the default).
The result contains all the elements of this instance for which the predicate returns true.
The first element of the deque.
The deque must not be empty.
Searches for needle in the range from (inclusive) - to (exclusive).
If last is false (the default) returns the index of the first occurrence of needle in the given range from - to. Otherwise returns the last occurrence.
Returns -1 if needle is not contained in the range.
Calls if-absent without argument if the needle is not contained in the range, and returns the result of the call.
Uses binary search, with
<, > and ==, to find the element.The given range must be sorted.
Searches for needle in the sorted range from (inclusive) - to (exclusive).
Uses binary search with
<, > and == to find the needle.If not found, calls if-absent with the smallest index at which the element is greater than needle. If no such index exists (either because this instance is empty, or because the first element is greater than the needle) calls if-absent with to (where to was adjusted according to the rules in index-of --last needle from to).
Uses binary-compare to compare the elements in the sorted range.
The binary-compare block always receives one of the list elements as first argument, and the needle as second argument.
Uses binary-compare to compare the elements in the sorted range.
The binary-compare block always receives one of the list elements as first argument, and the needle as second argument.
Inserts the given value at the given index at.
It is valid to insert at the size position, in which case this is equivalent to add. It is also valid to add at the zero position, in which case this is equivalent to add-first.
If n is the shortest distance to the start or end of the deque, the operation runs in
O(n) and is thus not efficient for insertions that are not near the start or end of the deque.Calls stringify on each element of the list, and concatenates the results into one string, using the separator.
Examples
[1, 2].join ", " // "1, 2"
Calls the block on each element of the list, and concatenates the results into one string, using the separator.
Examples
[1, 2].join ", ": "0x$(%02x it)" // "0x01, 0x02"
The last element of the deque.
The deque must not be empty.
Invokes the given block on each element.
Returns this instance if in-place is true. In this case replaces the elements in this list with the mapped elements.
Returns a new list if in-place is false (the default).
Returns a slice of this list.
Slices are views on the underlying object. As such they see and modify the object they come from.
The parameter from is inclusive.
The parameter to is exclusive.
Advanced
Slices keep the whole underlying object alive. This can lead to memory waste if the underlying object is not used otherwise. In some cases it might thus make sense to call copy on the slice.
At the call-site the arguments from and to are passed in with the slice syntax:
list[from..to]. Since both arguments are optional (as they have default values), it is valid to omit from or to.Examples
list := [1, 2, 3, 4, 5]
sub := list[1..3] // A view into [2, 3]
sub[0] = 22
print list // => [1, 22, 3, 4, 5]
sub = list[..3] // A view into [1, 22, 3]
sub.sort --in-place // Sorts just the 3 values.
print sub // => [1, 3, 22]
print list // => [1, 3, 22, 4, 5]
sub2 := sub[1..]
print sub2 // => [3, 22]
sub2[1] = 499
print list // => [1, 3, 499, 4, 5]
sub3 := list[2..].copy // => Creates a copy of [499, 4, 5]
sub3[0] = 3 // This time only the copy is affected.
print sub3 // => [3, 4, 5]
print list // => [1, 3, 499, 4, 5]
Returns the element at the given index.
Sets the element at the given index to the given value.
The index must be in the range [0, size).
Removes the value at the given index at.
It is valid to remove at the size - 1 position, in which case this is equivalent to remove-last. It is also valid to remove at the zero position, in which case this is equivalent to remove-first.
If n is the shortest distance to the start or end of the deque, the operation runs in
O(n) and is thus not efficient for deletions that are not near the start or end of the deque.Returns the value that was removed.
Removes the first entry that is equal to the given needle.
Does nothing if the needle is not in this instance.
This operation is in
O(n) and thus not efficient.It is an error to call this method on lists that can't change size.
Removes all entries that are equal to the given needle.
Does nothing if the needle is not in this instance.
This operation is in
O(n) and thus not efficient.It is an error to call this method on lists that can't change size.
Removes the last entry that is equal to the given needle.
Does nothing if the needle is not in this instance.
This operation is in
O(n) and thus not efficient.It is an error to call this method on lists that can't change size.
Removes the first element of the deque.
Returns the removed element.
The deque must not be empty.
Removes the last element of the deque.
Returns the removed element.
The deque must not be empty.
Replaces this[index..index+(to-from)[ with source[from..to[
Reserves amount additional space in the backing store of this instance.
This operation is useful when you know that you will add amount elements to the deque, and you want to avoid reallocations.
Resizes the backing store of this instance to the given new-size.
Sorts the range [from..to[ using the given compare block.
The compare block must take two arguments
a and b and should return:- -1 if
a < b, - 0 if
a == b, and - 1 if
a > b.
Sorts the range [from..to[ using the the < and > operators.
The sort is stable, meaning that equal elements do not change their relative order.
Returns this instance if in-place is true.
Returns a new list if in-place is false (the default).