12
\$\begingroup\$

I want to implement a method which, given some camelcased or underscored String, will return a list of separate words that make up this String. Examples:

  • ISomeCamelCasedString -> {I, Some, Camel, Cased, String}
  • UNDERSCORED_STRING -> {UNDERSCORED, STRING}
  • camelCased_and_UNDERSCORED -> {camel, Cased, and, UNDERSCORED}

My approach to solve this is as follows: I add a space character between each two words that should be separated and then divide them into a list using StringTokenizer.

public static List<String> split(String string) {
    StringBuilder separatedWords = new StringBuilder();

    for (int i=0; i<string.length(); i++) {
        char c = string.charAt(i);

        if (i > 0) {    
            char previousC = string.charAt(i-1);

            if ((!Character.isLowerCase(c) && !Character.isUpperCase(previousC)) //  UpperCamelCase, UPPER_DASHED
                    || !Character.isLetterOrDigit(previousC)                    // lower_dashed
                    || (i < string.length() - 1) && Character.isLowerCase(string.charAt(i+1))  && Character.isUpperCase(c)  ) // IAttribute
            {       
                separatedWords.append(" ");
            }
        }       
        if (Character.isLetterOrDigit(c)) {
            separatedWords.append(c);
        }
    }

    List<String> tokens = new ArrayList<String>();

    StringTokenizer tokenizer = new StringTokenizer(separatedWords.toString());

    while(tokenizer.hasMoreTokens()) {
        tokens.add(tokenizer.nextToken());
    }
    return tokens;
}

As you can see, it looks quite complicated. How can I improve this?

\$\endgroup\$
4
  • 4
    \$\begingroup\$ The first thing I would point out is to read the StringTokenizer JavaDoc - StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. Don't use it. \$\endgroup\$ Sep 10 '14 at 9:03
  • \$\begingroup\$ Consider using CaseFormat, if you need transformation rather than splitting. \$\endgroup\$
    – maaartinus
    Sep 10 '14 at 11:16
  • 1
    \$\begingroup\$ What would you consider the correct result for abc123_456xyz? Your code gives [abc, 1, 2, 3, 4, 5, 6xyz], just want to confirm that's what is intended. Same question for ISTHISLEGALPascalCase. \$\endgroup\$
    – mjolka
    Sep 10 '14 at 12:30
  • \$\begingroup\$ @mjolka It doesn't matter how numbers are handled. As for second example, it should return {ISTHISLEGAL, Pascal, Case} \$\endgroup\$
    – Kao
    Sep 10 '14 at 12:44
7
\$\begingroup\$

My first impression:

  • The implementation looks long and complicated for something that sounds simple
  • You've provided some example cases to verify correctness, which is a very good thing

My first reaction is to embody the example test cases in proper unit tests, and then replace the implementation with a different approach, and make the tests I broke work again.

The unit tests, straightforward from your examples:

@Test
public void testCamelCased() {
    assertEquals(Arrays.asList("I", "Some", "Camel", "Cased", "String"), split("ISomeCamelCasedString"));
}

@Test
public void testSnakeCased() {
    assertEquals(Arrays.asList("UNDERSCORED", "STRING"), split("UNDERSCORED_STRING"));
}

@Test
public void testMixed() {
    assertEquals(Arrays.asList("camel", "Cased", "and", "UNDERSCORED"), split("camelCased_and_UNDERSCORED"));
}

Next, I was thinking that this can be simplified by splitting on some clever regex. I'm no regex wiz, but there are a lot of those on Stack Overflow, and I found a suitable thread about splitting camelCase to its words, here. Adapting it to also split on underscores was relatively easy, though probably not perfect, resulting in this:

private static final String RE_CAMELCASE_OR_UNDERSCORE =
        "(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])|_";

public static List<String> split(String string) {
    List<String> words = new ArrayList<String>();
    for (String word : string.split(RE_CAMELCASE_OR_UNDERSCORE)) {
        if (!word.isEmpty()) {
            words.add(word);
        }
    }
    return words;
}

This is probably not perfect, but a lot shorter than the original, and easier to understand how it works. If somebody can figure out how to get RE_CAMELCASE_OR_UNDERSCORE so that it doesn't produce empty elements, then the method can be shortened to simply:

return Arrays.asList(string.split(RE_CAMELCASE_OR_UNDERSCORE));

PS: this_is_usually_called_snake_cased, not "underscored".

