class Deque(T)
Overview
A Deque ("double-ended queue") is a collection of objects of type T that behaves much like an Array.
Deque has a subset of Array's API. It performs better than an Array
when there are frequent insertions or deletions
of items near the beginning or the end.
The most typical use case of a Deque is a queue: use #push
to add items to the end of the queue and #shift
to get
and remove the item at the beginning of the queue.
This Deque is implemented with a dynamic array used as a circular buffer.
Included Modules
Defined in:
deque.crjson/to_json.cr
Constructors
-
.additive_identity : self
Returns the additive identity of this type.
-
.new(size : Int, value : T)
Creates a new
Deque
of the given size filled with the same value in each position. -
.new(array : Array(T))
Creates a new
Deque
that copies its items from an Array. -
.new(initial_capacity : Int)
Creates a new empty
Deque
backed by a buffer that is initiallyinitial_capacity
big. - .new(pull : JSON::PullParser)
-
.new
Creates a new empty Deque
-
.new(size : Int, & : Int32 -> T)
Creates a new
Deque
of the given size and invokes the block once for each index of the deque, assigning the block's value in that index. - .new(pull : JSON::PullParser, &)
Class Method Summary
Instance Method Summary
-
#+(other : Deque(U)) forall U
Concatenation.
-
#<<(value : T)
Alias for
#push
. -
#==(other : Deque)
Returns
true
if it is passed aDeque
andequals?
returnstrue
for both deques, the caller and the argument. -
#clear
Removes all elements from
self
. -
#clone
Returns a new
Deque
that has this deque's elements cloned. -
#concat(other : Indexable) : self
Appends the elements of other to
self
, and returnsself
. - #concat(other : Enumerable(T)) : self
-
#delete(obj) : Bool
Removes all items from
self
that are equal to obj. -
#delete_at(index : Int) : T
Deletes the item that is present at the index.
-
#dup
Returns a new
Deque
that has exactly this deque's elements. -
#each(& : T -> ) : Nil
Yields each item in this deque, from first to last.
-
#insert(index : Int, value : T) : self
Insert a new item before the item at index.
-
#inspect(io : IO) : Nil
Appends a String representation of this object which includes its class name, its object address and the values of all instance variables.
-
#pop(n : Int) : Nil
Removes the last n (at most) items in the deque.
-
#pop : T
Removes and returns the last item.
-
#pop(&)
Removes and returns the last item, if not empty, otherwise executes the given block and returns its value.
-
#pop? : T | Nil
Removes and returns the last item, if not empty, otherwise
nil
. - #pretty_print(pp)
-
#push(value : T)
Adds an item to the end of the deque.
-
#reject!(& : T -> ) : self
Modifies
self
, deleting the elements in the collection for which the passed block is truthy. -
#reject!(pattern) : self
Modifies
self
, deleting the elements in the collection for whichpattern === element
. -
#rotate!(n : Int = 1) : Nil
Shifts all elements of
self
to the left n times. -
#select!(& : T -> ) : self
Modifies
self
, keeping only the elements in the collection for which the passed block is truthy. -
#select!(pattern) : self
Modifies
self
, keeping only the elements in the collection for whichpattern === element
. -
#shift(n : Int) : Nil
Removes the first n (at most) items in the deque.
-
#shift
Removes and returns the first item.
-
#shift(&)
Removes and returns the first item, if not empty, otherwise executes the given block and returns its value.
-
#shift?
Removes and returns the first item, if not empty, otherwise
nil
. -
#size : Int32
Returns the number of elements in the deque.
- #to_json(json : JSON::Builder) : Nil
-
#to_s(io : IO) : Nil
Appends a short String representation of this object which includes its class name and its object address.
-
#unsafe_fetch(index : Int) : T
Returns the element at the given index, without doing any bounds check.
-
#unsafe_put(index : Int, value : T)
Sets the element at the given index to value, without doing any bounds check.
-
#unshift(value : T) : self
Adds an item to the beginning of the deque.
Instance methods inherited from module Indexable::Mutable(T)
[]=(index : Int, value : T) : T
[]=,
fill(value : T, start : Int, count : Int) : selffill(value : T, range : Range) : self
fill(value : T) : self
fill(start : Int, count : Int, & : Int32 -> T) : self
fill(range : Range, & : Int32 -> T) : self
fill(*, offset : Int = 0, & : Int32 -> T) : self fill, map!(& : T -> _) : self map!, map_with_index!(offset = 0, & : T, Int32 -> _) : self map_with_index!, reverse! : self reverse!, rotate!(n : Int = 1) : self rotate!, shuffle!(random : Random = Random::DEFAULT) : self shuffle!, sort! : self
sort!(&block : T, T -> U) : self forall U sort!, sort_by!(&block : T -> _) : self sort_by!, swap(index0 : Int, index1 : Int) : self swap, unsafe_put(index : Int, value : T) unsafe_put, unstable_sort! : self
unstable_sort!(&block : T, T -> U) : self forall U unstable_sort!, unstable_sort_by!(&block : T -> _) : self unstable_sort_by!, update(index : Int, & : T -> _) : T update
Instance methods inherited from module Indexable(T)
[](index : Int)
[],
[]?(index : Int)
[]?,
bsearch(& : T -> _)
bsearch,
bsearch_index(& : T, Int32 -> _)
bsearch_index,
cartesian_product(*others : Indexable)
cartesian_product,
combinations(size : Int = self.size)
combinations,
dig(index : Int, *subindexes)
dig,
dig?(index : Int, *subindexes)
dig?,
each(& : T -> )each
each(*, start : Int, count : Int, & : T -> )
each(*, within range : Range, & : T -> ) each, each_cartesian(*others : Indexable, &)
each_cartesian(*others : Indexable) each_cartesian, each_combination(size : Int = self.size, reuse = false, &) : Nil
each_combination(size : Int = self.size, reuse = false) each_combination, each_index(& : Int32 -> ) : Nil
each_index
each_index(*, start : Int, count : Int, &) each_index, each_permutation(size : Int = self.size, reuse = false, &) : Nil
each_permutation(size : Int = self.size, reuse = false) each_permutation, each_repeated_combination(size : Int = self.size, reuse = false, &) : Nil
each_repeated_combination(size : Int = self.size, reuse = false) each_repeated_combination, empty? : Bool empty?, equals?(other : Indexable, &) : Bool
equals?(other, &) equals?, fetch(index : Int, &)
fetch(index, default) fetch, first(&) first, hash(hasher) hash, index(object, offset : Int = 0)
index(offset : Int = 0, & : T -> ) index, index!(obj, offset : Int = 0)
index!(offset : Int = 0, & : T -> ) index!, join(separator : String | Char | Number = "") : String join, last : T
last(&) last, last? : T | Nil last?, permutations(size : Int = self.size) : Array(Array(T)) permutations, repeated_combinations(size : Int = self.size) : Array(Array(T)) repeated_combinations, reverse_each(& : T -> ) : Nil
reverse_each reverse_each, rindex(value, offset = size - 1)
rindex(offset = size - 1, & : T -> ) rindex, rindex!(value, offset = size - 1)
rindex!(offset = size - 1, & : T -> ) rindex!, sample(n : Int, random : Random = Random::DEFAULT) : Array(T)
sample(random : Random = Random::DEFAULT) sample, size size, to_a(& : T -> U) : Array(U) forall U to_a, unsafe_fetch(index : Int) unsafe_fetch, values_at(*indexes : Int) values_at
Class methods inherited from module Indexable(T)
cartesian_product(indexables : Indexable(Indexable))
cartesian_product,
each_cartesian(indexables : Indexable(Indexable), reuse = false, &)each_cartesian(indexables : Indexable(Indexable), reuse = false) each_cartesian
Instance methods inherited from module Enumerable(T)
accumulate(initial : U) : Array(U) forall Uaccumulate : Array(T)
accumulate(initial : U, &block : U, T -> U) : Array(U) forall U
accumulate(&block : T, T -> T) : Array(T) accumulate, all?(& : T -> ) : Bool
all?(pattern) : Bool
all? : Bool all?, any?(& : T -> ) : Bool
any?(pattern) : Bool
any? : Bool any?, chunks(&block : T -> U) forall U chunks, compact_map(& : T -> _) compact_map, count(& : T -> ) : Int32
count(item) : Int32 count, cycle(n, & : T -> ) : Nil
cycle(& : T -> ) : Nil cycle, each(& : T -> ) each, each_cons(count : Int, reuse = false, &) each_cons, each_cons_pair(& : T, T -> ) : Nil each_cons_pair, each_slice(count : Int, reuse = false, &) each_slice, each_step(n : Int, *, offset : Int = 0, & : T -> ) : Nil each_step, each_with_index(offset = 0, &) each_with_index, each_with_object(obj : U, & : T, U -> ) : U forall U each_with_object, empty? : Bool empty?, find(if_none = nil, & : T -> ) find, find!(& : T -> ) : T find!, first(&)
first(count : Int) : Array(T)
first : T first, first? : T | Nil first?, flat_map(& : T -> _) flat_map, group_by(& : T -> U) forall U group_by, in_groups_of(size : Int, filled_up_with : U = nil) forall U
in_groups_of(size : Int, filled_up_with : U = nil, reuse = false, &) forall U in_groups_of, in_slices_of(size : Int) : Array(Array(T)) in_slices_of, includes?(obj) : Bool includes?, index(& : T -> ) : Int32 | Nil
index(obj) : Int32 | Nil index, index!(& : T -> ) : Int32
index!(obj) : Int32 index!, index_by(& : T -> U) : Hash(U, T) forall U index_by, join(io : IO, separator = "") : Nil
join(separator, io : IO) : Nil
join(separator = "") : String
join(io : IO, separator = "", & : T, IO -> )
join(separator, io : IO, &)
join(separator = "", & : T -> ) join, map(& : T -> U) : Array(U) forall U map, map_with_index(offset = 0, & : T, Int32 -> U) : Array(U) forall U map_with_index, max(count : Int) : Array(T)
max : T max, max? : T | Nil max?, max_by(& : T -> U) : T forall U max_by, max_by?(& : T -> U) : T | Nil forall U max_by?, max_of(& : T -> U) : U forall U max_of, max_of?(& : T -> U) : U | Nil forall U max_of?, min(count : Int) : Array(T)
min : T min, min? : T | Nil min?, min_by(& : T -> U) : T forall U min_by, min_by?(& : T -> U) : T | Nil forall U min_by?, min_of(& : T -> U) : U forall U min_of, min_of?(& : T -> U) : U | Nil forall U min_of?, minmax : Tuple(T, T) minmax, minmax? : Tuple(T | Nil, T | Nil) minmax?, minmax_by(& : T -> U) : Tuple(T, T) forall U minmax_by, minmax_by?(& : T -> U) : Tuple(T, T) | Tuple(Nil, Nil) forall U minmax_by?, minmax_of(& : T -> U) : Tuple(U, U) forall U minmax_of, minmax_of?(& : T -> U) : Tuple(U, U) | Tuple(Nil, Nil) forall U minmax_of?, none?(& : T -> ) : Bool
none?(pattern) : Bool
none? : Bool none?, one?(& : T -> ) : Bool
one?(pattern) : Bool
one? : Bool one?, partition(& : T -> ) : Tuple(Array(T), Array(T))
partition(type : U.class) forall U partition, present? : Bool present?, product(initial : Number)
product
product(initial : Number, & : T -> )
product(& : T -> _) product, reduce(memo, &)
reduce(&) reduce, reduce?(&) reduce?, reject(& : T -> )
reject(type : U.class) forall U
reject(pattern) : Array(T) reject, sample(n : Int, random : Random = Random::DEFAULT) : Array(T)
sample(random : Random = Random::DEFAULT) : T sample, select(& : T -> )
select(type : U.class) : Array(U) forall U
select(pattern) : Array(T) select, size : Int32 size, skip(count : Int) skip, skip_while(& : T -> ) : Array(T) skip_while, sum(initial)
sum
sum(initial, & : T -> )
sum(& : T -> ) sum, take_while(& : T -> ) : Array(T) take_while, tally(hash)
tally : Hash(T, Int32) tally, tally_by(hash, &)
tally_by(&block : T -> U) : Hash(U, Int32) forall U tally_by, to_a : Array(T)
to_a(& : T -> U) : Array(U) forall U to_a, to_h
to_h(& : T -> Tuple(K, V)) forall K, V to_h, to_set : Set(T)
to_set(&block : T -> U) : Set(U) forall U to_set, zip(*others : Indexable | Iterable | Iterator, &)
zip(*others : Indexable | Iterable | Iterator) zip, zip?(*others : Indexable | Iterable | Iterator, &)
zip?(*others : Indexable | Iterable | Iterator) zip?
Class methods inherited from module Enumerable(T)
element_type(x)
element_type
Instance methods inherited from module Iterable(T)
chunk(reuse = false, &block : T -> U) forall U
chunk,
chunk_while(reuse : Bool | Array(T) = false, &block : T, T -> B) forall B
chunk_while,
cycle(n)cycle cycle, each each, each_cons(count : Int, reuse = false) each_cons, each_cons_pair each_cons_pair, each_slice(count : Int, reuse = false) each_slice, each_step(n : Int)
each_step(n : Int, *, offset : Int) each_step, each_with_index(offset = 0) each_with_index, each_with_object(obj) each_with_object, slice_after(reuse : Bool | Array(T) = false, &block : T -> B) forall B
slice_after(pattern, reuse : Bool | Array(T) = false) slice_after, slice_before(reuse : Bool | Array(T) = false, &block : T -> B) forall B
slice_before(pattern, reuse : Bool | Array(T) = false) slice_before, slice_when(reuse : Bool | Array(T) = false, &block : T, T -> B) forall B slice_when
Instance methods inherited from class Reference
==(other : self)==(other : JSON::Any)
==(other : YAML::Any)
==(other) ==, dup dup, hash(hasher) hash, initialize initialize, inspect(io : IO) : Nil inspect, object_id : UInt64 object_id, pretty_print(pp) : Nil pretty_print, same?(other : Reference) : Bool
same?(other : Nil) same?, to_s(io : IO) : Nil to_s
Constructor methods inherited from class Reference
new
new,
unsafe_construct(address : Pointer, *args, **opts) : self
unsafe_construct
Class methods inherited from class Reference
pre_initialize(address : Pointer)
pre_initialize
Instance methods inherited from class Object
! : Bool
!,
!=(other)
!=,
!~(other)
!~,
==(other)
==,
===(other : JSON::Any)===(other : YAML::Any)
===(other) ===, =~(other) =~, as(type : Class) as, as?(type : Class) as?, class class, dup dup, hash(hasher)
hash hash, in?(collection : Object) : Bool
in?(*values : Object) : Bool in?, inspect(io : IO) : Nil
inspect : String inspect, is_a?(type : Class) : Bool is_a?, itself itself, nil? : Bool nil?, not_nil!(message)
not_nil! not_nil!, pretty_inspect(width = 79, newline = "\n", indent = 0) : String pretty_inspect, pretty_print(pp : PrettyPrint) : Nil pretty_print, responds_to?(name : Symbol) : Bool responds_to?, tap(&) tap, to_json(io : IO) : Nil
to_json : String to_json, to_pretty_json(indent : String = " ") : String
to_pretty_json(io : IO, indent : String = " ") : Nil to_pretty_json, to_s(io : IO) : Nil
to_s : String to_s, to_yaml(io : IO) : Nil
to_yaml : String to_yaml, try(&) try, unsafe_as(type : T.class) forall T unsafe_as
Class methods inherited from class Object
from_json(string_or_io, root : String)from_json(string_or_io) from_json, from_yaml(string_or_io : String | IO) from_yaml
Constructor Detail
Returns the additive identity of this type.
This is an empty deque.
Creates a new Deque
of the given size filled with the same value in each position.
Deque.new(3, 'a') # => Deque{'a', 'a', 'a'}
Creates a new Deque
that copies its items from an Array.
Deque.new([1, 2, 3]) # => Deque{1, 2, 3}
Creates a new empty Deque
backed by a buffer that is initially initial_capacity
big.
The initial_capacity
is useful to avoid unnecessary reallocations of the internal buffer in case of growth. If you
have an estimate of the maximum number of elements a deque will hold, you should initialize it with that capacity
for improved execution performance.
deq = Deque(Int32).new(5)
deq.size # => 0
Creates a new Deque
of the given size and invokes the block once for
each index of the deque, assigning the block's value in that index.
Deque.new(3) { |i| (i + 1) ** 2 } # => Deque{1, 4, 9}
Class Method Detail
Instance Method Detail
Concatenation. Returns a new Deque
built by concatenating
two deques together to create a third. The type of the new deque
is the union of the types of both the other deques.
Returns true
if it is passed a Deque
and equals?
returns true
for both deques, the caller and the argument.
deq = Deque{2, 3}
deq.unshift 1
deq == Deque{1, 2, 3} # => true
deq == Deque{2, 3} # => false
Returns a new Deque
that has this deque's elements cloned.
That is, it returns a deep copy of this deque.
Use #dup
if you want a shallow copy.
Appends the elements of other to self
, and returns self
.
deq = Deque{"a", "b"}
deq.concat(Deque{"c", "d"})
deq # => Deque{"a", "b", "c", "d"}
Removes all items from self
that are equal to obj.
a = Deque{"a", "b", "b", "b", "c"}
a.delete("b") # => true
a # => Deque{"a", "c"}
Deletes the item that is present at the index. Items to the right
of this one will have their indices decremented.
Raises IndexError
if trying to delete an element outside the deque's range.
a = Deque{1, 2, 3}
a.delete_at(1) # => 2
a # => Deque{1, 3}
Returns a new Deque
that has exactly this deque's elements.
That is, it returns a shallow copy of this deque.
Yields each item in this deque, from first to last.
Do not modify the deque while using this variant of #each
!
Insert a new item before the item at index. Items to the right of this one will have their indices incremented.
a = Deque{0, 1, 2}
a.insert(1, 7) # => Deque{0, 7, 1, 2}
Appends a String representation of this object which includes its class name, its object address and the values of all instance variables.
class Person
def initialize(@name : String, @age : Int32)
end
end
Person.new("John", 32).inspect # => #<Person:0x10fd31f20 @name="John", @age=32>
Removes and returns the last item. Raises IndexError
if empty.
a = Deque{1, 2, 3}
a.pop # => 3
a # => Deque{1, 2}
Removes and returns the last item, if not empty, otherwise executes the given block and returns its value.
Adds an item to the end of the deque.
a = Deque{1, 2}
a.push 3 # => Deque{1, 2, 3}
Modifies self
, deleting the elements in the collection for which the
passed block is truthy. Returns self
.
a = Deque{1, 6, 2, 4, 8}
a.reject! { |x| x > 3 }
a # => Deque{1, 2}
See also: Deque#reject
.
Modifies self
, deleting the elements in the collection for which
pattern === element
.
a = Deque{1, 6, 2, 4, 8}
a.reject!(3..7)
a # => Deque{1, 2, 8}
See also: Deque#reject
.
Shifts all elements of self
to the left n times. Returns self
.
a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a2 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a3 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a1.rotate!
a2.rotate!(1)
a3.rotate!(3)
a1 # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
a2 # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
a3 # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
Modifies self
, keeping only the elements in the collection for which the
passed block is truthy. Returns self
.
a = Deque{1, 6, 2, 4, 8}
a.select! { |x| x > 3 }
a # => Deque{6, 4, 8}
See also: Deque#select
.
Modifies self
, keeping only the elements in the collection for which
pattern === element
.
ary = [1, 6, 2, 4, 8]
ary.select!(3..7)
ary # => [6, 4]
See also: Deque#select
.
Removes and returns the first item. Raises IndexError
if empty.
a = Deque{1, 2, 3}
a.shift # => 1
a # => Deque{2, 3}
Removes and returns the first item, if not empty, otherwise executes the given block and returns its value.
Returns the number of elements in the deque.
Deque{:foo, :bar}.size # => 2
Appends a short String representation of this object which includes its class name and its object address.
class Person
def initialize(@name : String, @age : Int32)
end
end
Person.new("John", 32).to_s # => #<Person:0x10a199f20>
Returns the element at the given index, without doing any bounds check.
Indexable
makes sure to invoke this method with index in 0...size
,
so converting negative indices to positive ones is not needed here.
Clients never invoke this method directly. Instead, they access
elements with #[](index)
and #[]?(index)
.
This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.
Sets the element at the given index to value, without doing any bounds check.
Indexable::Mutable
makes sure to invoke this method with index in
0...size
, so converting negative indices to positive ones is not needed
here.
Clients never invoke this method directly. Instead, they modify elements
with #[]=(index, value)
.
This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.
Adds an item to the beginning of the deque.
a = Deque{1, 2}
a.unshift 0 # => Deque{0, 1, 2}