Find common “characters” in 2 given strings (rev5)

Could you help me further improve this code, which includes some feedback from this site already Find common “characters” in 2 given strings (rev4)?

What has changed since version 4:

I re-implemented the short-circuiting of scanning the longest string argument via limit(), as suggested by @mjolka. I think that part is quite elegant.

Why I'd like a review:

I would like to explore the possibility of .collect()ing to a String in one go, without losing efficiency.

import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;
import org.junit.Assert;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;
@RunWith(Parameterized.class)
public class CommonCharacters5 {
private static String commonCharactersOf(String string1, String string2) {
// Requirement
//
// Always return lowercase versions of common characters. e.g.:
//
// OK: (a, a) -> a; OK: (a, A) -> a; OK: (A, A) -> a
// No: (a, A) -> a; No: (A, A) -> A; No: (aA, aA) -> aA;
//
// Requirement
//
// Return common characters joined in a String, preserving the order in
// which they appeared in the longest argument, or in the first argument if
// the arguments are of the same length.
//
// Requirement
//
// Handle "characters" (i.e. code points) outside the Basic Multilingual
// Plane (BMP), including characters from Supplementary Planes.
// There should be no char' or Character' based "false positives". e.g.:
//
// String string1 = "\uD835\uDC00", string2 = "\uD835\uDC01";
// string1 and string2 share no characters in the intended acceptation of
// "character".
String shorterArgument, longerArgument;
if (string1.length() < string2.length()) {
shorterArgument = string1;
longerArgument = string2;
} else {
shorterArgument = string2;
longerArgument = string1;
}
// @formatter:off
Set<Integer> shorterArgumentCodePoints =
shorterArgument.codePoints()
.map(Character::toLowerCase)
.boxed()
.collect(Collectors.toSet());
StringBuilder stringBuilder = new StringBuilder();
longerArgument.codePoints()
.map(Character::toLowerCase)
.distinct()
.filter(shorterArgumentCodePoints::contains)
.limit(shorterArgumentCodePoints.size())
.forEach(stringBuilder::appendCodePoint);
return stringBuilder.toString();
}
@Parameters(name = "({0}, {1}) -> {2}")
public static Collection<String[]> data() {
return Arrays.asList(new String[][] {
// @formatter:off
{ ""             , ""                  , ""             },
{ "a"            , ""                  , ""             },
{ ""             , "a"                 , ""             },
{ "aa"           , ""                  , ""             },
{ ""             , "aa"                , ""             },
{ "a"            , "a"                 , "a"            },
{ "aa"           , "b"                 , ""             },
{ "b"            , "aa"                , ""             },
{ "ab"           , "ba"                , "ab"           },
{ "aba"          , "ab"                , "ab"           },
{ "aba"          , "ba"                , "ab"           },
{ "aba"          , "aab"               , "ab"           },
{ "a"            , "A"                 , "a"            },
{ "A"            , "a"                 , "a"            },
{ "A"            , "A"                 , "a"            },
{ "ab"           , "AB"                , "ab"           },
{ "AB"           , "ab"                , "ab"           },
{ "aB"           , "Ab"                , "ab"           },
{ "aB"           , "Ba"                , "ab"           },
{ "aB"           , "Ba"                , "ab"           },
{ "abc"          , "ac"                , "ac"           },
{ "abc"          , "ca"                , "ac"           },
{ "abc"          , "cba"               , "abc"          },
{ "a"            , "\uD835\uDC1A"      , ""             },
{ "\uD835\uDC1A" , "\uD835\uDC1A"      , "\uD835\uDC1A" },
{ "\uD835\uDC00" , "\uD835\uDC00"      , "\uD835\uDC00" },
{ "\uD835\uDC1A" , "\uD835\uDC00"      , ""             },
{ "\uD835\uDC00" , "\uD835\uDC01"      , ""             },
{ "\uD801\uDC2B" , "\uD801\uDC2B"      , "\uD801\uDC2B" },
{ "\uD801\uDC03" , "\uD801\uDC03"      , "\uD801\uDC2B" },
{ "\uD801\uDC2B" , "\uD801\uDC03"      , "\uD801\uDC2B" },
{ "\uD83D\uDE80" , "\uD83D\uDE80"      , "\uD83D\uDE80" },
{ "a"            , "aaaaaaaaaaaaaaaaa" , "a"            },
// The last test should still work, and work fast, with a second
// argument string starting with "a" and ending _many_ characters later
// The last test values doe not test it, but illustrate the scenario
// @formatter:on
});
}
private String string1;
private String string2;
private String expected;
public CommonCharacters5(String string1, String string2, String expected) {
this.string1 = string1;
this.string2 = string2;
this.expected = expected;
}
@org.junit.Test
public void test() {
Assert.assertEquals(expected, commonCharactersOf(string1, string2));
}
}


