/*
 * Copyright 2008 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 * 
 * Modifications to this file made by IBM are copyright (c) 2008 IBM Corporation 
 * 
 */
package com.google.gwt.lang;

import com.google.gwt.core.client.UnsafeNativeLong;

/**
 * Implements a Java <code>long</code> in a way that can be translated to
 * JavaScript.
 */
public class LongLib {
  /*
   * Implementation: An array of two doubles, low and high, such that high+low
   * is mathematically equivalent to the original integer. Since a JavaScript
   * Number does not hold enough bits to precisely calculate high+low, all
   * operations must be implemented carefully. "low" is always between 0 and
   * 2^32-1 inclusive. "high" is always between -2^63 and 2^63-2^32 inclusive
   * and is a multiple of 2^32. The sign of the number is determined entirely by
   * "high". Since low is always positive, small negative numbers are encoded
   * with high=-2^32. For example, -1 is encoded as { high=-2^32, low=2^32-1 }.
   * 
   * Note that this class must be careful using type "long". Being the
   * implementation of the long type for web mode, any place it uses a long is
   * not usable in web mode. There are currently two such methods:
   * {@link #toLong(double[])} and {@link #make(long)}.
   * 
   * The GWT RPC serialization code is dependent on the internal format of the
   * long type; any changes made to this class should be reflected in the
   * implementations of SerializationStreamReader and Writer.
   */

  /**
   * Use nested class to avoid clinit on outer.
   */
////TODO: e4 handle inner classes
 // static class CachedInts {
    // Between -128 and 127.
    static double[][] boxedValues = new double[256][];
  //}

  //TODO: e4 handle inner classes
 // static class Const {
    static final double LN_2 = Math.log(2);
    static final double[] MAX_VALUE = typeChange(Long.MAX_VALUE);
    static final double[] MIN_VALUE = typeChange(Long.MIN_VALUE);
    static final double[] NEG_ONE = fromInt(-1);
    static final double[] ONE = fromInt(1);
    static final double[] TWO = fromInt(2);

    /**
     * Half of the number of bits we expect to be precise.
     * 
     * @see LongLib#PRECISION_BITS
     */
    static final double[] TWO_PWR_24 = typeChange(0x1000000L);

    static final double[] ZERO = fromInt(0);
  //}

  /**
   * Set this to false before calling any methods when using this class outside
   * of GWT!
   */
  public static boolean RUN_IN_JVM = false;

  /**
   * Number of bits we expect to be accurate for a double representing a large
   * integer.
   */
  private static final int PRECISION_BITS = 48;

  /**
   * Index of the high bits in a 2-double array.
   */
  private static final int HIGH = 1;
  private static final double HIGH_MAX = 9223372032559808512d;
  private static final double HIGH_MIN = -9223372036854775808d;

  /**
   * Index of the low bits in a 2-double array.
   */
  private static final int LOW = 0;
  private static final double LOW_MAX = 4294967295d;
  private static final double LOW_MIN = 0;

  private static final double TWO_PWR_15_DBL = 0x8000;
  private static final double TWO_PWR_16_DBL = 0x10000;
  private static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL * TWO_PWR_15_DBL;
  private static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL;
  private static final double TWO_PWR_48_DBL = TWO_PWR_32_DBL * TWO_PWR_16_DBL;
  private static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL * TWO_PWR_31_DBL;
  private static final double TWO_PWR_64_DBL = TWO_PWR_32_DBL * TWO_PWR_32_DBL;

  public static double[] add(double[] a, double[] b) {
    double newHigh = a[HIGH] + b[HIGH];
    double newLow = a[LOW] + b[LOW];
    return create(newLow, newHigh);
  }

  public static double[] and(double[] a, double[] b) {
    return makeFromBits(highBits(a) & highBits(b), lowBits(a) & lowBits(b));
  }

  /**
   * Compare the receiver to the argument.
   * 
   * @return 0 if they are the same, 1 if the receiver is greater, -1 if the
   *         argument is greater.
   */
  public static int compare(double[] a, double[] b) {
    if (eq(a, b)) {
      return 0;
    }

    boolean nega = isNegative(a);
    boolean negb = isNegative(b);
    if (nega && !negb) {
      return -1;
    }
    if (!nega && negb) {
      return 1;
    }

    // at this point, the signs are the same, so subtraction will not overflow
    ////TODO: e4 fix assert
    //assert (nega == negb);
    if (isNegative(sub(a, b))) {
      return -1;
    } else {
      return 1;
    }
  }

