/* Range object implementation */

#include "Python.h"

typedef struct {

	PyObject_HEAD

	long	start;

	long	step;

	long	len;

} rangeobject;

/* Return number of items in range/xrange (lo, hi, step).  step > 0

 * required.  Return a value < 0 if & only if the true value is too

 * large to fit in a signed long.

 */

static long

get_len_of_range(long lo, long hi, long step)

{

	/* -------------------------------------------------------------

	If lo >= hi, the range is empty.

	Else if n values are in the range, the last one is

	lo + (n-1)*step, which must be <= hi-1.  Rearranging,

	n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives

	the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so

	the RHS is non-negative and so truncation is the same as the

	floor.  Letting M be the largest positive long, the worst case

	for the RHS numerator is hi=M, lo=-M-1, and then

	hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough

	precision to compute the RHS exactly.

	---------------------------------------------------------------*/

	long n = 0;

	if (lo < hi) {

		unsigned long uhi = (unsigned long)hi;

		unsigned long ulo = (unsigned long)lo;

		unsigned long diff = uhi - ulo - 1;

		n = (long)(diff / (unsigned long)step + 1);

	}

	return n;

}

static PyObject *

range_new(PyTypeObject *type, PyObject *args, PyObject *kw)

{

	rangeobject *obj;

	long ilow = 0, ihigh = 0, istep = 1;

	long n;

	if (!_PyArg_NoKeywords("xrange()", kw))

		return NULL;

	if (PyTuple_Size(args) <= 1) {

		if (!PyArg_ParseTuple(args,

				"l;xrange() requires 1-3 int arguments",

				&ihigh))

			return NULL;

	}

	else {

		if (!PyArg_ParseTuple(args,

				"ll|l;xrange() requires 1-3 int arguments",

				&ilow, &ihigh, &istep))

			return NULL;

	}

	if (istep == 0) {

		PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");

		return NULL;

	}

	if (istep > 0)

		n = get_len_of_range(ilow, ihigh, istep);

	else

		n = get_len_of_range(ihigh, ilow, -istep);

	if (n < 0) {

		PyErr_SetString(PyExc_OverflowError,

				"xrange() result has too many items");

		return NULL;

	}

	obj = PyObject_New(rangeobject, &PyRange_Type);

	if (obj == NULL)

		return NULL;

	obj->start = ilow;

	obj->len   = n;

	obj->step  = istep;

	return (PyObject *) obj;

}

PyDoc_STRVAR(range_doc,

"xrange([start,] stop[, step]) -> xrange object\n\

\n\

Like range(), but instead of returning a list, returns an object that\n\

generates the numbers in the range on demand.  For looping, this is \n\

slightly faster than range() and more memory efficient.");

static PyObject *

range_item(rangeobject *r, Py_ssize_t i)

{

	if (i < 0 || i >= r->len) {

		PyErr_SetString(PyExc_IndexError,

				"xrange object index out of range");

		return NULL;

	}

	return PyInt_FromSsize_t(r->start + i * r->step);

}

static Py_ssize_t

range_length(rangeobject *r)

{

	return (Py_ssize_t)(r->len);

}

static PyObject *

range_repr(rangeobject *r)

{

	PyObject *rtn;

	if (r->start == 0 && r->step == 1)

		rtn = PyString_FromFormat("xrange(%ld)",

					  r->start + r->len * r->step);

	else if (r->step == 1)

		rtn = PyString_FromFormat("xrange(%ld, %ld)",

					  r->start,

					  r->start + r->len * r->step);

	else

		rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",

					  r->start,

					  r->start + r->len * r->step,

					  r->step);

	return rtn;

}

/* Pickling support */

static PyObject *

range_reduce(rangeobject *r, PyObject *args)

{

	return Py_BuildValue("(O(iii))", Py_TYPE(r),

			     r->start,

			     r->start + r->len * r->step,

			     r->step);

}

static PySequenceMethods range_as_sequence = {

	(lenfunc)range_length,	/* sq_length */

	0,			/* sq_concat */

	0,			/* sq_repeat */

	(ssizeargfunc)range_item, /* sq_item */

	0,			/* sq_slice */

};

static PyObject * range_iter(PyObject *seq);

static PyObject * range_reverse(PyObject *seq);

PyDoc_STRVAR(reverse_doc,

"Returns a reverse iterator.");

static PyMethodDef range_methods[] = {

	{"__reversed__",	(PyCFunction)range_reverse, METH_NOARGS, reverse_doc},

	{"__reduce__",		(PyCFunction)range_reduce, METH_VARARGS},

 	{NULL,		NULL}		/* sentinel */

};

