equal
deleted
inserted
replaced
150 }; |
150 }; |
151 |
151 |
152 template<class E> class GrowableArrayIterator; |
152 template<class E> class GrowableArrayIterator; |
153 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator; |
153 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator; |
154 |
154 |
|
155 template<class E> |
|
156 class CompareClosure : public Closure { |
|
157 public: |
|
158 virtual int do_compare(const E&, const E&) = 0; |
|
159 }; |
|
160 |
155 template<class E> class GrowableArray : public GenericGrowableArray { |
161 template<class E> class GrowableArray : public GenericGrowableArray { |
156 friend class VMStructs; |
162 friend class VMStructs; |
157 |
163 |
158 private: |
164 private: |
159 E* _data; // data array |
165 E* _data; // data array |
430 |
436 |
431 while (max >= min) { |
437 while (max >= min) { |
432 int mid = (int)(((uint)max + min) / 2); |
438 int mid = (int)(((uint)max + min) / 2); |
433 E value = at(mid); |
439 E value = at(mid); |
434 int diff = compare(key, value); |
440 int diff = compare(key, value); |
|
441 if (diff > 0) { |
|
442 min = mid + 1; |
|
443 } else if (diff < 0) { |
|
444 max = mid - 1; |
|
445 } else { |
|
446 found = true; |
|
447 return mid; |
|
448 } |
|
449 } |
|
450 return min; |
|
451 } |
|
452 |
|
453 E insert_sorted(CompareClosure<E>* cc, const E& key) { |
|
454 bool found; |
|
455 int location = find_sorted(cc, key, found); |
|
456 if (!found) { |
|
457 insert_before(location, key); |
|
458 } |
|
459 return at(location); |
|
460 } |
|
461 |
|
462 template<typename K> |
|
463 int find_sorted(CompareClosure<E>* cc, const K& key, bool& found) { |
|
464 found = false; |
|
465 int min = 0; |
|
466 int max = length() - 1; |
|
467 |
|
468 while (max >= min) { |
|
469 int mid = (int)(((uint)max + min) / 2); |
|
470 E value = at(mid); |
|
471 int diff = cc->do_compare(key, value); |
435 if (diff > 0) { |
472 if (diff > 0) { |
436 min = mid + 1; |
473 min = mid + 1; |
437 } else if (diff < 0) { |
474 } else if (diff < 0) { |
438 max = mid - 1; |
475 max = mid - 1; |
439 } else { |
476 } else { |