disjoint_sets.h

Go to the documentation of this file.

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; eval: (progn (c-set-style "stroustrup") (c-set-offset 'innamespace 0)); -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2010, The TPIE development team
// 
// This file is part of TPIE.
// 
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
// 
// TPIE is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
// License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE.  If not, see <http://www.gnu.org/licenses/>
#ifndef __TPIE_DISJOINT_SETS__
#define __TPIE_DISJOINT_SETS__

#include <tpie/array.h>
#include <tpie/unused.h>
#include <tpie/util.h>

namespace tpie {

template <typename value_t=size_type> 
class disjoint_sets: public linear_memory_base< disjoint_sets<value_t> > {
private:
    array<value_t> m_elements;
    value_t m_unused;
    size_type m_size;
public:
    static double memory_coefficient() {
        return array<value_t>::memory_coefficient();
    }

    static double memory_overhead() {
        return array<value_t>::memory_overhead() + sizeof(disjoint_sets) - sizeof(array<value_t>);
    }

    disjoint_sets(size_type n=0,
                  value_t u = default_unused<value_t>::v(),
                  tpie::memory_bucket_ref b = tpie::memory_bucket_ref())
        : m_elements(n, u, b), m_unused(u), m_size(0) {}    

    disjoint_sets(tpie::memory_bucket_ref b): m_elements(b), m_unused(default_unused<value_t>::v()), m_size(0) {}
    
    inline void make_set(value_t element) {m_elements[element] = element; ++m_size;}

    inline bool is_set(value_t element) {return m_elements[element] != m_unused;}

    inline value_t link(value_t a, value_t b) {
        if (a == b) return a;
        --m_size;
        m_elements[b] = a;
        return a;
    }

    inline value_t find_set(value_t t) {
        // If t sits in depth d, we halve the depth of d/2 nodes in the tree,
        // including t.
        while (true) {
            // Set t to point to its grandparent.
            value_t x = m_elements[m_elements[t]];
            if (x == t) return t;
            m_elements[t] = x;
            t = x;
        }

        // The textbook implementation below is faster for some adversarial
        // inputs, but is cache inefficient on ordinary input.

        //value_t r = m_elements[t];
        //if (r == t)
        //  return r;
        //while (r != m_elements[r])
        //  r = m_elements[r];
        //while (t != r) {
        //  value_t next = m_elements[t];
        //  m_elements[t] = r;
        //  t = next;
        //}
        //return r;
    }

    inline value_t union_set(value_t a, value_t b) {
        return link(find_set(a), find_set(b));
    }

    inline size_type count_sets() {
        return m_size;
    }

    void clear() {
        std::fill(m_elements.begin(), m_elements.end(), m_unused);
        m_size = 0;
    }

    void resize(size_t size) {
        m_elements.resize(size, m_unused);
        m_size = 0;
    }
};

}
#endif //__TPIE_DISJOINT_SETS__