Factor Language Blog

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.