/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/*                             Map Can Segment                               */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/* PURPOSE:   To determine if a certain map can be divided into 4 groups of  */
/*            unrelated villages.                                            */
/*                                                                           */
/* INPUT:     Map type - the map                                             */
/*                                                                           */
/* OUTPUT:    MapResult - enum type                                          */
/*                                                                           */
/* OPERATION: Allocates memory for an aiding array, and arranges all the     */
/*            nessecery arguments for the recursion. then, invoke the        */
/*            recursive function, and prints the results.                    */
/*                                                                           */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
MapResult MapCanSegment(Map map)
{
	int *groupArray = NULL; //aiding array - divides to groups
	
	//cutting back on edge cases: if there 4 or less villages
	if(map->numOfVillages <= 4)
	{
		printf("Can Segment!\n");
		return MAP_SUCCESS;
	}
	
	//memory allocation for array
	groupArray = (int*) calloc (map->numOfVillages + 1, sizeof(int));
	//if out of memory
	if(groupArray == NULL)
	{
		return MAP_OUT_OF_MEMORY;
	}	
	
	//assigning the last "cell" to a value that is different from 0/1/2/3
	groupArray = 4;
	
	//invoking the recursion
	if(RecursiveGrouping(map->roadMatrix, map->numOfVillages, groupArray))
		printf("Can Segment!\n");
	else
		printf("Can Not Segment!\n");
	
	return MAP_SUCCESS;
}
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/*                           Recursive Grouping                              */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/* PURPOSE:   To determine if a certain map can be divided into 4 groups of  */
/*            unrelated villages.                                            */
/*                                                                           */
/* INPUT:     an array of the roads (int*), the number of villages, and an   */
/*            aiding array with the group members as numbers from 0 to 3     */
/*                                                                           */
/* OUTPUT:    int - 1 or 0 - yes or no.                                      */
/*                                                                           */
/* OPERATION: Stoping condition, is when we reached the cell containing the  */
/*            value we first "planted" on the last cell. if we reached the   */
/* end, we call another function that determines if the current segmentation */
/* has no connections between group members. for all other recursive levels, */
/* we invoke the recursion in a loop, while assigning new value to the array */
/* and invoke the recursion with pointer incremention.                       */
/*                                                                           */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
static int RecursiveGrouping(int *roadMap, int numOfVlgs, int *groupArray)
{
	int iCounter = 0; //loop counter
	
	//if we went through all the array and reached the end
	if(groupArray == 4)
		//check segmentation (groupArray decremented to the starting point)
		return CheckSegmention(roadMap, numOfVlgs, groupArray - numOfVlgs);
	//loop that controls group assignment
	for(iCounter = 0; iCounter < 4; iCounter++)
	{
		//assigning group to current village
		groupArray = iCounter;
		//check recursively if it's a valid segmentation 
		if(RecursiveGrouping(roadMap, numOfVlgs, groupArray + 1))
			return 1;	
	}
	return 0;
}
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/*                            Check Segmention                               */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
/* PURPOSE:   To determine if a certain segmentation of villages to groups   */
/*            is valid. (connection between villages in group is forbidden)  */
/*                                                                           */
/* INPUT:     an array of the roads (int*), the number of villages, and an   */
/*            aiding array with the group members as numbers from 0 to 3     */
/*                                                                           */
/* OUTPUT:    int - 1 or 0 - yes or no.                                      */
/*                                                                           */
/* OPERATION: Through nested loops that checks for every village, if other   */
/*            villages in the same group are connected or not.               */
/*                                                                           */
/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/
static int CheckSegmention(int *roadMap, int numOfVlgs, int *groupArray)
{
	int iCounter1 = 0; //loop counter - village 1
	int iCounter2 = 0;//loop counter - village 2
	for(iCounter1 = 0; iCounter1 < numOfVlgs; iCounter1++)
	{
		for(iCounter2 = 0; iCounter2 < numOfVlgs; iCounter2++)
		{
			//if villages are not in the same group, continue
			if(groupArray !=  groupArray)
				continue;
			
			//if villages are in the same group and yet are connected, return 0
			if(roadMap != 0)
				return 0;
		}
	}
	//check passed ok: return 1 (succcess!)
	return 1;
}