/* This is -*- C -*- */
/* vim: set sw=2: */
/* $Id$ */

/*
 * seqmodel.c
 *
 * Copyright (C) 2003 The Free Software Foundation, Inc.
 *
 * Developed by Jon Trowbridge <trow@gnu.org>
 */

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * This program 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 General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA.
 */

#ifdef CONFIG_H
#include <config.h>
#endif
#include "seqmodel.h"

SeqModel *
seq_model_new (unsigned     N,
	       SeqAtom      padding_atom,
	       SeqAtom      wildcard_atom,
	       SeqAtomEq    atom_eq,
	       SeqAtomHash  atom_hash,
	       SeqAtomRef   atom_ref,
	       SeqAtomUnref atom_unref)
{
  SeqModel *model = g_new0 (SeqModel, 1);

  model->N             = N;
  model->padding_atom  = padding_atom;
  model->wildcard_atom = wildcard_atom;
  model->atom_eq       = atom_eq;
  model->atom_hash     = atom_hash;
  model->atom_ref      = atom_ref;
  model->atom_unref    = atom_unref;

  return model;
}

void
seq_model_free (SeqModel *model)
{
  /* No-op for now */
}

static GHashTable *
seq_model_make_atom_hash (SeqModel *model)
{
  return g_hash_table_new ((GHashFunc) model->atom_hash,
			   (GEqualFunc) model->atom_eq);
}

static GPtrArray *
seq_model_walk_tuple (SeqModel *model,
		      SeqAtom  *tuple,
		      gboolean  create_array)
{
  GHashTable *walk = model->tree;
  GPtrArray *array;
  unsigned i;

  if (walk == NULL) {
    model->tree = walk = seq_model_make_atom_hash (model);
  }

  for (i = 0; i < model->N-1; ++i) {
    GHashTable *step = g_hash_table_lookup (walk, tuple[i]);
    if (step == NULL) {
      if (! create_array)
	return NULL;
      step = seq_model_make_atom_hash (model);
      if (model->atom_ref)
	model->atom_ref (tuple[i]);
      g_hash_table_insert (walk, tuple[i], step); 
    }
    walk = step;
  }

  array = g_hash_table_lookup (walk, tuple[model->N-1]);
  if (array == NULL && create_array) {
    array = g_ptr_array_new ();
    if (model->atom_ref)
      model->atom_ref (tuple[model->N-1]);
    g_hash_table_insert (walk, tuple[model->N-1], array);
  }

  return array;
}

static void
seq_model_add_tuple (SeqModel *model,
		     SeqAtom  *tuple)
{
  GPtrArray *array;
  SeqAtom saved;
  unsigned i;

  for (i = 0; i < model->N; ++i) {
    saved = tuple[i];
    tuple[i] = model->wildcard_atom;

    array = seq_model_walk_tuple (model, tuple, TRUE);
    if (model->atom_ref)
      model->atom_ref (saved);
    g_ptr_array_add (array, saved);

    tuple[i] = saved;
  }
}

void
seq_model_add_sentence (SeqModel *model,
			SeqAtom  *sentence,
			unsigned  len)
{
  SeqAtom *tuple;
  unsigned i, j;

  /* build a fully-padded tuple */
  tuple = g_new0 (SeqAtom, model->N);
  for (i = 0; i < model->N; ++i)
    tuple[i] = model->padding_atom;

  /* slide our sentence through the tuple */
  for (j = 0; j < len; ++j) {
    /* shift tuple */
    for (i = 1; i < model->N; ++i)
      tuple[i-1] = tuple[i];
    tuple[model->N-1] = sentence[j];
    seq_model_add_tuple (model, tuple);
  }

  /* generate our right-padded tuples */
  for (j = 0; j < model->N-1; ++j) {
    /* shift tuple */
    for (i = 1; i < model->N; ++i)
      tuple[i-1] = tuple[i];
    tuple[model->N-1] = model->padding_atom;
    seq_model_add_tuple (model, tuple);
  }
  
  g_free (tuple);
}

/* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** */

typedef struct _PySeqModel PySeqModel;
struct _PySeqModel {
  PyObject_HEAD;
  SeqModel *model;
};

static PyObject *
py_seq_model_add_sentence (PyObject *self, PyObject *args)
{
  SeqModel *model = seq_model_from_py (self);
  int i, len;
  PyObject *py_seq;
  SeqAtom *sentence;

  if (! PyArg_ParseTuple (args, "O", &py_seq))
    return NULL;

  len = PySequence_Size (py_seq);
  sentence = g_new (SeqAtom, len);
  for (i = 0; i < len; ++i)
    sentence[i] = PySequence_Fast_GET_ITEM (py_seq, i);
  seq_model_add_sentence (model, sentence, len);
  g_free (sentence);

  Py_INCREF (Py_None);
  return Py_None;
}

