4
\$\begingroup\$

This is a follow up to my previous question, Base-changing numbers in Java

I have followed @Pimgd's advice in the answer to that question, and I'm posting the improved code for any further review.

Note:

I didn't bother with whitespace in the test method, because I don't use it anyway. It also isn't up for review, it's just there to help people to run the program quick and dirty.

Here's the code:

/**
 * Converts a number in digit representation from one base to another
 * Not guaranteed to work with bases above 65,451 (more characters than which the lookup can use for substituting digits)
 *
 * @author Tamoghna Chowdhury
 * @version 1.2
 */
public class BaseConverter {
    protected static final String negativeBaseErrorMessage = "Negative or zero base values are illegal - supplied bases were %d & %d.", 
    invalidInputNumberErrorMessage = "The supplied number (%s) for base conversion is invalid.", 
    tooLargeBaseForLookupErrorMessage = "Not enough available characters for substitution. Number of available characters is %d , minimum required number is %d";

    private static String lookup = "0123456789ABCDEFGHIJKLMNOPQRSTWXYZabcdefghijklmnopqrstwxyz+/=,?!;:\"'^`~|\\@#$%&*_<>(){}";

    private static void updateLookup(int base) {
        int charsToAdd = base - lookup.length();
        if (charsToAdd > 0) {
            for (int i = 0; i < Character.MAX_VALUE && charsToAdd > 0; ++i) {
                if ((!lookup.contains("" + (char) i)) &&
                        (!Character.isISOControl((char) i)) &&
                        (!Character.isWhitespace((char) i)) &&
                        ((char) i != '.') && (char) i != '-') {
                    lookup += (char) i;
                    --charsToAdd;
                }
            }
        }
        if (charsToAdd > 0) {
            throw new IllegalArgumentException(String.format(tooLargeBaseForLookupErrorMessage, lookup.length(), base));
        }
    }
    public static long convertToNumber(String inputNumber, int from_base) {
        if (from_base >= lookup.length()) {
            updateLookup(from_base);
        }
        long number = 0;
        int length = inputNumber.length();
        for (int i = 0; i < length; ++i) {
            long digitValue = lookup.indexOf(inputNumber.charAt(i));
            if (digitValue < 0) {//this digit does not exist in the lookup, so the input is incorrect
                throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
            }
            number += digitValue * Math.round(Math.pow(from_base, length - 1 - i));
        }
        return number;
    }
    private static int countDigits(long number, int to_base) {
        int num_digits = 0;
        while (number > 0) {
            number /= to_base;
            ++num_digits;
        }
        return num_digits;
    }
    private static int[] createDigits(long number, int to_base) {
        int[] digits = new int[countDigits(number, to_base)];
        int num_digits = 0;
        while (number > 0) {
            digits[num_digits++] = (int) (number % to_base);
            number /= to_base;
        }
        return digits;
    }
    public static String changeBase(String inputNumber, int from_base, int to_base) {
        return changeBase(inputNumber, from_base, to_base, true);
    }
    private static boolean isInvalidInputNumber(String inputNumber, int from_base) {
        //there should be no more than 1 - sign, which should have been removed already if it exists
        return inputNumber.contains("-") ||
                //there should be no more than 1 fixed point, which should have been removed already if it exists
                inputNumber.contains(".") ||
                //there should be no characters in the string which indicate values for a digit greater than the current base
                (!inputNumber.matches(String.format("^[%s]*$", lookup.substring(0, from_base))));
    }
    public static String changeBase(String inputNumber, int from_base, int to_base, boolean substituteNumerics) {
        boolean isNegative = false;
        if (inputNumber.startsWith("-")) {
            //the provided number is (supposedly) negative
            inputNumber = inputNumber.substring(1, inputNumber.length());
            isNegative = true;
        }
        if (from_base <= 0 || to_base <= 0) {
            //negative or zero bases can't be handled using simple integer arithmetic
            throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
        }
        updateLookup(Math.max(from_base, to_base));
        if (inputNumber.contains(".")) {
            return changeBase(inputNumber.substring(0, inputNumber.indexOf(".")), from_base, to_base, substituteNumerics)/*Integer part*/ + "." +
                    changeBase(inputNumber.substring(inputNumber.indexOf(".") + 1, inputNumber.length()), from_base, to_base, substituteNumerics)/*Fractional part*/;
        }
        //checking for invalid numbers is easier now when negatives and fixed points should have been taken care of
        if (isInvalidInputNumber(inputNumber, from_base)) {
            throw new IllegalArgumentException(String.format(invalidInputNumberErrorMessage, inputNumber));
        }
        //special handling for 0 to avoid undefined behaviour and other bugs
        if (inputNumber.matches("^[0]+$")) {//check for any number of only 0s in the input
            return (isNegative) ? "-" + lookup.charAt(0) : lookup.charAt(0) + "";//I could simply return "0", but this looks less hardcoded
        }
        String new_number = "";
        int[] digits = createDigits(convertToNumber(inputNumber, from_base), to_base);
        if (substituteNumerics) {
            //use character representation for digits
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += lookup.charAt(digits[i]);
            }
        } else {
            //use numeric representations for digits, separate using space
            for (int i = digits.length - 1; i >= 0; --i) {
                new_number += digits[i] + " ";
            }
        }
        return (isNegative) ? "-" + new_number.trim() : new_number.trim();
    }
}   

