// Collision Detection Tests
//
// What is best -
//   ordinary quadratic collision detection
//   quadratic collision detection with buckets
//   n.logn collision detection
//   n.logn collision detection with buckets
//
// Author  Matthew Caryl
// Created 11.5.97
//
// For an explaination of the sorting algorithms look at Java version.

#include <iostream.h>

#define null 0L

class Bot
{
    public:
    
    long x;
    long y;
    long r;
    
    long dx;
    long dy;
    
    bool collision;
};
typedef Bot* BotP;

void initialiseRandom(void);
long random(long range);
void tick(BotP bots, long number, long range);
BotP createBots(long number, long radius, long range);
long cycle(long number, long size, long time, long range);
void setup(BotP bots, long number);
void setdown(BotP bots, long number);
void collision(BotP bots, long number);
long newRecursiveCollision(BotP* bots, long left, long right);
long searchRight(BotP* bots, long left, long right, long x);
long searchLeft(BotP* bots, long left, long right, long x);
void quickSort(BotP* bots, long left, long right);
void bubbleSort(BotP* bots, int left, int right);
void insertionSort(BotP* bots, int left, int right);
void iSort(BotP* bots, int left, int right);
void bSort(BotP* bots, int left, int right);
void ciSort(BotP* bots, int left, int right);
void swap(BotP bots, long x, long y);
long max(long x, long y);
long sqr(long n);

unsigned long seed;

void initialiseRandom(void)
{
    seed = 0;
}

long random(long range)
{
    seed = seed * 1103515245 + 12345;
    return (unsigned long) ((seed / 65536) & (range - 1));
}

void tick(BotP bots, long number, long range)
{
    BotP    p;
    
    for (p = bots + number - 1; p >= bots; p--)
        {
        p->x = (p->x + p->dx) & (range - 1);
        p->y = (p->y + p->dy) & (range - 1);
        }
}

BotP createBots(long number, long radius, long range)
{
    BotP bots = new Bot[number];
    
    BotP p;
    
    for (p = bots + number - 1; p >= bots; p--)
        {
        p->x = random(range);
        p->y = random(range);
        p->r = radius;
        p->dx = random(15) - 7;
        p->dy = random(15) - 7;
        }
    return bots;
}

long cycle(long number, long size, long time, long range)
{
    initialiseRandom();
    
    BotP bots = createBots(number, size, range);
    long count;
    long start, finish, ticks;
    
    setup(bots, number);
        
    count = 0;
    start = ticks = TickCount();
    finish = TickCount() + time * 60;
    
    while (ticks < finish)
        {
        collision(bots, number);
        tick(bots, number, range);
        count++;
        ticks = TickCount();
        }
    
    setdown(bots, number);
    
    delete bots;
    
    return count;
}

inline long sqr(long n)
{
    return n * n;
}

inline void swap(BotP* bots, long x, long y)
{
    BotP swap = bots[x];
    bots[x] = bots[y];
    bots[y] = swap;
}

inline long max(long x, long y)
{
    if (x > y)
        return x;
    else
        return y;
}

void bSort(BotP* bots, int left, int right)
{
    if (left < right)
        {
        bool sorted = false;
        for (int r = right; left < r; r--)
            {
            sorted = true;
            for (int j = left; j < r; j++)
                if (bots[j]->x > bots[j + 1]->x)
                    {
                    BotP swap = bots[j];
                    bots[j] = bots[j + 1];
                    bots[j + 1] = swap;
                    sorted = false;
                    }
            if (sorted)
                return;
            }
        }
}

void iSort(BotP* bots, int left, int right)
{
    for (int i = left + 1; i < right;)
        {
        if (bots[i]->x > bots[right]->x)
            {
            BotP swap = bots[i];
            for (int j = i; j < right; j++)
                bots[j] = bots[j + 1];
            bots[right] = swap;
            }
        else if (bots[i]->x > bots[i + 1]->x)
            {
            int j;
            BotP swap = bots[i];
            bots[i] = bots[i + 1];
            for (j = i + 2; swap->x > bots[j]->x; j++)
                bots[j - 1] = bots[j];
            bots[j - 1] = swap;
            }
        else if (bots[i]->x < bots[left]->x)
            {
            BotP swap = bots[i];
            for (int j = i; j > left; j--)
                bots[j] = bots[j - 1];
            bots[left] = swap;
            }
        else if (bots[i]->x < bots[i - 1]->x)
            {
            int j;
            BotP swap = bots[i];
            bots[i] = bots[i - 1];
            for (j = i - 2; swap->x < bots[j]->x; j--)
                bots[j + 1] = bots[j];
            bots[j + 1] = swap;
            }
        else
            i++;
        }
}

