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

#define true 1
#define false 0
#define TH 5


/* ------------------------------------------------------------------------- */
/* This is a good, "low tech", solution to 2B --
   it only uses data structures that are covered in CSE13O3.
   Note that the Tree is reformed (and thus rebalanced) if
   it starts to get too "scrawny".  One could, of course, use
   an AVL tree (or priority-queues) but we wanted to show that
   2B could be done with CSE13O3 knowledge.
*/
/* ------------------------------------------------------------------------- */


typedef struct
{
	float elm;
	int pos;
} Element;

struct NODE
{
	float elm;
	struct NODE* lChild;
	struct NODE* rChild;
	struct NODE* parent;
};

typedef struct NODE Node;

/*
 *
 * Binray Tree
 *
 */

void insertNode(Node **root, float elm, float *mnNum, float *mxNum, int *searchReqToFindElm)
{
	Node *tempNode1 = NULL;
	Node *tempNode2 = *root;
	Node *newNode = (Node *)malloc(sizeof(Node));

	if(!newNode)
	{
	 printf("Not enough free memory to create a Node\n");
	 return;
	}

	newNode->lChild = NULL;
	newNode->rChild = NULL;
	newNode->parent = NULL;
	newNode->elm = elm;
	
	while(tempNode2)
	{
	 tempNode1 = tempNode2;
	 (*searchReqToFindElm)++;
	 if(newNode->elm < tempNode2->elm)
	   tempNode2 = tempNode2->lChild;
	 else
	   tempNode2 = tempNode2->rChild;
	}

	newNode->parent = tempNode1;

	if (!tempNode1)
	{
	  *root = newNode;
	  *mnNum = newNode->elm;
	  *mxNum = newNode->elm;
	}
	else
	{
		if(newNode->elm < tempNode1->elm)
		{
		  tempNode1->lChild = newNode;
		  if(tempNode1->elm == *mnNum)
		     *mnNum = newNode->elm;
		}
		else
		{
		  tempNode1->rChild = newNode;
		  if(tempNode1->elm == *mxNum)
		     *mxNum = newNode->elm;

		}
	}
	
}

void inorderTreeWalk(Node *node)
{
	if(node)
	{
	  inorderTreeWalk(node->lChild);
	  printf("%.3f ", node->elm);
	  inorderTreeWalk(node->rChild);
	}
}

Node *searchTree(Node *node, float elm, int *searchReqToFindElm)
{
	if((node == NULL) || (elm == node->elm))
		return node;

	(*searchReqToFindElm)++;
	if (elm < node->elm)
		return searchTree(node->lChild, elm, searchReqToFindElm);
	else
		return searchTree(node->rChild, elm, searchReqToFindElm);
}


Node *searchMinimum(Node *node)
{
	while(node->lChild )
		node = node->lChild;

	return node;
}

Node *searchMaximum(Node *node)
{
	while(node->rChild)
		node = node->rChild;

	return node;
}

Node *searchSuccessor(Node *node)
{
	Node *tempNode;

	if(node->rChild)
	{
		return searchMinimum(node->rChild);
	}

	tempNode = node->parent;

	while(tempNode && (node == tempNode->rChild))
	{
		node = tempNode;
		tempNode = tempNode->parent;
	}

	return tempNode;

}


