drwnDisjointSets.h

/*****************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnDisjointSets.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**
*****************************************************************************/

#pragma once

#include <vector>

// drwnDisjointSets ---------------------------------------------------------

class drwnDisjointSets {
 protected:
    typedef struct _node_t {
        int rank;                   // depth of node
        int size;                   // size of set (for root nodes)
        int index;                  // index of the element represented by this node
        _node_t *parent;            // parent of this node
    } node_t;

    int _nElements;                 
    int _nSets;                     
    std::vector<node_t> _nodes;     

 public:
    drwnDisjointSets(unsigned int count = 0);
    drwnDisjointSets(const drwnDisjointSets &dset);
    ~drwnDisjointSets();

    inline int size() const { return _nElements; }
    int size(int setId) const;
    inline int sets() const { return _nSets; }
    std::set<int> getMembers(int setId);
    void add(int count);
    int find(int elementId);
    int join(int setId1, int setId2);
    std::vector<int> getSetIds() const;

    drwnDisjointSets& operator=(const drwnDisjointSets& dset);
};