// Copyright 2016 Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland
// www.source-code.biz, www.inventec.ch/chdh
//
// License: GPL, GNU General Public License, http://www.gnu.org/licenses/gpl.html
// Home page: http://www.source-code.biz/snippets/typescript/patterns

/// <reference path="Polyfills.ts"/>
/// <reference path="SquareGridPatternGenerator.ts"/>
/// <reference path="Utils.ts"/>

namespace SquareGridPatternFinder1 {

import absSmi                    = Utils.absSmi;
import assertSmi                 = Utils.assertSmi;
import BitSpace                  = Utils.BitSpace;
import BivariateNumericFunction  = Utils.BivariateNumericFunction;
import hypot                     = Polyfills.hypot;
import makeSmi                   = Utils.makeSmi;
import Point                     = Utils.Point;
import UnivariateNumericFunction = Utils.UnivariateNumericFunction;
import wrap                      = Utils.wrap;

export enum FieldType {scalar, vector, vectorDir};

export class FieldConfig {
   influenceRange:              number;                    // integer
   squareRange:                 boolean;                   // true = square, false = circular
   fieldFunction:               UnivariateNumericFunction; // field strength as a function of distance
   fieldType:                   FieldType;
   foldingFactor:               number | null;             // integer, only for vector fields
   dirFunction:                 UnivariateNumericFunction | null; // directional lock-in function (boost value as a function of angle in the range -pi..+pi)
   targetFunction:              UnivariateNumericFunction;}// input: field strength, output: >=0 = the lower the better, <0 = not selectable

export class FinderConfig {
   stepWidth:                   number;                    // integer
   fieldConfigs:                FieldConfig[];
   aggregateFunction:           Function | null; }         // input: field target values, output: >=0 = the lower the better, <0 = not selectable
      // aggregateFunction is ignored if there is only a single field.

//--- Finder -------------------------------------------------------------------

// Architecture: finder -> aggregator -> targetFunction -> integrator -> fieldFunction
export class Finder implements SquareGridPatternGenerator.Finder {

   private bitSpace:            BitSpace;
   private config:              FinderConfig;
   private aggregator:          FieldAggregator;

   constructor (bitSpace: BitSpace, config: FinderConfig) {
      this.bitSpace = bitSpace;
      this.config = config;
      assertSmi(config.stepWidth);
      let n = config.fieldConfigs.length;
      let integrators: FieldIntegrator[] = Array(n);
      let targetFunctions: UnivariateNumericFunction[] = Array(n);
      for (let i = 0; i < n; i++) {
         let fieldConfig = config.fieldConfigs[i];
         integrators[i] = this.createFieldIntegrator(fieldConfig);
         targetFunctions[i] = fieldConfig.targetFunction; }
      this.aggregator = new FieldAggregator(integrators, targetFunctions, config.aggregateFunction); }

   private createFieldIntegrator (fieldConfig: FieldConfig) : FieldIntegrator {
      assertSmi(fieldConfig.influenceRange);
      switch (fieldConfig.fieldType) {
         case FieldType.scalar: {
            return new ScalarFieldIntegrator(this.bitSpace, fieldConfig); }
         case FieldType.vector: {
            return new VectorFieldIntegrator(this.bitSpace, fieldConfig); }
         case FieldType.vectorDir: {
            return new VectorDirFieldIntegrator(this.bitSpace, fieldConfig); }
         default: {
            throw new Error(); }}}

   public findNextPoint (p0: Point) : Point | null {
      let x0:        number = makeSmi(p0.x);
      let y0:        number = makeSmi(p0.y);
      var optX:      number | null = null;
      var optY:      number | null = null;
      var optAggr:   number | null = null;
      let bitSpace = this.bitSpace;
      let width = makeSmi(bitSpace.width);
      let height = makeSmi(bitSpace.height);
      let d = makeSmi(this.config.stepWidth);
      let aggregator = this.aggregator;
      for (let dy = -d; dy <= d; dy++) {
         for (let dx = -d; dx <= d; dx++) {
            let x = wrap(x0 + dx, width);
            let y = wrap(y0 + dy, height);
            if (!bitSpace.getCell(x, y)) {
               let aggr = aggregator.aggregate(x, y);
               if (aggr >= 0 && (aggr < optAggr || optAggr == null)) {
                  optX = x;
                  optY = y;
                  optAggr = aggr; }}}}
      if (optX == null || optY == null) {
         return null; }
      return {x: optX, y: optY}; }}

//--- Field Aggregator ---------------------------------------------------------

class FieldAggregator {

