357 for (int j = _len - 1; j >= idx; j--) { 358 _data[j + 1] = _data[j]; 359 } 360 _len++; 361 _data[idx] = elem; 362 } 363 364 void appendAll(const GrowableArray<E>* l) { 365 for (int i = 0; i < l->_len; i++) { 366 raw_at_put_grow(_len, l->_data[i], E()); 367 } 368 } 369 370 void sort(int f(E*,E*)) { 371 qsort(_data, length(), sizeof(E), (_sort_Fn)f); 372 } 373 // sort by fixed-stride sub arrays: 374 void sort(int f(E*,E*), int stride) { 375 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); 376 } 377 }; 378 379 // Global GrowableArray methods (one instance in the library per each 'E' type). 380 381 template<class E> void GrowableArray<E>::grow(int j) { 382 // grow the array by doubling its size (amortized growth) 383 int old_max = _max; 384 if (_max == 0) _max = 1; // prevent endless loop 385 while (j >= _max) _max = _max*2; 386 // j < _max 387 E* newData = (E*)raw_allocate(sizeof(E)); 388 int i = 0; 389 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); 390 // Needed for Visual Studio 2012 and older 391 #pragma warning(suppress: 4345) 392 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); 393 for (i = 0; i < old_max; i++) _data[i].~E(); 394 if (on_C_heap() && _data != NULL) { 395 FreeHeap(_data); 396 } | 357 for (int j = _len - 1; j >= idx; j--) { 358 _data[j + 1] = _data[j]; 359 } 360 _len++; 361 _data[idx] = elem; 362 } 363 364 void appendAll(const GrowableArray<E>* l) { 365 for (int i = 0; i < l->_len; i++) { 366 raw_at_put_grow(_len, l->_data[i], E()); 367 } 368 } 369 370 void sort(int f(E*,E*)) { 371 qsort(_data, length(), sizeof(E), (_sort_Fn)f); 372 } 373 // sort by fixed-stride sub arrays: 374 void sort(int f(E*,E*), int stride) { 375 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); 376 } 377 378 // Binary search and insertion utility. Search array for element 379 // matching key according to the static compare function. Insert 380 // that element is not already in the list. Assumes the list is 381 // already sorted according to compare function. 382 template <int compare(const E&, const E&)> E insert_sorted(E& key) { 383 bool found; 384 int location = find_sorted<E, compare>(key, found); 385 if (!found) { 386 insert_before(location, key); 387 } 388 return at(location); 389 } 390 391 template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) { 392 found = false; 393 int min = 0; 394 int max = length() - 1; 395 396 while (max >= min) { 397 int mid = (max + min) / 2; 398 E value = at(mid); 399 int diff = compare(key, value); 400 if (diff > 0) { 401 min = mid + 1; 402 } else if (diff < 0) { 403 max = mid - 1; 404 } else { 405 found = true; 406 return mid; 407 } 408 } 409 return min; 410 } 411 }; 412 413 // Global GrowableArray methods (one instance in the library per each 'E' type). 414 415 template<class E> void GrowableArray<E>::grow(int j) { 416 // grow the array by doubling its size (amortized growth) 417 int old_max = _max; 418 if (_max == 0) _max = 1; // prevent endless loop 419 while (j >= _max) _max = _max*2; 420 // j < _max 421 E* newData = (E*)raw_allocate(sizeof(E)); 422 int i = 0; 423 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); 424 // Needed for Visual Studio 2012 and older 425 #pragma warning(suppress: 4345) 426 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); 427 for (i = 0; i < old_max; i++) _data[i].~E(); 428 if (on_C_heap() && _data != NULL) { 429 FreeHeap(_data); 430 } |