//#####################################################################
// Copyright 2012.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYREGHT.txt.
//#####################################################################
// Class DOMINATORS
//#####################################################################
#ifndef __DOMINATORS__
#define __DOMINATORS__

#include <Core/Arrays/ARRAY.h>
#include <Core/Symbolics/INSTRUCTION.h>
namespace PhysBAM{
struct DOMINATORS
{
    typedef MEM_LABEL I;
    const ARRAY<ARRAY<I>,I> &in,&out;
    ARRAY<I,I> idom,vertex,parent;
    ARRAY<ARRAY<I>,I> frontier;
    ARRAY<ARRAY<I>,I> children;

    DOMINATORS(const ARRAY<ARRAY<I>,I>& in,const ARRAY<ARRAY<I>,I>& out)
        :in(in),out(out)
    {}

    void Compute_Idom();
    void Compute_Frontier();

protected:
    void DFS(const ARRAY<ARRAY<I>,I>& out,ARRAY<I,I>& semi,I v);
    void Link(ARRAY<I,I>& ancestor,I u,I w) {ancestor(w)=u;}
    I Eval(const ARRAY<I,I>& semi,ARRAY<I,I>& ancestor,ARRAY<I,I>& label,I v);
    void Compress(const ARRAY<I,I>& semi,ARRAY<I,I>& ancestor,ARRAY<I,I>& label,I v);
};
}
#endif
