Link shortener application - return the "following" string

Question

I'm working on developing an application to shorten links. Part of that requires me to be able to get the "next" string based on an allowed character ranges, as if we were counting up. Characters go from A-Z to a-z to 0-9. Some samples:

"A" => "B"
"AA" => "AB"
"AZ" => "Aa"
"Az" => "A0"
"A9" => "BA"
"999" => "AAAA"

I've written a small class to accomplish this. My main concerns are the way I've hard-coded the ranges, and I'm not sure if doing this recursively made the most sense.

package proceduralstring;

/**
 * Char succession: A-Z a-z 0-9
 * @author User
 *
 */
public class ProceduralStringCreator {

    public static String getFirst(){
        return "A";
    }

    public static String getFirst(int minLength){
        StringBuilder result = new StringBuilder();
        for(int i=0; i<minLength; i++){
            result.append("A");
        }
        return result.toString();
    }

    public static String getNext(String current) throws BadFormatException{
        if(!current.matches("[a-zA-Z0-9]+")){
            throw new BadFormatException("String contains illegal characters.");
        }
        if(current.matches("9{"+current.length()+"}")){
            return getFirst(current.length()+1);
        }
        StringBuilder result = new StringBuilder(current);
        replaceWithNext(result, result.length()-1);
        return result.toString();
    }

    private static StringBuilder replaceWithNext(StringBuilder toReplace, int index){
        char currentChar = toReplace.charAt(index);
        if(currentChar != '9'){ //base case
            if(currentChar != 'z' && currentChar != 'Z'){
                toReplace.replace(index, index+1, ((char)(currentChar+1))+"");
            }else{
                if(currentChar == 'z'){
                    toReplace.replace(index, index+1, "0");
                }else if(currentChar == 'Z'){
                    toReplace.replace(index, index+1, "a");
                }
            }
            return toReplace;
        }else{ //recursive case
            toReplace.replace(index, index+1, "A");
            return replaceWithNext(toReplace, index-1);
        }
    }
}

The code is tested and works as intended (the exception is the desired behavior, as there is an invalid character):

package proceduralstring;

public class ProcStringTest {

    public static void main(String[] args) throws BadFormatException {
        System.out.println("getFirst: "+ProceduralStringCreator.getFirst());
        System.out.println("getFirst(5): "+ProceduralStringCreator.getFirst(5));
        System.out.println("Next of A: "+ProceduralStringCreator.getNext("A"));
        System.out.println("Next of AA: "+ProceduralStringCreator.getNext("AA"));
        System.out.println("Next of AAA: "+ProceduralStringCreator.getNext("AAA"));
        System.out.println("Next of A9: "+ProceduralStringCreator.getNext("A9"));
        System.out.println("Next of Adhs3hdfh9: "+ProceduralStringCreator.getNext("Adhs3hdfh9"));
        System.out.println("Next of 9: "+ProceduralStringCreator.getNext("9"));
        System.out.println("Next of 99: "+ProceduralStringCreator.getNext("99"));
        System.out.println("Next of Aas9s99: "+ProceduralStringCreator.getNext("Aas9s99"));
        System.out.println("Next of 9z9999: "+ProceduralStringCreator.getNext("9z9999"));
        System.out.println("Next of 9Z9999: "+ProceduralStringCreator.getNext("9Z9999"));
        System.out.println("Next of AUHR(#H: "+ProceduralStringCreator.getNext("AUHR(#H"));
    }

}

Output:

getFirst: A
getFirst(5): AAAAA
Next of A: B
Next of AA: AB
Next of AAA: AAB
Next of A9: BA
Next of Adhs3hdfh9: Adhs3hdfiA
Next of 9: AA
Next of 99: AAA
Next of Aas9s99: Aas9tAA
Next of 9z9999: 90AAAA
Next of 9Z9999: 9aAAAA
Exception in thread "main" proceduralstring.BadFormatException: String contains illegal characters.
    at proceduralstring.ProceduralStringCreator.getNext(ProceduralStringCreator.java:24)
    at proceduralstring.ProcStringTest.main(ProcStringTest.java:18)
Picked up JAVA_TOOL_OPTIONS: -Duser.language=en

Answer 1

• Consider wrapping getFirst() into getNext(String) - just have it return "A" if it takes in a null or empty string. That might make it a little easier for the client to use.

• getFirst(int) can leverage Arrays.fill(), which will make it a little easier to read. Consider throwing an exception if the minLength is less than zero - otherwise you get an empty string returned. Another option would be to return "A".

