2
\$\begingroup\$

I'm trying to build simple pattern matching in a string.

ie., Given a template of: "Hello ${1}" and an input of "Hello world", I'd like to be able to return a map of 1='world'.

This test demonstrates what I'm trying to acheive:

@Test
public void detectsTokenValues()
{
    Properties properties = formatter.getTokenValues("${1}/andThen/${2}/followedBy/${3}","start/andThen/middle/followedBy/end");
    assertThat((String) properties.get("1"), equalTo("start"));
    assertThat((String) properties.get("2"), equalTo("middle"));
    assertThat((String) properties.get("3"), equalTo("end"));
}

Here's my implementation. It works, but I feel like it's convoluted, and I suspect there's Regex or other JDK native features I could be using to make it simpler.

// Matches ${0} - ${9999} etc.,  But not ${variblesWithWords}
private static final Pattern NUMERIC_VARIABLES = Pattern.compile("\\$\\{([0-9]+?)\\}");


Properties getTokenValues(String template, String input) {
    Properties properties = new Properties();
    Matcher matcher = NUMERIC_VARIABLES.matcher(sourcestring);
    final int variableWrapperLength = "${}".length();
    int accumulativeOffset = 0;
    while (matcher.find())
    {
        String variableName = matcher.group(1);
        String value = null;
        if (matcher.end() >= template.length())
        {
            value = input.substring(matcher.start() + accumulativeOffset);
        } else {
            // Find the character after the variable in the template.
            // This serves as the end-delimeter in the input string.
            String endDelimiter = template.substring(matcher.end(),matcher.end()+1);
            int variableEndIndex = findEndDelimiterIndex(input, matcher.start() + 1,
                    endDelimiter);
            value = input.substring(matcher.start() + accumulativeOffset, variableEndIndex);

            // Adjust the accumulative offset to account for the difference
            // in lengths between the variableName (eg., ${1}) 
            // and the the actual value (eg., 'foo') 
            accumulativeOffset += value.length() - (variableWrapperLength + variableName.length());
        }

        if (value != null)
            properties.put(variableName, value);
    }
    return properties;
}

private int findEndDelimiterIndex(String input, int fromIndex,
        String endDelimiter) {

    // Find the first instance of the delimiter in the input string
    // that occurs after the start of our  matches variable.
    if (fromIndex > input.length())
    {
        return Integer.MAX_VALUE;
    }
    int variableEndIndex = input.indexOf(endDelimiter,fromIndex);
    return variableEndIndex;
}

How can I improve this method?

\$\endgroup\$
  • \$\begingroup\$ NUMERIC_VARIABLES.matcher(sourcestring); shouldn't be NUMERIC_VARIABLES.matcher(template)? \$\endgroup\$ – palacsint Aug 31 '12 at 19:56
3
\$\begingroup\$

The function getTokenValues is actually a pattern matching function. It just uses a different syntax than the pattern format of java.util.regex.

I suggest you to convert your pattern string (the one with $ signs) into a valid Pattern.

${1}/andThen/${2}/followedBy/${3}

becomes

(.+?)/andThen/(.+?)/followedBy/(.+?)

And then you can use Pattern.matcher to find the content of the groups. There is still one thing missing : the fact that the numbering of the original pattern is lost. For that, you can parse the original pattern string to extract those numbers, to create a mapping table.

When you convert your pattern string into a Pattern, be careful to escape the substrings between the $ using Pattern.quote().

I don't know if this solution would be an improvement of yours, but it's an alternative to consider.

Edit

The implementation of my solution :

Map<String, String> getTokenValues(String pattern, String str) {
    Map<String, String> res = new HashMap<String, String>();
    List<String> identifiers = new ArrayList<String>();

    Pattern dollarRgx = Pattern.compile("\\$\\{([0-9]+?)\\}");
    Matcher dollarMatcher = dollarRgx.matcher(pattern);
    StringBuilder convRgxBd = new StringBuilder();
    int lastEnd = 0;
    while(dollarMatcher.find()) {
        String before = pattern.substring(lastEnd, dollarMatcher.start());
        convRgxBd.append(Pattern.quote(before));
        convRgxBd.append("(.+?)");
        lastEnd = dollarMatcher.end();
        identifiers.add(dollarMatcher.group(1));
    }
    String after = pattern.substring(lastEnd, pattern.length());
    convRgxBd.append(Pattern.quote(after));

    Pattern convRgx = Pattern.compile(convRgxBd.toString());
    Matcher convMatcher = convRgx.matcher(str);
    if(convMatcher.matches()) {
        for(int i = 0; i < convMatcher.groupCount(); i++) {
            String id = identifiers.get(i);
            res.put(id, convMatcher.group(i+1));
        }
    }

    return res;
}
\$\endgroup\$
2
\$\begingroup\$

Just a side note: You could avoid the (String) casting if you used a Map (a HashMap, for example) instead of Properties. Properties has a design flaw: it should not extend Hashtable.

Effetcive Java, 2nd Edition mentions it in its Item 16: Favor composition over inheritance:

In the case of Properties, the designers intended that only strings be allowed as keys and values, but direct access to the underlying Hashtable allows this invariant to be violated. Once this invariant is violated, it is no longer possible to use other parts of the Properties API (load and store). By the time this problem was discovered, it was too late to correct it because clients depended on the use of nonstring keys and values.


Here is an alternate implementation based on @barjak's idea:

private static final String NON_GROUP_REGEX = ".*?";
private static final String GROUP_REGEX = "(.*?)";

public Map<String, String> getTokenValues2(final String template, final String input) {
    final Map<String, String> result = new LinkedHashMap<String, String>();

    final List<String> variableNames = getVariableNames(template);
    // TODO: check duplicated variables here

    for (final String variableName: variableNames) {
        final String value = getValueForVariable(template, input, variableName);
        result.put(variableName, value);
    }
    return result;
}

private List<String> getVariableNames(final String template) {
    final List<String> result = new ArrayList<String>();
    final Matcher matcher = NUMERIC_VARIABLES.matcher(template);
    while (matcher.find()) {
        final String variableName = matcher.group(1);
        result.add(variableName);
    }
    return result;
}

private String getValueForVariable(final String template, final String input, 
        final String variableName) {
    final String variableRegex = createVariableRegex(template, variableName);
    final Matcher variableMatcher = Pattern.compile(variableRegex).matcher(input);
    if (!variableMatcher.matches()) {
        throw new IllegalStateException("template: " + template + ", input: " 
                + input + ", variableName " + variableName);
    }
    final String value = variableMatcher.group(1);
    return value;
}

private String createVariableRegex(String template, 
        final String groupMatcherVariableName) {
    template = replaceNumericVariableToGroupMatcher(template, groupMatcherVariableName);
    template = replaceNumericVariablesToNonGroupMatchers(template);
    return template;
}

private String replaceNumericVariablesToNonGroupMatchers(final String template) {
    return NUMERIC_VARIABLES.matcher(template)
        .replaceAll(Matcher.quoteReplacement(NON_GROUP_REGEX));
}

private String replaceNumericVariableToGroupMatcher(final String template, 
        final String variableName) {
    final Pattern variableNamePattern = Pattern.compile(Pattern
        .quote("${" + variableName + "}"));
    final String quotedVariableNameReplacementRegexp = 
        Matcher.quoteReplacement(GROUP_REGEX);
    return variableNamePattern.matcher(template)
        .replaceFirst(quotedVariableNameReplacementRegexp);
}
\$\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.