2
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ @Dannnno If you look at the input, you should see that the exception is expected. It's saying that ( is an illegal character. It only accepts the duosexigesimal digits. This is a weird method of testing, but it is working as intended. \$\endgroup\$ – mdfst13 Jul 13 '18 at 2:41
  • 1
    \$\begingroup\$ @Dannnno it's part of a link shortening thing! And yeah the exception is expected \$\endgroup\$ – Nicolás Marzano Jul 13 '18 at 12:08
  • \$\begingroup\$ I've edited the question a bit to clarify the intent and use-case here; please make sure I didn't make any mistakes there \$\endgroup\$ – Dannnno Jul 13 '18 at 13:28
  • \$\begingroup\$ The changes make sense to me, thanks! I'm not entirely sure about the caesar cipher tag? I guess there's the "substitute a character by the next one" part but I'm not seeing actual parallels beyond that... \$\endgroup\$ – Nicolás Marzano Jul 13 '18 at 17:41
1
\$\begingroup\$
  • 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);
        }
    }

}
\$\endgroup\$
  • \$\begingroup\$ Well that's silly, I had started with 'A' as a final char constant but ended up taking it out when I realized I was just hardcoding every other "special" char. I assume the first method's name is supposed to be "first" or similar? And I see, that's a way of solving the core of the "next string" problem I hadn't realized.. I had started with a 'for' loop and when I realized I was going through the whole string with no reason to because I had a "base case", my brain immediately went to recursion. This gives me insight into better use of regex pattern matching too, thanks! \$\endgroup\$ – Nicolás Marzano Jul 13 '18 at 16:39
  • \$\begingroup\$ Reviewing the code though, I get the feeling that the difference in behaviour between calling next(5) and next("Aad34s"), down to the way of calling them, should make for two different functions... \$\endgroup\$ – Nicolás Marzano Jul 13 '18 at 18:08
1
\$\begingroup\$

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.");
    }
}
\$\endgroup\$
0
\$\begingroup\$

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);
}
\$\endgroup\$

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.