-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
hash-table.spice
149 lines (136 loc) · 3.95 KB
/
hash-table.spice
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
import "std/data/vector";
import "std/data/linked-list";
import "std/type/result";
import "std/type/error";
import "std/math/hash";
// Generic types for key and value
type K dyn;
type V dyn;
type HashEntry<K, V> struct {
K key
V value
}
public type HashTable<K, V> struct {
Vector<LinkedList<HashEntry<K, V>>> buckets
}
public p HashTable.ctor(unsigned long bucketCount = 100l) {
this.buckets = Vector<LinkedList<HashEntry<K, V>>>(bucketCount);
for unsigned long i = 0l; i < bucketCount; i++ {
this.buckets.pushBack(LinkedList<HashEntry<K, V>>());
}
}
/**
* Insert a key-value pair into the hash table.
* If the key already exists, the value is updated.
*
* @param key The key to insert
* @param value The value to insert
*/
public p HashTable.upsert(const K& key, const V& value) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& bucket = this.buckets.get(index);
foreach const HashEntry<K, V>& entry : bucket {
if (entry.key == key) {
entry.value = value;
return;
}
}
bucket.pushBack(HashEntry<K, V>{key, value});
}
/**
* Retrieve the value associated with the given key.
* If the key is not found, panic.
*
* @param key The key to look up
* @return The value associated with the key
*/
public f<V&> HashTable.get(const K& key) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& bucket = this.buckets.get(index);
foreach const HashEntry<K, V>& entry : bucket {
if (entry.key == key) {
return entry.value;
}
}
panic(Error("The provided key was not found"));
}
/**
* Retrieve the value associated with the given key as Optional<T>.
* If the key is not found, return an empty optional.
*
* @param key The key to look up
* @return Optional<T>, containing the value associated with the key or empty if the key is not found
*/
public f<Result<V>> HashTable.getSafe(const K& key) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& bucket = this.buckets.get(index);
foreach const HashEntry<K, V>& entry : bucket {
if (entry.key == key) {
return ok(entry.value);
}
}
return err<V>(Error("The provided key was not found"));
}
/**
* Remove the key-value pair associated with the given key.
* If the key is not found, do nothing.
*
* @param key The key to remove
*/
public p HashTable.remove(const K& key) {
const unsigned long index = this.hash(key);
LinkedList<HashEntry<K, V>>& bucket = this.buckets.get(index);
for unsigned long i = 0l; i < bucket.getSize(); i++ {
if (bucket.get(i).key == key) {
bucket.removeAt(i);
return;
}
}
}
/**
* Check if the hash table contains the given key.
*
* @param key The key to check for
* @return True if the key is found, false otherwise
*/
public f<bool> HashTable.contains(const K& key) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& bucket = this.buckets.get(index);
foreach const HashEntry<K, V>& entry : bucket {
if (entry.key == key) {
return true;
}
}
return false;
}
/**
* Get the size of the hash table.
*
* @return The number of key-value pairs in the hash table
*/
public inline f<unsigned long> HashTable.getSize() {
result = 0l;
foreach LinkedList<HashEntry<K, V>>& bucket : this.buckets {
result += bucket.getSize();
}
}
/**
* Checks if the hash table is empty.
*
* @return True if empty, false otherwise.
*/
public inline f<bool> HashTable.isEmpty() {
return this.getSize() == 0l;
}
/**
* Clear the hash table, removing all key-value pairs.
*/
public inline p HashTable.clear() {
foreach LinkedList<HashEntry<K, V>>& bucket : this.buckets {
bucket.clear();
}
}
inline f<unsigned long> HashTable.hash(const K& key) {
const K keyCopy = key;
return hash(keyCopy) % this.buckets.getSize();
}