No subject

[Andrew Bromage]

G'day all.

Could someone review this?  Thnaks.

Cheers,
Andrew Bromage


Estimated hours taken: 0.2

library/queue.m:
	Fix an inefficiency where in some circumstances, queue__head
	could take O(n) time where n is the number of elements in the
	queue.  The fix is to impose (and maintain!) an extra
	constraint on the queue data structure which guarantess that
	the bad case never turns up.


Index: queue.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/queue.m,v
retrieving revision 1.15
diff -u -r1.15 queue.m
--- queue.m	1997/07/27 15:07:04	1.15
+++ queue.m	1997/10/14 06:58:34
@@ -95,6 +95,10 @@
 
 :- import_module list, std_util, int.
 
+% This implementation is in terms of a pair of lists.  We impose the
+% extra constraint that the `off' list is empty if and only if the queue
+% is empty.
+
 :- type queue(T) == pair(list(T)).
 
 queue__init([] - []).
@@ -106,37 +110,37 @@
 	list__append(Off1, On1R, Q1),
 	Q0 = Q1.
 
-queue__is_empty([] - []).
+queue__is_empty(_ - []).
 
 queue__is_full(_) :-
 	semidet_fail.
 
-queue__put(On - Off, Elem, [Elem | On] - Off).
+queue__put(On0 - Off0, Elem, On - Off) :-
+	( Off0 = [] ->
+		On = On0,
+		Off = [Elem]
+	;
+		On = [Elem | On0],
+		Off = Off0
+	).
+
+:- queue__put(_, X, _) when X.	% NU-Prolog indexing
 
 queue__put_list(Q0, [], Q0).
 queue__put_list(Q0, [X | Xs], Q1) :-
 	queue__put(Q0, X, Q2),
 	queue__put_list(Q2, Xs, Q1).
 
-queue__first(On - Off, Elem) :-
-	(	Off = [Elem | _]
-	;	Off = [],
-		% XXX efficiency could be improved
-		list__reverse(On, NewOff),
-		NewOff = [Elem | _]
-	).
-
-queue__get(On0 - Off0, Elem, On - Off) :-
-	queue__get_2(On0, Off0, Elem, On, Off).
-
-:- pred queue__get_2(list(T), list(T), T, list(T), list(T)).
-:- mode queue__get_2(in, in, out, out, out) is semidet.
+queue__first(_ - [Elem | _], Elem).
 
-:- queue__get_2(_, X, _, _, _) when X.	% NU-Prolog indexing
-
-queue__get_2(On, [Elem | Off], Elem, On, Off).
-queue__get_2(On, [], Elem, [], Off) :-
-	list__reverse(On, [Elem | Off]).
+queue__get(On0 - [Elem | Off0], Elem, On - Off) :-
+	( Off0 = [] ->
+		list__reverse(On0, Off),
+		On = []
+	;
+		On = On0,
+		Off = Off0
+	).
 
 queue__length(On - Off, Length) :-
 	list__length(On, LengthOn),