/* This file is part of GEGL

 *

 * GEGL is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 3 of the License, or (at your option) any later version.

 *

 * GEGL is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with GEGL; if not, see <http://www.gnu.org/licenses/>.

 *

 * Copyright 2003 Calvin Williamson

 */

#include "config.h"

#include <glib-object.h>

#include "gegl-types-internal.h"

#include "gegl.h"

#include "graph/gegl-node.h"

#include "graph/gegl-pad.h"

#include "gegl-visitor.h"

#include "gegl-visitable.h"

typedef struct _GeglVisitInfo GeglVisitInfo;

struct _GeglVisitInfo

{

  gboolean visited;

  gboolean discovered;

  gint     shared_count;

};

enum

{

  PROP_0,

  PROP_ID

};

static void           gegl_visitor_class_init  (GeglVisitorClass *klass);

static void           gegl_visitor_init        (GeglVisitor      *self);

static void           finalize                 (GObject          *gobject);

static void           init_dfs_traversal       (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           dfs_traverse             (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           init_bfs_traversal       (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           visit_info_destroy       (GeglVisitInfo    *visit_info);

static void           insert                   (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static GeglVisitInfo* lookup                   (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static gboolean       get_visited              (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           set_visited              (GeglVisitor      *self,

                                                GeglVisitable    *visitable,

                                                gboolean          visited);

static gboolean       get_discovered           (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           set_discovered           (GeglVisitor      *self,

                                                GeglVisitable    *visitable,

                                                gboolean          discovered);

static gint           get_shared_count         (GeglVisitor      *self,

                                                GeglVisitable    *visitable);

static void           set_shared_count         (GeglVisitor      *self,

                                                GeglVisitable    *visitable,

                                                gint              shared_count);

static void           visit_pad                (GeglVisitor      *self,

                                                GeglPad          *pad);

static void           visit_node               (GeglVisitor      *self,

                                                GeglNode         *node);

static void           set_property             (GObject          *gobject,

                                                guint             prop_id,

                                                const GValue     *value,

                                                GParamSpec       *pspec);

static void           get_property             (GObject          *gobject,

                                                guint             prop_id,

                                                GValue           *value,

                                                GParamSpec       *pspec);

G_DEFINE_TYPE (GeglVisitor, gegl_visitor, G_TYPE_OBJECT)

static void

gegl_visitor_class_init (GeglVisitorClass *klass)

{

  GObjectClass *gobject_class = G_OBJECT_CLASS (klass);

  gobject_class->finalize = finalize;

  klass->visit_pad            = visit_pad;

  klass->visit_node           = visit_node;

  gobject_class->set_property = set_property;

  gobject_class->get_property = get_property;

  g_object_class_install_property (gobject_class, PROP_ID,

                                   g_param_spec_pointer ("id",

                                                         "evaluation-id",

                                                         "The identifier for the evaluation context",

                                                         G_PARAM_CONSTRUCT |

                                                         G_PARAM_READWRITE));

}

static void

set_property (GObject      *gobject,

              guint         property_id,

              const GValue *value,

              GParamSpec   *pspec)

{

  GeglVisitor *self = GEGL_VISITOR (gobject);

  switch (property_id)

    {

      case PROP_ID:

        self->context_id = g_value_get_pointer (value);

        break;

      default:

        G_OBJECT_WARN_INVALID_PROPERTY_ID (gobject, property_id, pspec);

        break;

    }

}

static void

get_property (GObject    *gobject,

              guint       property_id,

              GValue     *value,

              GParamSpec *pspec)

{

  GeglVisitor *self = GEGL_VISITOR (gobject);

  switch (property_id)

    {

      case PROP_ID:

        g_value_set_pointer (value, self->context_id);

        break;

      default:

        G_OBJECT_WARN_INVALID_PROPERTY_ID (gobject, property_id, pspec);

        break;

    }

}

static void

gegl_visitor_init (GeglVisitor *self)

{

  self->visits_list = NULL;

  self->hash = g_hash_table_new_full (g_direct_hash, g_direct_equal,

                                      NULL,

                                      (GDestroyNotify) visit_info_destroy);

}

static void

finalize (GObject *gobject)

{

  GeglVisitor *self = GEGL_VISITOR (gobject);

  g_slist_free (self->visits_list);

  g_hash_table_destroy (self->hash);

  G_OBJECT_CLASS (gegl_visitor_parent_class)->finalize (gobject);

}

static GeglVisitInfo *

lookup (GeglVisitor   *self,

        GeglVisitable *visitable)

{

  return g_hash_table_lookup (self->hash, visitable);

}

/* resets the object's data (list of visits and visitable statuses) */

void gegl_visitor_reset (GeglVisitor   *self)

{

  if (self->visits_list)

    {

      g_slist_free (self->visits_list);

      self->visits_list = NULL;

    }

  g_hash_table_remove_all (self->hash);

}

/* Inserts the visitable into the object's hash table of visitables with the

 * object as a key and a new GeglVisitInfo (zero initialised) as object

 */

static void

insert (GeglVisitor   *self,

        GeglVisitable *visitable)

{

  if (lookup (self, visitable))

    {

      g_warning ("visitable already in visitor's hash table");

    }

  else

    {

      g_hash_table_insert (self->hash, visitable, g_slice_new0 (GeglVisitInfo));

    }

}

/* Returns TRUE if a GeglVisitable has already been visited */

static gboolean

get_visited (GeglVisitor   *self,

             GeglVisitable *visitable)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  return visit_info->visited;

}

static void

set_visited (GeglVisitor   *self,

             GeglVisitable *visitable,

             gboolean       visited)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  visit_info->visited = visited;

}

static gboolean

get_discovered (GeglVisitor   *self,

                GeglVisitable *visitable)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  return visit_info->discovered;

}

static void

set_discovered (GeglVisitor   *self,

                GeglVisitable *visitable,

                gboolean       discovered)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  visit_info->discovered = discovered;

}

static gint

get_shared_count (GeglVisitor   *self,

                  GeglVisitable *visitable)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  return visit_info->shared_count;

}

static void

set_shared_count (GeglVisitor   *self,

                  GeglVisitable *visitable,

                  gint           shared_count)

{

  GeglVisitInfo *visit_info = lookup (self, visitable);

  g_assert (visit_info);

  visit_info->shared_count = shared_count;

}

/**

 * gegl_visitor_get_visits_list

 * @self: a #GeglVisitor.

 *

 * Gets a list of the visitables the visitor has visited so far.

 *

 * Returns: A list of the visitables visited by this visitor.

 **/

GSList *

gegl_visitor_get_visits_list (GeglVisitor *self)

{

  g_return_val_if_fail (GEGL_IS_VISITOR (self), NULL);

  return self->visits_list;

}

static void

visit_info_destroy (GeglVisitInfo *visit_info)

{

  g_slice_free (GeglVisitInfo, visit_info);

}

/**

 * gegl_visitor_dfs_traverse:

 * @self: #GeglVisitor

 * @visitable: the start #GeglVisitable

 *

 * Traverse depth first starting at @visitable.

 **/

void

gegl_visitor_dfs_traverse (GeglVisitor   *self,

                           GeglVisitable *visitable)

{

  /* sets up the structures that keeps track of the */

  init_dfs_traversal (self, visitable);

  dfs_traverse (self, visitable);

}

/* Recursively (depth first) sets up the structure (hash) that keeps track of

 * if a visitable's status

 */

static void

init_dfs_traversal (GeglVisitor   *self,

                    GeglVisitable *visitable)

{

  GSList *depends_on_list;

  GSList *llink;

  /* add the visitable to the list */

  insert (self, visitable);

  depends_on_list = gegl_visitable_depends_on (visitable);

  llink           = depends_on_list;

  while (llink)

    {

      GeglVisitable *visitable  = llink->data;

      GeglVisitInfo *visit_info = lookup (self, visitable);

      /* if the visitable doesn't have a visit_info,

       * then it needs to be initialised

       */

      if (!visit_info)

        init_dfs_traversal (self, visitable);

      llink = g_slist_next (llink);

    }

  g_slist_free (depends_on_list);

}

/* Recursively (depth first) traverses the visitables and call's their

 * accept methods

 */

static void

dfs_traverse (GeglVisitor   *self,

              GeglVisitable *visitable)

{

  GSList *depends_on_list;

  GSList *llink;

  depends_on_list = gegl_visitable_depends_on (visitable);

  llink           = depends_on_list;

  while (llink)

    {

      GeglVisitable *visitable = llink->data;

      /* if the visitable has not yet been visitied then visit it */

      if (!get_visited (self, visitable))

        dfs_traverse (self, visitable);

      llink = g_slist_next (llink);

    }

  g_slist_free (depends_on_list);

  /* trigger the actual visit (call the visitable's accept method that will

   * call the visitable's visit method (c.f. the visitor pattern)

   */

  gegl_visitable_accept (visitable, self);

  /* mark the visitable as already visited*/

  set_visited (self, visitable, TRUE);

}

static void

init_bfs_traversal (GeglVisitor   *self,

                    GeglVisitable *visitable)

{

  GSList *depends_on_list;

  GSList *llink;

  insert (self, visitable);

  depends_on_list = gegl_visitable_depends_on (visitable);

  llink           = depends_on_list;

  while (llink)

    {

      gint           shared_count;

      GeglVisitable *depends_on_visitable = llink->data;

      GeglVisitInfo *visit_info           = lookup (self, depends_on_visitable);

      if (!visit_info)

        init_bfs_traversal (self, depends_on_visitable);

      shared_count = get_shared_count (self, depends_on_visitable);

      shared_count++;

      set_shared_count (self, depends_on_visitable, shared_count);

      llink = g_slist_next (llink);

    }

  g_slist_free (depends_on_list);

}

/**

 * gegl_visitor_bfs_traverse:

 * @self: a #GeglVisitor

 * @visitable: the root #GeglVisitable.

 *

 * Traverse breadth-first starting at @visitable.

 **/

void

gegl_visitor_bfs_traverse (GeglVisitor   *self,

                           GeglVisitable *visitable)

{

  GQueue  queue = G_QUEUE_INIT;

  /* Init all visitables */

  init_bfs_traversal (self, visitable);

  /* Initialize the queue with this visitable */

  g_queue_push_head (&queue, visitable);

  /* Mark visitable as "discovered" */

  set_discovered (self, visitable, TRUE);

  /* Pop the top of the queue*/

  while ((visitable = g_queue_pop_head (&queue)))

    {

      gint shared_count = get_shared_count (self, visitable);

      /* Put this one at the end of the queue if its active

       * immediate parents haven't all been visited yet.

       */

      if (shared_count > 0)

        {

          g_queue_push_tail (&queue, visitable);

          continue;

        }

      /* Loop through visitable's sources and examine them */

      {

        GSList *depends_on_list = gegl_visitable_depends_on (visitable);

        GSList *llink;

        for (llink = depends_on_list; llink; llink = g_slist_next (llink))

          {

            GeglVisitable *depends_on_visitable = llink->data;

            shared_count = get_shared_count (self, depends_on_visitable);

            shared_count--;

            set_shared_count (self, depends_on_visitable, shared_count);

            /* Add any undiscovered visitable to the queue at end */

            if (!get_discovered (self, depends_on_visitable))

              {

                g_queue_push_tail (&queue, depends_on_visitable);

                /* Mark it as discovered */

                set_discovered (self, depends_on_visitable, TRUE);

              }

          }

        g_slist_free (depends_on_list);

      }

      /* Visit the visitable */

      gegl_visitable_accept (visitable, self);

      set_visited (self, visitable, TRUE);

    }

}

/* should be called by extending classes when their visit_pad function

 * is called

 */

void

gegl_visitor_visit_pad (GeglVisitor *self,

                        GeglPad     *pad)

{

  GeglVisitorClass *klass;

  klass = GEGL_VISITOR_GET_CLASS (self);

  if (klass->visit_pad)

    klass->visit_pad (self, pad);

}

static void

visit_pad (GeglVisitor *self,

           GeglPad     *pad)

{

  self->visits_list = g_slist_prepend (self->visits_list, pad);

}

/* should be called by extending classes when their visit_node function

 * is called

 */

void

gegl_visitor_visit_node (GeglVisitor *self,

                         GeglNode    *node)

{

  GeglVisitorClass *klass;

  klass = GEGL_VISITOR_GET_CLASS (self);

  if (klass->visit_node)

    klass->visit_node (self, node);

}

/* adds the visiting node to the list of visits */

static void

visit_node (GeglVisitor *self,

            GeglNode    *node)

{

#if 0

#if ENABLE_MT

  g_mutex_lock (node->mutex);

#endif

#endif

  self->visits_list = g_slist_prepend (self->visits_list, node);

#if 0

#if ENABLE_MT

  g_mutex_unlock (node->mutex);

#endif

#endif

}