CS 136 Assignment 6

Due Wednesday, Oct. 24 at 11:59 am sharp. Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp. This assignment will involve the construction and use of mutable data structures in Scheme and C.

Assignment 6 Problem 1a. 5 marks. File: pointer.rkt

For this problem, you are to create and print the following linked structure in Scheme.

You must use the structure node provided by the module pointerplay.rkt, whose interface is shown below. You must print x, y and z in turn using the provided function pprint.

   ;; Provides:
   ;;
   ;; (define-struct node (data left right) #:mutable)
   ;; All operations on mutable Binary Search Tree node
   ;;
   ;; (pprint label x)
   ;; Prints a memory model rendering of x
   ;; x must be a node
   ;; Printing is incremental -- only prints nodes
   ;; that have not been printed since last (preset)
   ;;
   ;; (preset)
   ;; Resets pprint function

For example, the structure

is created and printed by the following program:

   #lang racket
   (require "pointerplay.rkt")
   (define x (make-node 123 empty empty))
   (define y (make-node 123 empty empty))
   (pprint 'x x)
   (pprint 'y y)

The output from the program -- the memory model rendering -- is:

   #1:	123	#null	#null
   x:	#1
   #2:	123	#null	#null
   y:	#2

In this representation, arrows in the box-and-pointer diagram are denoted by #n, where n is an arbitary unique number assigned to each node. The first column of the output identifies the memory location, and the following columns its contents.

As a second example, the structure

is created and printed by the following program:

   #lang racket
   (require "pointerplay.rkt")
   (define x (make-node 123 empty empty))
   (define y x)
   (pprint 'x x)
   (pprint 'y y)

The output from the program -- the memory model rendering -- is:

   #1:	123	#null	#null
   x:	#1
   y:	#1

You are to submit a program that prints the data structure corresponding to the first box-and-pointer diagram.

Assignment 6 Problem 1b. 5 marks. File: pointer.c

Solve exactly the same problem in C, using pointerplay.h and pointerplay.c. The corresponding example programs are:

   #include <stdlib.h>
   #include "pointerplay.h"

   struct node *x;
   struct node *y;
   
   int main(){
      x = malloc(sizeof(struct node));
      x->data = 123;
      x->left = NULL;
      x->right = NULL;
      y = malloc(sizeof(struct node));
      y->data = 123;
      y->left = NULL;
      y->right = NULL;
      pprint("x",x);
      pprint("y",y);
      free(x);
      free(y);
      preset();
      return 0;
   }

and

   #include <stdlib.h>
   #include "pointerplay.h"
   
   struct node *x;
   struct node *y;
      
   int  main(){
      x = malloc(sizeof(struct node));
      x->data = 123;
      x->left = NULL;
      x->right = NULL;
      y = x;
      pprint("x",x);
      pprint("y",y);
      free(x);
      preset();
      return 0;
   }

Assignment 6 Problem 2a. 5 marks. File: ilist_destructive.c

Implement an abstract data type with the following interface, which replaces icons and irest from Assignment 5 by destructive equivalents.

   // Destructive Abstract data type ilist

   struct ilist_ADT;
   typedef struct ilist_ADT *ilist;
   // prototype for secret implementation
   // do not rely on ilist being a pointer

   ilist iempty();
   //    returns an empty ilist
   
   int iempty_huh(ilist il);
   //    returns 1 (true) if il is empty
   //    returns 0 (false) if il is not empty
   
   int ifirst(ilist il);
   //    returns the first element in il
   //    il must not be empty
   
   ilist icons_destroy(int in, ilist il);
   // returns an ilist with in added as the first element of il
   // references to il cease to be valid ilists
   // all memory accessible from il is re-used or freed
   // the result must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete
   
   ilist irest_destroy(ilist il);
   // returns an ilist that is the same as il but with the first element removed   
   // references to il cease to be valid ilists
   // all memory accessible from il is re-used or freed
   // the result (if non-empty) must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete
   
   ilist icopy(ilist il);
   // returns a new copy of il that continues to be a valid
   // ilist with the same elements even when il is destroyed
   // the result must eventually be consumed by one of:
   //     icons_destroy, irest_destroy, idelete

   int ilength(ilist il);
   // computes the number of elements in il

   void idelete(ilist il);
   //    frees the storage for il
   //    all further references to il become invalid
   //    NOTE: every ilist created by icons_destroy or
   //          irest_destroy or icopy  must eventually be destroyed
   //          by being consumed by icons_destroy or
   //          irest_destroy or idelete

Create a suitable implementation in ilist_destructive.c You may not use recursion or arrays.

Assignment 6 Problem 2b. 5 marks. File ilist_destructive.rkt

Implement the equivalent module in Scheme. Your module should provide functions iempty, iempty?, icons_destroy, ifirst, irest_destroy, ilength and icopy. Note iempty? should return #t or #f rather than 1 or 0.

Assignment 6 Problem 3a. 5 marks. File: ilist_destructive.c

Assume that ilist_destructive is augmented to include

ilist iappend_destroy(ilist il1, ilist il2);
// returns an ilist consisting of the 
// elements from il1 followed by the elements from il2
// references to il1 and il2 cease to be valid ilists
// all memory accessible from il1 or il2 is re-used or freed
// the result must eventually be consumed by one of:
//     icons_destroy, irest_destroy, idelete, or
//     iappend_destroy

Add a suitable implementation to ilist_destructive.c. You may not use recursion or arrays.

Assignment 6 Problem 3b. 5 marks. File: ilist_destructive.rkt

Add iappend_destroy to your implementation of ilist_destructive.rkt. Make whatever changes are necessary, but do not change the interface (other than to add iappend_destroy).

Assignment 6 Problem 4a. 5 marks. File: ilist_destructive.c

Make whatever changes are necessary so that the running time of every operation except icopy and idelete is O(1). You may assume that the following restriction is added to the interface for iappend_destroy(il1,il2):

   il1 and il2 must not be the same ilist.

You may not use recursion or arrays.

Assignment 6 Problem 4b. 5 marks. File: ilist_destructive.rkt

Modify ilist_destructive.rkt so that the running time of every operation except icopy is O(1). You may assume that the following restriction is added to the interface for (iappend_destroy il1 il2):

   il1 and il2 must not be the same ilist.