class Algorithmable::DataStructs::Deque

Constants

Node

Attributes

size[R]

Public Class Methods

new(collection = []) click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 11
def initialize(collection = [])
  @front = nil
  @back = nil
  @size = 0
  collection.each { |item| push_back(item) }
end

Public Instance Methods

clear() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 22
def clear
  @front = nil
  @back = nil
  @size = 0
end
each(&block) click to toggle source

represent fifo iterator

# File lib/algorithmable/data_structs/deque.rb, line 93
def each(&block)
  collect_items(:forward).each(&block)
end
empty?() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 18
def empty?
  0 == size
end
map(&block) click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 106
def map(&block)
  each.map(&block)
end
peek_back() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 32
def peek_back
  @back && @back.item
end
peek_front() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 28
def peek_front
  @front && @front.item
end
pop_back() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 78
def pop_back
  fail NoSuchElementError unless @back
  node = @back
  if @size == 1
    clear
    return node.item
  else
    @back.prev.next = nil
    @back = @back.prev
  end
  @size -= 1
  node.item
end
pop_front() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 64
def pop_front
  fail NoSuchElementError unless @front
  node = @front
  if 1 == @size
    clear
    return node.item
  else
    @front.next.prev = nil
    @front = @front.next
  end
  @size -= 1
  node.item
end
push_back(obj) click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 50
def push_back(obj)
  node = Node.new(nil, nil, obj)
  if @back
    node.prev = @back
    @back.next = node
    @back = node
  else
    @front = node
    @back = @front
  end
  @size += 1
  obj
end
push_front(obj) click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 36
def push_front(obj)
  node = Node.new(nil, nil, obj)
  if @front
    node.next = @front
    @front.prev = node
    @front = node
  else
    @front = node
    @back = @front
  end
  @size += 1
  obj
end
reverse_each(&block) click to toggle source

represent lifo iterator

# File lib/algorithmable/data_structs/deque.rb, line 98
def reverse_each(&block)
  collect_items(:backward).each(&block)
end
to_a() click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 102
def to_a
  each.to_a
end

Private Instance Methods

collect_items(order) click to toggle source
# File lib/algorithmable/data_structs/deque.rb, line 112
def collect_items(order)
  variable = order == :backward ? @back : @front
  action = order == :backward ? :prev : :next
  items = []
  if variable
    node = variable
    while node
      items << node.item
      node = node.public_send action
    end
  end
  items
end