1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.Long; 13 14 import hunt.Byte; 15 import hunt.Integer; 16 import hunt.Nullable; 17 import hunt.Number; 18 import hunt.Exceptions; 19 import hunt.util.Comparator; 20 21 import std.algorithm.comparison; 22 import std.conv; 23 import std.exception; 24 25 /** 26 */ 27 class Long : AbstractNumber!long { 28 29 // Bit Twiddling 30 31 /** 32 * A constant holding the minimum value a {@code long} can 33 * have, -2<sup>63</sup>. 34 */ 35 static long MIN_VALUE = long.min; // 0x8000000000000000L; 36 37 /** 38 * A constant holding the maximum value a {@code long} can 39 * have, 2<sup>63</sup>-1. 40 */ 41 static long MAX_VALUE = long.max; // 0x7fffffffffffffffL; 42 43 /** 44 * The number of bits used to represent a {@code long} value in two's 45 * complement binary form. 46 * 47 * @since 1.5 48 */ 49 enum int SIZE = BYTES * Byte.SIZE; // 64; 50 51 /** 52 * The number of bytes used to represent a {@code long} value in two's 53 * complement binary form. 54 * 55 * @since 1.8 56 */ 57 enum BYTES = long.sizeof; // SIZE / 8; 58 59 /** 60 * Returns the signum function of the specified {@code long} value. (The 61 * return value is -1 if the specified value is negative; 0 if the 62 * specified value is zero; and 1 if the specified value is positive.) 63 * 64 * @param i the value whose signum is to be computed 65 * @return the signum function of the specified {@code long} value. 66 * @since 1.5 67 */ 68 static int signum(long i) { 69 // HD, Section 2-7 70 return cast(int) ((i >> 63) | (-i >>> 63)); 71 } 72 73 74 /** 75 * Returns the number of zero bits preceding the highest-order 76 * ("leftmost") one-bit in the two's complement binary representation 77 * of the specified {@code long} value. Returns 64 if the 78 * specified value has no one-bits in its two's complement representation, 79 * in other words if it is equal to zero. 80 * 81 * <p>Note that this method is closely related to the logarithm base 2. 82 * For all positive {@code long} values x: 83 * <ul> 84 * <li>floor(log<sub>2</sub>(x)) = {@code 63 - numberOfLeadingZeros(x)} 85 * <li>ceil(log<sub>2</sub>(x)) = {@code 64 - numberOfLeadingZeros(x - 1)} 86 * </ul> 87 * 88 * @param i the value whose number of leading zeros is to be computed 89 * @return the number of zero bits preceding the highest-order 90 * ("leftmost") one-bit in the two's complement binary representation 91 * of the specified {@code long} value, or 64 if the value 92 * is equal to zero. 93 * @since 1.5 94 */ 95 static int numberOfLeadingZeros(long i) { 96 // HD, Figure 5-6 97 if (i == 0) 98 return 64; 99 int n = 1; 100 int x = cast(int)(i >>> 32); 101 if (x == 0) { n += 32; x = cast(int)i; } 102 if (x >>> 16 == 0) { n += 16; x <<= 16; } 103 if (x >>> 24 == 0) { n += 8; x <<= 8; } 104 if (x >>> 28 == 0) { n += 4; x <<= 4; } 105 if (x >>> 30 == 0) { n += 2; x <<= 2; } 106 n -= x >>> 31; 107 return n; 108 } 109 110 /** 111 * The value of the {@code Long}. 112 * 113 * @serial 114 */ 115 // private long value; 116 117 /** 118 * Constructs a newly allocated {@code Long} object that 119 * represents the specified {@code long} argument. 120 * 121 * @param value the value to be represented by the 122 * {@code Long} object. 123 */ 124 this(long value) { 125 // this.value = value; 126 super(value); 127 } 128 129 /** 130 * Constructs a newly allocated {@code Long} object that 131 * represents the {@code long} value indicated by the 132 * {@code string} parameter. The string is converted to a 133 * {@code long} value in exactly the manner used by the 134 * {@code parseLong} method for radix 10. 135 * 136 * @param s the {@code string} to be converted to a 137 * {@code Long}. 138 * @throws NumberFormatException if the {@code string} does not 139 * contain a parsable {@code long}. 140 * @see java.lang.Long#parseLong(java.lang.string, int) 141 */ 142 this(string s) { 143 super(to!long(s)); 144 } 145 146 static long parseLong(string s, int radix=10) { 147 return to!long(s, radix); 148 } 149 150 /** 151 * Returns a {@code Long} instance representing the specified 152 * {@code long} value. 153 * If a new {@code Long} instance is not required, this method 154 * should generally be used in preference to the constructor 155 * {@link #Long(long)}, as this method is likely to yield 156 * significantly better space and time performance by caching 157 * frequently requested values. 158 * 159 * Note that unlike the {@linkplain Integer#valueOf(int) 160 * corresponding method} in the {@code Integer} class, this method 161 * is <em>not</em> required to cache values within a particular 162 * range. 163 * 164 * @param l a long value. 165 * @return a {@code Long} instance representing {@code l}. 166 * @since 1.5 167 */ 168 static Long valueOf(long l) { 169 int offset = 128; 170 if (l >= -128 && l <= 127) { // will cache 171 return LongCache.cache[cast(int)l + offset]; 172 } 173 return new Long(l); 174 } 175 176 177 178 /** 179 * Returns a {@code Long} object holding the value 180 * extracted from the specified {@code String} when parsed 181 * with the radix given by the second argument. The first 182 * argument is interpreted as representing a signed 183 * {@code long} in the radix specified by the second 184 * argument, exactly as if the arguments were given to the {@link 185 * #parseLong(java.lang.String, int)} method. The result is a 186 * {@code Long} object that represents the {@code long} 187 * value specified by the string. 188 * 189 * <p>In other words, this method returns a {@code Long} object equal 190 * to the value of: 191 * 192 * <blockquote> 193 * {@code new Long(Long.parseLong(s, radix))} 194 * </blockquote> 195 * 196 * @param s the string to be parsed 197 * @param radix the radix to be used in interpreting {@code s} 198 * @return a {@code Long} object holding the value 199 * represented by the string argument in the specified 200 * radix. 201 * @throws NumberFormatException If the {@code String} does not 202 * contain a parsable {@code long}. 203 */ 204 static Long valueOf(string s, int radix) { 205 return Long.valueOf(parseLong(s, radix)); 206 } 207 208 /** 209 * Returns a {@code Long} object holding the value 210 * of the specified {@code String}. The argument is 211 * interpreted as representing a signed decimal {@code long}, 212 * exactly as if the argument were given to the {@link 213 * #parseLong(java.lang.String)} method. The result is a 214 * {@code Long} object that represents the integer value 215 * specified by the string. 216 * 217 * <p>In other words, this method returns a {@code Long} object 218 * equal to the value of: 219 * 220 * <blockquote> 221 * {@code new Long(Long.parseLong(s))} 222 * </blockquote> 223 * 224 * @param s the string to be parsed. 225 * @return a {@code Long} object holding the value 226 * represented by the string argument. 227 * @throws NumberFormatException If the string cannot be parsed 228 * as a {@code long}. 229 */ 230 static Long valueOf(string s) { 231 return Long.valueOf(parseLong(s, 10)); 232 } 233 234 /** 235 * Returns a string representation of the first argument in the 236 * radix specified by the second argument. 237 * 238 * <p>If the radix is smaller than {@code Character.MIN_RADIX} 239 * or larger than {@code Character.MAX_RADIX}, then the radix 240 * {@code 10} is used instead. 241 * 242 * <p>If the first argument is negative, the first element of the 243 * result is the ASCII minus sign {@code '-'} 244 * ({@code '\u005Cu002d'}). If the first argument is not 245 * negative, no sign character appears in the result. 246 * 247 * <p>The remaining characters of the result represent the magnitude 248 * of the first argument. If the magnitude is zero, it is 249 * represented by a single zero character {@code '0'} 250 * ({@code '\u005Cu0030'}); otherwise, the first character of 251 * the representation of the magnitude will not be the zero 252 * character. The following ASCII characters are used as digits: 253 * 254 * <blockquote> 255 * {@code 0123456789abcdefghijklmnopqrstuvwxyz} 256 * </blockquote> 257 * 258 * These are {@code '\u005Cu0030'} through 259 * {@code '\u005Cu0039'} and {@code '\u005Cu0061'} through 260 * {@code '\u005Cu007a'}. If {@code radix} is 261 * <var>N</var>, then the first <var>N</var> of these characters 262 * are used as radix-<var>N</var> digits in the order shown. Thus, 263 * the digits for hexadecimal (radix 16) are 264 * {@code 0123456789abcdef}. If uppercase letters are 265 * desired, the {@link java.lang.string#toUpperCase()} method may 266 * be called on the result: 267 * 268 * <blockquote> 269 * {@code Long.toString(n, 16).toUpperCase()} 270 * </blockquote> 271 * 272 * @param i a {@code long} to be converted to a string. 273 * @param radix the radix to use in the string representation. 274 * @return a string representation of the argument in the specified radix. 275 * @see java.lang.Character#MAX_RADIX 276 * @see java.lang.Character#MIN_RADIX 277 */ 278 static string toStr(long i, int radix) { 279 if (radix < 2 || radix > 36) 280 radix = 10; 281 if (radix == 10) 282 return to!string(i); 283 char[] buf = new char[65]; 284 int charPos = 64; 285 bool negative = (i < 0); 286 287 if (!negative) { 288 i = -i; 289 } 290 291 while (i <= -radix) { 292 buf[charPos--] = Integer.digits[cast(int)(-(i % radix))]; 293 i = i / radix; 294 } 295 buf[charPos] = Integer.digits[cast(int)(-i)]; 296 297 if (negative) { 298 buf[--charPos] = '-'; 299 } 300 301 //return new string(buf, charPos, (65 - charPos)); 302 return to!string(buf[charPos..(65 - charPos)]); 303 } 304 305 306 /** 307 * Returns a string representation of the first argument as an 308 * unsigned integer value in the radix specified by the second 309 * argument. 310 * 311 * <p>If the radix is smaller than {@code Character.MIN_RADIX} 312 * or larger than {@code Character.MAX_RADIX}, then the radix 313 * {@code 10} is used instead. 314 * 315 * <p>Note that since the first argument is treated as an unsigned 316 * value, no leading sign character is printed. 317 * 318 * <p>If the magnitude is zero, it is represented by a single zero 319 * character {@code '0'} ({@code '\u005Cu0030'}); otherwise, 320 * the first character of the representation of the magnitude will 321 * not be the zero character. 322 * 323 * <p>The behavior of radixes and the characters used as digits 324 * are the same as {@link #toString(long, int) toString}. 325 * 326 * @param i an integer to be converted to an unsigned string. 327 * @param radix the radix to use in the string representation. 328 * @return an unsigned string representation of the argument in the specified radix. 329 * @see #toString(long, int) 330 * @since 1.8 331 */ 332 static string toUnsignedString(long i, int radix) { 333 if (i >= 0) 334 return toStr(i, radix); 335 else { 336 switch (radix) { 337 case 2: 338 return toBinaryString(i); 339 340 case 4: 341 return toUnsignedString0(i, 2); 342 343 case 8: 344 return toOctalString(i); 345 346 case 10: 347 /* 348 * We can get the effect of an unsigned division by 10 349 * on a long value by first shifting right, yielding a 350 * positive value, and then dividing by 5. This 351 * allows the last digit and preceding digits to be 352 * isolated more quickly than by an initial conversion 353 * to BigInteger. 354 */ 355 long quot = (i >>> 1) / 5; 356 long rem = i - quot * 10; 357 return to!string(quot) ~ to!string(rem); 358 359 case 16: 360 return toHexString(i); 361 362 case 32: 363 return toUnsignedString0(i, 5); 364 365 default: 366 return ""/* toUnsignedBigInteger(i).toString(radix) */; 367 } 368 } 369 } 370 371 /** 372 * Return a BigInteger equal to the unsigned value of the 373 * argument. 374 */ 375 // private static BigInteger toUnsignedBigInteger(long i) { 376 // if (i >= 0L) 377 // return BigInteger.valueOf(i); 378 // else { 379 // int upper = (int) (i >>> 32); 380 // int lower = (int) i; 381 382 // // return (upper << 32) + lower 383 // return (BigInteger.valueOf(Integer.toUnsignedLong(upper))).shiftLeft(32). 384 // add(BigInteger.valueOf(Integer.toUnsignedLong(lower))); 385 // } 386 // } 387 388 /** 389 * Returns a string representation of the {@code long} 390 * argument as an unsigned integer in base 16. 391 * 392 * <p>The unsigned {@code long} value is the argument plus 393 * 2<sup>64</sup> if the argument is negative; otherwise, it is 394 * equal to the argument. This value is converted to a string of 395 * ASCII digits in hexadecimal (base 16) with no extra 396 * leading {@code 0}s. 397 * 398 * <p>The value of the argument can be recovered from the returned 399 * string {@code s} by calling {@link 400 * Long#parseUnsignedLong(string, int) Long.parseUnsignedLong(s, 401 * 16)}. 402 * 403 * <p>If the unsigned magnitude is zero, it is represented by a 404 * single zero character {@code '0'} ({@code '\u005Cu0030'}); 405 * otherwise, the first character of the representation of the 406 * unsigned magnitude will not be the zero character. The 407 * following characters are used as hexadecimal digits: 408 * 409 * <blockquote> 410 * {@code 0123456789abcdef} 411 * </blockquote> 412 * 413 * These are the characters {@code '\u005Cu0030'} through 414 * {@code '\u005Cu0039'} and {@code '\u005Cu0061'} through 415 * {@code '\u005Cu0066'}. If uppercase letters are desired, 416 * the {@link java.lang.string#toUpperCase()} method may be called 417 * on the result: 418 * 419 * <blockquote> 420 * {@code Long.toHexString(n).toUpperCase()} 421 * </blockquote> 422 * 423 * @param i a {@code long} to be converted to a string. 424 * @return the string representation of the unsigned {@code long} 425 * value represented by the argument in hexadecimal 426 * (base 16). 427 * @see #parseUnsignedLong(string, int) 428 * @see #toUnsignedString(long, int) 429 * @since JDK 1.0.2 430 */ 431 static string toHexString(long i) { 432 return toUnsignedString0(i, 4); 433 } 434 435 /** 436 * Returns a string representation of the {@code long} 437 * argument as an unsigned integer in base 8. 438 * 439 * <p>The unsigned {@code long} value is the argument plus 440 * 2<sup>64</sup> if the argument is negative; otherwise, it is 441 * equal to the argument. This value is converted to a string of 442 * ASCII digits in octal (base 8) with no extra leading 443 * {@code 0}s. 444 * 445 * <p>The value of the argument can be recovered from the returned 446 * string {@code s} by calling {@link 447 * Long#parseUnsignedLong(string, int) Long.parseUnsignedLong(s, 448 * 8)}. 449 * 450 * <p>If the unsigned magnitude is zero, it is represented by a 451 * single zero character {@code '0'} ({@code '\u005Cu0030'}); 452 * otherwise, the first character of the representation of the 453 * unsigned magnitude will not be the zero character. The 454 * following characters are used as octal digits: 455 * 456 * <blockquote> 457 * {@code 01234567} 458 * </blockquote> 459 * 460 * These are the characters {@code '\u005Cu0030'} through 461 * {@code '\u005Cu0037'}. 462 * 463 * @param i a {@code long} to be converted to a string. 464 * @return the string representation of the unsigned {@code long} 465 * value represented by the argument in octal (base 8). 466 * @see #parseUnsignedLong(string, int) 467 * @see #toUnsignedString(long, int) 468 * @since JDK 1.0.2 469 */ 470 static string toOctalString(long i) { 471 return toUnsignedString0(i, 3); 472 } 473 474 /** 475 * Returns a string representation of the {@code long} 476 * argument as an unsigned integer in base 2. 477 * 478 * <p>The unsigned {@code long} value is the argument plus 479 * 2<sup>64</sup> if the argument is negative; otherwise, it is 480 * equal to the argument. This value is converted to a string of 481 * ASCII digits in binary (base 2) with no extra leading 482 * {@code 0}s. 483 * 484 * <p>The value of the argument can be recovered from the returned 485 * string {@code s} by calling {@link 486 * Long#parseUnsignedLong(string, int) Long.parseUnsignedLong(s, 487 * 2)}. 488 * 489 * <p>If the unsigned magnitude is zero, it is represented by a 490 * single zero character {@code '0'} ({@code '\u005Cu0030'}); 491 * otherwise, the first character of the representation of the 492 * unsigned magnitude will not be the zero character. The 493 * characters {@code '0'} ({@code '\u005Cu0030'}) and {@code 494 * '1'} ({@code '\u005Cu0031'}) are used as binary digits. 495 * 496 * @param i a {@code long} to be converted to a string. 497 * @return the string representation of the unsigned {@code long} 498 * value represented by the argument in binary (base 2). 499 * @see #parseUnsignedLong(string, int) 500 * @see #toUnsignedString(long, int) 501 * @since JDK 1.0.2 502 */ 503 static string toBinaryString(long i) { 504 return toUnsignedString0(i, 1); 505 } 506 507 /** 508 * Format a long (treated as unsigned) into a string. 509 * @param val the value to format 510 * @param shift the log2 of the base to format in (4 for hex, 3 for octal, 1 for binary) 511 */ 512 static string toUnsignedString0(long val, int shift) { 513 // assert shift > 0 && shift <=5 : "Illegal shift value"; 514 int mag = Long.SIZE - Long.numberOfLeadingZeros(val); 515 int chars = max(((mag + (shift - 1)) / shift), 1); 516 char[] buf = new char[chars]; 517 518 formatUnsignedLong(val, shift, buf, 0, chars); 519 return to!string(buf); 520 } 521 522 /** 523 * Format a long (treated as unsigned) into a character buffer. 524 * @param val the unsigned long to format 525 * @param shift the log2 of the base to format in (4 for hex, 3 for octal, 1 for binary) 526 * @param buf the character buffer to write to 527 * @param offset the offset in the destination buffer to start at 528 * @param len the number of characters to write 529 * @return the lowest character location used 530 */ 531 static int formatUnsignedLong(long val, int shift, char[] buf, int offset, int len) { 532 int charPos = len; 533 int radix = 1 << shift; 534 int mask = radix - 1; 535 do { 536 buf[offset + --charPos] = Integer.digits[(cast(int) val) & mask]; 537 val >>>= shift; 538 } while (val != 0 && charPos > 0); 539 540 return charPos; 541 } 542 543 /** 544 * Returns the number of zero bits following the lowest-order ("rightmost") 545 * one-bit in the two's complement binary representation of the specified 546 * {@code long} value. Returns 64 if the specified value has no 547 * one-bits in its two's complement representation, in other words if it is 548 * equal to zero. 549 * 550 * @param i the value whose number of trailing zeros is to be computed 551 * @return the number of zero bits following the lowest-order ("rightmost") 552 * one-bit in the two's complement binary representation of the 553 * specified {@code long} value, or 64 if the value is equal 554 * to zero. 555 * @since 1.5 556 */ 557 static int numberOfTrailingZeros(long i) { 558 // HD, Figure 5-14 559 int x, y; 560 if (i == 0) return 64; 561 int n = 63; 562 y = cast(int)i; if (y != 0) { n = n -32; x = y; } else x = cast(int)(i>>>32); 563 y = x <<16; if (y != 0) { n = n -16; x = y; } 564 y = x << 8; if (y != 0) { n = n - 8; x = y; } 565 y = x << 4; if (y != 0) { n = n - 4; x = y; } 566 y = x << 2; if (y != 0) { n = n - 2; x = y; } 567 return n - ((x << 1) >>> 31); 568 } 569 570 571 /** 572 * Returns the number of one-bits in the two's complement binary 573 * representation of the specified {@code long} value. This function is 574 * sometimes referred to as the <i>population count</i>. 575 * 576 * @param i the value whose bits are to be counted 577 * @return the number of one-bits in the two's complement binary 578 * representation of the specified {@code long} value. 579 * @since 1.5 580 */ 581 static int bitCount(long i) { 582 // HD, Figure 5-14 583 i = i - ((i >>> 1) & 0x5555555555555555L); 584 i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L); 585 i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL; 586 i = i + (i >>> 8); 587 i = i + (i >>> 16); 588 i = i + (i >>> 32); 589 return cast(int)i & 0x7f; 590 } 591 592 override int opCmp(Object o) { 593 if(o is null) throw new NullPointerException(); 594 Number n = cast(Number)o; 595 if(n is null) throw new Exception("Number needed."); 596 return compare(this.value, n.longValue()); 597 } 598 599 int opCmp(long n) { 600 return compare(this.value, n); 601 } 602 603 /** 604 * Returns a hash code for a {@code long} value; compatible with 605 * {@code Long.hashCode()}. 606 * 607 * @param value the value to hash 608 * @return a hash code value for a {@code long} value. 609 * @since 1.8 610 */ 611 override size_t toHash() @safe nothrow { 612 return cast(int)(value ^ (value >>> 32)); 613 } 614 } 615 616 617 private class LongCache { 618 private this(){} 619 620 __gshared Long[] cache; 621 622 shared static this(){ 623 cache = new Long[-(-128) + 127 + 1]; 624 for(int i = 0; i < cache.length; i++) 625 cache[i] = new Long(i - 128); 626 } 627 }