PyTypeObject PyRange_Type = {

	PyObject_HEAD_INIT(&PyType_Type)

	0,			/* Number of items for varobject */

	"xrange",		/* Name of this type */

	sizeof(rangeobject),	/* Basic object size */

	0,			/* Item size for varobject */

	(destructor)PyObject_Del, /* tp_dealloc */

	0,			/* tp_print */

	0,			/* tp_getattr */

	0,			/* tp_setattr */

	0,			/* tp_compare */

	(reprfunc)range_repr,	/* tp_repr */

	0,			/* tp_as_number */

	&range_as_sequence,	/* tp_as_sequence */

	0,			/* tp_as_mapping */

	0,			/* tp_hash */

	0,			/* tp_call */

	0,			/* tp_str */

	PyObject_GenericGetAttr,  /* tp_getattro */

	0,			/* tp_setattro */

	0,			/* tp_as_buffer */

	Py_TPFLAGS_DEFAULT,	/* tp_flags */

	range_doc,		/* tp_doc */

	0,			/* tp_traverse */

	0,			/* tp_clear */

	0,			/* tp_richcompare */

	0,			/* tp_weaklistoffset */

	range_iter,		/* tp_iter */

	0,			/* tp_iternext */

	range_methods,		/* tp_methods */

	0,			/* tp_members */

	0,			/* tp_getset */

	0,			/* tp_base */

	0,			/* tp_dict */

	0,			/* tp_descr_get */

	0,			/* tp_descr_set */

	0,			/* tp_dictoffset */

	0,			/* tp_init */

	0,			/* tp_alloc */

	range_new,		/* tp_new */

};

/*********************** Xrange Iterator **************************/

typedef struct {

	PyObject_HEAD

	long	index;

	long	start;

	long	step;

	long	len;

} rangeiterobject;

static PyObject *

rangeiter_next(rangeiterobject *r)

{

	if (r->index < r->len)

		return PyInt_FromLong(r->start + (r->index++) * r->step);

	return NULL;

}

static PyObject *

rangeiter_len(rangeiterobject *r)

{

	return PyInt_FromLong(r->len - r->index);

}

PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

static PyMethodDef rangeiter_methods[] = {

	{"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},

 	{NULL,		NULL}		/* sentinel */

};

static PyTypeObject Pyrangeiter_Type = {

	PyObject_HEAD_INIT(&PyType_Type)

	0,                                      /* ob_size */

	"rangeiterator",                        /* tp_name */

	sizeof(rangeiterobject),                /* tp_basicsize */

	0,                                      /* tp_itemsize */

	/* methods */

	(destructor)PyObject_Del,		/* tp_dealloc */

	0,                                      /* tp_print */

	0,                                      /* tp_getattr */

	0,                                      /* tp_setattr */

	0,                                      /* tp_compare */

	0,                                      /* tp_repr */

	0,                                      /* tp_as_number */

	0,					/* tp_as_sequence */

	0,                                      /* tp_as_mapping */

	0,                                      /* tp_hash */

	0,                                      /* tp_call */

	0,                                      /* tp_str */

	PyObject_GenericGetAttr,                /* tp_getattro */

	0,                                      /* tp_setattro */

	0,                                      /* tp_as_buffer */

	Py_TPFLAGS_DEFAULT,			/* tp_flags */

	0,                                      /* tp_doc */

	0,					/* tp_traverse */

	0,                                      /* tp_clear */

	0,                                      /* tp_richcompare */

	0,                                      /* tp_weaklistoffset */

	PyObject_SelfIter,			/* tp_iter */

	(iternextfunc)rangeiter_next,		/* tp_iternext */

	rangeiter_methods,			/* tp_methods */

	0,

};

static PyObject *

range_iter(PyObject *seq)

{

	rangeiterobject *it;

	if (!PyRange_Check(seq)) {

		PyErr_BadInternalCall();

		return NULL;

	}

	it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);

	if (it == NULL)

		return NULL;

	it->index = 0;

	it->start = ((rangeobject *)seq)->start;

	it->step = ((rangeobject *)seq)->step;

	it->len = ((rangeobject *)seq)->len;

	return (PyObject *)it;

}

static PyObject *

range_reverse(PyObject *seq)

{

	rangeiterobject *it;

	long start, step, len;

	if (!PyRange_Check(seq)) {

		PyErr_BadInternalCall();

		return NULL;

	}

	it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);

	if (it == NULL)

		return NULL;

	start = ((rangeobject *)seq)->start;

	step = ((rangeobject *)seq)->step;

	len = ((rangeobject *)seq)->len;

	it->index = 0;

	it->start = start + (len-1) * step;

	it->step = -step;

	it->len = len;

	return (PyObject *)it;

}