## queue.api
#
# Immutable, fully-persistent queues.
#
# For mutable queues see:
#
# src/lib/src/rw-queue.api#
# CrT notes to self: XXX SUCKO FIXME
# o Exposing the QUEUE implementation sucks because it prevents
# client code substituting other implementations like Michele Bini's (below).
#
# o But the threadkit code assumes access to the implementation for inlining speed.
# The near-term solution may be to have one implementation but export it via two apis,
# a standard implementation-agnostic queue.api and a more transparent threadkit-queue.api
# (Obviously, better cross-package inlining support would be a nicer longer-term solution!)
#
# o It is about time to write a queue-unit-test.pkg.
#
# o Maybe 'empty' *is* better than 'empty_queue' because we may want to present
# implementations under both queue.api and deque.api apis in the long run?
# But then Queue and queue_is_empty and such should be renamed too. Probably
# better to just rename as needed.
#
# o The queue.pkg implemention has an O(N) worst-case pull time, which sucks.
#
# o Michele Bini has a nice finger-tree implementation with an O(log(N)) worst-case time:
# Her post on it contains additional info:
#
# I have written an implementation of deques for Mythryl using finger
# trees (O(1) amortized time complexity, O(log n) worst case)
#
# This is similar to Haskell's deques implementation, except that 2-3
# concatenation trees have been replaced with much simpler symmetric
# concatenation binary trees.
#
# https://bitbucket.org/rev22/finger-deques/src/master/finger-deque.pkg
#
# o There is also Chris Osaki's realtime queue implementation on page 43 of
#
# http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
#
# [LATER:]
# From: Michele Bini <michele.bini@gmail.com>
# Subject: Re: FYI: Real-time queues
# To: Cynbe ru Taren <cynbe@mythryl.org>
# Date: Mon, 9 Apr 2012 01:23:45 +0200
#
# Hello Cynbe,
#
# I've now posted a Mythryl translation of Okasaki's code
#
# https://bitbucket.org/rev22/hard-real-time-queues
#
# The average execution speed was measured to be about 6-10 times that
# of my finger-based deques, on queues with sizes in the order of one
# million of elements.
#
# Michele
# Compiled by:
# src/lib/std/standard.lib# See also:
# src/lib/src/bounded-queue.api# This api is implemented in:
#
# src/lib/src/queue.pkgapi Queue {
#
Queue(X) = QUEUE { front: List(X), # No harm in publishing the structure -- it is not going to change.
back: List(X)
};
empty_queue: Queue(X); # An empty queue, to save clients from constantly recreating QUEUE { front => [], back => [] };
queue_is_empty: Queue(X) -> Bool;
put_on_back_of_queue: (Queue(X), X) -> Queue(X); # Normal way of adding an item.
push: (Queue(X), X) -> Queue(X); # Synonym for previous.
take_from_front_of_queue: Queue(X) -> (Queue(X), Null_Or(X)); # Normal way of removing an item.
pull: Queue(X) -> (Queue(X), Null_Or(X)); # Synonym for previous.
put_on_front_of_queue: (Queue(X), X) -> Queue(X); # Bass-ackwards way of adding an item.
unpull: (Queue(X), X) -> Queue(X); # Synonym for previous.
take_from_back_of_queue: Queue(X) -> (Queue(X), Null_Or(X)); # Bass-ackwards way of removing an item.
unpush: Queue(X) -> (Queue(X), Null_Or(X)); # Synonym for previous.
to_list: Queue(X) -> List(X);
from_list: List(X) -> Queue(X);
unpull': (Queue(X), List(X)) -> Queue(X);
push': (Queue(X), List(X)) -> Queue(X);
length: Queue(X) -> Int;
}; # api Queue
## COPYRIGHT (c) 1993 by AT&T Bell Laboratories. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.