current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

Working my way through Algorithms, Fourth edition by Robert Sedgewick & Kevin Wayne. I implemented a generic version of the Quick-Union algorithm and added Path Compression (not described in the book) to it.

Mainly I'm looking for feedback on these two aspects and whether I might have overlooked a side effect.

public class WeightedQuickUnionWithPathCompression<T> {
    private final Map<T, T> components = new HashMap<>();
    private final Map<T, Integer> treeSizes = new HashMap<>();

    public WeightedQuickUnionWithPathCompression(T[] components) {
        for (T component : components) {
            this.components.put(component, component);
            this.treeSizes.put(component, 1);
        }
    }

    public void connect(T leftComponent, T rightComponent) {
        Objects.requireNonNull(leftComponent);
        Objects.requireNonNull(rightComponent);

        if (areConnected(leftComponent, rightComponent)) {
            return;
        }

        T leftComponentTree = find(leftComponent);
        T rightComponentTree = find(rightComponent);

        int leftTreeSize = getTreeSize(leftComponentTree);
        int rightTreeSize = getTreeSize(rightComponentTree);
        if (leftTreeSize < rightTreeSize) {
            components.put(leftComponentTree, rightComponentTree);
            treeSizes.put(rightComponentTree, leftTreeSize + rightTreeSize);
        } else {
            components.put(rightComponentTree, leftComponentTree);
            treeSizes.put(leftComponentTree, leftTreeSize + rightTreeSize);
        }
    }

    private T find(T component) {
        while (!component.equals(components.get(component))) {
            components.put(component, components.get(components.get(component))); // Path compression
            component = components.get(component);
        }
        return component;
    }

    private int getTreeSize(T component) {
        return treeSizes.get(component);
    }

    public boolean areConnected(T leftComponent, T rightComponent) {
        Objects.requireNonNull(leftComponent);
        Objects.requireNonNull(rightComponent);
        return find(leftComponent).equals(find(rightComponent));
    }
}
share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

In find() and areConnected(), you should be able to use == rather than .equals() since you are comparing references, not contents.

Your find() loop is a bit inefficient:

  • You do components.get(component) once during the while condition test, and again during path compression.
  • You do components.put(component, …) during path compression, then immediately lookup components.get(component) to advance the loop.

The remedy is to introduce two temporary variables, which I call parent and grandparent.

I've chosen to write it as a for loop with side-effect assignments, but of course you can choose to use a while loop without side-effect assignments.

private T find(T c) {
    // Lookup with path compression
    for (T parent, grandparent; (parent = components.get(c)) != c; c = grandparent) {
        components.put(c, grandparent = components.get(parent));
    }
    return c;
}

connect() calls areConnected(), which performs redundant work. I suggest…

public void connect(T leftComponent, T rightComponent) {
    Objects.requireNonNull(leftComponent);
    Objects.requireNonNull(rightComponent);

    T leftComponentTree = find(leftComponent);
    T rightComponentTree = find(rightComponent);

    if (leftComponentTree == rightComponentTree) {
        return;     // Already connected
    }

    …
}
share|improve this answer
    
Invaluable remarks, much appreciated! I've stuck with a while loop inside find(T) because it stays more true to the original algorithm, but the intermediate assignments definitely were an eye-opener. –  Jeroen Vannevel May 8 at 1:11
add comment
up vote 1 down vote

While I applaud your effort to keep methods short by refactoring, I question the benefit of replacing

treeSizes.get(component)

with a private method call that saves two characters without abstracting or encapsulating anything:

getTreeSize(component)

I'd be curious to see if introducing a private static class to combine the result of find and getTreeSize could simplify connect.

Finally, why bother with the null checks when null values will immediately throw NPE anyway? It would make sense if the check included a message denoting the problem, but all you get here is a line number--no more than without them. Not that this isn't a good habit in general.

share|improve this answer
    
You're right about the simplicity of the method. On one hand I like the level of abstraction it brings but at the same time it's not something I expected to change so I'll remove the intermediate method. Could you clarify what you mean with the private class? Good point about the parameter checking as well, I've used the overload instead. –  Jeroen Vannevel May 8 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.