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 "StringArray.h"
19 #include "InputFile.h"
20 #include "Sort.h"
21 #include "Error.h"
22
23 #include <string.h>
24
25 int StringArray::alloc = 32;
26 bool StringArray::lazyMemoryManagement = false;
27
StringArray(int startsize)28 StringArray::StringArray(int startsize)
29 {
30 count = startsize;
31 size = (startsize + alloc) / alloc * alloc;
32 strings = new String * [size];
33 for (int i = 0; i < count; i++)
34 strings[i] = new String;
35 for (int i = count; i < size; i++)
36 strings[i] = NULL;
37 };
38
StringArray(StringArray & rhs)39 StringArray::StringArray(StringArray & rhs)
40 {
41 count = rhs.count;
42 size = (rhs.count + alloc) / alloc * alloc;
43 strings = new String * [size];
44
45 for (int i = 0; i < count; i++)
46 strings[i] = new String(rhs[i]);;
47 for (int i = count; i < size; i++)
48 strings[i] = NULL;
49 }
50
~StringArray()51 StringArray::~StringArray()
52 {
53 for (int i = 0; i < size; i++)
54 if (strings[i] != NULL)
55 delete strings[i];
56 else
57 break;
58
59 delete [] strings;
60 }
61
CharLength()62 int StringArray::CharLength()
63 {
64 int charlen = 0;
65 for (int i = 0; i < count; i++)
66 charlen += strings[i]->Length();
67 return charlen;
68 }
69
Read(const char * filename)70 void StringArray::Read(const char * filename)
71 {
72 IFILE f = ifopen(filename, "rb");
73 if (f == NULL) return;
74 Read(f);
75 ifclose(f);
76 }
77
Write(const char * filename)78 void StringArray::Write(const char * filename)
79 {
80 FILE * f = fopen(filename, "wt");
81 if (f == NULL) return;
82 Write(f);
83 fclose(f);
84 }
85
WriteLine(const char * filename)86 void StringArray::WriteLine(const char * filename)
87 {
88 FILE * f = fopen(filename, "wt");
89 if (f == NULL) return;
90 WriteLine(f);
91 fclose(f);
92 }
93
Read(FILE * f)94 void StringArray::Read(FILE * f)
95 {
96 while (!feof(f))
97 {
98 Grow(count + 1);
99 if (strings[count] == NULL)
100 strings[count] = new String;
101 strings[count]->ReadLine(f);
102 count++;
103 }
104 }
105
Write(FILE * f)106 void StringArray::Write(FILE * f)
107 {
108 for (int i = 0; i < count; i++)
109 strings[i]->WriteLine(f);
110 }
111
WriteLine(FILE * f)112 void StringArray::WriteLine(FILE * f)
113 {
114 for (int i = 0; i < count; i++)
115 fprintf(f, "%s%c", (const char *)(*strings[i]), i == count-1 ? '\n' : '\t');
116 }
117
Read(IFILE & f)118 void StringArray::Read(IFILE & f)
119 {
120 while (!ifeof(f))
121 {
122 Grow(count + 1);
123 if (strings[count] == NULL)
124 strings[count] = new String;
125 strings[count]->ReadLine(f);
126 if (ifeof(f) && strings[count]->Length()==0)
127 {
128 return;
129 }
130 count++;
131 }
132 }
133
Grow(int newsize)134 void StringArray::Grow(int newsize)
135 {
136 if (newsize >= size)
137 {
138 int oldsize = size;
139
140 if ((newsize >> 1) >= size)
141 size = (newsize + alloc) / alloc * alloc;
142 else
143 {
144 size = alloc;
145 while (size <= newsize)
146 size *= 2;
147 }
148 String ** tmp = new String * [size];
149 for (int i = 0; i < oldsize; i++)
150 tmp[i] = strings[i];
151 for (int i = oldsize; i < size; i++)
152 tmp[i] = NULL;
153 delete [] strings;
154 strings = tmp;
155 }
156 }
157
Clear()158 void StringArray::Clear()
159 {
160 if (!lazyMemoryManagement)
161 {
162 for (int i = 0; i < size; i++)
163 {
164 if (strings[i] != NULL)
165 {
166 delete strings[i];
167 strings[i] = NULL;
168 }
169 else
170 {
171 break;
172 }
173 }
174 }
175 count = 0;
176 }
177
AddColumns(const String & s,char ch)178 int StringArray::AddColumns(const String & s, char ch)
179 {
180 if (s.Length() > 0)
181 for (int pos = 0; pos <= s.Length(); pos++)
182 {
183 int oldpos = pos;
184 pos = s.FindChar(ch, pos);
185 if (pos == -1) pos = s.Length();
186 Grow(count + 1);
187
188 if (strings[count] == NULL)
189 {
190 strings[count] = new String(pos - oldpos);
191 }
192 strings[count]->SetLength(pos - oldpos);
193 memcpy((char *) *strings[count++], ((const char *) s) + oldpos, pos - oldpos);
194 }
195
196 return count;
197 }
198
AddColumns(const String & s,char ch,int maxColumns)199 int StringArray::AddColumns(const String & s, char ch, int maxColumns)
200 {
201 maxColumns += count;
202
203 if (s.Length() > 0)
204 for (int pos = 0; pos <= s.Length() && maxColumns != count; pos++)
205 {
206 int oldpos = pos;
207 pos = s.FindChar(ch, pos);
208 if (pos == -1) pos = s.Length();
209 Grow(count + 1);
210
211 if (strings[count] == NULL)
212 strings[count] = new String(pos - oldpos);
213 strings[count]->SetLength(pos - oldpos);
214 memcpy((char *) *strings[count++], ((const char *) s) + oldpos, pos - oldpos);
215 };
216
217 return count;
218 }
219
AddTokens(const String & s,char ch)220 int StringArray::AddTokens(const String & s, char ch)
221 {
222 for (int pos = 0; pos < s.Length(); pos++)
223 {
224 while (pos < s.Length() && s[pos] == ch) pos++;
225 int oldpos = pos;
226
227 while (pos < s.Length() && s[pos] != ch) pos++;
228
229 if (oldpos < s.Length())
230 {
231 Grow(count + 1);
232 if (strings[count] == NULL)
233 {
234 strings[count] = new String(pos - oldpos);
235 }
236 strings[count]->SetLength(pos - oldpos);
237 memcpy((char *) *strings[count++], (const char *) s + oldpos, pos - oldpos);
238 }
239 }
240
241 return count;
242 }
243
AddTokens(const String & s,const String & separators)244 int StringArray::AddTokens(const String & s, const String & separators)
245 {
246 for (int pos = 0; pos < s.Length(); pos++)
247 {
248 while (pos < s.Length() && separators.FindChar(s[pos]) != -1) pos++;
249 int oldpos = pos;
250
251 while (pos < s.Length() && separators.FindChar(s[pos]) == -1) pos++;
252
253 if (oldpos < s.Length())
254 {
255 Grow(count + 1);
256 if (strings[count] == NULL)
257 strings[count] = new String(pos - oldpos);
258 strings[count]->SetLength(pos - oldpos);
259 memcpy((char *) *strings[count++], ((const char *) s) + oldpos, pos - oldpos);
260 }
261 }
262
263 return count;
264 }
265
Dimension(int newcount)266 int StringArray::Dimension(int newcount)
267 {
268 if (newcount > count)
269 {
270 Grow(newcount);
271 for (int i = count; i < newcount; i++)
272 {
273 if (strings[i] == NULL)
274 strings[i] = new String;
275 else
276 strings[i]->Clear();
277 }
278 count = newcount;
279 }
280 else if (newcount < count)
281 {
282 if (!lazyMemoryManagement)
283 {
284 for (int i = newcount; i < size; i++)
285 {
286 if (strings[i] != NULL)
287 {
288 delete strings[i];
289 strings[i] = NULL;
290 }
291 else
292 {
293 break;
294 }
295 }
296 }
297 count = newcount;
298 }
299
300 return count;
301 }
302
Find(const String & s) const303 int StringArray::Find(const String & s) const
304 {
305 for (int i = 0; i < count; i++)
306 if (*(strings[i]) == s)
307 return i;
308 return -1;
309 }
310
FastFind(const String & s) const311 int StringArray::FastFind(const String & s) const
312 {
313 for (int i = 0; i < count; i++)
314 if (strings[i]->FastCompare(s) == 0)
315 return i;
316 return -1;
317 }
318
SlowFind(const String & s) const319 int StringArray::SlowFind(const String & s) const
320 {
321 for (int i = 0; i < count; i++)
322 if (strings[i]->SlowCompare(s) == 0)
323 return i;
324 return -1;
325 }
326
Add(const String & s)327 int StringArray::Add(const String & s)
328 {
329 Grow(count + 1);
330 if (strings[count] == NULL)
331 {
332 strings[count] = new String(s);
333 }
334 else
335 {
336 *strings[count] = s;
337 }
338 return ++count;
339 }
340
InsertAt(int position,const String & s)341 void StringArray::InsertAt(int position, const String & s)
342 {
343 Grow(count + 1);
344
345 String * newString = strings[count];
346 if (newString == NULL)
347 newString = new String(s);
348 else
349 *newString = s;
350
351 for (int i = count; i > position; i--)
352 strings[i] = strings[i - 1];
353 strings[position] = newString;
354 count++;
355 }
356
Last() const357 String & StringArray::Last() const
358 {
359 if (!count) error("StringArray: Null String Access");
360 return *(strings[count - 1]);
361 }
362
Delete(int index)363 void StringArray::Delete(int index)
364 {
365 String * oldString = strings[index];
366
367 count--;
368 for (; index < count; index++)
369 strings[index] = strings[index + 1];
370 strings[count] = oldString;
371 }
372
operator =(const StringArray & rhs)373 StringArray & StringArray::operator = (const StringArray & rhs)
374 {
375 Dimension(rhs.count);
376 for (int i = 0; i < rhs.count; i++)
377 *strings[i] = *rhs.strings[i];
378 return *this;
379 }
380
operator ==(const StringArray & rhs) const381 bool StringArray::operator == (const StringArray & rhs) const
382 {
383 if (count != rhs.count) return false;
384 for (int i = 0; i < rhs.count; i++)
385 if (*strings[i] != *rhs.strings[i])
386 return false;
387 return true;
388 }
389
Sort()390 void StringArray::Sort()
391 {
392 QuickSort(strings, count, sizeof(String *), ComparisonForSort);
393 }
394
ComparisonForSort(const void * a,const void * b)395 int StringArray::ComparisonForSort(const void * a, const void * b)
396 {
397 String * string1 = *(String **) a;
398 String * string2 = *(String **) b;
399
400 return Compare(*string1, *string2);
401 }
402
Pop()403 String StringArray::Pop()
404 {
405 String result = *(strings[count - 1]);
406
407 Dimension(count - 1);
408
409 return result;
410 }
411
Trim()412 void StringArray::Trim()
413 {
414 for (int i = 0; i < count; i++)
415 strings[i]->Trim();
416 }
417
Print()418 void StringArray::Print()
419 {
420 Print(stdout);
421 }
422
Print(FILE * output)423 void StringArray::Print(FILE * output)
424 {
425 for (int i = 0; i < count; i++)
426 fprintf(output, "%s\n", (const char *)(*strings[i]));
427 }
428
PrintLine()429 void StringArray::PrintLine()
430 {
431 PrintLine(stdout);
432 }
433
PrintLine(FILE * output)434 void StringArray::PrintLine(FILE * output)
435 {
436 for (int i = 0; i < count; i++)
437 fprintf(output, "%s%c", (const char *)(*strings[i]), i == count - 1 ? '\n' : '\t');
438 }
439
Swap(StringArray & s)440 void StringArray::Swap(StringArray & s)
441 {
442 String ** temp = s.strings;
443 s.strings = strings;
444 strings = temp;
445
446 int swap = s.size;
447 s.size = size;
448 size = swap;
449
450 swap = s.count;
451 s.count = count;
452 count = swap;
453 }
454
455