#include "Python.h"

#include "structmember.h"

/* collections module implementation of a deque() datatype

   Written and maintained by Raymond D. Hettinger <python@rcn.com>

   Copyright (c) 2004 Python Software Foundation.

   All rights reserved.

*/

/* The block length may be set to any number over 1.  Larger numbers

 * reduce the number of calls to the memory allocator but take more

 * memory.  Ideally, BLOCKLEN should be set with an eye to the

 * length of a cache line.

 */

#define BLOCKLEN 62

#define CENTER ((BLOCKLEN - 1) / 2)

/* A `dequeobject` is composed of a doubly-linked list of `block` nodes.

 * This list is not circular (the leftmost block has leftlink==NULL,

 * and the rightmost block has rightlink==NULL).  A deque d's first

 * element is at d.leftblock[leftindex] and its last element is at

 * d.rightblock[rightindex]; note that, unlike as for Python slice

 * indices, these indices are inclusive on both ends.  By being inclusive

 * on both ends, algorithms for left and right operations become

 * symmetrical which simplifies the design.

 *

 * The list of blocks is never empty, so d.leftblock and d.rightblock

 * are never equal to NULL.

 *

 * The indices, d.leftindex and d.rightindex are always in the range

 *     0 <= index < BLOCKLEN.

 * Their exact relationship is:

 *     (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.

 *

 * Empty deques have d.len == 0; d.leftblock==d.rightblock;

 * d.leftindex == CENTER+1; and d.rightindex == CENTER.

 * Checking for d.len == 0 is the intended way to see whether d is empty.

 *

 * Whenever d.leftblock == d.rightblock,

 *     d.leftindex + d.len - 1 == d.rightindex.

 *

 * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex

 * become indices into distinct blocks and either may be larger than the

 * other.

 */

typedef struct BLOCK {

	struct BLOCK *leftlink;

	struct BLOCK *rightlink;

	PyObject *data[BLOCKLEN];

} block;

#define MAXFREEBLOCKS 10

static Py_ssize_t numfreeblocks = 0;

static block *freeblocks[MAXFREEBLOCKS];

static block *

newblock(block *leftlink, block *rightlink, Py_ssize_t len) {

	block *b;

	/* To prevent len from overflowing PY_SSIZE_T_MAX on 64-bit machines, we

	 * refuse to allocate new blocks if the current len is dangerously

	 * close.  There is some extra margin to prevent spurious arithmetic

	 * overflows at various places.  The following check ensures that

	 * the blocks allocated to the deque, in the worst case, can only

	 * have PY_SSIZE_T_MAX-2 entries in total.

	 */

	if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {

		PyErr_SetString(PyExc_OverflowError,

				"cannot add more blocks to the deque");

		return NULL;

	}

	if (numfreeblocks) {

		numfreeblocks -= 1;

		b = freeblocks[numfreeblocks];

	} else {

		b = PyMem_Malloc(sizeof(block));

		if (b == NULL) {

			PyErr_NoMemory();

			return NULL;

		}

	}

	b->leftlink = leftlink;

	b->rightlink = rightlink;

	return b;

}

static void

freeblock(block *b)

{

	if (numfreeblocks < MAXFREEBLOCKS) {

		freeblocks[numfreeblocks] = b;

		numfreeblocks++;

	} else {

		PyMem_Free(b);

	}

}

typedef struct {

	PyObject_HEAD

	block *leftblock;

	block *rightblock;

	Py_ssize_t leftindex;	/* in range(BLOCKLEN) */

	Py_ssize_t rightindex;	/* in range(BLOCKLEN) */

	Py_ssize_t len;

	Py_ssize_t maxlen;

	long state;	/* incremented whenever the indices move */

	PyObject *weakreflist; /* List of weak references */

} dequeobject;

/* The deque's size limit is d.maxlen.  The limit can be zero or positive.

 * If there is no limit, then d.maxlen == -1.

 * 

 * After an item is added to a deque, we check to see if the size has grown past

 * the limit. If it has, we get the size back down to the limit by popping an

 * item off of the opposite end.  The methods that can trigger this are append(),

 * appendleft(), extend(), and extendleft().

 */

#define TRIM(d, popfunction)                               	\

    if (d->maxlen != -1 && d->len > d->maxlen) {              	\

            PyObject *rv = popfunction(d, NULL);                \

            assert(rv != NULL  &&  d->len <= d->maxlen);        \

            Py_DECREF(rv);                                      \

    }

static PyTypeObject deque_type;

static PyObject *

deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

{

	dequeobject *deque;

	block *b;

	/* create dequeobject structure */

	deque = (dequeobject *)type->tp_alloc(type, 0);

	if (deque == NULL)

		return NULL;

	b = newblock(NULL, NULL, 0);

	if (b == NULL) {

		Py_DECREF(deque);

		return NULL;

	}

	assert(BLOCKLEN >= 2);

	deque->leftblock = b;

	deque->rightblock = b;

	deque->leftindex = CENTER + 1;

	deque->rightindex = CENTER;

	deque->len = 0;

	deque->state = 0;

	deque->weakreflist = NULL;

	deque->maxlen = -1;

	return (PyObject *)deque;

}

static PyObject *

deque_pop(dequeobject *deque, PyObject *unused)

{

	PyObject *item;

	block *prevblock;

	if (deque->len == 0) {

		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

		return NULL;

	}

	item = deque->rightblock->data[deque->rightindex];

	deque->rightindex--;

	deque->len--;

	deque->state++;

	if (deque->rightindex == -1) {

		if (deque->len == 0) {

			assert(deque->leftblock == deque->rightblock);

			assert(deque->leftindex == deque->rightindex+1);

			/* re-center instead of freeing a block */

			deque->leftindex = CENTER + 1;

			deque->rightindex = CENTER;

		} else {

			prevblock = deque->rightblock->leftlink;

			assert(deque->leftblock != deque->rightblock);

			freeblock(deque->rightblock);

			prevblock->rightlink = NULL;

			deque->rightblock = prevblock;

			deque->rightindex = BLOCKLEN - 1;

		}

	}

	return item;

}

PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");

static PyObject *

deque_popleft(dequeobject *deque, PyObject *unused)

{

	PyObject *item;

	block *prevblock;

	if (deque->len == 0) {

		PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

		return NULL;

	}

	assert(deque->leftblock != NULL);

	item = deque->leftblock->data[deque->leftindex];

	deque->leftindex++;

	deque->len--;

	deque->state++;

	if (deque->leftindex == BLOCKLEN) {

		if (deque->len == 0) {

			assert(deque->leftblock == deque->rightblock);

			assert(deque->leftindex == deque->rightindex+1);

			/* re-center instead of freeing a block */

			deque->leftindex = CENTER + 1;

			deque->rightindex = CENTER;

		} else {

			assert(deque->leftblock != deque->rightblock);

			prevblock = deque->leftblock->rightlink;

			freeblock(deque->leftblock);

			assert(prevblock != NULL);

			prevblock->leftlink = NULL;

			deque->leftblock = prevblock;

			deque->leftindex = 0;

		}

	}

	return item;

}

PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");

static PyObject *

deque_append(dequeobject *deque, PyObject *item)

{

	deque->state++;

	if (deque->rightindex == BLOCKLEN-1) {

		block *b = newblock(deque->rightblock, NULL, deque->len);

		if (b == NULL)

			return NULL;

		assert(deque->rightblock->rightlink == NULL);

		deque->rightblock->rightlink = b;

		deque->rightblock = b;

		deque->rightindex = -1;

	}

	Py_INCREF(item);

	deque->len++;

	deque->rightindex++;

	deque->rightblock->data[deque->rightindex] = item;

	TRIM(deque, deque_popleft);

	Py_RETURN_NONE;

}

PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");

static PyObject *

deque_appendleft(dequeobject *deque, PyObject *item)

{

	deque->state++;

	if (deque->leftindex == 0) {

		block *b = newblock(NULL, deque->leftblock, deque->len);

		if (b == NULL)

			return NULL;

		assert(deque->leftblock->leftlink == NULL);

		deque->leftblock->leftlink = b;

		deque->leftblock = b;

		deque->leftindex = BLOCKLEN;

	}

	Py_INCREF(item);

	deque->len++;

	deque->leftindex--;

	deque->leftblock->data[deque->leftindex] = item;

	TRIM(deque, deque_pop);

	Py_RETURN_NONE;

}

PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");

static PyObject *

deque_extend(dequeobject *deque, PyObject *iterable)

{

	PyObject *it, *item;

	it = PyObject_GetIter(iterable);

	if (it == NULL)

		return NULL;

	while ((item = PyIter_Next(it)) != NULL) {

		deque->state++;

		if (deque->rightindex == BLOCKLEN-1) {

			block *b = newblock(deque->rightblock, NULL,

					    deque->len);

			if (b == NULL) {

				Py_DECREF(item);

				Py_DECREF(it);

				return NULL;

			}

			assert(deque->rightblock->rightlink == NULL);

			deque->rightblock->rightlink = b;

			deque->rightblock = b;

			deque->rightindex = -1;

		}

		deque->len++;

		deque->rightindex++;

		deque->rightblock->data[deque->rightindex] = item;

		TRIM(deque, deque_popleft);               

	}

	Py_DECREF(it);

	if (PyErr_Occurred())

		return NULL;

	Py_RETURN_NONE;

}

PyDoc_STRVAR(extend_doc,

"Extend the right side of the deque with elements from the iterable");

static PyObject *

deque_extendleft(dequeobject *deque, PyObject *iterable)

