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 |