blob: 24099856688d920bf7b1f776bc922215e6ee4426 (
about) (
plain)
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
|
#ifndef ASSOC_HH
#define ASSOC_HH
#include "vray.hh"
#include <assert.h>
template<class K,class V>
struct Assoc_ent_ {
bool free;
K key;
V val;
};
template<class K, class V>
struct Assoc {
svec< Assoc_ent_<K,V> > arr;
/****************/
int find(K key) const {
for (int i = 0; i < arr.sz(); i++) {
if (!arr[i].free && key == arr[i].key)
return i;
}
return -1;
}
int find_creat(K key) {
int free = -1;
for (int i = 0; i < arr.sz(); i++) {
if (key == arr[i].key) {
return i;
} else if (arr[i].free ) {
free = i;
}
}
if (free >= 0){
arr[free].free = false;
arr[free].key = key;
return free;
}
Assoc_ent_<K,V> ae;
ae.free = false;
ae.key = key;
arr.add(ae);
return arr.sz() -1;
}
public:
bool elt_query(K key) const {
return find(key) >= 0;
}
void del(K key) {
assert(elt_query(key));
int i= find(key);
arr[i].free = true;
}
void
add(K key, V val) {
int i = find_creat(key);
arr[i].val = val;
}
/**
should create "set" template
*/
V& operator[](K key) {
return arr[find_creat(key)].val;
}
const V& operator[](K key) const {
assert(elt_query(key));
return arr[find(key)].val;
}
};
/** mindblowingly stupid Associative array implementation
*/
#endif
|
