C/C++ code for persistent dynamic sets.

Here is the main program to test your code for PersistentTreeInsert:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "persistent.h"

/*  Given a persistent dynamic set t and a new value v to insert,     */
/*  returns a persistent dynamic set obtained from t by inserting v.  */

tree PersistentTreeInsert (tree, int);

tree PersistentTreeInsert (tree t, int v) {
    /*  Your code goes here.  */
}

void InorderTreeWalk (tree);

void InorderTreeWalk (tree x) {
    if (! Nil (x)) {
        InorderTreeWalk (Left(x));
        printf ("%d\n", Key(x)); /* or whatever */
        InorderTreeWalk (Right(x));
    }
}

void main(void)
{
    tree t1, t2, t3;
    
    t1 = PersistentTreeInsert (NIL, 1);
    t1 = PersistentTreeInsert (t1, 2);
    t1 = PersistentTreeInsert (t1, 3);
    t1 = PersistentTreeInsert (t1, 4);
    t1 = PersistentTreeInsert (t1, 5);
    t1 = PersistentTreeInsert (t1, 6);
    t1 = PersistentTreeInsert (t1, 7);
    t1 = PersistentTreeInsert (t1, 8);
    t1 = PersistentTreeInsert (t1, 9);
    t1 = PersistentTreeInsert (t1, 10);
    
    t2 = PersistentTreeInsert (NIL, 4);
    t2 = PersistentTreeInsert (t2, 1);
    t2 = PersistentTreeInsert (t2, 6);
    t2 = PersistentTreeInsert (t2, 5);
    t2 = PersistentTreeInsert (t2, 9);
    t2 = PersistentTreeInsert (t2, 8);
    t2 = PersistentTreeInsert (t2, 10);
    t2 = PersistentTreeInsert (t2, 3);
    t2 = PersistentTreeInsert (t2, 2);
    t2 = PersistentTreeInsert (t2, 7);
    
    t3 = PersistentTreeInsert (NIL, 87);
    t3 = PersistentTreeInsert (t3, 91);
    t3 = PersistentTreeInsert (t3, 55);
    t3 = PersistentTreeInsert (t3, 101);
    t3 = PersistentTreeInsert (t3, 44);
    
    /*  Print out all three trees in sorted order.  */
    
    InorderTreeWalk (t1);
    InorderTreeWalk (t2);
    InorderTreeWalk (t3);
}

Here is persistent.h:

/******************************************************************************
*
*       Persistent dynamic sets.
*
******************************************************************************/

/******************************************************************************
*
*       Private.
*       No client should depend on this part.
*
******************************************************************************/

typedef int tree;

/******************************************************************************
*
*       Public.
*       This is the abstract data type that clients can depend on.
*
******************************************************************************/

extern tree NIL;
extern tree MakeTree (int, tree, tree);
extern int Nil (tree);
extern int Key (tree);
extern tree Left (tree);
extern tree Right (tree);

Here is one particular implementation of persistent dynamic sets. No client should depend on any of this code. It's probably not a good idea even to look at this code until you've completed Problem 14-1.

#include 
#include 
#include "persistent.h"

/******************************************************************************
*
*       Implementation of persistent dynamic sets.
*       Everything in this file is private.
*
******************************************************************************/

#define nodesize 3
#define offset_key 1
#define offset_left 2
#define offset_right 0
#define disguise 8421
#define garbage -7
#define heapsize 5000

int heap[heapsize];

int avail = 0;

tree NIL = -17;

tree MakeTree (int z, tree t1, tree t2) {
    tree t = avail;
    avail = avail + nodesize;
    if (avail > heapsize) {
        fprintf (stderr, "Dynamic set overflow!\nGoing down in flames!!!\n");
        exit(1);
    }
    else {
        heap[t+offset_key] = z;
        heap[t+offset_left] = t1;
        heap[t+offset_right] = t2;
        return t + disguise;
    }
}

int Nil (tree t) {
    return (t == NIL) ? 1 : 0;
}

int Fetch (tree, int);

int Fetch (tree t0, int o) {
    char reply;
    tree t = t0 - disguise;
    if ((0 <= t) && (t < heapsize))
        return heap[t + o];
    else {
        fprintf (stderr, "Sorry, you have a bug in your program.\n");
        fprintf (stderr, "Garbage in, garbage out.\n");
        fprintf (stderr, "Shall I erase your hard disk (y/n)? ");
        scanf ("%c", &reply);
        if (reply == 'y')
            fprintf (stderr,
                     "You can't rely on a buggy program"
                     " to erase your disk!!!\n");
        exit(1);
    }
}

int Key (tree t) {
    return Fetch (t, offset_key);
}

tree Left (tree t) {
    return Fetch (t, offset_left);
}

tree Right (tree t) {
    return Fetch (t, offset_right);
}