JUnit test results screenshot, useful to glance at what the hexadecimal literals encode, in terms of surrogate pairs:

• Asking 5 reviews of very similar code with very few differences in one day is too much. You aren't giving time for people to answer your questions properly before you ask a new one.
– jess
Oct 4 '15 at 13:52
• You know, if you allowed 24 hours between questions, they would all count toward a badge. Posting 5 almost-identical questions a few minutes apart is abusive. I believe that's what the downvotes are trying to say. Oct 4 '15 at 15:07
• @Maroloccio Though we generally love iterative reviews, we usually like to allow 12-24 hours between each (at the least) to avoid people pointing out things in the later reviews that could have been pointed out in the original. Just because you get an answer, doesn't mean you shouldn't wait for more. You can also post a selfie-answer if you discover some issues yourself. This helps build the community more, and it keeps you from looking like a "help vampire." Oct 4 '15 at 19:00
• This type of situation is being discussed on Meta.CR as we speak, in case anyone is interested. Oct 4 '15 at 19:51
• My point is only that those who do not see a possible further improvement will want the revisions to stop, but they are exactly the people who should not determine that, as others may see "something" to upgrade :) Oct 4 '15 at 22:01

A number of efficiency issues have been addressed in your code, but there are a number of functional bugs which have not been pointed out, and some tricks you can try that make code more readable.

First up, your desire for the "most stream like" implementation is only useful if streams are the best tools for the job. Not everything in your code is suited to streams, and certainly not suited to a single stream.

Big Bug 1

Let's look at your first bug:

if (string1.length() < string2.length()) {


There are two issues here, both are related to the fact that length only counts the number of characters in the input - where character is a 16-bit value.

The first symptom here is for wide characters which your code anticipates, are 2 characters wide, but are only one code point. Since your code deals with code points, it should only treat the number of code points in the text, not the number of char values required to store them.

The second symptom is that your text may not be similarly represented. A simple character like ö could be represented in multiple ways in Unicode, with some of them requiring "combining character sequences" to append the accents to the base character. In other words, the input string that looks like ö may be one, or two characters long..... Also, not all combining marks can be composed in a single character. Unicode is complicated.

The bottom line is that your very fist step in your code makes assumptions that may be untrue, and as a result, your code will possibly choose the wrong input as being the shortest, and, subsequently, report the common characters in the wrong order.

Big Bug 2

By the way, this same issue results in another bug - you may not identify common characters. A Character using combination marks in one input string will not match a character in composite form in the other.

Here are two additional test cases you need to solve:

{ "abcdefg", "bo\u0308o\u0308o\u0308a", "ab" }, // the second input is shorter!
{ "aöbcdedgh", "bo\u0308o\u0308o\u0308a", "aöb" }, // the second input has expanded ö


The only real way to solve this problem is to normalize both inputs in the same way, and while you are normalizing the text, you may as well convert to lower-case at the same time.

This in turn leads on to a discussion about combining characters. If, after normalization, there are un-composited combining characters, it means that there is no composite character that represents the combining accents... so, how can you treat that as a single character? By maintaining an array of characters that form one base character only.

This is beyond the scope of my answer, how to do that (bug I did it anyway), but, in short, each character should be represented as an array of base character, followed by whatever combining characters are modifying it.

So, your goal: Handle "characters" (i.e. code points) outside the Basic Multilingual Plane (BMP), including characters from Supplementary Planes. is not handled correctly.

Now, I would expect your code to have a method that breaks down the input string in to a normalized set of base characters (possibly surrogate characters), followed by combining marks. Both sides of the input strings should normalize in the same ways, leading to common normalized outputs. The Java library contains the Normalizer class for this exact reason.

Re-implemented - functional, not necessarily efficient

I have put this all together here. If it looks complicated, well, it is because it is complicated.... ;-) :

import java.text.Normalizer;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.junit.Assert;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class CommonCharacters5 {

private static final class CompositeCharacter {
private final char[] sequence;
private final int hashcode;

public CompositeCharacter(char[] sequence) {
this.sequence = sequence;
this.hashcode = Arrays.hashCode(sequence);
}

@Override
public int hashCode() {
return hashcode;
}

@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof CompositeCharacter)) {
return false;
}
CompositeCharacter other = (CompositeCharacter) obj;
return hashcode == other.hashcode && Arrays.equals(sequence, other.sequence);
}

@Override
public String toString() {
return Normalizer.normalize(new String(sequence), Normalizer.Form.NFC);
}

}

