View difference between Paste ID: fpybLi3J and hzPR7LkN
SHOW: | | - or go back to the newest paste.
1
require './doubly_linked_list'
2
require 'pry'
3
4
class HashTable < Array
5-
  attr_reader :hash_funcion
5+
  attr_reader :hash_function
6
7
  ListElement = Struct.new(:key, :value)
8
9
  class KeyedDoublyLinkedList < DoublyLinkedList
10
    def initialize(elem)
11
      super
12
    end
13
14
    def search(k, node = @head)
15
      if node.nil?
16
        nil
17
      elsif node.elem.key == k
18
        node.elem
19
      else
20
        self.search(k, node.right)
21
      end
22
    end
23
  end
24
25
  def initialize(size = 100, default = nil)
26
    super
27
    @hash_function = Proc.new {|m, k| k % m}
28
  end
29
30
  def add(k, v)
31
    i = get_slot(k)
32
    if self[i].nil?
33
        self[i] = KeyedDoublyLinkedList.new( ListElement.new(k, v) )
34
    else
35
      if self[i].search(k).nil?
36
        self[i].push( ListElement.new(k, v) )
37
      else
38
        self[i].search(k).value = v
39
      end
40
    end
41
  end
42
43
  ## This is how I would like to call "add" but its not working
44
  ## Self doesn't update when I reassign the local variable
45
  # def add(k, v)
46
  #   list = self[get_slot(k)]
47
  #   if list.nil?
48
  #       list = KeyedDoublyLinkedList.new( ListElement.new(k, v) )
49
  #   else
50
  #     node = list.search(k)
51
  #     if node.nil?
52
  #       node.push( ListElement.new(k, v) )
53
  #     else
54
  #       node.value = v
55
  #     end
56
  #   end
57
  # end
58
59
  def contains_key(k)
60
    i = get_slot(k)
61
    if self[i].nil?
62
      false
63
    else
64
      if self[i].search(k) then true else false end
65
    end
66
  end
67
68
  def to_s
69
    self.select {|p| !p.nil? }.each do |slot|
70
      slot.to_s
71
    end
72
  end
73
74
  private
75
    def get_slot(k)
76
      @hash_function.call(self.length, k)
77
    end
78
end
79
80
81
table = HashTable.new(100)
82
(1..5).each do |i|
83
  table.add(i, "test")
84
end
85
86
table.add(1, "updated")
87
88
puts table.to_s
89
binding.pry