//#####################################################################
// Copyright 2021, Jason Goulding, Craig Schroeder, Tamar Shinar.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class DEPTH_FIRST_SEARCH
//#####################################################################
#ifndef __DEPTH_FIRST_SEARCH__
#define __DEPTH_FIRST_SEARCH__

#include <Core/Arrays/ARRAY.h>
#include <Core/Log/DEBUG_UTILITIES.h>
namespace PhysBAM{

class DEPTH_FIRST_SEARCH
{
    ARRAY<int> todo;
    ARRAY<char> visit_list;
public:
    
    DEPTH_FIRST_SEARCH(int size)
        :visit_list(size)
    {}

    void Reset(int size)
    {
        todo.Remove_All();
        visit_list.Resize(size,init_all,0);
    }
    
    void Add_Neighbor(int i)
    {
        if(!visit_list(i))
        {
            todo.Append(i);
            visit_list(i)=1;
        }
    }

    // void enter_node(int entry);
    //   Called once per entry in depth-first search order
    //   Calls Add_Neighbor on all neighbors of entry.
    // void exit_node(int entry);
    //   Called once per exit while backtracking
    // void component();
    //   Called after each connected component.
    template<class A,class B,class C>
    void Traverse(const A& enter_node,const B& exit_node,const C& component)
    {
        for(int i=0;i<visit_list.m;i++)
            if(!visit_list(i))
            {
                todo.Append(i);
                visit_list(i)=1;
                while(todo.m)
                {
                    int k=todo.Last();
                    if(visit_list(k)==1)
                    {
                        visit_list(k)=2;
                        enter_node(k);
                    }
                    else
                    {
                        exit_node(k);
                        todo.Pop();
                    }
                }
                component();
            }
    }
//#####################################################################
};
}
#endif
