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);
        }
    }
}

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));
    }
}