CMSC--202 , Section Computer Science II for Majors
Fall 1997 17 October 1997 Homework 5

Assigned: 21 October
Due Date: 30 October
Late Date: 3 November The purpose of this assignment is to give you more experience implementing and using ADTs. You will implement the fleezle ADT. The name fleezle has absolutely no meaning, it was chosen for its strange sound.

Abstract Data Type Implementation

A fleezle is a data storage structure that holds void pointers. These pointers will be pointing to some type of data. The type of a fleezle is fleezle_type. The fleezle ADT consists of the following operations. Note that any errors generated are to result in an appropriate message to stderr and termination of the program.

fleezle_type createFleezle(void)

-- create and return a new empty fleezle.

void addToFleezle(void * item, fleezle_type F)

-- add item to F.

void * getSmallest(fleezle_type F, fleezle_compare_type C)

-- return the smallest value stored in F. ``Smallest'' is determined by the comparator C. It is an error to invoke getSmallest on an empty fleezle.

BOOL isEmptyFleezle(fleezle_type F)

-- return TRUE if F does not contain any items, FALSE otherwise.

void transformFleezle(fleezle_type F,fleezle_xformer_type T)

-- replace every item in F with the result of applying T to that item. The type definition for fleezle_xformer_type is given on page .

printFleezleItem(FILE * fp, void * item, fleezle_print_type pfunc)

-- print item to fp using pfunc. The type definition for fleezle_print_type is given on page .

printFleezle(FILE * fp, fleezle_type F, fleezle_print_type pfunc)

-- print all the items in F to fp using pfunc.

Implementations and Interfaces

The interface for fleezle must match the ADT operations above. The implementation is entirely up to you. Choose an implementation that makes sense and that matches the ADT requirements. For example, since there is no maximum size on a fleezle, an array would not be a good choice.

Tasks

Here are the principle tasks you must accomplish:

1. Write an interface for fleezle. This must contain the prototypes of every ADT operation. Relevant typedefs should also be in the interface file.
2. Write an implementation for fleezle.
3. Write any auxiliary functions you may find useful. For example, write
   • the comparator int intCompare(void * I1, void * I2)
   • the transformer void * intTwoLarger(void * I)
   • the ``printer'' void intPrint(FILE * fp, void * I)
   • the ``constructor'' fleezle_type makeIntFleezle(int N) that returns a new fleezle containing N randomly-chosen integers.

4. Test your implementation for a fleezle that contains integers (the void pointers point to ints). Use the driver given on page as is. You may modify it to suit your own taste, if you wish, but it must perform the functions shown. Typical output from this driver is shown on page .

Submit your work in the usual way, using the submit command. For example, to submit the file foo.c, do:

  submit cs202_01 hw5 foo.c

You must submit all the files required to successfully compile your homework using your submitted makefile. The only constraints on file names are that the executable must be named hw5 and the makefile must be named Makefile or makefile. Otherwise, you may name your files as you wish. You will be graded on your choice of files and file names. Modularity requires that you have a separate file for interfaces (for example, fleezle.h), a similarly-named implementation file (for example, fleezle.c). The main function should be in its own file. Auxiliary functions should be logically grouped in their own file (or files) with appropriate interface files.

Type Definitions

  Here are some type definitions:

typedef void * (*fleezle_xformer_type)(void *);
typedef int (*fleezle_compare_type)(void *, void *);
typedef void (*fleezle_print_type)(FILE *, void *);

fleezle_xformer_type

A fleezle_xformer_type function performs a transforming operation. It takes a pointer to data and returns a pointer to a transformed version of the data. It does not change the original data, it returns a transformed version. For example, the function void * intTwoLarger(void *) is of type fleezle_xformer_type.

If used in the following code,

  int i = 3;
  int * ip = intTwoLarger(&i);

fleezle_compare_type

A fleezle_compare_type function compares the data pointed to. It returns a negative integer if the first datum precedes the second. It returns zero if the first and second data are equivalent. It returns a positive integer if the first datum follows the second. This is very much like the strcmp comparator to compare ``strings.'' For example, the function int intCompare(void * p1, void * p2) is of type fleezle_compare_type.

If used in the following code

  int i = 3;
  int j = 4;
  intCompare(&i, &j);

fleezle_print_type

A fleezle_print_type function prints a value to a file. For example, void intPrint(FILE * fp, void * p) is of type fleezle_print_type.

If used in the following code

  int i = 3;
  intPrint(stdout, &i);

Driver

  Here is a driver for you to use. The driver takes a command line argument that is the number of items to put into the fleezle. The fleezle holds integers. The integers are randomly generated using the rint202 function (see rint202.h in the directory ~anastasi/Public/202/Includes).

#include "fleezle.h"
#include "hw5_aux.h"
#include <stdio.h>

void main(int argc, char * argv[])
{
  fleezle_type F;
  int N;

  /* get number of entries from command line */
  /* exit with usage message if command line is not */
  /* of proper form (namely a single integer) */
  N = getCommandLineArg(argc, argv);
  
  /* construct a fleezle that holds N random integers */
  F = makeIntFleezle(N);

  printFleezle(stdout, F, intPrint);
  fprintf(stdout, "\n");

  transformFleezle(F, intTwoLarger);
  printFleezle(stdout, F, intPrint);
  fprintf(stdout, "\n");

  
  printf("Smallest is ");
  printFleezleItem(stdout, getSmallest(F, intCompare), intPrint);
  fprintf(stdout, "\n");

  /* test for error condition in getSmallest */
  F = createFleezle();  /* create empty fleezle */
  getSmallest(F, intCompare);
}

Typical Output from Driver

  Here is the output from two typical runs of the driver. Your output may differ since the integers are randomly generated.

>> hw5
Usage: hw5 <nentries>

>> hw5 4
157 629 764 451 
314 1258 1528 902 
Smallest is 314
Error: Attempt to getSmallest of empty fleezle