/* 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, unsigned int step)
{
   Eina_Array *stack = NULL;
   Eina_Array *adjs;
   _Eina_Graph_DFS_Data *vd;
   unsigned int p, w, n, i;

   p = v;
   stack = eina_array_new(step);
   eina_array_push_uint(stack, v);

   while (eina_array_count_get(stack) > 0)
     {
        w = eina_array_top_uint_get(stack);
        eina_array_pop(stack);

        vd = &_dfs->data[w];
        if(vd->m) continue;
        vd->m = EINA_TRUE;
        vd->e = p;
        p = w;

        adjs = _g->adjs[w];
        n = eina_array_count_get(adjs);
        for (i = 0; i < n; i++)
          {
             w = eina_array_uint_nth_get(adjs, i);
             if (!_dfs->data[w].m)
               eina_array_push_uint(stack, w);
          }
     }

   eina_array_free(stack);
}

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

   _dfs->data[v].m = EINA_TRUE;

   adjs = _g->adjs[v];
   n = eina_array_count_get(adjs);
   for (i = 0; i < n; i++)
     {
        w = eina_array_uint_nth_get(adjs, i);
        vd = &_dfs->data[w];
        if (!vd->m)
          {
             _eina_graph_dfs_rwalk(_g, _dfs, w);
             vd->e = 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->data = calloc(_g->vertices, sizeof(_Eina_Graph_DFS_Data));
   if (!_dfs->data)
     goto error_data;

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

   if (r)
     _eina_graph_dfs_rwalk(_g, _dfs, s);
   else
     _eina_graph_dfs_swalk(_g, _dfs, s, eina_graph_degree_max(g) * 2);

   return (Eina_Graph_DFS *) _dfs;

error_data:
   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->data);
   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->data[v].m;
}

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->data[v].m)
     return NULL;

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

   return path;
}