Insert & insert many

[pczarn]

• fn insert
• fn insert_many - needs a good name

[Jujumba]

I guess insert_slice may be a good name

[Jujumba]

I've been on insert_many for a while, and the edge-case of inserting a slice at block boundaries seems pretty tough to implement meaningfully

Maybe this function shouldn't be present at all? I mean, std::Vec and ferrilab's BitVec lacks this, and there seems to be no appetite for this function

@pczarn , what do you think?

[pczarn]

@Jujumba maybe, maybe not, hard to tell. It's true that I haven't ever seen this in Rust, and would expect it still to be useful for someone out there even ,

Edit: even if rarely, though more often for strings of bits.

Not a priority, but I think if you got started it's okay to finish.

Further, ferrilabs have BitSlice's copy_wthin so we would like to deal with edge cases of block boundaries in the future. You may take a look at how ferrilabs do copy_within.

[Jujumba]

@Jujumba maybe, maybe not, hard to tell. It's true that I haven't ever seen this in Rust, and would expect it still to be useful for someone out there even ,

Edit: even if rarely, though more often for strings of bits.

Not a priority, but I think if you got started it's okay to finish.

Further, ferrilabs have BitSlice's copy_wthin so we would like to deal with edge cases of block boundaries in the future. You may take a look at how ferrilabs do copy_within.

I've come up with a workaround that from my perspective is reasonable enough: if insertion crosses a block, then a simple way to insert the slice would be to "split" the insertion

I'll submit a PR for that soon

[Jujumba]

@Jujumba maybe, maybe not, hard to tell. It's true that I haven't ever seen this in Rust, and would expect it still to be useful for someone out there even ,
Edit: even if rarely, though more often for strings of bits.
Not a priority, but I think if you got started it's okay to finish.
Further, ferrilabs have BitSlice's copy_wthin so we would like to deal with edge cases of block boundaries in the future. You may take a look at how ferrilabs do copy_within.

I've come up with a workaround that from my perspective is reasonable enough: if insertion crosses a block, then a simple way to insert the slice would be to "split" the insertion

I'll submit a PR for that soon

Just looked into ferrilab's bitvec: seems like an overkill for me

[pczarn]

@Jujumba

They do it like this

1. do correctness checks / assertions like ours insert
2. if the copy source and destination overlap, then go through blocks in reverse
3. assign state to "first block"
4. for each block having destination and source
   a) if "first block" or "last block", then copy some bits
   b) if "body block", then copy block
   c) if "first block", then set state to "body block"
   d) if "body block", then maybe set state to "last block" (???)
   e) repeat 4.a-d until we are at "last block"

Also, we should allow this function for iter: impl ExactSizeIterator + Iterator<Item = bool>

[pczarn]

@Jujumba

This first/body/last block may be not quite accurate, I did not read that much of their code. Though essentially you are right about splitting copies, and there are at least two ways to split - state machine or 3x call.

[pczarn]

@Jujumba

Did you mean splitting insertions or copies?

[Jujumba]

@Jujumba

Did you mean splitting insertions or copies?

Something like splitting insertions

It may be unclear what I mean, so better see the code which I'll send now

[pczarn]

Basically all copies of strings or slices or bits or whatever that can overlap must work for the overlap and users sometimes can say there could be overlap or promise no overlap

[Jujumba]

@Jujumba

They do it like this

1. do correctness checks / assertions like ours `insert`

2. if the copy source and destination overlap, then go through blocks in reverse

3. assign state to "first block"

4. for each block having destination and source
   a) if "first block" or "last block", then copy some bits
   b) if "body block", then copy block
   c) if "first block", then set state to "body block"
   d) if "body block", then maybe set state to "last block" (???)
   e) repeat 4.a-d until we are at "last block"

Also, we should allow this function for iter: impl ExactSizeIterator + Iterator<Item = bool>

What do you mean by destination and source overlap? Do you mean crossing a block?

[pczarn]

I mean different blocks at the beginning of source and at the end of source and beginning of destination.

I recommend drawing it all on paper, how you would like the algorithm to work.