// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

abstract class _IntegerImplementation {
  // The Dart class _Bigint extending _IntegerImplementation requires a
  // default constructor.

  num operator +(num other) {
    var result = other._addFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._addFromInteger(this);
  }
  num operator -(num other) {
    var result = other._subFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._subFromInteger(this);
  }
  num operator *(num other) {
    var result = other._mulFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._mulFromInteger(this);
  }
  num operator ~/(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    var result = other._truncDivFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._truncDivFromInteger(this);
  }
  num operator /(num other) {
    return this.toDouble() / other.toDouble();
  }
  num operator %(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    var result = other._moduloFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._moduloFromInteger(this);
  }
  int operator -() {
    return 0 - this;
  }
  int operator &(int other) {
    var result = other._bitAndFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitAndFromInteger(this);
  }
  int operator |(int other) {
    var result = other._bitOrFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitOrFromInteger(this);
  }
  int operator ^(int other) {
    var result = other._bitXorFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitXorFromInteger(this);
  }
  num remainder(num other) {
    return other._remainderFromInteger(this);
  }
  int _bitAndFromSmi(int other) native "Integer_bitAndFromInteger";
  int _bitAndFromInteger(int other) native "Integer_bitAndFromInteger";
  int _bitOrFromInteger(int other) native "Integer_bitOrFromInteger";
  int _bitXorFromInteger(int other) native "Integer_bitXorFromInteger";
  int _addFromInteger(int other) native "Integer_addFromInteger";
  int _subFromInteger(int other) native "Integer_subFromInteger";
  int _mulFromInteger(int other) native "Integer_mulFromInteger";
  int _truncDivFromInteger(int other) native "Integer_truncDivFromInteger";
  int _moduloFromInteger(int other) native "Integer_moduloFromInteger";
  int _remainderFromInteger(int other) {
    return other - (other ~/ this) * this;
  }
  int operator >>(int other) {
    var result = other._shrFromInt(this);
    if (result != null) return result;
    return other._toBigint()._shrFromInt(this);
  }
  int operator <<(int other) {
    var result = other._shlFromInt(this);
    if (result != null) return result;
    return other._toBigint()._shlFromInt(this);
  }
  bool operator <(num other) {
    return other > this;
  }
  bool operator >(num other) {
    return other._greaterThanFromInteger(this);
  }
  bool operator >=(num other) {
    return (this == other) ||  (this > other);
  }
  bool operator <=(num other) {
    return (this == other) || (this < other);
  }
  bool _greaterThanFromInteger(int other)
      native "Integer_greaterThanFromInteger";
  bool operator ==(other) {
    if (other is num) {
      return other._equalToInteger(this);
    }
    return false;
  }
  bool _equalToInteger(int other) native "Integer_equalToInteger";
  int abs() {
    return this < 0 ? -this : this;
  }
  int get sign {
    return (this > 0) ? 1 : (this < 0) ? -1 : 0;
  }
  bool get isEven => ((this & 1) == 0);
  bool get isOdd => !isEven;
  bool get isNaN => false;
  bool get isNegative => this < 0;
  bool get isInfinite => false;
  bool get isFinite => true;

  int toUnsigned(int width) {
    return this & ((1 << width) - 1);
  }

  int toSigned(int width) {
    // The value of binary number weights each bit by a power of two.  The
    // twos-complement value weights the sign bit negatively.  We compute the
    // value of the negative weighting by isolating the sign bit with the
    // correct power of two weighting and subtracting it from the value of the
    // lower bits.
    int signMask = 1 << (width - 1);
    return (this & (signMask - 1)) - (this & signMask);
  }

  int compareTo(num other) {
    const int EQUAL = 0, LESS = -1, GREATER = 1;
    if (other is double) {
      const int MAX_EXACT_INT_TO_DOUBLE = 9007199254740992;  // 2^53.
      const int MIN_EXACT_INT_TO_DOUBLE = -MAX_EXACT_INT_TO_DOUBLE;
      double d = other;
      if (d.isInfinite) {
        return d == double.NEGATIVE_INFINITY ? GREATER : LESS;
      }
      if (d.isNaN) {
        return LESS;
      }
      if (MIN_EXACT_INT_TO_DOUBLE <= this && this <= MAX_EXACT_INT_TO_DOUBLE) {
        // Let the double implementation deal with -0.0.
        return -(d.compareTo(this.toDouble()));
      } else {
        // If abs(other) > MAX_EXACT_INT_TO_DOUBLE, then other has an integer
        // value (no bits below the decimal point).
        other = d.toInt();
      }
    }
    if (this < other) {
      return LESS;
    } else if (this > other) {
      return GREATER;
    } else {
      return EQUAL;
    }
  }