private static final CompositeCharacter[] normalize(String input) {
// decompose all input to separate combining marks.
final char[] normal = Normalizer.normalize(input.toLowerCase(), Normalizer.Form.NFD).toCharArray();
final int limit = normal.length;
final int last = limit - 1;
// assume one char per component
final CompositeCharacter[] span = new CompositeCharacter[limit];
int left = 0;
int cnt = 0;
while (left < limit) {
int right = left;
if (Character.isHighSurrogate(normal[right])) {
right++;
}
while (right < last && Character.NON_SPACING_MARK == Character.getType(normal[right + 1])) {
right++;
}
right++;
span[cnt++] = new CompositeCharacter(Arrays.copyOfRange(normal, left, right));
left = right;
}
return Arrays.copyOf(span, cnt);
}

private static String commonCharactersOf(String string1, String string2) {
CompositeCharacter[] common = commonComposites(normalize(string1), normalize(string2));
return Stream.of(common).map(CompositeCharacter::toString).collect(Collectors.joining());
}

private static CompositeCharacter[] commonComposites(final CompositeCharacter[] longer, final CompositeCharacter[] shorter) {
// Requirement
//
// Always return lowercase versions of common characters. e.g.:
//
// OK: (a, a) -> a; OK: (a, A) -> a; OK: (A, A) -> a
// No: (a, A) -> a; No: (A, A) -> A; No: (aA, aA) -> aA;
//
// Requirement
//
// Return common characters joined in a String, preserving the order in
// which they appeared in the longest argument, or in the first argument
// if
// the arguments are of the same length.
//
// Requirement
//
// Handle "characters" (i.e. code points) outside the Basic Multilingual
// Plane (BMP), including characters from Supplementary Planes.
// There should be no char' or Character' based "false positives".
// e.g.:
//
// String string1 = "\uD835\uDC00", string2 = "\uD835\uDC01";
// string1 and string2 share no characters in the intended acceptation
// of
// "character".

if (shorter.length > longer.length) {
// recurse with swapped arguments.
return commonComposites(shorter, longer);
}
// @formatter:off
Set<CompositeCharacter> shorterArgumentCodePoints = Stream.of(shorter).collect(Collectors.toSet());
return Stream.of(longer).filter(shorterArgumentCodePoints::contains)
.limit(shorterArgumentCodePoints.size()).toArray(s -> new CompositeCharacter[s]);
}

@Parameters(name = "({0}, {1}) -> {2}")
public static Collection<String[]> data() {
return Arrays.asList(new String[][] {
// @formatter:off
{ "", "", "" }, { "a", "", "" }, { "", "a", "" }, { "aa", "", "" }, { "", "aa", "" },
{ "a", "a", "a" }, { "aa", "b", "" }, { "b", "aa", "" }, { "ab", "ba", "ab" }, { "aba", "ab", "ab" },
{ "aba", "ba", "ab" }, { "aba", "aab", "ab" }, { "a", "A", "a" }, { "A", "a", "a" }, { "A", "A", "a" },
{ "ab", "AB", "ab" }, { "AB", "ab", "ab" }, { "aB", "Ab", "ab" }, { "aB", "Ba", "ab" },
{ "aB", "Ba", "ab" }, { "abc", "ac", "ac" }, { "abc", "ca", "ac" }, { "abc", "cba", "abc" },
{ "a", "\uD835\uDC1A", "" }, { "\uD835\uDC1A", "\uD835\uDC1A", "\uD835\uDC1A" },
{ "\uD835\uDC00", "\uD835\uDC00", "\uD835\uDC00" }, { "\uD835\uDC1A", "\uD835\uDC00", "" },
{ "\uD835\uDC00", "\uD835\uDC01", "" }, { "\uD801\uDC2B", "\uD801\uDC2B", "\uD801\uDC2B" },
{ "\uD801\uDC03", "\uD801\uDC03", "\uD801\uDC2B" }, { "\uD801\uDC2B", "\uD801\uDC03", "\uD801\uDC2B" },
{ "\uD83D\uDE80", "\uD83D\uDE80", "\uD83D\uDE80" }, { "a", "aaaaaaaaaaaaaaaaa", "a" },
// The last test should still work, and work fast, with a second
// argument string starting with "a" and ending _many_ characters later
// The last test values doe not test it, but illustrate the scenario
{ "abcdefg", "bo\u0308o\u0308o\u0308a", "ab" },
{ "aöbcdedgh", "bo\u0308o\u0308o\u0308a", "aöb" },
// @formatter:on
});
}

private String string1;
private String string2;
private String expected;

