Simple ADT Design

Taking the following specification for the Collection class, modify it to handle a deque. Note:

• There are quite a few ways that a software engineer could do this: see how many you can devise!
• A software engineer would probably try to ensure that code using the original specification continued to function correctly.

Similarly, modify the implementation to handle a deque.

/* Specification for Collection */

typedef struct t_Collection *Collection;

Collection ConsCollection( int max_items, int item_size );
/* Construct a new Collection
   Pre-condition: max_items > 0
   Post-condition: returns a pointer to an empty Collection
*/

void AddToCollection( Collection c, void *item );
/* Add an item to a Collection
   Pre-condition: (c is a Collection created by a call to
                       ConsCollection) &&
                  (existing item count < max_items) &&
                  (item != NULL)
   Post-condition: item has been added to c
*/

void DeleteFromCollection( Collection c, void *item );
/* Delete an item from a Collection
   Pre-condition: (c is a Collection created by a call to
                     ConsCollection) &&
                  (existing item count >= 1) &&
         	  (item != NULL)
   Post-condition: item has been deleted from c
*/

void *FindInCollection( Collection c, void *key );
/* Find an item in a Collection
   Pre-condition: c is a Collection created by a call to
                     ConsCollection
                  key != NULL
   Post-condition: returns an item identified by key if one
                   exists, otherwise returns NULL
*/


/* Linked list implementation of a collection */

#include 	/* calloc */
#include 	/* NULL */
#include 	/* Needed for assertions */
#include "collection.h"	/* import the specification */

extern void *ItemKey( void * );

struct t_node {
	void *item;
	struct t_node *next;
	} node;

struct t_collection {
	int size;	/* Needed by FindInCollection */
	struct t_node *node;
	};

collection ConsCollection(int max_items, int item_size )
/* Construct a new collection
   Pre-condition: (max_items > 0) && (item_size > 0)
   Post-condition: returns a pointer to an empty
collection
*/
	{
	collection c;
	/* Although redundant, this assertion should be
	   retained as it tests compliance with the formal
           specification */
 	assert( max_items > 0 );
 	assert( item_size > 0 );
	c = (collection)calloc( 1, sizeof(struct t_collection) );
	c->node = (struct t_node *)0;
	c->size = item_size;
	return c;
	}

void AddToCollection( collection c, void *item )
/* Add an item to a collection
   Pre-condition: (c is a collection created by a call to 
                ConsCollection) &&
                  (existing item count < max_items) &&
                  (item != NULL)
   Post-condition: item has been added to c
*/
	{
	struct t_node *new;
	assert( c != NULL );
	assert( item != NULL );
	/* Allocate space for a node for the new item */
	new = (struct t_node *)malloc(sizeof(struct t_node));
	/* Attach the item to the node */
	new->item = item;
	/* Make the existing list `hang' from this one */
	new->next = c->node;
	/* The new item is the new head of the list */
	c->node = new;
	assert( FindInCollection( c, ItemKey( item ) ) != NULL );
	}

void DeleteFromCollection( collection c, void *item )
/* Delete an item from a collection
   Pre-condition: (c is a collection created by a call to
                     ConsCollection) &&
                  (existing item count >= 1) &&
                  (item != NULL)
   Post-condition: item has been deleted from c
*/
	{
	struct t_node *node, *prev;
	assert( c != NULL );
        /* The requirement that the collection has at least
           one item is expressed a little differently */
	assert( c->node != NULL );
	assert( item != NULL);
	/* Select node at head of list */
	prev = node = c->node;
	/* Loop until we've reached the end of the list */
	while( node != NULL )
		{
		if ( item == node->item )
			{
			/* Found the item to be deleted,
                           re-link the list around it */
			if( node == c->node )
				/* We're deleting the head */
				c->node = node->next;
			else
				prev->next = node->next;
			/* Free the node */
			free( node );
			break;
			}
		prev = node;
		node = node->next;
		}
	}

Key terms

deque

A double-ended queue - one to which items can be added at both the head and the tail and one from which items can be extracted from the head or the tail.

Continue on to Tutorials: Part 3

Back to the Table of Contents

© John Morris, 1998