#include <stdio.h>
#include <stdlib.h>

#define M 10

typedef struct Node
{
	struct Node* next;
	int key;
} Node;

typedef struct Single_chain
{
	Node* first;
	Node* last;
	int size;
} Single_chain;

typedef struct Chained_hashing
{
	Single_chain* table;
} Chained_hashing;

void init_chain(Single_chain* sc);
void insert_to_chain(Single_chain* sc, int key);
void print_chain(Single_chain *sc);
int search_chain(Single_chain* sc, int key);
Node* search_chain_node(Single_chain* sl, int key);
void delete_from_chain(Single_chain* sc, int key);
void init_hashing(Chained_hashing* ch);
void insert_to_chained_hashing(Chained_hashing* ch, int key);
void delete_from_chained_hashing(Chained_hashing* ch, int key);
int search_in_chained_hashing(Chained_hashing* ch, int key);
void print_chained_hashing(Chained_hashing* ch);


int main(void)
{
	Chained_hashing ch;
    init_hashing(&ch);
    int i;
    for (i=0;i<100;i++){
        insert_to_chained_hashing(&ch, (int)rand()%100);
    }
    print_chained_hashing(&ch);

	
	return 0;
}

void init_chain(Single_chain* sc)
{
	sc->first = NULL;
	sc->last = NULL;
	sc->size = 0;
}
      
void insert_to_chain(Single_chain* sc, int key)
{
	if(sc->size == 0)
	{
		sc->first = (Node*)malloc(sizeof(Node));
		(sc->first)->key = key;
		(sc->first)->next = NULL;
		sc->last = sc->first;
     }
	else
	{
		(sc->last)->next=(Node*)malloc(sizeof(Node));
		((sc->last)->next)->key=key;
		((sc->last)->next)->next=NULL;
		sc->last=(sc->last)->next;
	}
	sc->size++;
}

void print_chain(Single_chain* sc)
{
	Node* nd;
	nd=sc->first;
	printf("List: ");
	if (sc->size>0) printf("First:%d Last:%d\t", (sc->first)->key, (sc->last)->key);
	while (nd != NULL)
	{
		printf("%d\t",nd->key);
		nd=nd->next;
	}
	printf("\n");
}

int search_chain(Single_chain* sc, int key)
{
	Node * nd;
	nd=sc->first;
	while (nd != NULL)
	{
		if(nd->key==key) 
			return 1;
		nd=nd->next;
	}
	return 0;
}

Node* search_chain_node(Single_chain* sc, int key)
{
	Node* nd;
	nd = sc->first;
	while (nd != NULL)
	{
		if(nd->key == key)
			return nd;
		nd = nd->next;
	}
	return NULL;
}

void delete_from_chain(Single_chain* sc, int key)
{
	Node* nd_prev = NULL;
	Node* nd = sc->first;
	while(nd != NULL)
	{
		if(nd->key == key)
		{
			//delete only node
			if((nd == sc->first) && (sc->first==sc->last))
				sc->first = sc->last = NULL;
			//delete first node, not only one
			else if ((nd == sc->first) && (sc->first!=sc->last))
				sc->first = (sc->first->next);
			//delete middle node
			else if (nd != sc->last)
				nd_prev->next = nd->next;
			//delete last node
			else
			{
				sc->last = nd_prev;
				(nd_prev)->next = NULL;
			}
		}
		
		(sc->size)--;
		free(nd);
		nd_prev=nd;
		nd=nd->next;
	}
}

void init_hashing(Chained_hashing* ch)
{
	int i;
	ch->table=(Single_chain*)malloc(M*sizeof(Single_chain));
	for (i=0; i<M; i++)
		init_chain(&(ch->table[i]));
}

void insert_to_chained_hashing(Chained_hashing* ch, int key)
{
	insert_to_chain(&(ch->table[key%M]), key);
}

void delete_from_chained_hashing(Chained_hashing* ch, int key)
{
	delete_from_chain(&(ch->table[key%M]), key);
} 

int search_in_chained_hashing(Chained_hashing* ch, int key)
{
	return search_chain(&(ch->table[key%M]), key);
}

void print_chained_hashing(Chained_hashing* ch)
{
	int i;
	for(i=0; i<M; i++)
	{
		printf("Pos %d \n",i);
		print_chain(&(ch->table[i]));
		printf("---------\n");
	}
}