Doubly-linked Lists and Queues
Factor has had doubly-linked lists for years now, but they were not well-documented or polished. Now, they're documented and have replaced the queues library.
An example of a dlist usage:
<dlist> "red" over push-front "blue" over push-front dup pop-back .
You can add/remove nodes of a dlist with
delete-node, and search with
Finding the length of a dlist is O(1) since it stores the length as
dlist-length, a tuple slot.
Heaps have been updated to allow for
<max-heap>data structures. Adding elements to a heap is achieved with
heap-push ( value key heap -- ), while popping elements is
heap-pop ( heap -- value key ).
Factor's green threads implementation had been using a hack for the sleep-queue: each time a new entry was added it would modify a non-growable array, which would then be sorted by the smallest timeout. Adding a sequence of sleep continuations would take O(n^2 log n) time! Running
10000 [ [ 100 sleep ] in-thread ] timesshould spawn 10000 threads and sleep for 100 ms in each one, and with the old sleep-queue implementation it takes over a minute on my Macbook. Now it's just O(n log n), which takes a second or two.