Cyclic Queue Requirements and Description
Good day, Assume the following requirements from a container: - O(logn) find operation - O(1) random access operation - O(logn) insert, O(logn) delete of a block of SEVERAL elements at a random position in the container This container can be described as a cyclic queue - a queue that you push items at its back and remove items from its front, but retaining the ability to randomly access any element in the container according to its index. The cyclic nature of the queue is in that if gaps are created due to element removal, then the inserts will first attempt filling those gaps (and expanding the queue IN THE MIDDLE if necessary) prior to moving to the back of the queue, enlarging it and copying the elements. The following 'diagram' demonstrates the idea: x x x x x x x x x x x x x x x x x x x (1) (2) (3) (1) - elements are normally removed from here. (2) - a gap that was created due to removal of two elements from the middle of the container. (3) - elements are normally inserted here, unless there are gaps in the container. Now if we want to insert two elements, we can just put them instead of (2) and we're done. But what if we want three? The requirement is to expand the queue to fill the gap and make room for the elements - i.e. insert at (2) but make room, at (2), for another element. I hope the requirements are clear :) Anyhow, I've had an idea of implementing this as a linked list of blocks, each being moved to the free pool when fully deallocated and pushed at the end of the queue from the free pool if all end blocks are full, if needed. Is there any interest in this sort of container? Is there any existing / pending library in Boost or elsewhere that provides an implementation of a similar concept? Have you any ideas that can make the whole problem go away by using some combination of the standard containers? Thanks in advance to all, Sasha Goldshtein.
"Sasha Goldshtein" <goldshtn@netvision.net.il> wrote
This container can be described as a cyclic queue - [snip]
You may take look on circular_buffer_v35.zip in http://groups.yahoo.com/group/boost/files/ It is (hopefully) scheduled for review. /Pavel
At Tuesday 2004-02-17 10:59, you wrote:
Good day,
Assume the following requirements from a container: - O(logn) find operation - O(1) random access operation - O(logn) insert, O(logn) delete of a block of SEVERAL elements at a random position in the container
This container can be described as a cyclic queue - a queue that you push items at its back and remove items from its front, but retaining the ability to randomly access any element in the container according to its index. The cyclic nature of the queue is in that if gaps are created due to element removal, then the inserts will first attempt filling those gaps (and expanding the queue IN THE MIDDLE if necessary) prior to moving to the back of the queue, enlarging it and copying the elements.
The following 'diagram' demonstrates the idea:
x x x x x x x x x x x x x x x x x x x (1) (2) (3)
(1) - elements are normally removed from here. (2) - a gap that was created due to removal of two elements from the middle of the container. (3) - elements are normally inserted here, unless there are gaps in the container.
Now if we want to insert two elements, we can just put them instead of (2) and we're done. But what if we want three? The requirement is to expand the queue to fill the gap and make room for the elements - i.e. insert at (2) but make room, at (2), for another element.
I hope the requirements are clear :)
this sounds like a solution in search of a problem. I like the O(logn) find, insert, and delete. I'm baffled by the insert "either at the end if no deletions have occurred recently, or somewhere in the middle". (what problem generates this requirement) Do the indexes for an element AFTER (2) above change when the delete occurs? how about pointers, references and iterators? what happens to indexes, iterators, references after inserting 2 things at (2)? inserting 3 things?
Anyhow, I've had an idea of implementing this as a linked list of blocks, each being moved to the free pool when fully deallocated and pushed at the end of the queue from the free pool if all end blocks are full, if needed.
Is there any interest in this sort of container? Is there any existing / pending library in Boost or elsewhere that provides an implementation of a similar concept? Have you any ideas that can make the whole problem go away by using some combination of the standard containers?
Thanks in advance to all, Sasha Goldshtein.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: "There oughta be a law"
this sounds like a solution in search of a problem. I like the O(logn) find, insert, and delete. I'm baffled by the insert "either at the end if no deletions have occurred recently, or somewhere in the middle". (what problem generates this requirement)
My intent wasn't clear. What I meant is that if there is a gap in the middle, then it should be filled (there may be some consideration of resizing efficiency, or none) - it's not a question of whether or not a delete has "ever" occurred. So if there is no gap - then the insert is at the end, and if there is a gap - it should be filled.
Do the indexes for an element AFTER (2) above change when the delete occurs? how about pointers, references and iterators?
The indexes DO change, but iterators and references should probably remain unchanged... I've looked at the implementation of the circular buffer that Pavel has posted a reference to - and it does not fulfill the above requirements... Thanks again for the comments.
participants (3)
-
Pavel Vozenilek -
Sasha Goldshtein -
Victor A. Wagner Jr.