2
\$\begingroup\$

I have an approach that seems to work though I feel like I must be misusing something to achieve it. I am implementing a keyword matching algorithm to a Java 8 IntStream. The goal is to walk over a stream of char values (created by calling .chars() on an input string called sentence). If a keyword matches it is returned with its replacement value otherwise the original characters are returned unmodified. The code I have written so far looks like this: The Replacer is implemented as a Consumer<Character> with some stateful properties:

class Replacer implements Consumer<Character> {
    StringBuffer out;
    StringBuffer buffer;
    KeywordTrieNode current_keyword_trie_node;
    KeywordTrieNode keyword_trie_root;

    public Replacer(KeywordTrieNode keyword_trie_root) {
        this.keyword_trie_root = keyword_trie_root;
        this.current_keyword_trie_node = keyword_trie_root;
        this.out = new StringBuffer();
        this.buffer = new StringBuffer();
    }

    @Override
    public void accept(Character c) {
        KeywordTrieNode node = current_keyword_trie_node.get(c);
        if (node != null) {
            buffer.append(c);
            current_keyword_trie_node = node;
        } else {
            String keyword = current_keyword_trie_node.get();
            if (keyword != null) {
                out.append(keyword);
            } else {
                out.append(buffer);
            }
            out.append(c);
            buffer = new StringBuffer();
            current_keyword_trie_node = this.keyword_trie_root;
        }
    }

    @Override
    public String toString() {
        // Flush the buffer
        String keyword = current_keyword_trie_node.get();
        if (keyword == null) {
            out.append(buffer);
        } else {
            out.append(keyword);
        }
        return out.toString();
    }
}

Then to use this I have this function:

public String replace(String sentance) {
    return replace(sentance.chars());
}
public String replace(IntStream stream) {
    Replacer replacer = new Replacer(this.keyword_trie_root);

    stream.mapToObj(c -> (char) c).forEachOrdered(replacer);

    return replacer.toString();
}

Here the String is converted into a IntStream, the stream is then mapped into a stream of char values (which are autoboxed into Character which is needed for the underlying Map inside the keyword_trie_root). Then the replacer is passed to forEachOrdered allowing it to see each character and build a bigger and bigger StringBuffer until it's toString() is invoked (performing one final buffer flush). This doesn't feel like the correct use of Java streams but I'm hitting a bit of a wall when trying to reimagine this as a Combiner which I think is the correct way to solve this problem. Any ideas?

\$\endgroup\$
2
\$\begingroup\$

Bug:

Calling toString repeatedly will append the last keyword (or the buffer) multiple times. This is not really in line with how this should work.

Conventions:

Java coding conventions state that member names should be lowerCamelCase. the fields related to the keyword trie do not follow that convention.

Another convention that you seem to disregard here is that Tries usually enable quick searching through strings by virtue of allowing skipping characters before doing the next comparison. As such naming the KeywordTrie as "Trie" is not really correct.

Minor simplifications & fixes:

You should specify explicit visibilities on all your fields. It's almost never appropriate to use the default visibility in java. package-private is almost always wrong.

The names you're using are somewhat wordy for my own taste as well.

In addition you can initialize fields in a field initializer instead of the constructor to make the ctor simpler to read. Consider:

public class Replacer [...] {
    private StringBuffer out = new StringBuffer();
    private StringBuffer buffer = new StringBuffer();
    private KeywordTrieNode currentNode;
    private KeywordTrieNode trieRoot;

Design issues:

A consumer should not return a result. That's not what they do. They take an element and that's it.

What you have here is a Collector. Something that takes a Stream and collapses it into a value. Let's make sure we use the correct interface here:

public class Replacer implements Collector<Character, StringBuilder, String> {

This in turn gives us the following functions to implement:

BiConsumer<StringBuffer, Character> accumulator()
Set<Consumer.Characteristics> characteristics()
BinaryOperator<StringBuffer> combiner()
Function<StringBuffer, String> finisher()
Supplier<StringBuffer> supplier()

Let's start with the important stuff that governs how the Collector will be used by the Stream implementation. Our collector is Ordered, Sequential and changes stuff when the finisher is invoked. This means that none of the Characteristics for optimization apply:

public Set<Collector.Characteristics> characteristics() { 
    return Collections.emptySet(); 
}

Now we can deal with the stuff that we need to set up:

public BinaryOperator<StringBuffer> combiner() {
    // explicitly doesn't do anything, supplier always returns the same object
    return (a, b) -> a;
}

public Supplier<StringBuffer> supplier() {
    return () -> {
        return out;
    };
}

Note that I assume we're using the same private fields (and constructor) as in the question, because they seem like an acceptable encapsulation of the problem you're trying to solve.

Now we need to implement the accumulation, this is basically your "accept":

public BiConsumer<StringBuffer, Character> accumulator() {
    return (out, character) -> {
        KeywordTrieNode next = currentNode.get(character);
        if (next != null) {
            buffer.append(character);
            currentNode = next;
        } else {
            String keyword = currentNode.get();
            out.append(keyword == null ? buffer : keyword)
               .append(character);
            buffer = new StringBuilder();
            currentNode = trieRoot;
        }
    };
};

public Function<StringBuffer, String> finisher() {
    return (out) -> {
        String keyword = currentNode.get();
        out.append(keyword == null ? buffer : keyword);
        return out.toString();
    };
}

With this implementation we can rewrite your replace function to look as follows:

public String replace(IntStream chars) {
     return chars.collect(new Replacer(keywordTrieRoot));
}
\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much! I was having the hardest time wrapping my head around this concept and now it makes sense. \$\endgroup\$ – Jason Sperske Jul 17 '18 at 17:54

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.