nearalign.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_NEARALIGN_H
#define DIALECT_NEARALIGN_H

#include <vector>
#include <memory>

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

namespace dialect {

enum class AlignmentFlag {
    NONE = 0,
    HALIGN = 1,
    VALIGN = 2,
    HINFEAS = 4,
    VINFEAS = 8
};

inline AlignmentFlag operator&(AlignmentFlag a, AlignmentFlag b)
{return static_cast<AlignmentFlag>(static_cast<int>(a) & static_cast<int>(b));}

inline AlignmentFlag& operator|= (AlignmentFlag& a, AlignmentFlag b) { return (AlignmentFlag&)((int&)a |= (int)b); }

struct AlignmentTable {

    AlignmentTable(Graph &graph, const Nodes &ignore);

    AlignmentTable(Graph &graph, const NodesById &ignore);

    bool areAligned(id_type uid, id_type vid, AlignmentFlag flag);

    void addAlignment(id_type uid, id_type vid, AlignmentFlag flag);

    void addAlignments(const NodesById &nodes, const SepMatrix &matrix);

    std::vector<id_type> getAlignedIds(id_type uid, AlignmentFlag flag);

    void noteInfeasibility(id_type uid, id_type vid, AlignmentFlag flag);

    bool isMarkedInfeasible(id_type uid, id_type vid, AlignmentFlag flag);

    SparseIdMatrix2d<AlignmentFlag>::type state;
};


double manhattan(Node_SP u, Node_SP v);


struct PotentialAlignment {

    PotentialAlignment(Node_SP u, Node_SP v, AlignmentFlag flag)
        : u(u),
          v(v),
          flag(flag),
          cost(manhattan(u, v)) {}

    void remove(void);

    void addToTable(AlignmentTable &table) { table.addAlignment(u->id(), v->id(), flag); }

    void noteInfeasibility(AlignmentTable &table) { table.noteInfeasibility(u->id(), v->id(), flag); }

    SepCo_SP writeSepCo(void);

    void addToGraph(Graph &G);

    Node_SP u;
    Node_SP v;
    AlignmentFlag flag;
    double cost;
    // For managing linked list:
    bool removed = false;
    PotentialAlignment *prev = nullptr;
    PotentialAlignment *next = nullptr;
};

typedef std::vector<PotentialAlignment*> PotentialAlignments;

size_t doNearAlignments(dialect::Graph &graph, dialect::AlignmentTable &atab, dialect::NodesById &ignore, const dialect::HolaOpts &opts, bool reattempt=false);



} // namespace dialect

#endif // DIALECT_NEARALIGN_H