Dequeue protocol, and search dequeues
Tuesday, June 10, 2008
While debugging the compiler and fixing some performance regressions yesterday, I ran into a situation where I needed a data structure with efficient insertion and removal at both ends, and constant-time membership testing.
This is pretty easy to implement, by combining a double linked list with
a hashtable, however I wanted this to have the same interface as a
double linked list, so I made a new dequeues
vocabulary which
abstracts the operations on a double linked list, such as
push-front
push-back
pop-front
pop-back
Double linked lists in the dlists
vocabulary now implement this
protocol instead of exposing dlist-specific operations.
The dequeue protocol also has a dequeue-member?
generic word. This
word runs in linear time on dlists.
Search dequeues in the search-dequeues
wrap an assoc and a dequeue and
provide a sub-linear implementation of dequeue-member?
(constant time
if the assoc is a hashtable). Pushing elements adds them to both the
dequeue and assoc; the membership test is then just a call to key?
on
the assoc.