// -*- Mode: C++ -*-

#include "Python.h"
#include <deque>

#if defined (NODOCSTRINGS)
#define DOCSTRING(v) ""
#else
#define DOCSTRING(v) v
#endif

// XXX catch exceptions

typedef deque <PyObject *> py_deque;

typedef struct _deque_object {
  PyObject_HEAD
  py_deque * d;
  // convenience function
  py_deque & D (void) {return *d;};
} py_deque_object;

PyObject * py_deque_new (PyObject * self, PyObject *args);
PyObject * deque_new (int size);
static inline bool py_deque_check (PyObject * o);

static void
deque_dealloc(py_deque_object *op)
{
  py_deque::iterator i;
  for (i = op->d->begin(); i != op->d->end(); i++) {
    Py_XDECREF (*i);
  }
  delete op->d;
  PyObject_DEL(op);
}

static int
deque_print(py_deque_object *op, FILE *fp, int flags)
{
  int i;
  int size = op->D().size();
  i = Py_ReprEnter((PyObject*)op);
  if (i != 0) {
    if (i < 0) {
      return i;
    }
    fprintf(fp, "[...]");
    return 0;
  }
  fprintf(fp, "[");
  for (i = 0; i < size; i++) {
    if (i > 0) {
      fprintf(fp, ", ");
    }
    if (PyObject_Print(op->D()[i], fp, 0) != 0) {
      Py_ReprLeave((PyObject *)op);
      return -1;
    }
  }
  fprintf(fp, "]");
  Py_ReprLeave((PyObject *)op);
  return 0;
}

static PyObject *
deque_repr(py_deque_object *v)
{
  PyObject *s, *comma;
  int i;
  int size = v->D().size();

  i = Py_ReprEnter((PyObject*)v);
  if (i != 0) {
    if (i > 0)
      return PyString_FromString("[...]");
    return NULL;
  }
  s = PyString_FromString("[");
  comma = PyString_FromString(", ");
  for (i = 0; i < size && s != NULL; i++) {
    if (i > 0) {
      PyString_Concat(&s, comma);
    }
    PyString_ConcatAndDel(&s, PyObject_Repr(v->D()[i]));
  }
  Py_XDECREF(comma);
  PyString_ConcatAndDel(&s, PyString_FromString("]"));
  Py_ReprLeave((PyObject *)v);
  return s;
}

static int
deque_compare(py_deque_object *v, py_deque_object *w)
{
  int i;
  int v_size = v->D().size();
  int w_size = w->D().size();

  for (i = 0; i < v_size && i < w_size; i++) {
    int cmp = PyObject_Compare(v->D()[i], w->D()[i]);
    if (cmp != 0) {
      return cmp;
    }
  }
  return v->D().size() - w->D().size();
}

static int
deque_length(py_deque_object *a)
{
  return a->D().size();
}

static int
deque_contains(py_deque_object *a, PyObject *el)
{
  int i, cmp;
  int size = a->D().size();

  for (i = 0; i < size; ++i) {
    cmp = PyObject_Compare(el, a->D()[i]);
    if (cmp == 0) {
      return 1;
    }
    if (PyErr_Occurred()) {
      return -1;
    }
  }
  return 0;
}

static PyObject *
deque_item(py_deque_object *a, int i)
{
  int size = a->D().size();
  if (i < 0 || i >= size) {
    PyErr_SetString (PyExc_IndexError, "index out of range");
    return NULL;
  }
  Py_INCREF(a->D()[i]);
  return a->D()[i];
}

static PyObject *
deque_slice(py_deque_object *a, int ilow, int ihigh)
{
  py_deque_object *np;
  int i;
  if (ilow < 0){
    ilow = 0;
  } else if ((unsigned int) ilow > a->D().size()) {
    ilow = a->D().size();
  }
  if (ihigh < ilow) {
    ihigh = ilow;
  } else if ((unsigned int) ihigh > a->D().size()) {
    ihigh = a->D().size();
  }
  np = (py_deque_object *) deque_new (ihigh - ilow);
  if (np == NULL) {
    return NULL;
  }
  for (i = ilow; i < ihigh; i++) {
    PyObject *v = a->D()[i];
    Py_INCREF(v);
    np->D()[i - ilow] = v;
  }
  return (PyObject *)np;
}

static PyObject *
deque_concat(py_deque_object *a, PyObject *bb)
{
  int size;
  int i;
  py_deque_object *np;
  if (!py_deque_check (bb)) {
    PyErr_Format (
      PyExc_TypeError,
      "can only concatenate deque (not \"%.200s\") to deque",
      bb->ob_type->tp_name
      );
    return NULL;
  }
  py_deque_object * b = (py_deque_object *) bb;
  size = a->D().size() + b->D().size();
  np = (py_deque_object *) deque_new (size);
  if (np == NULL) {
    return NULL;
  }
  int a_size = a->D().size();
  int b_size = b->D().size();
  for (i = 0; i < a_size; i++) {
    PyObject *v = a->D()[i];
    Py_INCREF(v);
    np->D()[i] = v;
  }
  for (i = 0; i < b_size; i++) {
    PyObject *v = b->D()[i];
    Py_INCREF(v);
    np->D()[i + a_size] = v;
  }
  return (PyObject *)np;
}

