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

#define MAX 100
#define TABLE_SIZE 10

int arr[MAX], n;

/* ====================== LINEAR SEARCH ====================== */
int linearSearch(int a[], int size, int key){
	for(int i = 0; i < size; i++){
		if(a[i] == key)
			return i;
	}
	return -1;
}

/* ================= BINARY SEARCH (ITERATIVE) ================ */
int binarySearch(int a[], int size, int key){
	int low = 0, high = size - 1;
	while(low <= high){
		int mid = low + (high - low) / 2;
		if(a[mid] == key) return mid;
		else if(a[mid] < key) low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

/* ================= BINARY SEARCH (RECURSIVE) ================ */
int binarySearchRec(int a[], int low, int high, int key){
	if(low > high) return -1;
	int mid = low + (high - low) / 2;
	if(a[mid] == key) return mid;
	else if(a[mid] < key)
		return binarySearchRec(a, mid + 1, high, key);
	else
		return binarySearchRec(a, low, mid - 1, key);
}

/* ====================== SORTING HELPER ====================== */
void insertionSort(int a[], int size){
	for(int i = 1; i < size; i++){
		int key = a[i];
		int j = i - 1;
		while(j >= 0 && a[j] > key){
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = key;
	}
}

/* ==================== HASH TABLE (CHAINING) ================== */
struct HashNode {
	int key;
	struct HashNode *next;
};

struct HashNode *hashTable[TABLE_SIZE];

void hashInit(){
	for(int i = 0; i < TABLE_SIZE; i++)
		hashTable[i] = NULL;
}

int hashFunction(int key){
	return ((key % TABLE_SIZE) + TABLE_SIZE) % TABLE_SIZE;
}

void hashInsert(int key){
	int index = hashFunction(key);
	struct HashNode *newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
	newNode->key = key;
	newNode->next = hashTable[index];
	hashTable[index] = newNode;
	printf("Inserted %d at index %d\n", key, index);
}

int hashSearch(int key){
	int index = hashFunction(key);
	struct HashNode *temp = hashTable[index];
	while(temp != NULL){
		if(temp->key == key)
			return 1;
		temp = temp->next;
	}
	return 0;
}

void hashDelete(int key){
	int index = hashFunction(key);
	struct HashNode *temp = hashTable[index];
	struct HashNode *prev = NULL;
	while(temp != NULL){
		if(temp->key == key){
			if(prev == NULL)
				hashTable[index] = temp->next;
			else
				prev->next = temp->next;
			free(temp);
			printf("Deleted %d from index %d\n", key, index);
			return;
		}
		prev = temp;
		temp = temp->next;
	}
	printf("%d not found in hash table!\n", key);
}

void hashDisplay(){
	printf("\n--- Hash Table ---\n");
	for(int i = 0; i < TABLE_SIZE; i++){
		printf("[%d]: ", i);
		struct HashNode *temp = hashTable[i];
		while(temp != NULL){
			printf("%d -> ", temp->key);
			temp = temp->next;
		}
		printf("NULL\n");
	}
}

/* ======================== UTILITIES ======================== */
void displayArray(int a[], int size){
	for(int i = 0; i < size; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void readArray(){
	printf("Enter number of elements: ");
	scanf("%d", &n);
	printf("Enter %d elements: ", n);
	for(int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
}

int main(){
	int choice, key, result;
	int sorted = 0;
	hashInit();

	printf("\n========================================\n");
	printf("  SEARCHING ALGORITHMS IMPLEMENTATION\n");
	printf("========================================\n");

	do {
		printf("\n--- Searching Menu ---\n");
		printf(" 1. Enter array\n");
		printf(" 2. Display array\n");
		printf(" 3. Linear Search\n");
		printf(" 4. Binary Search (Iterative)\n");
		printf(" 5. Binary Search (Recursive)\n");
		printf(" 6. Sort array (for binary search)\n");
		printf("--- Hash Table ---\n");
		printf(" 7. Hash Insert\n");
		printf(" 8. Hash Search\n");
		printf(" 9. Hash Delete\n");
		printf("10. Hash Display\n");
		printf(" 0. Exit\n");
		printf("Enter choice: ");
		scanf("%d", &choice);

		switch(choice){
			case 1:
				readArray();
				sorted = 0;
				break;
			case 2:
				if(n == 0){ printf("No array loaded!\n"); break; }
				printf("Array: "); displayArray(arr, n);
				printf("Sorted: %s\n", sorted ? "Yes" : "No");
				break;
			case 3:
				if(n == 0){ printf("Enter array first!\n"); break; }
				printf("Enter key to search: ");
				scanf("%d", &key);
				result = linearSearch(arr, n, key);
				if(result != -1)
					printf("Found %d at index %d\n", key, result);
				else
					printf("%d not found.\n", key);
				break;
			case 4:
				if(n == 0){ printf("Enter array first!\n"); break; }
				if(!sorted){
					printf("Array not sorted. Sorting first...\n");
					insertionSort(arr, n);
					sorted = 1;
					printf("Sorted array: "); displayArray(arr, n);
				}
				printf("Enter key to search: ");
				scanf("%d", &key);
				result = binarySearch(arr, n, key);
				if(result != -1)
					printf("Found %d at index %d\n", key, result);
				else
					printf("%d not found.\n", key);
				break;
			case 5:
				if(n == 0){ printf("Enter array first!\n"); break; }
				if(!sorted){
					printf("Array not sorted. Sorting first...\n");
					insertionSort(arr, n);
					sorted = 1;
					printf("Sorted array: "); displayArray(arr, n);
				}
				printf("Enter key to search: ");
				scanf("%d", &key);
				result = binarySearchRec(arr, 0, n - 1, key);
				if(result != -1)
					printf("Found %d at index %d\n", key, result);
				else
					printf("%d not found.\n", key);
				break;
			case 6:
				if(n == 0){ printf("Enter array first!\n"); break; }
				insertionSort(arr, n);
				sorted = 1;
				printf("Array sorted: "); displayArray(arr, n);
				break;
			case 7:
				printf("Enter key to insert into hash table: ");
				scanf("%d", &key);
				hashInsert(key);
				break;
			case 8:
				printf("Enter key to search in hash table: ");
				scanf("%d", &key);
				if(hashSearch(key))
					printf("%d found in hash table.\n", key);
				else
					printf("%d not found in hash table.\n", key);
				break;
			case 9:
				printf("Enter key to delete from hash table: ");
				scanf("%d", &key);
				hashDelete(key);
				break;
			case 10:
				hashDisplay();
				break;
			case 0:
				printf("Exiting...\n");
				break;
			default:
				printf("Invalid choice!\n");
		}
	} while(choice != 0);

	return 0;
}