// ============================================================================
// File:               $File$
//
// Project:            
//
// Purpose:            
//
// Author:             Rammi
//
// Copyright Notice:   (c) 2008  Rammi (rammi@caff.de)
//                     This code is in the public domain.
//                     Use at own risk.
//                     No guarantees given.
//
// Latest change:      $Date$
//
// History:	       $Log$
//=============================================================================
package de.caff.asteroid.rammi;

import de.caff.asteroid.*;
import de.caff.util.Tools;

import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;


/**
 *  Player for Asteroids shootout.
 *
 *  This class is part of a solution for a
 *  <a href="http://www.heise.de/ct/creativ/08/02/details/">competition by the German computer magazine c't</a>.
 */
public class AsteroidPlayer
        extends AbstractBasicAsteroidPlayer
        implements Runnable,
                   FrameListener,
                   DrawableProvider
{
  //private static final double SQRT_2 = Math.sqrt(2);

  public static final String VERSION = "0.93";
  private static final boolean USE_THREAD = false;
  private static final boolean DRIVE_TO_BORDER = true;
  private static final int     MAX_ASTEROIDS_FOR_MULTI_SHOT = MAX_NUMBER_ASTEROIDS - 2;
  private static final int MIN_BORDER = 140;
  private static final int MAX_BORDER = 230;

  private LinkedBlockingQueue<FrameInfo> incomingFrames = new LinkedBlockingQueue<FrameInfo>();
  private Map<Integer, Integer> targetAsteroids = new HashMap<Integer, Integer>();
  private BulletCounter bulletCounter = new BulletCounter();
  private Scorer scorer;
  private StandardFuturologist futurologist;
  private int pendingShots;
  private Target target;
  private int backTurn;
  private int maxAsteroidsForMultiShot = MAX_ASTEROIDS_FOR_MULTI_SHOT;
  private double smallUfoScore = -1;
  private double bigUfoScore = -1;
  private int minBorder = MIN_BORDER;
  private int maxBorder = MAX_BORDER;
  private int dangerFrames = 120;
  private int blackoutFrames = 6;
  private int maxVolleyCount = 3;
  private static final double MAX_VELOCITY = 0.125;
  private static final double TARGET_BONUS = 0; //12;
  private ShootingDirectionFixer shootingDirectionFixer;
  private boolean destroyed = false;
  private static final int MINIMAL_TARGET_ASTEROID_LIFETIME = 4;
  private static final int MINIMAL_TARGET_UFO_LIFETIME = 1;

  public AsteroidPlayer()
  {
    this(null);
  }


  public AsteroidPlayer(Communication com)
  {
    //this(com, new DefaultScorer());
    this(com, new DefaultScorer(DefaultScorer.DANGER_FRAMES, DefaultScorer.DANGER_SCORE, 0, 32));
  }

  public AsteroidPlayer(Communication com, Scorer scorer)
  {
    super(com);
    this.scorer = scorer;
    futurologist = new StandardFuturologist();
    if (com != null) {
      shootingDirectionFixer = new ShootingDirectionFixer();
      com.setFramePreparer(new FramePreparerSequence(new ImprovedVelocityPreparer(),
                                                     new ScoreFixer(),
                                                     shootingDirectionFixer));
      com.addDatagramListener(shootingDirectionFixer);

      if (USE_THREAD) {
        Thread playerThread = new Thread(this, "Player");
        playerThread.setUncaughtExceptionHandler(new Thread.UncaughtExceptionHandler()
        {
          public void uncaughtException(Thread t, Throwable e)
          {
            System.err.println("Player thread passed out.");
            e.printStackTrace(System.err);
            System.exit(1);
          }
        });
        playerThread.start();
      }
    }
    else {
      //  shootingLaneDisplay = new ShootingLaneDisplay(Color.pink);
    }
  }

  /**
   *  Call this to cleanup any resources taken by this object.
   */
  public void destroy()
  {
    if (shootingDirectionFixer != null) {
      com.removeDatagramListener(shootingDirectionFixer);
      shootingDirectionFixer = null;
    }
    destroyed = true;
  }

  /**
   * Called by the garbage collector on an object when garbage collection
   * determines that there are no more references to the object.
   * A subclass overrides the <code>finalize</code> method to dispose of
   * system resources or to perform other cleanup.
   * <p/>
   * The general contract of <tt>finalize</tt> is that it is invoked
   * if and when the Java<font size="-2"><sup>TM</sup></font> virtual
   * machine has determined that there is no longer any
   * means by which this object can be accessed by any thread that has
   * not yet died, except as a result of an action taken by the
   * finalization of some other object or class which is ready to be
   * finalized. The <tt>finalize</tt> method may take any action, including
   * making this object available again to other threads; the usual purpose
   * of <tt>finalize</tt>, however, is to perform cleanup actions before
   * the object is irrevocably discarded. For example, the finalize method
   * for an object that represents an input/output connection might perform
   * explicit I/O transactions to break the connection before the object is
   * permanently discarded.
   * <p/>
   * The <tt>finalize</tt> method of class <tt>Object</tt> performs no
   * special action; it simply returns normally. Subclasses of
   * <tt>Object</tt> may override this definition.
   * <p/>
   * The Java programming language does not guarantee which thread will
   * invoke the <tt>finalize</tt> method for any given object. It is
   * guaranteed, however, that the thread that invokes finalize will not
   * be holding any user-visible synchronization locks when finalize is
   * invoked. If an uncaught exception is thrown by the finalize method,
   * the exception is ignored and finalization of that object terminates.
   * <p/>
   * After the <tt>finalize</tt> method has been invoked for an object, no
   * further action is taken until the Java virtual machine has again
   * determined that there is no longer any means by which this object can
   * be accessed by any thread that has not yet died, including possible
   * actions by other objects or classes which are ready to be finalized,
   * at which point the object may be discarded.
   * <p/>
   * The <tt>finalize</tt> method is never invoked more than once by a Java
   * virtual machine for any given object.
   * <p/>
   * Any exception thrown by the <code>finalize</code> method causes
   * the finalization of this object to be halted, but is otherwise
   * ignored.
   *
   * @throws Throwable the <code>Exception</code> raised by this method
   */
  @Override
  protected void finalize() throws Throwable
  {
    destroy();
  }

  public int getMaxAsteroidsForMultiShot()
  {
    return maxAsteroidsForMultiShot;
  }

  public void setMaxAsteroidsForMultiShot(int maxAsteroidsForMultiShot)
  {
    this.maxAsteroidsForMultiShot = maxAsteroidsForMultiShot;
  }

  public double getSmallUfoScore()
  {
    return smallUfoScore;
  }

  public void setSmallUfoScore(double smallUfoScore)
  {
    this.smallUfoScore = smallUfoScore;
  }

  public double getBigUfoScore()
  {
    return bigUfoScore;
  }

  public void setBigUfoScore(double bigUfoScore)
  {
    this.bigUfoScore = bigUfoScore;
  }

  public void setMinBorder(int minBorder)
  {
    this.minBorder = minBorder;
  }

  public void setMaxBorder(int maxBorder)
  {
    this.maxBorder = maxBorder;
  }

  public int getDangerFrames()
  {
    return dangerFrames;
  }

  public void setDangerFrames(int dangerFrames)
  {
    this.dangerFrames = dangerFrames;
  }

  public int getBlackoutFrames()
  {
    return blackoutFrames;
  }

  public void setBlackoutFrames(int blackoutFrames)
  {
    this.blackoutFrames = blackoutFrames;
  }

  public int getMaxVolleyCount()
  {
    return maxVolleyCount;
  }

  public void setMaxVolleyCount(int maxVolleyCount)
  {
    this.maxVolleyCount = maxVolleyCount;
  }

  /**
   * Run in thread.
   * @see Thread#run()
   */
  public void run()
  {
    while (!destroyed) {
      try {
        FrameInfo info = incomingFrames.take();
        /*
        while (!incomingFrames.isEmpty()) {
          info = incomingFrames.take();
        }
        */
        handleFrame(info);
      } catch (InterruptedException e) {
        e.printStackTrace(System.err);
      }
    }
  }

  private void handleFrame(FrameInfo info)
  {
    bulletCounter.frameReceived(info);
    if (info.getSpaceShip() != null) {
      if (hasIncomingDangerousShots(info, 2)) {
        // no way to react to shots sauf HYPERSPACE
        // (and maybe THRUST, but that depends on the current direction)
        pushButton(BUTTON_HYPERSPACE);
      }
      else {
        makeTargetScoring(info, NULL_INFO_DRAWER);
      }
    }
  }


  /**
   *  Are there any shots which will hit the ship in the over-next frame?
   *  @param info the frame info
   *  @param predictionLag lag used for prediction
   *  @return the answer
   */
  private static boolean hasIncomingDangerousShots(FrameInfo info, int predictionLag)
  {
    SpaceShip ship = info.getSpaceShip();
    Point sPos = ship.getPredictedLocation(predictionLag);
    int size = ship.getSize();
    for (Bullet bullet: info.getBullets()) {
      if (bullet.getVelocityX() == 0  &&  bullet.getVelocityY() == 0) {
        continue;
      }
      Point distance = GameObject.getTorusDelta(bullet.getPredictedLocation(predictionLag), sPos);

      if (Math.abs(distance.x) <= size &&
          Math.abs(distance.y) <= size)  {
        return true;
      }
    }
    return false;
  }

  /**
   *  Are there any asteroids which will hit the ship in the over-next frame?
   *  @param info frame info
   *  @param predictionLag lag used for prediction
   *  @return the answer
   */
  private boolean hasIncomingDangerousAsteroids(FrameInfo info, int predictionLag)
  {
    SpaceShip ship = info.getSpaceShip();
    for (Asteroid ast: info.getAsteroids()) {
      int framesTillDestroyed = futurologist.getFramesTillDestroyed(ast, info);
      if (framesTillDestroyed < 0  ||
          framesTillDestroyed > predictionLag) {
        double hitFrames = getFramesUntilCollision(ship, ast, predictionLag);
        if (hitFrames > 0  &&  hitFrames <= predictionLag) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Called each time a frame is received.
   * <p/>
   * <b>ATTENTION:</b> this is called from the communication thread!
   * Implementing classes must be aware of this and take care by synchronization or similar!
   *
   * @param frame the received frame
   */
  public void frameReceived(FrameInfo frame)
  {
    if (USE_THREAD) {
      try {
        incomingFrames.put(frame);
      } catch (InterruptedException x) {
        x.printStackTrace(System.err);
      }
    }
    else {
      handleFrame(frame);
    }
  }

  /**
   *  Make a scoring and move to the best target.
   *  Fire shot if it will hit.
   *  @param info the frame info
   *  @param infoDrawer drawer for additional information
   */
  private void makeTargetScoring(FrameInfo info, InfoDrawer infoDrawer)
  {
    updateTargetAsteroids(info);
    futurologist.frameReceived(info);

    if (hasIncomingDangerousAsteroids(info, 2)) {
      pushButton(BUTTON_HYPERSPACE);
      return;
    }

    if (pendingShots > 0) {
      if (!haveFiredInLastFrame()) {
        pushButton(BUTTON_FIRE);
        --pendingShots;
      }
      else {
        pushButton(NO_BUTTON);
      }
      return;
    }

    Map<Integer, RotateAndWait> rawForTarget = new HashMap<Integer, RotateAndWait>(87);
    SpaceShip ship = info.getSpaceShip();
    byte nextDir = info.getNextShootingDirectionLowLevel();
    int size = info.getAsteroidCount() < maxAsteroidsForMultiShot ? 8 : 32;
    SortedMap<Double,Collection<MovingGameObject>> sortedTargets = new TreeMap<Double, Collection<MovingGameObject>>();
    for (Asteroid ast: info.getAsteroids()) {
      if (ast.getLifetime() < MINIMAL_TARGET_ASTEROID_LIFETIME ||
          targetAsteroids.containsKey(ast.getIdentity())  ||
          futurologist.getFramesTillDestroyed(ast, info) >= 0) {
        continue;
      }
      Double key = null;
      int hitFrames = getFramesUntilCollision(ship, ast, dangerFrames);
      if (hitFrames > 0) {
        key = new Double(hitFrames - dangerFrames);
        rawForTarget.put(ast.getIdentity(), getRotationForHit(ship, nextDir, ast, size, 1, 136));
      }
      if (key == null) {
        RotateAndWait raw = getRotationForHit(ship, nextDir, ast, size, 1, 136);
        if (raw != null) {
          key = raw.getHitFrames() + Math.abs(raw.getRotation())/256.0;
          rawForTarget.put(ast.getIdentity(), raw);
        }
      }
                                
      if (key != null) {
        insertTarget(sortedTargets, key, ast);
      }
    }
    Ufo ufo = info.getUfo();
    if (ufo != null) {
      if (ufo.getLifetime() < MINIMAL_TARGET_UFO_LIFETIME  ||
          futurologist.getFramesTillDestroyed(ufo, info) < 0  &&
          !targetAsteroids.containsKey(ufo.getIdentity()))  {
        insertTarget(sortedTargets, ufo.getScore() == Ufo.SCORE_SMALL_UFO ? smallUfoScore : bigUfoScore, ufo);
        rawForTarget.put(ufo.getIdentity(), getRotationForHit(ship, nextDir, ufo, size, 1, 136));
      }
    }

    List<MovingGameObject> targets = Collections.emptyList();
    MovingGameObject target = null;
    RotateAndWait targetRaw = null;
    if (!sortedTargets.isEmpty()) {
      if (sortedTargets.firstKey() < 0) {
        // optimize shooting sequence
        int minRotWait = Integer.MAX_VALUE;
        MovingGameObject bestIntermediate = null;
outer:
        for (Collection<MovingGameObject> coll: sortedTargets.values()) {
          for (MovingGameObject obj: coll) {
            if (target == null) {
              targetRaw = rawForTarget.get(obj.getIdentity());
              if (targetRaw != null) {
                target = obj;
                if (getAvailableBullets(info, targetRaw.getShootFrames()) < 2) {
                  break outer;
                }
                minRotWait = targetRaw.getWait() + 1;
              }
            }
            else {
              RotateAndWait raw = rawForTarget.get(obj.getIdentity());
              if (raw != null &&
                  2*Math.abs(raw.getRotation()) + raw.getWait() < minRotWait  &&
                  getAvailableBullets(info, raw.getShootFrames()) > 0) {
                bestIntermediate = obj;
                minRotWait = 2*Math.abs(raw.getRotation()) + raw.getWait();
                break outer;
              }
            }
          }
        }
        if (bestIntermediate != null) {
          target = bestIntermediate;
          targetRaw = rawForTarget.get(target.getIdentity());
        }
      }
      else {
        Collection<MovingGameObject> possibleTargets = new LinkedList<MovingGameObject>();
        for (Collection<MovingGameObject> coll: sortedTargets.values()) {
          possibleTargets.addAll(coll);
        }
        targets = getNextTargets(ship, nextDir, size, possibleTargets);
        if (!targets.isEmpty()) {
          target = targets.remove(0);
          targetRaw = rawForTarget.get(target.getIdentity());
        }
      }
    }
    if (targetRaw != null) {
      if (targetRaw.getRotation() == 0) {
        if (!haveFiredInLastFrame() &&  targetRaw.getWait() == 0) {
          int bulletsLeft = 4 - bulletCounter.getNextShipBulletCount();
          if (bulletsLeft > 0) {
            pushButton(BUTTON_FIRE);

            if (--bulletsLeft > 0  &&  size == 8) {
              switch (target.getScore()) {
              case Asteroid.SCORE_LARGE_ASTEROID:
                pendingShots = Math.min(bulletsLeft, maxVolleyCount);
                break;
              case Asteroid.SCORE_MIDDLE_ASTEROID:
                pendingShots = Math.min(bulletsLeft, Math.min(maxVolleyCount, 3));
                break;
              case Asteroid.SCORE_SMALL_ASTEROID:
                break;
              }
            }
            targetAsteroids.put(target.getIdentity(), info.getIndex()+blackoutFrames);
            if (pendingShots > 0) {
              return;
            }
            if (false && !targets.isEmpty()) {
              target = targets.remove(0);
              targetRaw = getRotationForHit(ship, nextDir, target, size, 1, 136);
            }
            else {
              target = null;
              targetRaw = null;
            }
          }
          else {
            pushButton(NO_BUTTON);
            target = null;
            targetRaw = null;
          }
        }
        else {
          pushButton(NO_BUTTON);
          target = null;
          targetRaw = null;
        }
      }
      if (target != null  &&  targetRaw.getRotation() != 0) {
        pushButton(targetRaw.getRotation() > 0 ? BUTTON_LEFT : BUTTON_RIGHT);
      }
      driveToBorder(ship, info, false);
    }
    else {
      int nrTargets = info.getAsteroidCount();
      if (info.getUfo() != null) {
        ++nrTargets;
      }
      driveToBorder(ship, info, nrTargets == 0);
    }
  }

  private int getAvailableBullets(FrameInfo frame, int frameCount)
  {
    return 2;
    /* not really useful
    if (frameCount >= Bullet.MAX_LIFETIME) {
      return 4;
    }
    int nr = 4;
    for (Bullet bullet: frame.getBullets()) {
      if (bulletCounter.isShipBullet(bullet)) {
        int frames = futurologist.getFramesTillDestroyed(bullet, frame);
        if (frames >= frameCount  &&  Bullet.MAX_LIFETIME - bullet.getLifetime() >= frameCount) {
          --nr;
        }
      }
    }
    if (haveFiredInLastFrame()) {
      --nr;
    }
    return nr;
    */
  }

  private static void insertTarget(SortedMap<Double, Collection<MovingGameObject>> sortedTargets, Double key,
                                   MovingGameObject ast)
  {
    Collection<MovingGameObject> objects = sortedTargets.get(key);
    if (objects == null) {
      objects = new LinkedList<MovingGameObject>();
      sortedTargets.put(key, objects);
    }
    objects.add(ast);
  }

  private void driveToBorder(SpaceShip ship, FrameInfo info, boolean rotationAllowed)
  {
    final Point delta = new Point(ship.getX() - EXTENT / 2,
                                  ship.getY() - EXTENT / 2);
    int xBorder = EXTENT_X/2 - Math.abs(delta.x);
    int yBorder = EXTENT_Y/2 - Math.abs(delta.y);
    boolean xOkay = MIN_BORDER <= xBorder  &&  xBorder <= MAX_BORDER;
    boolean yOkay = MIN_BORDER <= yBorder  &&  yBorder <= MAX_BORDER;
    if (DRIVE_TO_BORDER && (!xOkay || !yOkay)) {
      if (xOkay) {
        delta.x = 0;
      }
      if (yOkay) {
        delta.y = 0;
      }
      Point2D shipPos = ship.getCorrectedNextLocation();
      int borderDist = (MIN_BORDER + MAX_BORDER)/2;
      Point nearestCorner = new Point(shipPos.getX() >= EXTENT_X/2  ?
              EXTENT_X - borderDist  :
              borderDist,
                                      shipPos.getY() >= EXTENT_Y/2  ?
                                              MIN_Y + EXTENT_Y - borderDist  :
                                              MIN_Y + borderDist);
      Point2D cornerDeltaNorm = Tools.normalize(new Point2D.Double(nearestCorner.x - shipPos.getX(),
                                                                   nearestCorner.y - shipPos.getY()));
      Point2D shipDirNorm = Tools.normalize(info.getNextShootingDirection().getBulletVelocity());
      double cross = Tools.crossProduct(cornerDeltaNorm, shipDirNorm);
      if (rotationAllowed) {
        if (Math.abs(cross) > ROT_BORDER) {
          pushButton(cross > 0  ?  BUTTON_RIGHT  :  BUTTON_LEFT);
        }
      }
      if (Math.abs(ship.getVelocityX()) <= MAX_VELOCITY &&  Math.abs(ship.getVelocityY()) <= MAX_VELOCITY) {
        double scalar = Tools.scalarProduct(cornerDeltaNorm, shipDirNorm);
        if (scalar > 0.9) {
          pushButton(BUTTON_THRUST);
        }
      }
    }
    else if (rotationAllowed) {
      Point2D outwards = Tools.normalize(delta);
      if (outwards != null) {
        double cross = Tools.crossProduct(outwards, Tools.normalize(info.getNextShootingDirection().getBulletVelocity()));
        if (Math.abs(cross) > ROT_BORDER) {
          // turn outwards
          pushButton(cross > 0 ? BUTTON_RIGHT : BUTTON_LEFT);
        }
      }
    }
  }

  private void updateTargetAsteroids(FrameInfo info)
  {
    if (com == null) {
      // in analysis mode
      targetAsteroids.clear();
    }
    else {
      final int counter = info.getIndex();
      for (Integer ident: new ArrayList<Integer>(targetAsteroids.keySet())) {
        if (targetAsteroids.get(ident).intValue() <= counter) {
          targetAsteroids.remove(ident);
        }
      }
    }
  }

  public void draw(Graphics2D g, FrameInfo frame)
  {
    SpaceShip ship = frame.getSpaceShip();
    if (ship != null) {
      DefaultInfoDrawer drawer = new DefaultInfoDrawer();
      makeTargetScoring(frame, drawer);
      drawer.draw(g);
      g.setColor(Color.yellow);
      g.drawLine(ship.getX(), ship.getY(), ship.getX() + ship.getDirX(), ship.getY() + ship.getDirY());
      g.setColor(Color.green);
      Point2D shootDir = frame.getNextShootingDirection().getBulletVelocity();
      g.drawLine(ship.getX(), ship.getY(), ship.getX() + (int)(8*shootDir.getX()), ship.getY() + (int)(8*shootDir.getY()));
      g.setColor(Color.red);
      shootDir = frame.getShootingDirection().getBulletVelocity();
      g.drawLine(ship.getX(), ship.getY(), ship.getX() + (int)(8*shootDir.getX()), ship.getY() + (int)(8*shootDir.getY()));
    }
    futurologist.draw(g, frame);
  }

  private static final int MAX_PERMUTATE_TARGETS = 5;
  private static final int[][][] PERMUTATIONS = {
          {
                  {}
          },
          {
                  { 0 }
          },
          {
                  { 0, 1 },
                  { 1, 0 }
          },
          {
                  { 0, 1, 2 },
                  { 0, 2, 1 },
                  { 1, 0, 2 },
                  { 1, 2, 0 },
                  { 2, 0, 1 },
                  { 2, 1, 0 }
          },
          {
                  { 0, 1, 2, 3 },
                  { 0, 1, 3, 2 },
                  { 0, 2, 1, 3 },
                  { 0, 2, 3, 1 },
                  { 0, 3, 1, 2 },
                  { 0, 3, 2, 1 },
                  { 1, 0, 2, 3 },
                  { 1, 0, 3, 2 },
                  { 1, 2, 0, 3 },
                  { 1, 2, 3, 0 },
                  { 1, 3, 0, 2 },
                  { 1, 3, 2, 0 },
                  { 2, 0, 1, 3 },
                  { 2, 0, 3, 1 },
                  { 2, 1, 0, 3 },
                  { 2, 1, 3, 0 },
                  { 2, 3, 0, 1 },
                  { 2, 3, 1, 0 },
                  { 3, 0, 1, 2 },
                  { 3, 0, 2, 1 },
                  { 3, 1, 0, 2 },
                  { 3, 1, 2, 0 },
                  { 3, 2, 0, 1 },
                  { 3, 2, 1, 0 }
          },
          {
                  { 0, 1, 2, 3, 4 },
                  { 0, 1, 2, 4, 3 },
                  { 0, 1, 3, 2, 4 },
                  { 0, 1, 3, 4, 2 },
                  { 0, 1, 4, 2, 3 },
                  { 0, 1, 4, 3, 2 },
                  { 0, 2, 1, 3, 4 },
                  { 0, 2, 1, 4, 3 },
                  { 0, 2, 3, 1, 4 },
                  { 0, 2, 3, 4, 1 },
                  { 0, 2, 4, 1, 3 },
                  { 0, 2, 4, 3, 1 },
                  { 0, 3, 1, 2, 4 },
                  { 0, 3, 1, 4, 2 },
                  { 0, 3, 2, 1, 4 },
                  { 0, 3, 2, 4, 1 },
                  { 0, 3, 4, 1, 2 },
                  { 0, 3, 4, 2, 1 },
                  { 0, 4, 1, 2, 3 },
                  { 0, 4, 1, 3, 2 },
                  { 0, 4, 2, 1, 3 },
                  { 0, 4, 2, 3, 1 },
                  { 0, 4, 3, 1, 2 },
                  { 0, 4, 3, 2, 1 },
                  { 1, 0, 2, 3, 4 },
                  { 1, 0, 2, 4, 3 },
                  { 1, 0, 3, 2, 4 },
                  { 1, 0, 3, 4, 2 },
                  { 1, 0, 4, 2, 3 },
                  { 1, 0, 4, 3, 2 },
                  { 1, 2, 0, 3, 4 },
                  { 1, 2, 0, 4, 3 },
                  { 1, 2, 3, 0, 4 },
                  { 1, 2, 3, 4, 0 },
                  { 1, 2, 4, 0, 3 },
                  { 1, 2, 4, 3, 0 },
                  { 1, 3, 0, 2, 4 },
                  { 1, 3, 0, 4, 2 },
                  { 1, 3, 2, 0, 4 },
                  { 1, 3, 2, 4, 0 },
                  { 1, 3, 4, 0, 2 },
                  { 1, 3, 4, 2, 0 },
                  { 1, 4, 0, 2, 3 },
                  { 1, 4, 0, 3, 2 },
                  { 1, 4, 2, 0, 3 },
                  { 1, 4, 2, 3, 0 },
                  { 1, 4, 3, 0, 2 },
                  { 1, 4, 3, 2, 0 },
                  { 2, 0, 1, 3, 4 },
                  { 2, 0, 1, 4, 3 },
                  { 2, 0, 3, 1, 4 },
                  { 2, 0, 3, 4, 1 },
                  { 2, 0, 4, 1, 3 },
                  { 2, 0, 4, 3, 1 },
                  { 2, 1, 0, 3, 4 },
                  { 2, 1, 0, 4, 3 },
                  { 2, 1, 3, 0, 4 },
                  { 2, 1, 3, 4, 0 },
                  { 2, 1, 4, 0, 3 },
                  { 2, 1, 4, 3, 0 },
                  { 2, 3, 0, 1, 4 },
                  { 2, 3, 0, 4, 1 },
                  { 2, 3, 1, 0, 4 },
                  { 2, 3, 1, 4, 0 },
                  { 2, 3, 4, 0, 1 },
                  { 2, 3, 4, 1, 0 },
                  { 2, 4, 0, 1, 3 },
                  { 2, 4, 0, 3, 1 },
                  { 2, 4, 1, 0, 3 },
                  { 2, 4, 1, 3, 0 },
                  { 2, 4, 3, 0, 1 },
                  { 2, 4, 3, 1, 0 },
                  { 3, 0, 1, 2, 4 },
                  { 3, 0, 1, 4, 2 },
                  { 3, 0, 2, 1, 4 },
                  { 3, 0, 2, 4, 1 },
                  { 3, 0, 4, 1, 2 },
                  { 3, 0, 4, 2, 1 },
                  { 3, 1, 0, 2, 4 },
                  { 3, 1, 0, 4, 2 },
                  { 3, 1, 2, 0, 4 },
                  { 3, 1, 2, 4, 0 },
                  { 3, 1, 4, 0, 2 },
                  { 3, 1, 4, 2, 0 },
                  { 3, 2, 0, 1, 4 },
                  { 3, 2, 0, 4, 1 },
                  { 3, 2, 1, 0, 4 },
                  { 3, 2, 1, 4, 0 },
                  { 3, 2, 4, 0, 1 },
                  { 3, 2, 4, 1, 0 },
                  { 3, 4, 0, 1, 2 },
                  { 3, 4, 0, 2, 1 },
                  { 3, 4, 1, 0, 2 },
                  { 3, 4, 1, 2, 0 },
                  { 3, 4, 2, 0, 1 },
                  { 3, 4, 2, 1, 0 },
                  { 4, 0, 1, 2, 3 },
                  { 4, 0, 1, 3, 2 },
                  { 4, 0, 2, 1, 3 },
                  { 4, 0, 2, 3, 1 },
                  { 4, 0, 3, 1, 2 },
                  { 4, 0, 3, 2, 1 },
                  { 4, 1, 0, 2, 3 },
                  { 4, 1, 0, 3, 2 },
                  { 4, 1, 2, 0, 3 },
                  { 4, 1, 2, 3, 0 },
                  { 4, 1, 3, 0, 2 },
                  { 4, 1, 3, 2, 0 },
                  { 4, 2, 0, 1, 3 },
                  { 4, 2, 0, 3, 1 },
                  { 4, 2, 1, 0, 3 },
                  { 4, 2, 1, 3, 0 },
                  { 4, 2, 3, 0, 1 },
                  { 4, 2, 3, 1, 0 },
                  { 4, 3, 0, 1, 2 },
                  { 4, 3, 0, 2, 1 },
                  { 4, 3, 1, 0, 2 },
                  { 4, 3, 1, 2, 0 },
                  { 4, 3, 2, 0, 1 },
                  { 4, 3, 2, 1, 0 }
          }
  };

  // stats
  private int reordered = 0;
  private int originalOrder = 0;

  private List<MovingGameObject> getNextTargets(SpaceShip ship, byte dirByte, int maxSize, Collection<MovingGameObject> targets)
  {
    List<MovingGameObject> validTargets = new ArrayList<MovingGameObject>(MAX_PERMUTATE_TARGETS);
    for (MovingGameObject object: targets) {
      if (targetAsteroids.get(object.getIdentity()) == null) {
        validTargets.add(object);
        if (validTargets.size() == MAX_PERMUTATE_TARGETS) {
          break;
        }
      }
    }
    if (validTargets.size() == 0) {
      return Collections.emptyList();
    }
    else if (validTargets.size() == 1) {
      return validTargets;
    }
    else {
      int minimalFrames = Integer.MAX_VALUE;
      int minimalPermutation = -1;
      int maxFutureFrames = 600;
      int[][] permutation = PERMUTATIONS[validTargets.size()];
outer:
      for (int p = 0;  p < permutation.length;  ++p) {
        int frames = 1;
        RotateAndWait raw = null;
        for (int t = 0;  t < permutation[p].length;  ++t) {
          raw = getRotationForHit(ship, dirByte, validTargets.get(permutation[p][t]),
                                  maxSize, frames, maxFutureFrames);
          if (raw == null) {
            continue outer;
          }
          frames += raw.getShootFrames() + 1;
        }
        if (raw != null) {
          frames += raw.getFly();
        }
        if (frames < minimalFrames) {
          minimalFrames = frames;
          minimalPermutation = p;
        }
      }
      if (minimalPermutation > 0) {
        ++reordered;
      }
      else {
        ++originalOrder;
      }
      if (minimalPermutation > 0) {
        List<MovingGameObject> result = new LinkedList<MovingGameObject>();
        for (int i = 0;  i < permutation[minimalPermutation].length;  ++i) {
          result.add(validTargets.get(permutation[minimalPermutation][i]));
        }
        return result;
      }
      else {
        return validTargets;
      }
    }
  }

  public int getReordered()
  {
    return reordered;
  }

  public int getOriginalOrder()
  {
    return originalOrder;
  }
}
