//#####################################################################
// Copyright 2012.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYREGHT.txt.
//#####################################################################
#include <Core/Symbolics/DOMINATORS.h>
#include <Core/Arrays/ARRAY.h>
#include <Core/Data_Structures/HASHTABLE.h>
using namespace PhysBAM;
namespace PhysBAM{
//#####################################################################
// Function DFS
//#####################################################################
void DOMINATORS::
DFS(const ARRAY<ARRAY<I>,I>& out,ARRAY<I,I>& semi,I v)
{
    semi(v)=vertex.Append(v);
    for(int i=0;i<out(v).m;i++)
        if(semi(out(v)(i))==I{-1}){
            parent(out(v)(i))=v;
            DFS(out,semi,out(v)(i));}
}
//#####################################################################
// Function Compress
//#####################################################################
void DOMINATORS::
Compress(const ARRAY<I,I>& semi,ARRAY<I,I>& ancestor,ARRAY<I,I>& label,I v)
{
    if(ancestor(ancestor(v))!=I{-1}){
        Compress(semi,ancestor,label,ancestor(v));
        if(semi(label(ancestor(v)))<semi(label(v)))
            label(v)=label(ancestor(v));
        ancestor(v)=ancestor(ancestor(v));}
}
//#####################################################################
// Function Eval
//#####################################################################
MEM_LABEL DOMINATORS::
Eval(const ARRAY<I,I>& semi,ARRAY<I,I>& ancestor,ARRAY<I,I>& label,I v)
{
    if(ancestor(v)==I{-1}) return v;
    Compress(semi,ancestor,label,v);
    return label(v);
}
//#####################################################################
// Function Compute_Idom
//#####################################################################
void DOMINATORS::
Compute_Idom()
{
    ARRAY<I,I> ancestor(in.m),label(in.m);
    Set_Counting(label);
    ARRAY<I,I> semi(in.m);
    ARRAY<HASHTABLE<I>,I> bucket(in.m);
    idom.Resize(in.m);
    idom.Fill(I{-1});
    semi.Fill(I{-1});
    ancestor.Fill(I{-1});
    parent.Resize(in.m);

    DFS(out,semi,{});
    parent({})=I{-1};

    for(I i=vertex.m-1;i>=I{1};i--){
        I w=vertex(i);
        for(int j=0;j<in(w).m;j++){
            I u=Eval(semi,ancestor,label,in(w)(j));
            if(semi(u)<semi(w)) semi(w)=semi(u);}
        bucket(vertex(semi(w))).Set(w);
        Link(ancestor,parent(w),w);
        for(auto i:bucket(parent(w))){
            I u=Eval(semi,ancestor,label,i);
            idom(i)=(semi(u)<semi(i))?u:parent(w);}
        bucket(parent(w)).Remove_All();}

    for(I i{1};i<vertex.m;i++){
        I w=vertex(i);
        if(idom(w)!=vertex(semi(w)))
            idom(w)=idom(idom(w));}
    idom(vertex({}))=I{-1};

    children.Resize(out.m);
    for(I i{1};i<out.m;i++)
        children(parent(i)).Append(i);
}
//#####################################################################
// Function Compute_Frontier
//#####################################################################
void DOMINATORS::
Compute_Frontier()
{
    if(!parent.m) Compute_Idom();

    frontier.Resize(out.m);
    for(I i=vertex.m-1;i>=I{};i--){
        HASHTABLE<I> hash;
        I x=vertex(i);
        for(int j=0;j<out(x).m;j++){
            I y=out(x)(j);
            if(idom(y)!=x)
                hash.Set(y);}
        for(int j=0;j<children(x).m;j++){
            I z=children(x)(j);
            for(int k=0;k<frontier(z).m;k++){
                I y=frontier(z)(k);
                if(idom(y)!=x)
                    hash.Set(y);}}
        hash.Get_Keys(frontier(x));}
}
}
