//#####################################################################
// Copyright 2022, Jason Goulding, Craig Schroeder
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
#include <Core/Arrays/FLOOD_FILL.h>
namespace PhysBAM {
template<int d,class IV> int
Flood_Fill(const RANGE<IV>& domain,AT_CELLS,
    ARRAY<int,IV>& colors,
    const VECTOR<ARRAY_VIEW<bool,IV>,IV::m>* edge_is_blocked,
    ARRAY<int>* color_flags,VECTOR<bool,d> periodic_axis,
    ARRAY<VECTOR<int,2> >* region_boundaries)
{
    PHYSBAM_ASSERT(colors.domain.Thickened(-1).Intersect(domain)==domain);
    for(int side=0;side<2*IV::m;side++)
    {
        int value=periodic_axis(side/2)?-3:-4;
        for(RANGE_ITERATOR<IV::m> it(domain,1,0,RI::ghost,side);it.Valid();it.Next())
            colors(it.index)=value;
    }
    
    int fill_color=0;
    if(color_flags) color_flags->Remove_All();
    
    ARRAY<IV> flood_fill_stack;
    for(RANGE_ITERATOR<IV::m> it(domain);it.Valid();it.Next())
    {
        if(colors(it.index)!=-1) continue;
        
        int flags=0;
        
        flood_fill_stack.Append(it.index);
        while(flood_fill_stack.Size())
        {
            IV node=flood_fill_stack.Pop_Value();
            int* p_color=&colors(node);
            int color=*p_color;
            if(color>=0) continue;
            else if(color!=-1)
            {
                if(color==-2)
                {
                    flags|=FLOOD_FILL::uncolorable_flag;
                    continue;
                }
                else if(color==-4)
                {
                    flags|=FLOOD_FILL::uncolorable_flag|FLOOD_FILL::boundary_flag;
                    continue;
                }
                else if(color==-3)
                {
                    node=wrap(node,domain.min_corner,domain.max_corner);
                    p_color=&colors(node);
                    if(*p_color>=0) continue;
                }
            }

            *p_color=fill_color;

            for(int a=0;a<IV::m;a++)
            {
                IV node0(node),node1(node);
                node0(a)--;
                node1(a)++;
                if(!edge_is_blocked || !(*edge_is_blocked)(a)(node)) flood_fill_stack.Append(node0);
                if(!edge_is_blocked || !(*edge_is_blocked)(a)(node1)) flood_fill_stack.Append(node1);
            }
        }
        
        if(color_flags) color_flags->Append(flags);
        
        fill_color++;
    }
    return fill_color;
}

//#####################################################################
// Flood_Fill (1D)
//#####################################################################
template<> int
Flood_Fill(const RANGE<VECTOR<int,1> >& domain,AT_CELLS,
    ARRAY<int,VECTOR<int,1> >& colors,
    const VECTOR<ARRAY_VIEW<bool,VECTOR<int,1> >,1>* edge_is_blocked,
    ARRAY<int>* color_flags,VECTOR<bool,1> periodic_axis,
    ARRAY<VECTOR<int,2> >* region_boundaries)
{
    PHYSBAM_ASSERT(colors.domain.Thickened(-1).Intersect(domain)==domain);
    if(periodic_axis(0)) colors(colors.domain.min_corner)=colors(colors.domain.max_corner-1)=-3;
    else colors(colors.domain.min_corner)=colors(colors.domain.max_corner-1)=-4;    

    if(color_flags) color_flags->Remove_All();
    if(region_boundaries) region_boundaries->Remove_All();
    
    int fill_color=0;    
    int flags=0;
    for(int i=domain.min_corner.x;i<domain.max_corner.x;i++)
    {
        int* p_color=&colors(i);
        int color=*p_color;
        int color_next=colors(i+1);
        int color_prev=colors(i-1);
        
        if(color==-2) continue;
        if(edge_is_blocked && (*edge_is_blocked)(0)(VECTOR<int,1>(i)))
        {
            if(region_boundaries) region_boundaries->Append(VECTOR<int,2>(i,i));
        }
        else if(color_prev==-2)
        {
            flags|=FLOOD_FILL::uncolorable_flag;
            if(region_boundaries) region_boundaries->Append(VECTOR<int,2>(i,i));
        }
        else if(color_prev==-4)
        {
            flags|=FLOOD_FILL::uncolorable_flag|FLOOD_FILL::boundary_flag;
            if(region_boundaries) region_boundaries->Append(VECTOR<int,2>(i,i));
        }

        *p_color=fill_color;
        
        if(edge_is_blocked && (*edge_is_blocked)(0)(VECTOR<int,1>(i+1)))
        {
            if(region_boundaries) (*region_boundaries)(fill_color).y=i;
            fill_color++;
            if(color_flags) color_flags->Append(flags);
            flags=0;
        }
        else if(color_next==-2)
        {
            if(region_boundaries) (*region_boundaries)(fill_color).y=i;
            fill_color++;
            flags|=FLOOD_FILL::uncolorable_flag;
            if(color_flags) color_flags->Append(flags);
            flags=0;
        }
        else if(color_next==-4)
        {
            if(region_boundaries) (*region_boundaries)(fill_color).y=i;
            fill_color++;
            flags|=FLOOD_FILL::uncolorable_flag|FLOOD_FILL::boundary_flag;
            if(color_flags) color_flags->Append(flags);
            flags=0;
        }
    }
    if(periodic_axis(0) && (!edge_is_blocked || !(*edge_is_blocked)(0)(domain.min_corner)) && fill_color>1)
    {
        for(int i=domain.max_corner.x-1;colors(i)==fill_color;i--)
            colors(i)=0;
    }
    
    return fill_color;
}
template int Flood_Fill(const RANGE<VECTOR<int,2> >&,AT_CELLS,ARRAY<int,VECTOR<int,2> >&,const VECTOR<ARRAY_VIEW<bool,VECTOR<int,2> >,2>*,ARRAY<int>*,VECTOR<bool,2>,ARRAY<VECTOR<int,2> >*);
template int Flood_Fill(const RANGE<VECTOR<int,3> >&,AT_CELLS,ARRAY<int,VECTOR<int,3> >&,const VECTOR<ARRAY_VIEW<bool,VECTOR<int,3> >,3>*,ARRAY<int>*,VECTOR<bool,3>,ARRAY<VECTOR<int,2> >*);
}
