//  Swarming simulation
//
//  Author  Matthew Caryl
//  Created 13.12.96
//  Modified 27.2.01
//
//  Although under copywrite to the author (Matthew Caryl) this code can be copied and modified for non-commercial
//  purposes as long as any derivatives contain this condition.

package Swarm;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Polygon;
import java.awt.Event;
import java.applet.Applet;
import ADT.Queue;
import ADT.Random;
import ADT.BSPT;
import java.lang.Thread;
import java.lang.Runnable;
import java.lang.Integer;
import java.lang.String;
import java.lang.System;
import java.lang.Math;
import java.util.Date;

public final class World extends Applet implements Runnable {
    //
    // Private interface
    //

    private static final Color      backgroundColor = Color.black;
    private static final Color      outlineColor = Color.white;
    
    private Thread          animation;
    private float			frameTime = 40;
    private Control         control;
    private Graphics        graphics;
    private Random          random = new Random();
    
    private BSPT            bspt;
    private Bot[]           allBots;
    private int             currentBots;
    private int             requiredBots;
    private Kestrel         kestrel;
    private int             wait = 1;
    // I would like to synchronise on allBots but this gives errors so here is a dummy queue to use instead
    private Queue           dummy = new Queue();
    
    // sorting using a recursive bubble sort
    // this gives a marginally faster implementation
    private void bubblesort(int left, int right) {
        if (left < right) {
            int h = (int) ((right - left) / 2) + left;
            
            bubblesort(left, h);
            bubblesort(h + 1, right);
            
            boolean sorted = false;
            for (int i = h; !sorted; i--) {
                sorted = true;
                for (int j = left; j < right; j++)
                    if (allBots[j].x() > allBots[j + 1].x()) {
                        Bot swap = allBots[j];
                        allBots[j] = allBots[j + 1];
                        allBots[j + 1] = swap;
                        sorted = false;
                        }
                }
            }
        }
    
    // sorting using quicksort
    private void quicksort(int left, int right) {
        if (left < right) {
            int l, r;
            int x = allBots[left].x();
            
            for (l = left + 1, r = right; l <= r;)
                if (allBots[l].x() < x)
                    l++;
                else if (allBots[r].x() >= x)
                    r--;
                else {
                    // swap l with r
                    Bot swap = allBots[l];
                    allBots[l] = allBots[r];
                    allBots[r] = swap;
                    l++;
                    r--;
                    }
            // swap left with l-1
            Bot swap = allBots[left];
            allBots[left] = allBots[l - 1];
            allBots[l - 1] = swap;
            quicksort(left, l - 2);
            quicksort(l, right);
            }
        }
    
    // search back in area of allBots for all physicals >= x
    // if none are found return right + 1
    // using binary search seems slightly slower
    private int searchLeft(int left, int right, int x) {
        int i;
        
        for (i = right; i >= left && allBots[i].x() >= x; i--)
            ; // do nothing
        return i + 1;
        }
    
    // search forward in area of allBots for all physicals <= x
    // if none are found return left - 1
    // using binary search seems slightly slower
    private int searchRight(int left, int right, int x) {
        int i;
        
        for (i = left; i <= right && allBots[i].x() <= x; i++)
            ; // do nothing
        return i - 1;
        }
    
    // set nearest neighbours for allBots in range [left, right]
    // return distance of farthest neighbour in range
    //
    // Further speed improvements may be possible if neighbours were sorted by y value
    // upon return.  Then only neighbours clustered on y axis would need be presented
    // to each other.  However, this would slow the process of finding leftmost and
    // rightmost neighbours.
    private int neighbours(int left, int right) {
        if (left + Bot.MINIMUM_SWARM < right) {
            int h = (int) ((right - left) / 2) + left;
            int farthest_left = neighbours(left, h);
            int farthest_right = neighbours(h + 1, right);
            int l = searchLeft(left, h, allBots[h + 1].x() - farthest_right);
            int r = searchRight(h + 1, right, allBots[h].x() + farthest_left);

            // present right hand bots as possible neighbours to left hand bots
            for (int i = l; i <= h; i++) {
                Bot b = allBots[i];
                
                for (int j = h + 1; j <= r; j++)
                    b.possibleNeighbour(allBots[j]);
                }
            
            // present left hand bots as possible neighbours to right hand bots
            for (int i = h + 1; i <= r; i++) {
                Bot b = allBots[i];
                
                for (int j = l; j <= h; j++)
                    b.possibleNeighbour(allBots[j]);
                }
            
            // find farthest neighbour distance
            if (farthest_left > farthest_right)
                return farthest_left;
            else
                return farthest_right;
            }
        else {
            // base case alert bots that new neighbours are being found
            // present bots clustered on x axis as possible neighbours
            
            int farthest = 0;
            for (int i = left; i <= right; i++) {
                allBots[i].newNeighbours();
                
                for (int j = left; j < i; j++)
                    allBots[i].possibleNeighbour(allBots[j]);
                for (int j = i + 1; j <= right; j++)
                    allBots[i].possibleNeighbour(allBots[j]);
                if (allBots[i].farthest() > farthest)
                    farthest = allBots[i].farthest();
                }
            return farthest;
            }
        }
    
