1 module bcaa;
2 pragma(LDC_no_moduleinfo);
3 
4 import core.stdc.stdlib;
5 
6 import dvector;
7 
8 struct Bcaa(K, V, size_t tableSize = 16) {
9     struct Node {
10         K key;
11         V val;
12         Node* next;
13     }
14 
15     private Node*[tableSize] htable;
16     
17     private uint hashCode(K key) @nogc nothrow {
18         static if(is(K : int)){
19             if(key<0)
20                 return -cast(uint)(key % htable.length);
21             return cast(uint)(key % htable.length);
22         } else
23         static if(is(K == string)){
24             uint hashval;
25             foreach (i, char c; key)
26                 hashval = c + 31 * hashval;
27             return hashval % htable.length;
28         } else {
29             static assert(false, "Unsupported key type!");
30         }
31     }
32 
33     void set(K key, V val) @nogc nothrow {
34         uint pos = hashCode(key);
35         Node *list = htable[pos];
36         Node *temp = list;
37 
38         while(temp){
39             if(temp.key == key){
40                 temp.val = val;
41                 return;
42             }
43             temp = temp.next;
44         }
45         Node *newNode = cast(Node*)malloc(Node.sizeof);
46         newNode.key = key;
47         newNode.val = val;
48         newNode.next = list;
49         htable[pos] = newNode;
50     }
51 
52     private Node* lookup(K key) @nogc nothrow {
53         immutable pos = hashCode(key);
54         Node* list = htable[pos];
55         Node* temp = list;
56         while(temp){
57             if(temp.key == key){
58                 return temp;
59             }
60             temp = temp.next;
61         }
62         return null;
63     }
64 
65     V get(K key) @nogc nothrow {
66         const node = lookup(key);
67         if(node !is null)
68             return node.val;
69         return V.init;
70     }
71 
72     V opIndex(K key) @nogc nothrow {
73         return get(key);
74     }
75 
76     void opIndexAssign(V value, K key) @nogc nothrow {
77         set(key, value);
78     }
79 
80     /// returning vector has to be cleaned-up with member free method of Dvector.
81     Dvector!K keys() @nogc nothrow {
82         Dvector!K ks;
83 
84         foreach(i; 0..tableSize){
85             auto node = htable[i];
86             if(node is null)
87                 continue;
88             Node* tmp = node;
89             while(tmp){
90                 ks.pushBack(tmp.key);
91                 tmp = tmp.next;
92             }
93         }
94 
95         return ks;
96     }
97 
98     /// returning vector has to be cleaned-up with member free method of Dvector.
99     Dvector!V values() @nogc nothrow {
100         Dvector!V vals;
101 
102         foreach(i; 0..tableSize){
103             auto node = htable[i];
104             if(node is null)
105                 continue;
106             Node* tmp = node;
107             while(tmp){
108                 vals.pushBack(tmp.val);
109                 tmp = tmp.next;
110             }
111         }
112 
113         return vals;
114     }
115     
116     // uses iteration
117     bool remove(K key) @nogc nothrow {
118         foreach(i; 0..tableSize){
119             Node* current, previous;
120             previous = null;
121             for (current = htable[i];
122                 current != null;
123                 previous = current,
124                 current = current.next) {
125 
126                 if (current.key == key) {
127                     if (previous == null) {
128                         htable[i] = current.next;
129                     } else {
130                         previous.next = current.next;
131                     }
132                     core.stdc.stdlib.free(current);
133                     current = null;
134                     return true;
135                 }
136             }
137         }
138         return false;
139     }
140 
141     // uses recursion
142     bool remove2(K key) @nogc nothrow {
143 
144         Node *recursiveDelete(Node *current, K key, bool* removed) @nogc nothrow {
145             if (current == null)
146                 return null;
147             if (current.key == key) {
148                 Node *tmpNext = current.next;
149                 core.stdc.stdlib.free(current);
150                 *removed = true;
151                 return tmpNext;
152             }
153             current.next = recursiveDelete(current.next, key, removed);
154             return current;
155         }
156 
157         bool removed = false;
158 
159         foreach(i; 0..tableSize){
160             htable[i] = recursiveDelete(htable[i], key, &removed);
161             if(removed)
162                 return true;
163         }
164         return false;
165     }
166 
167     void free() @nogc nothrow {
168         auto _keys = keys();
169         foreach (key; _keys)
170             core.stdc.stdlib.free(lookup(key));
171         _keys.free;
172     }
173 }
174 
175 unittest {
176     import core.stdc.stdio;
177 
178     Bcaa!(string, string) aa;
179 
180     aa["Stevie"] = "Ray Vaughan";
181     aa["Asım Can"] = "Gündüz";
182     aa["Dan"] = "Patlansky";
183     aa["İlter"] = "Kurcala";
184     aa["Ferhat"] = "Kurtulmuş";
185     
186     assert(aa.remove("Ferhat") == true);
187     assert(aa["Ferhat"] == null);
188     assert(aa.remove("Foe") == false);
189     assert(aa["İlter"] =="Kurcala");
190 
191     printf("%s\n",aa["Stevie"].ptr);
192     printf("%s\n",aa["Asım Can"].ptr);
193     printf("%s\n",aa["Dan"].ptr);
194 
195     auto _keys = aa.keys;
196     foreach(key; _keys)
197         printf("%s -> %s \n", key.ptr, aa[key].ptr);
198     _keys.free;
199     
200     aa.free;
201 
202     struct Guitar {
203         string brand;
204     }
205 
206     Bcaa!(int, Guitar) guitars;
207 
208     guitars[0] = Guitar("Fender");
209     guitars[3] = Guitar("Gibson");
210     guitars[356] = Guitar("Stagg");
211 
212     assert(guitars[3].brand == "Gibson");
213 
214     printf("%s \n", guitars[356].brand.ptr);
215 
216     guitars.free;
217 }