Converting long values in Java to unsigned strings

Question

This one is a research attempt to find out how to convert long values as unsigned long integers to Strings. It is much slower than java.lang.Long.toUnsignedString, but it was fun to code:

net.coderodde.util.Long

package net.coderodde.util;

import java.util.Random;

/**
 * This class contains a method for converting {@code long} values to unsigned 
 * strings.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (May 16, 2019)
 */
public final class Long {

    /**
     * Caching a string builder in order to save some computation.
     */
    private static final StringBuilder STRING_BUILDER = 
            new StringBuilder(java.lang.Long.SIZE);

    /**
     * Maps individual radices and bits to the numbers they represent in the 
     * given radix.
     */
    private static final Digit[][] bitIndexToDigitChainMaps = new Digit[37][];

    /**
     * Maps a given internal representation of a digit character to its visual
     * glyph.
     */
    private static char[] digitsToCharsMap;

    /**
     * This static inner class represents a single decimal digit.
     */
    static final class Digit {

        /**
         * The actual decimal digit.
         */
        int value;

        /**
         * The higher-order decimal digit.
         */
        Digit next;

        Digit(int digit) {
            this.value = digit;
        }
    }

    static {
        initializeBitDigitLists();
        initalizeDigitsToCharMap();
    }

    private static final void initializeBitDigitLists() {
        for (int radix = 2; radix != 37; radix++) {
            bitIndexToDigitChainMaps[radix] = new Digit[java.lang.Long.SIZE];

            for (int bitIndex = 0; bitIndex < 63; bitIndex++) {
                long value = 1L << bitIndex;
                bitIndexToDigitChainMaps[radix][bitIndex] =
                        getDigitList(value, radix);
            }

            bitIndexToDigitChainMaps[radix][java.lang.Long.SIZE - 1] = 
                    getLastDigitList(radix);
        }
    }

    private static final void initalizeDigitsToCharMap() {
        digitsToCharsMap = new char[] {
            '0' , '1' , '2' , '3' , '4' , '5' ,
            '6' , '7' , '8' , '9' , 'a' , 'b' ,
            'c' , 'd' , 'e' , 'f' , 'g' , 'h' ,
            'i' , 'j' , 'k' , 'l' , 'm' , 'n' ,
            'o' , 'p' , 'q' , 'r' , 's' , 't' ,
            'u' , 'v' , 'w' , 'x' , 'y' , 'z'
        };
    }

    /**
     * Converts the given {@code long} value as unsigned to a 
     * {@link java.lang.String} using the input radix.
     * 
     * @param value the value to convert.
     * @param radix the requested radix.
     * @return the string representation of the input value as unsigned.
     */
    public static String toUnsignedString(long value, int radix) {
        checkRadix(radix);
        final Digit leastSignificantDigit = new Digit(0);

        for (int bitIndex = 0; bitIndex != java.lang.Long.SIZE; bitIndex++) {
            if ((value & (1L << bitIndex)) != 0) {
                digitsPlus(bitIndexToDigitChainMaps[radix][bitIndex],
                           leastSignificantDigit,
                           radix);
            }
        }

        return inferString(leastSignificantDigit);
    }

    public static String toUnsignedBinaryString(long value) {
        return toUnsignedString(value, 2);
    }

    public static String toUnsignedOctalString(long value) {
        return toUnsignedString(value, 8);
    }

    public static String toUnsignedString(long value) {
        return toUnsignedString(value, 10);
    }

    public static String toUnsignedHexString(long value) {
        return toUnsignedString(value, 16);
    }

    public static final class ThreadSafe {

        /**
         * Converts the given {@code long} value as unsigned to a 
         * {@link java.lang.String}. Unlike 
         * {@link net.coderodde.util.Long#toUnsignedString(long)}, this version
         * is thread-safe.
         * 
         * @param value the value to convert.
         * @return the string representation of the input value as unsigned.
         */
        public static String toUnsignedString(long value, int radix) {
            final Digit leastSignificantDigit = new Digit(0);

            for (int bitIndex = 0; bitIndex != java.lang.Long.SIZE; bitIndex++) {
                if ((value & (1L << bitIndex)) != 0) {
                    digitsPlus(bitIndexToDigitChainMaps[radix][bitIndex],
                               leastSignificantDigit,
                               radix);
                }
            }

            return inferStringThreadSafe(leastSignificantDigit);
        }

