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