-
Notifications
You must be signed in to change notification settings - Fork 81
Expand file tree
/
Copy pathhashtable.go
More file actions
156 lines (137 loc) · 3.04 KB
/
hashtable.go
File metadata and controls
156 lines (137 loc) · 3.04 KB
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
package hashtable
import . "github.com/timtadh/data-structures/types"
import . "github.com/timtadh/data-structures/errors"
type entry struct {
key Hashable
value interface{}
next *entry
}
type Hash struct {
table []*entry
size int
}
func abs(x int) int {
if x < 0 {
return -x
} else {
return x
}
}
func (self *entry) Put(key Hashable, value interface{}) (e *entry, appended bool) {
if self == nil {
return &entry{key, value, nil}, true
}
if self.key.Equals(key) {
self.value = value
return self, false
} else {
self.next, appended = self.next.Put(key, value)
return self, appended
}
}
func (self *entry) Get(key Hashable) (has bool, value interface{}) {
if self == nil {
return false, nil
} else if self.key.Equals(key) {
return true, self.value
} else {
return self.next.Get(key)
}
}
func (self *entry) Remove(key Hashable) *entry {
if self == nil {
panic(Errors["not-found-in-bucket"](key))
}
if self.key.Equals(key) {
return self.next
} else {
self.next = self.next.Remove(key)
return self
}
}
func NewHashTable(initial_size int) *Hash {
return &Hash{
table: make([]*entry, initial_size),
size: 0,
}
}
func (self *Hash) bucket(key Hashable) int {
return abs(key.Hash()) % len(self.table)
}
func (self *Hash) Size() int { return self.size }
func (self *Hash) Put(key Hashable, value interface{}) (err error) {
bucket := self.bucket(key)
var appended bool
self.table[bucket], appended = self.table[bucket].Put(key, value)
if appended {
self.size += 1
}
if self.size*2 > len(self.table) {
return self.expand()
}
return nil
}
func (self *Hash) expand() error {
table := self.table
self.table = make([]*entry, len(table)*2)
self.size = 0
for _, E := range table {
for e := E; e != nil; e = e.next {
if err := self.Put(e.key, e.value); err != nil {
return err
}
}
}
return nil
}
func (self *Hash) Get(key Hashable) (value interface{}, err error) {
bucket := self.bucket(key)
if has, value := self.table[bucket].Get(key); has {
return value, nil
} else {
return nil, Errors["not-found"](key)
}
}
func (self *Hash) Has(key Hashable) (has bool) {
has, _ = self.table[self.bucket(key)].Get(key)
return
}
func (self *Hash) Remove(key Hashable) (value interface{}, err error) {
bucket := self.bucket(key)
has, value := self.table[bucket].Get(key)
if !has {
return nil, Errors["not-found"](key)
}
self.table[bucket] = self.table[bucket].Remove(key)
self.size -= 1
return value, nil
}
func (self *Hash) Iterate() KVIterator {
table := self.table
i := -1
var e *entry
var kv_iterator KVIterator
kv_iterator = func() (key Hashable, val interface{}, next KVIterator) {
for e == nil {
i++
if i >= len(table) {
return nil, nil, nil
}
e = table[i]
}
key = e.key
val = e.value
e = e.next
return key, val, kv_iterator
}
return kv_iterator
}
func (self *Hash) Items() (vi KIterator) {
return MakeItemsIterator(self)
}
func (self *Hash) Keys() KIterator {
return MakeKeysIterator(self)
}
func (self *Hash) Values() Iterator {
return MakeValuesIterator(self)
}