[m-rev.] diff: add svstack and svpqueue to the standard library
Julien Fischer
juliensf at csse.unimelb.edu.au
Wed May 18 12:08:28 AEST 2011
Branches: main
Add the modules svstack and svpqueue to the standard library.
library/svpqueue.m:
library/svstack.m:
Add state variable friendly interfaces to stacks and pqueues.
library/pqueue.m:
Add a det version of remove/4.
Group function definitions with the clauses for the corresponding
predicates.
library/library.m:
Include the new modules.
NEWS:
Announce the above changes.
Julien.
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.570
diff -u -r1.570 NEWS
--- NEWS 10 May 2011 07:02:27 -0000 1.570
+++ NEWS 18 May 2011 02:03:51 -0000
@@ -115,6 +115,16 @@
All are synonyms for the existing empty/1 predicates in those modules.
+* We have added the predicate pqueue.det_remove/4. It is like pqueue.remove/4
+ except that it throws an exception instead of failing if the priority queue
+ is empty.
+
+* The new modules svstack and svpqueue provide state variable friendly
+ versions of predicates in the stack and pqueue modules.
+ (As with the other sv* modules these modules are intended to pave the
+ way for an eventual change of the predicate argument ordering in the
+ stack and pqueue modules.)
+
NEWS for Mercury 11.01
----------------------
Index: library/library.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/library.m,v
retrieving revision 1.129
diff -u -r1.129 library.m
--- library/library.m 9 May 2011 16:45:31 -0000 1.129
+++ library/library.m 18 May 2011 01:52:39 -0000
@@ -120,8 +120,10 @@
:- import_module sveqvclass.
:- import_module svmap.
:- import_module svmulti_map.
+:- import_module svpqueue.
:- import_module svqueue.
:- import_module svset.
+:- import_module svstack.
:- import_module svvarset.
:- import_module table_statistics.
:- import_module term.
@@ -297,8 +299,10 @@
mercury_std_library_module("sveqvclass").
mercury_std_library_module("svmap").
mercury_std_library_module("svmulti_map").
+mercury_std_library_module("svpqueue").
mercury_std_library_module("svqueue").
mercury_std_library_module("svset").
+mercury_std_library_module("svstack").
mercury_std_library_module("svvarset").
mercury_std_library_module("table_builtin").
mercury_std_library_module("table_statistics").
Index: library/pqueue.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/pqueue.m,v
retrieving revision 1.30
diff -u -r1.30 pqueue.m
--- library/pqueue.m 30 Jan 2009 03:57:05 -0000 1.30
+++ library/pqueue.m 18 May 2011 01:55:52 -0000
@@ -53,6 +53,11 @@
:- pred pqueue.remove(pqueue(K, V)::in, K::out, V::out, pqueue(K, V)::out)
is semidet.
+ % As above, but calls error/1 if the priority queue is empty.
+ %
+:- pred pqueue.det_remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
+ is det.
+
% Extract all the items from a priority queue by repeated
% removal, and place them in an association list.
%
@@ -84,6 +89,7 @@
:- import_module int.
:- import_module list.
:- import_module pair.
+:- import_module require.
%---------------------------------------------------------------------------%
@@ -93,10 +99,16 @@
%---------------------------------------------------------------------------%
+pqueue.init = PQ :-
+ pqueue.init(PQ).
+
pqueue.init(empty).
%---------------------------------------------------------------------------%
+pqueue.insert(PQ1, K, V) = PQ2 :-
+ pqueue.insert(PQ1, K, V, PQ2).
+
pqueue.insert(empty, K, V, pqueue(0, K, V, empty, empty)).
pqueue.insert(pqueue(D0, K0, V0, L0, R0), K, V, PQ) :-
D = D0 + 1,
@@ -132,6 +144,14 @@
%---------------------------------------------------------------------------%
+pqueue.det_remove(K, V, !PQ) :-
+ ( if pqueue.remove(!.PQ, K0, V0, !:PQ) then
+ K = K0,
+ V = V0
+ else
+ error("pqueue.det_remove/4: empty priority queue")
+ ).
+
pqueue.remove(pqueue(_, K, V, L0, R0), K, V, PQ) :-
pqueue.remove_2(L0, R0, PQ).
@@ -157,6 +177,9 @@
%---------------------------------------------------------------------------%
+pqueue.to_assoc_list(PQ) = AL :-
+ pqueue.to_assoc_list(PQ, AL).
+
pqueue.to_assoc_list(Q0, L) :-
( pqueue.remove(Q0, K, V, Q1) ->
pqueue.to_assoc_list(Q1, L0),
@@ -165,6 +188,9 @@
L = []
).
+pqueue.assoc_list_to_pqueue(AL) = PQ2 :-
+ pqueue.assoc_list_to_pqueue(AL, PQ2).
+
pqueue.assoc_list_to_pqueue([], Q) :-
pqueue.init(Q).
pqueue.assoc_list_to_pqueue([K - V | L], Q) :-
@@ -180,22 +206,5 @@
pqueue.length(pqueue(D, _, _, _, _)) = D + 1.
%---------------------------------------------------------------------------%
-%---------------------------------------------------------------------------%
-% Ralph Becket <rwab1 at cl.cam.ac.uk> 29/04/99
-% Functional forms added.
-
-pqueue.init = PQ :-
- pqueue.init(PQ).
-
-pqueue.insert(PQ1, K, V) = PQ2 :-
- pqueue.insert(PQ1, K, V, PQ2).
-
-pqueue.to_assoc_list(PQ) = AL :-
- pqueue.to_assoc_list(PQ, AL).
-
-pqueue.assoc_list_to_pqueue(AL) = PQ2 :-
- pqueue.assoc_list_to_pqueue(AL, PQ2).
-
-%---------------------------------------------------------------------------%
:- end_module pqueue.
%---------------------------------------------------------------------------%
Index: library/svpqueue.m
===================================================================
RCS file: library/svpqueue.m
diff -N library/svpqueue.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ library/svpqueue.m 18 May 2011 01:52:04 -0000
@@ -0,0 +1,54 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+%
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+%
+% File: svpqueue.m.
+% Main author: conway.
+% Stability: high.
+%
+% This file provides an interface to the 'pqueue' ADT that is conducive to the
+% use of state variable notation. The predicates here do the same thing as
+% their counterparts in the pqueue module; the only difference is the order
+% of the arguments.
+%
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- module svpqueue.
+:- interface.
+
+:- import_module pqueue.
+
+%---------------------------------------------------------------------------%
+
+ % Insert a value V with key K into a priority queue
+ % and return the new priority queue.
+ %
+:- pred svpqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
+ is det.
+
+ % Remove the smallest item from the priority queue.
+ % Fails if the priority queue is empty.
+ %
+:- pred svpqueue.remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
+ is semidet.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+svpqueue.insert(K, V, !PQ) :-
+ pqueue.insert(!.PQ, K, V, !:PQ).
+
+svpqueue.remove(K, V, !PQ) :-
+ pqueue.remove(!.PQ, K, V, !:PQ).
+
+%---------------------------------------------------------------------------%
+:- end_module svpqueue.
+%---------------------------------------------------------------------------%
Index: library/svstack.m
===================================================================
RCS file: library/svstack.m
diff -N library/svstack.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ library/svstack.m 18 May 2011 01:46:00 -0000
@@ -0,0 +1,72 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+% Copyright (C) 2011 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+%
+% File: stack.m.
+% Main author: fjh.
+% Stability: high.
+%
+% This file provides an interface to the 'stack' ADT that is conducive to the
+% use of state variable notation. The predicates here do the same thing as
+% their counterparts in the stack module; the only difference is the order of
+% the arguments.
+%
+%--------------------------------------------------------------------------%
+
+:- module svstack.
+:- interface.
+
+:- import_module list.
+:- import_module stack.
+
+%--------------------------------------------------------------------------%
+
+ % `svstack.push(Elem, Stack0, Stack)' is true iff `Stack' is
+ % the stack which results from pushing `Elem' onto the top
+ % of `Stack0'.
+ %
+:- pred svstack.push(T::in, stack(T)::in, stack(T)::out) is det.
+
+ % `svstack.push_list(Elems, Stack0, Stack)' is true iff `Stack'
+ % is the stack which results from pushing the elements of the
+ % list `Elems' onto the top of `Stack0'.
+ %
+:- pred svstack.push_list(list(T)::in, stack(T)::in, stack(T)::out) is det.
+
+ % `svstack.pop(Elem, Stack0, Stack)' is true iff `Stack0' is
+ % a non-empty stack whose top element is `Elem', and `Stack'
+ % the stack which results from popping `Elem' off `Stack0'.
+ %
+:- pred svstack.pop(T::out, stack(T)::in, stack(T)::out) is semidet.
+
+ % `svstack.det_pop' is like `svstack.pop' except that it will
+ % call error/1 rather than failing if given an empty stack.
+ %
+:- pred svstack.det_pop(T::out, stack(T)::in, stack(T)::out) is det.
+
+%--------------------------------------------------------------------------%
+%--------------------------------------------------------------------------%
+
+:- implementation.
+
+%--------------------------------------------------------------------------%
+
+svstack.push(E, !S) :-
+ stack.push(!.S, E, !:S).
+
+svstack.push_list(Es, !S) :-
+ stack.push_list(!.S, Es, !:S).
+
+svstack.pop(E, !S) :-
+ stack.pop(!.S, E, !:S).
+
+svstack.det_pop(E, !S) :-
+ stack.det_pop(!.S, E, !:S).
+
+%--------------------------------------------------------------------------%
+:- end_module svstack.
+%--------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list