/* sort.c */
/* Howard Means (Algorithms competition: Spring 2001 with Dr. Fink) */
/* File containing the sort() function used on a million element array */

/* Node structure */
typedef struct NODE
{
  int value;
  int count;
  struct NODE* next;
}node;

/* Memory module structure */
typedef struct MEMMOD
{
  node* data;
  struct MEMMOD* next;
}memMod;

/* Memory module list structure */
typedef struct
{
  int count;
  memMod* theMod;
}memList;

/* Function prototype */
void sort(int* a, int n);
node* NewNode(int value);
node* NewMem(int value);
void FreeMem(node* theNode);

/* Global Variable */
int timeIn = 0;
memList freeMem;
memList useMem;

void sort(int* a, int n)
{
  int i, cellNum, value, startPt;
  char rowOffset, j;
  node* tmpPtr, *tmpPtr2, *tmpPtr3;
  static node section[250000][10];
  
  /* Clear the list (first time in) */
  if(timeIn == 0)
  {
    freeMem.count = 0;
    freeMem.theMod = NULL;
    useMem.count = 0;
    useMem.theMod = NULL;
    
    for(i = 0; i < 250000; i++)
     for(j = 0; j < 5; j++)
     {
       section[i][j].value = 6000000;
       section[i][j].count = 0;
       section[i][j].next = NULL;
     }
  }
  
  /* Read all the values from a */
  for(i = 0; i < 1000000; i++)
  {
    /* Get the array section this value should fall into */
    value = a[i];
    if(value == 5000000)
    {
      cellNum = 249999;
      rowOffset = 9;
    }
    else /* regular */
    {
      cellNum = (5000000 + value) / 40;
      startPt = -5000000 + (cellNum * 40);
      rowOffset = ((startPt * -1) + value) / 8;
      if(rowOffset < 0) rowOffset *= -1;
    }
    
    /* Add the value to the element (sorted style) */
    if(section[cellNum][rowOffset].value == 6000000)
    {
      /* Fill in that empty spot */
      section[cellNum][rowOffset].value = value;
      section[cellNum][rowOffset].count = 1;
    }
    else if(section[cellNum][rowOffset].value == value)
    {
      /* Incremet the count for that variable */
      section[cellNum][rowOffset].count++;
    }
    else if(section[cellNum][rowOffset].value > value)
    {
      /* Swap positions in the list */
      tmpPtr = NewNode(section[cellNum][rowOffset].value);
       if(tmpPtr == NULL)
       {
         printf("\nCannor Allocate Memory for a[%d].", i);
         return;
       }
      tmpPtr->count = section[cellNum][rowOffset].count;
      tmpPtr->next = section[cellNum][rowOffset].next;
      section[cellNum][rowOffset].value = value;
      section[cellNum][rowOffset].count = 1;
      section[cellNum][rowOffset].next = tmpPtr;
    }
    else if(section[cellNum][rowOffset].value < value)
    {
      tmpPtr = NULL;
      for(tmpPtr = &section[cellNum][rowOffset]; tmpPtr != NULL; tmpPtr = tmpPtr->next)
      {
        if(tmpPtr->value == value)
        {
          tmpPtr->count++;
          break;
        }
        else if(tmpPtr->value > value)
        {
          for(tmpPtr2 = &section[cellNum][rowOffset]; ((tmpPtr2 != NULL)&&(tmpPtr2->next != tmpPtr)); tmpPtr2 = tmpPtr2->next)
          {}
          if(tmpPtr2->next == tmpPtr)
          {
            tmpPtr3 = NewNode(value);
            tmpPtr3->next = tmpPtr;
            tmpPtr2->next = tmpPtr3;
            break;
          }
        }
        else if(tmpPtr->next == NULL)
        {
          tmpPtr->next = NewNode(value);
          break;
        }
      }
    }
  } /* End of top "for" loop */
  
  /* Now, just copy everything back to the array */
  i = 0;
  for(cellNum = 0; cellNum < 250000; cellNum++)
  {
    for(rowOffset = 0; rowOffset < 5; rowOffset++)
    {
      if(section[cellNum][rowOffset].value != 6000000)
      {
        tmpPtr2 = &section[cellNum][rowOffset];
        for(tmpPtr = &section[cellNum][rowOffset]; tmpPtr != NULL; tmpPtr = tmpPtr->next)
        {
          if(tmpPtr2 != &section[cellNum][rowOffset]) free(tmpPtr2);
          while(tmpPtr->count > 0)
	      {
	        /* Get all the duplicates */
	        a[i] = tmpPtr->value;
	        i++;
	        if(i >= 1000000) return; /* Quick escape */
	        tmpPtr->count--;
	      }
	      tmpPtr2 = tmpPtr;
        }
         if(tmpPtr2 != &section[cellNum][rowOffset]) free(tmpPtr2);
         section[cellNum][rowOffset].value = 6000000;
         section[cellNum][rowOffset].count = 0;
         section[cellNum][rowOffset].next = NULL;
      }
    }
  }
  timeIn++;
} /* End of sort() */

