Strictly Functional, Real-Time Deques with Catenation
Report ID: TR-584-98Author: Kaplan, Haim / Tarjan, Robert E.
Date: 1998-06-00
Pages: 37
Download Formats: |Postscript|
Abstract:
We describe an efficient purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, functional implementation of catenable deques is the tool required to add certain sophisticated programming constructs to functional programming languages. Our solution has a worst-case running time of O(1) for each push, pop, inject, eject and catenation. The best previously known solution has an O(log*k) time bound for the kth deque operation. Our solution is not only faster but simpler. A key idea used in our result is an algorithmic technique related to the redundant digital representations and to avoid carry propagation in binary counting.