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


#define NAME 1024
#define EMAIL 512
#define PHONE 64
#define FALSE 0
#define TRUE 1


typedef struct node {
	char *name;
	char *email;
	char *domain;
	char *phone;
	struct node *next;
	struct node *prev;
} node;


typedef struct tree {
	node *contact;
	struct tree *left;
	struct tree *right;
} tree;


// a Alan alan@gmail.com 1-2-3
// a asff afsaf@gmail.com 6-5-7
// a mmmeo didn1134@gmail.com 55-44-3



/* ================================================================================= //
//                            "a" - ADD A NEW CONTACT                                //
// ================================================================================= */


/* Receives a node and an email and adds the email domain to the node */
void  add_domain(node *contact, char email[]) {
	char aux[NAME];
	char *p = strtok(email, "@");
	strcpy(aux, strtok(NULL, ""));
	contact->domain = (char*)malloc(sizeof(aux));
	strcpy(contact->domain, aux);
}


/* Receives user input and stores it in the right parameters of the node */
void create_contact(char input[], node *contact) {
	char aux[NAME];

	strcpy(aux, strtok(input, " "));
	contact->name = (char*)malloc(sizeof(aux));
	strcpy(contact->name, aux);

	strcpy(aux, strtok(NULL, " "));
	contact->email = (char*)malloc(sizeof(aux));
	strcpy(contact->email, aux);

	strcpy(aux, strtok(NULL, " "));
	contact->phone = (char*)malloc(sizeof(aux));
	strcpy(contact->phone, aux);

	strcpy(aux, contact->email);
	add_domain(contact, aux);
}


int existing_name(tree *root, char name[], node **searched) {
	int comp;

	while (root != NULL) {
		switch (comp = strcmp(root->contact->name, name)) {

		case 0:
			*searched = root->contact;
			return TRUE;
			break;

		case -1:
			return existing_name(root->right, name, searched);
			break;

		case 1:
			return existing_name(root->left, name, searched);
			break;

		default:

			break;
		}
	}
	return FALSE;
}


tree *insert(tree *root, node *contact) {
	tree *new_root;

	if (root == NULL) {
		new_root = (tree*)malloc(sizeof(tree));
		new_root->contact = contact;
		new_root->left = NULL;
		new_root->right = NULL;
		root = new_root;
	}
	else if (strcmp(root->contact->name, contact->name) > 0)
		root->left = insert(root->left, contact);
	else
		root->right = insert(root->right, contact);

	return root;
}


/* Creates a new node, stores the contact information inside of it, links
  it to the rest of the list and returns the address of the new list */
void add_contact(node **head, node **tail, tree **root, char input[]) {
	node *new_contact = (node*)malloc(sizeof(node));
	node *temp_search;
	create_contact(input, new_contact);

	if (!existing_name(*root, new_contact->name, &temp_search)) {
		if (*head == NULL)
		{
			new_contact->next = NULL;
			new_contact->prev = NULL;
			*head = new_contact;
			*tail = new_contact;
			*root = insert(*root, new_contact);

		}
		else {
			new_contact->next = (*tail)->next;
			new_contact->prev = *tail;
			(*tail)->next = new_contact;
			*tail = new_contact;
			*root = insert(*root, new_contact);
		}
	}
	else
		printf("Nome existente.\n");
}


/* ================================================================================= //
//                      "l" - PRINT CONTACTS CHRONOLOGICALLY                         //
// ================================================================================= */


void print_contact(node *contact) {
	printf("%s %s %s\n", contact->name, contact->email, contact->phone);
}


void print_contacts(node *head) {
	node *contact = head;

	for (; contact != NULL; contact = contact->next)
		print_contact(contact);
}


/* ================================================================================= //
//                          "p" - SEARCH CONTACTS BY NAME                            //
// ================================================================================= */

void search_contact(tree *root, char name[]) {
	tree *root_copy = root;
	node *n_contact;

	if (!existing_name(root_copy, name, &n_contact)) {
		printf("Nome inexistente.\n");
		return;
	}
	print_contact(n_contact);
}


/* ================================================================================= //
//                               "r" - REMOVE CONTACT                                //
// ================================================================================= */

tree *parent(tree *root) {
	if (root == NULL || root->right == NULL)
		return root;
	else
		return parent(root->right);
}


tree *tree_remove(tree *root, char name[]) {
	tree *new_parent;
	node *removed;

	if (root == NULL)
		return root;

	else if (strcmp(root->contact->name, name) < 0)
		tree_remove(root->right, name);

	else if (strcmp(root->contact->name, name) > 0)
		tree_remove(root->left, name);

	else {
		if ((root->left != NULL) && (root->right != NULL)) {
			new_parent = parent(root->left);
			removed = root->contact;
			root->contact = new_parent->contact;
			new_parent->contact = removed;
			root->left = tree_remove(root->left, new_parent->contact->name);
		}
		else {
			if ((root->left == NULL) && (root->right == NULL))
				root = NULL;

			else if (root->left == NULL)
				root = root->right;

			else
				root = root->left;
		}
	}
	return root;
}


void remove_contact(node **head, tree **root, char name[]) {
	node *temp_prev, *temp_next, *removed;

	if (!existing_name(*root, name, &removed)) {
		printf("Nome inexistente.\n");
		return;
	}

	*root = tree_remove(*root, name);
	if (removed->prev == NULL) {
		temp_prev = *head;
		*head = (*head)->next;
		(*head)->prev = NULL;
		free(temp_prev);
	}
	else {
		temp_prev = removed->prev;
		temp_next = removed->next;
		temp_prev->next = temp_next;
		free(removed);
	}
}


/* ================================================================================= //
//                          "e" - CHANGE THE EMAIL ADDRESS                           //
// ================================================================================= */

void change_email(node *head, tree *root, char name[], char new_email[]) {
	node *temp;
	node *contact = head;

	if (!existing_name(root, name, &temp)) {
		printf("Nome inexistente.\n");
		return;
	}

	for (; contact != NULL; contact = contact->next) {
		if (!strcmp(contact->name, name)) {
			strcpy(contact->email, new_email);
			add_domain(contact, new_email);
		}
	}
}

/* ================================================================================= //
//                          "c" - COUNT EMAIL DOMAIN INSTANCES                       //
// ================================================================================= */

void count_domain(node *head, char domain[]) {
	node *contact = head;
	int count = 0;

	for (; contact != NULL; contact = contact->next) {
		if (!strcmp(contact->domain, domain))
			++count;
	}
	printf("%s:%d\n", domain, count);
}



int main() {
	char c, input[NAME + EMAIL + PHONE], name[NAME], email[EMAIL];
	node *head = NULL;
	node *tail = NULL;
	tree *root = NULL;


	while (1) {
		switch (c = getchar()) {

		case 'a':

			scanf("%[0-9a-zA-Z:-+@ ]s", input);
			add_contact(&head, &tail, &root, input);
			break;

		case 'l':

			print_contacts(head);
			break;

		case 'p':

			scanf("%s", name);
			search_contact(root, name);
			break;

		case 'r':

			scanf("%s", name);
			remove_contact(&head, &root, name);
			break;

		case 'e':

			scanf("%s %s", name, email);
			//head = change_email(head, name, email);
			break;

		case 'c':

			scanf("%s", email);
			count_domain(head, email);
			break;

		case 'x':

			free(head);
			free(root);
			return 0;

		default:

			break;

		}
	}
}