fixd: Fix an rdeque

Description

Maintains the invariant that there is always something in two stacks used by rdeques under the hood so long as there is 2 more elements in the rdeque.

Usage

1
fixd(d, ...)

Arguments

d

rdeque to fix.

...

additional arguments to be passed to or from methods (ignored).

Details

In fact, fix will be called whenever there are fewer than 6 elements in both the front and end of the deque. Generally this method is O(N), and so a full copy is returned.

Value

fixed, "balanced" deque.

References

Okasaki, Chris. Purely Functional Data Structures. Cambridge University Press, 1999.


Questions? Problems? Suggestions? or email at ian@mutexlabs.com.

All documentation is copyright its authors; we didn't write any of that.