components.h

Go to the documentation of this file.

#ifndef COMPONENTS_H
#define COMPONENTS_H

#include <boost/pending/disjoint_sets.hpp>
#include <interval.h>
#include <array2d.h>
#include <bitset.h>

namespace frechet { namespace fs {

class FreeSpace;
class Cell;

class Components {

public:
    typedef boost::disjoint_sets_with_storage<> DisjointSet;
    typedef data::Array2D<data::IntervalPair> IntervalArray;

private:
    int n;  
    int m;  
    DisjointSet disjointSet;    
    //size_t countID;

    IntervalArray intervalArray;
    data::BitSet intervalSet;

    component_id_t componentID(int i, int j);

public:
    static const component_id_t NO_COMPONENT;
    Components(int n, int m);
    void clear();
    component_id_t representative(int i, int j);

    void calculateComponents(FreeSpace& fs);

    component_id_t count() const     { return intervalSet.count(); }

    data::BitSet::iterator begin() const   { return intervalSet.begin(); }
    data::BitSet::iterator end() const     { return intervalSet.end(); }

    data::BitSet::iterator first() const   { return intervalSet.first(); }
    data::BitSet::iterator last() const    { return intervalSet.last(); }

    const IntervalArray& intervals() const { return intervalArray; }

private:
    component_id_t assignComponent(const FreeSpace& fs, int i, int j);
    void normalize();
};

} }  //  namespace

#endif // COMPONENTS_H