/* ILLUSTRATING TEXT BY TAG CLOUDS - Parsing the Data File -tagCloud.h
----------------------------------------------------------------------------------------------------------------
Author: Emma E. Alberts
Instructor: Bonita McVey & Dave Pankratz
Date: 5/6/2019
Purpose: create a program that reads a data file and constructs a tag cloud
----------------------------------------------------------------------------------------------------------------*/
#pragma once
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include "ctype.h"
using namespace std;

struct node {
	string word;
	int frequency;
	node * next;
};

void addWord(string curWord, node * list[], int index);
void MergeSort(node * headRef);
node * mergeList(node * left, node * right);
void split(node * source, node * frontRef, node * backRef);
void removeDuplicates(node * head);
void deleteNode(node * list);
bool addNodeToFile(node * list);
bool isEmpty(node * list[]);


/* addWord
----------------------------------------------------------------------------------------------------------------
Purpose:	add a word to the array of linked lists
Parameters:	curWord		- the word you want to add
			list		- the array of linked lists you will be adding to
			index		- the index of the array where the word should be added
Output:		list is a reference parameter (by nature of an array) 
----------------------------------------------------------------------------------------------------------------*/
void addWord(string curWord, node * list[], int index) {
	node * addMe = new node();
	addMe->word = curWord;
	addMe->next = NULL;
	addMe->frequency = 1;
	if (list[index] == NULL) {
		list[index] = addMe;
	}
	else {
		addMe->next = list[index];
		list[index] = addMe;
	}
}

/* MergeSort
----------------------------------------------------------------------------------------------------------------
Purpose:	perform a merge sort to sort words alphabetically
Parameters:	list	- the linked list you wish to sort
Output:		pointer will point to the sorted list
----------------------------------------------------------------------------------------------------------------*/
void MergeSort(node * list){
	node * head = list;
	node * left = NULL;
	node * right = NULL;

	if ((head == NULL) || (head->next == NULL)) {
		return;
	}

	split(head, left, right);
	MergeSort(left);
	MergeSort(right);

	list = mergeList(left, right);
}

/* mergeList
----------------------------------------------------------------------------------------------------------------
Purpose:	merges two lists, sorting as you go
Parameters:	left	- a pointer to the left side of the linked list
			right	- a pointer to the right side of the linked list
Output:		node *	- a pointer to the merged list
----------------------------------------------------------------------------------------------------------------*/
node * mergeList(node * left, node * right){
	node * result = NULL;

	if (left == NULL)
		return (right);
	else if (right == NULL)
		return (left);

	if (left->word <= right->word) {
		result = left;
		result->next = mergeList(left->next, right);
	}
	else {
		result = right;
		result->next = mergeList(left, right->next);
	}
	return (result);
}

/* split
----------------------------------------------------------------------------------------------------------------
Purpose:	split the linked list so that the sides can be sorted
Parameters:	source	- a pointer to the beginning of the list
			front	- a pointer that will hold the front of the list
			back	- a pointer that will hold the back of the list
Output:		front and back now hold the split list
----------------------------------------------------------------------------------------------------------------*/
void split(node * source, node * front, node * back){
	node * left;
	node * right;
	right = source;
	left = source->next;

	while (left != NULL) {
		left = left->next;
		if (left != NULL) {
			right = right->next;
			left = left->next;
		}
	}

	front = source;
	back = right->next;
	right->next = NULL;
}

/* removeDuplicates
----------------------------------------------------------------------------------------------------------------
Purpose:	remove duplicate words from the list and increase the counter
Parameters:	list	- the linked list in which the duplicates should be removed from
Output:		list will contain the new list
----------------------------------------------------------------------------------------------------------------*/
void removeDuplicates(node * list){
	node * curNode = list;
	node * nextNode;

	// is the list empty?
	if (curNode == NULL)
		return;

	while (curNode->next != NULL)
	{
		// compare curNode to nextNode
		if (curNode->word == curNode->next->word)
		{
			// means they are the same word and should remove and increase frequency
			curNode->frequency += 1;
			nextNode = curNode->next->next;
			free(curNode->next);
			curNode->next = nextNode;
		}
		else //only advance if no deletion
		{
			curNode = curNode->next;
		}
	}
}

/* deleteNode
----------------------------------------------------------------------------------------------------------------
Purpose:    deletes first node in a linked list
Parameters: list	- the list in which a word needs to be deleted from
Output:     list will contain the list without the first node
----------------------------------------------------------------------------------------------------------------*/
void deleteNode(node * list) {
	node * dump = list;
	list = dump->next;
	dump->next = NULL;
	delete(dump);
	return;
}

/* addNodeToFile                                                                                 
----------------------------------------------------------------------------------------------------------------
Purpose:    determine if a member of the linked list should be added to the file
Parameters: list	- a pointer to a linked list
Output:     boolean	- true if it should be added to the file
					- false if it is empty and should not be added
----------------------------------------------------------------------------------------------------------------*/
bool addNodeToFile(node * list) {
	if (list == NULL)
		return false;
	else
		return true;
}

/* isEmpty                                                                                
----------------------------------------------------------------------------------------------------------------
Purpose:    to determine if the array of lists is empty
Parameters: list	- an array of linked lists
Output:     boolean	- true if the array is empty
					- false if the array still contains word
----------------------------------------------------------------------------------------------------------------*/
bool isEmpty(node * list[]) {
	for (int i = 0; i < 27; i++) {
		if (list[i] != NULL)
			return true;
	}
	return false;
}