main.c
Code:
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "coll_a.h" /* import the specification */
int (*private_print)(void *item);
int (*ItemCmp)(void *a, void *b);
int main();
{
collection myCollection;
int max_items;
FILE *f1;
int i;
int j;
j=100000000;
int intData[1000];
f1=fopen("out3.txt","wt");
/* Generating 1000 integers from 100,000,001 to 100,001,000 */
for (i =0; i <1000; i++)
{
intData[i] = ++j;
}
printf("Testing Part A....\n\n");
max_items = 1000;
j = 0;
myCollection = ConsCollection(max_items,ItemCmp);
printf("adding 500 items\n");
for (i = 0; i <500; i++)
{
AddToCollection(myCollection, (void *)&intData[j ++]);
}
printf("deleting 400 items\n");
for (i = 0; i <400; i++)
{
DeleteFromCollection(myCollection, (void *)&intData[--j]);
}
printf("adding the rest of 500 items\n");
j+=400;
for (i = 0; i <500; i++)
{
AddToCollection(myCollection, (void *)&intData[++j]);
}
for (i=0;i <100;i++)
{
if((intData[i]%2)!=0)
{
DeleteFromCollection(myCollection, (void *)&intData[i]);
}
}
for (i=500;i<1000;i++)
{
if((intData[i]%2)!=0)
{
DeleteFromCollection(myCollection, (void *)&intData[i]);
}
}
InOrderTraversal(c,private_print);
}
int ItemCmp(void *a, void *b)
{
long *d1,*d2;
*d1=(long *)a;
*d2=(long *)b;
if(*d1>*d2)
return -1;
else if(*d1<*d2)
return 1;
else
return 0;
}
int private_print(void *item)
{ long *t;
*t=(long *)item;
if(t!=NULL)
{printf("%d",*t );
fprintf (f1, "\n%d",*t);
}
else
{
return 0;
}
}
coll_at.c
Code:
#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;
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);
}
coll_a.h
Code:
/* Specification for collection */
typedef struct t_collection *collection;
collection ConsCollection( int max_items,
int (*ItemCmp)(void *, void *) );
/* 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
*/
void InOrderTraversal(collection c, int(*private_print)(void *item))
the compile time errors which I am unable to solve
ont> gcc -c main.c coll_at.c
main.c: In function `InOrderTraversal':
main.c:15: error: old-style parameter declarations in prototyped function definition
main.c:34: error: `ItemCmp' undeclared (first use in this function)
main.c:34: error: (Each undeclared identifier is reported only once
main.c:34: error: for each function it appears in.)
main.c: In function `ItemCmp':
main.c:73: warning: assignment makes integer from pointer without a cast
main.c:74: warning: assignment makes integer from pointer without a cast
main.c: In function `private_print':
main.c:85: warning: assignment makes integer from pointer without a cast
main.c:88: error: `f1' undeclared (first use in this function)
main.c:93: error: syntax error at end of input
coll_at.c: In function `InOrderTraversal':
coll_at.c:13: warning: structure defined inside parms
coll_at.c:20: warning: structure defined inside parms
coll_at.c:20: warning: empty declaration
coll_at.c:29: error: syntax error before '{' token
coll_at.c:92: error: syntax error before '*' token