    // place bot in world without colliding with scenery
    private void placeBot(Bot b) {
        while (bspt.in(b.x(), b.y(), b.radius())) {
            b.set(random.range(width()), random.range(height()));
            }
        allBots[currentBots] = b;
        currentBots++;
        }
    
    // non-locked removal of bot
    void baseRemove(Bot b) {
        b.set(-width(), -height()); // move so no longer a neighbour of anything
        graphics.setColor(backgroundColor);
        b.erase(graphics);
        
        // locate and remove
        int i, j;
        for (i = 0; allBots[i] != b; i++)
            ; // do nothing
        for (currentBots--; i < currentBots; i++)
            allBots[i] = allBots[i + 1];
        }
    
    // non-locked clone replacement
    void baseReplace() {
        // clone replacement from existing bot
        Bot b = allBots[random.range(currentBots)];
        while (b instanceof Kestrel)
            b = allBots[random.range(currentBots)];
        b = new Sparrow((Sparrow) b);
        placeBot(b);
        }

    //
    // Package interface
    //
    
    // redo all bots
    void reset() {
        synchronized (dummy) {
            currentBots = 0;
            allBots = new Bot[requiredBots + 1]; // additional place for kestrel
            
            // check for previous presence of kestrel
            if (kestrelOn()) {
                kestrel = new Kestrel(this, -1, -1);
                placeBot(kestrel);
                }
            else
                kestrel = null;
            
            // add swarm
            for (int i = requiredBots; i > 0; i--)
                placeBot(new Sparrow(this, -1, -1));
            
            // allocate starting neighbours from beginning of allBots
            Bot[] neighbours = new Bot[Bot.MINIMUM_NEIGHBOURS];
            // easy for most of them, just given them those early in the list
            for (int i = Bot.MINIMUM_NEIGHBOURS - 1; i >= 0; i--)
                neighbours[i] = allBots[i];
            for (int i = currentBots - 1; i >= Bot.MINIMUM_NEIGHBOURS; i--)
                allBots[i].addNeighbours(neighbours);
            // for those early allBots, they cannot be neighbour to themselves
            for (int i = Bot.MINIMUM_NEIGHBOURS - 1; i >= 0; i--) {
                for (int j = Bot.MINIMUM_NEIGHBOURS, k = Bot.MINIMUM_NEIGHBOURS - 1; j >= 0; j--)
                    if (i != j) {
                        neighbours[k] = allBots[j];
                        k--;
                        }
                allBots[i].addNeighbours(neighbours);
                }
            paint(graphics);
            }
        }
    
    // supply random number generator
    Random random() {
        return random;
        }

    // applet width
    int width() {
        return size().width;
        }
    
    // applet height
    int height() {
        return size().height;
        }
    
    // replace dead bot with new one
    void remove(Bot b) {
        synchronized (dummy) {
            baseRemove(b);
            baseReplace();
            }
        }
    
    // return kestrel if it exists
    Bot kestrel() {
        return kestrel;
        }
    
    // allow control panel to be opened again
    void controlOff() {
        control = null;
        }
    
    // current number of bots
    int numberBots() {
        synchronized (dummy) {
            return currentBots - (kestrelOn() ? 1 : 0);
            }
        }
    
    // set current number of bots
    void numberBots(int size) {
        synchronized (dummy) {
            requiredBots = size;
            // increase up to new number
            if (requiredBots > allBots.length) {
                Bot[] a = new Bot[requiredBots + 1]; // free space for kestrel
                for (int i = currentBots - 1; i >= 0; i--)
                    a[i] = allBots[i];
                allBots = a;
                }
            for (int i = requiredBots - numberBots(); i > 0; i--)
                baseReplace();
            // decrease down to new number
            for (int i = numberBots() - requiredBots; i > 0; i--) {
                // locate and remove
                int j = random.range(currentBots);
                while (allBots[j] instanceof Kestrel)
                    j = random.range(currentBots);
                baseRemove(allBots[j]);
                }
            }
        }
    
