On Thu, Jan 14, 2016 at 7:13 PM, Kevin Wortman <xxxxxx@gmail.com> wrote:

I might be missing something, but I think the trivial reversal algorithm actually takes O(n) time: while the input deque is non-empty, remove an element from its front and add that element to the front of a new output deque. There are n elements so this takes O(n) time. Are you thinking of something different?

Yes. Any plausible implementation that meets the requirements has a representation that is symmetric with respect to "front" and "back". Ie. if there is a lazy-sequence or stream for the front, there's one just like it on the back.

The reversal algorithm just constructs a new ideque containing the source components flipped. There is no other work to be done.

...and even if the implementor decided NOT to do this, one could merely wrap ideque with another abstraction called reversible-ideque that contains an ideque and a boolean flag indicating whether the the number of reversals in the evolution of this ideque is odd. The flag then controls whether requests such as reversible-ideque-front are mapped to ideque-front or ideque-back on the contained ideque. The resulting abstraction would meet all the time complexity requirements of ideque and have O(1) reversal complexity.