\$\endgroup\$
2
  • \$\begingroup\$ Empty elements from list can be deleted this way: words.removeAll(Collections.singleton("")); \$\endgroup\$
    – Kao
    Sep 10 '14 at 13:55
  • \$\begingroup\$ That's a nice idea, in a way, but I would incur another iteration to do this, compared to the current solution which makes only one pass on the String array returned by the split. \$\endgroup\$
    – janos
    Sep 10 '14 at 14:22
5
\$\begingroup\$

This has presented an interesting problem. Your solution concerns me, because it does not solve things the way I would. This, in itself, is not a problem, but I had to look through your code, and figure out why you were doing things. Your solution has a couple of unexpected, and useful side effects.

  • Your method is defined to split a word in to the tokens that are CamelCase or Underscore separated, but it actually splits on any other punctuation, including space (anything that is not Character.isLetterOrDigit(..), so your solution gets 'hello' and 'world' from '!hello! .... world !!!'

  • Your solution also splits some complex CamelCase examples well, like thisIsHTMLInCamelCase, which surprised me.

So, I set out to suggest why your solution was a problem, but then found that it worked better than I thought.

This intrigued me, so I set about understanding your solution, and, bottom line, you do text-break-processing on punctuation and before-consecutive capitals....

Essentially, you split the word with spaces between all sequences of characters, and then you also add a space before the capital of a Xx combination, and before the capital of a xX combination (or both).

The process you are using, though, is really ugly. Regular expressions are a better tool for the job. They may be hard to understand, occasionally, but they 'compile' down to what are called Deterministic Finite Automaton.

So, your code does a lot more than the description, since it can deal with space and punctuation separated words (i.e. sentences), but it does it in a way that is slow, and requires intermediate results (a space separated string), which is then post-processed to words.

I took this system, and implemented it as regular expressions as an exercise myself:

First, I compiled two patterns, one to split the content in to words, the other to split the words in CamelCase, etc.

private static final Pattern PUNCTSPACE = Pattern.compile("[ \\p{Punct}]+");
private static final Pattern TRANSITION = Pattern.compile("(?<=[^\\p{Lu}])(?=[\\p{Lu}])|(?=[\\p{Lu}][^\\p{Lu}])");

Note that the PUNCTSPACE pattern includes the underscore.

The second pattern TRANSITION contains two zero-length lookahead/lookbehind alternatives. With CamelCase, you split before the first Capital after a lower letter, and you also split before the capital before a lower-case letter (or end-of-word). Consider CamelHTMLCase where we split before the H, and before the C of Case. These are marked by Transitions, one is from lower-to-upper, the other is from upper-to-lower. In each case, we split before the upper.

Note, that \p{Lu} is a regular expression identifier for all upper-case Unicode letters. The \ needs to be escaped in the String constant, so in the constant, you will see two patterns: [\\p{Lu}] and [^\\p{Lu}] The first represents any upper-case character, the second represents any non-upper-case character (including digits, and other punctuation).

So, there are two parts to the TRANSITION pattern:

  • (?<=[^\\p{Lu}])(?=[\\p{Lu}]) - This first one takes the given spot between two characters, and if the char before the spot is not upper, and the char after the spot is upper, then it splits at that spot.
  • (?=[\\p{Lu}][^\\p{Lu}]) - this pattern takes a spot before a character, and, if the character is upper, and after that character is a lower, then split at the spot.

Now, I am not suggesting this is easy, but, it works, and it will work fast.

When splitting the original sentence, it is possible for there to be some leading space, punctuation, or other junk. This may lead to having an initial empty string in the word-split, so we need to ignore empty words.

Putting this together, you get:

private static final Pattern PUNCTSPACE = Pattern.compile("[ \\p{Punct}]+");
private static final Pattern TRANSITION = Pattern.compile("(?<=[^\\p{Lu}])(?=[\\p{Lu}])|(?=[\\p{Lu}][^\\p{Lu}])");

public static final List<String> deHump(String text) {
    List<String> result = new ArrayList<String>();
    for (String word : PUNCTSPACE.split(text)) {
        if (word.isEmpty()) {
            continue;
        }
        for (String part : TRANSITION.split(word)) {
            result.add(part);
        }
    }
    return result;
}

Now, this is great, it will populate a list, but, in the world of Java8, with Lambda expressions, it is 'fun' to do it the streaming way too:

public static final List<String> deHumpLambda(String text) {
    return Arrays.stream(PUNCTSPACE.split(text))
                 .filter(word -> !word.isEmpty())
                 .flatMap(word -> Arrays.asList(TRANSITION.split(word)).stream())
                 .collect(Collectors.toList());
}

The above splits the input in to words based on punctuation and the _ character, then it takes each non-empty word, and splits it again at CamelCase transitions. It accumulates the results in a List, and returns that.

\$\endgroup\$
3
\$\begingroup\$

Code in the question is reinventing the wheel. Apache Commons Lang provides a method splitByCharacterTypeCamelCase() which makes this very simple:

public static List<String> split(String string) {

    List<String> splitted = new ArrayList<>( Arrays.asList(StringUtils.splitByCharacterTypeCamelCase(string)));
    splitted.removeAll(Collections.singleton("_"));

    return splitted;
}

One may ask a question: why list returned by Arrays.asList() is wrapped with new ArrayList<>()?

The answer is simple: Arrays.asList() returns java.util.Arrays.ArrayList which is immutable. Because of this, calling removeAll(), would cause an UnsupportedOperationException. Wrapping this by new ArrayList<>() will create an java.util.ArrayList which is mutable and allows to call removeAll().

\$\endgroup\$
4
  • \$\begingroup\$ This doesn't solve your problem; you didn't get a list of words. There's still things like spaces and empty strings in here. Additionally, have you checked that it supports splitting via underscores? \$\endgroup\$
    – Pimgd
    Sep 10 '14 at 11:36
  • \$\begingroup\$ -1: Closer inspection of splitByCharacterTypeCamelCase reveals it handles numbers different than you do. This might be correct for you in your current environment, but as a replacement it's not suitable. \$\endgroup\$
    – Pimgd
    Sep 10 '14 at 11:56
  • \$\begingroup\$ @Pimgd I didn't state how to handle numbers and spaces, it doesn't matter. Let's assume that there are only cases similar to these shown in examples. \$\endgroup\$
    – Kao
    Sep 10 '14 at 12:42
  • \$\begingroup\$ Sorry, I thought any and all facets of the code were up for review, including correctness with corner cases. The code in the question and the code in here have a different result without explaining why or giving a disclaimer as such. That's what nets you a -1. \$\endgroup\$
    – Pimgd
    Sep 10 '14 at 12:59
3
\$\begingroup\$

First thing I would do, is remove the StringTokenizer and the idea of inserting a separator. If we know where to insert a separator, we can just build up tokens using a StringBuilder.

List<String> tokens = new ArrayList<>();
StringBuilder token = new StringBuilder();

for (int i = 0; i < string.length(); i++) {
  char c = string.charAt(i);

  if (i > 0) {    
    char previousC = string.charAt(i-1);

    if ((!Character.isLowerCase(c) && !Character.isUpperCase(previousC)) //  UpperCamelCase, UPPER_DASHED
        || !Character.isLetterOrDigit(previousC)                    // lower_dashed
        || (i < string.length() - 1) && Character.isLowerCase(string.charAt(i+1))  && Character.isUpperCase(c)  ) // IAttribute
    {       
      if (token.length() > 0) {
        tokens.add(token.toString());
        token.setLength(0);
      }
    }
  }       
  if (Character.isLetterOrDigit(c)) {
    token.append(c);
  }
}

if (token.length() > 0) {
  tokens.add(token.toString());
}

return tokens;

Now that if (i > 0) looks ugly. Let's move the special case out of the loop.

List<String> tokens = new ArrayList<>();
if (string.length() == 0) {
  return tokens;
}

StringBuilder token = new StringBuilder().append(string.charAt(0));
for (int i = 1; i < string.length(); i++) {
  char c = string.charAt(i);
  char prev = string.charAt(i - 1);
  if ((!Character.isLowerCase(c) && !Character.isUpperCase(prev)) //  UpperCamelCase, UPPER_DASHED
      || !Character.isLetterOrDigit(prev)                    // lower_dashed
      || (i < string.length() - 1) && Character.isLowerCase(string.charAt(i+1)) && Character.isUpperCase(c)) // IAttribute
  {       
    if (token.length() > 0) {
      tokens.add(token.toString());
      token.setLength(0);
    }
  }
  if (Character.isLetterOrDigit(c)) {
    token.append(c);
  }
}

if (token.length() > 0) {
  tokens.add(token.toString());
}

return tokens;

Since the conditional is long enough to require three comments, it's time to move it into a separate method.

List<String> tokens = new ArrayList<>();
if (string.length() == 0) {
  return tokens;
}

StringBuilder token = new StringBuilder().append(string.charAt(0));
for (int i = 1; i < string.length(); i++) {
  if (token.length() > 0 && isTransition(string, i)) {       
    tokens.add(token.toString());
    token.setLength(0);
  }

  char c = string.charAt(i);
  if (Character.isLetterOrDigit(c)) {
    token.append(c);
  }
}

if (token.length() > 0) {
  tokens.add(token.toString());
}

return tokens;
\$\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.