libStatGen Software  1
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 
20 int StringMap::alloc = 8;
21 
22 StringMap::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 
30 StringMap::~StringMap()
31 {
32  for (int i = 0; i < count; i++)
33  delete strings[i];
34  delete [] strings;
35  delete [] objects;
36 }
37 
38 void 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 
70 int 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 
129 int 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 
181 int 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 
211 int 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 
244 int 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 
276 void * StringMap::CreateMap()
277 {
278  return (void *) new StringMap();
279 }
280 
281 void StringMap::Clear()
282 {
283  for (int i = 0; i < count; i++)
284  delete strings[i];
285  count = 0;
286 }
287 
288 void 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 
304 int StringIntMap::alloc = 8;
305 
306 StringIntMap::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 
314 StringIntMap::~StringIntMap()
315 {
316  for (int i = 0; i < count; i++)
317  delete strings[i];
318  delete [] strings;
319  delete [] integers;
320 }
321 
322 void 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 
352 int 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 
411 int 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 
460 int 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 
490 int 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 
523 void StringIntMap::Clear()
524 {
525  for (int i = 0; i < count; i++)
526  delete strings[i];
527  count = 0;
528 }
529 
530 int StringIntMap::GetCount(const ::String & key) const
531 {
532  int index = Find(key);
533  return index == -1 ? 0 : integers[index];
534 }
535 
536 int 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 
547 int 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 
558 void 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 
String
Definition: StringBasics.h:38
StringMap
Definition: StringMap.h:23