18 #include "StringMap.h"
20 int StringMap::alloc = 8;
22 StringMap::StringMap(
int startsize)
25 size = (startsize + alloc) / alloc * alloc;
26 strings = new ::String * [size];
27 objects =
new void * [size];
30 StringMap::~StringMap()
32 for (
int i = 0; i < count; i++)
38 void StringMap::Grow(
int newsize)
42 if ((newsize >> 1) >= size)
43 size = (newsize + alloc) / alloc * alloc;
47 while (size <= newsize)
51 size = (newsize + alloc) / alloc * alloc;
53 ::String ** newStrings = new ::String * [size];
54 void ** newObjects =
new void * [size];
56 for (
int i = 0; i < count; i++)
58 newStrings[i] = strings[i];
59 newObjects[i] = objects[i];
70 int StringMap::Add(const ::String & key,
void *
object)
75 strings[0] = new ::String(key);
81 int right = count - 1;
85 int probe = (left + right) / 2;
86 int test = key.SlowCompare(*(strings[probe]));
90 objects[probe] = object;
101 int test = key.SlowCompare(*(strings[insertAt]));
105 objects[insertAt] = object;
109 if (test > 0) insertAt++;
113 if (insertAt < count)
115 for (
int i = count; i > insertAt; i--)
117 strings[i] = strings[i - 1];
118 objects[i] = objects[i - 1];
122 strings[insertAt] = new ::String(key);
123 objects[insertAt] = object;
129 int StringMap::Find(const ::String & s,
void *(*create_object)())
132 return create_object == NULL ? -1 : Add(s, create_object());
135 int right = count - 1;
139 int probe = (left + right) / 2;
140 int test = s.SlowCompare(*(strings[probe]));
152 int test = s.SlowCompare(*(strings[left]));
157 if (create_object == NULL)
165 if (position < count)
167 for (
int i = count; i > position; i--)
169 strings[i] = strings[i - 1];
170 objects[i] = objects[i - 1];
174 strings[position] = new ::String(s);
175 objects[position] = create_object();
181 int StringMap::Find(const ::String & s)
const
183 if (!count)
return -1;
186 int right = count - 1;
190 int probe = (left + right) / 2;
191 int test = s.SlowCompare(*(strings[probe]));
203 int test = s.SlowCompare(*(strings[left]));
211 int StringMap::FindStem(const ::String & stem)
const
213 if (!count)
return -1;
216 int right = count - 1;
220 int probe = (left + right) / 2;
221 int test = strings[probe]->SlowCompareToStem(stem);
225 if ((left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0) ||
226 (right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0))
238 if (strings[left]->SlowCompareToStem(stem) == 0)
244 int StringMap::FindFirstStem(const ::String & stem)
const
246 if (!count)
return -1;
249 int right = count - 1;
253 int probe = (left + right) / 2;
254 int test = strings[probe]->SlowCompareToStem(stem);
258 while (left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0)
270 if (strings[left]->SlowCompareToStem(stem) == 0)
276 void * StringMap::CreateMap()
281 void StringMap::Clear()
283 for (
int i = 0; i < count; i++)
288 void StringMap::Delete(
int index)
292 delete strings[index];
294 for (
int i = index; i < count; i++)
296 strings[i] = strings[i+1];
297 objects[i] = objects[i+1];
304 int StringIntMap::alloc = 8;
306 StringIntMap::StringIntMap(
int startsize)
309 size = (startsize + alloc) / alloc * alloc;
310 strings = new ::String * [size];
311 integers =
new int[size];
314 StringIntMap::~StringIntMap()
316 for (
int i = 0; i < count; i++)
322 void StringIntMap::Grow(
int newsize)
326 if ((newsize >> 1) >= size)
327 size = (newsize + alloc) / alloc * alloc;
331 while (size <= newsize)
335 ::String ** newStrings = new ::String * [size];
336 int * newIntegers =
new int [size];
338 for (
int i = 0; i < count; i++)
340 newStrings[i] = strings[i];
341 newIntegers[i] = integers[i];
347 strings = newStrings;
348 integers = newIntegers;
352 int StringIntMap::Add(const ::String & key,
int integer)
357 strings[0] = new ::String(key);
358 integers[0] = integer;
363 int right = count - 1;
367 int probe = (left + right) / 2;
368 int test = key.SlowCompare(*(strings[probe]));
372 integers[probe] = integer;
383 int test = key.SlowCompare(*(strings[insertAt]));
387 integers[insertAt] = integer;
391 if (test > 0) insertAt++;
395 if (insertAt < count)
397 for (
int i = count; i > insertAt; i--)
399 strings[i] = strings[i - 1];
400 integers[i] = integers[i - 1];
404 strings[insertAt] = new ::String(key);
405 integers[insertAt] = integer;
411 int StringIntMap::Find(const ::String & s,
int defaultValue)
414 return Add(s, defaultValue);
417 int right = count - 1;
421 int probe = (left + right) / 2;
422 int test = s.SlowCompare(*(strings[probe]));
434 int test = s.SlowCompare(*(strings[left]));
444 if (position < count)
446 for (
int i = count; i > position; i--)
448 strings[i] = strings[i - 1];
449 integers[i] = integers[i - 1];
453 strings[position] = new ::String(s);
454 integers[position] = defaultValue;
460 int StringIntMap::Find(const ::String & s)
const
462 if (!count)
return -1;
465 int right = count - 1;
469 int probe = (left + right) / 2;
470 int test = s.SlowCompare(*(strings[probe]));
482 int test = s.SlowCompare(*(strings[left]));
490 int StringIntMap::FindStem(const ::String & stem)
const
492 if (!count)
return -1;
495 int right = count - 1;
499 int probe = (left + right) / 2;
500 int test = strings[probe]->SlowCompareToStem(stem);
504 if ((left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0) ||
505 (right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0))
517 if (strings[left]->SlowCompareToStem(stem) == 0)
523 void StringIntMap::Clear()
525 for (
int i = 0; i < count; i++)
530 int StringIntMap::GetCount(const ::String & key)
const
532 int index = Find(key);
533 return index == -1 ? 0 : integers[index];
536 int StringIntMap::IncrementCount(const ::String & key)
538 int index = Find(key);
541 return ++(integers[index]);
547 int StringIntMap::DecrementCount(const ::String & key)
549 int index = Find(key);
552 return --(integers[index]);
558 void StringIntMap::Delete(
int index)
562 delete strings[index];
564 for (
int i = index; i < count; i++)
566 strings[i] = strings[i+1];
567 integers[i] = integers[i+1];