• The core problem can be solved non-recursively. A helper method to return the next character would be, well, helpful, and easier to read than what you're doing now. The math gets done inside the loop, and you prepend an 'A' if appropriate.

• You might want to make 'A' a constant, since it's special.

If you make the changes I suggest, your code might look something like:

import java.util.Arrays;
import java.util.regex.Pattern;

public class ProceduralStringCreator {

    private static final Pattern VALID = Pattern.compile("[a-zA-Z0-9]+");
    private static final char FIRST_CHARACTER = 'A';

    public static String next(final int size) {
        if (size < 0) {
            throw new IllegalArgumentException("Size must be greater than or equal to zero, was " + size);
        }
        final char[] value = new char[size];
        Arrays.fill(value, FIRST_CHARACTER);
        return new String(value);
    }

    public static String next(final String current) throws BadFormatException {
        if (current == null || current.isEmpty()) {
            return Character.toString(FIRST_CHARACTER);
        }

        if (!VALID.matcher(current).matches()) {
            throw new BadFormatException("String contains illegal characters.");
        }

        final StringBuilder stringBuilder = new StringBuilder(current);
        int index = stringBuilder.length();

        do {
            index--;
            stringBuilder.setCharAt(index, nextCharacter(stringBuilder.charAt(index)));
        } while ((index >= 1) && (stringBuilder.charAt(index) == FIRST_CHARACTER));

        if ((index == 0) && (stringBuilder.charAt(index) == FIRST_CHARACTER)) {
            stringBuilder.insert(0, FIRST_CHARACTER);
        }

        return stringBuilder.toString();
    }

    private static char nextCharacter(final char character) {
        switch (character) {
        case 'Z':
            return 'a';
        case 'z':
            return '0';
        case '9':
            return 'A';
        default :
            return (char) (character + 1);
        }
    }

}

Answer 2

The test cases you give are very good. They cover all important normal cases and also the corner cases.

One bad thing is that you, as a human, have to inspect the test output to see whether the test still succeeds. You should rewrite your test to an automated unit test. For that, you need to add JUnit to your project, and I also recommend AssertJ. Using these tools, your test class might look like this:

package proceduralstring;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

import org.junit.jupiter.api.Test;

public class ProceduralStringCreatorTest {

    @Test
    void test() {
        assertThat(ProceduralStringCreator.getFirst()).isEqualTo("A");
        assertThat(ProceduralStringCreator.getFirst(5)).isEqualTo("AAAAA");

        assertThat(ProceduralStringCreator.getNext("A")).isEqualTo("B");
        assertThat(ProceduralStringCreator.getNext("AA")).isEqualTo("AB");
        assertThat(ProceduralStringCreator.getNext("AAA")).isEqualTo("AAB");
        assertThat(ProceduralStringCreator.getNext("A9")).isEqualTo("BA");
        assertThat(ProceduralStringCreator.getNext("Adhs3hdfh9")).isEqualTo("Adhs3hdfiA");
        assertThat(ProceduralStringCreator.getNext("9")).isEqualTo("AA");
        assertThat(ProceduralStringCreator.getNext("99")).isEqualTo("AAA");
        assertThat(ProceduralStringCreator.getNext("Aas9s99")).isEqualTo("Aas9tAA");
        assertThat(ProceduralStringCreator.getNext("9z9999")).isEqualTo("90AAAA");
        assertThat(ProceduralStringCreator.getNext("9Z9999")).isEqualTo("9aAAAA");

        assertThatThrownBy(() -> ProceduralStringCreator.getNext("AUHR(#H"))
                .isInstanceOf(BadFormatException.class)
                .hasMessage("String contains illegal characters.");
    }
}

You can see that the code is similar to your existing code.

I renamed the class to ProceduralStringCreatorTest so that it matches exactly the class that it is testing.

The nice thing about this test is that you get an empty output if everything succeeds. No manual inspection necessary. And if a test fails, you get a clear error message about the expected and the actual value.

---

Now to your main code. I don't like the name ProceduralStringCreator. First, I don't understand the word Procedural. I would remove that word. And instead of StringGenerator, I'd prefer ShortURLGenerator, since that's the only thing this class will be used for in your project.

The Javadoc comment above the public class is not friendly to the reader. It should describe in a full sentence what the class does. For example:

/**
 * Generates unique identifiers to be used in short URLs.
 */

The @author User is useless because it doesn't provide any information. You should either fill in your name or remove that line.

