Did you know ... Search Documentation:
Pack rtp_qsndqs -- prolog/rtp_dqs.pl
PublicShow source

Offers a Prolog implementation of double-ended queues (deques) 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, +DQ:deque means that DQ is an input argument and must be sufficiently instantiated, that is, it is a valid deque representing term as produced by a deque 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_qs.pl somehow doesn't work.
 reverse_deque(+DQ:deque, -DQ_rev:deque) is det
Reverse a deque.
 empty_deque(?DQ:deque) is semidet
Holds of the empty deque.
 push_deque(?El, +DQ_old:deque, -DQ_new:deque) is det
Adds El to the front of DQ_old to give DQ_new.
 inject_deque(?El, +DQ_old:deque, -DQ_new:deque) is det
Adds El to the back of DQ_old to give DQ_new.
 pop_deque(+DQ_old:deque, ?El, -DQ_new:deque) is semidet
Removes ?El from the front of DQ_old to give DQ_new.

May fail if ?El cannot be unified with the front element of DQ_old or if DQ_old is empty.

 eject_deque(+DQ_old:deque, ?El, -DQ_new:deque) is semidet
Removes ?El from the back of DQ_old to give DQ_new.

May fail if ?El cannot be unified with the rear element of DQ_old or if DQ_old is empty.

 pushlist_deque(+Els:list, +DQ_old:deque, -DQ_new:deque) is det
Pushes elements of Els onto DQ_old to give DQ_new.
 injectlist_deque(+Els:list, +DQ_old:deque, -DQ_new:deque) is det
Injects elements of Els into DQ_old to give DQ_new.
 poplist_deque(+DQ_old:deque, ?Els:list, -DQ_new:deque) is nondet
Pops elements from DQ_old onto Els to give DQ_new. See pop_deque/3.

Gives a.o. quick (and dirty?) ways of implementing deque-to-list ( poplist_deque(DQ_old,Els,DQ_new), empty(DQ_new) ) and `take N' ( length(N,Els), poplist(DQ_old,Els,DQ_new) ).

 ejectlist_deque(+DQ_old:deque, ?Els:list, -DQ_new:deque) is nondet
Ejects elements from DQ_old onto Els to give DQ_new. See eject_deque/3 and usage hints at poplist_deque/3.