//  Collision detection test
//
//  Author  Matthew Caryl
//  Created 26.5.97

package Test;

import java.awt.*;
import java.applet.*;
import ADT.*;

public final class ClosestPairTest extends Applet implements Runnable {
    //
    // Private interface
    //
    
    private Thread          animation;
    private Graphics        graphics;
    private Random          random = new Random(0);
    
    //
    // Public world interface
    //
    
    public void init() {
        setBackground(Color.black);

        // save graphics context for later
        // note: this seems to reduce garbage collection problems
        graphics = this.getGraphics();
        }
    
    public void destroy() {
        if (animation != null && animation.isAlive())
            animation.stop();
        if (graphics != null)
            graphics.dispose();
        super.destroy();
        }

     public void start() {
        if (animation == null) {
            animation = new Thread(this);
            animation.start();
            }
        else
            animation.resume();
        }
    
    public void stop() {
        if (animation != null && animation.isAlive())
            animation.suspend();
        }

    public void run() {
        int width = size().width;
        // create 16 bots of radius 16 with positions in ([0..width-1], [0..width-1)
        Bot[] bots = createBots(16, 16, width);
        
        while (true) {
            long ticks = System.currentTimeMillis();
            
            erase(bots);
            tick(bots, width);
            // perform appropriate sorting algorithm
            insertionSort(bots, 0, bots.length - 1);
            // ensure bots are in sorted order
            check(bots);
            collision(bots, 0, bots.length - 1);
            display(bots, Color.white);
            
            try {
                animation.sleep(Math.max(100, 100 - (System.currentTimeMillis() - ticks)));
                }
            catch (InterruptedException e) {
                // do nothing
                }
            }
        }
    
    public void erase(Bot[] bots) {
        graphics.setColor(Color.black);
        
        for (int i = bots.length - 1; i >= 0; i--) {
            Bot b = bots[i];
            if (b.collision)
                graphics.fillOval(b.x - b.r / 2, b.y - b.r / 2, 2 * b.r, 2 * b.r);
            else
                graphics.drawOval(b.x - b.r / 2, b.y - b.r / 2, 2 * b.r, 2 * b.r);
            b.collision = false;
            }
        }
    
    public void display(Bot[] bots, Color color) {
        graphics.setColor(color);
        
        for (int i = bots.length - 1; i >= 0; i--) {
            Bot b = bots[i];
            if (b.collision)
                graphics.fillOval(b.x - b.r / 2, b.y - b.r / 2, 2 * b.r, 2 * b.r);
            else
                graphics.drawOval(b.x - b.r / 2, b.y - b.r / 2, 2 * b.r, 2 * b.r);
            }
        }
    
    public void check(Bot[] bots) {
        int x = bots[bots.length - 1].x;
        boolean right = true;
        
        for (int i = bots.length - 2; i >= 0; i--) {
            if (bots[i].x > x)
                right = false;
            x = bots[i].x;
            }
        if (!right) {
        	// old x coordinates used to give idea of what went wrong with sorting
            for (int i = bots.length - 1; i >= 0; i--)
                System.out.print(bots[i].ox + " ");
            System.out.println();
            for (int i = bots.length - 1; i >= 0; i--)
                System.out.print(bots[i].x + " ");
            System.out.println();
            System.out.println();
            }
        }
                
    public Bot[] createBots(int number, int radius, int range) {
        Bot[] bots = new Bot[number];
        
        for (int i = bots.length - 1; i >= 0; i--) {
            Bot b = new Bot();
            
            b.x = random.range(range);
            b.y = random.range(range);
            b.r = radius;
            b.dx = random.range(15) - 7;
            b.dy = random.range(15) - 7;
            bots[i] = b;
            }
        return bots;
        }
    
    public void tick(Bot[] bots, int range) {
        for (int i = bots.length - 1; i >= 0; i--) {
            Bot b = bots[i];
            b.ox = b.x;
            b.oy = b.y;
            b.x = (b.x + b.dx) & (range - 1);
            b.y = (b.y + b.dy) & (range - 1);
            }
        }
    
    public int searchLeft(Bot[] bots, int left, int right, int x) {
        int i;
        
        for (i = right; bots[i].x >= x; i--)
            if (i == left)
                return left;
        return i + 1;
        }
    