  int round() { return this; }
  int floor() { return this; }
  int ceil() { return this; }
  int truncate() { return this; }

  double roundToDouble() { return this.toDouble(); }
  double floorToDouble() { return this.toDouble(); }
  double ceilToDouble() { return this.toDouble(); }
  double truncateToDouble() { return this.toDouble(); }

  num clamp(num lowerLimit, num upperLimit) {
    if (lowerLimit is! num) {
      throw new ArgumentError.value(lowerLimit, "lowerLimit", "not a number");
    }
    if (upperLimit is! num) {
      throw new ArgumentError.value(upperLimit, "upperLimit", "not a number");
    }

    // Special case for integers.
    if (lowerLimit is int && upperLimit is int && lowerLimit <= upperLimit) {
      if (this < lowerLimit) return lowerLimit;
      if (this > upperLimit) return upperLimit;
      return this;
    }
    // Generic case involving doubles, and invalid integer ranges.
    if (lowerLimit.compareTo(upperLimit) > 0) {
      throw new ArgumentError(lowerLimit);
    }
    if (lowerLimit.isNaN) return lowerLimit;
    // Note that we don't need to care for -0.0 for the lower limit.
    if (this < lowerLimit) return lowerLimit;
    if (this.compareTo(upperLimit) > 0) return upperLimit;
    return this;
  }

  int toInt() { return this; }
  double toDouble() { return new _Double.fromInteger(this); }
  _Bigint _toBigint() { return new _Bigint._fromInt(this); }
  num _toBigintOrDouble() { return _toBigint(); }

  String toStringAsFixed(int fractionDigits) {
    return this.toDouble().toStringAsFixed(fractionDigits);
  }
  String toStringAsExponential([int fractionDigits]) {
    return this.toDouble().toStringAsExponential(fractionDigits);
  }
  String toStringAsPrecision(int precision) {
    return this.toDouble().toStringAsPrecision(precision);
  }

  static const _digits = "0123456789abcdefghijklmnopqrstuvwxyz";

  String toRadixString(int radix) {
    if (radix < 2 || 36 < radix) {
      throw new RangeError.range(radix, 2, 36, "radix");
    }
    if (radix & (radix - 1) == 0) {
      return _toPow2String(radix);
    }
    if (radix == 10) return this.toString();
    final bool isNegative = this < 0;
    int value = isNegative ? -this : this;
    List temp = new List();
    do {
      int digit = value % radix;
      value ~/= radix;
      temp.add(_digits.codeUnitAt(digit));
    } while (value > 0);
    if (isNegative) temp.add(0x2d);  // '-'.

    _OneByteString string = _OneByteString._allocate(temp.length);
    for (int i = 0, j = temp.length; j > 0; i++) {
      string._setAt(i, temp[--j]);
    }
    return string;
  }

  String _toPow2String(int radix) {
    int value = this;
    if (value == 0) return "0";
    assert(radix & (radix - 1) == 0);
    var negative = value < 0;
    var bitsPerDigit = radix.bitLength - 1;
    var length = 0;
    if (negative) {
      value = -value;
      length = 1;
    }
    // Integer division, rounding up, to find number of _digits.
    length += (value.bitLength + bitsPerDigit - 1) ~/ bitsPerDigit;
    _OneByteString string = _OneByteString._allocate(length);
    string._setAt(0, 0x2d);  // '-'. Is overwritten if not negative.
    var mask = radix - 1;
    do {
      string._setAt(--length, _digits.codeUnitAt(value & mask));
      value >>= bitsPerDigit;
    } while (value > 0);
    return string;
  }

  // Returns pow(this, e) % m.
  int modPow(int e, int m) {
    if (e is! int) {
      throw new ArgumentError.value(e, "exponent", "not an integer");
    }
    if (m is! int) {
      throw new ArgumentError.value(m, "modulus", "not an integer");
    }
    if (e < 0) throw new RangeError.range(e, 0, null, "exponent");
    if (m <= 0) throw new RangeError.range(m, 1, null, "modulus");
    if (e == 0) return 1;
    if (e is _Bigint || m is _Bigint) {
      return _toBigint().modPow(e, m);
    }
    int b = this;
    if (b < 0 || b > m) {
      b %= m;
    }
    int r = 1;
    while (e > 0) {
      if (e.isOdd) {
        r = (r * b) % m;
      }
      e >>= 1;
      b = (b * b) % m;
    }
    return r;
  }

