cc_nonoverlapconstraints.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libcola - A library providing force-directed network layout using the 
 *           stress-majorization method subject to separation constraints.
 *
 * Copyright (C) 2010-2014  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):  Michael Wybrow
 *
*/

#ifndef COLA_CC_NONOVERLAPCONSTRAINTS_H
#define COLA_CC_NONOVERLAPCONSTRAINTS_H

#include <vector>

#include "libcola/cola.h"
#include "libcola/compound_constraints.h"
#include "libcola/shapepair.h"

namespace vpsc {
class Rectangle;
}

namespace cola {

class Cluster;

class OverlapShapeOffsets : public SubConstraintInfo
{
    public:
        OverlapShapeOffsets(unsigned ind, double xOffset, double yOffset,
                unsigned int group)
            : SubConstraintInfo(ind),
              cluster(nullptr),
              rectPadding(0),
              group(group)
        {
            halfDim[0] = xOffset;
            halfDim[1] = yOffset;
        }
        OverlapShapeOffsets(unsigned ind, Cluster *cluster, unsigned int group)
            : SubConstraintInfo(ind),
              cluster(cluster),
              rectPadding(cluster->margin()),
              group(group)
        {
            halfDim[0] = 0;
            halfDim[1] = 0;
        }
        OverlapShapeOffsets()
            : SubConstraintInfo(1000000),
              cluster(nullptr),
              rectPadding(0)
        {
        }
        bool usesClusterBounds(void) const
        {
            return (cluster && !cluster->clusterIsFromFixedRectangle());
        }
        void resize(double xOffset, double yOffset)
        {
            halfDim[0] = xOffset;
            halfDim[1] = yOffset;
        }
        Cluster *cluster;
        double halfDim[2];   // Half width and height values.
        Box rectPadding;  // Used for cluster padding.
        unsigned int group;
};


class ShapePairInfo
{
    public:
        ShapePairInfo(unsigned ind1, unsigned ind2, unsigned ord = 1)
            : order(ord),
              satisfied(false),
              processed(false)
        {
            COLA_ASSERT(ind1 != ind2);
            // Assign the lesser value to varIndex1.
            varIndex1 = (ind1 < ind2) ? ind1 : ind2;
            // Assign the greater value to varIndex2.
            varIndex2 = (ind1 > ind2) ? ind1 : ind2;
        }
        bool operator<(const ShapePairInfo& rhs) const
        {
            // Make sure the processed ones are at the end after sorting.
            int processedInt = processed ? 1 : 0;
            int rhsProcessedInt = rhs.processed ? 1 : 0;
            if (processedInt != rhsProcessedInt)
            {
                return processedInt < rhsProcessedInt;
            }
            // Use cluster ordering for primary sorting.
            if (order != rhs.order)
            {
                return order < rhs.order;
            }
            return overlapMax > rhs.overlapMax;
        }
        unsigned short order;
        unsigned short varIndex1;
        unsigned short varIndex2;
        bool satisfied;
        bool processed;
        double overlapMax;
};


// Stores IDs of all rectangles exempt from non-overlap constraints.
class NonOverlapConstraintExemptions {
    public:
        NonOverlapConstraintExemptions();
        void addExemptGroupOfNodes(ListOfNodeIndexes listOfNodeGroups);
        bool shapePairIsExempt(ShapePair shapePair) const;
        std::set<ShapePair> getExemptPairs(void) {return m_exempt_pairs;}

    private:
        std::set<ShapePair> m_exempt_pairs;
};

// Non-overlap constraints prevent a set of given shapes from overlapping.
class NonOverlapConstraints : public CompoundConstraint {
    public:
        NonOverlapConstraints(NonOverlapConstraintExemptions *exemptions,
                unsigned int priority = PRIORITY_NONOVERLAP);
        void addShape(unsigned id, double halfW, double halfH, 
                unsigned int group = 1, std::set<unsigned> exemptions = std::set<unsigned>());
        void resizeShape(unsigned id, double halfW, double halfH);
        void removeShape(unsigned id);
        void addCluster(Cluster *cluster, unsigned int group);
        void computeAndSortOverlap(vpsc::Variables vs[]);
        void markCurrSubConstraintAsActive(const bool satisfiable);
        void markAllSubConstraintsAsInactive(void);
        bool subConstraintsRemaining(void) const;
        SubConstraintAlternatives getCurrSubConstraintAlternatives(
                vpsc::Variables vs[]);
        std::string toString(void) const;
        void setClusterClusterExemptions(std::set<ShapePair> exemptions);

        void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& gcs);
        void generateSeparationConstraints(const vpsc::Dim dim, 
                vpsc::Variables& vars, vpsc::Constraints& gcs,
                std::vector<vpsc::Rectangle*>& boundingBoxes);

    private:
        void computeOverlapForShapePairInfo(ShapePairInfo& info,
                vpsc::Variables vs[]);
        
        std::list<ShapePairInfo> pairInfoList;
        std::map<unsigned, OverlapShapeOffsets> shapeOffsets;
        bool pairInfoListSorted;
        bool initialSortCompleted;

        // Cluster variables
        size_t clusterVarStartIndex;
        size_t currClusterIndex;
        size_t clusterMode;

        NonOverlapConstraintExemptions *m_exemptions;
        std::set<ShapePair> m_cluster_cluster_exemptions;
};

} // namespace cola
#endif // COLA_CC_NONOVERLAPCONSTRAINTS