'''
    This file is part of PM4Py (More Info: https://pm4py.fit.fraunhofer.de).

    PM4Py is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    PM4Py 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.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with PM4Py.  If not, see <https://www.gnu.org/licenses/>.
'''
from enum import Enum
from typing import Optional, Dict
from typing import Tuple, List, Any

import numpy as np

from pm4py.objects.log.obj import Trace
from pm4py.objects.petri_net.utils import align_utils, petri_utils as petri_utils
from pm4py.objects.petri_net.utils.consumption_matrix import ConsumptionMatrix
from pm4py.objects.petri_net.utils.incidence_matrix import IncidenceMatrix
from pm4py.objects.petri_net.obj import PetriNet, Marking
from pm4py.util import exec_utils, constants, xes_constants, points_subset
from pm4py.util.lp import solver


class Parameters(Enum):
    CASE_ID_KEY = constants.PARAMETER_CONSTANT_CASEID_KEY
    ACTIVITY_KEY = constants.PARAMETER_CONSTANT_ACTIVITY_KEY
    MAX_K_VALUE = "max_k_value"
    COSTS = "costs"
    SPLIT_IDX = "split_idx"
    INCIDENCE_MATRIX = "incidence_matrix"
    A = "A_matrix"
    CONSUMPTION_MATRIX = "consumption_matrix"
    C = "C_matrix"
    FULL_BOOTSTRAP_REQUIRED = "full_bootstrap_required"


"""
Implements the extended marking equation as explained in the following paper:

<NAME>, <NAME>. "Efficiently computing alignments." International Conference on Business Process Management.
<NAME>, 2018.
https://link.springer.com/chapter/10.1007/978-3-319-98648-7_12
"""


