generated from freudenreichan/info2Praktikum-DobleSpiel
99 lines
2.9 KiB
C
99 lines
2.9 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <time.h>
|
|
#include <string.h>
|
|
#include "numbers.h"
|
|
#include "bintree.h"
|
|
|
|
static int compareUnsigned(const void *a, const void *b)
|
|
{
|
|
unsigned int va = *(const unsigned int *)a;
|
|
unsigned int vb = *(const unsigned int *)b;
|
|
if (va < vb) return -1;
|
|
if (va > vb) return 1;
|
|
return 0;
|
|
}
|
|
|
|
// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
|
|
// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while
|
|
// creating random numbers.
|
|
unsigned int *createNumbers(unsigned int len)
|
|
{
|
|
if (len < 2) return NULL;
|
|
|
|
unsigned int *arr = (unsigned int *)malloc(len * sizeof(unsigned int));
|
|
if (arr == NULL) return NULL;
|
|
|
|
TreeNode *root = NULL;
|
|
/* create len-1 unique values in range [1, 2*len] */
|
|
srand((unsigned int)time(NULL));
|
|
|
|
while (treeSize(root) < len - 1) {
|
|
unsigned int v = (unsigned int)(rand() % (2 * len)) + 1;
|
|
int isDup = 0;
|
|
TreeNode *newRoot = addToTree(root, &v, sizeof(unsigned int), compareUnsigned, &isDup);
|
|
if (newRoot == NULL && root != NULL) { // allocation failed
|
|
clearTree(root);
|
|
free(arr);
|
|
return NULL;
|
|
}
|
|
root = newRoot;
|
|
/* if duplicate, addToTree left tree unchanged; loop continues */
|
|
}
|
|
|
|
/* extract values from tree (in-order) into arr[0..len-2] */
|
|
unsigned int idx = 0;
|
|
void *data = nextTreeData(root); // initializes iterator
|
|
while (data != NULL && idx < len - 1) {
|
|
arr[idx++] = *(unsigned int *)data;
|
|
data = nextTreeData(NULL);
|
|
}
|
|
|
|
if (idx != len - 1) {
|
|
clearTree(root);
|
|
free(arr);
|
|
return NULL;
|
|
}
|
|
|
|
/* pick a random existing index and duplicate it */
|
|
unsigned int dupIndex = (unsigned int)(rand() % (len - 1));
|
|
arr[len - 1] = arr[dupIndex];
|
|
|
|
/* free tree memory */
|
|
clearTree(root);
|
|
|
|
/* shuffle array */
|
|
for (unsigned int i = len - 1; i > 0; --i) {
|
|
unsigned int j = (unsigned int)(rand() % (i + 1));
|
|
unsigned int tmp = arr[i];
|
|
arr[i] = arr[j];
|
|
arr[j] = tmp;
|
|
}
|
|
|
|
return arr;
|
|
}
|
|
|
|
// Returns only the only number in numbers which is present twice. Returns zero on errors.
|
|
unsigned int getDuplicate(const unsigned int numbers[], unsigned int len)
|
|
{
|
|
if (numbers == NULL || len < 2) return 0;
|
|
|
|
TreeNode *root = NULL;
|
|
for (unsigned int i = 0; i < len; ++i) {
|
|
unsigned int v = numbers[i];
|
|
int isDup = 0;
|
|
TreeNode *newRoot = addToTree(root, &v, sizeof(unsigned int), compareUnsigned, &isDup);
|
|
if (newRoot == NULL && root != NULL) { // allocation failed
|
|
clearTree(root);
|
|
return 0;
|
|
}
|
|
root = newRoot;
|
|
if (isDup) {
|
|
clearTree(root);
|
|
return v;
|
|
}
|
|
}
|
|
|
|
clearTree(root);
|
|
return 0;
|
|
} |