Offers a Prolog implementation of queues with constant time basic
operations and full version reusability. The implementation is based
on Bouma (2012), referenced below. Time guarantees and determinism
indications apply to the cases in which the predicate signature is
respected.
In the signatures, +Q:queue means that Q is an input argument and must
be sufficiently instantiated, that is, it is a valid queue
representing term as constructed by a queue outputting predicate. Due
to the design of the datastructure, these need not be ground.
- author
- - Gerlof Bouma, Uni Gothenburg
- See also
- - Bouma, Gerlof. 2012. Real-time Persistent Queues and Deques with
Logic Variables (Declarative Pearl). In Schrijvers and Thiemann
(Eds), Functional and Logic Programming, Proceedings of the 11th
International Symposium FLOPS 2012, LNCS 7294, pp. 62-72,
Heidelberg: Springer.
- - http://spraakbanken.gu.se/personal/gerlof/home
- bug
- - Loading together with
rtp_dqs.pl
somehow doesn't work.
- empty_queue(?Q:queue) is semidet
- Holds of the empty queue.
- pop_queue(+Q_old:queue, ?El, -Q_new:queue) is semidet
- Removes ?El from the front of Q_old to give Q_new.
May fail if ?El cannot be unified with the front element of Q_old
or if Q_old is empty.
- inject_queue(?El, +Q_old:queue, -Q_new:queue) is det
- Adds El to the back of Q_old to give Q_new.
- push_queue(?El, +DQ_old:queue, -DQ_new:queue) is det
- Adds El to the front of DQ_old to give DQ_new.
( This extension of the version presented in the paper makes the
datastructure an output-restricted double-ended queue. )
- poplist_queue(+Q_old:queue, ?Els:list, -Q_new:queue) is nondet
- Pops elements from Q_old onto Els to give Q_new. See pop_queue/3.
Gives a.o. quick (and dirty?)
ways of implementing queue-to-list
( poplist_queue(Q_old,Els,Q_new), empty(Q_new)
) and `take N'
( length(N,Els), poplist(Q_old,Els,Q_new)
).
- injectlist_queue(+Els:list, +Q_old:queue, -Q_new:queue) is det
- Injects elements of Els into Q_old to give Q_new.
- pushlist_queue(+Els:list, +Q_old:queue, -Q_new:queue) is det
- Pushs elements of Els onto Q_old to give Q_new.