Pushes `item` into the vector. If the vector does not have sufficient capacity, we'll first consolidate and then increase its capacity if the consolidated results still occupy a significant fraction of the vector. The worst-case cost of this function is O(n log n) in the number of items the vector stores, but amortizes to O(log n).
(&mut self, item: (D, Diff))
| 448 | /// The worst-case cost of this function is O(n log n) in the number of items the vector stores, |
| 449 | /// but amortizes to O(log n). |
| 450 | pub fn push(&mut self, item: (D, Diff)) { |
| 451 | let capacity = self.data.capacity(); |
| 452 | if self.data.len() == capacity { |
| 453 | // The vector is full. First, consolidate to try to recover some space. |
| 454 | self.consolidate(); |
| 455 | |
| 456 | // We may need more capacity if our current capacity is within `1+1/(n+1)` of the length. |
| 457 | // This corresponds to `cap < len + len/(n+1)`, which is the logic we use. |
| 458 | let length = self.data.len(); |
| 459 | let dampener = self.growth_dampener; |
| 460 | if capacity < length + length / (dampener + 1) { |
| 461 | // We would like to increase the capacity by a factor of `1+1/(n+1)`, which involves |
| 462 | // determining the target capacity, and then reserving an amount that achieves this |
| 463 | // while working around the existing length. |
| 464 | let new_cap = capacity + capacity / (dampener + 1); |
| 465 | self.data.reserve_exact(new_cap - length); |
| 466 | } |
| 467 | } |
| 468 | |
| 469 | self.data.push(item); |
| 470 | } |
| 471 | |
| 472 | /// Consolidate the contents. |
| 473 | pub fn consolidate(&mut self) { |