/* 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 Eina_Graph_BFS *
_eina_graph_bfs_allocate(_Eina_Graph *_g, unsigned int s)
{
   _Eina_Graph_BFS *_bfs;

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

   _bfs->data = calloc(_g->vertices, sizeof(_Eina_Graph_BFS_Data));
   if (!_bfs->data)
     goto error_data;

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

   return (Eina_Graph_BFS *) _bfs;

error_data:
   free(_bfs);
error_bfs:
   ERR("calloc failed : %s", strerror(errno));
   return NULL;
}

static void
_eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs,
                     unsigned int s, unsigned int d)
{
   Eina_Bool has_target = (s != d);
   Eina_List *fifo = NULL;
   Eina_Array *adjs;
   _Eina_Graph_BFS_Data *vd;
   unsigned int p, w, n, i, dst;

   dst = 0;
   vd = &_bfs->data[s];
   vd->m = EINA_TRUE;
   vd->e = s;
   vd->d = dst;
   fifo = eina_list_append(fifo, CAST_V(s));

   while (eina_list_count(fifo) > 0)
     {
        dst++;
        p = w = CAST_D(eina_list_data_get(fifo));
        fifo = eina_list_remove(fifo, CAST_V(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);
             vd = &_bfs->data[w];
             if (!vd->m)
               {
                  vd->m = EINA_TRUE;
                  vd->e = p;
                  vd->d = dst;
                  if (has_target && (d == w))
                    {
                       eina_list_free(fifo);
                       return;
                    }
                  fifo = eina_list_append(fifo, CAST_V(w));
               }
          }
     }

   eina_list_free(fifo);
}

EAPI Eina_List *
eina_graph_bfs_shortest_path_get(Eina_Graph *g, unsigned int s, unsigned int d)
{
   Eina_List *path;
   Eina_Graph_BFS *bfs;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   bfs = _eina_graph_bfs_allocate(_g, s);
   if (!bfs) return NULL;

   _eina_graph_bfs_walk(_g, (_Eina_Graph_BFS *)bfs, s, d);
   path = eina_graph_bfs_path_get(bfs, d);

   eina_graph_bfs_free(bfs);

   return path;
}


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 = _eina_graph_bfs_allocate(_g, s);
   if (!bfs) return NULL;

   _eina_graph_bfs_walk(_g, (_Eina_Graph_BFS *)bfs, s, s);

   return bfs;
}

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

   free(_bfs->data);
   free(_bfs);
}

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

   return _bfs->s;
}

EAPI Eina_Bool
eina_graph_bfs_path_exists(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->data[v].m;
}

EAPI Eina_List *
eina_graph_bfs_path_get(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->data[v].m)
     return NULL;

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

   return path;
}

EAPI unsigned int
eina_graph_bfs_dist_get(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->data[v].d;
}