Re: [boost] Cyclic Queue Requirements and Description

From: Victor A. Wagner Jr. (vawjr_at_[hidden])
Date: 2004-02-20 03:03:44

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"