void deleteNode(Node **root, Node* node, float *mnNum, float *mxNum)
{
	Node *tempNode1 = NULL;
	Node *tempNode2 = NULL;
	int flag = 1;

	if((node->lChild==NULL) || (node->rChild==NULL))
	{
		tempNode1 = node;

		if((node->lChild==NULL) && (node->rChild==NULL))
		{
			if( (node->elm == *mnNum) && node->parent)
				*mnNum = node->parent->elm;
			else if( (node->elm == *mxNum) && node->parent)
				*mxNum = node->parent->elm;
			flag = 0;
		}
		
		if( (*root == node) && ((*root)->elm == *mnNum) )
		{
			*mnNum = searchMinimum((*root)->rChild)->elm;
			flag = 0;
		}
		else if( (*root == node) && ((*root)->elm == *mxNum) )
		{
			*mxNum = searchMaximum((*root)->lChild)->elm;
			flag = 0;
		}	
	}
	else
		tempNode1 = searchSuccessor(node);

	if(tempNode1->lChild)
		tempNode2 = tempNode1->lChild;
	else
		tempNode2 = tempNode1->rChild;

	if(tempNode2)
		tempNode2->parent = tempNode1->parent;

	if(tempNode1->parent==NULL)
	{
		
		*root = tempNode2;
		flag = 0;

	}
	else
	{
		if(tempNode1 == tempNode1->parent->lChild)
			tempNode1->parent->lChild = tempNode2;
		else
			tempNode1->parent->rChild = tempNode2;
	}

	if(tempNode1 != node)
	{
		node->elm = tempNode1->elm;
		flag =0;
		
		if( tempNode1->elm == *mnNum )
			*mnNum = node->elm;
		else if( tempNode1->elm == *mxNum )
			*mxNum = node->elm;
		
	}

	if(*mnNum==tempNode1->elm || *mxNum==tempNode1->elm)
	{
		*mnNum = searchMinimum(*root)->elm;
		*mxNum = searchMaximum(*root)->elm;
	}

	free(tempNode1);
	tempNode1 = NULL;
}


void freeTree(Node *node)
{
	if(node)
	{
		freeTree(node->lChild);
		freeTree(node->rChild);
		free(node);
	}
}

void createBalTree(long hi, long lo, Element *sList, Node **root, float *mnNum, float *mxNum)
{
	int useless;
	if(hi<=lo || (sList[(hi+lo)/2].pos == -1))
		return;
	else
	{
		insertNode(root, sList[(hi+lo)/2].elm, mnNum, mxNum, &useless);
		sList[(hi+lo)/2].pos = -1;
		createBalTree((hi+lo)/2, lo, sList, root, mnNum, mxNum);
		createBalTree(hi, ((hi+lo)/2), sList, root, mnNum, mxNum);
	}
}

/*
 *
 * Merge Sort
 *
 */

void merge(Element *inA, int lo, int hi, Element *opA, Element *uslist)
/* sort (input) inA[lo..hi] into (output) opA[lo..hi] */
 { 
   int i, j, k;

   if(hi > lo) /* at least 2 elements */
    { 
	  int mid = (lo+hi)/2;          /* lo <= mid < hi */
      merge(opA, lo,   mid, inA, uslist);     /* sort the ... */
      merge(opA, mid+1, hi, inA, uslist);      /* ... 2 halfs */

      i = lo;  j = mid+1;  k = lo;  /* and merge them */
      while(true)
       { 
        if( inA[i].elm <= inA[j].elm )        /* smaller */
          { 
	   opA[k] = inA[i]; 
	   uslist[inA[i].pos].pos = k;
	   i++; k++;
           if(i > mid) /* copy rest */
             { 
	       for( ; j <= hi;  j++)
		{
              	 opA[k]=inA[j]; 
		 uslist[inA[j].pos].pos = k;
		 k++;
	        }
              break;
             }
          }
         else
          { 
		   opA[k] = inA[j]; 
		   uslist[inA[j].pos].pos = k;
		   j++; k++;
           if(j > hi) /* copy rest */
             { 
				for( ; i <= mid; i++)
				{
				 opA[k]=inA[i]; 
				 uslist[inA[i].pos].pos = k;
				 k++;
				}
				break;
             }
          }
       }/*while */
    }/*if  */
 }/*merge */

void mergeSort(Element *a, int N, Element uslist[])  /* wrapper routine */
/* NB sort a[1..N] */
 { 
   int i; 
   
   Element *b = (Element *)malloc((N)*sizeof(Element));

   if(b)
   {
   for(i=0; i <= N-1; i++) 
	   b[i]=a[i];
   merge(b, 0, N-1, a, uslist);
   free(b);
   }

 }


