Repository: opencv/opencv
File: modules/objdetect/src/aruco/apriltag/unionfind.hpp (C++)

Code before:
// Copyright (C) 2013-2016, The Regents of The University of Michigan.
//
// This software was developed in the APRIL Robotics Lab under the
// direction of Edwin Olson, ebolson@umich.edu. This software may be
// available under alternative licensing terms; contact the address above.
//
// The views and conclusions contained in the software and documentation are those
// of the authors and should not be interpreted as representing official policies,
// either expressed or implied, of the Regents of The University of Michigan.
#ifndef _OPENCV_UNIONFIND_HPP_
#define _OPENCV_UNIONFIND_HPP_

namespace cv {
namespace aruco {

struct ufrec {
    // the parent of this node. If a node's parent is its own index,
    // then it is a root.
    uint32_t parent;

    // for the root of a connected component, the number of components
    // connected to it. For intermediate values, it's not meaningful.
    uint32_t size;
};

struct Unionfind {
    Unionfind(uint32_t _maxid)
    {
        maxid = _maxid;
        data = (struct ufrec*) malloc((maxid+1) * sizeof(struct ufrec));
        for (unsigned int i = 0; i <= maxid; i++) {
            data[i].size = 1;
            data[i].parent = i;
        }
    };

    ~Unionfind() {
        if (data)
            free(data);
    }

    inline uint32_t get_representative(uint32_t id) {
        uint32_t root = id;

        // chase down the root
        while (data[root].parent != root) {
            root = data[root].parent;
        }

        // go back and collapse the tree.
        //

Review comment (suggestion):
I think the data structure name is `DisjointSet` like [`scipy` does](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.DisjointSet.html), but if original naming should be preserved its better to use CamelCase: `UnionFind`.

Code after:
// Copyright (C) 2013-2016, The Regents of The University of Michigan.
//
// This software was developed in the APRIL Robotics Lab under the
// direction of Edwin Olson, ebolson@umich.edu. This software may be
// available under alternative licensing terms; contact the address above.
//
// The views and conclusions contained in the software and documentation are those
// of the authors and should not be interpreted as representing official policies,
// either expressed or implied, of the Regents of The University of Michigan.
#ifndef _OPENCV_UNIONFIND_HPP_
#define _OPENCV_UNIONFIND_HPP_

namespace cv {
namespace aruco {

struct UnionFind {
    UnionFind(uint32_t _maxid)
    {
        maxid = _maxid;
        data.resize(maxid+1);
        for (unsigned int i = 0; i <= maxid; i++) {
            data[i].size = 1;
            data[i].parent = i;
        }
    };

    inline uint32_t get_representative(uint32_t id) {
        uint32_t root = id;

        // chase down the root
        while (data[root].parent != root) {
            root = data[root].parent;
        }

        // go back and collapse the tree.
        //
        // XXX: on some of our workloads that have very shallow trees
        // (e.g. image segmentation), we are actually faster not doing
        // this...
        while (data[id].parent != root) {
            uint32_t tmp = data[id].parent;
            data[id].parent = root;
            id = tmp;
        }

        return root;
    }

    inline uint32_t get_set_size(uint32_t id) {
        uint32_t repid = get_representative(id);
        return data[repid].size;