Skip to main content
added last section about helper functions
Source Link
Edward
  • 66.6k
  • 4
  • 118
  • 282

Define helper functions to improve readability

All of the parent and grandparent code gives the function above, even in its rewritten version, some clutter. We can greatly improve readability with the use of two helper functions:

S parentOf(S elemIndex) const {
    return nodes.at(elemIndex).parent;
}
// sets new parent and returns previous value
S setParent(S elemIndex, S newparent) const { 
    auto oldparent{parentOf(elemIndex)};
    nodes.at(elemIndex).parent = newparent;
    return oldparent;
}

Now we can rewrite getRepr like this:

S getRepr(S elemIndex) const {
    // Follow parent pointers until we reach a representative
    for (const auto curr = parentOf(elemIndex); curr != parentOf(curr); )  {
        // set parent = grandparent
        elemIndex = setParent(elemIndex, parentOf(curr));
    }
    return parentOf(elemIndex);
}

I find that easier to read and reason about and it's shorter.

Define helper functions to improve readability

All of the parent and grandparent code gives the function above, even in its rewritten version, some clutter. We can greatly improve readability with the use of two helper functions:

S parentOf(S elemIndex) const {
    return nodes.at(elemIndex).parent;
}
// sets new parent and returns previous value
S setParent(S elemIndex, S newparent) const { 
    auto oldparent{parentOf(elemIndex)};
    nodes.at(elemIndex).parent = newparent;
    return oldparent;
}

Now we can rewrite getRepr like this:

S getRepr(S elemIndex) const {
    // Follow parent pointers until we reach a representative
    for (const auto curr = parentOf(elemIndex); curr != parentOf(curr); )  {
        // set parent = grandparent
        elemIndex = setParent(elemIndex, parentOf(curr));
    }
    return parentOf(elemIndex);
}

I find that easier to read and reason about and it's shorter.

Source Link
Edward
  • 66.6k
  • 4
  • 118
  • 282

Here are some things that may help you improve your program.

Use include guards instead of #pragma once

The use of #pragma once, while common, is not standard C++. Use include guards instead as:

#ifndef DISJOINT_SET_HPP
#define DISJOINT_SET_HPP
// your header here
#endif // DISJOINT_SET_HPP

See SF.8 for details.

Don't mark every data member with public or private

If you are uniquely writing in this style, then almost by definition, everyone else who uses your code will find it that much more difficult to read and understand your code. Inserting unnecessary keywords adds visual clutter rather than clarity.

Avoid unneeded casts

The getRepr() function is declared as returning type S, but the return statement within it is this:

return static_cast<std::size_t>(parent);

That makes no sense at all because parent is already declared to be of type S.

Give better messages in exceptions

In the checkStructure() function, the code checks to verify a large number of predicates, collapsing them all into a single bool. If any of the conditions fails, the caller gets only the vague "Assertion error" message. At this point, the structure is somehow corrupted and no longer usable, which represents a rather catastrophic failure of the structure. For that reason, I'd suggest either writing each clause as a separate throw with a clear message or using old-fashioned assert which is likely to be the better choice in this case.

Move error checking to compile time where practical

The constructor currently looks like this:

public: explicit DisjointSet(S numElems) :
        numSets(numElems) {
    if (numElems < 0)
        throw std::domain_error("Number of elements must be non-negative");
    if (!safeLessEquals(numElems, SIZE_MAX))
        throw std::length_error("Number of elements too large");
    nodes.reserve(static_cast<std::size_t>(numElems));
    for (S i = 0; i < numElems; i++)
        nodes.push_back(Node{i, 0, 1});
}

However, if we look carefully at this, both of the checks could actually be done at compile-time instead. That suggests that the use of C++20 requires or C++11 enable_if. Here I'm using the C++14 enable_if_t which is just a convenience function:

template <typename S, 
    typename = std::enable_if_t<std::is_integral<S>::value>,
    typename = std::enable_if_t<std::is_unsigned<S>::value> 
>
class DisjointSet final {

Now if we attempt to create something invalid like DisjoinSet<float> ds(3); we get a much clearer error versus a relatively obscure and unhelpful error pointing to safeLessEquals or checkStructure.

Provide sensible default values where practical

The Node structure is only used internally to the DisjointSet class and is only created in the constructor of DisjointSet. For that reason, I'd suggest declaring it like this:

struct Node final {
    mutable S parent;
    signed char rank = 0;
    S size = 1;
    Node& operator++() { ++parent; return *this; }
};

If you're wondering about the operator, that's part of the next suggestion.

Use standard library functions where practical

I would suggest rewriting the constructor for DisjointSet like this:

explicit DisjointSet(S numElems) 
    : numSets(numElems) 
    , nodes(numElems) 
{
    std::iota(nodes.begin(), nodes.end(), Node{0});
}

Note that this also assumes that we declare numSets before nodes so as not to confuse the reader. (Elements are initialized in declaration order.) In C++20, one could likely use a range and make this even more efficient.

Don't hide a loop return condition

The getRepr() function has a while(true), but actually returns when the parent and grandparent are the same. I'd suggest rewriting that so that the looping exit condition is part of the loop rather than hidden within the body. For example, one way to rewrite would be this:

S getRepr(S elemIndex) const {
    while (nodes.at(elemIndex).parent != nodes.at(nodes.at(elemIndex).parent).parent) {
        auto parent = nodes.at(elemIndex).parent;
        // set parent = grandparent
        nodes.at(elemIndex).parent = nodes.at(parent).parent;
        elemIndex = parent;
    }
    return nodes.at(elemIndex).parent;
}