structure.h

Go to the documentation of this file.

#ifndef STRUCTURE_H
#define STRUCTURE_H

#include <boundary.h>
#include <freespace.h>
#include <tbb/tbb.h>

namespace frechet {
using namespace fs;

namespace reach {

class StructureIterator;

class Structure {

private:    
    const FreeSpace::ptr fs;
    BoundaryList _boundary[2][2];
    int concurrency;
    volatile bool* cancelFlag;

    friend class StructureIterator;
    friend class GraphModel;
    friend class CalculateTask;
    friend class MergeTask;
public:
    typedef boost::shared_ptr<Structure> ptr;

    Structure(int concurrency=1, volatile bool* cancelFlag=nullptr);
    Structure(const FreeSpace::ptr fs, int concurrency=1, volatile bool* cancelFlag=nullptr);

    Structure(const Structure& that);
    Structure(Structure&& that);

    Structure& operator= (const Structure& that);
    Structure& operator= (Structure&& that);

    void copy(const Structure& that);
    void swap(Structure& that);
    virtual ~Structure();

    const FreeSpace::ptr freeSpace() const { return fs; }

    BoundaryList& boundary(Orientation ori, Direction dir) {
        return _boundary[ori][dir];
    }

    const BoundaryList& boundary(Orientation ori, Direction dir) const {
        return _boundary[ori][dir];
    }
    BoundaryList& first(Orientation ori)    { return _boundary[ori][FIRST]; }
    BoundaryList& second(Orientation ori)   { return _boundary[ori][SECOND]; }

    const BoundaryList& first(Orientation ori) const    { return _boundary[ori][FIRST]; }
    const BoundaryList& second(Orientation ori) const   { return _boundary[ori][SECOND]; }

    BoundaryList& horizontal(Direction dir) { return _boundary[HORIZONTAL][dir]; }
    BoundaryList& vertical(Direction dir) { return _boundary[VERTICAL][dir]; }

    BoundaryList& left()        { return _boundary[VERTICAL][FIRST]; }
    BoundaryList& right()       { return _boundary[VERTICAL][SECOND]; }
    BoundaryList& bottom()      { return _boundary[HORIZONTAL][FIRST]; }
    BoundaryList& top()         { return _boundary[HORIZONTAL][SECOND]; }

    const BoundaryList& left() const       { return _boundary[VERTICAL][FIRST]; }
    const BoundaryList& right() const      { return _boundary[VERTICAL][SECOND]; }
    const BoundaryList& bottom() const     { return _boundary[HORIZONTAL][FIRST]; }
    const BoundaryList& top() const        { return _boundary[HORIZONTAL][SECOND]; }

    Pointer calculate();

    Pointer calculateDouble();

    Pointer calculateSingle();

    void calculateColumns(int i, int j);

    //
    void singleCell(int i, int j);

    void calculateDouble(Orientation fringe);

    Pointer findStartingPoint(Orientation edge);

    void shift(Point offset);

    Pointer next(Pointer p) const;
    Pointer prev(Pointer p) const;
    void synchIntervals(Orientation fringe, Structure& that);

private:
    Pointer prevReachable(Pointer p);
    Pointer nextReachable(Pointer p);

    void calcRecursive(const Rect& r);
    void doCalcRecursive(const Rect& r);

    //  Structure Merging
    void merge(Orientation fringe, Structure& that,
               const Rect& r1, const Rect& r2);
    //  buildings blocks of the merge process:
    Pointer split(Pointer seg, double y, Pointer twin);
    void split2(Pointer& a, double x, Pointer& b);
    void crossLink(Pointer i1, Pointer i2, Pointer j1, Pointer j2);
    void merge(BoundaryList& list, Pointer a, Pointer b);
    void mergeConsecutive(Orientation ori);
    void scanAndMerge (Pointer K, Orientation fringe);
    void markNonAccesible(Orientation fringe, Structure& that);
    void markNonAccesible(Pointer p, Pointer p2);
    void updatePointers(Pointer K, Pointer l, Pointer h, Pointer K1);


    struct SingleCellAuxData {
        data::Interval F[2][2];           //  [Orientation][Direction]
        int arr[2];                 //  [Orientation]
        Pointer seg[2][2][5];       //  [Orientation][Direction][0..4]
        PointerInterval P[2][2];    //  [Orientation][Direction]
    };

public:
    static int freeSpaceArrangement(data::Interval LF, data::Interval RF);
private:
    static int freeSpaceArrangement(SingleCellAuxData& aux, Orientation ori);
    void createSingleCellSegments(SingleCellAuxData& aux, Orientation ori, double y0);
    void linkSingleCellSegments(SingleCellAuxData& aux, Orientation ori);
    void clipSeeThroughPointer(Pointer p);
    PointerInterval reachableInterval(Pointer seg[5]);
    void create2Segments(Pointer& first, Pointer& second, data::Interval ival, Orientation ori, Type t1, Type t2);
    void copySegments(BoundaryList& list, Pointer seg[5]);
    void testCancelFlag();

    static bool assertSynchedIntervals(Pointer i1, Pointer i2, Pointer i3, Pointer i4);

public:
    static bool assertPointerInterval(Pointer p, const PointerInterval& ival);

    typedef void (*assert_hook) (
            Structure*, const Rect*,
            Structure*, const Rect*,
            Orientation);

    static assert_hook after_single_cell, before_merge, after_merge;
    void takeOwnership();
};

class StructureIterator
{
private:
    const Structure& str;
    Pointer current;
    Pointer last;

public:
    StructureIterator(const Structure& str, Pointer first, Pointer last);
    StructureIterator(const Structure& str,
                      const PointerInterval& ival, Pointer ifnull=nullptr);

    operator bool() const { return current; }
    bool operator!() const { return !current; }

    explicit operator Pointer() { return current; }
    BoundarySegment& operator *() { return *current; }
    BoundarySegment* operator ->() { return current; }
    StructureIterator& operator++();
};

class StructureTask
{
public:
    StructureTask(Structure* owner);
    virtual ~StructureTask();

    virtual void start()=0;
    static StructureTask* createTask(Structure* owner, const frechet::Rect& r, tbb::flow::graph& graph, int concurrency);

    typedef tbb::flow::continue_msg msg_t;
    typedef tbb::flow::continue_node<msg_t> node_t;

    Structure* owner;
    node_t* node;
};

class CalculateTask: public StructureTask {
public:
    CalculateTask(Structure* owner, frechet::Rect r, tbb::flow::graph& graph);
    virtual void start() override;
};

class MergeTask: public StructureTask {
private:
    Structure buddy;
    StructureTask *child1;
    StructureTask *child2;
public:
    MergeTask(Structure* owner, frechet::Rect r, tbb::flow::graph& graph, int concurrency);
    virtual ~MergeTask();
    virtual void start() override;
};

std::ostream& operator<< (std::ostream& out, const Structure& str);

} }     //  namespace frechet::reach
#endif // STRUCTURE_H