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.cr
json/to_json.cr

Constructors

Class Method Summary

Instance Method Summary

Instance methods inherited from module Indexable::Mutable(T)

[]=(index : Int, value : T) : T []=, fill(value : T, start : Int, count : Int) : self
fill(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 : Array(T)
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 U
accumulate : 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

Macros inherited from class Object

class_getter(*names, &block) class_getter, class_getter!(*names) class_getter!, class_getter?(*names, &block) class_getter?, class_property(*names, &block) class_property, class_property!(*names) class_property!, class_property?(*names, &block) class_property?, class_setter(*names) class_setter, def_clone def_clone, def_equals(*fields) def_equals, def_equals_and_hash(*fields) def_equals_and_hash, def_hash(*fields) def_hash, delegate(*methods, to object) delegate, forward_missing_to(delegate) forward_missing_to, getter(*names, &block) getter, getter!(*names) getter!, getter?(*names, &block) getter?, property(*names, &block) property, property!(*names) property!, property?(*names, &block) property?, setter(*names) setter

Constructor Detail

def self.additive_identity : self #

Returns the additive identity of this type.

This is an empty deque.


[View source]
def self.new(size : Int, value : T) #

Creates a new Deque of the given size filled with the same value in each position.

Deque.new(3, 'a') # => Deque{'a', 'a', 'a'}

[View source]
def self.new(array : Array(T)) #

Creates a new Deque that copies its items from an Array.

Deque.new([1, 2, 3]) # => Deque{1, 2, 3}

[View source]
def self.new(initial_capacity : Int) #

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

[View source]
def self.new(pull : JSON::PullParser) #

[View source]
def self.new #

Creates a new empty Deque


[View source]
def self.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.

Deque.new(3) { |i| (i + 1) ** 2 } # => Deque{1, 4, 9}

[View source]
def self.new(pull : JSON::PullParser, &) #

[View source]

Class Method Detail

def self.from_json(string_or_io, &) : Nil #

[View source]

Instance Method Detail

def +(other : Deque(U)) forall U #

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.


[View source]
def <<(value : T) #

Alias for #push.


[View source]
def ==(other : Deque) #

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

[View source]
def clear #

Removes all elements from self.


[View source]
def clone #

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.


[View source]
def concat(other : Indexable) : self #

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"}

[View source]
def concat(other : Enumerable(T)) : self #

[View source]
def delete(obj) : Bool #

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"}

[View source]
def delete_at(index : Int) : T #

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}

[View source]
def dup #

Returns a new Deque that has exactly this deque's elements. That is, it returns a shallow copy of this deque.


[View source]
def each(& : T -> ) : Nil #

Yields each item in this deque, from first to last.

Do not modify the deque while using this variant of #each!


[View source]
def insert(index : Int, value : T) : self #

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}

[View source]
def inspect(io : IO) : Nil #
Description copied from class Reference

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>

[View source]
def pop(n : Int) : Nil #

Removes the last n (at most) items in the deque.


[View source]
def pop : T #

Removes and returns the last item. Raises IndexError if empty.

a = Deque{1, 2, 3}
a.pop # => 3
a     # => Deque{1, 2}

[View source]
def pop(&) #

Removes and returns the last item, if not empty, otherwise executes the given block and returns its value.


[View source]
def pop? : T | Nil #

Removes and returns the last item, if not empty, otherwise nil.


[View source]
def pretty_print(pp) #

[View source]
def push(value : T) #

Adds an item to the end of the deque.

a = Deque{1, 2}
a.push 3 # => Deque{1, 2, 3}

[View source]
def reject!(& : T -> ) : self #

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.


[View source]
def reject!(pattern) : self #

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.


[View source]
def rotate!(n : Int = 1) : Nil #

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]

[View source]
def select!(& : T -> ) : self #

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.


[View source]
def select!(pattern) : self #

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.


[View source]
def shift(n : Int) : Nil #

Removes the first n (at most) items in the deque.


[View source]
def shift #

Removes and returns the first item. Raises IndexError if empty.

a = Deque{1, 2, 3}
a.shift # => 1
a       # => Deque{2, 3}

[View source]
def shift(&) #

Removes and returns the first item, if not empty, otherwise executes the given block and returns its value.


[View source]
def shift? #

Removes and returns the first item, if not empty, otherwise nil.


[View source]
def size : Int32 #

Returns the number of elements in the deque.

Deque{:foo, :bar}.size # => 2

[View source]
def to_json(json : JSON::Builder) : Nil #

[View source]
def to_s(io : IO) : Nil #
Description copied from class Reference

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>

[View source]
def unsafe_fetch(index : Int) : T #
Description copied from module Indexable(T)

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.


[View source]
def unsafe_put(index : Int, value : T) #
Description copied from module Indexable::Mutable(T)

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.


[View source]
def unshift(value : T) : self #

Adds an item to the beginning of the deque.

a = Deque{1, 2}
a.unshift 0 # => Deque{0, 1, 2}

[View source]