class ExtendedMarkingEquationSolver(object):
    def __init__(self, trace: Trace, sync_net: PetriNet, sync_im: Marking, sync_fm: Marking,
                 parameters: Optional[Dict[Any, Any]] = None):
        """
        Constructor

        Parameters
        ---------------
        trace
            Trace
        sync_net
            Synchronous product net
        sync_im
            Initial marking
        sync_fm
            Final marking
        parameters
            Parameters of the algorithm, including:
            - Parameters.CASE_ID_KEY => attribute to use as case identifier
            - Parameters.ACTIVITY_KEY => attribute to use as activity
            - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)
            - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace
                (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").
                If not provided, some split points at uniform distances are found.
            - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes
                if necessary).
            - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net
            - Parameters.A => (if provided) the A numpy matrix of the incidence matrix
            - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net
            - Parameters.C => (if provided) the C numpy matrix of the consumption matrix
            - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted
        """
        if parameters is None:
            parameters = {}

        activity_key = exec_utils.get_param_value(Parameters.ACTIVITY_KEY, parameters, xes_constants.DEFAULT_NAME_KEY)
        max_k_value = exec_utils.get_param_value(Parameters.MAX_K_VALUE, parameters, 5)
        costs = exec_utils.get_param_value(Parameters.COSTS, parameters, None)
        split_idx = exec_utils.get_param_value(Parameters.SPLIT_IDX, parameters, None)
        self.full_bootstrap_required = exec_utils.get_param_value(Parameters.FULL_BOOTSTRAP_REQUIRED, parameters, True)

        self.trace = [x[activity_key] for x in trace]
        if costs is None:
            costs = align_utils.construct_standard_cost_function(sync_net, align_utils.SKIP)
        if split_idx is None:
            split_idx = [i for i in range(1, len(trace))]
        self.split_idx = split_idx
        if len(self.split_idx) > max_k_value:
            self.split_idx = points_subset.pick_chosen_points_list(max_k_value, self.split_idx)
        self.k = len(self.split_idx) if len(self.split_idx) > 1 else 2
        self.sync_net = sync_net
        self.ini = sync_im
        self.fin = sync_fm
        self.costs = costs
        self.incidence_matrix = exec_utils.get_param_value(Parameters.INCIDENCE_MATRIX, parameters,
                                                           IncidenceMatrix(self.sync_net))
        self.consumption_matrix = exec_utils.get_param_value(Parameters.CONSUMPTION_MATRIX, parameters,
                                                             ConsumptionMatrix(self.sync_net))
        self.A = exec_utils.get_param_value(Parameters.A, parameters, np.asmatrix(self.incidence_matrix.a_matrix))
        self.C = exec_utils.get_param_value(Parameters.C, parameters, np.asmatrix(self.consumption_matrix.c_matrix))

        self.__build_entities()

    def __build_entities(self):
        """
        Builds entities useful to define the marking equation
        """
        self.Aeq = None
        self.__build_encodings()
        if self.full_bootstrap_required:
            petri_utils.decorate_transitions_prepostset(self.sync_net)
            petri_utils.decorate_places_preset_trans(self.sync_net)

    def __build_encodings(self):
        """
        Encodes the aforementioned objects in Numpy matrixes
        """
        self.zeros = np.zeros((self.A.shape[0], self.A.shape[1]))
        self.ini_vec = np.matrix(self.incidence_matrix.encode_marking(self.ini)).transpose()
        self.fin_vec = np.matrix(self.incidence_matrix.encode_marking(self.fin)).transpose()
        transitions = self.incidence_matrix.transitions
        self.inv_indices = {y: x for x, y in transitions.items()}
        self.inv_indices = [self.inv_indices[i] for i in range(len(self.inv_indices))]
        self.c = self.__build_cost_vector()
        self.__build_variable_corr()
        self.__build_h_value_cost_vector()
        self.c1 = list(self.c)
        self.__build_non_null_entries_y()

    def __build_cost_vector(self) -> List[int]:
        """
        Builds the complete cost vector of the integer problem
        """
        c1 = [self.costs[self.inv_indices[i]] for i in range(len(self.inv_indices))] * self.k
        c2 = [self.costs[self.inv_indices[i]] for i in range(len(self.inv_indices))] * (self.k - 1)
        c3 = [0 for i in range(len(self.inv_indices))] * (self.k - 1)
        c = c1 + c2 + c3
        return c

    def __build_h_value_cost_vector(self):
        """
        Builds the cost vector for the heuristics calculation as explained in the paper
        """
        self.c0 = list(self.c)
        for idx in self.y[-1]:
            self.c0[idx] = 0

    def __build_variable_corr(self):
        """
        The variables of the LP are split between both "x", "y" and "xy" (which is the sum of x and y)

        Make sure we can reconstruct that!
        """
        count = 0
        self.x = []
        for i in range(self.k):
            self.x.append([])
            for j in range(len(self.inv_indices)):
                self.x[-1].append(count)
                count = count + 1
        self.y = []
        for i in range(self.k - 1):
            self.y.append([])
            for j in range(len(self.inv_indices)):
                self.y[-1].append(count)
                count = count + 1
        self.xy = []
        for i in range(self.k - 1):
            self.xy.append([])
            for j in range(len(self.inv_indices)):
                self.xy[-1].append(count)
                count = count + 1

    def __build_Aeq1(self) -> np.ndarray:
        """
        Builds point (1) of the extended marking equation paper
        """
        Aeq1 = np.hstack([self.A] + (2 * self.k - 2) * [self.zeros] + (self.k - 1) * [self.A])
        return Aeq1

    def __build_Aeq2(self) -> np.ndarray:
        """
        We have some variables xy, that are the sum of x and y.
        Just make sure that xy = x + y
        (not implementing any specific point!)
        """
        Aeq_stack = []
        for i in range(1, len(self.x)):
            Aeq = np.zeros((len(self.x[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.x[i])):
                Aeq[j][self.x[i][j]] = 1
                Aeq[j][self.y[i - 1][j]] = 1
                Aeq[j][self.xy[i - 1][j]] = -1
            Aeq_stack.append(Aeq)
        Aeq = np.vstack(Aeq_stack)
        return Aeq

    def __build_non_null_entries_y(self):
        """
        Utility function that is needed for point (6) of the extended marking equation paper
        """
        self.null_entries = []
        for i in self.split_idx:
            self.null_entries.append([])
            act = self.trace[i]
            for j in range(len(self.inv_indices)):
                if self.inv_indices[j].label[0] == act:
                    self.null_entries[-1].append(j)

    def __build_Aeq3(self) -> np.ndarray:
        """
        Implements point (6) of the extended marking equation paper
        """
        Aeq_stack = []
        for i in range(len(self.y)):
            Aeq = np.zeros((1, self.xy[-1][-1] + 1))
            for j in range(len(self.y[i])):
                Aeq[0][self.y[i][j]] = 1
            Aeq_stack.append(Aeq)
        Aeq = np.vstack(Aeq_stack)
        return Aeq

    def __build_Aeq4(self) -> np.ndarray:
        """
        Implements point (5) of the extended marking equation paper
        """
        Aeq = np.zeros((len(self.null_entries), self.xy[-1][-1] + 1))
        for i in range(min(len(self.null_entries), len(self.y))):
            for j in range(len(self.y[i])):
                if j not in self.null_entries[i]:
                    Aeq[i][self.y[i][j]] = 1
        return Aeq

    def __build_Aub1(self) -> np.ndarray:
        """
        Implements points (3) and (4) of the extended marking equation paper
        """
        Aub_stack = []
        for i in range(len(self.x)):
            Aub = np.zeros((len(self.x[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.x[i])):
                Aub[j][self.x[i][j]] = -1
            Aub_stack.append(Aub)
        for i in range(len(self.y)):
            Aub = np.zeros((len(self.y[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.y[i])):
                Aub[j][self.y[i][j]] = -1
            Aub_stack.append(Aub)
        Aub = np.vstack(Aub_stack)
        return Aub

    def __build_Aub2(self) -> np.ndarray:
        """
        Implements point (2) of the extended marking equation paper
        """
        Aub_stack = []
        for i in range(self.k - 1):
            v = [self.A]
            v = v + (self.k - 1) * [self.zeros]
            for j in range(self.k - 1):
                if j == i:
                    v = v + [self.C]
                else:
                    v = v + [self.zeros]
            for j in range(self.k - 1):
                if j < i:
                    v = v + [self.A]
                else:
                    v = v + [self.zeros]
            Aub = np.hstack(v)
            Aub_stack.append(Aub)
        Aub = np.vstack(Aub_stack)
        Aub = -Aub
        return Aub

    def __build_lin_prog_components(self):
        """
        Builds the components needed to solve the marking equation
        """
        Aeq1 = self.__build_Aeq1()
        Aeq2 = self.__build_Aeq2()
        Aeq3 = self.__build_Aeq3()
        Aeq4 = self.__build_Aeq4()
        self.Aeq = np.vstack([Aeq1, Aeq2, Aeq3, Aeq4])
        Aub1 = self.__build_Aub1()
        Aub2 = self.__build_Aub2()
        self.Aub = np.vstack([Aub1, Aub2])

        if solver.DEFAULT_LP_SOLVER_VARIANT == solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            from cvxopt import matrix

            self.Aeq_transf = matrix(self.Aeq.astype(np.float64))
            self.Aub_transf = matrix(self.Aub.astype(np.float64))
            self.c = matrix([1.0 * x for x in self.c])
        else:
            self.Aeq_transf = self.Aeq
            self.Aub_transf = self.Aub

    def __calculate_vectors(self) -> Tuple[np.ndarray, np.ndarray]:
        """
        Calculates the inequality/equality vector from the knowledge of the
        initial/final marking of the synchronous product net
        """
        beq_stack = []
        bub_stack = []
        beq_stack.append(self.fin_vec - self.ini_vec)
        beq_stack.append(np.zeros(((len(self.x) - 1) * len(self.x[0]), 1)))
        beq_stack.append(np.ones((len(self.y), 1)))
        beq_stack.append(np.zeros((len(self.null_entries), 1)))
        bub_stack.append(np.zeros((len(self.x) * len(self.x[0]), 1)))
        bub_stack.append(np.zeros((len(self.y) * len(self.y[0]), 1)))
        for i in range(self.k - 1):
            bub_stack.append(self.ini_vec)

        beq = np.vstack(beq_stack)
        bub = np.vstack(bub_stack)

        return beq, bub

    def get_components(self) -> Tuple[Any, Any, Any, Any, Any]:
        """
        Retrieve the components (Numpy matrixes) of the problem

        Returns
        ---------------
        c
            objective function
        Aub
           Inequalities matrix
        bub
            Inequalities vector
        Aeq
            Equalities matrix
        beq
            Equalities vector
        """
        if self.Aeq is None:
            self.__build_lin_prog_components()

        self.beq, self.bub = self.__calculate_vectors()

        if solver.DEFAULT_LP_SOLVER_VARIANT == solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            from cvxopt import matrix

            self.beq_transf = matrix(self.beq.astype(np.float64))
            self.bub_transf = matrix(self.bub.astype(np.float64))
        else:
            self.beq_transf = self.beq
            self.bub_transf = self.bub

        return self.c, self.Aub_transf, self.bub_transf, self.Aeq_transf, self.beq_transf

    def change_ini_vec(self, ini: Marking):
        """
        Changes the initial marking of the synchronous product net

        Parameters
        --------------
        ini
            Initial marking
        """
        self.ini = ini
        self.ini_vec = np.matrix(self.incidence_matrix.encode_marking(ini)).transpose()

    def get_x_vector(self, sol_points: List[int]) -> List[int]:
        """
        Returns the x vector of the solution

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        ---------------
        x
            X vector
        """
        x_vector = [0] * len(self.sync_net.transitions)
        for i in range(len(self.x)):
            for j in range(len(self.x[i])):
                x_vector[j] += sol_points[self.x[i][j]]
        for i in range(len(self.y)):
            for j in range(len(self.y[i])):
                x_vector[j] += sol_points[self.y[i][j]]
        return x_vector

    def get_h(self, sol_points: List[int]) -> int:
        """
        Returns the value of the heuristics

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        --------------
        h
            Heuristics value
        """
        h = 0.0
        for i in range(len(sol_points)):
            h += sol_points[i] * self.c1[i]
        return int(h)

    def get_activated_transitions(self, sol_points: List[int]) -> List[PetriNet.Transition]:
        """
        Gets the transitions of the synchronous product net that are non-zero
        in the solution of the marking equation

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        --------------
        act_trans
            Activated transitions
        """
        act_trans = []
        for i in range(len(sol_points)):
            for j in range(sol_points[i]):
                act_trans.append(self.inv_indices[i])
        return act_trans

    def solve(self, variant=None) -> Tuple[int, List[int]]:
        """
        Solves the extended marking equation, returning the heuristics and the x vector

        Parameters
        -------------
        variant
            Variant of the ILP solver to use

        Returns
        -------------
        h
            Heuristics value
        x
            X vector
        """
        if variant is None:
            variant = solver.DEFAULT_LP_SOLVER_VARIANT
        # use ILP solver
        if variant is solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            variant = solver.CVXOPT_SOLVER_CUSTOM_ALIGN_ILP
        c, Aub, bub, Aeq, beq = self.get_components()
        parameters_solver = {}
        parameters_solver["use_ilp"] = True
        sol = solver.apply(c, Aub, bub, Aeq, beq, variant=variant, parameters=parameters_solver)
        sol_points = solver.get_points_from_sol(sol, variant=variant)
        if sol_points is not None:
            x = self.get_x_vector(sol_points)
            x = [int(y) for y in x]
            h = self.get_h(sol_points)
            return h, x
        return None, None

    def get_firing_sequence(self, x: List[int]) -> Tuple[List[PetriNet.Transition], bool, int]:
        """
        Gets a firing sequence from the X vector

        Parameters
        ----------------
        x
            X vector

        Returns
        ----------------
        firing_sequence
            Firing sequence
        reach_fm
            Boolean value that is true whether the firing sequence reaches the final marking
        explained_events
            Number of explaned events by the firing sequence
        """
        activated_transitions = self.get_activated_transitions(x)
        firing_sequence, reach_fm, explained_events = align_utils.search_path_among_sol(self.sync_net, self.ini,
                                                                                        self.fin,
                                                                                        activated_transitions)
        return firing_sequence, reach_fm, explained_events


def build(trace: Trace, sync_net: PetriNet, sync_im: Marking, sync_fm: Marking,
          parameters: Optional[Dict[Any, Any]] = None) -> ExtendedMarkingEquationSolver:
    """
    Builds the extended marking equation out of a trace and a synchronous product net

    Parameters
    ---------------
    trace
        Trace
    sync_net
        Synchronous product net
    sync_im
        Initial marking (of sync net)
    sync_fm
        Final marking (of sync net)
    parameters
        Parameters of the algorithm, including:
        - Parameters.CASE_ID_KEY => attribute to use as case identifier
        - Parameters.ACTIVITY_KEY => attribute to use as activity
        - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)
        - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace
            (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").
            If not provided, some split points at uniform distances are found.
        - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes
            if necessary).
        - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net
        - Parameters.A => (if provided) the A numpy matrix of the incidence matrix
        - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net
        - Parameters.C => (if provided) the C numpy matrix of the consumption matrix
        - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted
    """
    if parameters is None:
        parameters = {}

    return ExtendedMarkingEquationSolver(trace, sync_net, sync_im, sync_fm, parameters=parameters)


def get_h_value(solver: ExtendedMarkingEquationSolver, parameters: Optional[Dict[Any, Any]] = None) -> int:
    """
    Gets the heuristics value from the extended marking equation

    Parameters
    --------------
    solver
        Extended marking equation solver (class in this file)
    parameters
        Possible parameters of the algorithm
    """
    return solver.solve()[0]

'''
    This file is part of PM4Py (More Info: https://pm4py.fit.fraunhofer.de).

    PM4Py is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    PM4Py 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.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with PM4Py.  If not, see <https://www.gnu.org/licenses/>.
'''
from enum import Enum
from typing import Optional, Dict
from typing import Tuple, List, Any

import numpy as np

from pm4py.objects.log.obj import Trace
from pm4py.objects.petri_net.utils import align_utils, petri_utils as petri_utils
from pm4py.objects.petri_net.utils.consumption_matrix import ConsumptionMatrix
from pm4py.objects.petri_net.utils.incidence_matrix import IncidenceMatrix
from pm4py.objects.petri_net.obj import PetriNet, Marking
from pm4py.util import exec_utils, constants, xes_constants, points_subset
from pm4py.util.lp import solver


class Parameters(Enum):
    CASE_ID_KEY = constants.PARAMETER_CONSTANT_CASEID_KEY
    ACTIVITY_KEY = constants.PARAMETER_CONSTANT_ACTIVITY_KEY
    MAX_K_VALUE = "max_k_value"
    COSTS = "costs"
    SPLIT_IDX = "split_idx"
    INCIDENCE_MATRIX = "incidence_matrix"
    A = "A_matrix"
    CONSUMPTION_MATRIX = "consumption_matrix"
    C = "C_matrix"
    FULL_BOOTSTRAP_REQUIRED = "full_bootstrap_required"


"""
Implements the extended marking equation as explained in the following paper:

<NAME>, <NAME>. "Efficiently computing alignments." International Conference on Business Process Management.
<NAME>, 2018.
https://link.springer.com/chapter/10.1007/978-3-319-98648-7_12
"""


class ExtendedMarkingEquationSolver(object):
    def __init__(self, trace: Trace, sync_net: PetriNet, sync_im: Marking, sync_fm: Marking,
                 parameters: Optional[Dict[Any, Any]] = None):
        """
        Constructor

        Parameters
        ---------------
        trace
            Trace
        sync_net
            Synchronous product net
        sync_im
            Initial marking
        sync_fm
            Final marking
        parameters
            Parameters of the algorithm, including:
            - Parameters.CASE_ID_KEY => attribute to use as case identifier
            - Parameters.ACTIVITY_KEY => attribute to use as activity
            - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)
            - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace
                (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").
                If not provided, some split points at uniform distances are found.
            - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes
                if necessary).
            - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net
            - Parameters.A => (if provided) the A numpy matrix of the incidence matrix
            - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net
            - Parameters.C => (if provided) the C numpy matrix of the consumption matrix
            - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted
        """
        if parameters is None:
            parameters = {}

        activity_key = exec_utils.get_param_value(Parameters.ACTIVITY_KEY, parameters, xes_constants.DEFAULT_NAME_KEY)
        max_k_value = exec_utils.get_param_value(Parameters.MAX_K_VALUE, parameters, 5)
        costs = exec_utils.get_param_value(Parameters.COSTS, parameters, None)
        split_idx = exec_utils.get_param_value(Parameters.SPLIT_IDX, parameters, None)
        self.full_bootstrap_required = exec_utils.get_param_value(Parameters.FULL_BOOTSTRAP_REQUIRED, parameters, True)

        self.trace = [x[activity_key] for x in trace]
        if costs is None:
            costs = align_utils.construct_standard_cost_function(sync_net, align_utils.SKIP)
        if split_idx is None:
            split_idx = [i for i in range(1, len(trace))]
        self.split_idx = split_idx
        if len(self.split_idx) > max_k_value:
            self.split_idx = points_subset.pick_chosen_points_list(max_k_value, self.split_idx)
        self.k = len(self.split_idx) if len(self.split_idx) > 1 else 2
        self.sync_net = sync_net
        self.ini = sync_im
        self.fin = sync_fm
        self.costs = costs
        self.incidence_matrix = exec_utils.get_param_value(Parameters.INCIDENCE_MATRIX, parameters,
                                                           IncidenceMatrix(self.sync_net))
        self.consumption_matrix = exec_utils.get_param_value(Parameters.CONSUMPTION_MATRIX, parameters,
                                                             ConsumptionMatrix(self.sync_net))
        self.A = exec_utils.get_param_value(Parameters.A, parameters, np.asmatrix(self.incidence_matrix.a_matrix))
        self.C = exec_utils.get_param_value(Parameters.C, parameters, np.asmatrix(self.consumption_matrix.c_matrix))

        self.__build_entities()

    def __build_entities(self):
        """
        Builds entities useful to define the marking equation
        """
        self.Aeq = None
        self.__build_encodings()
        if self.full_bootstrap_required:
            petri_utils.decorate_transitions_prepostset(self.sync_net)
            petri_utils.decorate_places_preset_trans(self.sync_net)

    def __build_encodings(self):
        """
        Encodes the aforementioned objects in Numpy matrixes
        """
        self.zeros = np.zeros((self.A.shape[0], self.A.shape[1]))
        self.ini_vec = np.matrix(self.incidence_matrix.encode_marking(self.ini)).transpose()
        self.fin_vec = np.matrix(self.incidence_matrix.encode_marking(self.fin)).transpose()
        transitions = self.incidence_matrix.transitions
        self.inv_indices = {y: x for x, y in transitions.items()}
        self.inv_indices = [self.inv_indices[i] for i in range(len(self.inv_indices))]
        self.c = self.__build_cost_vector()
        self.__build_variable_corr()
        self.__build_h_value_cost_vector()
        self.c1 = list(self.c)
        self.__build_non_null_entries_y()

    def __build_cost_vector(self) -> List[int]:
        """
        Builds the complete cost vector of the integer problem
        """
        c1 = [self.costs[self.inv_indices[i]] for i in range(len(self.inv_indices))] * self.k
        c2 = [self.costs[self.inv_indices[i]] for i in range(len(self.inv_indices))] * (self.k - 1)
        c3 = [0 for i in range(len(self.inv_indices))] * (self.k - 1)
        c = c1 + c2 + c3
        return c

    def __build_h_value_cost_vector(self):
        """
        Builds the cost vector for the heuristics calculation as explained in the paper
        """
        self.c0 = list(self.c)
        for idx in self.y[-1]:
            self.c0[idx] = 0

    def __build_variable_corr(self):
        """
        The variables of the LP are split between both "x", "y" and "xy" (which is the sum of x and y)

        Make sure we can reconstruct that!
        """
        count = 0
        self.x = []
        for i in range(self.k):
            self.x.append([])
            for j in range(len(self.inv_indices)):
                self.x[-1].append(count)
                count = count + 1
        self.y = []
        for i in range(self.k - 1):
            self.y.append([])
            for j in range(len(self.inv_indices)):
                self.y[-1].append(count)
                count = count + 1
        self.xy = []
        for i in range(self.k - 1):
            self.xy.append([])
            for j in range(len(self.inv_indices)):
                self.xy[-1].append(count)
                count = count + 1

    def __build_Aeq1(self) -> np.ndarray:
        """
        Builds point (1) of the extended marking equation paper
        """
        Aeq1 = np.hstack([self.A] + (2 * self.k - 2) * [self.zeros] + (self.k - 1) * [self.A])
        return Aeq1

    def __build_Aeq2(self) -> np.ndarray:
        """
        We have some variables xy, that are the sum of x and y.
        Just make sure that xy = x + y
        (not implementing any specific point!)
        """
        Aeq_stack = []
        for i in range(1, len(self.x)):
            Aeq = np.zeros((len(self.x[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.x[i])):
                Aeq[j][self.x[i][j]] = 1
                Aeq[j][self.y[i - 1][j]] = 1
                Aeq[j][self.xy[i - 1][j]] = -1
            Aeq_stack.append(Aeq)
        Aeq = np.vstack(Aeq_stack)
        return Aeq

    def __build_non_null_entries_y(self):
        """
        Utility function that is needed for point (6) of the extended marking equation paper
        """
        self.null_entries = []
        for i in self.split_idx:
            self.null_entries.append([])
            act = self.trace[i]
            for j in range(len(self.inv_indices)):
                if self.inv_indices[j].label[0] == act:
                    self.null_entries[-1].append(j)

    def __build_Aeq3(self) -> np.ndarray:
        """
        Implements point (6) of the extended marking equation paper
        """
        Aeq_stack = []
        for i in range(len(self.y)):
            Aeq = np.zeros((1, self.xy[-1][-1] + 1))
            for j in range(len(self.y[i])):
                Aeq[0][self.y[i][j]] = 1
            Aeq_stack.append(Aeq)
        Aeq = np.vstack(Aeq_stack)
        return Aeq

    def __build_Aeq4(self) -> np.ndarray:
        """
        Implements point (5) of the extended marking equation paper
        """
        Aeq = np.zeros((len(self.null_entries), self.xy[-1][-1] + 1))
        for i in range(min(len(self.null_entries), len(self.y))):
            for j in range(len(self.y[i])):
                if j not in self.null_entries[i]:
                    Aeq[i][self.y[i][j]] = 1
        return Aeq

    def __build_Aub1(self) -> np.ndarray:
        """
        Implements points (3) and (4) of the extended marking equation paper
        """
        Aub_stack = []
        for i in range(len(self.x)):
            Aub = np.zeros((len(self.x[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.x[i])):
                Aub[j][self.x[i][j]] = -1
            Aub_stack.append(Aub)
        for i in range(len(self.y)):
            Aub = np.zeros((len(self.y[i]), self.xy[-1][-1] + 1))
            for j in range(len(self.y[i])):
                Aub[j][self.y[i][j]] = -1
            Aub_stack.append(Aub)
        Aub = np.vstack(Aub_stack)
        return Aub

    def __build_Aub2(self) -> np.ndarray:
        """
        Implements point (2) of the extended marking equation paper
        """
        Aub_stack = []
        for i in range(self.k - 1):
            v = [self.A]
            v = v + (self.k - 1) * [self.zeros]
            for j in range(self.k - 1):
                if j == i:
                    v = v + [self.C]
                else:
                    v = v + [self.zeros]
            for j in range(self.k - 1):
                if j < i:
                    v = v + [self.A]
                else:
                    v = v + [self.zeros]
            Aub = np.hstack(v)
            Aub_stack.append(Aub)
        Aub = np.vstack(Aub_stack)
        Aub = -Aub
        return Aub

    def __build_lin_prog_components(self):
        """
        Builds the components needed to solve the marking equation
        """
        Aeq1 = self.__build_Aeq1()
        Aeq2 = self.__build_Aeq2()
        Aeq3 = self.__build_Aeq3()
        Aeq4 = self.__build_Aeq4()
        self.Aeq = np.vstack([Aeq1, Aeq2, Aeq3, Aeq4])
        Aub1 = self.__build_Aub1()
        Aub2 = self.__build_Aub2()
        self.Aub = np.vstack([Aub1, Aub2])

        if solver.DEFAULT_LP_SOLVER_VARIANT == solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            from cvxopt import matrix

            self.Aeq_transf = matrix(self.Aeq.astype(np.float64))
            self.Aub_transf = matrix(self.Aub.astype(np.float64))
            self.c = matrix([1.0 * x for x in self.c])
        else:
            self.Aeq_transf = self.Aeq
            self.Aub_transf = self.Aub

    def __calculate_vectors(self) -> Tuple[np.ndarray, np.ndarray]:
        """
        Calculates the inequality/equality vector from the knowledge of the
        initial/final marking of the synchronous product net
        """
        beq_stack = []
        bub_stack = []
        beq_stack.append(self.fin_vec - self.ini_vec)
        beq_stack.append(np.zeros(((len(self.x) - 1) * len(self.x[0]), 1)))
        beq_stack.append(np.ones((len(self.y), 1)))
        beq_stack.append(np.zeros((len(self.null_entries), 1)))
        bub_stack.append(np.zeros((len(self.x) * len(self.x[0]), 1)))
        bub_stack.append(np.zeros((len(self.y) * len(self.y[0]), 1)))
        for i in range(self.k - 1):
            bub_stack.append(self.ini_vec)

        beq = np.vstack(beq_stack)
        bub = np.vstack(bub_stack)

        return beq, bub

    def get_components(self) -> Tuple[Any, Any, Any, Any, Any]:
        """
        Retrieve the components (Numpy matrixes) of the problem

        Returns
        ---------------
        c
            objective function
        Aub
           Inequalities matrix
        bub
            Inequalities vector
        Aeq
            Equalities matrix
        beq
            Equalities vector
        """
        if self.Aeq is None:
            self.__build_lin_prog_components()

        self.beq, self.bub = self.__calculate_vectors()

        if solver.DEFAULT_LP_SOLVER_VARIANT == solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            from cvxopt import matrix

            self.beq_transf = matrix(self.beq.astype(np.float64))
            self.bub_transf = matrix(self.bub.astype(np.float64))
        else:
            self.beq_transf = self.beq
            self.bub_transf = self.bub

        return self.c, self.Aub_transf, self.bub_transf, self.Aeq_transf, self.beq_transf

    def change_ini_vec(self, ini: Marking):
        """
        Changes the initial marking of the synchronous product net

        Parameters
        --------------
        ini
            Initial marking
        """
        self.ini = ini
        self.ini_vec = np.matrix(self.incidence_matrix.encode_marking(ini)).transpose()

    def get_x_vector(self, sol_points: List[int]) -> List[int]:
        """
        Returns the x vector of the solution

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        ---------------
        x
            X vector
        """
        x_vector = [0] * len(self.sync_net.transitions)
        for i in range(len(self.x)):
            for j in range(len(self.x[i])):
                x_vector[j] += sol_points[self.x[i][j]]
        for i in range(len(self.y)):
            for j in range(len(self.y[i])):
                x_vector[j] += sol_points[self.y[i][j]]
        return x_vector

    def get_h(self, sol_points: List[int]) -> int:
        """
        Returns the value of the heuristics

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        --------------
        h
            Heuristics value
        """
        h = 0.0
        for i in range(len(sol_points)):
            h += sol_points[i] * self.c1[i]
        return int(h)

    def get_activated_transitions(self, sol_points: List[int]) -> List[PetriNet.Transition]:
        """
        Gets the transitions of the synchronous product net that are non-zero
        in the solution of the marking equation

        Parameters
        --------------
        sol_points
            Solution of the integer problem

        Returns
        --------------
        act_trans
            Activated transitions
        """
        act_trans = []
        for i in range(len(sol_points)):
            for j in range(sol_points[i]):
                act_trans.append(self.inv_indices[i])
        return act_trans

    def solve(self, variant=None) -> Tuple[int, List[int]]:
        """
        Solves the extended marking equation, returning the heuristics and the x vector

        Parameters
        -------------
        variant
            Variant of the ILP solver to use

        Returns
        -------------
        h
            Heuristics value
        x
            X vector
        """
        if variant is None:
            variant = solver.DEFAULT_LP_SOLVER_VARIANT
        # use ILP solver
        if variant is solver.CVXOPT_SOLVER_CUSTOM_ALIGN:
            variant = solver.CVXOPT_SOLVER_CUSTOM_ALIGN_ILP
        c, Aub, bub, Aeq, beq = self.get_components()
        parameters_solver = {}
        parameters_solver["use_ilp"] = True
        sol = solver.apply(c, Aub, bub, Aeq, beq, variant=variant, parameters=parameters_solver)
        sol_points = solver.get_points_from_sol(sol, variant=variant)
        if sol_points is not None:
            x = self.get_x_vector(sol_points)
            x = [int(y) for y in x]
            h = self.get_h(sol_points)
            return h, x
        return None, None

    def get_firing_sequence(self, x: List[int]) -> Tuple[List[PetriNet.Transition], bool, int]:
        """
        Gets a firing sequence from the X vector

        Parameters
        ----------------
        x
            X vector

        Returns
        ----------------
        firing_sequence
            Firing sequence
        reach_fm
            Boolean value that is true whether the firing sequence reaches the final marking
        explained_events
            Number of explaned events by the firing sequence
        """
        activated_transitions = self.get_activated_transitions(x)
        firing_sequence, reach_fm, explained_events = align_utils.search_path_among_sol(self.sync_net, self.ini,
                                                                                        self.fin,
                                                                                        activated_transitions)
        return firing_sequence, reach_fm, explained_events


def build(trace: Trace, sync_net: PetriNet, sync_im: Marking, sync_fm: Marking,
          parameters: Optional[Dict[Any, Any]] = None) -> ExtendedMarkingEquationSolver:
    """
    Builds the extended marking equation out of a trace and a synchronous product net

    Parameters
    ---------------
    trace
        Trace
    sync_net
        Synchronous product net
    sync_im
        Initial marking (of sync net)
    sync_fm
        Final marking (of sync net)
    parameters
        Parameters of the algorithm, including:
        - Parameters.CASE_ID_KEY => attribute to use as case identifier
        - Parameters.ACTIVITY_KEY => attribute to use as activity
        - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)
        - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace
            (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").
            If not provided, some split points at uniform distances are found.
        - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes
            if necessary).
        - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net
        - Parameters.A => (if provided) the A numpy matrix of the incidence matrix
        - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net
        - Parameters.C => (if provided) the C numpy matrix of the consumption matrix
        - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted
    """
    if parameters is None:
        parameters = {}

    return ExtendedMarkingEquationSolver(trace, sync_net, sync_im, sync_fm, parameters=parameters)


def get_h_value(solver: ExtendedMarkingEquationSolver, parameters: Optional[Dict[Any, Any]] = None) -> int:
    """
    Gets the heuristics value from the extended marking equation

    Parameters
    --------------
    solver
        Extended marking equation solver (class in this file)
    parameters
        Possible parameters of the algorithm
    """
    return solver.solve()[0]

This file is part of PM4Py (More Info: https://pm4py.fit.fraunhofer.de).      PM4Py is free software: you can redistribute it and/or modify     it under the terms of the GNU General Public License as published by     the Free Software Foundation, either version 3 of the License, or     (at your option) any later version.      PM4Py 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.  See the     GNU General Public License for more details.      You should have received a copy of the GNU General Public License     along with PM4Py.  If not, see <https://www.gnu.org/licenses/>. Implements the extended marking equation as explained in the following paper:  <NAME>, <NAME>. "Efficiently computing alignments." International Conference on Business Process Management. <NAME>, 2018. https://link.springer.com/chapter/10.1007/978-3-319-98648-7_12 Constructor          Parameters         ---------------         trace             Trace         sync_net             Synchronous product net         sync_im             Initial marking         sync_fm             Final marking         parameters             Parameters of the algorithm, including:             - Parameters.CASE_ID_KEY => attribute to use as case identifier             - Parameters.ACTIVITY_KEY => attribute to use as activity             - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)             - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace                 (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").                 If not provided, some split points at uniform distances are found.             - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes                 if necessary).             - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net             - Parameters.A => (if provided) the A numpy matrix of the incidence matrix             - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net             - Parameters.C => (if provided) the C numpy matrix of the consumption matrix             - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted Builds entities useful to define the marking equation Encodes the aforementioned objects in Numpy matrixes Builds the complete cost vector of the integer problem Builds the cost vector for the heuristics calculation as explained in the paper The variables of the LP are split between both "x", "y" and "xy" (which is the sum of x and y)          Make sure we can reconstruct that! Builds point (1) of the extended marking equation paper We have some variables xy, that are the sum of x and y.         Just make sure that xy = x + y         (not implementing any specific point!) Utility function that is needed for point (6) of the extended marking equation paper Implements point (6) of the extended marking equation paper Implements point (5) of the extended marking equation paper Implements points (3) and (4) of the extended marking equation paper Implements point (2) of the extended marking equation paper Builds the components needed to solve the marking equation Calculates the inequality/equality vector from the knowledge of the         initial/final marking of the synchronous product net Retrieve the components (Numpy matrixes) of the problem          Returns         ---------------         c             objective function         Aub            Inequalities matrix         bub             Inequalities vector         Aeq             Equalities matrix         beq             Equalities vector Changes the initial marking of the synchronous product net          Parameters         --------------         ini             Initial marking Returns the x vector of the solution          Parameters         --------------         sol_points             Solution of the integer problem          Returns         ---------------         x             X vector Returns the value of the heuristics          Parameters         --------------         sol_points             Solution of the integer problem          Returns         --------------         h             Heuristics value Gets the transitions of the synchronous product net that are non-zero         in the solution of the marking equation          Parameters         --------------         sol_points             Solution of the integer problem          Returns         --------------         act_trans             Activated transitions Solves the extended marking equation, returning the heuristics and the x vector          Parameters         -------------         variant             Variant of the ILP solver to use          Returns         -------------         h             Heuristics value         x             X vector # use ILP solver Gets a firing sequence from the X vector          Parameters         ----------------         x             X vector          Returns         ----------------         firing_sequence             Firing sequence         reach_fm             Boolean value that is true whether the firing sequence reaches the final marking         explained_events             Number of explaned events by the firing sequence Builds the extended marking equation out of a trace and a synchronous product net      Parameters     ---------------     trace         Trace     sync_net         Synchronous product net     sync_im         Initial marking (of sync net)     sync_fm         Final marking (of sync net)     parameters         Parameters of the algorithm, including:         - Parameters.CASE_ID_KEY => attribute to use as case identifier         - Parameters.ACTIVITY_KEY => attribute to use as activity         - Parameters.COSTS => (if provided) the cost function (otherwise the default cost function is applied)         - Parameters.SPLIT_IDX => (if provided) the split points as indices of elements of the trace             (e.g. for ["A", "B", "C", "D", "E"], specifying [1,3] as split points means splitting at "B" and "D").             If not provided, some split points at uniform distances are found.         - Parameters.MAX_K_VALUE => the maximum number of split points that is allowed (trim the specified indexes             if necessary).         - Parameters.INCIDENCE_MATRIX => (if provided) the incidence matrix associated to the sync product net         - Parameters.A => (if provided) the A numpy matrix of the incidence matrix         - Parameters.CONSUMPTION_MATRIX => (if provided) the consumption matrix associated to the sync product net         - Parameters.C => (if provided) the C numpy matrix of the consumption matrix         - Parameters.FULL_BOOTSTRAP_REQUIRED => The preset/postset of places/transitions need to be inserted Gets the heuristics value from the extended marking equation      Parameters     --------------     solver         Extended marking equation solver (class in this file)     parameters         Possible parameters of the algorithm