faces.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_FACES_H
#define DIALECT_FACES_H

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

#include "libvpsc/rectangle.h"

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

namespace dialect {

class Side {
public:

    Side(Nodes nodeSeq, CardinalDir direc);

    Nodes getNodeSeq(void) const { return m_nodeSeq; }

    bool containsNode(id_type id) const;

    size_t findNodeIndex(id_type id) const;

    CardinalDir getForwardDirec(void) const;

    vpsc::Dim getAlignmentDimension(void) const { return m_vardim; }

    Node_SP firstNode(void) const;

    Node_SP lastNode(void) const;

    std::string toString(void) const;

    double getCentreCoord(void) const;

    size_t getNumRootNodes(void) const;

    void addTreePlacement(TreePlacement_SP tp);

    ProjSeq_SP computeCollateralProjSeq(TreePlacement_SP tp, double padding=0);

    interval closedInterval(void) const;

    interval getIntervalOppositeSegment(LineSegment &seg, bool openInterval=false) const;

    bool liesOppositeSegment(LineSegment &seg, bool openInterval=false) const;

    Avoid::Point getFirstPtOppositeSegment(LineSegment &seg) const;

    double halfWidthOppositeSegment(LineSegment &seg) const;

    const std::set<TreePlacement_SP> &getTreePlacements(void) const { return m_treePlacements; }

private:

    Nodes m_nodeSeq;
    CardinalDir m_forward;
    CardinalDir m_inward;
    vpsc::Dim m_vardim;
    vpsc::Dim m_constdim;
    std::set<TreePlacement_SP> m_treePlacements;

};

enum class NexusPolarity {
    ENTER_FROM,
    EXIT_TO
};

class Nexus {
public:

    Nexus(Node_SP u) : m_node(u), m_slots(8) {}

    void addSide(Side_SP side);

    std::set<Side_SP> getNeighboursOfADirection(CompassDir direc);

    std::string toString(void) const;

private:

    void writeSlot(CardinalDir direc, NexusPolarity polarity, Side_SP side);

    static const std::map<CompassDir, size_t> DIREC_TO_INITIAL_SEARCH_INDEX;

    Node_SP m_node;
    std::vector<Side_SP> m_slots;
    bool m_isEmpty = true;
};

class FaceSet {
public:
    FaceSet(Graph_SP &G);

    size_t getNumFaces(void) { return m_faces.size(); }

    TreePlacements listAllPossibleTreePlacements(Tree_SP tree, dialect::HolaOpts opts);

    TreePlacements getAllTreePlacements(void);

    Faces getFaces(void) { return m_faces; }

    Face_SP getExternalFace(void) { return m_externalFace; }

    std::map<CardinalDir, size_t> getNumTreesByGrowthDir(bool scaleBySize=false) const;

private:

    void computeFaces(void);
    void identifyExternalFace(void);

    Graph_SP m_graph;
    Faces m_faces;
    Face_SP m_externalFace;
    std::map<id_type, std::set<Face_SP>> m_facesByMemberNodeId;
    std::map<id_type, std::set<id_type>> m_hSets;
    std::map<id_type, std::set<id_type>> m_vSets;
};


class Face {
    friend class FaceSet;
public:
    Face(Graph_SP &G) : m_ID(nextID++), m_graph(G) {}

    void initWithEdgeSeq(const std::vector<IdPair> &edges);

    Nodes getNodeSeq(void) { return m_nodeSeq; }

    Sides getSides(void) { return m_sides; }

    NexesById getNexusLookup(void) { return m_nexesByNodeIds; }

    bool containsNodeIdSeq(std::vector<id_type> idSeq) const;

    Graph_SP getGraph(void) { return m_graph; }

    id_type id(void) const { return m_ID; }

    bool isExternal(void) const { return m_isExternal; }

    std::string toString(void) const;

    std::map<id_type, std::vector<std::pair<Node_SP, Node_SP>>> getNbrPairs(void) {return m_nbrPairs;}

    Sides getRelevantSidesForPlacement(TreePlacement_SP tp) const;

    void listAllPossibleTreePlacements(TreePlacements &tps, Tree_SP tree, Node_SP root, HolaOpts opts);

    CompassDirs inwardDirsAvailable(Node_SP node);

    void insertTreeNode(TreePlacement_SP tp, double padding=0);

    ProjSeq_SP computeCollateralProjSeq(TreePlacement_SP tp, double padding=0);

    bool applyProjSeq(ProjSeq &ps);

    ProjSeq_SP doCollateralExpansion(TreePlacement_SP tp, double padding=-1);

    void buildBdrySegsFacingOneDir(CardinalDir facingDir,
                                   LineSegments &closedSegs, LineSegments &openSegs,
                                   TreePlacement_SP ignoreTP = nullptr);

    ProjSeq_SP buildBestProjSeq(TreePlacement_SP tp, double padding=0,
                                bool doCostlierDimensionFirst=false,
                                ExpansionEstimateMethod estimateMethod=ExpansionEstimateMethod::CONSTRAINTS);

    Sides getAllSidesOppositeSegment(LineSegment &seg, bool openInterval=false) const;

    TreePlacements getAllTreePlacements(void) const;

    std::set<TreePlacement_SP> getSetOfAllTreePlacements(void) const;

    void getAllTreePlacements(TreePlacements &tps) const;

    void getNumTreesByGrowthDir(std::map<CardinalDir, size_t> &counts, bool scaleBySize=false) const;

private:

    void computeNbrPairs(void);
    void computeSides(void);
    void buildNexes(void);

    size_t findIndexOfFirstBend(void);

    CardinalDir direc(const Node_SP &u, const Node_SP &v);

    static id_type nextID;
    const id_type m_ID;

    Graph_SP m_graph;
    Nodes m_nodeSeq;
    size_t m_n;
    bool m_isExternal = false;
    std::map<id_type, std::vector<std::pair<Node_SP, Node_SP>>> m_nbrPairs;
    Sides m_sides;
    NexesById m_nexesByNodeIds;
    NodesById m_treeNodes;
    std::map<id_type, TreePlacement_SP> m_treePlacementsByNodeIds;

};


} // namespace dialect

#endif // DIALECT_FACES_H