// 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
//
// THIS CODE IN UNFINISHED.  DO NOT ATTEMPT TO RUN.
// ONLY WORK WITH THIS CODE IF YOU KNOW EXACTLY WHAT YOU ARE DOING.

#include <iostream.h>

#define null 0L

class Bot;
class Bucket;
class Universe;

typedef Bot* BotP;
typedef Bucket* BucketP;
typedef Universe* UniverseP;

////////////////////////////////////////////////////////////////////////////////////////////////
// random number generation
////////////////////////////////////////////////////////////////////////////////////////////////

void initialiseRandom(void);
long random(long range);

unsigned long seed;

void initialiseRandom(void)
{
    seed = 0;
}

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

////////////////////////////////////////////////////////////////////////////////////////////////
// bot class
////////////////////////////////////////////////////////////////////////////////////////////////

class Bot
{
    public:
    Bot(void);
    
    void initialise(long radius, long range);
    
    long x, y;
    long r;
    long dx, dy;
    
    BotP next, prev;
    BucketP home;
};

Bot::Bot(void)
{
    next = this;
    prev = this;
    home = null;
}

void Bot::initialise(long radius, long range)
{
    x = random(range);
    y = random(range);
    r = radius;
    dx = random(15) - 7;
    dy = random(15) - 7;
}

////////////////////////////////////////////////////////////////////////////////////////////////
// bucket class
////////////////////////////////////////////////////////////////////////////////////////////////

class Bucket
{
    public:
    Bucket(void);
    Bucket(long t, long l, long b, long r);
    ~Bucket(void);
    
    void initialise(long t, long l, long b, long r, BucketP p);
    void setNeighbours(BucketP n, BucketP e, BucketP s, BucketP w);
    bool out(long x, long y);
    void move(BotP bot);
    void add(BotP bot);
    void sub(BotP bot);
    void pushDown(BucketP NE, BucketP NW, BucketP SE, BucketP SW);
    void pullUp(void);
    
    BucketP north, east, south, west;
    BucketP ne, nw, se, sw;
    long top, left, bottom, right;
    
    BotP bots;
    long number;
    
    BucketP next, prev;
    BucketP parent;
};

Bucket::Bucket(void)
{
    initialise(0, 0, 0, 0, null);
    
    bots = new Bot;
    number = 0;
    
    next = this;
    prev = this;
}

Bucket::Bucket(long t, long l, long b, long r)
{
    initialise(t, l, b, r, null);
    
    bots = new Bot;
    number = 0;
    
    next = this;
    prev = this;
}

Bucket::~Bucket(void) 
{
    delete bots;
}

void Bucket::initialise(long t, long l, long b, long r, BucketP p)
{
    top = t;
    bottom = b;
    left = l;
    right = r;
    
    north = null;
    south = null;
    east = null;
    west = null;
    
    ne = null;
    nw = null;
    se = null;
    sw = null;
    
    parent = p;
}

void Bucket::setNeighbours(BucketP n, BucketP e, BucketP s, BucketP w)
{
    north = n;
    south = s;
    east = e;
    west = w;
}

bool Bucket::out(long x, long y)
{
    return x > right || x < left || y > bottom || y < top;
}

void Bucket::move(BotP bot)
{
    // TEMPORARY
}

void Bucket::add(BotP bot)
{
    bot->next = bots->next;
    bot->prev = bots;
    bot->home = this;
    bots->next->prev = bot;
    bots->next = bot;
    number++;
}

void Bucket::sub(BotP bot)
{
    bot->next->prev = bot->prev;
    bot->prev->next = bot->next;
    number--;
}

void Bucket::pushDown(BucketP NE, BucketP NW, BucketP SE, BucketP SW)
{
    nw = NW;
    ne = NE;
    sw = SE;
    se = SW;
    
    long mid_h = (right + left) / 2;
    long mid_v = (bottom + top) / 2;
    
    nw->initialise(top, left, mid_v, mid_h, this);
    ne->initialise(top, mid_h, mid_v, right, this);
    sw->initialise(mid_v, left, bottom, mid_h, this);
    se->initialise(mid_v, mid_h, bottom, right, this);
    
    nw->setNeighbours((north == null) ? null : ((north->sw == null) ? north : north->sw),
                      ne,
                      sw,
                      (west == null) ? null : ((west->ne == null) ? west : north->sw))
    
    while (bots != bots->next)
        {
        BotP bot = bots->next;
        sub(bot);
        number++;
        
        if (bot->x <= mid_h)
            {
            if (bot->y <= mid_v)
                nw->add(bot);
            else
                ne->add(bot);
            }
        else
            {
            if (bot->y <= mid_v)
                sw->add(bot);
            else
                se->add(bot);
            }
        }
    
}

void Bucket::pullUp(void)
{
    BucketP p;
    
    p = nw;
    while (p->bots != p->bots->next)
        {
        BotP bot = p->bots->next;
        p->sub(bot);
        number--;
        add(bot);
        }
    p = ne;
    while (p->bots != p->bots->next)
        {
        BotP bot = p->bots->next;
        p->sub(bot);
        number--;
        add(bot);
        }
    p = sw;
    while (p->bots != p->bots->next)
        {
        BotP bot = p->bots->next;
        p->sub(bot);
        number--;
        add(bot);
        }
    p = se;
    while (p->bots != p->bots->next)
        {
        BotP bot = p->bots->next;
        p->sub(bot);
        number--;
        add(bot);
        }
}