  // If inv is false, returns gcd(x, y).
  // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1.
  // If inv is true and gcd(x, y) != 1, throws Exception("Not coprime").
  static int _binaryGcd(int x, int y, bool inv) {
    int s = 0;
    if (!inv) {
      while (x.isEven && y.isEven) {
        x >>= 1;
        y >>= 1;
        s++;
      }
      if (y.isOdd) {
        var t = x;
        x = y;
        y = t;
      }
    }
    final bool ac = x.isEven;
    int u = x;
    int v = y;
    int a = 1,
        b = 0,
        c = 0,
        d = 1;
    do {
      while (u.isEven) {
        u >>= 1;
        if (ac) {
          if (!a.isEven || !b.isEven) {
            a += y;
            b -= x;
          }
          a >>= 1;
        } else if (!b.isEven) {
          b -= x;
        }
        b >>= 1;
      }
      while (v.isEven) {
        v >>= 1;
        if (ac) {
          if (!c.isEven || !d.isEven) {
            c += y;
            d -= x;
          }
          c >>= 1;
        } else if (!d.isEven) {
          d -= x;
        }
        d >>= 1;
      }
      if (u >= v) {
        u -= v;
        if (ac) a -= c;
        b -= d;
      } else {
        v -= u;
        if (ac) c -= a;
        d -= b;
      }
    } while (u != 0);
    if (!inv) return v << s;
    if (v != 1) {
      throw new Exception("Not coprime");
    }
    if (d < 0) {
      d += x;
      if (d < 0) d += x;
    } else if (d > x) {
      d -= x;
      if (d > x) d -= x;
    }
    return d;
  }

  // Returns 1/this % m, with m > 0.
  int modInverse(int m) {
    if (m is! int) {
      throw new ArgumentError.value(m, "modulus", "not an integer");
    }
    if (m <= 0) throw new RangeError.range(m, 1, null, "modulus");
    if (m == 1) return 0;
    if (m is _Bigint) {
      return _toBigint().modInverse(m);
    }
    int t = this;
    if ((t < 0) || (t >= m)) t %= m;
    if (t == 1) return 1;
    if ((t == 0) || (t.isEven && m.isEven)) {
      throw new Exception("Not coprime");
    }
    return _binaryGcd(m, t, true);
  }

  // Returns gcd of abs(this) and abs(other).
  int gcd(int other) {
    if (other is! int) {
      throw new ArgumentError.value(other, "other", "not an integer");
    }
    int x = this.abs();
    int y = other.abs();
    if (x == 0) return y;
    if (y == 0) return x;
    if ((x == 1) || (y == 1)) return 1;
    if (other is _Bigint) {
      return _toBigint().gcd(other);
    }
    return _binaryGcd(x, y, false);
  }
}

class _Smi extends _IntegerImplementation implements int {
  factory _Smi._uninstantiable() {
    throw new UnsupportedError(
        "_Smi can only be allocated by the VM");
  }
  int get hashCode => this;
  int get _identityHashCode => this;
  int operator ~() native "Smi_bitNegate";
  int get bitLength native "Smi_bitLength";

  int operator &(int other) => other._bitAndFromSmi(this);

  int _bitAndFromSmi(int other) native "Smi_bitAndFromSmi";
  int _shrFromInt(int other) native "Smi_shrFromInt";
  int _shlFromInt(int other) native "Smi_shlFromInt";