static int
deque_ass_item(py_deque_object *a, int i, PyObject *v)
{
  PyObject *old_value;
  if (v == NULL) {
    PyErr_SetString (PyExc_ValueError, "del <slice> not supported on this type");
    return -1;
  }
  Py_INCREF(v);
  old_value = a->D()[i];
  a->D()[i] = v;
  Py_DECREF(old_value);
  return 0;
}

static
PyObject *
py_deque_pop_back (py_deque_object * self, PyObject * args)
{
  if (!PyArg_ParseTuple (args, "")) {
    return NULL;
  } else {
    if (self->d->size() > 0) {
      PyObject * ob = self->d->back();
      self->d->pop_back();
      return ob;
    } else {
      PyErr_SetString (PyExc_IndexError, "pop from empty deque");
      return NULL;
    }
  }
}

static
PyObject *
py_deque_pop_front (py_deque_object * self, PyObject * args)
{
  if (!PyArg_ParseTuple (args, "")) {
    return NULL;
  } else {
    if (self->d->size() > 0) {
      PyObject * ob = self->d->front();
      self->d->pop_front();
      return ob;
    } else {
      PyErr_SetString (PyExc_IndexError, "pop from empty deque");
      return NULL;
    }
  }
}

static
PyObject *
py_deque_push_back (py_deque_object * self, PyObject * args)
{
  PyObject * ob;
  if (!PyArg_ParseTuple (args, "O", &ob)) {
    return NULL;
  } else {
    self->d->push_back (ob);
    Py_INCREF (ob);
  }
  Py_INCREF (Py_None);
  return Py_None;
}

static
PyObject *
py_deque_push_front (py_deque_object * self, PyObject * args)
{
  PyObject * ob;
  if (!PyArg_ParseTuple (args, "O", &ob)) {
    return NULL;
  } else {
    self->d->push_front (ob);
    Py_INCREF (ob);
  }
  Py_INCREF (Py_None);
  return Py_None;
}

static PyMethodDef deque_object_methods[] = {
  {"pop_front",   (PyCFunction) py_deque_pop_front,  METH_VARARGS },
  {"pop_back",    (PyCFunction) py_deque_pop_back,   METH_VARARGS },
  {"push_front",  (PyCFunction) py_deque_push_front, METH_VARARGS },
  {"push_back",   (PyCFunction) py_deque_push_back,  METH_VARARGS },
  {NULL, NULL}		// sentinel
};

static PyObject *
deque_getattr(py_deque_object *f, char *name)
{
  return Py_FindMethod(deque_object_methods, (PyObject *)f, name);
}

static PySequenceMethods deque_as_sequence = {
  (inquiry)             deque_length,   // sq_length
  (binaryfunc)          deque_concat,   // sq_concat
  (intargfunc)          0,              // sq_repeat
  (intargfunc)          deque_item,     // sq_item
  (intintargfunc)       deque_slice,    // sq_slice
  (intobjargproc)       deque_ass_item, // sq_ass_item
  (intintobjargproc)    0,              // sq_ass_slice
  (objobjproc)          deque_contains, // sq_contains
  (binaryfunc)          0,              // sq_inplace_concat
  (intargfunc)          0,              // sq_inplace_repeat
};

PyTypeObject py_deque_type = {
  PyObject_HEAD_INIT(&PyType_Type)
  0,
  "deque",
  sizeof(py_deque_object) + PyGC_HEAD_SIZE,
  0,
  (destructor)deque_dealloc,    //tp_dealloc
  (printfunc)deque_print,       //tp_print
  (getattrfunc)deque_getattr,   //tp_getattr
  0,                            //tp_setattr
  (cmpfunc)deque_compare,       //tp_compare
  (reprfunc)deque_repr,         //tp_repr
  0,                            //tp_as_number
  &deque_as_sequence,           //tp_as_sequence
  0,                            //tp_as_mapping
  0,                            //tp_hash
  0,                            //tp_call
  0,                            //tp_str
  0,                            //tp_getattro
  0,                            //tp_setattro
  0,                            //tp_as_buffer
  Py_TPFLAGS_DEFAULT,           //tp_flags
  0,                            //tp_doc 
};

static
inline
bool
py_deque_check (PyObject * o)
{
  return (o->ob_type == &py_deque_type);
}

PyObject *
deque_new (int size)
{
  py_deque_object * ob = PyObject_NEW (py_deque_object, &py_deque_type);
  if (!ob) {
    return NULL;
  } else {
    ob->d = new py_deque (size);
    if (!ob->d) {
      PyObject_FREE (ob);
      return NULL;
    } else {
      return (PyObject *) ob;
    }
  }
}

PyObject *
py_deque_new (PyObject * self, PyObject *args)
{
  return deque_new (0);
}

static PyMethodDef deque_methods[] = {
  {"deque", py_deque_new, METH_VARARGS},
  {0, 0}
};

static char module_doc[] = DOCSTRING (
  "<module doc>\n"
  );

extern "C" {
DL_EXPORT(void)
initdeque (void)
{
  PyObject *m, *d;
	
  m = Py_InitModule3("deque", deque_methods, module_doc);
  /* Let the user get access to the Type object. */
  d = PyModule_GetDict(m);
  PyDict_SetItemString(d, "deque_Type", (PyObject *)&py_deque_type);
}
}