PreviousUpNext

15.3.426  src/lib/src/queue.api

## 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.pkg

api 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.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext