## Sliding Window functional data structure

2012-08-31 04:45:27 GMT

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.(Continue reading)