-
Notifications
You must be signed in to change notification settings - Fork 606
/
fixedmap.h
149 lines (114 loc) · 2.16 KB
/
fixedmap.h
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
#ifndef __FIXEDMAP_H
#define __FIXEDMAP_H
/*
An STL map-like container. Quickly thrown together to replace STL maps
in specific instances. Many gotchas. Use with caution.
*/
#include <stdlib.h>
template < class T, class U >
class VVFixedMap
{
private:
struct Data {
T data;
U key;
};
Data *items;
unsigned int numItems;
unsigned int maxItems;
VVFixedMap(void) {}
public:
VVFixedMap(unsigned int maxItems)
{
items = new Data[maxItems];
numItems = 0;
this->maxItems = maxItems;
}
~VVFixedMap(void)
{
items -= ( maxItems - numItems );
delete [] items;
numItems = 0;
}
bool Insert(const T &newItem, const U &key)
{
Data *storage = NULL;
//Check for fullness.
if(numItems >= maxItems) {
assert( 0 );
return false;
}
//Check for reuse.
if(!FindUnsorted(key, storage)) {
storage = items + numItems;
numItems++;
}
storage->data = newItem;
storage->key = key;
return true;
}
void Sort(void)
{
qsort(items, numItems, sizeof(Data),
VVFixedMap< T, U >::FixedMapSorter);
}
//Binary search, items must have been sorted!
T *Find(const U &key)
{
int i;
int high;
int low;
for(low = -1, high = numItems; high - low > 1; ) {
i = (high + low) / 2;
if(key < items[i].key) {
high = i;
} else if(key > items[i].key) {
low = i;
} else {
return &items[i].data;
}
}
if(items[i+1].key == key) {
return &items[i+1].data;
} else if(items[i-1].key == key) {
return &items[i-1].data;
}
return NULL;
}
//Slower, but don't need to call sort first.
T *FindUnsorted(const U &key, Data *&storage)
{
int i;
for(i=0; i<numItems; i++) {
if(items[i].key == key) {
storage = items + i;
return &items[i].data;
}
}
return NULL;
}
// returns the top item's data
// and removes the item from the map
T *Pop(void)
{
T* top = NULL;
if(numItems)
{
top = &items[0].data;
items++;
numItems--;
}
return top;
}
static int FixedMapSorter(const void *a, const void *b)
{
if(((Data*)a)->key > ((Data*)b)->key) {
return 1;
} else if(((Data*)a)->key == ((Data*)b)->key) {
return 0;
} else {
return -1;
}
}
};
#endif