kalgorithm.h

Go to the documentation of this file.

#ifndef ALGORITHMBASE_H
#define ALGORITHMBASE_H

#include <freespace.h>
#include <app/workerthread.h>

#include <exception>
#include <stack>
#include <functional>

//#include <boost/thread/mutex.hpp>
#include <QMutex>

//  throw (...) considered deprecated (but still useful)
#if defined __GNUC__
# pragma GCC diagnostic ignored "-Wdeprecated"
#elif defined _MSC_VER
# pragma warning( disable : 4290 )
#endif

namespace frechet { namespace k {

class MappedInterval : public data::Interval {
public:
    int componentID;

    MappedInterval()
            : Interval(), componentID(-1) {}

    MappedInterval(const Interval &ival, int compID)
            : Interval(ival), componentID(compID) {}

    bool operator<(const MappedInterval &that) const;
    bool operator==(const MappedInterval &that) const;
};
typedef std::vector<MappedInterval> IntervalMap;


class kAlgorithm : public QObject {
    Q_OBJECT
signals:
    void greedyFinished();
    void bruteForceIteration(int);
    void bruteForceFinished();
    //void bruteForceCancelled();

public:
    enum Result {
        UNKNOWN = -3,       
        RUNNING = -2,       
        NO_SOLUTION = -1    
    };

protected:
    typedef std::vector<std::pair<int, double>> Stack;

    const fs::Components &components;
    data::IntervalPair domain;

    struct WorkingSet {
        IntervalMap hmap;
        IntervalMap vmap;
        data::BitSet set;
        QMutex lock;

        WorkingSet() : hmap(),vmap(),set(),lock() {}
    } working;

    void working_add(const MappedInterval &ival);
    void working_remove(const MappedInterval &ival);
    void working_add(component_id_t comp);
    void working_remove(component_id_t comp);

public:
    const IntervalMap &horizontalIntervals() const { return working.hmap; }
    const IntervalMap &verticalIntervals() const { return working.vmap; }

    struct Greedy {
        int k_x;
        int k_y;
        int k_xy;
        int k_yx;
        data::BitSet result;

        bool valid() const { return k_yx > 0; }

        Result lowerBound() const { return (Result) std::max(k_x, k_y); }
        Result upperBound() const { return (Result) std::min(k_xy, k_yx); }

        Greedy() :  k_x(UNKNOWN),k_y(UNKNOWN), k_xy(UNKNOWN), k_yx(UNKNOWN),
                    result()
        { }
    };

    const struct Greedy &greedyResult() const { return greedy; }

private:
    struct Greedy greedy;

public:
    struct BruteForce {
        /*  Bounds for the BF algorthm.
         *  Initially from the Greedy results; k_min may increase when the BF returns unsucessfully
         */
        int k_min = 0;
        int k_max = 0;
        int k_current;
        int k_iteration;
        int k_optimal;

        data::BitSet result;
        Stack stack1, stack2;

        bool valid() const { return k_optimal > 0; }

        BruteForce() :  k_min(0),k_max(0),
                        k_current(UNKNOWN), k_iteration(UNKNOWN), k_optimal(UNKNOWN),
                        result(), stack1(), stack2()
        { }
    };

    const struct BruteForce &optimalResult() const { return bf; }

private:
    struct BruteForce bf;

    std::pair<int, double> &bf_top1();
    std::pair<int, double> &bf_top2();

    void bf_push1(int i, double x);
    bool bf_pop1();
    void bf_push2(int i, double y);
    bool bf_backtrack2();

    void setupMapsAndResults();

public:
    typedef boost::shared_ptr<kAlgorithm> ptr;

    kAlgorithm(fs::FreeSpace::ptr fs);

    int runGreedy();

    int runBruteForce(volatile bool *cancelFlag = 0) throw(frechet::app::InterruptedException);

private:
    friend class KWorkerJob;

    int greedy_xy();
    int greedy_yx();

    int greedy_12(
            const IntervalMap &map1, const data::Interval &range1,
            const IntervalMap &map2, const data::Interval &range2,
            int &k_1);

    int greedy_1(const IntervalMap &map, const data::Interval &range);
    int greedy_2(const IntervalMap &map, const data::Interval &range);

    bool bf_search_1(volatile bool *cancelFlag = 0) throw(frechet::app::InterruptedException);
    bool bf_search_2() throw(frechet::app::InterruptedException);
};

class KWorkerJob : public frechet::app::WorkerJob {
private:
    kAlgorithm *alg;
public:
    KWorkerJob(kAlgorithm *owner) : alg(owner) {}

    virtual void runJob() {
        alg->runBruteForce(&cancelRequested);
    }

    virtual void afterInterrupted() {
        emit alg->bruteForceFinished();
    }
};

} } //  namespaces

#endif // ALGORITHMBASE_H