class Containers::RubyDeque
rdoc
A Deque is a container that allows items to be added and removed from both the front and back, acting as a combination of a Stack and Queue. This implementation uses a doubly-linked list, guaranteeing O(1) complexity for all operations. MIT License Copyright (c) 2009 Kanwei Li Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Constants
- Node
Public Class Methods
new(ary=[])
click to toggle source
Create a new Deque. Takes an optional array argument to initialize the Deque.
d = Containers::Deque.new([1, 2, 3]) d.front #=> 1 d.back #=> 3
# File lib/containers/deque.rb, line 39 def initialize(ary=[]) @front = nil @back = nil @size = 0 ary.to_a.each { |obj| push_back(obj) } end
Public Instance Methods
back()
click to toggle source
Returns the object at the back of the Deque but does not remove it.
d = Containers::Deque.new d.push_front(1) d.push_front(2) d.back #=> 1
# File lib/containers/deque.rb, line 82 def back @back && @back.obj end
clear()
click to toggle source
Removes all the objects in the Deque.
# File lib/containers/deque.rb, line 52 def clear @front = @back = nil @size = 0 end
each_backward() { |obj| ... }
click to toggle source
Iterate over the Deque in LIFO order.
# File lib/containers/deque.rb, line 176 def each_backward return unless @back node = @back while node yield node.obj node = node.left end end
Also aliased as: reverse_each
each_forward() { |obj| ... }
click to toggle source
Iterate over the Deque in FIFO order.
# File lib/containers/deque.rb, line 165 def each_forward return unless @front node = @front while node yield node.obj node = node.right end end
Also aliased as: each
empty?()
click to toggle source
Returns true if the Deque is empty, false otherwise.
# File lib/containers/deque.rb, line 47 def empty? @size == 0 end
front()
click to toggle source
Returns the object at the front of the Deque but does not remove it.
d = Containers::Deque.new d.push_front(1) d.push_front(2) d.front #=> 2
# File lib/containers/deque.rb, line 72 def front @front && @front.obj end
pop_back()
click to toggle source
Returns the object at the back of the Deque and removes it.
d = Containers::Deque.new d.push_front(1) d.push_front(2) d.pop_back #=> 1 d.size #=> 1
# File lib/containers/deque.rb, line 150 def pop_back return nil unless @back node = @back if @size == 1 clear return node.obj else @back.left.right = nil @back = @back.left end @size -= 1 node.obj end
pop_front()
click to toggle source
Returns the object at the front of the Deque and removes it.
d = Containers::Deque.new d.push_front(1) d.push_front(2) d.pop_front #=> 2 d.size #=> 1
# File lib/containers/deque.rb, line 129 def pop_front return nil unless @front node = @front if @size == 1 clear return node.obj else @front.right.left = nil @front = @front.right end @size -= 1 node.obj end
push_back(obj)
click to toggle source
Adds an object at the back of the Deque.
d = Containers::Deque.new([1, 2, 3]) d.push_back(4) d.pop_back #=> 4
# File lib/containers/deque.rb, line 109 def push_back(obj) node = Node.new(nil, nil, obj) if @back node.left = @back @back.right = node @back = node else @front = @back = node end @size += 1 obj end
push_front(obj)
click to toggle source
Adds an object at the front of the Deque.
d = Containers::Deque.new([1, 2, 3]) d.push_front(0) d.pop_front #=> 0
# File lib/containers/deque.rb, line 91 def push_front(obj) node = Node.new(nil, nil, obj) if @front node.right = @front @front.left = node @front = node else @front = @back = node end @size += 1 obj end
size()
click to toggle source
Return the number of items in the Deque.
d = Containers::Deque.new([1, 2, 3]) d.size #=> 3
# File lib/containers/deque.rb, line 61 def size @size end
Also aliased as: length