#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*#include <assert.h>*/

#define ITERATIONS 100000
#define MAX_SIZE 200
#define BITMAP_SIZE ((MAX_SIZE / 32)+1)

#define RANDOM_DOUBLE() ((double)rand()/(RAND_MAX+1))
#define RANDOM_INT(x)   ((int)x*(double)rand()/(RAND_MAX+1))

typedef unsigned int uint;
typedef unsigned char uchar;

typedef struct List {
    uint size;
    uint data[MAX_SIZE];
    uint bitmap[BITMAP_SIZE];
} List;

void List_init(List *this)
{
    memset(this,0,sizeof(List));
}

int List_contains(List *this,uint i)
{
    return 0 != (this->bitmap[i >> 5] & ((uint)1 << (i & 31)));
}

void List_set(List *this,uint i)
{
    /*assert(!List_contains(this,i));*/
    this->data[this->size++] = i;
    this->bitmap[i >> 5] |= ((uint)1 << (i & 31));
}

void List_remove(List *this,uint i)
{
    /*assert(List_contains(this,i));*/
    int j = 0;
    while (j < this->size && this->data[j] != i) {
	j++;
    }
    if (j < this->size) {
	for (int k=j;k<this->size;k++)
	    this->data[k] = this->data[k+1];
	this->size--;
	this->bitmap[i >> 5] &= ~((uint)1 << (i & 31));
    }
}

int List_empty(List *this)
{
    return this->size == 0;
}

void List_shuffle(List *this)
{
    List_init(this);
    for (int i=0;i<MAX_SIZE;i++) {
        List_set(this,i);
    }
    for (int i=0;i<MAX_SIZE;i++) {
        int j = RANDOM_INT(MAX_SIZE);
        int tmp       = this->data[i];
        this->data[i] = this->data[j];
        this->data[j] = tmp;
    }
}

void List_mutate(List *this)
{
    for (int i=0;i<MAX_SIZE-1;i++) {
        if (RANDOM_DOUBLE() < 0.1) {
            int tmp         = this->data[i];
            this->data[i]   = this->data[i+1];
            this->data[i+1] = tmp;
        }
    }
}

void cross(List *l1, List *l2, List *out)
{
    List_init(out);

    int idx = RANDOM_INT(MAX_SIZE);

    for (int i=0;i<idx;i++) {
        List_set(out,l1->data[i]);
    }
    for (int i=0;i<MAX_SIZE;i++) {
        if (!List_contains(out,l2->data[i]))
            List_set(out,l2->data[i]);
    }
    List_mutate(out);
}

int main(int argc, char *argv[])
{
    List list1,list2,list3;

    for (int i=0;i<ITERATIONS;i++) {
        /*printf("%d\n",i);*/
        /*List_init(&list1);*/
        List_shuffle(&list1);
        /*List_init(&list2);*/
        List_shuffle(&list2);

        cross(&list1,&list2,&list3);
    }
    return 0;
}