void insertionSort(BotP* bots, int left, int right)
{
    if (left < right)
        {
        int h = (right - left) / 2 + left;
        
        insertionSort(bots, left, h);
        insertionSort(bots, h + 1, right);
        
        if (bots[h]->x > bots[right]->x)
            {
            BotP swap = bots[h];
            for (int i = h; i < right; i++)
                bots[i] = bots[i + 1];
            bots[right] = swap;
            h--;
            if (h < left)
                return;
            }
        
        if (bots[left]->x > bots[h + 1]->x)
            {
            BotP swap = bots[left];
            for (int i = left; i <= h; i++)
                bots[i] = bots[i + 1];
            bots[h + 1] = swap;
            h++;
            if (h > right)
                return;
            }
        
        for (int l = h; bots[l]->x > bots[l + 1]->x; l--)
            {
            int i;
            BotP swap = bots[l];
            bots[l] = bots[l + 1];
            for (i = l + 2; swap->x > bots[i]->x; i++)
                bots[i - 1] = bots[i];
            bots[i - 1] = swap;
            }
        }
}

void bubbleSort(BotP* bots, int left, int right)
{
    if (left < right)
        {
        int h = (right - left) / 2 + left;
        
        bubbleSort(bots, left, h);
        bubbleSort(bots, h + 1, right);
        
        bool sorted = false;
        for (int l = h, r = right; l >= left; l--, r--)
            {
            sorted = true;
            for (int j = l; j < r; j++)
                if (bots[j]->x > bots[j + 1]->x)
                    {
                    BotP swap = bots[j];
                    bots[j] = bots[j + 1];
                    bots[j + 1] = swap;
                    sorted = false;
                    }
            if (sorted)
                return;
            }
        }
}

void quickSort(BotP* bots, long left, long right)
{
    if (left < right)
        {
        long h = (right - left) / 2 + left;
        long l, r;
        long x = bots[left]->x;
        
        for (l = left + 1, r = right; l <= r;)
            if (bots[l]->x < x)
                l++;
            else if (bots[r]->x >= x)
                r--;
            else
                {
                swap(bots, l, r);
                l++;
                r--;
                }
        swap(bots, left, l - 1);
        quickSort(bots, left, l - 2);
        quickSort(bots, l, right);
        }
}

long searchLeft(BotP* bots, long left, long right, long x)
{
    long i;
    
    for (i = right; bots[i]->x >= x; i--)
        if (i == left)
            return left;
    return i + 1;
}

long searchRight(BotP* bots, long left, long right, long x)
{
    long i;
    
    for (i = left; bots[i]->x <= x; i++)
        if (i == right)
            return right;
    return i - 1;
}

long newRecursiveCollision(BotP* bots, long left, long right)
{
    if (left < right)
        {
        long h = (right - left) / 2 + left;
        long left_radius = newRecursiveCollision(bots, left, h);
        long right_radius = newRecursiveCollision(bots, h + 1, right);
        long radius = left_radius + right_radius;
        long l = searchLeft(bots, left, h, bots[h + 1]->x - radius);
        long r = searchRight(bots, h + 1, right, bots[h]->x + radius);

        for (long i = h + 1; i <= r; i++)
            {
            BotP p = bots[i];
            
            for (long j = l; j <= h; j++)
                {
                BotP q = bots[j];
                
                if (sqr(p->x - q->x) + sqr(p->y - q->y) < sqr(p->r + q->r))
                    {
                    p->collision = true;
                    q->collision = true;
                    }
                }
            }
        
        return max(left_radius, right_radius);
        }
    else
        return bots[left]->r;
}

BotP* new_bot_pointer_list;

void collision(BotP, long number)
{
    iSort(new_bot_pointer_list, 0, number - 1);
    newRecursiveCollision(new_bot_pointer_list, 0, number - 1);
}

void setup(BotP bots, long number)
{
    new_bot_pointer_list = (BotP*) malloc(sizeof(BotP) * number);
    for (int i = number - 1; i >= 0; i--)
        new_bot_pointer_list[i] = &bots[i];
}

void setdown(BotP, long)
{
    delete new_bot_pointer_list;
}

void main(void)
{
    long time = 1;
    long count;
    long base_range = 128;
    
    for (long number = 2; number <= 512; number *= 4, base_range *= 2)
        for (long size = 4, range = base_range; size <= 32; size *= 2, range *= 2)
            {
            count = cycle(number, size, time, range);
            cout << time << " seconds " << number << " objects of size " << size << " gives density of ";
            cout << 100 * (3.14 * size * size * number) / (range * range);
            cout << "% - " << count << " cycles." << "\r";
            }
}