/* NewNode() */
node* NewNode(int value)
{
  node* theNode;
  theNode = (node*)malloc(sizeof(node));
   if(theNode == NULL) return NULL;
  theNode->value = value;
  theNode->count = 1;
  theNode->next = NULL;
  return theNode;
}

/* NewMem() */
node* NewMem(int value)
{
  memMod* tmpMod;
  node* theNode;
  
  if(timeIn == 0)
  {
    /* Just allocate nodes */
    theNode = (node*)malloc(sizeof(node));
     if(theNode == NULL) return NULL;
    theNode->value = value;
    theNode->count = 1;
    theNode->next = NULL;
    
    /* Append to useMem */
    tmpMod = (memMod*)malloc(sizeof(memMod));
     if(tmpMod == NULL) return NULL;
    tmpMod->next = useMem.theMod;
    tmpMod->data = theNode;
    useMem.theMod = tmpMod;
    useMem.count++;
    return theNode;
  }
  else /* Pull node from pool of free nodes */
  {
    if(freeMem.count > 0)
    {
      tmpMod = freeMem.theMod;
      freeMem.theMod = freeMem.theMod->next;
      freeMem.count--;
      
      /* Add to front of nodes in use */
      tmpMod->next = useMem.theMod;
      useMem.theMod = tmpMod;
      useMem.count++;
      
      tmpMod->data->value = value;
      tmpMod->data->count = 1;
      tmpMod->data->next = NULL;
      return(tmpMod->data);
    }
    else /* Forced to allocate again */
    {
      /* Just allocate nodes */
      theNode = (node*)malloc(sizeof(node));
       if(theNode == NULL) return NULL;
      theNode->value = value;
      theNode->count = 1;
      theNode->next = NULL;
    
      /* Append to useMem */
      tmpMod = (memMod*)malloc(sizeof(memMod));
       if(tmpMod == NULL) return NULL;
      tmpMod->next = useMem.theMod;
      tmpMod->data = theNode;
      useMem.theMod = tmpMod;
      useMem.count++;
      return theNode;
    }
  }
}

/* FreeMem() */
void FreeMem(node* theNode)
{
  memMod* rover, *prev;
  
  if((theNode == NULL)||(useMem.theMod == NULL)) return;
  
  prev = useMem.theMod;
  if(prev->data == theNode)
  {
    /* Add to pool of free nodes */
    useMem.theMod = prev->next;
    prev->next = freeMem.theMod;
    freeMem.theMod = prev;
    freeMem.count++;
    useMem.count--;
  }
  else for(rover = prev->next; rover != NULL; rover = rover->next)
  {
    if(rover->data == theNode)
    {
      prev->next = rover->next;
      useMem.count--;
      rover->next = freeMem.theMod;
      freeMem.theMod = rover;
      freeMem.count++;
      return;
    }
    prev = rover;
  }
}