    // is kestrel present
    boolean kestrelOn() {
        return kestrel != null;
        }
    
    // set presence of kestrel
    void kestrelOn(boolean on) {
        synchronized (dummy) {
            if (kestrelOn() == on)
                return;
            
            // add new kestrel
            if (on) {
                kestrel = new Kestrel(this, -1, -1);
                Bot[] neighbours = new Bot[Bot.MINIMUM_NEIGHBOURS];
                for (int i = Bot.MINIMUM_NEIGHBOURS - 1; i >= 0; i--)
                    neighbours[i] = allBots[i];
                kestrel.addNeighbours(neighbours);
                placeBot(kestrel);
                return;
                }
            
            // remove old kestrel
            baseRemove(kestrel);
            kestrel = null;
            }
        }

    //
    // Public world interface
    //
    
    // once only initialisation
    public void init() {
        super.init();
        setBackground(backgroundColor);

        // save graphics context for later
        // note: this seems to reduce garbage collection problems
        graphics = this.getGraphics();
        
        // create boundary wall
        int[] wallx = {0, 0, width(), width(), 0};
        int[] wally = {0, height(), height(), 0, 0};
        Polygon[] polygons = {new Polygon(wallx, wally, 5)};
        bspt = new BSPT(polygons);
        
        // read in swarm size
        String botString = this.getParameter("numberPrey");
        try {
            requiredBots = Integer.parseInt(botString);
            if (requiredBots < Bot.MINIMUM_SWARM)
                throw new NumberFormatException("Must be at least " + Bot.MINIMUM_SWARM + " prey.");
            }
        catch (NumberFormatException e) {requiredBots = Bot.MINIMUM_SWARM;}
        
        // is hunter required
        String hunterString = this.getParameter("hunterOn");
        // set kestrel to non-null
        if ("yes".equals(hunterString))
            kestrel = new Kestrel(this, -1, -1);
        
        // how fast do we go
        String frameRateString = this.getParameter("frameRate");
        try {
        	frameTime = (float) 1000 / (float) Integer.parseInt(frameRateString);
        	}
        catch (NumberFormatException e) {
        	// do nothing
        	}
        
        reset();
        }
    
    // free all resources
    public void destroy() {
        super.destroy();
        if (animation != null && animation.isAlive())
            animation.stop();
        if (control != null)
            control.dispose();
        if (graphics != null)
            graphics.dispose();
        }
    
    // start animation
    public void start() {
        synchronized (dummy) {
            // check locking level
            if (wait == 0)
                return;
            // decrement locking level
            wait--;
            // check locking level
            if (wait == 0) {
                if (animation == null) {
                    animation = new Thread(this);
                    animation.start();
                    }
                else
                    animation.resume();
                }
            }
        }
    
    // stop anmation
    public void stop() {
        synchronized (dummy) {
            // check locking level
            if (wait == 0 && animation != null && animation.isAlive())
                animation.suspend();
            // increment locking level
            wait++;
            }
        }

    // animation sequence
    public void run() {
        while (true) {
        	long Time = System.currentTimeMillis();
        	
            synchronized (dummy) {
                // find nearest neighbours
                bubblesort(0, currentBots - 1);
                neighbours(0, currentBots - 1);
                // tick for all bots
                for (int i = currentBots - 1; i >= 0; i--) {
                    allBots[i].tick();
                    if (bspt.in(allBots[i].x(), allBots[i].y(), allBots[i].radius()))
                        allBots[i].collision(false);
                    graphics.setColor(backgroundColor);
                    allBots[i].erase(graphics);
                    allBots[i].paint(graphics);
                    }
                }
            
            // slow thread down
            try {
            	long sleepTime = (long)(frameTime - (float) System.currentTimeMillis() + (float) Time);
            	
            	System.out.println(sleepTime);
            	
                animation.sleep(Math.max(0, sleepTime));
                }
            catch (InterruptedException e) {
                // do nothing
                }
            }
        }

    // display background but not animation
    public void paint(Graphics g) {
        g.setColor(backgroundColor);
        g.fillRect(0, 0, width(), height());
        bspt.draw(g);
        }

    // perhaps create new control panel
    public boolean mouseDown(Event e, int x, int y) {
        if (control == null)
            control = new Control(this);
        return true;
        }
    
    // return parameter information
    public String[][] getParameterInfo() {
        String[][] info = { {"numberPrey ", "positive integer ", "number of bodies in swarm"}, 
                            {"hunterOn ", "yes/no ", "hunter present"} };
        
        return info;
        }
    }