  /**
   * The digits of '00', '01', ... '99' as a single array.
   *
   * Get the digits of `n`, with `0 <= n < 100`, as
   * `_digitTable[n * 2]` and `_digitTable[n * 2 + 1]`.
   */
  static const _digitTable = const [
    0x30, 0x30, 0x30, 0x31, 0x30, 0x32, 0x30, 0x33,
    0x30, 0x34, 0x30, 0x35, 0x30, 0x36, 0x30, 0x37,
    0x30, 0x38, 0x30, 0x39, 0x31, 0x30, 0x31, 0x31,
    0x31, 0x32, 0x31, 0x33, 0x31, 0x34, 0x31, 0x35,
    0x31, 0x36, 0x31, 0x37, 0x31, 0x38, 0x31, 0x39,
    0x32, 0x30, 0x32, 0x31, 0x32, 0x32, 0x32, 0x33,
    0x32, 0x34, 0x32, 0x35, 0x32, 0x36, 0x32, 0x37,
    0x32, 0x38, 0x32, 0x39, 0x33, 0x30, 0x33, 0x31,
    0x33, 0x32, 0x33, 0x33, 0x33, 0x34, 0x33, 0x35,
    0x33, 0x36, 0x33, 0x37, 0x33, 0x38, 0x33, 0x39,
    0x34, 0x30, 0x34, 0x31, 0x34, 0x32, 0x34, 0x33,
    0x34, 0x34, 0x34, 0x35, 0x34, 0x36, 0x34, 0x37,
    0x34, 0x38, 0x34, 0x39, 0x35, 0x30, 0x35, 0x31,
    0x35, 0x32, 0x35, 0x33, 0x35, 0x34, 0x35, 0x35,
    0x35, 0x36, 0x35, 0x37, 0x35, 0x38, 0x35, 0x39,
    0x36, 0x30, 0x36, 0x31, 0x36, 0x32, 0x36, 0x33,
    0x36, 0x34, 0x36, 0x35, 0x36, 0x36, 0x36, 0x37,
    0x36, 0x38, 0x36, 0x39, 0x37, 0x30, 0x37, 0x31,
    0x37, 0x32, 0x37, 0x33, 0x37, 0x34, 0x37, 0x35,
    0x37, 0x36, 0x37, 0x37, 0x37, 0x38, 0x37, 0x39,
    0x38, 0x30, 0x38, 0x31, 0x38, 0x32, 0x38, 0x33,
    0x38, 0x34, 0x38, 0x35, 0x38, 0x36, 0x38, 0x37,
    0x38, 0x38, 0x38, 0x39, 0x39, 0x30, 0x39, 0x31,
    0x39, 0x32, 0x39, 0x33, 0x39, 0x34, 0x39, 0x35,
    0x39, 0x36, 0x39, 0x37, 0x39, 0x38, 0x39, 0x39
  ];

  /**
   * Result of int.toString for -99, -98, ..., 98, 99.
   */
  static const _smallLookupTable = const [
    "-99", "-98", "-97", "-96", "-95", "-94", "-93", "-92", "-91", "-90",
    "-89", "-88", "-87", "-86", "-85", "-84", "-83", "-82", "-81", "-80",
    "-79", "-78", "-77", "-76", "-75", "-74", "-73", "-72", "-71", "-70",
    "-69", "-68", "-67", "-66", "-65", "-64", "-63", "-62", "-61", "-60",
    "-59", "-58", "-57", "-56", "-55", "-54", "-53", "-52", "-51", "-50",
    "-49", "-48", "-47", "-46", "-45", "-44", "-43", "-42", "-41", "-40",
    "-39", "-38", "-37", "-36", "-35", "-34", "-33", "-32", "-31", "-30",
    "-29", "-28", "-27", "-26", "-25", "-24", "-23", "-22", "-21", "-20",
    "-19", "-18", "-17", "-16", "-15", "-14", "-13", "-12", "-11", "-10",
    "-9", "-8", "-7", "-6", "-5", "-4", "-3", "-2", "-1", "0",
    "1", "2", "3", "4", "5", "6", "7", "8", "9", "10",
    "11", "12", "13", "14", "15", "16", "17", "18", "19", "20",
    "21", "22", "23", "24", "25", "26", "27", "28", "29", "30",
    "31", "32", "33", "34", "35", "36", "37", "38", "39", "40",
    "41", "42", "43", "44", "45", "46", "47", "48", "49", "50",
    "51", "52", "53", "54", "55", "56", "57", "58", "59", "60",
    "61", "62", "63", "64", "65", "66", "67", "68", "69", "70",
    "71", "72", "73", "74", "75", "76", "77", "78", "79", "80",
    "81", "82", "83", "84", "85", "86", "87", "88", "89", "90",
    "91", "92", "93", "94", "95", "96", "97", "98", "99"
  ];

  // Powers of 10 above 1000000 are indistinguishable by eye.
  static const int _POW_10_7  = 10000000;
  static const int _POW_10_8  = 100000000;
  static const int _POW_10_9  = 1000000000;

  // Find the number of decimal digits in a positive smi.
  // Never called with numbers < 100. These are handled before calling.
  static int _positiveBase10Length(var smi) {
    // A positive smi has length <= 19 if 63-bit,  <=10 if 31-bit.
    // Avoid comparing a 31-bit smi to a non-smi.
    if (smi < 1000) return 3;
    if (smi < 10000) return 4;
    if (smi < _POW_10_7) {
      if (smi < 100000) return 5;
      if (smi < 1000000) return 6;
      return 7;
    }
    if (smi < _POW_10_8) return 8;
    if (smi < _POW_10_9) return 9;
    smi = smi ~/ _POW_10_9;
    // Handle numbers < 100 before calling recursively.
    if (smi < 10) return 10;
    if (smi < 100) return 11;
    return 9 + _positiveBase10Length(smi);
  }