  public static double[] div(double[] a, double[] b) {
    if (isZero(b)) {
      throw new ArithmeticException("/ by zero");
    }
    if (isZero(a)) {
      return ZERO;
    }

    if (eq(a, MIN_VALUE)) {
      // handle a==MIN_VALUE carefully because of overflow issues
      if (eq(b, ONE) || eq(b, NEG_ONE)) {
        // this strange exception is described in JLS3 17.17.2
        return MIN_VALUE;
      }
      // at this point, abs(b) >= 2, so |a/b| < -MIN_VALUE
      double[] halfa = shr(a, 1);
      double[] approx = shl(div(halfa, b), 1);
      double[] rem = sub(a, mul(b, approx));
    //TODO: e4 fix assert
      //  assert gt(rem, MIN_VALUE);
      return add(approx, div(rem, b));
    }

    if (eq(b, MIN_VALUE)) {
      //TODO: e4 fix assert
      //assert !eq(a, MIN_VALUE);
      return ZERO;
    }

    // To keep the implementation compact, make a and be
    // both be positive and swap the sign of the result
    // if necessary.
    if (isNegative(a)) {
      if (isNegative(b)) {
        return div(neg(a), neg(b));
      } else {
        return neg(div(neg(a), b));
      }
    }
  //TODO: e4 fix assert
    //assert (!isNegative(a));
    if (isNegative(b)) {
      return neg(div(a, neg(b)));
    }
  //TODO: e4 fix assert
    //assert (!isNegative(b));

    // Use float division to approximate the answer.
    // Repeat until the remainder is less than b.
    double[] result = ZERO;
    double[] rem = a;
    while (gte(rem, b)) {
      // approximate using float division
      double[] deltaResult = fromDouble(Math.floor(toDoubleRoundDown(rem)
          / toDoubleRoundUp(b)));
      if (isZero(deltaResult)) {
    	//TODO: e4 support inner classes
        //deltaResult = Const.ONE;
        deltaResult = ONE;
      }
      double[] deltaRem = mul(deltaResult, b);

    //TODO: e4 fix assert
      //assert gte(deltaResult, ONE);
      //assert lte(deltaRem, rem);
      result = add(result, deltaResult);
      rem = sub(rem, deltaRem);
    }

    return result;
  }

  public static boolean eq(double[] a, double[] b) {
    return ((a[LOW] == b[LOW]) && (a[HIGH] == b[HIGH]));
  }

  public static double[] fromDouble(double value) {
    if (Double.isNaN(value)) {
      return ZERO;
    }
    if (value < -TWO_PWR_63_DBL) {
      return MIN_VALUE;
    }
    if (value >= TWO_PWR_63_DBL) {
      return MAX_VALUE;
    }
    if (value > 0) {
      return create(Math.floor(value), 0.0);
    } else {
      return create(Math.ceil(value), 0.0);
    }
  }

  public static double[] fromInt(int value) {
    if (value > -129 && value < 128) {
      int rebase = value + 128;
    //TODO: e4 support inner classes
      //double[] result = CachedInts.boxedValues[rebase];
      double[] result = boxedValues[rebase];
      if (result == null) {
    	//TODO: e4 support inner classes
        //result = CachedInts.boxedValues[rebase] = internalFromInt(value);
    	 result = boxedValues[rebase] = internalFromInt(value);
      }
      return result;
    }
    return internalFromInt(value);
  }

  public static boolean gt(double[] a, double[] b) {
    return compare(a, b) > 0;
  }

  public static boolean gte(double[] a, double[] b) {
    return compare(a, b) >= 0;
  }

  public static boolean lt(double[] a, double[] b) {
    return compare(a, b) < 0;
  }

  public static boolean lte(double[] a, double[] b) {
    return compare(a, b) <= 0;
  }

  public static double[] mod(double[] a, double[] b) {
    return sub(a, mul(div(a, b), b));
  }

