[net.lang] C++ help : my solution and thanks

cs161@sdcsvax.UUCP (Grader for 161) (12/10/85)

Earlier I posted a article asking for help with C++.  Thanks for all
the replies.  I am sorry about some of the bugs I introduced when copying
the sample program.  I am posting my solution to the problem which keeps
internal details hidden (binomial queues could be used without the user 
knowing it!).  I can do this now that the assignment is finished and students
can't copy it from the net.

Class object is used since this was for an assignment.  It
contains virtual functions for keys, ranks, etc.  It could have just
as easily used ``void *'', which is easier to use, but gets rid of
useful typechecking.  Of course, a subclass can also be written solving
this, but...

Thanks to all and to all a good night.

Darin Johnson
sdcsvax!beowulf!wbreader

--------------------------------------------------------------------------

/*----------------------------------------------------------------------
 * PRQ.H:This is the header file that the user of the abstract
 * data type, priority queues, has access to, when he is writing his
 * program. A user may refer to the manual page for detailed information.
 *----------------------------------------------------------------------*/
extern class object;	/* to be defined by user */
extern class p_node;	/* defined only be implementation */

class Pqueue {
	p_node *head;
public:
	Pqueue();
	void insert(object*, double);
	object *fetch();
};

--------------------------------------------------------------------

/*---------------------------------------------------------------------
 * PRQ.C:Contains the library files for the abstract data type, priority
 * queues.This is the implementor module.
 *---------------------------------------------------------------------*/
#include <stdio.h>
#include "prq.h"

/** definition of p_node declared in prq.h **/
struct p_node {
    double   rank; 
    struct p_node *left;
    struct p_node *right;
    object* data;
    p_node(object *, double); 
};

/* structure for external node */
/* is there an elegant way to do this making sentinel a pointer? */
static p_node sentinel = {
    -1e+100,
    (&sentinel),
    (&sentinel),
    NULL
};

p_node.p_node() {...}

/*The constructor "Pqueue()" initializes the queue to be empty
 * and the head to point to it. */
Pqueue.Pqueue() {
	head = (& sentinel);
}

/* The function "swap()" takes as parameters two nodes representing
 * subtrees, and swaps them (what they are pointing to).
 * Could be made as a macro or inline function! */
void swap (p_node **p1, p_node **p2)
{
    p_node *temp;
    temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

/* The function "merge()" takes as parameters two nodes representing
 * subtrees and merges them, returning a single tree where heap ordering
 * of the tree is still preserved.
 */
p_node *merge (p_node *p1, p_node *p2, double sign)
{
    /*swap if heap is not preserved*/
    if ( p1 -> rank < p2 -> rank)	
	swap (&p1, &p2);

    if (p2 != &sentinel) {
	p1 -> right = merge (p1 -> right, p2, sign);	
	swap (&p1 -> left, &p1 -> right);
    }
    return (p1);
}

/* The function "Pqueue.insert()" takes as an object associated with the 
 * key to be inserted, and it's rank.
 * It inserts the key into the queue (self adjusting heap) preserving the 
 * heap condition.
 */
void Pqueue.insert (object *prq_o, double rank)
{
    p_node *temp;
    temp = new p_node(prq_o, rank);
    head = merge (head, temp, sign);
}

 object* Pqueue.fetch ()
{
    object* data;
    p_node *temp;
    data = head -> data;
    if (head == (& sentinel))
	return (data);
    temp = head;
    head = merge (temp -> left, temp -> right, sign);
    delete temp;
    return (data);
}