-
Notifications
You must be signed in to change notification settings - Fork 2
/
dict.rb
77 lines (65 loc) · 1.59 KB
/
dict.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
module Dict
def Dict.new(num_buckets=256)
# Initializes a Dict with the given number of buckets.
aDict = []
(0...num_buckets).each do |i|
aDict.push([])
end
return aDict
end
def Dict.hash_key(aDict, key)
# Given a key this will create a number and then convert it to
# an index for the aDict's buckets.
return key.hash % aDict.length
end
def Dict.get_bucket(aDict, key)
# Given a key, find the bucket where it would go.
bucket_id = Dict.hash_key(aDict, key)
return aDict[bucket_id]
end
def Dict.get_slot(aDict, key, default=nil)
# Returns the index, key, and value of a slot found in a bucket.
bucket = Dict.get_bucket(aDict, key)
bucket.each_with_index do |kv, i|
k, v = kv
if key == k
return i, k, v
end
end
return -1, key, default
end
def Dict.get(aDict, key, default=nil)
# Gets the value in a bucket for the given key, or the default.
i, k, v = Dict.get_slot(aDict, key, default=default)
return v
end
def Dict.set(aDict, key, value)
# Sets the key to the value, replacing any existing value.
bucket = Dict.get_bucket(aDict, key)
i, k, v = Dict.get_slot(aDict, key)
if i >= 0
bucket[i] = [key, value]
else
bucket.push([key, value])
end
end
def Dict.delete(aDict, key)
# Deletes the given key from the Dict.
bucket = Dict.get_bucket(aDict, key)
(0...bucket.length).each do |i|
k, v = bucket[i]
if key == k
bucket.delete_at(1)
break
end
end
end
def Dict.list(aDict)
# print out what's in the Dict.
aDict.each do |bucket|
if bucket
bucket.each {|k, v| print k, "\s", v, "\n"}
end
end
end
end