    int searchRight(Bot[] bots, int left, int right, int x) {
        int i;
        
        for (i = left; bots[i].x <= x; i++)
            if (i == right)
                return right;
        return i - 1;
        }

    public int max(int x, int y) {
        if (x > y)
            return x;
        else
            return y;
        }
    
    public int collision(Bot[] bots, int left, int right) {
        if (left < right) {
            int h = (right - left) / 2 + left;
            int radius = collision(bots, left, h) + collision(bots, h + 1, right);
            int l = searchLeft(bots, left, h, bots[h + 1].x - radius);
            int r = searchRight(bots, h + 1, right, bots[h].x + radius);
    
            for (int i = h + 1; i <= r; i++) {
                Bot p = bots[i];
                
                for (int j = l; j <= h; j++) {
                    Bot q = bots[j];
                    
                    int dx = (p.x - q.x);
                    int dy = (p.y - q.y);
                    int dr = (p.r + q.r);
                    
                    if (dx * dx + dy * dy <= dr * dr) {
                        p.collision = true;
                        q.collision = true;
                        }
                    }
                }
            
            return radius;
            }
        else
            return bots[left].r;
        }
    
    public void swap(Bot[] bots, int x, int y) {
        Bot swap = bots[x];
        bots[x] = bots[y];
        bots[y] = swap;
        }

    public void quickSort(Bot[] bots, int left, int right) {
        if (left < right) {
            int h = (right - left) / 2 + left;
            int l, r;
            int 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);
            }
        }
    
    // ordinary bubble sort
    void bSort(Bot[] bots, int left, int right) {
        if (left < right) {
            boolean 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) {
                        Bot swap = bots[j];
                        bots[j] = bots[j + 1];
                        bots[j + 1] = swap;
                        sorted = false;
                        }
                if (sorted)
                    return;
                }
            }
        }
    
    // recursive bubble sort
    public void bubbleSort(Bot[] bots, int left, int right) {
        if (left < right) {
            int h = (right - left) / 2 + left;
            
            bubbleSort(bots, left, h);
            bubbleSort(bots, h + 1, right);
            
            // work from center where any problems will be found
            boolean 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) {
                        Bot swap = bots[j];
                        bots[j] = bots[j + 1];
                        bots[j + 1] = swap;
                        sorted = false;
                        }
                if (sorted)
                    return;
                }
            }
        }
    
    // insertion sort but not like anything normally used
    void iSort(Bot[] bots, int left, int right) {
        for (int i = left + 1; i < right;) {
        	// move bot to far right if need be
            if (bots[i].x > bots[right].x) {
                Bot swap = bots[i];
                for (int j = i; j < right; j++)
                    bots[j] = bots[j + 1];
                bots[right] = swap;
                }
            // or slightly to the right
            // no need to check array bounds because of previous case
            else if (bots[i].x > bots[i + 1].x) {
                int j;
                Bot 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;
                }
            // move bot to far left if need be
            else if (bots[i].x < bots[left].x) {
                Bot swap = bots[i];
                for (int j = i; j > left; j--)
                    bots[j] = bots[j - 1];
                bots[left] = swap;
                }
            // or slightly to the left
            // no need to check array bounds because of previous case
            else if (bots[i].x < bots[i - 1].x) {
                int j;
                Bot 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;
                }
            // if everything is alright then move on
            else
                i++;
            }
        }
    
    // recursive insertion sort
    void insertionSort(Bot[] bots, int left, int right) {
        if (left < right) {
            int h = (right - left) / 2 + left;
            
            insertionSort(bots, left, h);
            insertionSort(bots, h + 1, right);
            // there are now definitely two sorted halves
            // the total array may already be sorted
            
            // ensure largest value is rightmost
            if (bots[h].x > bots[right].x) {
                Bot swap = bots[h];
                for (int i = h; i < right; i++)
                    bots[i] = bots[i + 1];
                bots[right] = swap;
                h--;
                if (h < left)
                    return;
                }
            
            // and smallest value is left most
            if (bots[h + 1].x < bots[left].x) {
                Bot swap = bots[h + 1];
                for (int i = h + 1; i > left; i--)
                    bots[i] = bots[i - 1];
                bots[left] = swap;
                h++;
                if (h > right)
                    return;
                }
            
            // work at middle and reorder any problem bots
            for (int l = h; bots[l].x > bots[l + 1].x; l--) {
                int i;
                Bot 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;
                }
            }
        }
    }