On Fri, Aug 31, 2012 at 05:45:27AM +0100, Richard O'Keefe wrote:
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
Any search tree implementation will do add and purge in O(log n) time.
Add's obvious, but could you explain to me about purge?
All of the explanations of search trees I'm familiar with,
if they bother to explain deletion at all, talk about how
to repair the balance of a tree after deleting
One possibility would be a random-access list
(http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5156), which is a
kind of list of trees.
Then 'add' is trivially O(1) and 'since' is trivially O(length result).
The only tricky operation is purge, which naively would be O(N), where N is
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 -
