[m-rev.] Additions to queue.m

[Ralph Becket]

Estimated hours taken: 0.5
Branches: main

library/queue.m:
	Added to_list, put_on_front, put_list_on_front, and get_from_back.

NEWS:
	Mention the new additions.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.366
diff -u -r1.366 NEWS
--- NEWS	24 Jan 2005 22:29:30 -0000	1.366
+++ NEWS	25 Jan 2005 02:47:53 -0000
@@ -130,7 +130,12 @@
 Changes to the Mercury standard library:
 
 * We've add the function queue.from_list/1 as a synonym for
-  queue.list_to_queue/1.
+  queue.list_to_queue/1, function queue.to_list/1 (and predicate
+  queue.to_list/2) as the converse of queue.from_list/1, queue.put_on_front/2
+  (and predicate queue.put_on_front/3) to put items on to the front of a
+  queue, queue.put_list_on_front/2 (and predicate queue.put_list_on_front/3)
+  to put a list of items on to the front of a queue, and predicate
+  queue.get_from_back/3 which removes the last element from a queue.
 
 * We've added the function pqueue.from_assoc_list/1 as a synonym
   for pqueue.assoc_list_to_pqueue/1.
Index: library/queue.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/queue.m,v
retrieving revision 1.26
diff -u -r1.26 queue.m
--- library/queue.m	24 Jan 2005 23:16:38 -0000	1.26
+++ library/queue.m	25 Jan 2005 02:43:27 -0000
@@ -88,6 +88,10 @@
 	%
 :- func queue__from_list(list(T)) = queue(T).
 
+	% `queue__to_list(Queue) = List' is the inverse of queue__from_list/1.
+	%
+:- func queue__to_list(queue(T)) = list(T).
+
 	% `queue__delete_all(Queue0, Elem, Queue)' is true iff `Queue' is
 	% the same queue as `Queue0' with all occurrences of `Elem' removed
 	% from it.
@@ -95,6 +99,25 @@
 :- pred queue__delete_all(queue(T)::in, T::in, queue(T)::out) is det.
 :- func queue__delete_all(queue(T), T) = queue(T).
 
+	% `queue__put_on_front(Queue0, Elem, Queue)' pushes `Elem' on to
+	% the front of `Queue0', giving `Queue'.
+	%
+:- pred queue__put_on_front(queue(T)::in, T::in, queue(T)::out) is det.
+:- func queue__put_on_front(queue(T), T) = queue(T).
+
+	% `queue__put_list_on_front(Queue0, Elems, Queue)' pushes `Elems'
+	% on to the front of `Queue0', giving `Queue' (the Nth member
+	% of `Elems' becomes the Nth member from the front of `Queue').
+	%
+:- pred queue__put_list_on_front(queue(T)::in, list(T)::in, queue(T)::out)
+	is det.
+:- func queue__put_list_on_front(queue(T), list(T)) = queue(T).
+
+	% `queue__get_from_back(Queue0, Elem, Queue)' removes `Elem' from
+	% the back of `Queue0', giving `Queue'.
+	%
+:- pred queue__get_from_back(queue(T)::in, T::out, queue(T)::out) is semidet.
+
 %--------------------------------------------------------------------------%
 %--------------------------------------------------------------------------%
 
@@ -166,6 +189,8 @@
 
 queue__from_list(List) = [] - List.
 
+queue__to_list(On - Off) = Off ++ list__reverse(On).
+
 queue__delete_all(On0 - Off0, Elem, On - Off) :-
 	list__delete_all(On0, Elem, On1),
 	list__delete_all(Off0, Elem, Off1),
@@ -175,6 +200,45 @@
 	;
 		On = On1,
 		Off = Off1
+	).
+
+queue__put_on_front(On - Off, Elem, On - [Elem | Off]).
+
+queue__put_on_front(Queue0, Elem) = Queue :-
+	queue__put_on_front(Queue0, Elem, Queue).
+
+queue__put_list_on_front(On - Off, Elems, On - (Elems ++ Off)).
+
+queue__put_list_on_front(Queue0, Elems) = Queue :-
+	queue__put_list_on_front(Queue0, Elems, Queue).
+
+queue__get_from_back(On0 - Off0, Elem, On - Off) :-
+	(
+		% The On list is non-empty and the last element
+		% in the queue is the head of the On list.
+		%
+		On0 = [Elem | On],
+		Off = Off0
+	;
+		% The On list is empty.
+		%
+		On0 = [],
+		(
+			% The Off list contains a single element.
+			%
+			Off0 = [Elem],
+			On   = [],
+			Off  = []
+		;
+			% The Off list contains two or more elements.
+			% We split it in two and take the head of the
+			% new On list as Elem.
+			%
+			Off0 = [_, _ | _],
+			N    = list__length(Off0),
+			list__split_list(N / 2, Off0, Off, RevOn),
+			[Elem | On] = list__reverse(RevOn)
+		)
 	).
 
 %--------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------