components.cpp

Go to the documentation of this file.

#include <boost/iterator/counting_iterator.hpp>

#include <components.h>
#include <types.h>
#include <freespace.h>
#include <limits.h>

#include <QDebug>
#include <iostream>

using namespace frechet;
using namespace data;
using namespace fs;

const component_id_t Components::NO_COMPONENT = (component_id_t)SIZE_MAX;
component_id_t Components::componentID(int i, int j) {
    return intervalArray.offset(i,j);
}

Components::Components(int an, int am) :
    n(an), m(am),
    disjointSet(),
    //countID(0),
    intervalArray(std::max(n-1,0),std::max(m-1,0)),
    intervalSet(intervalArray.n * intervalArray.m)
{
    clear();
}

void Components::clear() {
    intervalSet.clear();

    if ((n > 0) && (m > 0)) {
        disjointSet = DisjointSet((n-1)*(m-1));
        //  TODO disjointSet.clear()
        //intervals.resize((n-1)*(m-1));
    }
}

//size_t frechet::Components::newComponent()
//{
//    disjointSet.make_set(++countID);
//    intervals.resize(countID+1);
//    return countID;
//}

void Components::calculateComponents(FreeSpace& fs)
{
    clear();

    int i,j;
    for(i=0; i < (fs.n-1); ++i)
        for(j=0; j < (fs.m-1); ++j)
            if (fs.cellEmptyBounds(i,j))
            {
                component_id_t thisRep=componentID(i,j);
                disjointSet.make_set(thisRep); //  singleton component without an interval
                intervalSet -= thisRep;
                //intervalArray.at(i,j).clear();
            }
            else {
                component_id_t thisRep = assignComponent(fs,i,j);
                Q_ASSERT(intervalSet[thisRep]);
            }

    //normalize();    //  DONT this destroys the relation between disjointSet and intervals set

    //  now, let's list all components and their intervals
/*    std::cout << "===========================\n";
    Array2DSet<IntervalPair>::iterator it = intervals.begin();
    for( ; it.valid(); )
    {
        Q_ASSERT(*it == intervals.at(it.offset()));
        Q_ASSERT(*it == intervals.at(it.i(),it.j()));
        std::cout << " ["<<it.offset()<<"] "
                 << " ("<<it.i()<<","<<it.j()<<") "
                 << *it
                 << "\n";
        ++it;
    }
    std::cout << "===========================\n";
    //  disjointSet and interval set must be in synch
    for(i=0; i < (fs.n-1); ++i)
    {
        for(j=0; j < (fs.m-1); ++j)
            if (! fs.cellEmpty(i,j)) {
                size_t rep = representative(i,j);
                if (!intervals.contains(rep)) {
                    std::cout << rep << " gone missing " << intervals.at(rep) << "\n";
                }
            }
    }
    std::cout << "\n";
*/
}

component_id_t Components::assignComponent(const FreeSpace& fs, int i, int j)
{
    const Cell& cl = fs.cell(i,j);

    component_id_t thisRep = componentID(i,j);
    disjointSet.make_set(thisRep);

    bool connectLeft = (i > 0) && cl.L;
    bool connectBottom = (j > 0) && cl.B;

    IntervalPair thisBounds = cl.bounds.translated(i,j);
    if (!connectLeft && !connectBottom) {
        //  singleton component
        intervalSet += intervalArray.offset(i,j);
        intervalArray.at(i,j) = thisBounds;
        return thisRep;
    }

    component_id_t leftRep=Components::NO_COMPONENT, bottomRep=Components::NO_COMPONENT;
    if (connectLeft) {
        leftRep = representative(i-1,j);    //  component REPRESENTATIVE of left neighbor
        Q_ASSERT(intervalSet[leftRep]);  //  representatives MUST be in the interval set, too
    }
    if (connectBottom) {
        bottomRep = representative(i,j-1);    //  component REPRESENTATIVE of bottom neighbor
        Q_ASSERT(intervalSet[bottomRep]);
    }

    if (connectLeft && connectBottom) {
        disjointSet.link(leftRep,thisRep);
        if (leftRep!=bottomRep)
            disjointSet.union_set(leftRep,bottomRep);
    }
    else if (connectLeft) {
        disjointSet.link(leftRep,thisRep);
    }
    else /*if (connectBottom)*/ {
        Q_ASSERT(connectBottom);
        disjointSet.link(bottomRep,thisRep);
    }

    component_id_t newRep = disjointSet.find_set(thisRep);

    Q_ASSERT((newRep==leftRep) || (newRep==bottomRep) || (newRep==thisRep));

    if (newRep==leftRep) {
        Q_ASSERT(intervalSet[leftRep]);
        IntervalPair& ival = intervalArray[leftRep];
        if (connectBottom && (bottomRep!=leftRep)) {
            intervalSet -= bottomRep;
            ival += intervalArray[bottomRep];
        }
        ival += thisBounds;
    }
    else if (newRep==bottomRep) {
        Q_ASSERT(intervalSet[bottomRep]);
        IntervalPair& ival = intervalArray[bottomRep];
        if (connectLeft && (leftRep!=bottomRep)) {
            intervalSet -= leftRep;
            ival += intervalArray[leftRep];
        }
        ival += thisBounds;
    }
    else {
        Q_ASSERT(newRep==thisRep);
        intervalSet += thisRep;
        IntervalPair& ival = intervalArray[thisRep] = thisBounds;
        Q_ASSERT(intervalSet[thisRep]);
        if (connectBottom) {
            intervalSet -= bottomRep;
            ival += intervalArray[bottomRep];
        }
        if (connectLeft) {
            intervalSet -= leftRep;
            ival += intervalArray[leftRep];
        }
    }

    Q_ASSERT(!connectLeft || (representative(i-1,j)==newRep));
    Q_ASSERT(!connectBottom || (representative(i,j-1)==newRep));
    Q_ASSERT(representative(i,j)==newRep);

    //  intervals[newRep] contains now the union of all three (or two) intervals
    Q_ASSERT(representative(i,j)==newRep && intervalSet[newRep]);
    Q_ASSERT(!connectLeft || (representative(i-1,j)==newRep &&
                              (leftRep==newRep || !intervalSet[leftRep])));
    Q_ASSERT(!connectBottom || (representative(i,j-1)==newRep &&
                                (bottomRep==newRep || !intervalSet[bottomRep])));
    Q_ASSERT(intervalSet[newRep]);
    return newRep;
}

component_id_t Components::representative(int i, int j) {
    return disjointSet.find_set(componentID(i,j));
    //  representative of the component
}

void Components::normalize()
{
    //  normalize components
    if ((n > 0) && (m > 0))
        disjointSet.normalize_sets(
                    boost::make_counting_iterator(0),
                    boost::make_counting_iterator((n-1)*(m-1)));

}