libStatGen Software 1
Loading...
Searching...
No Matches
StringMap.cpp
1/*
2 * Copyright (C) 2010 Regents of the University of Michigan
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18#include "StringMap.h"
19
20int StringMap::alloc = 8;
21
22StringMap::StringMap(int startsize)
23{
24 count = 0;
25 size = (startsize + alloc) / alloc * alloc;
26 strings = new ::String * [size];
27 objects = new void * [size];
28};
29
30StringMap::~StringMap()
31{
32 for (int i = 0; i < count; i++)
33 delete strings[i];
34 delete [] strings;
35 delete [] objects;
36}
37
38void StringMap::Grow(int newsize)
39{
40 if (newsize >= size)
41 {
42 if ((newsize >> 1) >= size)
43 size = (newsize + alloc) / alloc * alloc;
44 else
45 {
46 size = alloc;
47 while (size <= newsize)
48 size *= 2;
49 }
50
51 size = (newsize + alloc) / alloc * alloc;
52
53 ::String ** newStrings = new ::String * [size];
54 void ** newObjects = new void * [size];
55
56 for (int i = 0; i < count; i++)
57 {
58 newStrings[i] = strings[i];
59 newObjects[i] = objects[i];
60 }
61
62 delete [] strings;
63 delete [] objects;
64
65 strings = newStrings;
66 objects = newObjects;
67 }
68}
69
70int StringMap::Add(const ::String & key, void * object)
71{
72 if (count == 0)
73 {
74 Grow(1);
75 strings[0] = new ::String(key);
76 objects[0] = object;
77 return count++;
78 }
79
80 int left = 0;
81 int right = count - 1;
82
83 while (right > left)
84 {
85 int probe = (left + right) / 2;
86 int test = key.SlowCompare(*(strings[probe]));
87
88 if (test == 0)
89 {
90 objects[probe] = object;
91 return probe;
92 }
93
94 if (test < 0)
95 right = probe - 1;
96 else
97 left = probe + 1;
98 }
99
100 int insertAt = left;
101 int test = key.SlowCompare(*(strings[insertAt]));
102
103 if (test == 0)
104 {
105 objects[insertAt] = object;
106 return insertAt;
107 }
108
109 if (test > 0) insertAt++;
110
111 Grow(count + 1);
112
113 if (insertAt < count)
114 {
115 for (int i = count; i > insertAt; i--)
116 {
117 strings[i] = strings[i - 1];
118 objects[i] = objects[i - 1];
119 }
120 }
121
122 strings[insertAt] = new ::String(key);
123 objects[insertAt] = object;
124 count++;
125
126 return insertAt;
127}
128
129int StringMap::Find(const ::String & s, void *(*create_object)())
130{
131 if (!count)
132 return create_object == NULL ? -1 : Add(s, create_object());
133
134 int left = 0;
135 int right = count - 1;
136
137 while (right > left)
138 {
139 int probe = (left + right) / 2;
140 int test = s.SlowCompare(*(strings[probe]));
141
142 if (test == 0)
143 return probe;
144
145 if (test < 0)
146 right = probe - 1;
147 else
148 left = probe + 1;
149 }
150
151 int position = left;
152 int test = s.SlowCompare(*(strings[left]));
153
154 if (test == 0)
155 return position;
156
157 if (create_object == NULL)
158 return -1;
159
160 if (test > 0)
161 position++;
162
163 Grow(count + 1);
164
165 if (position < count)
166 {
167 for (int i = count; i > position; i--)
168 {
169 strings[i] = strings[i - 1];
170 objects[i] = objects[i - 1];
171 }
172 }
173
174 strings[position] = new ::String(s);
175 objects[position] = create_object();
176 count++;
177
178 return position;
179}
180
181int StringMap::Find(const ::String & s) const
182{
183 if (!count) return -1;
184
185 int left = 0;
186 int right = count - 1;
187
188 while (right > left)
189 {
190 int probe = (left + right) / 2;
191 int test = s.SlowCompare(*(strings[probe]));
192
193 if (test == 0)
194 return probe;
195
196 if (test < 0)
197 right = probe - 1;
198 else
199 left = probe + 1;
200 }
201
202 int position = left;
203 int test = s.SlowCompare(*(strings[left]));
204
205 if (test == 0)
206 return position;
207
208 return -1;
209}
210
211int StringMap::FindStem(const ::String & stem) const
212{
213 if (!count) return -1;
214
215 int left = 0;
216 int right = count - 1;
217
218 while (right > left)
219 {
220 int probe = (left + right) / 2;
221 int test = strings[probe]->SlowCompareToStem(stem);
222
223 if (test == 0)
224 {
225 if ((left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0) ||
226 (right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0))
227 return -2;
228
229 return probe;
230 }
231
232 if (test > 0)
233 right = probe - 1;
234 else
235 left = probe + 1;
236 }
237
238 if (strings[left]->SlowCompareToStem(stem) == 0)
239 return left;
240
241 return -1;
242}
243
244int StringMap::FindFirstStem(const ::String & stem) const
245{
246 if (!count) return -1;
247
248 int left = 0;
249 int right = count - 1;
250
251 while (right > left)
252 {
253 int probe = (left + right) / 2;
254 int test = strings[probe]->SlowCompareToStem(stem);
255
256 if (test == 0)
257 {
258 while (left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0)
259 probe--;
260
261 return probe;
262 }
263
264 if (test > 0)
265 right = probe - 1;
266 else
267 left = probe + 1;
268 }
269
270 if (strings[left]->SlowCompareToStem(stem) == 0)
271 return left;
272
273 return -1;
274}
275
276void * StringMap::CreateMap()
277{
278 return (void *) new StringMap();
279}
280
281void StringMap::Clear()
282{
283 for (int i = 0; i < count; i++)
284 delete strings[i];
285 count = 0;
286}
287
288void StringMap::Delete(int index)
289{
290 count--;
291
292 delete strings[index];
293
294 for (int i = index; i < count; i++)
295 {
296 strings[i] = strings[i+1];
297 objects[i] = objects[i+1];
298 }
299}
300
301// StringIntMap class
302//
303
304int StringIntMap::alloc = 8;
305
306StringIntMap::StringIntMap(int startsize)
307{
308 count = 0;
309 size = (startsize + alloc) / alloc * alloc;
310 strings = new ::String * [size];
311 integers = new int[size];
312};
313
314StringIntMap::~StringIntMap()
315{
316 for (int i = 0; i < count; i++)
317 delete strings[i];
318 delete [] strings;
319 delete [] integers;
320}
321
322void StringIntMap::Grow(int newsize)
323{
324 if (newsize >= size)
325 {
326 if ((newsize >> 1) >= size)
327 size = (newsize + alloc) / alloc * alloc;
328 else
329 {
330 size = alloc;
331 while (size <= newsize)
332 size *= 2;
333 }
334
335 ::String ** newStrings = new ::String * [size];
336 int * newIntegers = new int [size];
337
338 for (int i = 0; i < count; i++)
339 {
340 newStrings[i] = strings[i];
341 newIntegers[i] = integers[i];
342 }
343
344 delete [] strings;
345 delete [] integers;
346
347 strings = newStrings;
348 integers = newIntegers;
349 }
350}
351
352int StringIntMap::Add(const ::String & key, int integer)
353{
354 if (count == 0)
355 {
356 Grow(1);
357 strings[0] = new ::String(key);
358 integers[0] = integer;
359 return count++;
360 }
361
362 int left = 0;
363 int right = count - 1;
364
365 while (right > left)
366 {
367 int probe = (left + right) / 2;
368 int test = key.SlowCompare(*(strings[probe]));
369
370 if (test == 0)
371 {
372 integers[probe] = integer;
373 return probe;
374 }
375
376 if (test < 0)
377 right = probe - 1;
378 else
379 left = probe + 1;
380 }
381
382 int insertAt = left;
383 int test = key.SlowCompare(*(strings[insertAt]));
384
385 if (test == 0)
386 {
387 integers[insertAt] = integer;
388 return insertAt;
389 }
390
391 if (test > 0) insertAt++;
392
393 Grow(count + 1);
394
395 if (insertAt < count)
396 {
397 for (int i = count; i > insertAt; i--)
398 {
399 strings[i] = strings[i - 1];
400 integers[i] = integers[i - 1];
401 }
402 }
403
404 strings[insertAt] = new ::String(key);
405 integers[insertAt] = integer;
406 count++;
407
408 return insertAt;
409}
410
411int StringIntMap::Find(const ::String & s, int defaultValue)
412{
413 if (!count)
414 return Add(s, defaultValue);
415
416 int left = 0;
417 int right = count - 1;
418
419 while (right > left)
420 {
421 int probe = (left + right) / 2;
422 int test = s.SlowCompare(*(strings[probe]));
423
424 if (test == 0)
425 return probe;
426
427 if (test < 0)
428 right = probe - 1;
429 else
430 left = probe + 1;
431 }
432
433 int position = left;
434 int test = s.SlowCompare(*(strings[left]));
435
436 if (test == 0)
437 return position;
438
439 if (test > 0)
440 position++;
441
442 Grow(count + 1);
443
444 if (position < count)
445 {
446 for (int i = count; i > position; i--)
447 {
448 strings[i] = strings[i - 1];
449 integers[i] = integers[i - 1];
450 }
451 }
452
453 strings[position] = new ::String(s);
454 integers[position] = defaultValue;
455 count++;
456
457 return position;
458}
459
460int StringIntMap::Find(const ::String & s) const
461{
462 if (!count) return -1;
463
464 int left = 0;
465 int right = count - 1;
466
467 while (right > left)
468 {
469 int probe = (left + right) / 2;
470 int test = s.SlowCompare(*(strings[probe]));
471
472 if (test == 0)
473 return probe;
474
475 if (test < 0)
476 right = probe - 1;
477 else
478 left = probe + 1;
479 }
480
481 int position = left;
482 int test = s.SlowCompare(*(strings[left]));
483
484 if (test == 0)
485 return position;
486
487 return -1;
488}
489
490int StringIntMap::FindStem(const ::String & stem) const
491{
492 if (!count) return -1;
493
494 int left = 0;
495 int right = count - 1;
496
497 while (right > left)
498 {
499 int probe = (left + right) / 2;
500 int test = strings[probe]->SlowCompareToStem(stem);
501
502 if (test == 0)
503 {
504 if ((left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0) ||
505 (right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0))
506 return -2;
507
508 return probe;
509 }
510
511 if (test > 0)
512 right = probe - 1;
513 else
514 left = probe + 1;
515 }
516
517 if (strings[left]->SlowCompareToStem(stem) == 0)
518 return left;
519
520 return -1;
521}
522
523void StringIntMap::Clear()
524{
525 for (int i = 0; i < count; i++)
526 delete strings[i];
527 count = 0;
528}
529
530int StringIntMap::GetCount(const ::String & key) const
531{
532 int index = Find(key);
533 return index == -1 ? 0 : integers[index];
534}
535
536int StringIntMap::IncrementCount(const ::String & key)
537{
538 int index = Find(key);
539
540 if (index != -1)
541 return ++(integers[index]);
542
543 SetInteger(key, 1);
544 return 1;
545}
546
547int StringIntMap::DecrementCount(const ::String & key)
548{
549 int index = Find(key);
550
551 if (index != -1)
552 return --(integers[index]);
553
554 SetInteger(key, -1);
555 return -1;
556}
557
558void StringIntMap::Delete(int index)
559{
560 count--;
561
562 delete strings[index];
563
564 for (int i = index; i < count; i++)
565 {
566 strings[i] = strings[i+1];
567 integers[i] = integers[i+1];
568 }
569}
570
571
572