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.