A test class with a main method:

public class BaseConverterTest
{
    public static void main(String[] args){
        if (args.length == 3) {
            System.out.println(
            BaseConverter.changeBase(args[0],
            Integer.parseInt(args[1]),
            Integer.parseInt(args[2])));
        } else if (args.length == 4) {
            System.out.println(
            BaseConverter.changeBase(args[0],
            Integer.parseInt(args[1]),
            Integer.parseInt(args[2]),
            Boolean.parseBoolean(args[3])));
        }else{
            throw new IllegalArgumentException("Invalid Command Line Arguments");
        }
    }
}

Ensure both files are in the same folder!

\$\endgroup\$
3
\$\begingroup\$
private static void updateLookup(int base) {
    int charsToAdd = base - lookup.length();
    if (charsToAdd > 0) {
        for (int i = 0; i < Character.MAX_VALUE && charsToAdd > 0; ++i) {
            if ((!lookup.contains("" + (char) i)) &&
                    (!Character.isISOControl((char) i)) &&
                    (!Character.isWhitespace((char) i)) &&
                    ((char) i != '.') && (char) i != '-') {
                lookup += (char) i;
                --charsToAdd;
            }
        }
    }
    if (charsToAdd > 0) {
        throw new IllegalArgumentException(String.format(tooLargeBaseForLookupErrorMessage, lookup.length(), base));
    }
}

So thing is, this method is still too slow for really huge bases. On one hand, you could say "such a huge base is overkill". On the other hand, denial of service attacks are a thing, and servers are better at recovering from crashes than infinite loops.

But the thing is, you don't add other characters to lookup, nor do you ever clear lookup.

So you don't need to start from 0 whenever you enter the loop. You can start from where you left off!

So keep track of a lastUsedCharacterIndex of sorts (might need a better name).

Second, if we assume that the character set doesn't contain duplicates, then any newly added character cannot be encountered via incrementing i. So the only thing you need to test against is the value of lookup before you entered the loop.

Once we make these changes, you'd think the issue is fixed, but no! String concatenation in a loop KILLS performance, and any lint tool of quality will give you a warning for += to a string in a loop. So you will have to use something like StringBuilder. By using a StringBuilder we also stored the old value in lookup, so there's no need for a seperate variable (like I suggested earlier).

Once we do that...

private static StringBuilder builder = new StringBuilder(lookup);

private static void updateLookup(int base) {
    int charsToAdd = base - lookup.length();
    if (charsToAdd > 0) {
        for (int i = 0; i < Character.MAX_VALUE && charsToAdd > 0; ++i) {
            if ((!lookup.contains("" + (char) i)) &&
                    (!Character.isISOControl((char) i)) &&
                    (!Character.isWhitespace((char) i)) &&
                    ((char) i != '.') && (char) i != '-') {
                builder.append((char) i);
                --charsToAdd;
            }
        }
    }
    lookup = builder.toString();
    if (charsToAdd > 0) {
        throw new IllegalArgumentException(String.format(tooLargeBaseForLookupErrorMessage, lookup.length(), base));
    }
}

By just applying StringBuilder, what used to take 5 seconds (and then broke, on ideone, after hitting 40000 characters), now runs in 0.14 seconds.

Another performance improvement would be to add && charsToAdd < (Character.MAX_VALUE - lookup.length()) - check if it's going to fit BEFORE you fill up the lookup table.


    if (from_base <= 0 || to_base <= 0) {
        //negative or zero bases can't be handled using simple integer arithmetic
        throw new IllegalArgumentException(String.format(negativeBaseErrorMessage, from_base, to_base));
    }

This guard clause should placed before the isNegative check because it doesn't rely on the negative check.

\$\endgroup\$
  • \$\begingroup\$ Oh yeah, I should have done that too. Thanks. \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 16:43
  • \$\begingroup\$ Well, calls to this class are meant to be independent, so... That oldLookup stuff may not actually be useful in my possible use case. Thanks anyway. \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 16:45
  • \$\begingroup\$ @TamoghnaChowdhury the calls are independent; oldLookup is to prevent you from checking all the values you've added. Basically it assumes you won't hit the same characters twice, so there's no need to check a character you've already passed. \$\endgroup\$ – Pimgd Mar 17 '16 at 16:46
  • \$\begingroup\$ By independent calls I meant separate JVM invocations. There should be only one call to this method per JVM invocation in my program, but I'll keep your suggestion just in case it gets used somewhere else or by someone else. \$\endgroup\$ – Tamoghna Chowdhury Mar 17 '16 at 16:49
  • \$\begingroup\$ @TamoghnaChowdhury oldLookup is useless, you're right \$\endgroup\$ – Pimgd Mar 17 '16 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.