Is there a purely functional implementation for a Bounded Queue with peek() in O(1)?

user_816777 0
Viewed 1735

I want to maintain an immutable bounded FIFO queue from which I can remove the oldest values after a certain time. In Scala, the immutable.Queue works well for size-bounded queues (.size seems to be O(N) since it's internally based on List, but I can maintain the size separately), but there seems to be no cheap way to access the head element to test the age of the oldest value with anything cheaper than O(N), so I cannot test the expiration state of the oldest entry. Any pointers to a purely functional (immutable) implementation?

queue scala functional-programming
4 Answers

If you do are looking for a double-ended queue (deque), Scala 1.13 (June 2019, eight years later) now have ArrayDeque

An implementation of a double-ended queue that internally uses a resizable circular buffer.

Append, prepend, removeFirst, removeLast and random-access (indexed-lookup and indexed-replacement) take amortized constant time.

In general, removals and insertions at i-th index are O(min(i, n-i)) and thus insertions and removals from end/beginning are fast.

This comes from scala/collection-strawman PR 490, merged to Scala in commit c0129af.

VonC_63090
Related