The first getFirst method looks good. I would put a space between the (){ at the end of the line, to follow the Java Coding Conventions, which describe how the source code should look.

In the second getFirst method, the parameter name is wrong. It should not be minLength but simply length since the generated string has always exactly this many characters.

In that method, you use the general pattern for building strings out of smaller parts, which is good. In this particular case, you can use alternative code that is even faster but not as general as your code:

public static String first(int length) {
    char[] digits = new char[length];
    Arrays.fill(digits, 'A');
    return new String(digits);
}

The getNext method is inefficient. Each time it is called it compiles the regular expression [a-zA-Z0-9]+, which is complicated and takes a lot of time. And then, you create a second regular expression for testing the 99999 case, which is also slow.

When you learned counting as a kid, you did not know about regular expressions, so there must be a computationally simpler way. And indeed, there is one. I'll show you at the end of my answer.

The replaceWithNext method is filled with the characters from your allowed alphabet. This makes the code complicated to read. The simple counting algorithm, as used for decimal numbers, is not as complicated. Again, you'll see at the end.

If you generalize your code for an arbitrary alphabet (maybe you want to leave out 0, O, 1, l, I because they look so similar), it can become much simpler. Here is what I ended up with:

package de.roland_illig;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Calculates the next "number" using an arbitrary alphabet.
 * <p>
 * Note: This counter is not suitable for decimal counting
 * since in decimal numbers, leading digits are not written down.
 */
public class Counter {

    /** All possible "digits" making up the "numbers", from small to large. */
    private final char[] alphabet;

    /**
     * Remembers the value for each "digit" from the alphabet,
     * to quickly find the next "digit". It would also be possible
     * to search where in the alphabet the digit appears, but that
     * would be slower, especially for large alphabets.
     */
    private final Map<Character, Integer> indexes = new HashMap<>();

    public Counter(String alphabet) {
        this.alphabet = alphabet.toCharArray();

        if (alphabet.isEmpty()) {
            throw new IllegalArgumentException("The alphabet must not be empty.");
        }

        for (int i = 0; i < alphabet.length(); i++) {
            char ch = alphabet.charAt(i);
            Integer prev = indexes.put(ch, i);
            if (prev != null) {
                String message = String.format(
                        "Duplicate character '%c' at indexes %d and %d.",
                        ch, prev, i);
                throw new IllegalArgumentException(message);
            }
        }
    }

    /** Returns the smallest "number" of the given length. */
    public String first(int length) {
        char[] digits = new char[length];
        Arrays.fill(digits, alphabet[0]);
        // For a true decimal counter, set digits[0] = alphabet[1] here.
        return new String(digits);
    }

    /** Returns the next "number" after the given number. */
    public String next(String number) {
        char[] digits = number.toCharArray();
        boolean carry = true;

        for (int i = digits.length - 1; i >= 0; i--) {
            char ch = digits[i];
            Integer chIndex = indexes.get(ch);

            if (chIndex == null) {
                String message = String.format(
                        "Invalid character '%c' at index %d.", ch, i);
                throw new IllegalArgumentException(message);
            }

            if (chIndex == alphabet.length - 1) {
                digits[i] = alphabet[0];
                // take the carry over to the next digit
            } else {
                digits[i] = alphabet[chIndex + 1];
                carry = false;
            }
        }

        if (carry) {
            return first(digits.length + 1);
        } else {
            return new String(digits);
        }
    }
}

And the corresponding test:

package de.roland_illig;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

import org.junit.jupiter.api.Test;

class CounterTest {

    private final Counter peano = new Counter("x");
    private final Counter digits = new Counter("0123456789");
    private final Counter alnum = new Counter(""
            + "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
            + "abcdefghijklmnopqrstuvwxyz"
            + "0123456789");

    @Test
    void first() {
        assertThat(peano.first(1)).isEqualTo("x");
        assertThat(peano.first(5)).isEqualTo("xxxxx");

        assertThat(digits.first(1)).isEqualTo("0");
        assertThat(digits.first(5)).isEqualTo("00000");
    }

    @Test
    void nextPeano() {
        assertThat(peano.next("")).isEqualTo("x");
        assertThat(peano.next("x")).isEqualTo("xx");
        assertThat(peano.next("xx")).isEqualTo("xxx");
        assertThat(peano.next("xxxxx")).isEqualTo("xxxxxx");
    }

    @Test
    void nextDigits() {
        assertThat(digits.next("")).isEqualTo("0");
        assertThat(digits.next("0")).isEqualTo("1");
        assertThat(digits.next("1")).isEqualTo("2");
        assertThat(digits.next("2")).isEqualTo("3");
        assertThat(digits.next("8")).isEqualTo("9");

        // Note: this is different from traditional decimal counting,
        // where leading zeros are not written out.
        assertThat(digits.next("9")).isEqualTo("00");
        assertThat(digits.next("99999")).isEqualTo("000000");
    }

    @Test
    void nextAlnum() {
        assertThat(alnum.next("")).isEqualTo("A");
        assertThat(alnum.next("A")).isEqualTo("B");
        assertThat(alnum.next("Z")).isEqualTo("a");
        assertThat(alnum.next("z")).isEqualTo("0");
        assertThat(alnum.next("9")).isEqualTo("AA");

        // This is different from traditional decimal counting,
        // where leading zeros are not written.
        assertThat(alnum.next("9")).isEqualTo("00");
        assertThat(alnum.next("99999")).isEqualTo("000000");
    }

    @Test
    void invalidCounter() {
        assertThatThrownBy(() -> new Counter(""))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("The alphabet must not be empty.");

        assertThatThrownBy(() -> new Counter("Duplicates are forbidden."))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("Duplicate character 'a' at indexes 6 and 11.");
    }

    @Test
    void invalidNext() {
        assertThatThrownBy(() -> digits.next("a"))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("Invalid character 'a' at index 0.");

        // Even if the counter would only have to look at the
        // rightmost zero to increment the complete number,
        // all characters are checked nevertheless.
        assertThatThrownBy(() -> digits.next("123a0000000000000000000"))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("Invalid character 'a' at index 3.");

        assertThatThrownBy(() -> digits.next("123a999"))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("Invalid character 'a' at index 3.");
    }
}

Answer 3

If you think of this as an addition problem:

To that end a constant string of all the accepted characters, to get the the character for a specific index, and a Map to get the index of a specific character, would help.

Since the result of adding 1, will never be more than 1 character longer than the length of the string, we can use a char[], to store the result. A simple loop and some math and a few lines later it's done. It could look something like this:

static final Map<Character, Integer> CHARS = Map.ofEntries(
        entry('A', 0),
        entry('B', 1),
        entry('C', 2),
        entry('D', 3),
        entry('E', 4),
        entry('F', 5),
        entry('G', 6),
        entry('H', 7),
        entry('I', 8),
        entry('J', 9),
        entry('K', 10),
        entry('L', 11),
        entry('M', 12),
        entry('N', 13),
        entry('O', 14),
        entry('P', 15),
        entry('Q', 16),
        entry('R', 17),
        entry('S', 18),
        entry('T', 19),
        entry('U', 20),
        entry('V', 21),
        entry('W', 22),
        entry('X', 23),
        entry('Y', 24),
        entry('Z', 25),
        entry('a', 26),
        entry('b', 27),
        entry('c', 28),
        entry('d', 29),
        entry('e', 30),
        entry('f', 31),
        entry('g', 32),
        entry('h', 33),
        entry('i', 34),
        entry('j', 35),
        entry('k', 36),
        entry('l', 37),
        entry('m', 38),
        entry('n', 39),
        entry('o', 40),
        entry('p', 41),
        entry('q', 42),
        entry('r', 43),
        entry('s', 44),
        entry('t', 45),
        entry('u', 46),
        entry('v', 47),
        entry('w', 48),
        entry('x', 49),
        entry('y', 50),
        entry('z', 51),
        entry('0', 52),
        entry('1', 53),
        entry('2', 54),
        entry('3', 55),
        entry('4', 56),
        entry('5', 57),
        entry('6', 58),
        entry('7', 59),
        entry('8', 60),
        entry('9', 61));
static final String KEYS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

public static String getNext(String value)throws BadFormatException{
    int increment = 1;
    int modulus = KEYS.length();
    int length = value.length();
    char[] result = new char[length + 1];
    result[length] = (char)(increment + '0');
    for (int i = length; i > 0; i--) {
        char nextChar = value.charAt(i - 1);
        if(!CHARS.containsKey(nextChar)){
            throw new BadFormatException("String contains illegal characters.");
        }                
        int temp = (CHARS.get(value.charAt(i - 1)) + (result[i] - '0'));
        result[i] = KEYS.charAt(temp % modulus);
        result[i - 1] = (char) ((temp / modulus) + '0');
    }
    if(result[0] == '0'){
        return new String(result, 1, result.length-1 );
    }
    result[0] = KEYS.charAt(0);
    return new String(result);
}