Append Sequence of Renumbered Items

[tjlaboss]

Is your feature request related to a problem? Please describe.

The method NumberedDataObjectCollection.append_renumber(step=...):

Appends the object, but will renumber the object if collision occurs. This behaves like append, except if there is a number collision the object will be renumbered to an available number. The number will be incremented by step until an available number is found.

Feature request: implement a related method to add a sequence of items with the same starting number and step. Use the next available complete sequence. We could call it something like NumberedObjectCollection.extend_renumber().

Describe the solution you'd like

Example: Assume we are building an input deck. We have cells 1, 2, 3, and 100. The next number is 4.

>>> new_cells = []
>>> for i in range(100):
...     new_cells.append( modify_cell(template=deck.cells[1].clone(), piece=i+1) )
>>> deck.cells.extend_renumber(new_cells)
>>> max(deck.cells.numbers)
200

Because there is not room for the 100 new cells on the interval [4, 100), the Cells collection adds them at [101, 200].

When step > 1, use the next uninterrupted range. For instance, if the user said cells.extend_renumber(new_cells, step=5), the sequence should not start at 4, even though it would safely skip over 100. Instead, the sequence should start at either 101 or 105. (Which?)

Describe alternatives you've considered
Right now, the user can just iterate over append_renumber(). That will work, but doing an extend_renumber() will be more efficient and will allow for a collection of related objects to be added in a sequence.

The user can also figure out the next sequence of available numbers manually and then just call extend().

Additional context
This will be useful for practical problems where a range of numbers is available for an addition to a model. If there are enough available numbers in the range, the numbered objects will be added there; but it is more important to keep them together than to put only some in the range.

[MicahGale]

So right now step is applied to the starting number until a gap is found. So I believe in this example it would try 101.

[tjlaboss]

Correct. Should it? Most likely yes, because that is consistent with the current append_renumber behavior.

[MicahGale]

I'm thinking about this and trying to think of the most efficient algorithm to find an open slot. Poor implementation feels like it be easily O(N^2).

I thinking:

1. find block size as a delta of max_num - min_num needed.
2. Maybe get a sorted NP array of the numbers then do something like nums[1:] - nums[:-1] then something like: valid_slots = slots > delta then valid_slots.index(True)?

This seems like it would be efficient.

[tjlaboss]

That would work. My first thought was just to add onto the end rather than finding the next available slot.

need = set(range(min_num, max_num + step))  # entire range must be available
nums = set(self.numbers)
if need & nums:
    oldmax = max(self.numbers)
    return range(oldmax, oldmax + max_num - min_num + step, step)
else:
    return range(min_num, max_num+step, step)

[MicahGale]

Just adding it all onto the end would effectively disregard the user's intent.

Also what you proposed would allow something:

used_nums = {1,3,5,7}
need = {2,4,6,8}

While valid I don't think the user would like that much, probably.

[tjlaboss]

need would be the complete range with a step of 1: {2,3,4,5,6,7,8}, resulting in an intersection of {3,5,7}.

I agree that adding it onto the end if a match is not found right away would displease users.

[MicahGale]

Oh ok. I see why you didn't do range(..,..,step) now. Your implementation seems like it could still lead to a lot retrying things. I'm trying to think of ways to optimize it so your not thrashing a lot of failed ones, because it feels elegant.

[tjlaboss]

Agreed. It's very efficient if you try once and then give up. Your solution is much better for always finding the next available slot.