public CommonCharacters5(String string1, String string2, String expected) {
this.string1 = string1;
this.string2 = string2;
this.expected = expected;
}

@org.junit.Test
public void test() {
Assert.assertEquals(expected, commonCharactersOf(string1, string2));
}
}


Self-call with swapped args trick

One trick I have in the above code, is the simple 1-level recursion if the argument-length guess is wrong.... it's a common trick that sometimes confuses people:

    if (shorter.length > longer.length) {
// recurse with swapped arguments.
return commonComposites(shorter, longer);
}


In the code, you call it with a short and long argument. If you guessed the wrong argument is shorter, then just call the method again with the arguments reversed. This removes the need for a conditional "swap" routine, and additional variables.

To Do

Even with the more comprehensive handling of composited accents, etc. the code still should probably check for COMBINING_SPACING_MARK characters too. I don't know unicode well enough to know if that is significant.

• Your review is beyond awesome. I did actually know about unicode character "composition" but paid no attention to it in my code. Your remarks are perfect. I am glad you highlighted those bugs. I love your sample code too. Oct 4 '15 at 21:43
• I really feel privileged to get that kind of review. Thank you so much (I had to say it again) Oct 4 '15 at 21:50
• Awesome! But what about { "i", "I", "i" } with java.util.Locale.setDefault(java.util.Locale.forLanguageTag("tr-TR"));? Calling toLowerCase()/toUpperCase() without specifying a Locale should issue a warning. Use toLowerCase(Locale.getDefault()) if { "i", "I", "" } is correct or toLowerCase(Locale.ROOT) if { "i", "I", "i" } is correct. Oct 16 '15 at 12:35

/**
* Return common characters joined in a String, preserving the order in...
*/
public class CommonCharacters5 {
// ...
}


Utility classes and methods

For utility classes and methods, the convention is to make the class final and the constructor private so that it's clear that they should not be instantiated:

public final class CommonCharacters5 {

private CommonCharacters5() {
// empty
}

public static String commonCharactersOf(String string1, String string2) {
// ...
}
}


CharSequence vs String

Since codePoints() is actually a method from the CharSequence interface, you may want to consider making your method accept a pair of CharSequences so that they are even less restrictive to work with.

Unit testing

I lean more towards TestNG myself, and I think its @DataProvider annotation usage is more expressive to construct a set of tests to assert iteratively. I happen to have another answer here that touches on parameterized testing with TestNG. :)

Regardless of the testing framework though, you may want to consider whether to opt for a better modeling approach for your tests, to make them more expressive. For example, if you can encapsulate them as an Enum:

enum MyTestCase {
EMPTY_STRINGS("", "", ""),
A_AND_EMPTY("a", "", ""),
A_AND_B("a", "b", ""),
// ...
ROCKET_EMOJI("\uD83D\uDE80", "\uD83D\uDE80", "\uD83D\uDE80"),
// ...

private final String one;
private final String other;
private final String expected;

private MyTestCase(String one, String other, String expected) {
this.one = one;
this.other = other;
this.expected = expected;
}
}


In your case, the slight benefit I can see is that you can freely swap the inputs to test that your method works regardless of which argument is the longer one:

@org.junit.Test
public void test() {
// assuming current is an instance of MyTestCase
Assert.assertEquals(current.expected, commonCharactersOf(current.one, current.other));
Assert.assertEquals(current.expected, commonCharactersOf(current.other, current.one));
}

• Thanks for the review. In JUnit, if I use @RunWith(Parameterized.class), I need that constructor in that form. I cannot use your "private constructor" advice. I agree: the many // lines are out of place, they belong to JavaDoc. The method signature was given to me but sure, CharSequence sounds better, I often use that when coding for Android (android.text.TextUtils style). Oct 4 '15 at 17:22
• @Maroloccio you can use the enum as the constructor argument to your JUnit test class. Oct 4 '15 at 23:38
• Generally, I like your grouping/labelling of tests. It is an improvement to any battery of parametrised runs. Enums, sometimes static nested classes.. Oct 5 '15 at 2:14
• JUnit vs TestNG is primarily opinion based, and I would definitely not make the test cases into an enum. The benefit can be accomplished anyway, by adding Assert.assertEquals(expected, commonCharactersOf(string2, string1)); to the existing code. Oct 5 '15 at 7:23
• @SimonForsberg right, testing frameworks are a personal choice. :) The other (slight) benefit for an enum-based test values wrapper is that you do get the choice of 'describing' the tests, as I've shown in my example. Instead of guessing what "\uD83D\uDE80" is, the enum value can describe it as ROCKET_EMOJI. Oct 5 '15 at 7:36