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(E&, E&)> E insert_sorted(E& key) { 383 bool found; 384 int location = find_sorted<E, compare>(key, found); 385 if (!found) { 386 assert(location <= length(), "out of range"); 387 insert_before(location, key); 388 } 389 return at(location); 390 } 391 392 template <typename K, int compare(K&, E&)> int find_sorted(K& key, bool& found) { 393 found = false; 394 int min = 0; 395 int max = length() - 1; 396 397 while (max >= min) { 398 int mid = (max + min) / 2; 399 E value = at(mid); 400 int diff = compare(key, value); 401 if (diff > 0) { 402 min = mid + 1; 403 } else if (diff < 0) { 404 max = mid - 1; 405 } else { 406 found = true; 407 return mid; 408 } 409 } 410 return min; 411 } 412 }; 413 414 // Global GrowableArray methods (one instance in the library per each 'E' type). 415 416 template<class E> void GrowableArray<E>::grow(int j) { 417 // grow the array by doubling its size (amortized growth) 418 int old_max = _max; 419 if (_max == 0) _max = 1; // prevent endless loop 420 while (j >= _max) _max = _max*2; 421 // j < _max 422 E* newData = (E*)raw_allocate(sizeof(E)); 423 int i = 0; 424 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); 425 // Needed for Visual Studio 2012 and older 426 #pragma warning(suppress: 4345) 427 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); 428 for (i = 0; i < old_max; i++) _data[i].~E(); 429 if (on_C_heap() && _data != NULL) { 430 FreeHeap(_data); 431 } |