/*
 * The Python Imaging Library.
 *
 * 2D path utilities
 *
 * history:
 * 1996-11-04 fl   Added to PIL (incomplete)
 * 1996-11-05 fl   Added sequence semantics
 * 1997-02-28 fl   Fixed getbbox
 * 1997-06-12 fl   Added id attribute
 * 1997-06-14 fl   Added slicing and setitem
 * 1998-12-29 fl   Improved sequence handling (from Richard Jones)
 * 1999-01-10 fl   Fixed IndexError test for 1.5 (from Fred Drake)
 * 2000-10-12 fl   Added special cases for tuples and lists
 * 2002-10-27 fl   Added clipping boilerplate
 * 2004-09-19 fl   Added tolist(flat) variant
 * 2005-05-06 fl   Added buffer interface support to path constructor
 *
 * notes:
 * FIXME: fill in remaining slots in the sequence api
 *
 * Copyright (c) 1997-2005 by Secret Labs AB
 * Copyright (c) 1997-2005 by Fredrik Lundh
 *
 * See the README file for information on usage and redistribution.
 */


#include "Python.h"
#include "Imaging.h"

#include <math.h>

#include "py3.h"

/* compatibility wrappers (defined in _imaging.c) */
extern int PyImaging_CheckBuffer(PyObject* buffer);
extern int PyImaging_GetBuffer(PyObject* buffer, Py_buffer *view);

/* -------------------------------------------------------------------- */
/* Class                                                                */
/* -------------------------------------------------------------------- */

typedef struct {
    PyObject_HEAD
    Py_ssize_t count;
    double *xy;
    int index; /* temporary use, e.g. in decimate */
} PyPathObject;

static PyTypeObject PyPathType;

static double*
alloc_array(Py_ssize_t count)
{
    double* xy;
    if (count < 0) {
        PyErr_NoMemory();
        return NULL;
    }
    if (count > (SIZE_MAX / (2 * sizeof(double))) - 1 ) {
        PyErr_NoMemory();
        return NULL;
    }
    xy = malloc(2 * count * sizeof(double) + 1);
    if (!xy)
        PyErr_NoMemory();
    return xy;
}

static PyPathObject*
path_new(Py_ssize_t count, double* xy, int duplicate)
{
    PyPathObject *path;

    if (duplicate) {
        /* duplicate path */
        double* p = alloc_array(count);
        if (!p)
            return NULL;
        memcpy(p, xy, count * 2 * sizeof(double));
        xy = p;
    }

    if (PyType_Ready(&PyPathType) < 0)
        return NULL;

    path = PyObject_New(PyPathObject, &PyPathType);
    if (path == NULL)
        return NULL;

    path->count = count;
    path->xy = xy;

    return path;
}

static void
path_dealloc(PyPathObject* path)
{
    free(path->xy);
    PyObject_Del(path);
}

/* -------------------------------------------------------------------- */
/* Helpers                                                              */
/* -------------------------------------------------------------------- */

#define PyPath_Check(op) (Py_TYPE(op) == &PyPathType)

