Sliding window data structure

[Richard A. O'Keefe]

Not so long ago we had a thread about tuple operations,
with the motivation being sliding windows.

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.

Is this of any interest?  It does suggest to me that we don't need
fancy array operations for sliding windows.