W3cubDocs

/Crystal 0.31

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

Constructors

Instance Method Summary

Instance methods inherited from module Indexable(T)

[](index : Int) [], []?(index : Int) []?, bsearch(&block : T -> Bool) bsearch, bsearch_index(&block : T, Int32 -> Bool) bsearch_index, dig(index : Int, *subindexes) dig, dig?(index : Int, *subindexes) dig?, each(*, start : Int, count : Int, &block)
each(*, within range : Range, &block)
each(&block)
each each
, each_index(*, start : Int, count : Int, &block)
each_index(&block) : Nil
each_index each_index
, empty? empty?, equals?(other : Indexable, &block)
equals?(other, &block) equals?
, fetch(index, default)
fetch(index : Int, &block) fetch
, first
first(&block) first
, first? first?, hash(hasher) hash, index(object, offset : Int = 0)
index(offset : Int = 0, &block) index
, join(separator = "") join, last
last(&block) last
, last? last?, reverse_each(&block) : Nil
reverse_each reverse_each
, rindex(offset = size - 1, &block)
rindex(value, offset = size - 1) rindex
, sample(random = Random::DEFAULT) sample, size size, to_a to_a, unsafe_fetch(index : Int) unsafe_fetch, values_at(*indexes : Int) values_at

Instance methods inherited from module Enumerable(T)

all?(&block)
all?(pattern)
all? all?
, any?(&block)
any?(pattern)
any? any?
, chunks(&block : T -> U) forall U chunks, compact_map(&block) compact_map, count(item)
count(&block) count
, cycle(&block)
cycle(n, &block) cycle
, each(&block : T -> UNDERSCORE) each, each_cons(count : Int, reuse = false, &block) each_cons, each_slice(count : Int, reuse = false, &block) each_slice, each_with_index(offset = 0, &block) each_with_index, each_with_object(obj, &block) each_with_object, find(if_none = nil, &block) find, first(count : Int)
first first
, first? first?, flat_map(&block : T -> Array(U) | Iterator(U) | U) forall U flat_map, grep(pattern) grep, group_by(&block : 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, &block) forall U in_groups_of
, includes?(obj) includes?, index(&block)
index(obj) index
, index_by(&block : T -> U) forall U index_by, join(separator = "", &block)
join(separator, io, &block)
join(separator, io)
join(separator = "") join
, map(&block : T -> U) forall U map, map_with_index(&block : T, Int32 -> U) forall U map_with_index, max max, max? max?, max_by(&block : T -> U) forall U max_by, max_by?(&block : T -> U) forall U max_by?, max_of(&block : T -> U) forall U max_of, max_of?(&block : T -> U) forall U max_of?, min min, min? min?, min_by(&block : T -> U) forall U min_by, min_by?(&block : T -> U) forall U min_by?, min_of(&block : T -> U) forall U min_of, min_of?(&block : T -> U) forall U min_of?, minmax minmax, minmax? minmax?, minmax_by(&block : T -> U) forall U minmax_by, minmax_by?(&block : T -> U) forall U minmax_by?, minmax_of(&block : T -> U) forall U minmax_of, minmax_of?(&block : T -> U) forall U minmax_of?, none?
none?(pattern)
none?(&block) none?
, one?(&block)
one?(pattern)
one? one?
, partition(&block) partition, product(&block)
product(initial : Number, &block)
product
product(initial : Number) product
, reduce(memo, &block)
reduce(&block) reduce
, reduce?(&block) reduce?, reject(&block : T -> )
reject(type : U.class) forall U
reject(pattern) reject
, select(pattern)
select(type : U.class) forall U
select(&block : T -> ) select
, size size, skip(count : Int) skip, skip_while(&block) skip_while, sum(initial)
sum
sum(initial, &block)
sum(&block) sum
, take_while(&block) take_while, tally : Hash(T, Int32) tally, to_a to_a, to_h
to_h(&block : T -> Tuple(K, V)) forall K, V to_h
, to_set to_set, zip(*others : Indexable | Iterable | Iterator, &block)
zip(*others : Indexable | Iterable | Iterator) zip
, zip?(*others : Indexable | Iterable | Iterator, &block)
zip?(*others : Indexable | Iterable | Iterator) zip?

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_slice(count : Int, reuse = false) each_slice, 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, inspect(io : IO) : Nil inspect, object_id : UInt64 object_id, pretty_print(pp) : Nil pretty_print, same?(other : Reference)
same?(other : Nil) same?
, to_s(io : IO) : Nil to_s

Constructor methods inherited from class Reference

new new

Instance methods inherited from class Object

!=(other) !=, !~(other) !~, ==(other) ==, ===(other : JSON::Any)
===(other : YAML::Any)
===(other) ===
, =~(other) =~, class class, dup dup, hash(hasher)
hash hash
, inspect(io : IO) : Nil
inspect : String inspect
, itself itself, not_nil! not_nil!, pretty_inspect(width = 79, newline = "\n", indent = 0) : String pretty_inspect, pretty_print(pp : PrettyPrint) : Nil pretty_print, tap(&block) tap, to_json(io : IO)
to_json to_json
, to_pretty_json(indent : String = " ")
to_pretty_json(io : IO, indent : String = " ") to_pretty_json
, to_s : String
to_s(io : IO) : Nil to_s
, to_yaml(io : IO)
to_yaml to_yaml
, try(&block) try, unsafe_as(type : T.class) forall T unsafe_as

Constructor methods inherited from class Object

from_json(string_or_io, root : String) : self
from_json(string_or_io) : self from_json
, from_yaml(string_or_io : String | IO) : self from_yaml

Constructor Detail

def self.new(size : Int, value : T)Source

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

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

def self.new(array : Array(T))Source

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

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

def self.new(initial_capacity : Int)Source

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

def self.newSource

Creates a new empty Deque

def self.new(size : Int, &block : Int32 -> T)Source

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}

Instance Method Detail

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

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.

def <<(value : T)Source

Alias for #push.

def ==(other : Deque)Source

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

def []=(index : Int, value : T)Source

Sets the given value at the given index.

Raises IndexError if the deque had no previous value at the given index.

def clearSource

Removes all elements from self.

def cloneSource

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.

def concat(other : Enumerable(T))Source

Appends the elements of other to self, and returns self.

def delete(obj)Source

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

def delete_at(index : Int)Source

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}

def delete_if(&block)Source

def dupSource

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

def each(&block) : NilSource

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

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

def insert(index : Int, value : T)Source

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}

def inspect(io : IO) : NilSource

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>

def pop(&block)Source

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

def popSource

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

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

def pop(n : Int)Source

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

def pop?Source

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

def pretty_print(pp)Source

def push(value : T)Source

Adds an item to the end of the deque.

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

def rotate!(n : Int = 1)Source

Rotates this deque in place so that the element at n becomes first.

  • For positive n, equivalent to n.times { push(shift) }.
  • For negative n, equivalent to (-n).times { unshift(pop) }.

def shift(n : Int)Source

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

def shiftSource

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

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

def shift(&block)Source

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

def shift?Source

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

def sizeSource

Returns the number of elements in the deque.

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

def swap(i, j)Source

Swaps the items at the indices i and j.

def to_s(io : IO) : NilSource

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>

def unsafe_fetch(index : Int)Source

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.

def unshift(value : T)Source

Adds an item to the beginning of the deque.

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

© 2012–2019 Manas Technology Solutions.
Licensed under the Apache License, Version 2.0.
https://crystal-lang.org/api/0.31.1/Deque.html