Add LIFO functions to 'ring-buffer type.

[solbloch]

Accidentally closed last PR.

Split into three commits.

[solbloch]

Do we need to add some next-item things for the LIFO implementation? It doesn't seem to have any obvious uses, maybe I just don't notice?

[Ambrevar]

Finally found time to look at this, sorry for the delay!

Thinking a bit more about it, I think "last-in-first-out" should be an container slot and all methods should change their behaviour depending on the value of this slot.

Rationale: the container is meant to be generic, i.e. to use the same function as any other container. Say, you have a list of containers (lists, ring-buffers, vectors) in a list and you want index X in all those containers: the generic item-at will pick the wrong index in a LIFO ring-buffer.

Does that make sense? Any other idea?

Suggestions:

• delete-item should be named delete-item-at.

• Can you implement delete-item too? It takes an item as argument, see the others uses in the library.

• To implement the delete-* defmethods, I believe ring-buffer should be an ordered-container-mixin.

• Once you've adapted item-at, first-element, etc. to obbey the last-in-first-out slot, you can have all other functions depend on those methods. For instance, at the moment iterate-nodes uses buffer-start and buffer-end which is wrong for LIFOs, so it should be changed to use first-element and (item-at (size ...)).

Thoughts?

Let me know if you need help with this, I can also work on it.

[solbloch]

It seems the item-at function is just reducing the ring-buffer to the list that's underneath it, ignoring all the existing FIFO logic. Am I misreading? What should I change?

[Ambrevar]

item-at can take multiple indices in other containers, but apparently for ring-buffers it was decided to ignore the indices after the first one, hence the (car indexes).

What you need to do here is check the value of last-in-first-out-flag: if true, return the lifo-indexed element, otherwise return the value originally returned by item-at.

In make-ring-buffer I suggest you make last-in-first-out optional and default to nil.

[solbloch]

Do you think it's better etiquette to define a ring-buffer and write LIFO and FIFO subclasses?

[Ambrevar]

It's a good idea. What about the following:

• The current ring-buffer class is the FIFO one.

• Overhaul the methods so that it's easy to change the direction.

• Create a new ring-buffer-reverse that inherits from ring-buffer and overloads the few methods where the direction matters.

What do you think?

[solbloch]

Seems good. Maybe reverse should be the default, but I guess we can leave it how it is.

Also will have to adapt our deleting functions and such. I'll start working on it.

[Ambrevar]

Great!

We can't change the default because that would break backward compatibility :(

[solbloch]

Shall I extend our item-at's to ref multiple indices?

[Ambrevar]

If other containers support this, it makes sense. Would be nice to know why it wasn't supported in the first place. Maybe out of laziness?

[solbloch]

Another question: delete-item-at for ring-buffer-reverse is our LIFO one that keeps the LIFO-indexes intact, but delete-item-at for ring-buffer, should I just NIL the item? What do you think?

[solbloch]

Also, still don't understand this current-item nonsense. Doesn't seem useful to me, again maybe I'm not seeing it's usefulness?

[Ambrevar]

delete-item-at: Why just NIL the item? To me it seems that you need to shift all the elements, just like for ring-buffer-reverse. Actually, beside the index, it's the same function for both ring-buffers if I'm not mistaken.

current-item: indeed, it does not seem to make sense. I think there was some confusion by the time the library was written precisely between FIFO and LIFO. To keep backward compatibility, I suggest we make current-item return the last index. For ring-buffer, that's the buffer end (as currently implemented), for ring-buffer-reverse, that's the buffer start.

[solbloch]

current-item for ring-buffer-reverse should be the buffer start? Why not just lifo-index 0 (most recent added item).

Also I'm not sure how to implement delete-item-at for ring-buffer, because I'm not sure why one would want to delete from ring-buffer by arbitrary underlying vector index.

There should really be no difference for a FIFO and LIFO data structure except the dequeue behavior (irrelevant here), not sure what this ring-buffer with raw vector indexing has to do with it. If we wanted our data structure to be FIFO we could just write a fifo-index function similar to the lifo-index that I already implemented.

[Ambrevar]

Solomon Bloch notifications@github.com writes:

current-item for ring-buffer-reverse should be the buffer start? Why not just lifo-index 0 (most recent added item).

Why not. Then both LIFO and FIFO's current-item would point to the same item, right? Probably no big deal.

Also I'm not sure how to implement delete-item-at for ring-buffer, because I'm not sure why one would want to delete from ring-buffer by arbitrary underlying vector index.

Simple use case: imagine the user wants to clear specific items in a history. Emacs can do this for instance.

There should really be no difference for a FIFO and LIFO data structure except the dequeue behavior (irrelevant here), not sure what this ring-buffer with raw vector indexing has to do with it. If we wanted our data structure to be FIFO we could just write a fifo-index function similar to the lifo-index that I already implemented.

I'm not sure what you are asking here. Indeed, the FIFO and LIFO structures should be the same except for one method, the one that retrieves the element at a given index. If all other methods depend on this index method, then we are done.

The problem is that at the moment, many methods touch the underlying vector manually instead of using the index method. We need to fix this.

Makes sense?

[Ambrevar]

Friendly ping! ;)

[solbloch]

Working on this again; was busy with finals at university!

[Ambrevar]

Great, thanks!

[Ambrevar]

Hi again! Did you find time to make progress on this? Cheers!

[solbloch]

I finished awhile ago, but should probably test to make sure it all works properly.

[Ambrevar]

Great! Looks good, almost ready to be merged. My main pick is that we can generalize the fifo-index and lifo-index functions and remove the other duplicate methods. What do you think?

[Ambrevar]

It would be great to add tests, but since there were none before and your changes don't break backward compatibility, it can always be added later.

[Ambrevar]

I've pushed your changes after squashing them in f4fb24a4be6737179afa7e6c4fc3ed4e70a38a07.

I've fixed a couple of things afterwards:

• %index now wraps over the size, not the total-size to avoid indexing elements outside of the buffer-start - buffer-end range.
• I've simplified delete-item-at which now accepts only one index, like item-at.

[Ambrevar]

Thanks for your patience, we've finally made it! :)