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

Class Method Summary

Instance Method Summary

Instance methods inherited from module Comparable(T)

<(other : T) <, <=(other : T) <=, <=>(other : T) <=>, ==(other : T) ==, >(other : T) >, >=(other : T) >=

Instance methods inherited from module Iterable

cycle
cycle(n) cycle, each each, each_cons(count : Int) each_cons, each_slice(count : Int) each_slice, each_with_index(offset = 0) each_with_index, each_with_object(obj) each_with_object

Instance methods inherited from module Enumerable(T)

all?
all?(&block) all?, any?
any?(&block) any?, compact_map(&block) compact_map, count(item)
count(&block) count, cycle(&block)
cycle(n, &block) cycle, each(&block : T -> _) each, each_cons(count : Int, &block) each_cons, each_slice(count : Int, &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
first(count : Int) first, first? first?, flat_map(&block : T -> Array(U)) flat_map, grep(pattern) grep, group_by(&block : T -> U) group_by, in_groups_of(size : Int, filled_up_with : U = nil, &block)
in_groups_of(size : Int, filled_up_with : U = nil) in_groups_of, includes?(obj) includes?, index(obj)
index(&block) index, index_by(&block : T -> U) index_by, join(separator = "")
join(separator, io, &block)
join(separator = "", &block)
join(separator, io) join, map(&block : T -> U) map, map_with_index(&block : T, Int32 -> U) map_with_index, max max, max? max?, max_by(&block : T -> U) max_by, max_by?(&block : T -> U) max_by?, max_of(&block : T -> U) max_of, max_of?(&block : T -> U) max_of?, min min, min? min?, min_by(&block : T -> U) min_by, min_by?(&block : T -> U) min_by?, min_of(&block : T -> U) min_of, min_of?(&block : T -> U) min_of?, minmax minmax, minmax? minmax?, minmax_by(&block : T -> U) minmax_by, minmax_by?(&block : T -> U) minmax_by?, minmax_of(&block : T -> U) minmax_of, minmax_of?(&block : T -> U) minmax_of?, none?(&block)
none? none?, one?(&block) one?, partition(&block) partition, product(initial : Number, &block)
product
product(initial : Number)
product(&block) product, reduce(memo, &block)
reduce(&block) reduce, reject(&block : T -> ) reject, select(&block : T -> ) select, size size, skip(count : Int) skip, skip_while(&block) skip_while, sum
sum(initial)
sum(&block)
sum(initial, &block) sum, take_while(&block) take_while, to_a to_a, to_h to_h, to_set to_set

Instance methods inherited from class Reference

==(other)
==(other : self) ==, hash hash, inspect(io : IO) : Nil inspect, object_id : UInt64 object_id, same?(other : Reference)
same?(other : Nil) same?, to_s(io : IO) : Nil to_s

Instance methods inherited from class Object

!=(other) !=, !~(other) !~, ==(other) ==, ===(other)
===(other : YAML::Any)
===(other : JSON::Any) ===, =~(other) =~, class class, clone clone, crystal_type_id crystal_type_id, dup dup, hash hash, inspect
inspect(io : IO) inspect, itself itself, not_nil! not_nil!, tap(&block) tap, to_json to_json, to_pretty_json(io : IO)
to_pretty_json to_pretty_json, to_s
to_s(io : IO) to_s, to_yaml(io : IO)
to_yaml to_yaml, try(&block) try

Class methods inherited from class Object

==(other : Class) ==, ===(other) ===, cast(other) : self cast, from_json(string_or_io) : self from_json, from_yaml(string : String) : self from_yaml, hash hash, inspect(io) inspect, name : String name, to_s(io) to_s, |(other : U.class) |

Class Method Detail

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(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(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 #

Creates a new empty Deque


[View source]
def self.new(size : Int, &block : 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]

Instance Method Detail

def +(other : Deque(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) #

Equality. 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 [](index : Int) #

Returns the element at the given index.

Negative indices can be used to start counting from the end of the deque. Raises IndexError if trying to access an element outside the deque's range.


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

Sets the given value at the given index.

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


[View source]
def []?(index : Int) #

Returns the element at the given index.

Negative indices can be used to start counting from the end of the deque. Returns nil if trying to access an element outside the deque's range.


[View source]
def at(index : Int, &block) #

Returns the element at the given index, if in bounds, otherwise executes the given block and returns its value.


[View source]
def at(index : Int) #

Returns the element at the given index, if in bounds, otherwise raises IndexError.


[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 : Enumerable(T)) #

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


[View source]
def delete(obj) #

Removes all items from self that are equal to obj.

a = Deque{"a", "b", "b", "b", "c"}
a.delete("b")
a # => Deque{"a", "c"}

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

Delete 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) # => 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 #

Gives an iterator over each item in this deque, from first to last.


[View source]
def each(&block) #

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

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


[View source]
def each_index #

Gives an iterator over the indices of each item in this deque, from first (0) to last (size - 1).


[View source]
def each_index(&block) #

Yields indices of each item in this deque, from first (0) to last (size - 1).


[View source]
def empty? #

Returns true if this deque has 0 items.


[View source]
def equals?(other : Deque, &block) #

Zips two deques and gives each pair to the passed block. Returns true if the block returns true every time.


[View source]
def first(&block) #

Returns the leftmost item in the deque (index 0), if not empty, otherwise executes the given block and returns its value.


[View source]
def first #

Returns the leftmost item in the deque (index 0). Raises IndexError if empty.


[View source]
def first? #

Returns the leftmost item in the deque (index 0), if not empty, otherwise nil.


[View source]
def hash #

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

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_at(1, 7) # => Deque{0, 7, 1, 2}

[View source]
def inspect(io : IO) #

[View source]
def last(&block) #

Returns the rightmost item in the deque (index size - 1), if not empty, otherwise executes the given block and returns its value.


[View source]
def last #

Returns the rightmost item in the deque (index size - 1). Raises IndexError if empty.


[View source]
def last? #

Returns the rightmost item in the deque (index size - 1), if not empty, otherwise nil.


[View source]
def pop #

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(&block) #

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


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

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


[View source]
def pop? #

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


[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 reverse_each(&block) #

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

Do not modify the deque while using #reverse_each!


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

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) }.


[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(&block) #

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


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

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


[View source]
def shift? #

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


[View source]
def size #

Returns the number of elements in the deque.

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

[View source]
def swap(i, j) #

Swaps the items at the indices i and j.


[View source]
def to_a #

Returns an Array (shallow copy) that contains all the items of this deque.


[View source]
def to_s(io : IO) #

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

Adds an item to the beginning of the deque.

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

[View source]