  public static double[] mul(double[] a, double[] b) {
    if (isZero(a)) {
      return ZERO;
    }
    if (isZero(b)) {
      return ZERO;
    }

    // handle MIN_VALUE carefully, because neg(MIN_VALUE)==MIN_VALUE
    if (eq(a, MIN_VALUE)) {
      return multByMinValue(b);
    }
    if (eq(b, MIN_VALUE)) {
      return multByMinValue(a);
    }

    // If either argument is negative, change it to positive, multiply,
    // and then negate the result.
    if (isNegative(a)) {
      if (isNegative(b)) {
        return mul(neg(a), neg(b));
      } else {
        return neg(mul(neg(a), b));
      }
    }
    //TODO: e4 fix assert
    //assert (!isNegative(a));
    if (isNegative(b)) {
      return neg(mul(a, neg(b)));
    }
    //TODO: e4 fix assert
    //assert (!isNegative(b));

    // If both numbers are small, use float multiplication
    if (lt(a, TWO_PWR_24) && lt(b, TWO_PWR_24)) {
      return create(toDouble(a) * toDouble(b), 0.0);
    }

    // Divide each number into 4 chunks of 16 bits, and then add
    // up 4x4 multiplies. Skip the six multiplies where the result
    // mod 2^64 would be 0.
    double a3 = a[HIGH] % TWO_PWR_48_DBL;
    double a4 = a[HIGH] - a3;
    double a1 = a[LOW] % TWO_PWR_16_DBL;
    double a2 = a[LOW] - a1;

    double b3 = b[HIGH] % TWO_PWR_48_DBL;
    double b4 = b[HIGH] - b3;
    double b1 = b[LOW] % TWO_PWR_16_DBL;
    double b2 = b[LOW] - b1;

    double[] res = ZERO;

    res = addTimes(res, a4, b1);
    res = addTimes(res, a3, b2);
    res = addTimes(res, a3, b1);
    res = addTimes(res, a2, b3);
    res = addTimes(res, a2, b2);
    res = addTimes(res, a2, b1);
    res = addTimes(res, a1, b4);
    res = addTimes(res, a1, b3);
    res = addTimes(res, a1, b2);
    res = addTimes(res, a1, b1);

    return res;
  }

  public static double[] neg(double[] a) {
    if (eq(a, MIN_VALUE)) {
      return MIN_VALUE;
    }
    double newHigh = -a[HIGH];
    double newLow = -a[LOW];
    if (newLow > LOW_MAX) {
      newLow -= TWO_PWR_32_DBL;
      newHigh += TWO_PWR_32_DBL;
    }
    if (newLow < LOW_MIN) {
      newLow += TWO_PWR_32_DBL;
      newHigh -= TWO_PWR_32_DBL;
    }
    return createNormalized(newLow, newHigh);
  }

  public static boolean neq(double[] a, double[] b) {
    return ((a[LOW] != b[LOW]) || (a[HIGH] != b[HIGH]));
  }

  public static double[] not(double[] a) {
    return makeFromBits(~highBits(a), ~lowBits(a));
  }

  public static double[] or(double[] a, double[] b) {
    return makeFromBits(highBits(a) | highBits(b), lowBits(a) | lowBits(b));
  }

  public static double[] shl(double[] a, int n) {
    n &= 63;

    if (eq(a, MIN_VALUE)) {
      if (n == 0) {
        return a;
      } else {
        return ZERO;
      }
    }

    if (isNegative(a)) {
      return neg(shl(neg(a), n));
    }

    final double twoToN = pwrAsDouble(n);

    double newHigh = a[HIGH] * twoToN % TWO_PWR_64_DBL;
    double newLow = a[LOW] * twoToN;
    double diff = newLow - (newLow % TWO_PWR_32_DBL);
    newHigh += diff;
    newLow -= diff;
    if (newHigh >= TWO_PWR_63_DBL) {
      newHigh -= TWO_PWR_64_DBL;
    }

    return createNormalized(newLow, newHigh);
  }

  public static double[] shr(double[] a, int n) {
    n &= 63;
    double shiftFact = pwrAsDouble(n);
    double newHigh = a[HIGH] / shiftFact;
    double newLow = Math.floor(a[LOW] / shiftFact);
    return create(newLow, newHigh);
  }

  /**
   * Logical right shift. It does not preserve the sign of the input.
   */
  public static double[] shru(double[] a, int n) {
    n &= 63;
    double[] sr = shr(a, n);
    if (isNegative(a)) {
      // the following changes the high bits to 0, using
      // a formula from JLS3 section 15.19
      sr = add(sr, shl(TWO, 63 - n));
    }

    return sr;
  }

