Sliding window data structure

[David Hopwood]

Richard A. O'Keefe wrote:
> I've found a fairly simple data structure for sliding windows
> (indexed collections with the property that when you push a
> new value on one end an old value drops off the other)
> with the following properties:
> 
>     make_window(N, Element) -> Window
>     list_to_window(List) -> Window
>     window_to_list(Window) -> List
> 	are all O(N)
> 
>     index_window(I, Window) -> Element
>         is O(log(N))
> 
>     shift_window(New_Element, Window) -> New_Window
> 	is O(log(N)) worst case,
>     BUT is O(1) amortised.
> 
> I've measured the performance for indexing and shifting,
> and they are empirically O(log(N)) -- I haven't seen such a beautiful
> straight line in an empirical plot in a *long* time -- and O(1) as
> claimed over N = 1 to 1,000,000.
> 
> It's pretty easy to come up with a data structure which is O(1)
> amortised cost for shift_window/2; the old back-to-back pair of
> lists for queues will do it.  But that doesn't give you O(log(N))
> worst case, and it doesn't give you O(log(N)) indexing.

I think it's possible to get O(log(N)) indexing and O(1) worst-case
shifting, by using the the skew binary random access list from Chapter 9
of Chris Okasaki's "Purely Functional Data Structures" [*]. This structure
supports O(log(N)) indexing and an O(1) worst case 'head', 'cons' and
'tail'. It is not quite a sliding window, but it can be made into one
(for the shift operation, use 'cons' and drop the final digit/tree whenever
the list grows too long; this doesn't affect the bounds). But that's quite
complicated, so yes, I'd be interested in a simple way of doing a purely
functional sliding window.

[*] or section 6.4.1 of <http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf>

-- 
David Hopwood <david.nospam.hopwood@REDACTED>