/* Array implementation of a Collection */

#include <stdio.h>	/* Definition of NULL */
#include <assert.h>	/* Needed for assertions */
#include "Collection.h"	/* import the specification */


/* Binary tree implementation of a collection */

struct t_node {
	void *item;
	struct t_node *left;
	struct t_node *right;
	};

typedef struct t_node *Node;

struct t_collection {
	Node root;
	int (*compar)(void *, void *);
	};

Collection ConsCollection(int max_items, int (*compar)(void *, void *) )
/* Construct a new Collection
   Pre-condition: (max_items > 0) &&
                  (item_size > 0)
   Post-condition: returns a pointer to an empty Collection
*/
	{
	Collection c;
	assert( max_items > 0 );
	assert( compar != NULL );
	c = (Collection)calloc( 1, sizeof(struct t_collection) );
	if ( c != NULL ) {
		c->root = (Node)0;
		c->compar = compar;
		}
	return c;
	}

static void DeleteTree( Node n ) {
  if ( n != NULL ) {
    DeleteTree( n->left );
    DeleteTree( n->left );
    free( n );
    }
  }

void DeleteCollection( Collection c ) {
  DeleteTree( c->root );
  free( c );
  }

/* Binary tree implementation of a collection */
static int (*IC)( void *, void *) = 0;

static void AddToTree( Node *t, Node new ) {
	Node base;
	assert( IC != NULL );
	base = *t;
	/* If it's a null tree, just add it here */
	if ( base == NULL ) {
		*t = new;
		return;
		}
	else {
		if ( IC( new->item, base->item ) < 0 ) {
			AddToTree( &(base->left), new );
			}
		else
			AddToTree( &(base->right), new );
		}
	}

void AddToCollection( Collection c, void *item ) {
	Node new, node_p;
	assert( c != NULL );
	assert( item != NULL );
	/* Allocate space for a node for the new item */
	new = (Node)malloc(sizeof(struct t_node));
	/* Attach the item to the node */
	new->item = item;
	new->left = new->right = (Node)0;
	IC = c->compar;
	AddToTree( &(c->root), new );
	}

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
*/
	{
	int i;
	assert( c != NULL );
	assert( item != NULL );
	}

void *FindInTree( Node t, void *item ) {
	/* printf("FIT t %ld l %ld r %ld\n", t, (t!=0)?t->left:0, (t!=0)?t->right:0 ); */
	if ( t == (Node)0 ) return NULL;
	switch( IC( item, t->item ) ) {
		case -1 : return FindInTree( t->left, item );	
		case 0: return t->item;
		case +1 : return FindInTree( t->right, item );
		}
	}

void *FindInCollection( Collection c, void *item ) {
/* 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
*/
	assert( c != NULL );
	assert( item != NULL );
	/* Select node at head of list */
	IC = c->compar;
	return FindInTree( c->root, item );
	}