IF tree is right heavy
{
IF tree's right subtree is left heavy
{
Perform Double Left rotation
}
ELSE
{
Perform Single Left rotation
}
}
ELSE IF tree is left heavy
{
IF tree's left subtree is right heavy
{
Perform Double Right rotation
}
ELSE
{
Perform Single Right rotation
}
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <string.h>
#include <errno.h>
#define ERRNUM -1
typedef enum bool {
FALSE =0,
TRUE
} e_bool;
typedef enum stauts {
FAILURE = 0,
SUCCESS
} e_status;
typedef struct list* tsp_list;
struct list{
unsigned int val;
unsigned int index;
tsp_list next;
};
e_status Append (unsigned int num, tsp_list *list)
{
tsp_list lsp_primeNode = NULL;
lsp_primeNode = (tsp_list) calloc (1, sizeof (struct list));
if (NULL == lsp_primeNode)
{
fprintf (stderr, "ERROR: memory allocation failed.\n");
return FAILURE;
}
lsp_primeNode->val = num;
lsp_primeNode->next = NULL;
if (NULL == *list)
{
*list = lsp_primeNode;
lsp_primeNode->index = 1;
}
else
{
tsp_list node = *list;
while (NULL != node->next)
{
node = node->next;
}
node->next = lsp_primeNode;
lsp_primeNode->index = node->index + 1;
}
return SUCCESS;
}
e_bool IsPrime (unsigned int num, tsp_list list)
{
if (1 >= num)
{
return FALSE;
}
switch (num)
{
case 2:
case 3:
return TRUE;
default:
{
unsigned int lv_max_limit = (unsigned int) sqrt (num);
while (list && list->val <= lv_max_limit)
{
if (0 == num % list->val)
{
return FALSE;
}
list = list->next;
}
return TRUE;
}
}
}
void GetPrimeList (tsp_list *list, unsigned count)
{
unsigned int i = 2;
unsigned int index = 1;
struct timeval start;
struct timeval end;
struct timeval diff;
if(-1 == gettimeofday(&start, NULL))
{
fprintf (stderr, "ERROR: %s\n", strerror (errno));
return;
}
for (; i && 0 < count; i++)
{
if (TRUE == IsPrime (i, *list))
{
if(-1 == gettimeofday(&end, NULL))
{
fprintf (stderr, "ERROR: %s\n", strerror (errno));
return;
}
/* Ref [http://www.linuxquestions.org/questions/programming-9/how-to-calculate-time-difference-in-milliseconds-in-c-c-711096] */
diff.tv_sec =end.tv_sec - start.tv_sec ;
diff.tv_usec=end.tv_usec - start.tv_usec;
if(diff.tv_usec<0)
{
diff.tv_usec+=1000000;
diff.tv_sec -=1;
}
printf ("%d (index: %d) (Time taken: %f sec)\n", i, index++, (float)(1000000LL*diff.tv_sec + diff.tv_usec)/1000000);
if (FAILURE == Append (i, list))
{
return;
}
else
{
count --;
}
}
}
}
int main (int argc, char *argv[])
{
tsp_list primeList = NULL;
int dig = 0;
if ( 2 != argc)
{
return 0;
}
GetPrimeList (&primeList, (int) atoi(argv[1]));
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ERRNUM -1
#define SUCCESS 0
#define TRUE 1
#define FALSE 0
#define TOTAL_ALPHA 26
/* Function : permutations
* Args : str [IN]
* index [IN]
* result [IN/OUT]
* Description: Function will print all the permutations and combinations of a given string
* without repeated patterns. PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) }
* Note : This "without repeated patterns" will not work for non-alpha characters [TBD].
*/
int permutations (char *str, int index, char *result)
{
char *temp = NULL; // To store the given string for processing
int len = strlen (str); // Length of the given string
int count = 0; // Counter variable used in the loop
int j = 0; // Temporary variable
char found[52] = {0}; // To check the variable to check the duplicate characters to avoid duplicate patterns
/* Allocate memory for the temp variable to store the given string for processing.
* So that the given string will not change.
*/
temp = (char *) calloc (len+1, sizeof (char));
if (NULL == temp)
{
fprintf (stderr, "Memory allocation failed.\n");
return ERRNUM;
}
/* Copy the given string into the temporary variable */
strcpy (temp, str);
/* Traverse through the string and find the permutations and combinations of the substring
* PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) }
*/
for (count=0; count < len; count++)
{
char ch = 0;
*(result + index) = *temp;
if (1 == len)
{
/* We can store in an array of string or a stack */
printf ("%s\n", result);
}
else
{
if (isupper (*temp))
{
if (FALSE == found [TOTAL_ALPHA + (*temp) - 'A'])
{
found [TOTAL_ALPHA + (*temp) - 'A'] = TRUE;
}
else
{
/* Its a duplicate character */
goto NEXT;
}
}
else if (islower (*temp))
{
if (FALSE == found [(*temp) - 'a'])
{
found [(*temp) - 'a'] = TRUE;
}
else
{
/* Its a duplicate character */
goto NEXT;
}
}
/* We can store in an array of string or a stack */
for (j=0; j<=index; j++)
{
printf ("%c", *(result+j));
}
printf ("\n");
/* Find the permutations and combinations for the substring too */
if (ERRNUM == permutations (temp+1, index+1, result))
{
return ERRNUM;
}
NEXT:
ch = *temp;
memcpy (temp, temp+1, len-1);
temp[len-1] = ch;
}
}
/* Free the allocated memory for the temporary variable */
free (temp);
return SUCCESS;
}
int main (int argc, char *argv[])
{
char *result = NULL; // Variable to store the result for printing
int retVal = SUCCESS; // Variable to stroe the return value
// No code to check/validate the input [TBD].
if (NULL == result)
{
result = (char *) calloc (strlen (argv[1])+1, sizeof (char));
if (NULL == result)
{
fprintf (stderr, "Memory allocation failed.\n");
return ERRNUM;
}
}
retVal = permutations (argv[1], 0, result);
free (result);
return retVal;
}
The results: