graph_model.h

Go to the documentation of this file.

#ifndef GRAPH_MODEL_H
#define GRAPH_MODEL_H

#include <boundary.h>
#include <freespace.h>
#include <boost/container/map.hpp>

namespace frechet { namespace reach {

using namespace data;
using namespace fs;

struct IndexRange {
    Orientation ori;
    int lower;
    int upper;

    IndexRange();
    IndexRange(Orientation ori, int l, int u);

    bool empty() const;
    void clear();
    int len() const;

    bool contains(int i) const;
    bool contains(const IndexRange& that) const;
    bool operator==(const IndexRange& that) const;
    bool operator!=(const IndexRange& that) const;

    IndexRange operator+ (const IndexRange& b) const;
    IndexRange operator+ (int offset) const;
    IndexRange operator- (int offset) const;

    IndexRange operator& (const IndexRange& b) const;
    IndexRange& operator+= (const IndexRange& b);
    IndexRange& operator-= (int offset);

    IndexRange& operator&= (const IndexRange& b);

    bool intersects(const IndexRange& b) const;
};



struct Placement
{
    Interval fs;
    double w;
    IndexRange gn;
};

typedef std::vector<frechet::reach::Placement> Placements;

enum Bias: uint8_t {
    UNBIASED=0, 
    LOWER=1,    
    UPPER=2,    
    LOWER_UPPER=3   
};

Bias operator| (Bias a, Bias b);
Bias& operator|= (Bias& a, Bias b);

struct BoundsIndex {
    int index;
    Bias bias;
    BoundsIndex(int i, Bias b) : index(i),bias(b) {}
    BoundsIndex operator+ (int offset) const {
        return BoundsIndex(index+offset,bias);
    }
};

class GraphModelAxis {
private:
    typedef boost::container::map<double,BoundsIndex> Map;
    Map map;
    int _max_index;
    int _dim;

    friend class GraphModel;

public:
    GraphModelAxis();

    void insert1(double x, Bias bias);
    void insert2(double x, Bias bias);

    const BoundsIndex& lookup(double x) const;
    const BoundsIndex* lookupLowerEqual(double x) const;
    const BoundsIndex* lookupLarger(double x) const;

    void createReverseMap(std::vector<Interval>& result) const;

private:
    void remove(double x);
    void indexify(int start);
};

class GraphModel {

private:
    GraphModelAxis axis[2];
    std::vector<Interval> reversed[2];

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

    GraphModel() : axis{GraphModelAxis(),GraphModelAxis()} {}

    void init(const FreeSpace::ptr fs);
    bool empty() const;

    int dim1(Orientation ori) const;
    int dim2(Orientation ori) const;

    int lowerShiftedHorizontally(int hindex) const {
        double x = reversed[HORIZONTAL][hindex].lower();
        double offset = dim1(HORIZONTAL);
        return map_lower(HORIZONTAL,x+offset);
    }

    IndexRange shiftedHorizontally(const IndexRange& r) const {
        Q_ASSERT(r.ori==HORIZONTAL);
        return IndexRange(HORIZONTAL,
                          lowerShiftedHorizontally(r.lower),
                          lowerShiftedHorizontally(r.upper));
    }
    int count2(Orientation ori) const;
    int count2() const;

    IndexRange map(Orientation ori, const Interval&,
                    bool upperBoundInclusive) const;

    IndexRange map(Pointer b) const;

    int map_lower(Pointer p) const;
    int map_upper(Pointer p) const;

    int map_lower(Orientation ori, double x) const;
    int map_upper(Orientation ori, double x, bool inclusive) const;

    IndexRange mapClosest(Orientation ori, const Interval& ival) const;

    const std::vector<Interval>& reverseMap(Orientation ori) const {
        return reversed[ori];
    }

    IndexRange mergedHMask(const IndexRange& m1, const IndexRange& m2) const;

private:
    void initVertical(const FreeSpace::ptr fs);
    void initHorizontal(const FreeSpace::ptr fs);
};

} }     //  namespace frechet::reach

#endif // GRAPH_MODEL_H