Consider the following interface
type Ord k => Sliding_Window k v
entries :: Sliding_Window k v -> [(k,v)]
The cost is expected to be linear in the length of
the result. The pairs are listed in increasing
order of k.
add :: Ord k => k -> v -> Sliding_Window k v -> Sliding_Window k v
precondition: all (< k) [k' | (k',_) <- entries q]
The cost should be at most O((log . length . entries) q).
post: entries (add k v q) = entries q ++ [(k,v)]
since :: Ord k => k -> Sliding_Window k v -> [(k,v)]
answers [(k',v) | (k',v) <- entries q, k' > k]
The cost should be at most O((log . length . entries) q
+ length result)
purge :: Ord k => k -> Sliding_Window k v -> Sliding_Window k v
answers q' such that entries q' = [(k',v) | (k',v) <- entries q,
k' > k]
The cost should be at most O((log . length . entries) q
+ length [k' | (k',v) <- entries q,
k' <= k])
Ignoring costs, this can obviously be done trivially using
a list of pairs. Paying some attention to costs, it can also
be done using some sort of balanced search tree. The data
structure is close to a priority queue, but subtly different.
I believe I can see how to do this in an imperative language
using a Dijkstra-style array of pairs: add is amortised O(1)
using the well known doubling strategy, thanks to the strictly
increasing key requirement; since is a binary search followed
by a segment copy; purge is a binary search followed by nilling
out the now unwanted elements. By adapting the back-to-back
pair of lists implementation of queues, we can obviously do
add in O(1) and purge in O(1+#deleted items) time in a pure
functional language.
Thing is, there's a baffling array of data structures to examine
(AVL, RB, 2-3, 2-3-4, 1-2-brother, finger ... trees) and I wondered
if anyone had any idea what would be particularly good for this
rather asymmetric problem.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