  public static double[] sub(double[] a, double[] b) {
    double newHigh = a[HIGH] - b[HIGH];
    double newLow = a[LOW] - b[LOW];
    return create(newLow, newHigh);
  }

  /**
   * Cast from long to double or float.
   */
  public static double toDouble(double[] a) {
    return a[HIGH] + a[LOW];
  }

  /**
   * Cast from long to int.
   */
  public static int toInt(double[] a) {
    return lowBits(a);
  }

  /**
   * Implicit conversion from long to String.
   */
  public static String toString(double[] a) {
    if (isZero(a)) {
      return "0";
    }

    if (eq(a, MIN_VALUE)) {
      // Special-case MIN_VALUE because neg(MIN_VALUE)==MIN_VALUE
      return "-9223372036854775808";
    }

    if (isNegative(a)) {
      return "-" + toString(neg(a));
    }

    double[] rem = a;
    String res = "";

    while (!isZero(rem)) {
      // Do several digits each time through the loop, so as to
      // minimize the calls to the very expensive emulated div.
      final int divByZeroes = 9;
      final int divBy = 1000000000;

      String digits = "" + toInt(mod(rem, fromInt(divBy)));
      rem = div(rem, fromInt(divBy));

      if (!isZero(rem)) {
        int zeroesNeeded = divByZeroes - digits.length();
        for (; zeroesNeeded > 0; zeroesNeeded--) {
          digits = "0" + digits;
        }
      }

      res = digits + res;
    }

    return res;
  }

  public static double[] typeChange(long value) {
    if (RUN_IN_JVM) {
      return makeFromBits((int) (value >> 32), (int) value);
    } else {
      return typeChange0(value);
    }
  }

  public static double[] xor(double[] a, double[] b) {
    return makeFromBits(highBits(a) ^ highBits(b), lowBits(a) ^ lowBits(b));
  }

  static long toLong(double[] a) {
    return (long) a[HIGH] + (long) a[LOW];
  }

  private static double[] addTimes(double[] accum, double a, double b) {
    if (a == 0.0) {
      return accum;
    }
    if (b == 0.0) {
      return accum;
    }
    return add(accum, create(a * b, 0.0));
  }

  /*
   * Make a new instance equal to valueLow+valueHigh. The arguments do not need
   * to be normalized, though by convention valueHigh and valueLow will hold the
   * high and low bits, respectively.
   */
  private static double[] create(double valueLow, double valueHigh) {
	  //TODO: e4 fix assert
    //assert (!Double.isNaN(valueHigh));
    //assert (!Double.isNaN(valueLow));
    //assert (!Double.isInfinite(valueHigh));
    //assert (!Double.isInfinite(valueLow));
    //assert (Math.floor(valueHigh) == valueHigh);
    //assert (Math.floor(valueLow) == valueLow);

    // remove overly high bits
    valueHigh %= TWO_PWR_64_DBL;
    valueLow %= TWO_PWR_64_DBL;

    // segregate high and low bits between high and low
    {
      double diffHigh = valueHigh % TWO_PWR_32_DBL;
      double diffLow = Math.floor(valueLow / TWO_PWR_32_DBL) * TWO_PWR_32_DBL;

      valueHigh = (valueHigh - diffHigh) + diffLow;
      valueLow = (valueLow - diffLow) + diffHigh;
    }

    // Most or all of the while's in this implementation could probably be if's,
    // but they are left as while's for now pending a careful review.

    // make valueLow be positive
    while (valueLow < LOW_MIN) {
      valueLow += TWO_PWR_32_DBL;
      valueHigh -= TWO_PWR_32_DBL;
    }

    // make valueLow not too large
    while (valueLow > LOW_MAX) {
      valueLow -= TWO_PWR_32_DBL;
      valueHigh += TWO_PWR_32_DBL;
    }

    // make valueHigh within range
    valueHigh = valueHigh % TWO_PWR_64_DBL;
    while (valueHigh > HIGH_MAX) {
      valueHigh -= TWO_PWR_64_DBL;
    }
    while (valueHigh < HIGH_MIN) {
      valueHigh += TWO_PWR_64_DBL;
    }

    return createNormalized(valueLow, valueHigh);
  }