        public static String toUnsignedBinaryString(long value) {
            return toUnsignedString(value, 2);
        }

        public static String toUnsignedOctalString(long value) {
            return toUnsignedString(value, 8);
        }

        public static String toUnsignedString(long value) {
            return toUnsignedString(value, 10);
        }

        public static String toUnsignedHexString(long value) {
            return toUnsignedString(value, 16);
        }
    }

    /**
     * Infers the {@code long} string from the digit-wise representation.
     * 
     * @param leastSignificantDigit the least-significant digit of the value.
     * @return the string representing the digit-wise number.
     */
    private static final String inferString(Digit leastSignificantDigit) {
        STRING_BUILDER.setLength(0);
        return inferString(leastSignificantDigit, STRING_BUILDER);
    }

    /**
     * Infers the {@code long} string from the digit-wise representation. Unlike
     * {@link net.coderodde.util.Long#inferString(net.coderodde.util.Long.Digit)},
     * this implementation is thread-safe.
     * 
     * @param leastSignificantDigit the least-significant digit of the number to
     *                              infer.
     * @return the string representation of the given number.
     */
    private static final String inferStringThreadSafe(
            Digit leastSignificantDigit) {
        return inferString(leastSignificantDigit, 
                           new StringBuilder(java.lang.Long.SIZE));
    }

    /**
     * Infers the resulting string from the input digit list.
     * 
     * @param leastSignificantDigit the digit list.
     * @param stringBuilder         the string builder.
     * @return the resulting string.
     */
    private static final String inferString(Digit leastSignificantDigit, 
                                            StringBuilder stringBuilder) {
        for (Digit digit = leastSignificantDigit; 
                digit != null; 
                digit = digit.next) {
            stringBuilder.append(digitsToCharsMap[digit.value]);
        }

        return stringBuilder.reverse().toString();
    }

    /**
     * Performs the addition operation upon two input digit lists. 
     * 
     * @param sourceDigits the digits to add.
     * @param targetDigits the digits to which to add.
     */
    static final void digitsPlus(Digit sourceDigits,
                                 Digit targetDigits,
                                 int radix) {
        Digit sourceDigit = sourceDigits;
        Digit targetDigit = targetDigits;
        Digit targetNumberHead = targetDigit;
        boolean carryFlag = false;

        //! Try to remove sourceDigit != null
        while (sourceDigit != null && targetDigit != null) {
            int digitValue = sourceDigit.value + targetDigit.value + 
                            (carryFlag ? 1 : 0);

            if (digitValue >= radix) {
                digitValue -= radix;
                carryFlag = true;
            } else {
                carryFlag = false;
            }

            targetNumberHead = targetDigit;
            targetDigit.value = digitValue;
            sourceDigit = sourceDigit.next;
            targetDigit = targetDigit.next;
        }

        // Deal with the leftovers:
        while (sourceDigit != null) {
            int value = sourceDigit.value + (carryFlag ? 1 : 0);

            if (value >= radix) {
                value -= radix;
                carryFlag = true;
            } else {
                carryFlag = false;
            }

            targetNumberHead.next = new Digit(value);
            targetNumberHead = targetNumberHead.next;
            sourceDigit = sourceDigit.next;
        }

        if (carryFlag) {
            targetNumberHead.next = new Digit(1);
        }
    }

    /**
     * Computes the digit list representing {@code value}.
     * 
     * @param value the target value.
     * @return the digit list representing the input value.
     */
    private static final Digit getDigitList(long value, int radix) {
        Digit previousDigit = null;
        Digit leastSignificantDigit = null;

        while (value != 0L) {
            int digit = (int)(value % radix);

            if (previousDigit == null) {
                previousDigit = new Digit(digit);
                leastSignificantDigit = previousDigit;
            } else {
                Digit tmp = new Digit(digit);
                previousDigit.next = tmp;
                previousDigit = tmp;
            }

            // Drop the last digit of 'value':
            value /= radix;
        }

        return leastSignificantDigit;
    }