   private integrators:         FieldIntegrator[];
   private targetFunctions:     UnivariateNumericFunction[];
   private aggregateFunction:   Function | null;
   private targetValues:        number[];

   constructor (integrators: FieldIntegrator[], targetFunctions: UnivariateNumericFunction[], aggregateFunction: Function | null) {
      this.integrators = integrators;
      this.targetFunctions = targetFunctions;
      this.aggregateFunction = aggregateFunction;
      this.targetValues = Array(integrators.length); }

   public aggregate (x: number, y: number) : number {
      let n = this.integrators.length;
      let targetValues = this.targetValues;
      for (let i = 0; i < n; i++) {
         let v = this.integrators[i].integrate(x, y);
         targetValues[i] = this.targetFunctions[i](v); }
      if (n == 1) {
         return targetValues[0]; }
      return this.aggregateFunction!.apply(null, targetValues); }}

//--- Field integrators --------------------------------------------------------

interface FieldIntegrator {
   integrate:                   BivariateNumericFunction; }

class ScalarFieldIntegrator implements FieldIntegrator {

   private bitSpace:            BitSpace;
   private fieldConfig:         FieldConfig;
   private fieldMap:            Float64Array;              // maps relative coordinates to scalar field values

   constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) {
      this.bitSpace = bitSpace;
      this.fieldConfig = fieldConfig;
      this.fieldMap = Calc.createScalarFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange); }

   public integrate (px: number, py: number) : number {
      let sum: number = 0;
      let bitSpace = this.bitSpace;
      let width = makeSmi(bitSpace.width);
      let height = makeSmi(bitSpace.height);
      let r = makeSmi(this.fieldConfig.influenceRange);    // makeSmi() is necessary here for V8 optimization!? It's not clear why.
      let w = makeSmi(r + r + 1);
      let fieldMap = this.fieldMap;
      for (let dy = -r; dy <= r; dy++) {
         let y = wrap(py + dy, height);
         let mapNdxBase = (dy + r) * w + r;
         for (let dx = -r; dx <= r; dx++) {
            let x = wrap(px + dx, width);
            if (bitSpace.getCell(x, y)) {
               let p = mapNdxBase + dx;
               sum += fieldMap[p]; }}}
      return sum; }}

class VectorFieldIntegrator implements FieldIntegrator {

   private bitSpace:            BitSpace;
   private fieldConfig:         FieldConfig;
   private fieldMap:            Float64Array;             // maps relative coordinates to vector field X/Y values

   constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) {
      this.bitSpace = bitSpace;
      this.fieldConfig = fieldConfig;
      this.fieldMap = Calc.createVectorFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange, fieldConfig.foldingFactor!); }

   public integrate (px: number, py: number) : number {
      let v = integrateVector(px, py, this.bitSpace, this.fieldConfig.influenceRange, this.fieldMap);
      let strength = hypot(v.x, v.y);
      return strength; }}

function integrateVector (px: number, py: number, bitSpace: BitSpace, influenceRange: number, fieldMap: Float64Array) : Point {
   let sumX: number = 0;
   let sumY: number = 0;
   let width = makeSmi(bitSpace.width);
   let height = makeSmi(bitSpace.height);
   let r = makeSmi(influenceRange);                        // makeSmi() is necessary here for V8 optimization!? It's not clear why.
   let w = makeSmi(r + r + 1);
   for (let dy = -r; dy <= r; dy++) {
      let y = wrap(py + dy, height);
      let mapNdxBase = 2 * ((dy + r) * w + r);
      for (let dx = -r; dx <= r; dx++) {
         let x = wrap(px + dx, width);
         if (bitSpace.getCell(x, y)) {
            let p = mapNdxBase + dx + dx;
            sumX += fieldMap[p];
            sumY += fieldMap[p + 1]; }}}
   return {x: sumX, y: sumY}; }

class VectorDirFieldIntegrator implements FieldIntegrator {

   private bitSpace:            BitSpace;
   private fieldConfig:         FieldConfig;
   private scalarFieldMap:      Float64Array;              // maps relative coordinates to scalar field values
   private vectorFieldMap:      Float64Array;              // maps relative coordinates to vector field X/Y values
   private angleMap:            Float64Array;              // maps relative coordinates to angles in the range -pi..+pi
   private dirFunctionCached:   UnivariateNumericFunction;

   constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) {
      this.bitSpace = bitSpace;
      this.fieldConfig = fieldConfig;
      this.scalarFieldMap = Calc.createScalarFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange);
      this.vectorFieldMap = Calc.createVectorFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange, fieldConfig.foldingFactor!);
      this.angleMap = Calc.createAngleMap(fieldConfig.influenceRange, fieldConfig.foldingFactor!);
      this.dirFunctionCached = Utils.createLinearInterpolationCacheFunction(fieldConfig.dirFunction!, -Math.PI, Math.PI, 0x1001); }

   public integrate (px: number, py: number) : number {
      let v = integrateVector(px, py, this.bitSpace, this.fieldConfig.influenceRange, this.vectorFieldMap);
      if (v.x == 0 && v.y == 0) {
         return 0; }
      let directionAngle = Math.atan2(v.y, v.x);
      // let directionStrength = hypot(v.x, v.y);
      return this.computeFieldStrengthDirected(px, py, directionAngle); }

   private computeFieldStrengthDirected (px: number, py: number, directionAngle: number) : number {
      let sum: number = 0;
      let bitSpace = this.bitSpace;
      let width = makeSmi(bitSpace.width);
      let height = makeSmi(bitSpace.height);
      let r = makeSmi(this.fieldConfig.influenceRange);  // makeSmi() is necessary here for V8 optimization!? It's not clear why.
      let w = makeSmi(r + r + 1);
      let dirFunctionCached = this.dirFunctionCached;
      for (let dy = -r; dy <= r; dy++) {
         let y = wrap(py + dy, height);
         let mapNdxBase = (dy + r) * w + r;
         for (let dx = -r; dx <= r; dx++) {
            let x = wrap(px + dx, width);
            if (bitSpace.getCell(x, y)) {
               let p = mapNdxBase + dx;
               let level = this.scalarFieldMap[p];
               let angle = this.angleMap[p];
               let relAngle = Utils.normalizeAngle(angle - directionAngle);
               let directionalBoost = dirFunctionCached(relAngle);
               // console.log("direction=" + direction + " dx=" + dx + " dy=" + dy + " angle=" + angle + " relAngle=" + relAngle + " dirBoost=" + directionalBoost + " level=" + level);
               sum += level * directionalBoost; }}}
      return sum; }}

//--- Field calculations -------------------------------------------------------

class Calc {

   public static calcPointFieldStrength (dx: number, dy: number, fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean) : number {
      const eps = 1E-9;
      if (dx > -eps && dx < eps && dy > -eps && dy < eps) {
         return 0; }                                                 // field value at 0,0 is undefined and must have no effect
      if (dx < -range - eps || dx > range + eps || dy < -range - eps || dy > range + eps) {
         return 0; }
      let d = hypot(dx, dy);
      if (!squareRange && d > range + eps) {
         return 0; }
      return fieldFunction(d); }

   public static createScalarFieldMap (fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean) : Float64Array {
      let w = 2 * range + 1;
      let map = new Float64Array(w * w);
      for (let dy = -range; dy <= range; dy++) {
         for (let dx = -range; dx <= range; dx++) {
            let p = (dy + range) * w + dx + range;
            map[p] = Calc.calcPointFieldStrength(dx, dy, fieldFunction, range, squareRange); }}
      return map; }

   public static calcPointFieldVector (dx: number, dy: number, fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean, foldingFactor: number) : Point {
      const eps = 1E-9;
      if (dx > -eps && dx < eps && dy > -eps && dy < eps) {
         return new Point(0, 0); }                                   // field value at 0,0 is undefined and must have no effect
      if (dx < -range - eps || dx > range + eps || dy < -range - eps || dy > range + eps) {
         return new Point(0, 0); }
      let d = hypot(dx, dy);
      if (!squareRange && d > range + eps) {
         return new Point(0, 0); }
      let fieldStrength = fieldFunction(d);
      if (foldingFactor == 1) {
         let vx = dx / d * fieldStrength;
         let vy = dy / d * fieldStrength;
         return new Point(vx, vy); }
      let arg = Math.atan2(dy, dx) * foldingFactor;
      let vx = Math.cos(arg) * fieldStrength;
      let vy = Math.sin(arg) * fieldStrength;
      // console.log("y=" + dy + " x=" + dx + " d=" + d + " arg=" + arg + " vy=" + vy + " vx=" + vx);
      return new Point(vx, vy); }

