Add stack and queue implementations to storage-plus

[itsHaseebSaeed]

I was hoping cosmwasm devs can add something like this; if not, I'd love to add such a package.

Description in mind: An "append store" is a storage wrapper that guarantees constant-cost appending to and popping from a list of items in storage. This is achieved by storing each item in a separate storage entry. A unique key is reserved for storing the length of the collection so far.

[webmaster128]

I don't think this is implemented yet in a standardized way. Do I understand correctly that you are looking for a queue or stack implementation?

[itsHaseebSaeed]

Stack implementation works best for the Append store. We can also do a Queue implementation like a Queue_store

I don't think this is implemented yet in a standardized way. Do I understand correctly that you are looking for a queue or stack implementation?

[uint]

Doesn't seem like we have any overlap here with storage-plus, which deals pretty much purely with KV storage, snapshots, and deserialization convenience.

I imagine once we implement the core in cosmwasm-storage, we might add a wrapper in storage-plus (like the Item one) for easier deserialization?

[webmaster128]

After internal discussions we concluded that cosmwasm-storage is more or less deprecated and should not be enhanced anymore. Adding a stack and queue implementation to storage-plus would be nice though. Moving to the other repo ...

[itsHaseebSaeed]

That makes much more sense, tbh. Let me know what the team thinks. I'm very excited to contribute. Thanks

[chipshort]

Hi @itsHaseebSaeed
Is there any work done on the queue already? I need it for something and would like to implement it. If you want, I can also take over the stack PR you started.

[itsHaseebSaeed]

Hi @itsHaseebSaeed Is there any work done on the queue already? I need it for something and would like to implement it. If you want, I can also take over the stack PR you started.

The stack is almost ready but needs a few modifications plus the need to write documentation. Planning to complete it this weekend. Maybe check back on Sunday morning. In the meanwhile, if you see any errors feel free to comment.

[uint]

We just talked on Slack with @chipshort. Chris suggested having one double-ended queue instead of a separate queue and stack. And he suggested we could even call it a VecDeque, and keep the random access. Seems like a good idea - we have no reason for two separate implementations here AFAIK. @webmaster128 @ethanfrey what do you think?

I'm also thinking if we skip having any sort of "stack of stacks" or "StackMap" functionality now, we could:

1. Implement a simple Deque (or even VecDeque) type
2. Take time figuring out if we can somehow compose the map types we already have, like Map<_, Deque> and so on. @itsHaseebSaeed are you looking to use this in some contract of yours?

I'd rather move carefully with these complex storage types. Once we provide an implementation, it will be a bit hard to go back and change it.

[itsHaseebSaeed]

Sure I would love to work on Deque; I planned to propose stack and then deque. It all would be a little easier If I could have a list of DO and DON'T. I DM-ed you on discord. Let's talk there and make this happen. Thanks.