Simple ADT Design
A double-ended queue or deque is one that has both LIFO and FIFO behaviour, ie you can add an item to the head or the tail of a list and extract an item from the head or the tail.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 |
, 1998