-
Notifications
You must be signed in to change notification settings - Fork 4
/
collection.h
232 lines (192 loc) · 5.4 KB
/
collection.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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
/* ----------------------------------------------------------------------------
This library contains a number of collection classes:
* they all store (void*) that point to objects
* user of these classes needs to provide data types compatible to void*, or
type cast them (e.g. (void*)a)
---------------------------------------------------------------------------- */
#ifndef COLLECTION_DEFINED
#define COLLECTION_DEFINED
#define INITSIZE 1000000 // default collection size
#define EXTENSION 1000000 // default extension size if the collection object overflows
namespace Collection
{
class Array;
class Stack;
class Queue;
class Hash;
class HashReader;
class Set;
class BinHeap;
class Array
{
// data members
protected:
void** m_p; // pointer to an array of void*
int m_lim; // the array size (max No. of items)
int m_max; // the max current usage of array space
int m_ext; // the extension space if the array is overflow;
public:
Array(const int a_max = INITSIZE, const int a_ext = EXTENSION);
Array(const Array& a_v);
virtual ~Array();
// update
virtual int append(void* a_p);
virtual int remove(void* a_p);
virtual int removeAt(int i);
virtual int replaceAt(const int a_i, void* a_p);
virtual int clean();
virtual int partialsort(const int a_start, const int a_end, int(*a_compare)(const void* a_p0, const void* a_p1) = 0);
virtual int sort(int(*a_compare)(const void* a_p0, const void* a_p1) = 0);
virtual int reverse();
virtual int trim(const int _k);
virtual int copy(const Array& a_array);
virtual void removeDuplicate(int(*a_compare)(const void* a_p0, const void* a_p1) = 0);
// search
virtual int size() const;
virtual void* get(const int a_i) const;
virtual void* operator[](const int a_i) const;
virtual int find(void* a_p, int(*a_compare)(const void* a_p0, const void* a_p1) = 0) const;
virtual int binSearch(void*a_p, int(*a_compare)(const void* a_p0, const void* a_p1) = 0) const; // this assumes the array is sorted!!!
virtual bool operator==(const Array& a_array) const;
};
class Stack :protected Array
{
public:
//constructor / destructor
Stack(const int a_max = INITSIZE, const int a_ext = EXTENSION);
Stack(const Stack& a_s);
virtual ~Stack();
// update
virtual int push(void* a_p);
virtual void* pop();
// search
virtual int height() const;
virtual void* top() const;
virtual bool isEmpty() const;
virtual int size() const;
};
class Queue : protected Array
{
protected:
int m_head; // head position
public:
Queue(const int a_max = INITSIZE, const int a_ext = EXTENSION);
Queue(const Queue& a_q);
virtual ~Queue();
// update
virtual int enqueue(void* a_p);
virtual void* dequeue();
// search
virtual int length() const;
virtual void* head() const;
virtual bool isEmpty() const;
virtual void* operator[](const int a_i) const; // added by tangloner for efficient queue traverse
};
class Hash
{
friend class HahReader;
public:
class HashEntry
{
public:
const int m_key;
void* m_p;
public:
HashEntry(const int a_key, void* a_p) :m_key(a_key), m_p(a_p){};
virtual ~HashEntry(){};
static int comparekey(const void* a_p0, const void* a_p1)
{
HashEntry* p0 = *(HashEntry**)a_p0;
HashEntry* p1 = *(HashEntry**)a_p1;
if (p0->m_key == p1->m_key) return 0;
return -1;
};
};
// data member
public:
const int m_slot;
Array** m_a;
int m_size;
public:
Hash(const int a_max = INITSIZE);
Hash(const Hash& a_h);
virtual ~Hash();
// update
virtual int put(const int a_key, void* a_p);
virtual int remove(const int a_key);
virtual int replace(const int a_key, void* a_p);
virtual int clean();
// search
virtual int size() const;
virtual void* get(const int) const;
};
class HashReader
{
protected:
const Hash& m_hash;
int m_curarray;
int m_curcontent;
public:
HashReader(const Hash& a_hash);
virtual ~HashReader();
void next();
void first();
bool isEnd() const;
int getKey() const;
void* getVal() const;
};
class Set : protected Hash
{
public:
Set(const int a_max = INITSIZE);
virtual ~Set();
virtual int insert(void* a_p);
virtual int remove(void* a_p);
virtual int size() const;
virtual bool in(void*) const;
};
class BinHeap
{
friend class BinHeapReader;
class BinHeapEntry
{
public:
void* m_p;
BinHeapEntry* m_left;
BinHeapEntry* m_right;
public:
BinHeapEntry(void* a_p) :m_p(a_p), m_left(0), m_right(0){};
virtual ~BinHeapEntry(){};
};
protected:
int(*m_compare)(const void*, const void*);
BinHeapEntry* m_root;
Queue m_reuse;
int m_count;
public:
BinHeap(int(*a_compare)(const void*, const void*));
virtual ~BinHeap();
virtual void insert(void* a_p);
virtual void* removeTop();
virtual void clean();
virtual void* top() const;
virtual int size() const;
virtual bool isEmpty() const;
virtual bool exist(void* a_p) const;
};
class BinHeapReader
{
protected:
const BinHeap& m_heap;
Stack m_stack;
public:
BinHeapReader(const BinHeap& a_heap);
virtual ~BinHeapReader();
void next();
void first();
bool isEnd() const;
void* get() const;
};
}
using namespace Collection;
#endif // COLLECTION_DEFINED