#include#include   #include                         #define MinLength 1#define MaxLength 64   #define MinWidth 1            #define MaxWidth 64              #define Black 0#define White 1#define Grey 2typedef struct node   { int PositionX; int PositionY; int Value; int Width; int** MainArray; struct node* Sub4;}Node;void ExecuteFile ( char *File_Name, Node *node);      void LayNode(Node* node,int PositionX, int PositionY, int Width, int Value, int** MainArray);int Validity (int x);void Quadtree(Node *node);int CheckColor (Node *node, int Top, int Bot, int Left, int Right);int** ProduceArray (Node *node, int Top, int Bot, int Left, int Right, int axis);int main ( int argc, char *argv )   //The main function is specified to start the program, resulting in reading all the functions.//{ Node RootNode; if ( argc != 2) {  puts (“Error executing input!”);  exit(-1); } ExecuteFile( argv1, &RootNode); Quadtree(&RootNode);}void ExecuteFile ( char *File_Name, Node* node ){ int CountedNumberofBlack=1, Counter=0, i, j, a, TerminalWidth, XValue, YValue, b, val, ValidSize, NumberofBlack; long StringSize, ReadSize; int** OriginalArray; char *buffer = NULL; FILE *fp; fp = fopen(File_Name,”r”); if (fp == NULL) {  puts(“Invalid input file!”);  exit (-1); } if (fp) {  fseek(fp,0,SEEK_END);  StringSize = ftell(fp);  rewind(fp);  buffer = (char*) malloc (sizeof(char) * (StringSize + 1) );  ReadSize = fread(buffer,sizeof(char),StringSize,fp);  bufferStringSize = ‘’;  if(bufferStringSize-1 == ‘
‘)  {   bufferStringSize-1 = ‘’;  }  if (StringSize != ReadSize)  {   free(buffer);   buffer =NULL;   puts(“Error storing file!”);   exit(-1);  } } char *str=buffer, *p=str; while (*p) {  if (*p== ‘
‘)  {   CountedNumberofBlack++;   p++;  }  else if (isdigit(*p))  {   val = strtol(p, &p, 10);   if (Counter==0)   {    TerminalWidth = val;    ValidSize=Validity(TerminalWidth);    if (ValidSize != 1)    {     puts(“The image width is not a power of 2.”);     exit (-1);    }    if (TerminalWidthMaxWidth)    {     puts(“Image is large; more than maximum image width.”);     exit (-1);    }    Counter++;    OriginalArray = (int**) malloc(TerminalWidth*sizeof(int*));    for(i = 0; i < TerminalWidth; i++)    {     OriginalArrayi = (int*) malloc(TerminalWidth*sizeof(int));     for ( j = 0; j < TerminalWidth; j++ )     {      OriginalArrayij = White;     }    }   }   else if (Counter==1)   {    NumberofBlack=val;    if (NumberofBlack>(TerminalWidth*TerminalWidth))    {     puts(“Number of black nodes exceed limit!”);     exit (-1);    }    if (NumberofBlack==(TerminalWidth*TerminalWidth))    {     puts(“Image contains only black nodes.”);     exit (-1);    }    if (NumberofBlack==0)    {     puts(“Image contains only white nodes.”);     exit (-1);    }    if (NumberofBlack<0)    {     puts("There is less than 0 black nodes.");     exit (-1);    }    Counter++;   }   else if (Counter%2 == 0)   {    XValue=val;    Counter++;   }   else   {    YValue=val;    if (XValue<0 || XValue>=TerminalWidth || YValue<0 || YValue>=TerminalWidth)    {     printf(“Coordinate (%i,%i) is out of bounds.
“, XValue, YValue);     exit (-1);    }    OriginalArrayXValueYValue=Black;    Counter++;   }  }  else  {   p++;  } } CountedNumberofBlack=CountedNumberofBlack-2; if (NumberofBlack!= CountedNumberofBlack) {  puts(“Number of black nodes does not equal the number counted!”);  exit (0); } b=TerminalWidth-1; LayNode(node, 0, b, TerminalWidth, 2, OriginalArray); free(buffer); for ( a=0; a < TerminalWidth; a++) {  free(OriginalArraya); } free(OriginalArray); fclose(fp); return;}int Validity (int x){ while (((x % 2) == 0) && x > 1) /* While x is even and > 1 */ x /= 2; return x;}void LayNode(Node* newNode, int PositionX, int PositionY, int Width, int Value, int** Nodes){ int i,j,k; newNode->PositionX=PositionX; newNode->PositionY=PositionY; newNode->Width= Width; newNode->Value= Value; for (k = 0; k < 4; k++) newNode->Subk = (Node*) malloc(sizeof(Node)); newNode->MainArray = (int**) malloc(Width*sizeof(int*)); for(i = 0; i < Width; i++) {  newNode->MainArrayi = (int*) malloc(Width*sizeof(int));  for ( j = 0; j < Width; j++ )  {   newNode->MainArrayij = Nodesij;  } }}void Quadtree(Node *node){ int x, Value, axis, upperrange, edge, a, PreviousPositionX,PreviousPositionY, PositionX, PositionY; int** TempArray; PreviousPositionX=node->PositionX; PreviousPositionY=node->PositionY; upperrange=((node->Width)/2); axis=upperrange-1; edge=node->Width-1; for (x=0; x< 4; x++) {  switch(x)  {   case 0:    Value= CheckColor(node, 0, axis, 0, axis);   TempArray = ProduceArray(node, 0, axis, 0, axis, upperrange);   PositionX=PreviousPositionX;   PositionY=PreviousPositionY-upperrange;   LayNode(node->Sub0, PositionX, PositionY, upperrange, Value, TempArray);   for ( a=0; a < upperrange; a++)   {    free(TempArraya);   }   free(TempArray);   if (Value==Black)   {    if (upperrange==1)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY, upperrange);    if (upperrange==2)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-1, upperrange);    if (upperrange==4)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-3, upperrange);    if (upperrange==8)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-7, upperrange);    if (upperrange==16)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-15, upperrange);    if (upperrange==32)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-31, upperrange);    if (upperrange==64)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-63, upperrange);   }   if (Value==Grey)   Quadtree(node->Sub0);   break;   case 1:    Value= CheckColor(node, 0, axis, upperrange, edge);   TempArray = ProduceArray(node, 0, axis, upperrange, edge, upperrange);   PositionX=PreviousPositionX+upperrange;   PositionY=PreviousPositionY-upperrange;   LayNode(node->Sub1, PositionX , PositionY , upperrange, Value, TempArray);   for ( a=0; a < upperrange; a++)   {    free(TempArraya);   }   free(TempArray);   if (Value==Black)   {    if (upperrange==1)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY, upperrange);    if (upperrange==2)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-1, upperrange);    if (upperrange==4)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-3, upperrange);    if (upperrange==8)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-7, upperrange);    if (upperrange==16)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-15, upperrange);    if (upperrange==32)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-31, upperrange);    if (upperrange==64)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-63, upperrange);   }   if (Value==Grey)   Quadtree(node->Sub1);   break;   case 2:    Value= CheckColor(node, upperrange, edge, 0, axis);   TempArray = ProduceArray(node, upperrange, edge, 0, axis, upperrange);   PositionX=PreviousPositionX;   PositionY=PreviousPositionY;   LayNode(node->Sub2, PositionX, PositionY, upperrange, Value, TempArray);   for ( a=0; a < upperrange; a++)   {    free(TempArraya);   }   free(TempArray);   if (Value==Black)   {    if (upperrange==1)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY, upperrange);    if (upperrange==2)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-1, upperrange);    if (upperrange==4)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-3, upperrange);    if (upperrange==8)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-7, upperrange);    if (upperrange==16)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-15, upperrange);    if (upperrange==32)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-31, upperrange);    if (upperrange==64)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-63, upperrange);   }   if (Value==Grey)   Quadtree(node->Sub2);   break;   case 3:    Value= CheckColor(node, upperrange, edge, upperrange, edge);   TempArray = ProduceArray(node, upperrange, edge, upperrange, edge, upperrange);   PositionX=PreviousPositionX+upperrange;   PositionY=PreviousPositionY;   LayNode(node->Sub3, PositionX, PositionY, upperrange, Value, TempArray);   for ( a=0; a < upperrange; a++)   {    free(TempArraya);   }   free(TempArray);   if (Value==Black)   {    if (upperrange==1)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY, upperrange);    if (upperrange==2)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-1, upperrange);    if (upperrange==4)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-3, upperrange);    if (upperrange==8)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-7, upperrange);    if (upperrange==16)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-15, upperrange);    if (upperrange==32)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-31, upperrange);    if (upperrange==64)    printf("Black terminal node at position:(%i,%i), with size:%i. ", PositionX,PositionY-63, upperrange);   }   if (Value==Grey)   Quadtree(node->Sub3);   break;  } }}int CheckColor (Node *node, int Top, int Bot, int Left, int Right){ int i,j,BlackCount=0, WhiteCount=0; for ( j = Top; j <= Bot; j++ ) {  for ( i = Left; i <= Right; i++ )  {   if (node->MainArrayij==White)   {    WhiteCount++;   }   else if (node->MainArrayij==Black)   {    BlackCount ++;   }  } } if (WhiteCount==0) {  return Black; } if (BlackCount==0) {  return White; } return Grey;}int** ProduceArray (Node *node, int Top, int Bot, int Left, int Right, int axis){ int i=0,j=0,x,y,z; int** TempArray = (int**) malloc(axis*sizeof(int*)); for(z = 0; z < axis; z++) {  TempArrayz = (int*) malloc(axis*sizeof(int)); } for ( y=Top ; y <= Bot; y++ ) {  for ( x=Left ; x <= Right; x++ )  {   TempArrayij = node->MainArrayxy;   i=i+1;   if (i==axis)   {    j=j+1;LayNode;    i=0;   }  } } return TempArray;}