////////////////////////////////////////////////////////////////////////////////////////////////
// universe class
////////////////////////////////////////////////////////////////////////////////////////////////

class Universe
{
    public:
    Universe(long range, long max);
    ~Universe(void);
    
    void add(BotP bot);
    void sub(BotP bot);
    
    private:
    void addBucket(BucketP bucket);
    void subBucket(BucketP bucket);
    BucketP spareBucket(void);
    void ensureSpares(void);
    
    BucketP buckets;
    long used_number;
    
    BucketP unused_buckets;
    long unused_number;
    
    long maximum;
};

Universe::Universe(long range, long max)
{
    buckets = new Bucket();
    used_number = 0;
    unused_buckets = new Bucket();
    unused_buckets = 0;
    
    maximum = max;
    
    addBucket(new Bucket(0, 0, range - 1, range - 1));
}

Universe::~Universe(void)
{
    while (used_number > 0)
        {
        BucketP b = buckets->next;
        subBucket(b);
        delete b;
        }
    while (unused_number > 0)
        {
        BucketP b = spareBucket();
        delete b;
        }
    delete buckets;
    delete unused_buckets;
}

void Universe::add(BotP bot)
{
    BucketP p = buckets;
    long mid_h, mid_v;
    
    while (p->ne != null)
        {
        mid_h = (p->right + p->left) / 2;
        mid_v = (p->bottom + p->top) / 2;
        
        if (bot->x <= mid_h)
            p = (bot->y <= mid_v) ? p->nw : p->ne;
        else
            p = (bot->y <= mid_v) ? p->sw : p->se;
                
        p->number++;
        }
    
    p->add(bot);
    
    if (p->number == maximum && (p->right - p->left) > 32)
        {
        ensureSpares();
        p->pushDown(spareBucket(), spareBucket(), spareBucket(), spareBucket());
        }
}

void Universe::sub(BotP bot)
{
    BucketP p = bot->home;
    
    p->sub(bot);
    
    if (p->parent != null && p->parent->number < maximum)
        {
        subBucket(p->nw);
        subBucket(p->ne);
        subBucket(p->sw);
        subBucket(p->se);
        p->pullUp();
        }
}

void Universe::addBucket(BucketP bucket)
{
    bucket->next = buckets->next;
    bucket->prev = buckets;
    buckets->next->prev = bucket;
    buckets->next = bucket;
    used_number++;
}

void Universe::subBucket(BucketP bucket)
{
    bucket->next = bucket->prev;
    bucket->prev = bucket->next;
    used_number--;
    bucket->next = unused_buckets->next;
    bucket->prev = unused_buckets;
    unused_buckets->next->prev = bucket;
    unused_buckets->next = bucket;
    unused_buckets++;
}

BucketP Universe::spareBucket(void)
{
    BucketP bucket = unused_buckets->next;
    
    bucket->next = bucket->prev;
    bucket->prev = bucket->next;
    unused_number--;
    
    return bucket;
}

void Universe::ensureSpares(void)
{
    while (unused_number < 4)
        {
        BucketP p = new Bucket();
        addBucket(p);
        subBucket(p);
        }
}

////////////////////////////////////////////////////////////////////////////////////////////////
// main program
////////////////////////////////////////////////////////////////////////////////////////////////

long cycle(long number, long size, long time, long range, int maximum);
void tick(UniverseP universe, BotP bots, long number, long range);
BotP createBots(UniverseP universe, long number, long radius, long range);

BotP createBots(UniverseP universe, long number, long radius, long range)
{
    BotP bots = new Bot[number];
    
    for (BotP p = bots + number - 1; p >= bots; p--)
        {
        p->initialise(radius, range);
        universe->add(p);
        }
    return bots;
}

void tick(UniverseP universe, BotP bots, long number, long range)
{
    for (BotP p = bots + number - 1; p >= bots; p--)
        {
        universe->sub(p);
        p->x = (p->x + p->dx) & (range - 1);
        p->y = (p->y + p->dy) & (range - 1);
        //if (p->home->out(p->x, p->y))
        //  p->home->move(p);
        universe->add(p);
        }
}

long cycle(long number, long size, long time, long range, int maximum)
{
    initialiseRandom();
    
    UniverseP universe = new Universe(range, maximum);
    BotP bots = createBots(universe, number, size, range);
    long count;
    long start, finish, ticks;
    
    count = 0;
    start = ticks = TickCount();
    finish = TickCount() + time * 60;
    
    while (ticks < finish)
        {
        // collision(bots, number);
        tick(universe, bots, number, range);
        count++;
        ticks = TickCount();
        }
    
    delete bots;
    delete universe;
    
    return count;
}

void main(void)
{
    long time = 1;
    long count;
    long base_range = 32;
    
    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, 8);
            cout << time << " seconds " << number << " objects of size " << size << " gives density of ";
            cout << 100 * (3.14 * size * size * number) / (range * range);
            cout << "% - " << count << " cycles." << "\r";
            }
}