the file coll_at.c
//////////////////
coll_at.c
///////////////////////////////////////
#include <stdlib.h> /* calloc */
#include <stdio.h> /* NULL */
#include <assert.h> /* Needed for assertions */
#include "coll_a.h" /* import the specification */
struct t_node
{
void *item;
struct t_node *left;
struct t_node *right;
} node;
struct t_collection
{
/* Note that size is not needed any longer! */
int (*ItemCmp)( void *, void * );
struct t_node *node;
};
collection ConsCollection(int max_items,
int (*ItemCmp)(void *,void *))
/* Construct a data 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 );
c = (collection)calloc( 1, sizeof(struct t_collection) );
c->node = (struct t_node *)0;
c->ItemCmp = ItemCmp;
return c;
}
static void AddToTree( struct t_node **t, struct t_node *data,
int (*ItemCmp)(void *, void *) )
{
struct t_node *base;
base = *t;
/* If it's a null tree, just add it here */
if ( base == NULL )
{
*t = data;
return;
}
else
{
if ( ItemCmp( base->item, data ) < 0 )
{
AddToTree( &(base->left), data, ItemCmp );
}
else
AddToTree( &(base->right), data, ItemCmp );
}
}
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 *data, *node_p;
assert( c != NULL );
assert( item != NULL );
/* Allocate space for a node for the data item */
data = (struct t_node *)malloc(sizeof(struct t_node));
/* Attach the item to the node */
data->item = item;
data->left = data->right = (struct t_node *)0;
node_p = c->node;
AddToTree( &node_p, data, c->ItemCmp );
c->node=node_p;
}
void DeleteFromTree( struct t_node **t, void *item )
{
struct t_node *temp, *prev, *succ;
prev=temp=*t;
void *val;
*val=(void*)item;
//val=item;
if(*t==NULL)
printf("NO NODES TO BE DELETED");
else
{
while(temp->item!=val && temp!=NULL) //define val
{
prev=temp;
if(temp->item >val)
temp=temp->left;
else
temp=temp->right;
}
if(temp==NULL)
{
printf("the value could not be found\n");
return;
}
if(temp->left!=NULL && temp->right!=NULL)
{
prev=temp;
succ=temp->right;
while(succ->left!=NULL)
{
prev=succ;
succ=succ->left;
}
temp->item=succ->item;
temp=succ;
}
if(temp->left!=NULL && temp->right==NULL)
{
if(prev->left==temp)
prev->left=temp->left;
else
prev->right=temp->left;
}
if(temp->left==NULL && temp->right!=NULL)
{
if(prev->left==temp)
prev->left=temp->right;
else
prev->right=temp->right;
}
if(temp->left==NULL && temp->right==NULL)
{
if(prev->left==temp)
prev->left=NULL;
else
prev->right=NULL;
}
/* if(temp==*root) // define root
{
if(temp->left!=NULL)
*root=temp->left;
else
*root=temp->right;
}*/
free(temp);
}
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;
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 */
node = c->node;
DeleteFromTree( &node, item );
c->node=node;
}
void *FindInTree( struct t_node *t, void *key )
{
if(t==NULL)
return;
else if(t->item==key)
return t;
else if ( ItemCmp( t->item, key ) < 0 )
return FindInTree( (t->left), key );
else
return FindInTree( (t->right), key );
}
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
*/
{
struct t_node *node;
assert( c != NULL );
assert( key != NULL );
/* Select node at head of list */
node = c->node;
return FindInTree( node, key );
}
}
void InOrderTreeTraversal(struct t_node *t, int(*private_print)(void *item))
{
if(t != NULL)
{
InOrderTreeTraversal(t->left,private_print);
private_print(t->item);
InOrderTreeTraversal(t->right, private_print);
}
}
void InOrderTraversal(collection c, int(*private_print)(void *item))
{
assert(c != NULL);
InOrderTreeTraversal(c->node,private_print);
}
9
