// ============================================================================
// File:               $File$
//
// Project:            
//
// Purpose:            
//
// Author:             Rammi
//
// Copyright Notice:   (c) 2008  Rammi (rammi@caff.de)
//                     The usage of this source code in commercial products
//                     is not allowed without explicite permission.
//
// Latest change:      $Date$
//
// History:	       $Log$
//=============================================================================
// ============================================================================
// File:               $File$
//
// Project:
//
// Purpose:
//
// Author:             Rammi
//
// Copyright Notice:   (c) 2008  Rammi (rammi@caff.de)
//                     The usage of this source code in commercial products
//                     is not allowed without explicite permission.
//
// Latest change:      $Date$
//
// History:	       $Log$
//=============================================================================
package de.caff.asteroid.rammi;

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

import java.awt.geom.Point2D;
import java.util.*;
import java.io.*;

/**
 *  Where bullets are in which frame.
 */
public class BulletLifetimeInformation
        implements GameData
{
  /** The margin around the original playground, for faster lookup. */
  private static final int MARGIN_WIDTH = 32;
  /** The width of a cell. */
  private static final int CELL_WIDTH   = 16;
  /** The number of cells in horizontal (x) direction. */
  private static final int HOR_CELLS = (EXTENT_X + 2*MARGIN_WIDTH + CELL_WIDTH - 1) / CELL_WIDTH;
  /** The number of cells in vertical (y) direction. */
  private static final int VER_CELLS = (EXTENT_Y + 2*MARGIN_WIDTH + CELL_WIDTH - 1) / CELL_WIDTH;
  /** The center cell index (horizontal). */
  private static final int HOR_CENTER = HOR_CELLS/2;
  /** The center cell index (vertical). */
  private static final int VER_CENTER = VER_CELLS/2;

  /** Knowledge about bullets. */
  public static class BulletFrameInfo
  {
    /** Direction in which the bullet was fired. */
    private final byte direction;
    /** The frame for which this position was reached. */
    private final int frame;

    /**
     *  Constructor.
     *  @param direction  direction in which the bullet was fired
     *  @param frame      frame for which this position was reached
     */
    BulletFrameInfo(byte direction, int frame)
    {
      this.direction = direction;
      this.frame = frame;
    }

    /**
     *  Get the shooting direction.
     *  @return shooting direction
     */
    public byte getDirection()
    {
      return direction;
    }

    /**
     *  Get the frame after which the position is reached if
     *  firing in the given direction.
     *  @return frame
     */
    public int getFrame()
    {
      return frame;
    }

  }

  public static class BulletFramePositionInfo
          extends BulletFrameInfo
  {
    /** The position. */
    private final Point2D position;

    /**
     *  Constructor.
     *  @param direction  direction in which the bullet was fired
     *  @param frame      frame for which this position was reached
     *  @param x          the position (x coordinate)
     *  @param y          the position (y coordinate)
     */
    BulletFramePositionInfo(byte direction, int frame, double x, double y)
    {
      super(direction, frame);
      this.position = new Point2D.Double(x, y);
    }

    public Point2D getPosition()
    {
      return position;
    }

  }

  private static class Match
  {
    private final int cellX;
    private final int cellY;
    private final double offsetX;
    private final double offsetY;

    private Match(int cellX, int cellY, double offsetX, double offsetY)
    {
      this.cellX = cellX;
      this.cellY = cellY;
      this.offsetX = offsetX;
      this.offsetY = offsetY;
    }

    public int getCellX()
    {
      return cellX;
    }

    public int getCellY()
    {
      return cellY;
    }

    public double getOffsetX()
    {
      return offsetX;
    }

    public double getOffsetY()
    {
      return offsetY;
    }

    public boolean isValid()
    {
      return cellX >= 0  &&  cellX < HOR_CELLS  &&  cellY >= 0  &&  cellY < VER_CELLS;
    }
  }

  private static final Comparator<BulletFrameInfo> FRAME_COMPARATOR = new Comparator<BulletFrameInfo>()
  {
    public int compare(BulletFrameInfo o1, BulletFrameInfo o2)
    {
      int result = o1.getFrame() - o2.getFrame();
      if (result != 0) {
        return result;
      }
      // NOTE: making arbitrary comparision to be sure the order is always the same
      return o1.getDirection() - o2.getDirection();
    }
  };

  private static final BulletFramePositionInfo[][][] area = new BulletFramePositionInfo[HOR_CELLS][VER_CELLS][];
  static {
    // initialize array
    for (int dir = 0;  dir < 256;  ++dir) {
      byte dirByte = (byte)dir;
      FrameInfo.Direction direction = FrameInfo.getShootingDirection(dir);
      double posX = direction.getDisplacement().x;
      double posY = direction.getDisplacement().y;
      for (int frame = 1;  frame < Bullet.MIN_LIFETIME - 1;  ++frame) {
        double nx = GameObject.normalizeDeltaX(posX);
        double ny = GameObject.normalizeDeltaY(posY);
        for (int deltaX: new int[] {-EXTENT_X, 0, EXTENT_X}) {
          for (int deltaY: new int[] { -EXTENT_Y, 0, EXTENT_Y}) {
            Match m = mapToAreaUnnormalized(nx + deltaX, ny + deltaY);
            if (m.isValid()) {
              BulletFramePositionInfo newInfo = new BulletFramePositionInfo(dirByte, frame, nx + deltaX, ny + deltaY);
              int cx = m.getCellX();
              int cy = m.getCellY();

              if (area[cx][cy] == null) {
                area[cx][cy] = new BulletFramePositionInfo[] { newInfo };
              }
              else {
                BulletFramePositionInfo[] newEntries = new BulletFramePositionInfo[area[cx][cy].length+1];
                System.arraycopy(area[cx][cy], 0, newEntries, 0, area[cx][cy].length);
                newEntries[area[cx][cy].length] = newInfo;
                area[cx][cy] = newEntries;
              }
            }
          }
        }
        posX += direction.getBulletVelocity().getX();
        posY += direction.getBulletVelocity().getY();
      }
    }
    BulletFramePositionInfo[] empty = new BulletFramePositionInfo[0];
    for (int x = 0;  x < HOR_CELLS;  ++x) {
      for (int y = 0;  y < VER_CELLS;  ++y) {
        if (area[x][y] == null) {
          area[x][y] = empty;
        }
      }
    }
  }

  private static class OverscanAndHits
  {
    private final int overscan;
    private final BulletFrameInfo[][] hits;

    private OverscanAndHits(int overscan, BulletFrameInfo[][] hits)
    {
      this.overscan = overscan;
      this.hits = hits;
    }

    public int getOverscan()
    {
      return overscan;
    }

    public BulletFrameInfo[][] getHits()
    {
      return hits;
    }
  }

  /** Cached infos. */
  private static Map<Integer, BulletLifetimeInformation> cachedInfos = new HashMap<Integer, BulletLifetimeInformation>();

  /**
   *  Get an info based using a given overscan.
   *  @param size     8, 16, 32
   *  @param overscan 1, 2, 4, 8
   *  @return the bullet lifetime information read from precalculated files
   *  @throws IOException on read errors
   */
  public static BulletLifetimeInformation getLifetimeInformation(int size, int overscan) throws IOException
  {
    BulletLifetimeInformation info = cachedInfos.get(overscan);
    if (info == null) {
      info = new BulletLifetimeInformation(String.format("/data/hits-%d-%d.data", size, overscan));
      cachedInfos.put(overscan, info);
    }
    return info;
  }
  /**
   *  The fastest hit.
   *  This has to be packed, because even in packed form it's still 800 MBytes only for the pointers.
   *  High byte is direction, low byte is frame.
   */
  private BulletFrameInfo[][] hits;
  /** Overscan value. */
  private final int overscan;

  private BulletLifetimeInformation(String resource) throws IOException
  {
    OverscanAndHits oh = readHitsFromRessource(resource);
    overscan = oh.getOverscan();
    hits = oh.getHits();
    System.gc();
  }

  /**
   *  Initialize hits from scratch, than save everything.
   *  This may last several hours depending on the overscan.
   *  @param size     object size
   *  @param overscan overscan factor
   *  @return the hits array
   */
  private static short[][] calculateHits(int size, int overscan)
  {
    size -= 2;  // using smaller size as a countermeasure for inaccuracy
    double granularity = 1.0/overscan;
    // initialize hits
    short[][] hits = new short[EXTENT_X*overscan * EXTENT_Y*overscan][];

    System.out.println("Starting initialization");
    long start = System.currentTimeMillis();
    Point2D.Double pos = new Point2D.Double();
    for (int s = 0;  s < overscan;  ++s) {
      System.out.println("s="+s);
      for (int x = 0;  x < EXTENT_X;  ++x) {
        System.out.println("\tx="+x);
        for (int t = 0;  t < overscan;  ++t) {
          for (int y = 0;  y < EXTENT_Y;  ++y) {
            int index = ((x*overscan + s)*EXTENT_Y + y)*overscan + t;
            double posX = x + s*granularity - EXTENT_X/2;
            double posY = y + t*granularity - EXTENT_Y/2;
            pos.setLocation(posX, posY);
            Collection<BulletFramePositionInfo> infos = getBulletFrameInfos(pos, size);
            short[] entry = new short[infos.size()];
            int e = 0;
            for (BulletFrameInfo info: infos) {
              entry[e++] = (short)(Tools.byteToUnsigned(info.getDirection()) << 8 | (info.getFrame() & 0xFF));
            }
            if (y > 0 && Arrays.equals(entry, hits[index-overscan])) {
              entry = hits[index-overscan];
            }
            else if (t > 0 && Arrays.equals(entry, hits[index-1])) {
              entry = hits[index-1];
            }
            else if (x > 0 && Arrays.equals(entry, hits[index - EXTENT_Y*overscan])) {
              entry = hits[index - EXTENT_Y*overscan];
            }
            else if (s > 0 && Arrays.equals(entry, hits[index - EXTENT_Y])) {
              entry = hits[index - EXTENT_Y];
            }
            hits[index] = entry;
          }
        }
      }
    }
    System.out.println("Initialization lasted "+(System.currentTimeMillis() - start)+" ms");
    System.out.println("Memory: "+ (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));

    return hits;
  }

  /**
   *  Get the bullets which can hit an object at a given delta to the ship.
   *  @param x x coordinate
   *  @param y y coordinate
   *  @return infos of the hitting bullets
   */
  public BulletFrameInfo[] getHitBulletInfos(double x, double y)
  {
    x = Math.floor(overscan * x + .5)/overscan;
    y = Math.floor(overscan * y + .5)/overscan;
    int entryX = (int)Math.floor((GameObject.normalizeDeltaX(x) + EXTENT_X/2)*overscan);
    int entryY = (int)Math.floor((GameObject.normalizeDeltaY(y) + EXTENT_Y/2)*overscan);
    try {
      return hits[entryX*EXTENT_Y*overscan + entryY];
    } catch (ArrayIndexOutOfBoundsException e) {
      System.out.println("x="+x+",y="+y+",entryX="+entryX+",entryY="+entryY+",len="+hits.length);
      System.exit(2);
      return null;
    }
    /*
    List<BulletFrameInfo> result = new ArrayList<BulletFrameInfo>(packed.length);
    for (int i = 0;  i < packed.length;  ++i) {
      result.add(new BulletFrameInfo((byte)(packed[i] >> 8), packed[i] & 0xFF));
    }
    return result;
    */
  }

  private static class ShortArrayWrapper
  {
    private final short[] array;

    ShortArrayWrapper(short[] array)
    {
      this.array = array;
    }

    public boolean equals(Object o)
    {
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }

      ShortArrayWrapper that = (ShortArrayWrapper)o;

      return Arrays.equals(array, that.array);
    }

    public int hashCode()
    {
      return Arrays.hashCode(array);
    }

    public short[] getArray()
    {
      return array;
    }
  }

  private static void saveHits(String filename, short[][] hits, int overscan)
          throws IOException
  {
    FileWriter fw = new FileWriter(filename);
    BufferedWriter bw = new BufferedWriter(fw, 1<<20);
    bw.write(String.format("*%d\n", overscan));
    Map<ShortArrayWrapper,Integer> mapping = new HashMap<ShortArrayWrapper,Integer>();
    int index = 0;
    int hitIndex = 0;
    for (short[] hit: hits) {
      //System.out.println("index="+(hitIndex++));
      ShortArrayWrapper wrapper = new ShortArrayWrapper(hit);
      if (!mapping.containsKey(wrapper)) {
        for (short h: hit) {
          bw.write(String.format("%d ", h));
        }
        bw.write("\n");
        mapping.put(wrapper, index++);
      }
    }
    bw.write("[\n");
    int count = 0;    // for RLE
    ShortArrayWrapper lastWrapper = null;
    for (short[] hit: hits) {
      ShortArrayWrapper wrapper = new ShortArrayWrapper(hit);
      if (wrapper.equals(lastWrapper)) {
        ++count;
      }
      else {
        if (lastWrapper != null) {
          if (count > 1) {
            bw.write(Integer.toString(count));
            bw.write("*");
          }
          bw.write(mapping.get(lastWrapper).toString());
          bw.write("\n");
        }
        lastWrapper = wrapper;
        count = 1;
      }
    }
    if (lastWrapper != null) {
      if (count > 1) {
        bw.write(Integer.toString(count));
        bw.write("*");
      }
      bw.write(mapping.get(lastWrapper).toString());
      bw.write("\n");
    }
    bw.write("]\n");
    bw.close();
    fw.close();
  }


  private static OverscanAndHits readHitsFromRessource(String resname)
          throws IOException
  {
    InputStream is = BulletLifetimeInformation.class.getResourceAsStream(resname);
    try {
      return readHits(new InputStreamReader(is));
    } finally {
      is.close();
    }
  }

  private static OverscanAndHits readHits(String filename)
          throws IOException
  {
    FileReader fr = new FileReader(filename);
    try {
      return readHits(fr);
    } finally {
      fr.close();
    }
  }

  private static OverscanAndHits readHits(Reader reader)
          throws IOException
  {
    BufferedReader br = new BufferedReader(reader, 1<<20);

    ArrayList<BulletFrameInfo[]> array = new ArrayList<BulletFrameInfo[]>(666666);
    String line = br.readLine().trim();
    if (!line.startsWith("*")) {
      throw new IOException(String.format("Missing overscan entry in line 1"));
    }
    int overscan = Integer.parseInt(line.substring(1));
    BulletFrameInfo[][] hits = new BulletFrameInfo[EXTENT_X*overscan * EXTENT_Y*overscan][];
    line = br.readLine().trim();
    do {
      BulletFrameInfo[] newEntry;
      if (line.length() == 0) {
        newEntry = new BulletFrameInfo[0];
      }
      else {
        String[] items = line.split(" ");
        newEntry = new BulletFrameInfo[items.length];
        for (int i = items.length - 1;  i >= 0;  --i) {
          short packed = Short.parseShort(items[i]);
          newEntry[i] = new BulletFrameInfo((byte)((packed & 0xFF00) >> 8), packed & 0xFF);
        }
      }
      array.add(newEntry);
      line = br.readLine().trim();
    } while (!"[".equals(line));
    int count = 0;
    BulletFrameInfo[] entry = null;
    for (int i = 0;  i < hits.length;  ++i) {
      if (count == 0) {
        line = br.readLine().trim();
        String[] parts = line.split("\\*");
        if (parts.length == 2) {
          count = Integer.parseInt(parts[0]);
          entry = array.get(Integer.parseInt(parts[1]));
        }
        else {
          count = 1;
          entry = array.get(Integer.parseInt(line));
        }
      }
      hits[i] = entry;
      --count;
    }
    br.close();
    return new OverscanAndHits(overscan, hits);
  }

  private static void compressHits(short[][] hits)
  {
    Map<ShortArrayWrapper, Integer> map = new HashMap<ShortArrayWrapper, Integer>();
    int unique = 0;
    int doublett = 0;
    for (int i = 0;  i < hits.length;  ++i) {
      ShortArrayWrapper wrapper = new ShortArrayWrapper(hits[i]);
      Integer index = map.get(wrapper);
      if (index == null) {
        map.put(wrapper, i);
        ++unique;
      }
      else {
        hits[i] = hits[map.get(wrapper)];
        ++doublett;
      }
    }
    System.out.println("\tUnique:   "+unique);
    System.out.println("\tDoublett: "+doublett);
    System.out.println("\tTotal:    "+(unique+doublett));
  }

  private static Match mapToArea(double x, double y)
  {
    return mapToAreaUnnormalized(GameObject.normalizeDeltaX(x),
                                 GameObject.normalizeDeltaY(y));
  }

  private static Match mapToAreaUnnormalized(double x, double y)
  {
    int cellX = (int)Math.floor(x / CELL_WIDTH);
    int cellY = (int)Math.floor(y / CELL_WIDTH);

    return new Match(cellX + HOR_CENTER, cellY + VER_CENTER,
                     x - cellX * CELL_WIDTH, y - cellY * CELL_WIDTH);
  }

  /**
   *  Get the bullet frame infos for a given position.
   *  @param pos object position
   *  @param size half extent size 
   *  @return bullet frame infos, sorted by frame
   */
  public static Collection<BulletFramePositionInfo> getBulletFrameInfos(Point2D pos, int size)
  {
    java.util.List<BulletFramePositionInfo> result = new LinkedList<BulletFramePositionInfo>();
    Match match = mapToArea(pos.getX(), pos.getY());
    size += Bullet.BULLET_SIZE;
    int minOffsetX = (int)Math.floor((match.getOffsetX() - size)/CELL_WIDTH);
    int maxOffsetX = (int)Math.floor((match.getOffsetX() + size)/CELL_WIDTH);
    int minOffsetY = (int)Math.floor((match.getOffsetY() - size)/CELL_WIDTH);
    int maxOffsetY = (int)Math.floor((match.getOffsetY() + size)/CELL_WIDTH);
    double sizeSquared = Tools.square(size);
    for (int x = minOffsetX;  x <= maxOffsetX;  ++x) {
      for (int y = minOffsetY;  y <= maxOffsetY;  ++y) {
        for (BulletFramePositionInfo info: area[match.getCellX() + x][match.getCellY() + y]) {
          if (Tools.square(info.getPosition().getX() - pos.getX()) + Tools.square(info.getPosition().getY() - pos.getY()) < sizeSquared) {
            result.add(info);
          }
        }
      }
    }
    Collections.sort(result, FRAME_COMPARATOR);
    return result;
  }

  public void checkHits()
  {
    for (int i = 0;  i < hits.length;  ++i) {
      if (hits[i] == null) {
        System.out.println("hits["+i+"]=null!");
      }
    }
  }


  public static void main(String[] args) throws IOException
  {
    if (args.length < 1) {
      System.err.println("Need arguments!");
      System.exit(1);
    }
    if (args.length >= 3) {
      int size = Integer.parseInt(args[0]);
      int overscan = Integer.parseInt(args[1]);
      short[][] hits = calculateHits(size, overscan);
      System.out.println("Starting compression...");
      compressHits(hits);
      System.out.println("Finished compression.");
      System.out.println("Saving...");
      saveHits(args[2], hits, overscan);
      System.out.println("Finished saving.");
    }
    else {
      long start = System.currentTimeMillis();
      System.out.println("Starting read...");
      readHits(args[0]);
      System.out.println("Finished. Reading took "+(System.currentTimeMillis() - start)+" ms");
    }
    System.out.println("Memory: "+ (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));
  }
}