   public static createVectorFieldMap (fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean, foldingFactor: number) : Float64Array {
      let w = 2 * range + 1;
      let map = new Float64Array(2 * w * w);
      for (let dy = -range; dy <= range; dy++) {
         for (let dx = -range; dx <= range; dx++) {
            let v = Calc.calcPointFieldVector(dx, dy, fieldFunction, range, squareRange, foldingFactor);
            let p = 2 * ((dy + range) * w + dx + range);
            map[p    ] = v.x;
            map[p + 1] = v.y; }}
      return map; }

   public static calcPointAngle (dx: number, dy: number, foldingFactor: number) {
      let a = Math.atan2(dy, dx);
      return Utils.normalizeAngle(a * foldingFactor); }

   public static createAngleMap (range: number, foldingFactor: number) : Float64Array {
      let w = 2 * range + 1;
      let map = new Float64Array(w * w);
      for (let dy = -range; dy <= range; dy++) {
         for (let dx = -range; dx <= range; dx++) {
            let p = (dy + range) * w + dx + range;
            map[p] = Calc.calcPointAngle(dx, dy, foldingFactor); }}
      return map; }}

//--- Info ---------------------------------------------------------------------

export function genScalarFieldInfo (fieldFunction: UnivariateNumericFunction, influenceRange: number, squareRange: boolean) : string {
   let minSum = 0, maxSum = 0, fullSum = 0;
   let r = influenceRange;
   for (let dy = -r; dy <= r; dy++) {
      for (let dx = -r; dx <= r; dx++) {
         let fieldStrength = Calc.calcPointFieldStrength(dx, dy, fieldFunction, r, squareRange);
         if (fieldStrength < 0) {
            minSum += fieldStrength; }
         if (fieldStrength > 0) {
            maxSum += fieldStrength; }
         fullSum += fieldStrength; }}
   return (minSum == 0 ? "" : "min=" + minSum.toFixed(2) + " ") + "max=" + maxSum.toFixed(2) + (fullSum == maxSum ? "" : " full=" + fullSum.toFixed(2)); }

export function genVectorFieldInfo (fieldFunction: UnivariateNumericFunction, influenceRange: number, squareRange: boolean, foldingFactor: number) : string {
   // const eps = 1E-9;
   // let sum180 = 0, sum90x = 0, sum90y = 0;
   // let sum = new Point(0, 0);
   // let sec: Point[] = Array(5);
   // for (let i = 0; i < 5; i++) {
   //    sec[i] = new Point(0, 0); }
   let sumX = 0;
   let r = influenceRange;
   for (let dy = -r; dy <= r; dy++) {
      for (let dx = -r; dx <= r; dx++) {
         let v = Calc.calcPointFieldVector(dx, dy, fieldFunction, r, squareRange, foldingFactor);
         // if (v.x > 0) {
         //    sum180 += v.x; }
         // if (v.x >= -eps && v.y >= -eps) {
         //    sum90x += v.x;
         //    sum90y += v.y; }}
         // sum.x += v.x; sum.y += v.y;
         // let i = getVectorSectorOrAxis(v);
         // sec[i].x += v.x;
         // sec[i].y += v.y;
         if (v.x > 0) {
            sumX += v.x; }
         }}
   // let sum90 = hypot(sum90x, sum90y);
   // return "sum180=" + sum180.toFixed(2) + " sum90=" + sum90.toFixed(2) + " (" + sum90x.toFixed(2) + ", " + sum90y.toFixed(2) + ")";
   // return "sum=" + sum.x + "/" + sum.y;
   // let s = "<br>";
   // for (let i = 0; i < 5; i++) {
   //   s += "sec" + i + "=" + sec[i].x + "/" + sec[i].y + " "; }
   // return s; }
   return "max=" + sumX.toFixed(2); }

function getVectorSector (v: Point) : number {
   const eps = 1E-9;
   if (v.x >= eps && v.y > -eps) {
      return 0; }
    else if (v.x < eps && v.y >= eps) {
      return 1; }
    else if (v.x <= -eps && v.y < eps) {
      return 2; }
    else {
      return 3; }}

// Returns 4 if the point is on the x or y axis.
function getVectorSectorOrAxis (v: Point) : number {
   const eps = 1E-9;
   if (v.x > -eps && v.x < eps || v.y > -eps && v.y < eps) {
      return 4; }
   if (v.y > 0) {
      if (v.x > 0) {
         return 0; }
       else {
         return 1; }}
    else {
      if (v.x < 0) {
         return 2; }
       else {
         return 3; }}}

} // end namespace SquareGridFinder1