  /**
   * Create an instance. The high and low parts must be normalized. Normal
   * callers should use the factory method {@link #make(double, double) make}.
   */
  private static double[] createNormalized(double valueLow, double valueHigh) {
	//TODO: e4 fix assert
    //assert (valueHigh <= HIGH_MAX);
    //assert (valueHigh >= HIGH_MIN);
    //assert (valueLow >= 0);
    //assert (valueLow <= LOW_MAX);
    //assert (valueHigh % TWO_PWR_32_DBL == 0);
    //assert (Math.floor(valueLow) == valueLow); // no fractional bits allowed

    if (RUN_IN_JVM) {
      return new double[] {valueLow, valueHigh};
    } else {
      return newLong0(valueLow, valueHigh);
    }
  }

  private static int highBits(double[] a) {
    return (int) (a[HIGH] / TWO_PWR_32_DBL);
  }

  private static double[] internalFromInt(int value) {
    if (value >= 0) {
      return createNormalized(value, 0.0);
    } else {
      return createNormalized(value + TWO_PWR_32_DBL, -TWO_PWR_32_DBL);
    }
  }

  private static boolean isNegative(double[] a) {
    return a[HIGH] < 0;
  }

  private static boolean isOdd(double[] a) {
    return (lowBits(a) & 1) == 1;
  }

  private static boolean isZero(double[] a) {
    return a[LOW] == 0.0 && a[HIGH] == 0.0;
  }

  private static int lowBits(double[] a) {
    if (a[LOW] >= TWO_PWR_31_DBL) {
      return (int) (a[LOW] - TWO_PWR_32_DBL);
    } else {
      return (int) a[LOW];
    }
  }

  /**
   * Make an instance equivalent to stringing highBits next to lowBits, where
   * highBits and lowBits are assumed to be in 32-bit twos-complement notation.
   * As a result, for any double[] l, the following identity holds:
   * 
   * <blockquote> <code>l == makeFromBits(l.highBits(), l.lowBits())</code>
   * </blockquote>
   */
  private static double[] makeFromBits(int highBits, int lowBits) {
    double high = highBits * TWO_PWR_32_DBL;
    double low = lowBits;
    if (lowBits < 0) {
      low += TWO_PWR_32_DBL;
    }
    return createNormalized(low, high);
  }

  private static double[] multByMinValue(double[] a) {
    if (isOdd(a)) {
      return MIN_VALUE;
    } else {
      return ZERO;
    }
  }

  /**
   * Faster web mode implementation doesn't need full type semantics.
   */
  private static native double[] newLong0(double valueLow, double valueHigh) /*-{
  	var array = @java.lang.JavaArray::new(Ljava/lang/String;)("D");
  	array.array = [valueLow, valueHigh];
  	return array;
    //e4 explicity create array
    //return [valueLow, valueHigh];
  }-*/;

  /**
   * Return a power of two as a double.
   * 
   * @return 2 raised to the <code>n</code>
   */
  private static double pwrAsDouble(int n) {
    if (n <= 30) {
      return (1 << n);
    } else {
      return pwrAsDouble(30) * pwrAsDouble(n - 30);
    }
  }

  private static double toDoubleRoundDown(double[] a) {
    int magnitute = (int) (Math.log(a[HIGH]) / LN_2);
    if (magnitute <= PRECISION_BITS) {
      return toDouble(a);
    } else {
      int diff = magnitute - PRECISION_BITS;
      int toSubtract = (1 << diff) - 1;
      return a[HIGH] + (a[LOW] - toSubtract);
    }
  }

  private static double toDoubleRoundUp(double[] a) {
    int magnitute = (int) (Math.log(a[HIGH]) / LN_2);
    if (magnitute <= PRECISION_BITS) {
      return toDouble(a);
    } else {
      int diff = magnitute - PRECISION_BITS;
      int toAdd = (1 << diff) - 1;
      return a[HIGH] + (a[LOW] + toAdd);
    }
  }

  /**
   * Web mode implementation; the long is already the right object.
   */
  @UnsafeNativeLong
  private static native double[] typeChange0(long value) /*-{
   	var array = @java.lang.JavaArray::new(Ljava/lang/String;)("D");
  	array.array = [value];
  	return array;
  	//TODO: e4 explicitly create an array
    //return value;
  }-*/;

  /**
   * Not instantiable.
   */
  private LongLib() {
  }

}
