[m-rev.] For review 1/2: Beefed up the pqueue implementation.

[Paul Bone]

On Wed, Nov 27, 2013 at 04:08:22PM +1100, Julien Fischer wrote:
> On Tue, Nov 26, 2013 at 4:15 PM, Peter Wang <novalazy at gmail.com> wrote:
> 
> > On Sun, 24 Nov 2013 15:42:14 +1100, Paul Bone <paul at bone.id.au> wrote:
> > > +
> > > +:- pred pqueue.merge2(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K,
> > V)::out)
> > > +    is det.
> > > +
> > > +pqueue.merge2(empty,                   B,     B).
> > > +pqueue.merge2(A at pqueue(_, _, _, _, _), empty, A).
> > > +pqueue.merge2(pqueue(_, K, V, L, R),   !.PQ at pqueue(_, _, _, _, _),
> > !:PQ) :-
> > > +    pqueue.merge2(L, !PQ),
> > > +    pqueue.merge2(R, !PQ),
> > > +    pqueue.insert(K, V, !PQ).
> >
> > pqueue.merge2(A, B, C) :-
> >     (
> >         A = empty,
> >         C = B
> >     ;
> >         A = pqueue(_, _, _, _, _),
> >         B = empty,
> >         C = A
> >     ;
> >         A = pqueue(_, K, V, L, R),
> >         B = pqueue(_, _, _, _, _),
> >         merge2(L, B, C0),
> >         merge2(R, C0, C1),
> >         insert(K, V, C1, C)
> >     ).
> 
> 
> I suggest s/merge2/merge_2/ or s/merge2/do_merge/.  The library tends to use
> names of the form <<name>>N (without an underscore) for non-auxiliary
> predicates
> that operate on N of something (or have N accumulators).

Okay, I'll make these and Peter's suggestion, since they seem to have more
votes.

Personally I prefer to factor out A = pqueue(...):

pqueue.merge2(A, B, C) :-
    (
        A = empty,
        C = B
    ;
        A = pqueue(_, K, V, L, R),
        (
            B = empty,
            C = A
        ;
            B = pqueue(_, _, _, _, _),
            merge2(L, B, C0),
            merge2(R, C0, C1),
            insert(K, V, C1, C)
        )
    ).

This code makes it clear that there are two switches here.


-- 
Paul Bone
http://www.bone.id.au