class RubyCollections::Deque
Public Class Methods
new()
click to toggle source
TODO: implement iterator TODO: implement to_a
# File lib/ruby_collections/deque.rb, line 8 def initialize @hash = {size: 0, front: {data: nil, next: :rear, prev: nil}, rear: {data: nil, next: nil, prev: :front}} end
Public Instance Methods
add(data, index = 0)
click to toggle source
# File lib/ruby_collections/deque.rb, line 29 def add(data, index = 0) return nil if index > size if index == 0 then add_first(data) and return end setNext(getNode(index-1), data) if index > 0 and index < size hash[:size] += 1 end
add_first(data)
click to toggle source
# File lib/ruby_collections/deque.rb, line 36 def add_first(data) setNext(:front, data) hash[:size] += 1 end
add_last(data)
click to toggle source
# File lib/ruby_collections/deque.rb, line 41 def add_last(data) setPrev(:rear, data) hash[:size] += 1 end
empty?()
click to toggle source
# File lib/ruby_collections/deque.rb, line 13 def empty? size.zero? end
get(index)
click to toggle source
# File lib/ruby_collections/deque.rb, line 46 def get(index) return nil if index >= size hash[getNode(index)][:data] end
head()
click to toggle source
# File lib/ruby_collections/deque.rb, line 21 def head hash[front[:next]][:data] end
remove(index)
click to toggle source
# File lib/ruby_collections/deque.rb, line 56 def remove(index) return nil if index >= size or index < 0 node_id = getNode(index) hash[getNext(node_id)][:prev] = getPrev(node_id) hash[getPrev(node_id)][:next] = getNext(node_id) hash.delete(node_id) hash[:size] -= 1 end
remove_first()
click to toggle source
# File lib/ruby_collections/deque.rb, line 65 def remove_first return nil if empty? remove(0) end
remove_last()
click to toggle source
# File lib/ruby_collections/deque.rb, line 70 def remove_last return nil if empty? node_id = getPrev(:rear) prev_id = getPrev(node_id) hash[prev_id][:next] = :rear rear[:prev] = prev_id hash.delete(node_id) hash[:size] -= 1 end
set(index, data)
click to toggle source
# File lib/ruby_collections/deque.rb, line 51 def set(index, data) return nil if index >= size hash[getNode(index)][:data] = data end
size()
click to toggle source
# File lib/ruby_collections/deque.rb, line 17 def size hash[:size] end
tail()
click to toggle source
# File lib/ruby_collections/deque.rb, line 25 def tail hash[rear[:prev]][:data] end
to_s()
click to toggle source
# File lib/ruby_collections/deque.rb, line 80 def to_s return "" if empty? data = [] node_id = :front size.times do node_id = getNext(node_id) data << hash[node_id][:data] end return data.to_s end
Private Instance Methods
front()
click to toggle source
# File lib/ruby_collections/deque.rb, line 97 def front hash[:front] end
getNext(node_id)
click to toggle source
# File lib/ruby_collections/deque.rb, line 119 def getNext(node_id) hash[node_id][:next] end
getNode(index)
click to toggle source
# File lib/ruby_collections/deque.rb, line 127 def getNode(index) node = front[:next] index.times {node = getNext(node)} return node end
getPrev(node_id)
click to toggle source
# File lib/ruby_collections/deque.rb, line 123 def getPrev(node_id) hash[node_id][:prev] end
hash()
click to toggle source
# File lib/ruby_collections/deque.rb, line 93 def hash @hash end
rear()
click to toggle source
# File lib/ruby_collections/deque.rb, line 101 def rear hash[:rear] end
setNext(node_id, data)
click to toggle source
# File lib/ruby_collections/deque.rb, line 105 def setNext(node_id, data) uuid = SecureRandom.uuid hash[uuid] = {data: data, next: getNext(node_id), prev: node_id} hash[getNext(node_id)][:prev] = uuid hash[node_id][:next] = uuid end
setPrev(node_id, data)
click to toggle source
# File lib/ruby_collections/deque.rb, line 112 def setPrev(node_id, data) uuid = SecureRandom.uuid hash[uuid] = {data: data, next: node_id, prev: getPrev(node_id)} hash[getPrev(node_id)][:next] = uuid hash[node_id][:prev] = uuid end