20

Let us suppose we want to revert the following String "áe".

The unicode for that is "\u0061\u0301\u0065".

The naive aproach of reverting it would be char by char

private static String reverseStringNaive(String s) {
    char[] characters = new char[s.length()];
    for (int i = s.length() - 1; i >= 0; i--) {
        int j = s.length() - i - 1;
        characters[j] = s.charAt(i); 
    }
    return new String(characters);
}

which gives us "éa"(\u0065\u0301\u0061) when we hope to get "eá" (\u0065\u0061\u0301). The accute accent "´" should stick together with the "a", not change to the "e".

The following code gives me the expected result for that String:

private static String reverseString(String s) {
    char[] characters = new char[s.length()];
    for (int i = s.length() - 1; i >= 0; i--) {
        int j = s.length() - i - 1;
        if (Character.isLetterOrDigit(s.charAt(i)) || Character.isISOControl(s.charAt(i))) {
            characters[j] = s.charAt(i); 
        } else {
            characters[j] = s.charAt(i-1);
            characters[j+1] = s.charAt(i);
            i--;
        }
    }
    return new String(characters);
}

I'm checking if each character is Letter, Digit or ISO Control. If not, I'm assuming it should stick together with the previous character.

The question is, are there other things I should check or worry about? Is my aproach still naive?

9
  • What about commons.apache.org/lang/api-2.5/org/apache/commons/lang/… ?
    – user180100
    Sep 19, 2011 at 19:59
  • 2
    Why would anybody want to do that? :-)
    – KarlP
    Sep 19, 2011 at 20:25
  • 1
    Would a change in normalization form be tolerated? Sep 19, 2011 at 20:32
  • 4
    You must never use charAt. It’s broken. YOU JUST ILLEGALLY REVERSED ALL YOUR SURROGATES!!!
    – tchrist
    Sep 19, 2011 at 21:41
  • 2
    @pablosaraiva You have to step through it by grapheme boundaries, not code point boundaries and certainly not code unit boundaries. It looks like icu.text.BreakIterator.getCharacterInstance can be used to build something, but I haven’t tried. It’s much easier in Perl with its support for extended grapheme clusters: reverse /(\X)/g is all it takes. If you don’t do that, you can also invert CRLF combos, enough error.
    – tchrist
    Sep 19, 2011 at 22:51

1 Answer 1

4

Your issue could also be resolved by converting the string into the canonical decomposition form NFC. Basically, the java.text.Normalizer class can be used to combine accents and other combining characters with their base characters so you will be able to reverse properly.

All these other ideas (String.reverse(), StringBuffer.reverse()) will correctly reverse the characters in your buffer, but if you start with decomposed characters, you might not get what you expect :).

In some "decomposition forms", accent characters are stored separate from their base forms (as separate characters), but in "combined" form they are not. So in one form "áe" is stored as three characters, and in the other, combined form, as two.

However, such normalization isn't sufficient for handling other kinds of character combination, nor can it account for characters in the Unicode astral planes, which are stored as two characters (or more?) in Java.

Thanks to tchrist for pointing out the ICU support for text segmentation including extended grapheme clusters such as the one identified in the comments below (see virama). This resource seems to be the authoritative source of information on this kind of stuff.

13
  • It is indeed a nice a aproach that works for the input I gave you, but it fails to the following string: सरस्वती. Sep 19, 2011 at 20:25
  • 1
    Mike, I would have thought normalization to NFC would be the way to go, so each surrogate pair has the best chance of representing the intended abstract character... Sep 19, 2011 at 20:34
  • 1
    @Mike: You have to use ICU. OraSun can’t do it. Also, you cannot use String.reverse(), StringBuffer.reverse() because you break all the surrogates. Try flipping MATHEMATICAL FRAKTUR CAPITAL A, COMBINING DOT ABOVE, MATHEMATICAL FRAKTUR CAPITAL B: U+1D504 U+0307 U+1D505. The right answer is MATHEMATICAL FRAKTUR CAPITAL B, MATHEMATICAL FRAKTUR CAPITAL A, COMBINING DOT ABOVE: U+1D505 U+1D504 U+0307. The naïve way flips surrogates and creates illegal noncharacter sequences.
    – tchrist
    Sep 19, 2011 at 21:46
  • 3
    Normalization doesn't sound right: Turning base+modifier pairs into single characters is decidedly a legacy operation, and in general there aren't any compound characters for a given sequence of modifiers -- that's the whole point of separating the base character from the modifiers. So I would abandon this approach entirely and rather look for a proper Unicode library that understands combining characters.
    – Kerrek SB
    Sep 19, 2011 at 21:57
  • 3
    @Mike: It looks like you need to use the getCharacterInstance method from icu.text.BreakInterator. Gosh, what a terrible pain. I’m use to being able to just do reverse /(\X)/g in Perl.
    – tchrist
    Sep 19, 2011 at 22:02

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.