blob: d46885c8e0de2987a2fcf2d7cd3cd9791aa6c1f2 [file] [log] [blame]
// 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.
part of dart.core;
/**
* An arbitrarily large integer.
*
* **Note:** When compiling to JavaScript, integers are
* implemented as JavaScript numbers. When compiling to JavaScript,
* integers are therefore restricted to 53 significant bits because
* all JavaScript numbers are double-precision floating point
* values. The behavior of the operators and methods in the [int]
* class therefore sometimes differs between the Dart VM and Dart code
* compiled to JavaScript.
*
* It is a compile-time error for a class to attempt to extend or implement int.
*/
abstract class int extends num {
/**
* Returns the integer value of the given environment declaration [name].
*
* The result is the same as would be returned by:
*
* int.parse(const String.fromEnvironment(name, defaultValue: ""),
* (_) => defaultValue)
*
* Example:
*
* const int.fromEnvironment("defaultPort", defaultValue: 80)
*/
const factory int.fromEnvironment(String name, {int defaultValue})
native "Integer_fromEnvironment";
/**
* Bit-wise and operator.
*
* Treating both `this` and [other] as sufficiently large two's component
* integers, the result is a number with only the bits set that are set in
* both `this` and [other]
*
* Of both operands are negative, the result is negative, otherwise
* the result is non-negative.
*/
int operator &(int other);
int compareTo(int other);
/**
* Bit-wise or operator.
*
* Treating both `this` and [other] as sufficiently large two's component
* integers, the result is a number with the bits set that are set in either
* of `this` and [other]
*
* If both operands are non-negative, the result is non-negative,
* otherwise the result us negative.
*/
int operator |(int other);
/**
* Bit-wise exclusive-or operator.
*
* Treating both `this` and [other] as sufficiently large two's component
* integers, the result is a number with the bits set that are set in one,
* but not both, of `this` and [other]
*
* If the operands have the same sign, the result is non-negative,
* otherwise the result is negative.
*/
int operator ^(int other);
/**
* The bit-wise negate operator.
*
* Treating `this` as a sufficiently large two's component integer,
* the result is a number with the opposite bits set.
*
* This maps any integer `x` to `-x - 1`.
*/
int operator ~();
/**
* Shift the bits of this integer to the left by [shiftAmount].
*
* Shifting to the left makes the number larger, effectively multiplying
* the number by `pow(2, shiftIndex)`.
*
* There is no limit on the size of the result. It may be relevant to
* limit intermediate values by using the "and" operator with a suitable
* mask.
*
* It is an error if [shiftAmount] is negative.
*/
int operator <<(int shiftAmount);
/**
* Shift the bits of this integer to the right by [shiftAmount].
*
* Shifting to the right makes the number smaller and drops the least
* significant bits, effectively doing an integer division by
*`pow(2, shiftIndex)`.
*
* It is an error if [shiftAmount] is negative.
*/
int operator >>(int shiftAmount);
/**
* Returns this integer to the power of [exponent] modulo [modulus].
*
* The [exponent] must be non-negative and [modulus] must be
* positive.
*/
int modPow(int exponent, int modulus);
/**
* Returns the modular multiplicative inverse of this integer
* modulo [modulus].
*
* The [modulus] must be positive.
*
* It is an error if no modular inverse exists.
*/
int modInverse(int modulus);
/**
* Returns the greatest common divisor of this integer and [other].
*
* If either number is non-zero, the result is the numerically greatest
* integer dividing both `this` and `other`.
*
* The greatest common divisor is independent of the order,
* so `x.gcd(y)` is always the same as `y.gcd(x)`.
*
* For any integer `x`, `x.gcd(x)` is `x.abs()`.
*
* If both `this` and `other` is zero, the result is also zero.
*/
int gcd(int other);
/** Returns true if and only if this integer is even. */
bool get isEven;
/** Returns true if and only if this integer is odd. */
bool get isOdd;
/**
* Returns the minimum number of bits required to store this integer.
*
* The number of bits excludes the sign bit, which gives the natural length
* for non-negative (unsigned) values. Negative values are complemented to
* return the bit position of the first bit that differs from the sign bit.
*
* To find the number of bits needed to store the value as a signed value,
* add one, i.e. use `x.bitLength + 1`.
*
* x.bitLength == (-x-1).bitLength
*
* 3.bitLength == 2; // 00000011
* 2.bitLength == 2; // 00000010
* 1.bitLength == 1; // 00000001
* 0.bitLength == 0; // 00000000
* (-1).bitLength == 0; // 11111111
* (-2).bitLength == 1; // 11111110
* (-3).bitLength == 2; // 11111101
* (-4).bitLength == 2; // 11111100
*/
int get bitLength;
/**
* Returns the least significant [width] bits of this integer as a
* non-negative number (i.e. unsigned representation). The returned value has
* zeros in all bit positions higher than [width].
*
* (-1).toUnsigned(5) == 31 // 11111111 -> 00011111
*
* This operation can be used to simulate arithmetic from low level languages.
* For example, to increment an 8 bit quantity:
*
* q = (q + 1).toUnsigned(8);
*
* `q` will count from `0` up to `255` and then wrap around to `0`.
*
* If the input fits in [width] bits without truncation, the result is the
* same as the input. The minimum width needed to avoid truncation of `x` is
* given by `x.bitLength`, i.e.
*
* x == x.toUnsigned(x.bitLength);
*/
int toUnsigned(int width);
/**
* Returns the least significant [width] bits of this integer, extending the
* highest retained bit to the sign. This is the same as truncating the value
* to fit in [width] bits using an signed 2-s complement representation. The
* returned value has the same bit value in all positions higher than [width].
*
* V--sign bit-V
* 16.toSigned(5) == -16 // 00010000 -> 11110000
* 239.toSigned(5) == 15 // 11101111 -> 00001111
* ^ ^
*
* This operation can be used to simulate arithmetic from low level languages.
* For example, to increment an 8 bit signed quantity:
*
* q = (q + 1).toSigned(8);
*
* `q` will count from `0` up to `127`, wrap to `-128` and count back up to
* `127`.
*
* If the input value fits in [width] bits without truncation, the result is
* the same as the input. The minimum width needed to avoid truncation of `x`
* is `x.bitLength + 1`, i.e.
*
* x == x.toSigned(x.bitLength + 1);
*/
int toSigned(int width);
/**
* Return the negative value of this integer.
*
* The result of negating an integer always has the opposite sign, except
* for zero, which is its own negation.
*/
int operator -();
/**
* Returns the absolute value of this integer.
*
* For any integer `x`, the result is the same as `x < 0 ? -x : x`.
*/
int abs();
/**
* Returns the sign of this integer.
*
* Returns 0 for zero, -1 for values less than zero and
* +1 for values greater than zero.
*/
int get sign;
/** Returns `this`. */
int round();
/** Returns `this`. */
int floor();
/** Returns `this`. */
int ceil();
/** Returns `this`. */
int truncate();
/** Returns `this.toDouble()`. */
double roundToDouble();
/** Returns `this.toDouble()`. */
double floorToDouble();
/** Returns `this.toDouble()`. */
double ceilToDouble();
/** Returns `this.toDouble()`. */
double truncateToDouble();
/**
* Returns a String-representation of this integer.
*
* The returned string is parsable by [parse].
* For any `int` [:i:], it is guaranteed that
* [:i == int.parse(i.toString()):].
*/
String toString();
/**
* Converts [this] to a string representation in the given [radix].
*
* In the string representation, lower-case letters are used for digits above
* '9', with 'a' being 10 an 'z' being 35.
*
* The [radix] argument must be an integer in the range 2 to 36.
*/
String toRadixString(int radix);
/**
* Parse [source] as a, possibly signed, integer literal and return its value.
*
* The [source] must be a non-empty sequence of base-[radix] digits,
* optionally prefixed with a minus or plus sign ('-' or '+').
*
* The [radix] must be in the range 2..36. The digits used are
* first the decimal digits 0..9, and then the letters 'a'..'z' with
* values 10 through 35. Also accepts upper-case letters with the same
* values as the lower-case ones.
*
* If no [radix] is given then it defaults to 10. In this case, the [source]
* digits may also start with `0x`, in which case the number is interpreted
* as a hexadecimal literal, which effectively means that the `0x` is ignored
* and the radix is instead set to 16.
*
* For any int [:n:] and radix [:r:], it is guaranteed that
* [:n == int.parse(n.toRadixString(r), radix: r):].
*
* If the [source] is not a valid integer literal, optionally prefixed by a
* sign, the [onError] is called with the [source] as argument, and its return
* value is used instead. If no [onError] is provided, a [FormatException]
* is thrown.
*
* The [onError] handler can be chosen to return `null`. This is preferable
* to to throwing and then immediately catching the [FormatException].
* Example:
*
* var value = int.parse(text, onError: (source) => null);
* if (value == null) ... handle the problem
*
* The [onError] function is only invoked if [source] is a [String]. It is
* not invoked if the [source] is, for example, `null`.
*/
static int parse(String source, {int radix: -1, int onError(String source)}) {
if (source == null) throw new ArgumentError("The source must not be null");
if (source.isEmpty) return _throwFormatException(onError, source, 0, radix);
if (radix == -1 || radix == 10) {
try {
// Try parsing immediately, without trimming whitespace.
return _tryParseSmi(source, 0, source.length - 1);
} catch (e) {
}
} else if (radix < 2 || radix > 36) {
throw new RangeError("Radix $radix not in range 2..36");
}
// Split here so improve odds of parse being inlined and the checks omitted.
return _parse(source, radix, onError);
}
static int _tryParseSmi(String str, int first, int last) {
assert(first <= last);
var ix = first;
var sign = 1;
var c = str.codeUnitAt(ix);
// Check for leading '+' or '-'.
if ((c == 0x2b) || (c == 0x2d)) {
ix++;
sign = 0x2c - c; // -1 for '-', +1 for '+'.
if (ix > last) {
throw "Error"; // Empty.
}
}
var smiLimit = internal.is64Bit ? 18 : 9;
if ((last - ix) >= smiLimit) {
throw "Error"; // May not fit into a Smi.
}
var result = 0;
for (int i = ix; i <= last; i++) {
var c = 0x30 ^ str.codeUnitAt(i);
if (9 < c) {
throw "Error";
// return null;
}
result = 10 * result + c;
}
return sign * result;
}
static int _parse(String source, int radix, int onError(String source)) {
int end = (source as _StringBase)._lastNonWhitespace() + 1;
if (end == 0) {
return _throwFormatException(onError, source, source.length, radix);
}
int start = (source as _StringBase)._firstNonWhitespace();
int first = source.codeUnitAt(start);
int sign = 1;
if (first == 0x2b /* + */ || first == 0x2d /* - */) {
sign = 0x2c - first; // -1 if '-', +1 if '+'.
start++;
if (start == end) {
return _throwFormatException(onError, source, end, radix);
}
first = source.codeUnitAt(start);
}
if (radix == -1) {
// check for 0x prefix.
int index = start;
if (first == 0x30 /* 0 */) {
index++;
if (index == end) return 0;
first = source.codeUnitAt(index);
if ((first | 0x20) == 0x78 /* x */) {
index++;
if (index == end) {
return _throwFormatException(onError, source, index, -1);
}
try {
return _parseRadix(source, 16, index, end, sign);
} catch (_) {
return _throwFormatException(onError, source, -1, -1);
}
}
}
radix = 10;
}
try {
return _parseRadix(source, radix, start, end, sign);
} catch (_) {
return _throwFormatException(onError, source, -1, radix);
}
}
static int _throwFormatException(int onError(String source), String source, int index, int radix) {
if (onError != null) return onError(source);
if (radix == -1) {
throw new FormatException("Invalid number", source, index);
}
throw new FormatException("Invalid radix-$radix number", source, index);
}
static int _parseRadix(
String source, int radix, int start, int end, int sign) {
int tableIndex = (radix - 2) * 4 + (internal.is64Bit ? 2 : 0);
int blockSize = _PARSE_LIMITS[tableIndex];
int length = end - start;
if (length <= blockSize) {
int smi = _parseBlock(source, radix, start, end);
return sign * smi;
}
// Often cheaper than: int smallBlockSize = length % blockSize;
// because digit count generally tends towards smaller. rather
// than larger.
int smallBlockSize = length;
while (smallBlockSize >= blockSize) smallBlockSize -= blockSize;
int result = 0;
if (smallBlockSize > 0) {
int blockEnd = start + smallBlockSize;
int smi = _parseBlock(source, radix, start, blockEnd);
result = sign * smi;
start = blockEnd;
}
int multiplier = _PARSE_LIMITS[tableIndex + 1];
int blockEnd = start + blockSize;
do {
int smi = _parseBlock(source, radix, start, blockEnd);
result = (result * multiplier) + (sign * smi);
start = blockEnd;
blockEnd = start + blockSize;
} while (blockEnd <= end);
return result;
}
static int _parseBlock(String source, int radix, int start, int end) {
int result = 0;
if (radix <= 10) {
for (int i = start; i < end; i++) {
int digit = source.codeUnitAt(i) ^ 0x30;
if (digit >= radix) throw "Error";
result = radix * result + digit;
}
} else {
for (int i = start; i < end; i++) {
int char = source.codeUnitAt(i);
int digit = char ^ 0x30;
if (digit > 9) {
digit = (char | 0x20) - (0x61 - 10);
if (digit < 10 || digit >= radix) throw "Error";
}
result = radix * result + digit;
}
}
return result;
}
static const _PARSE_LIMITS = const [
30, 1073741824, 62, 4611686018427387904, // radix: 2
18, 387420489, 39, 4052555153018976267,
15, 1073741824, 30, 1152921504606846976,
12, 244140625, 26, 1490116119384765625, // radix: 5
11, 362797056, 23, 789730223053602816,
10, 282475249, 22, 3909821048582988049,
10, 1073741824, 20, 1152921504606846976,
9, 387420489, 19, 1350851717672992089,
9, 1000000000, 18, 1000000000000000000, // radix: 10
8, 214358881, 17, 505447028499293771,
8, 429981696, 17, 2218611106740436992,
8, 815730721, 16, 665416609183179841,
7, 105413504, 16, 2177953337809371136,
7, 170859375, 15, 437893890380859375, // radix: 15
7, 268435456, 15, 1152921504606846976,
7, 410338673, 15, 2862423051509815793,
7, 612220032, 14, 374813367582081024,
7, 893871739, 14, 799006685782884121,
6, 64000000, 14, 1638400000000000000, // radix: 20
6, 85766121, 14, 3243919932521508681,
6, 113379904, 13, 282810057883082752,
6, 148035889, 13, 504036361936467383,
6, 191102976, 13, 876488338465357824,
6, 244140625, 13, 1490116119384765625, // radix: 25
6, 308915776, 13, 2481152873203736576,
6, 387420489, 13, 4052555153018976267,
6, 481890304, 12, 232218265089212416,
6, 594823321, 12, 353814783205469041,
6, 729000000, 12, 531441000000000000, // radix: 30
6, 887503681, 12, 787662783788549761,
6, 1073741824, 12, 1152921504606846976,
5, 39135393, 12, 1667889514952984961,
5, 45435424, 12, 2386420683693101056,
5, 52521875, 12, 3379220508056640625, // radix: 35
5, 60466176, 11, 131621703842267136,
];
}