void findStable(long r, char *fileName)
{
	long i;
	Node *treeRoot=NULL;
	Node *tempNode;
	Element *uslist,*list;
	float fNum, elmToDel, prevDiff, minNum, maxNum, prevMinNum, prevMaxNum;
	long itemsCount, prevPos, treeBalCount, countB4TreeIsBal;
	clock_t ticks1, ticks2;
	FILE *in;
	double searchAvg = 0;
	int flag = 0;
	int searchReqToFindElm;

	in = fopen(fileName,"r+t");

	if(!in)
	{
		printf("Input file is missing\n");
		return ;
	}

	if(r<1)
	{
		printf("Please make sure r>=1.\n");
		fclose(in);
		return;
	}

	uslist = (Element *)malloc(sizeof(Element)*(r));
	list = (Element *)malloc(sizeof(Element)*(r));
	
	ticks1=clock();
	ticks2=ticks1;
  	i = 0;
	while( i<r )
	{
		if (fscanf(in,"%f",&fNum)!=1)
		{
			printf("Please make sure 'r' is less than total items in the input file\n");

			free(uslist);
			free(list);
			fclose(in);
			return;
		}
		uslist[i].elm = fNum;
		uslist[i].pos = i;
		list[i].elm = fNum;
		list[i].pos = i;
		i++;
	}

	mergeSort(list, r, uslist);
	createBalTree(r, 0, list, &treeRoot, &minNum, &maxNum);
	
	i=0;
	itemsCount=1;
	prevDiff = maxNum-minNum;
	prevMinNum = minNum;
	prevMaxNum = maxNum;
	prevPos = 1;
	treeBalCount = 1;
	countB4TreeIsBal = 1;

	while(fscanf(in,"%f",&fNum)==1)
	{
		elmToDel = uslist[i].elm;
		uslist[i].elm = fNum;
		uslist[i].pos = i;
		i++;
		itemsCount++;
		if(i>r-1)
			i=0;

		//memcpy(list, uslist, sizeof(Element)*(r));
		//mergeSort(list, r, uslist);

		if(flag==1)
		{
			freeTree(treeRoot);
			treeRoot = NULL;
			memcpy(list, uslist, sizeof(Element)*(r));
			mergeSort(list, r, uslist);
			createBalTree(r, 0, list, &treeRoot, &minNum, &maxNum);
			flag = 0;
			treeBalCount++;
			countB4TreeIsBal = 1;
			searchAvg = 0;
		}
		else
		{
			searchReqToFindElm=0;
			tempNode = searchTree( treeRoot, elmToDel, &searchReqToFindElm);
			searchAvg += searchReqToFindElm;
			deleteNode( &treeRoot, tempNode, &minNum, &maxNum);

			searchReqToFindElm=0;
			insertNode(&treeRoot, fNum, &minNum, &maxNum, &searchReqToFindElm);
			searchAvg += searchReqToFindElm;

			if( searchAvg/(2*countB4TreeIsBal) > TH*log10(r)/log10(2))
			  flag = 1;
			else
			  countB4TreeIsBal++;
		}
	
		
		if(prevDiff > maxNum-minNum )
		{
			prevDiff = maxNum-minNum;
			prevPos = itemsCount;
			prevMinNum = minNum;
			prevMaxNum = maxNum;
		}


	}

    ticks2=clock();	

	printf("Total items in the file:                %ld\n",(itemsCount-1)+r);
	printf("Stable range:                           %ld ~ %ld\n", prevPos-1, prevPos+r-2); 	
	printf("Maximum number in the stable range:     %0.3f\n", prevMaxNum);
	printf("Minimum number in the stable range:     %0.3f\n", prevMinNum);
	printf("Difference between maximum and minimum: %0.3f\n", prevDiff);
	printf("Time taken to get this result:          %0.3f secs [%ld ticks]\n", ((ticks2-ticks1)*1.0)/CLOCKS_PER_SEC, ticks2-ticks1);
	printf("Tree has been balanced:                 %ld times \n", treeBalCount);

	free(uslist);
	free(list);
	fclose(in);
	freeTree(treeRoot);

}

int main(int argc, char *argv[])
{
	if(argc != 3)
	{
		printf("Please use the following syntax:\n");
		printf("stable r filename\n");
		return 0;
	}

	printf("Window size (r) : %ld\n", atol(argv[1]));
	printf("Filename        : %s\n", argv[2]);

	printf("\nPlease wait ........\n\n");
	
	findStable( atol(argv[1]), argv[2]);
	return 0;
}