[RFC] Normalize array's "auto-increment" value on copy on write

> On Thu, 20 Jun 2019 at 13:11, Wes <netmo.php@gmail.com> wrote: > > > I left that out of scope for the RFC, for reasons I don't have the > > knowledge to describe properly. In the following example, `unset()` > should > > reset the auto increment to `1` only after the third `unset()` call > > > > ``` > > $array = [0, 1, 2, 3]; // auto increment is 4 because there are "holes" > in > > the index > > unset($array[1]); // auto increment is still 4 > > unset($array[2]); // auto increment is still 4 > > unset($array[3]); // auto increment is 1, because the index sequence is > > contiguous, without holes > > ``` > > > > > I wonder if it would be possible (and sufficient) to detect if the element > being removed was the highest key, and only then look for the new "next" > value. > > The new value can be found either by decrementing the known value until you > hit an existing entry (optimal for large arrays with few gaps in the > sequence of keys) or by checking all the keys and finding the max (optimal > for small but sparse arrays like [12, 145, 65546]). > > # pseudocode: > > if ( key_being_unset == array.next_key - 1 ) { > if ( short_or_likely_to_be_sparse(array) ) { > new_highest_key = max(array.keys); > } else { > # Find highest unused number, starting from the one just deleted > do { > new_highest_key = key_being_unset - 1; > } while ( not key_exists(array, new_highest_key) ); > array.next_key = new_highest_key + 1; > } > } > > > I've no idea if this is plausible or not. > > Regards, > -- > Rowan Collins > [IMSoP] >