/* Implementacija skupa pomocu binarnih stabala */

#include <stdlib.h>	/* zbog definicije calloc */
#include <stdio.h>	/* zbog definicije NULL */
#include <assert.h>	/* zbog definicije assert */
#include "coll_a.h"	/* ucitavanje specifikacije */


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

struct t_collection {
	/* Velicina nam vise nije neophodna! */
	int (*ItemCmp)( void *, void * );
	struct t_node *node;
	};

collection ConsCollection(int max_items,
		int (*ItemCmp)(void *,void *) )
/* Kreiraj novi skup
   Pre-uslov: (max_items > 0) && (item_size > 0)
   Post-uslov: vraca pointer na prazan skup
*/
	{
	collection c;
	/* Iako nepotrebna, ova assert provera se zadrzava
	   posto testira saglasnost sa formalnom specifikacijom */
 	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 *new,
			int (*ItemCmp)(void *, void *) )
	{
	struct t_node *base;
	base = *t;
	/* Ako je stablo prazno (NULL), kreiraj ga */
	if ( base == NULL )
		{
		*t = new;
		return;
		}
	else
		{
		if ( ItemCmp( base->item, new ) < 0 )
			{
			AddToTree( &(base->left), new, ItemCmp );
			}
		else
			AddToTree( &(base->right), new, ItemCmp );
		}
	}

void AddToCollection( collection c, void *item )
/* Dodaje objekat u skup
   Pre-uslov: (c je skup kreiran pozivom ConsCollection) &&
              (postojeci broj objekata u c < max_items) &&
              (item != NULL)
   Post-uslov: objekat je dodat u skup c
*/
	{
	struct t_node *new, *node_p;
	assert( c != NULL );
	assert( item != NULL );
	/* alociraj memoriju za novi objekat */
	new = (struct t_node *)malloc(sizeof(struct t_node));
	/* prikaci objekat na cvor */
	new->item = item;
	new->left = new->right = (struct t_node *)0;
	node_p = c->node;
	AddToTree( &node_p, new, c->ItemCmp );
	}

void DeleteFromTree( struct t_node **t, void *item )
	{

	}

void DeleteFromCollection( collection c, void *item )
/* Brise objekat iz skupa
   Pre-uslov: (c je skup kreiran pozivom ConsCollection) &&
              (postojeci broj objekata u c >= 1) &&
         	  (item != NULL)
   Post-uslov: objekat je obrisan iz c
*/
	{
	struct t_node *node;
	assert( c != NULL );
        /* Zahtev da skup sadrzi bar jedan objekat je
           izrazen malo drugacije */
	assert( c->node != NULL );
	assert( item != NULL);
	/* Izaberi cvor na pocetku liste */
	node = c->node;
	DeleteFromTree( &node, item );
	}

void *FindInTree( struct t_node *t, void *key )
	{

	}

void *FindInCollection( collection c, void *key )
/* Trazi objekat u skupu
   Pre-uslov: (c je skup kreiran pozivom ConsCollection) &&
              (key != NULL)
   Post-uslov: vraca objekat identifikovan kljucem key ako takav postoji,
               u suprotnom vraca NULL
*/
	{
	struct t_node *node;
	assert( c != NULL );
	assert( key != NULL );
	/* Izaberi cvor na pocetku liste */
	node = c->node;
	return FindInTree( node, key );
	}