/* EINA_GRAPH - EFL graph processing library
 * Copyright (C) 2013 Jérémy Zurcher
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies of the Software and its Copyright notices. In addition publicly
 * documented acknowledgment must be given that this software has been used if no
 * source code of this software is made available publicly. This includes
 * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
 * documents or any documentation provided with any product containing this
 * software. This License does not apply to any software that links to the
 * libraries provided by this software (statically or dynamically), but only to
 * the software provided.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif /* HAVE_CONFIG_H */

#include <eina_graph_dfs.h>
#include "eina_graph_private.h"

static void
_eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
{
   Eina_List *stack = NULL;
   Eina_Graph_Adjacents *adjs;
   unsigned int p, w, n, i;

   p = v;
   stack = eina_list_prepend(stack, CAST_V(v));

   while (eina_list_count(stack) > 0)
     {
        w = CAST_D(eina_list_data_get(stack));
        stack = eina_list_remove(stack, CAST_V(w));

        if(_dfs->marked[w]) continue;
        _dfs->marked[w] = EINA_TRUE;
        _dfs->edge_to[w] = p;
        p = w;

        adjs = &_g->adjs[w];
        n = adjs->count;
        for (i = 0; i < n; i++)
          {
             w =  adjs->data[i];
             if (!_dfs->marked[w])
               {
                  stack = eina_list_prepend(stack, CAST_V(w));
               }
          }
     }
}

static void
_eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
{
   Eina_Graph_Adjacents *adjs;
   unsigned int i, n, w;

   _dfs->marked[v] = EINA_TRUE;

   adjs = &_g->adjs[v];
   n = adjs->count;
   for (i = 0; i < n; i++)
     {
        w =  adjs->data[i];
        if (!_dfs->marked[w])
          {
             _eina_graph_dfs_rwalk(_g, _dfs, w);
             _dfs->edge_to[w] = v;
          }
     }
}

EAPI Eina_Graph_DFS *
eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r)
{
   _Eina_Graph_DFS *_dfs;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   _dfs = calloc(1, sizeof(_Eina_Graph_DFS));
   if (!_dfs)
     goto error_dfs;

   _dfs->marked = calloc(_g->vertices, sizeof(Eina_Bool));
   if (!_dfs->marked)
     goto error_marked;

   _dfs->edge_to = calloc(_g->vertices, sizeof(unsigned int));
   if (!_dfs->edge_to)
     goto error_edge_to;

   _dfs->s = s;
   _dfs->vertices = _g->vertices;

   if (r)
     _eina_graph_dfs_rwalk(_g, _dfs, s);
   else
     _eina_graph_dfs_swalk(_g, _dfs, s);

   return (Eina_Graph_DFS *) _dfs;

error_edge_to:
   free(_dfs->marked);
error_marked:
   free(_dfs);
error_dfs:
   ERR("calloc failed : %s", strerror(errno));
   return NULL;
}

EAPI void
eina_graph_dfs_free(Eina_Graph_DFS *dfs)
{
   _Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;

   free(_dfs->marked);
   free(_dfs->edge_to);
   free(_dfs);
}

EAPI unsigned int
eina_graph_dfs_source(Eina_Graph_DFS *dfs)
{
   _Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;

   return _dfs->s;
}

EAPI Eina_Bool
eina_graph_dfs_has_path_to(Eina_Graph_DFS *dfs, unsigned int v)
{
   _Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;

   if (v >= _dfs->vertices)
     {
        ERR("%u is out of [0;%u[", v, _dfs->vertices);
        return EINA_FALSE;
     }

   return _dfs->marked[v];
}

EAPI Eina_List *
eina_graph_dfs_path_to(Eina_Graph_DFS *dfs, unsigned int v)
{
   unsigned int w = v;
   Eina_List *path = NULL;
   _Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;

   if (v >= _dfs->vertices)
     {
        ERR("%u is out of [0;%u[", v, _dfs->vertices);
        return NULL;
     }

   if (!_dfs->marked[v])
     return NULL;

   while (w != _dfs->s)
     {
        path = eina_list_prepend(path, CAST_V(w));
        w = _dfs->edge_to[w];
     }
   path = eina_list_prepend(path, CAST_V(_dfs->s));

   return path;
}