{

	PyObject *it, *item;

	it = PyObject_GetIter(iterable);

	if (it == NULL)

		return NULL;

	while ((item = PyIter_Next(it)) != NULL) {

		deque->state++;

		if (deque->leftindex == 0) {

			block *b = newblock(NULL, deque->leftblock,

					    deque->len);

			if (b == NULL) {

				Py_DECREF(item);

				Py_DECREF(it);

				return NULL;

			}

			assert(deque->leftblock->leftlink == NULL);

			deque->leftblock->leftlink = b;

			deque->leftblock = b;

			deque->leftindex = BLOCKLEN;

		}

		deque->len++;

		deque->leftindex--;

		deque->leftblock->data[deque->leftindex] = item;

		TRIM(deque, deque_pop);               

	}

	Py_DECREF(it);

	if (PyErr_Occurred())

		return NULL;

	Py_RETURN_NONE;

}

PyDoc_STRVAR(extendleft_doc,

"Extend the left side of the deque with elements from the iterable");

static int

_deque_rotate(dequeobject *deque, Py_ssize_t n)

{

	Py_ssize_t i, len=deque->len, halflen=(len+1)>>1;

	PyObject *item, *rv;

	if (len == 0)

		return 0;

	if (n > halflen || n < -halflen) {

		n %= len;

		if (n > halflen)

			n -= len;

		else if (n < -halflen)

			n += len;

	}

	for (i=0 ; i<n ; i++) {

		item = deque_pop(deque, NULL);

		assert (item != NULL);

		rv = deque_appendleft(deque, item);

		Py_DECREF(item);

		if (rv == NULL)

			return -1;

		Py_DECREF(rv);

	}

	for (i=0 ; i>n ; i--) {

		item = deque_popleft(deque, NULL);

		assert (item != NULL);

		rv = deque_append(deque, item);

		Py_DECREF(item);

		if (rv == NULL)

			return -1;

		Py_DECREF(rv);

	}

	return 0;

}

static PyObject *

deque_rotate(dequeobject *deque, PyObject *args)

{

	Py_ssize_t n=1;

	if (!PyArg_ParseTuple(args, "|n:rotate", &n))

		return NULL;

	if (_deque_rotate(deque, n) == 0)

		Py_RETURN_NONE;

	return NULL;

}

PyDoc_STRVAR(rotate_doc,

"Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.");

static Py_ssize_t

deque_len(dequeobject *deque)

{

	return deque->len;

}

static PyObject *

deque_remove(dequeobject *deque, PyObject *value)

{

	Py_ssize_t i, n=deque->len;

	for (i=0 ; i<n ; i++) {

		PyObject *item = deque->leftblock->data[deque->leftindex];

		int cmp = PyObject_RichCompareBool(item, value, Py_EQ);

		if (deque->len != n) {

			PyErr_SetString(PyExc_IndexError,

				"deque mutated during remove().");

			return NULL;

		}

		if (cmp > 0) {

			PyObject *tgt = deque_popleft(deque, NULL);

			assert (tgt != NULL);

			Py_DECREF(tgt);

			if (_deque_rotate(deque, i) == -1)

				return NULL;

			Py_RETURN_NONE;

		}

		else if (cmp < 0) {

			_deque_rotate(deque, i);

			return NULL;

		}

		_deque_rotate(deque, -1);

	}

	PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");

	return NULL;

}

PyDoc_STRVAR(remove_doc,

"D.remove(value) -- remove first occurrence of value.");

static int

deque_clear(dequeobject *deque)

{

	PyObject *item;

	while (deque->len) {

		item = deque_pop(deque, NULL);

		assert (item != NULL);

		Py_DECREF(item);

	}

	assert(deque->leftblock == deque->rightblock &&

	       deque->leftindex - 1 == deque->rightindex &&

	       deque->len == 0);

	return 0;

}

static PyObject *

deque_item(dequeobject *deque, Py_ssize_t i)

{

	block *b;

	PyObject *item;

	Py_ssize_t n, index=i;

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

		PyErr_SetString(PyExc_IndexError,

				"deque index out of range");

		return NULL;

	}

	if (i == 0) {

		i = deque->leftindex;

		b = deque->leftblock;

	} else if (i == deque->len - 1) {

		i = deque->rightindex;

		b = deque->rightblock;

	} else {

		i += deque->leftindex;

		n = i / BLOCKLEN;

		i %= BLOCKLEN;

		if (index < (deque->len >> 1)) {

			b = deque->leftblock;

			while (n--)

				b = b->rightlink;

		} else {

			n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;

			b = deque->rightblock;

			while (n--)

				b = b->leftlink;

		}

	}

	item = b->data[i];

	Py_INCREF(item);

	return item;

}

/* delitem() implemented in terms of rotate for simplicity and reasonable

   performance near the end points.  If for some reason this method becomes

   popular, it is not hard to re-implement this using direct data movement

   (similar to code in list slice assignment) and achieve a two or threefold

   performance boost.

*/

static int

deque_del_item(dequeobject *deque, Py_ssize_t i)

{

	PyObject *item;

	assert (i >= 0 && i < deque->len);

	if (_deque_rotate(deque, -i) == -1)

		return -1;

	item = deque_popleft(deque, NULL);

	assert (item != NULL);

	Py_DECREF(item);

	return _deque_rotate(deque, i);

}

static int

deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)

{