constraints.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libdialect - A library for computing DiAlEcT layouts:
 *                 D = Decompose/Distribute
 *                 A = Arrange
 *                 E = Expand/Emend
 *                 T = Transform
 *
 * Copyright (C) 2018  Monash University
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * See the file LICENSE.LGPL distributed with the library.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author(s):   Steve Kieffer   <http://skieffer.info>
*/

#ifndef DIALECT_CONSTRAINTS_H
#define DIALECT_CONSTRAINTS_H

#include <map>
#include <set>
#include <string>
#include <vector>
#include <utility>
#include <memory>

#include "libvpsc/rectangle.h"
#include "libcola/compound_constraints.h"

#include "libdialect/commontypes.h"
#include "libdialect/ortho.h"

namespace dialect {

class Graph;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// SepMatrices

enum class GapType {
    CENTRE,
    BDRY
};

enum class SepDir {
    EAST, SOUTH, WEST, NORTH,
    RIGHT, DOWN, LEFT, UP
};

enum class SepType {
    NONE,
    EQ,
    INEQ
};

SepDir negateSepDir(SepDir sd);

bool sepDirIsCardinal(SepDir sd);

CardinalDir sepDirToCardinalDir(SepDir sd);

SepDir cardinalDirToSepDir(CardinalDir dir);

SepDir lateralWeakening(SepDir sd);

SepDir cardinalStrengthening(SepDir sd);

enum class SepTransform {
    ROTATE90CW,
    ROTATE90ACW,
    ROTATE180,
    FLIPV,
    FLIPH,
    FLIPMD,
    FLIPOD
};

class SepMatrix;

struct SepPair {
    SepPair(void) : src(0), tgt(0), xgt(GapType::CENTRE), ygt(GapType::CENTRE), xst(SepType::NONE), yst(SepType::NONE), xgap(0.0), ygap(0.0) {}

    id_type src;
    id_type tgt;
    GapType xgt;
    GapType ygt;
    SepType xst;
    SepType yst;
    double xgap;
    double ygap;

    unsigned tglfPrecision = 3;

    bool flippedRetrieval = false;

    void addSep(GapType gt, SepDir sd, SepType st, double gap);
    void transform(SepTransform tf);
    bool isVerticalCardinal(void) const;
    bool isHorizontalCardinal(void) const;
    bool isVAlign(void) const;
    bool isHAlign(void) const;
    bool isCardinal(void) const;
    CardinalDir getCardinalDir(void) const;
    void roundGapsUpAbs(void);
    std::string writeTglf(std::map<id_type, unsigned> id2ext, const SepMatrix &m) const;
    bool hasConstraintInDim(vpsc::Dim dim) const;
    vpsc::Constraint *generateSeparationConstraint(const vpsc::Dim dim, const ColaGraphRep &cgr, SepMatrix *m, vpsc::Variables &vs);
};

struct SepPairSubConstraintInfo : public cola::SubConstraintInfo {
    SepPairSubConstraintInfo(SepPair_SP sp, vpsc::Dim dim) : cola::SubConstraintInfo(0), sp(sp), dim(dim) {}
    SepPair_SP sp = nullptr;
    vpsc::Dim dim;
};


static const unsigned int PRIORITY_SEPMATRIX = cola::DEFAULT_CONSTRAINT_PRIORITY;

class SepMatrix : public cola::CompoundConstraint {
public:
    SepMatrix(Graph *G) : cola::CompoundConstraint(vpsc::UNSET, PRIORITY_SEPMATRIX), m_graph(G) {
        _combineSubConstraints = true;
    }
    SepMatrix(void) = delete;
    SepMatrix(const SepMatrix &m) = default;
    ~SepMatrix(void) = default;
    void addSep(id_type id1, id_type id2, GapType gt, SepDir sd, SepType st, double gap);

    void setCardinalOP(id_type id1, id_type id2, dialect::CardinalDir dir) {
        addSep(id1, id2, GapType::BDRY, (SepDir) dir, SepType::INEQ, 0.0);
    }

    void addFixedRelativeSep(id_type id1, id_type id2, double dx, double dy);

    void addFixedRelativeSep(id_type id1, id_type id2);

    void hAlign(id_type id1, id_type id2) { addSep(id1, id2, GapType::CENTRE, SepDir::DOWN, SepType::EQ, 0); }

    void vAlign(id_type id1, id_type id2) { addSep(id1, id2, GapType::CENTRE, SepDir::RIGHT, SepType::EQ, 0); }

    void alignByEquatedCoord(id_type id1, id_type id2, vpsc::Dim eqCoord);

    void free(id_type id1, id_type id2);

    void clear(void) { m_sparseLookup.clear(); }

    void setCorrespondingConstraints(SepMatrix &matrix) const;

    void setSepPair(id_type id1, id_type id2, SepPair_SP sp);

    void transform(SepTransform tf);
    void transformClosedSubset(SepTransform tf, const std::set<id_type> &ids);
    void transformOpenSubset(SepTransform tf, const std::set<id_type> &ids);
    void removeNode(id_type id);
    void removeNodes(const NodesById &nodes);
    CardinalDir getCardinalDir(id_type id1, id_type id2) const;
    void getAlignedSets(std::map<id_type, std::set<id_type>> &hSets,
                        std::map<id_type, std::set<id_type>> &vSets) const;
    bool areHAligned(id_type id1, id_type id2) const;
    bool areVAligned(id_type id1, id_type id2) const;
    std::string writeTglf(std::map<id_type, unsigned> id2ext) const;
    void setGraph(Graph *G) { m_graph = G; }
    Graph *getGraph(void) { return m_graph; }
    void roundGapsUpward(void);
    void setExtraBdryGap(double extraBdryGap) { m_extraBdryGap = extraBdryGap; }
    double getExtraBdryGap(void) const { return m_extraBdryGap; }


    void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
    void generateSeparationConstraints(const vpsc::Dim dim,
            vpsc::Variables& vs, vpsc::Constraints& cs,
            vpsc::Rectangles& bbs);
    std::string toString(void) const;
    void markAllSubConstraintsAsInactive(void);
    cola::SubConstraintAlternatives getCurrSubConstraintAlternatives(vpsc::Variables vs[]);

private:

    double m_extraBdryGap = 0.0;

    SepPair_SP &getSepPair(id_type id1, id_type id2);

    SepPair_SP checkSepPair(id_type id1, id_type id2) const;

    Graph *m_graph;

    SparseIdMatrix2d<SepPair_SP>::type m_sparseLookup;
};


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// SepCos, Projections, ProjSeqs


struct SepCo {

    SepCo(vpsc::Dim dim, Node_SP left, Node_SP right, double gap, bool exact=false)
        : dim(dim), left(left), right(right), gap(gap), exact(exact) {}

    void generateColaConstraints(const ColaGraphRep &cgr, cola::CompoundConstraints &ccs);

    CardinalDir getDirecRelativeToNode(Node_SP baseNode) const;

    void addToMatrix(SepMatrix &matrix) const;

    double violation(void) const;

    std::string toString(void) const;

    vpsc::Dim dim;
    Node_SP left;
    Node_SP right;
    double gap;
    bool exact;
};

typedef std::shared_ptr<SepCo> SepCo_SP;
typedef std::set<SepCo_SP> SepCoSet;
typedef std::vector<SepCoSet> SepCoSets;

struct Projection{

    Projection(SepCoSet s, vpsc::Dim d) : sepCoSet(s), dim(d) {}

    size_t size(void) { return sepCoSet.size(); }

    cola::CompoundConstraints generateColaConstraints(const ColaGraphRep &cgr);

    std::string toString(void) const;

    SepCoSet sepCoSet;
    vpsc::Dim dim;
};
typedef std::shared_ptr<Projection> Projection_SP;
typedef std::vector<Projection_SP> Projections;

class ProjSeq {
public:

    ProjSeq(void) {
        // Initialize an empty final set in each dimension.
        m_finalSets[vpsc::XDIM];
        m_finalSets[vpsc::YDIM];
    }

    void addProjection(SepCoSet sepCos, vpsc::Dim dim);

    Projection_SP nextProjection(void);

    void noteStresschange(double dS) { m_dSes.push_back(dS); }

    std::string toString(void) const;

    ProjSeq &operator+=(const ProjSeq &rhs);

    SepCoSet getAllConstraints(void) const;

    void reset(void) { m_ptr = 0; }

    double violation(void) const;

private:
    Projections m_projections;
    std::vector<double> m_dSes;
    size_t m_ptr = 0;
    std::map<vpsc::Dim, SepCoSet> m_finalSets;
};

} // namespace dialect

// Global Operators
dialect::ProjSeq operator+(const dialect::ProjSeq &lhs, const dialect::ProjSeq &rhs);

#endif // DIALECT_CONSTRAINTS_H