    /**
     * Copies the digit list starting from {@code leastSignificantDigit}.
     * 
     * @param leastSignificantDigit the least-significant digit of the digit
     *                              list to be copied.
     * @return the copy of the input digit list.
     */
    static final Digit copyDigitList(Digit leastSignificantDigit) {
        Digit currentSourceDigit = leastSignificantDigit;
        Digit returnDigit = new Digit(leastSignificantDigit.value);
        Digit headTargetDigit = returnDigit;
        currentSourceDigit = currentSourceDigit.next;

        while (currentSourceDigit != null) {
            Digit targetDigit = new Digit(currentSourceDigit.value);
            headTargetDigit.next = targetDigit;
            headTargetDigit = targetDigit;
            currentSourceDigit = currentSourceDigit.next;
        }

        return returnDigit;
    }

    /**
     * Returns the decimal number corresponding to {@code 2^64 - 1}.
     * 
     * @return the decimal number corresponding to {@code 2^64 - 1}.
     */
    private static final Digit getLastDigitList(int radix) { 
        Digit source = bitIndexToDigitChainMaps[radix][62];
        Digit target = copyDigitList(source);
        digitsPlus(source, target, radix);
        return target;
    }

    private static final int BENCHMARK_ITERATIONS = 100_000;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        Random random1 = new Random(seed);
        Random random2 = new Random(seed);
        System.out.println("main(): seed = " + seed);
        run(BENCHMARK_ITERATIONS, random1, random2, false); // Warm up.
        run(BENCHMARK_ITERATIONS, random1, random2, true);  // Benchmark.
    }

    private static final void run(int numberOfValuesToGenerate,
                                  Random random1,
                                  Random random2,
                                  boolean printElapsedTime) {
        long startTime = System.currentTimeMillis();

        for (int iteration = 0; 
                iteration < numberOfValuesToGenerate;
                iteration++) {
            long value = random1.nextLong();
            net.coderodde.util.Long.toUnsignedString(value);
        }

        long endTime = System.currentTimeMillis();

        if (printElapsedTime) {
            System.out.print("net.coderodde.util.Long.toString() in ");
            System.out.print(endTime - startTime);
            System.out.println(" milliseconds.");
        }

        startTime = System.currentTimeMillis();

        for (int iteration = 0; 
                iteration < numberOfValuesToGenerate;
                iteration++) {
            long value = random2.nextLong();
            java.lang.Long.toUnsignedString(value);
        }

        endTime = System.currentTimeMillis();

        if (printElapsedTime) {
            System.out.print("java.lang.Long.toString() in ");
            System.out.print(endTime - startTime);
            System.out.println(" milliseconds.");
        }
    }

    private static final void checkRadix(int radix) {
        if (radix < 2 || radix > digitsToCharsMap.length) {
            throw new IllegalArgumentException("Bad radix: " + radix);
        }
    }
}

net.coderodde.util.LongTest

package net.coderodde.util;

import java.util.Random;
import net.coderodde.util.Long.Digit;
import static net.coderodde.util.Long.digitsPlus;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * This unit test class tests the {@link net.coderodde.util.Long}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 14, 2019)
 */
public class LongTest {

    /**
     * The number of brute force iteration when comparing the {@code toString}
     * static methods.
     */
    private static final int BRUTE_FORCE_ITERATIONS = 1_000;

    @Test
    public void testDigitsPlusOnEqualLengthSourceTargetNumbers() {
        // Number 123:
        Digit source3 = new Digit(1);
        Digit source2 = new Digit(2);
        Digit source1 = new Digit(3);

        source1.next = source2;
        source2.next = source3;

        // Number 456:
        Digit target3 = new Digit(4);
        Digit target2 = new Digit(5);
        Digit target1 = new Digit(6);

        target1.next = target2;
        target2.next = target3;

        // Number 579:
        digitsPlus(source1, target1, 10);

        assertEquals(9, target1.value);
        assertEquals(7, target2.value);
        assertEquals(5, target3.value);
    }

    @Test
    public void testDigitsPlusOnLongerTargetNumber() {
        Digit source = new Digit(7);
        Digit target = new Digit(8);
        digitsPlus(source, target, 10);

        assertEquals(5, target.value);
        assertEquals(1, target.next.value);
    }

