/* 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_bfs.h>
#include "eina_graph_private.h"

static void
_eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
{
   Eina_List *fifo = NULL;
   _Eina_Graph_Adjacents *adjs;
   unsigned int p, w, n, i, d;

   d = 0;
   _bfs->marked[v] = EINA_TRUE;
   _bfs->edge_to[v] = v;
   _bfs->dist_to[v] = d;
   fifo = eina_list_append(fifo, CAST_V(v));

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

        p = w;
        d++;

        adjs = &_g->adjs[w];
        n = adjs->count;
        for (i = 0; i < n; i++)
          {
             w =  adjs->data[i];
             if (!_bfs->marked[w])
               {
                  _bfs->marked[w] = EINA_TRUE;
                  _bfs->edge_to[w] = p;
                  _bfs->dist_to[w] = d;
                  fifo = eina_list_append(fifo, CAST_V(w));
               }
          }
     }
}

EAPI Eina_Graph_BFS *
eina_graph_bfs_new(Eina_Graph *g, unsigned int s)
{
   _Eina_Graph_BFS *_bfs;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   _bfs = calloc(1, sizeof(_Eina_Graph_BFS));
   if (!_bfs)
     goto error_bfs;

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

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

   _bfs->dist_to = calloc(_g->vertices, sizeof(unsigned int));
   if (!_bfs->dist_to)
     goto error_dist_to;

   _bfs->s = s;
   _bfs->vertices = _g->vertices;

   _eina_graph_bfs_fwalk(_g, _bfs, s);

   return (Eina_Graph_BFS *) _bfs;

error_dist_to:
   free(_bfs->edge_to);
error_edge_to:
   free(_bfs->marked);
error_marked:
   free(_bfs);
error_bfs:
   ERR("calloc failed : %s", strerror(errno));
   return NULL;
}

EAPI void
eina_graph_bfs_free(Eina_Graph_BFS *bfs)
{
   _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;

   free(_bfs->marked);
   free(_bfs->edge_to);
   free(_bfs->dist_to);
   free(_bfs);
}

EAPI unsigned int
eina_graph_bfs_source(Eina_Graph_BFS *bfs)
{
   _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;

   return _bfs->s;
}

EAPI Eina_Bool
eina_graph_bfs_has_path_to(Eina_Graph_BFS *bfs, unsigned int v)
{
   _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;

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

   return _bfs->marked[v];
}

EAPI Eina_List *
eina_graph_bfs_path_to(Eina_Graph_BFS *bfs, unsigned int v)
{
   unsigned int w = v;
   Eina_List *path = NULL;
   _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;

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

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

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

   return path;
}

EAPI unsigned int
eina_graph_bfs_dist_to(Eina_Graph_BFS *bfs, unsigned int v)
{
   _Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;

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

   return _bfs->dist_to[v];
}