static PyObject *
py_seq_model_solve (PyObject *self, PyObject *args)
{
  SeqModel *model = seq_model_from_py (self);
  SeqAtom *tuple;
  PyObject *py_seq, *soln;
  GPtrArray *array;
  int i, len;

  if (! PyArg_ParseTuple (args, "O", &py_seq))
    return NULL;

  len = PySequence_Size (py_seq);
  if (len != model->N) {
    Py_INCREF (Py_None);
    return Py_None;
  }

  tuple = g_new (SeqAtom, model->N);
  for (i = 0; i < model->N; ++i) {
    tuple[i] = PySequence_Fast_GET_ITEM (py_seq, i);
  }

  array = seq_model_walk_tuple (model, tuple, FALSE);
  g_free (tuple);

  if (array == NULL) {
    soln = PyList_New (0);
  } else {
    soln = PyList_New (array->len);
    for (i = 0; i < array->len; ++i) {
      PyObject *obj = g_ptr_array_index (array, i);
      Py_INCREF (obj);
      PyList_SetItem (soln, i, obj);
    }
  }

  return soln;
}

static PyMethodDef py_seq_model_methods[] = {
  { "add_sentence", py_seq_model_add_sentence, METH_VARARGS,
    "Add a sentence to the model." },
  { "solve", py_seq_model_solve, METH_VARARGS,
    "Solve a tuple." },
  { NULL, NULL, 0, NULL }
};

static PyObject *
py_seq_model_getattr (PyObject *self, char *name)
{
  return Py_FindMethod (py_seq_model_methods, self, name);
}

static void
py_seq_model_dealloc (PyObject *self)
{
  SeqModel *model = seq_model_from_py (self);
  seq_model_free (model);
  PyObject_Del (self);
}

static PyTypeObject py_seq_model_type_info = {
  PyObject_HEAD_INIT(NULL)
  0,
  "SeqModel",
  sizeof(PySeqModel),
  0,
  py_seq_model_dealloc, /*tp_dealloc*/
  NULL,                 /*tp_print*/
  py_seq_model_getattr, /*tp_getattr*/
  NULL,                 /*tp_setattr*/
  NULL,                 /*tp_compare*/
  NULL,                 /*tp_repr*/
  NULL,                 /*tp_as_number*/
  NULL,                 /*tp_as_sequence*/
  NULL,                 /*tp_as_mapping*/
  NULL,                 /*tp_hash */
};

PyObject *
seq_model_to_py (SeqModel *model)
{
  PySeqModel *py_model;

  if (model == NULL) {
    Py_INCREF (Py_None);
    return Py_None;
  }

  py_model = PyObject_New (PySeqModel,
			   &py_seq_model_type_info);
  py_model->model = model;

  return (PyObject *) py_model;
}

SeqModel *
seq_model_from_py (PyObject *obj)
{
  return ((PySeqModel *) obj)->model;
}

/* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** */

static gboolean
py_seq_atom_eq (SeqAtom a, SeqAtom b)
{
  int res;
  if (PyObject_Cmp ((PyObject *) a, (PyObject *) b, &res) == -1) {
    g_assert (0);
  }
  return res == 0;
}

static guint
py_seq_atom_hash (SeqAtom a)
{
  return PyObject_Hash ((PyObject *) a);
}

static void
py_seq_atom_ref (SeqAtom a)
{
  Py_INCREF ((PyObject *) a);
}

static void
py_seq_atom_unref (SeqAtom a)
{
  Py_DECREF ((PyObject *) a);
}

PyObject *
py_seq_model_new (PyObject *self, PyObject *args)
{
  SeqModel *model;
  int N;
  PyObject *py_padding_atom, *py_wildcard_atom;

  if (! PyArg_ParseTuple (args, "i", &N))
    return NULL;

  if (N < 2)
    return NULL;

  Py_INCREF (Py_None);
  py_padding_atom = Py_None;

  py_wildcard_atom = Py_BuildValue ("s", "?");

  model = seq_model_new (N,
			 (SeqAtom) py_padding_atom,
			 (SeqAtom) py_wildcard_atom,
			 py_seq_atom_eq,
			 py_seq_atom_hash,
			 py_seq_atom_ref,
			 py_seq_atom_unref);

  return seq_model_to_py (model);
}