  String toString() {
    if (this < 100 && this > -100) return _smallLookupTable[this + 99];
    if (this < 0) return _negativeToString(this);
    // Inspired by Andrei Alexandrescu: "Three Optimization Tips for C++"
    // Avoid expensive remainder operation by doing it on more than
    // one digit at a time.
    const int DIGIT_ZERO = 0x30;
    int length = _positiveBase10Length(this);
    _OneByteString result = _OneByteString._allocate(length);
    int index = length - 1;
    var smi = this;
    do {
      // Two digits at a time.
      var twoDigits = smi.remainder(100);
      smi = smi ~/ 100;
      int digitIndex = twoDigits * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
      index -= 2;
    } while (smi >= 100);
    if (smi < 10) {
      // Character code for '0'.
      result._setAt(index, DIGIT_ZERO + smi);
    } else {
      // No remainder for this case.
      int digitIndex = smi * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
    }
    return result;
  }

  // Find the number of decimal digits in a negative smi.
  // Never called with numbers > -100. These are handled before calling.
  static int _negativeBase10Length(var negSmi) {
    // A negative smi has length <= 19 if 63-bit, <=10 if 31-bit.
    // Avoid comparing a 31-bit smi to a non-smi.
    if (negSmi > -1000) return 3;
    if (negSmi > -10000) return 4;
    if (negSmi > -_POW_10_7) {
      if (negSmi > -100000) return 5;
      if (negSmi > -1000000) return 6;
      return 7;
    }
    if (negSmi > -_POW_10_8) return 8;
    if (negSmi > -_POW_10_9) return 9;
    negSmi = negSmi ~/ _POW_10_9;
    // Handle numbers > -100 before calling recursively.
    if (negSmi > -10) return 10;
    if (negSmi > -100) return 11;
    return 9 + _negativeBase10Length(negSmi);
  }

  // Convert a negative smi to a string.
  // Doesn't negate the smi to avoid negating the most negative smi, which
  // would become a non-smi.
  static String _negativeToString(int negSmi) {
    // Character code for '-'
    const int MINUS_SIGN = 0x2d;
    // Character code for '0'.
    const int DIGIT_ZERO = 0x30;
    if (negSmi > -10) {
      return _OneByteString._allocate(2).._setAt(0, MINUS_SIGN)
                                        .._setAt(1, DIGIT_ZERO - negSmi);
    }
    if (negSmi > -100) {
      int digitIndex = 2 * -negSmi;
      return _OneByteString._allocate(3)
          .._setAt(0, MINUS_SIGN)
          .._setAt(1, _digitTable[digitIndex])
          .._setAt(2, _digitTable[digitIndex + 1]);
    }
    // Number of digits, not including minus.
    int digitCount = _negativeBase10Length(negSmi);
    _OneByteString result = _OneByteString._allocate(digitCount + 1);
    result._setAt(0, MINUS_SIGN);  // '-'.
    int index = digitCount;
    do {
      var twoDigits = negSmi.remainder(100);
      negSmi = negSmi ~/ 100;
      int digitIndex = -twoDigits * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
      index -= 2;
    } while (negSmi <= -100);
    if (negSmi > -10) {
      result._setAt(index, DIGIT_ZERO - negSmi);
    } else {
      // No remainder necessary for this case.
      int digitIndex = -negSmi * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
    }
    return result;
  }
}

// Represents integers that cannot be represented by Smi but fit into 64bits.
class _Mint extends _IntegerImplementation implements int {
  factory _Mint._uninstantiable() {
    throw new UnsupportedError(
        "_Mint can only be allocated by the VM");
  }
  int get hashCode => this;
  int get _identityHashCode => this;
  int operator ~() native "Mint_bitNegate";
  int get bitLength native "Mint_bitLength";

  int _bitAndFromSmi(int other) => _bitAndFromInteger(other);

  // Shift by mint exceeds range that can be handled by the VM.
  int _shrFromInt(int other) {
    if (other < 0) {
      return -1;
    } else {
      return 0;
    }
  }
  int _shlFromInt(int other) native "Mint_shlFromInt";
}