    @Test
    public void testDigitsPlusWhenSourceIsLonger() {
        // source = 591
        Digit source1 = new Digit(1);
        Digit source2 = new Digit(9);
        Digit source3 = new Digit(5);

        source1.next = source2;
        source2.next = source3;

        // target = 79
        Digit target1 = new Digit(9);
        Digit target2 = new Digit(7);

        target1.next = target2;
        // 591 + 79
        digitsPlus(source1, target1, 10);

        // 591 + 79 = 670
        assertEquals(6, target1.next.next.value);
        assertEquals(7, target1.next.value);
        assertEquals(0, target1.value);
    }

    @Test
    public void testDigitsPlusWhenSourceNumberContainsLongCarryChain() {
        // 99500
        Digit source1 = new Digit(0);
        Digit source2 = new Digit(0);
        Digit source3 = new Digit(5);
        Digit source4 = new Digit(9);
        Digit source5 = new Digit(9);

        source1.next = source2;
        source2.next = source3;
        source3.next = source4;
        source4.next = source5;

        // 601
        Digit target1 = new Digit(1);
        Digit target2 = new Digit(0);
        Digit target3 = new Digit(6);

        target1.next = target2;
        target2.next = target3;

        // 100101
        digitsPlus(source1, target1, 10);

        assertEquals(1, target1.value);
        assertEquals(0, target1.next.value);
        assertEquals(1, target1.next.next.value);
        assertEquals(0, target1.next.next.next.value);
        assertEquals(0, target1.next.next.next.next.value);
        assertEquals(1, target1.next.next.next.next.next.value);
    }

    @Test
    public void testLongToStringWithBruteForce() {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        System.out.println("testLongToStringWithBruteForce, seed = " + seed);

        for (int i = 0; i < BRUTE_FORCE_ITERATIONS; i++) {
            long value = random.nextLong();
            int radix = 2 + random.nextInt(35);
            String expected = java.lang.Long.toUnsignedString(value, radix);
            String actual   = net.coderodde.util.Long.toUnsignedString(value,
                                                                       radix);
            assertEquals(expected, actual);
        }
    }

    @Test
    public void testWhenValueIsNegative() {
        String expected = java.lang.Long.toUnsignedString(-1000);
        String actual   = net.coderodde.util.Long.toUnsignedString(-1000);
        assertEquals(expected, actual);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testThrowsWhenTooSmallRadix() {
        net.coderodde.util.Long.toUnsignedString(1, 1);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testThrowsWhenTooLargeRadix() {
        net.coderodde.util.Long.toUnsignedString(1, 37);
    }

    @Test
    public void testWhenLargestRadix() {
        assertEquals(java.lang.Long.toUnsignedString(1000L, 36),
                     net.coderodde.util.Long.toUnsignedString(1000L, 36));
    }
}

So, how am I doing here? Are the unit tests in order? Is my code readable/maintainable?

Answer 1

Since you're asking about readability, let's take a look at that.

Your functions and variables could be named better. Especially parts like this:

static final void digitsPlus(Digit sourceDigits,
                             Digit targetDigits,
                             int radix) {
    Digit sourceDigit = sourceDigits;
    Digit targetDigit = targetDigits;

How many Digit are passed to the function? 2? 2 lists of Digit? And why does it read like you're putting multiple Digit in a single Digit? I know, because I read the rest of the code. But from how this function is written, I'd have questions.

But your tests are worse:

@Test
public void testDigitsPlusWhenSourceIsLonger() {
    // source = 591
    Digit source1 = new Digit(1);
    Digit source2 = new Digit(9);
    Digit source3 = new Digit(5);

    source1.next = source2;
    source2.next = source3;

    // target = 79
    Digit target1 = new Digit(9);
    Digit target2 = new Digit(7);

    target1.next = target2;
    // 591 + 79
    digitsPlus(source1, target1, 10);

    // 591 + 79 = 670
    assertEquals(6, target1.next.next.value);
    assertEquals(7, target1.next.value);
    assertEquals(0, target1.value);
}

Why are there numbers in your variable names? Not just once, but all over the place. The moment you start putting numbers in your variable names, often you're either naming them wrong or using the wrong type of variable.

testDigitsPlusWhenSourceIsLonger() Longer than what? Probably the target number, but this function is ran on data already in storage. It takes no arguments. So your tests aren't reusable.