Py_ssize_t
PyPath_Flatten(PyObject* data, double **pxy)
{
    Py_ssize_t i, j, n;
    double *xy;

    if (PyPath_Check(data)) {
        /* This was another path object. */
        PyPathObject *path = (PyPathObject*) data;
        xy = alloc_array(path->count);
        if (!xy)
            return -1;
        memcpy(xy, path->xy, 2 * path->count * sizeof(double));
        *pxy = xy;
        return path->count;
    }

    if (PyImaging_CheckBuffer(data)) {
        /* Assume the buffer contains floats */
        Py_buffer buffer;
        if (PyImaging_GetBuffer(data, &buffer) == 0) {
            int n = buffer.len / (2 * sizeof(float));
            float *ptr = (float*) buffer.buf;
            xy = alloc_array(n);
            if (!xy)
                return -1;
            for (i = 0; i < n+n; i++)
                xy[i] = ptr[i];
            *pxy = xy;
            PyBuffer_Release(&buffer);
            return n;
        }
        PyErr_Clear();
    }

    if (!PySequence_Check(data)) {
        PyErr_SetString(PyExc_TypeError, "argument must be sequence");
        return -1;
    }

    j = 0;
    n = PyObject_Length(data);
    /* Just in case __len__ breaks (or doesn't exist) */
    if (PyErr_Occurred())
        return -1;

    /* Allocate for worst case */
    xy = alloc_array(n);
    if (!xy)
        return -1;

    /* Copy table to path array */
    if (PyList_Check(data)) {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PyList_GET_ITEM(data, i);
            if (PyFloat_Check(op))
                xy[j++] = PyFloat_AS_DOUBLE(op);
            else if (PyInt_Check(op))
                xy[j++] = (float) PyInt_AS_LONG(op);
            else if (PyNumber_Check(op))
                xy[j++] = PyFloat_AsDouble(op);
            else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                free(xy);
                return -1;
            }
        }
    } else if (PyTuple_Check(data)) {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PyTuple_GET_ITEM(data, i);
            if (PyFloat_Check(op))
                xy[j++] = PyFloat_AS_DOUBLE(op);
            else if (PyInt_Check(op))
                xy[j++] = (float) PyInt_AS_LONG(op);
            else if (PyNumber_Check(op))
                xy[j++] = PyFloat_AsDouble(op);
            else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                free(xy);
                return -1;
            }
        }
    } else {
        for (i = 0; i < n; i++) {
            double x, y;
            PyObject *op = PySequence_GetItem(data, i);
            if (!op) {
                /* treat IndexError as end of sequence */
                if (PyErr_Occurred() &&
                    PyErr_ExceptionMatches(PyExc_IndexError)) {
                    PyErr_Clear();
                    break;
                } else {
                    free(xy);
                    return -1;
                }
            }
            if (PyFloat_Check(op))
                xy[j++] = PyFloat_AS_DOUBLE(op);
            else if (PyInt_Check(op))
                xy[j++] = (float) PyInt_AS_LONG(op);
            else if (PyNumber_Check(op))
                xy[j++] = PyFloat_AsDouble(op);
            else if (PyArg_ParseTuple(op, "dd", &x, &y)) {
                xy[j++] = x;
                xy[j++] = y;
            } else {
                Py_DECREF(op);
                free(xy);
                return -1;
            }
            Py_DECREF(op);
        }
    }

    if (j & 1) {
        PyErr_SetString(PyExc_ValueError, "wrong number of coordinates");
        free(xy);
        return -1;
    }

    *pxy = xy;
    return j/2;
}


/* -------------------------------------------------------------------- */
/* Factories                                                            */
/* -------------------------------------------------------------------- */

PyObject*
PyPath_Create(PyObject* self, PyObject* args)
{
    PyObject* data;
    Py_ssize_t count;
    double *xy;

    if (PyArg_ParseTuple(args, "n:Path", &count)) {

        /* number of vertices */
        xy = alloc_array(count);
        if (!xy)
            return NULL;

    } else {

        /* sequence or other path */
        PyErr_Clear();
        if (!PyArg_ParseTuple(args, "O", &data))
            return NULL;

        count = PyPath_Flatten(data, &xy);
        if (count < 0)
            return NULL;
    }

    return (PyObject*) path_new(count, xy, 0);
}


/* -------------------------------------------------------------------- */
/* Methods                                                              */
/* -------------------------------------------------------------------- */

static PyObject*
path_compact(PyPathObject* self, PyObject* args)
{
    /* Simple-minded method to shorten path.  A point is removed if
       the city block distance to the previous point is less than the
       given distance */
    Py_ssize_t i, j;
    double *xy;

    double cityblock = 2.0;

    if (!PyArg_ParseTuple(args, "|d:compact", &cityblock))
        return NULL;

    xy = self->xy;

    /* remove bogus vertices */
    for (i = j = 1; i < self->count; i++) {
        if (fabs(xy[j+j-2]-xy[i+i]) + fabs(xy[j+j-1]-xy[i+i+1]) >= cityblock) {
            xy[j+j] = xy[i+i];
            xy[j+j+1] = xy[i+i+1];
            j++;
        }
    }

    i = self->count - j;
    self->count = j;

    /* shrink coordinate array */
    /* malloc check ok, self->count is smaller than it was before */
    self->xy = realloc(self->xy, 2 * self->count * sizeof(double));

    return Py_BuildValue("i", i); /* number of removed vertices */
}

static PyObject*
path_getbbox(PyPathObject* self, PyObject* args)
{
    /* Find bounding box */
    Py_ssize_t i;
    double *xy;
    double x0, y0, x1, y1;

    if (!PyArg_ParseTuple(args, ":getbbox"))
        return NULL;

    xy = self->xy;

    x0 = x1 = xy[0];
    y0 = y1 = xy[1];

    for (i = 1; i < self->count; i++) {
        if (xy[i+i] < x0)
            x0 = xy[i+i];
        if (xy[i+i] > x1)
            x1 = xy[i+i];
        if (xy[i+i+1] < y0)
            y0 = xy[i+i+1];
        if (xy[i+i+1] > y1)
            y1 = xy[i+i+1];
    }

    return Py_BuildValue("dddd", x0, y0, x1, y1);
}