blob: c48bee0164e7a6050a05b74dff7bd4a558a332a3 [file] [log] [blame]
Guido van Rossum12d12c51993-10-26 17:58:25 +00001/* Range object implementation */
2
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003#include "Python.h"
Thomas Woutersefafcea2001-07-09 12:30:54 +00004
Guido van Rossum12d12c51993-10-26 17:58:25 +00005typedef struct {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00006 PyObject_HEAD
Guido van Rossum12d12c51993-10-26 17:58:25 +00007 long start;
8 long step;
9 long len;
Guido van Rossum12d12c51993-10-26 17:58:25 +000010} rangeobject;
11
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000012/* Return number of items in range/xrange (lo, hi, step). step > 0
13 * required. Return a value < 0 if & only if the true value is too
14 * large to fit in a signed long.
15 */
16static long
17get_len_of_range(long lo, long hi, long step)
18{
19 /* -------------------------------------------------------------
20 If lo >= hi, the range is empty.
21 Else if n values are in the range, the last one is
22 lo + (n-1)*step, which must be <= hi-1. Rearranging,
23 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
24 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
25 the RHS is non-negative and so truncation is the same as the
26 floor. Letting M be the largest positive long, the worst case
27 for the RHS numerator is hi=M, lo=-M-1, and then
28 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
29 precision to compute the RHS exactly.
30 ---------------------------------------------------------------*/
31 long n = 0;
32 if (lo < hi) {
33 unsigned long uhi = (unsigned long)hi;
34 unsigned long ulo = (unsigned long)lo;
35 unsigned long diff = uhi - ulo - 1;
36 n = (long)(diff / (unsigned long)step + 1);
37 }
38 return n;
39}
40
41static PyObject *
42range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
43{
Tim Petersfeec4532004-08-08 07:17:39 +000044 rangeobject *obj;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000045 long ilow = 0, ihigh = 0, istep = 1;
46 long n;
47
Georg Brandl02c42872005-08-26 06:42:30 +000048 if (!_PyArg_NoKeywords("xrange()", kw))
49 return NULL;
50
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000051 if (PyTuple_Size(args) <= 1) {
52 if (!PyArg_ParseTuple(args,
53 "l;xrange() requires 1-3 int arguments",
54 &ihigh))
55 return NULL;
56 }
57 else {
58 if (!PyArg_ParseTuple(args,
59 "ll|l;xrange() requires 1-3 int arguments",
60 &ilow, &ihigh, &istep))
61 return NULL;
62 }
63 if (istep == 0) {
64 PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
65 return NULL;
66 }
67 if (istep > 0)
68 n = get_len_of_range(ilow, ihigh, istep);
69 else
70 n = get_len_of_range(ihigh, ilow, -istep);
71 if (n < 0) {
72 PyErr_SetString(PyExc_OverflowError,
73 "xrange() result has too many items");
74 return NULL;
75 }
Tim Petersfeec4532004-08-08 07:17:39 +000076
77 obj = PyObject_New(rangeobject, &PyRange_Type);
78 if (obj == NULL)
79 return NULL;
80 obj->start = ilow;
81 obj->len = n;
82 obj->step = istep;
83 return (PyObject *) obj;
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000084}
85
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +000086PyDoc_STRVAR(range_doc,
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000087"xrange([start,] stop[, step]) -> xrange object\n\
88\n\
89Like range(), but instead of returning a list, returns an object that\n\
Raymond Hettingerd2bef822002-12-11 07:14:03 +000090generates the numbers in the range on demand. For looping, this is \n\
91slightly faster than range() and more memory efficient.");
Raymond Hettingerc4c453f2002-06-05 23:12:45 +000092
Guido van Rossumc0b618a1997-05-02 03:12:38 +000093static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +000094range_item(rangeobject *r, Py_ssize_t i)
Guido van Rossum12d12c51993-10-26 17:58:25 +000095{
Fred Draked9018322002-05-02 19:56:55 +000096 if (i < 0 || i >= r->len) {
97 PyErr_SetString(PyExc_IndexError,
Guido van Rossum5dadf7e1999-01-09 21:40:35 +000098 "xrange object index out of range");
Fred Draked9018322002-05-02 19:56:55 +000099 return NULL;
100 }
Martin v. Löwis18e16552006-02-15 17:27:45 +0000101 return PyInt_FromSsize_t(r->start + (i % r->len) * r->step);
Guido van Rossum12d12c51993-10-26 17:58:25 +0000102}
103
Martin v. Löwis18e16552006-02-15 17:27:45 +0000104static Py_ssize_t
Fred Drake45cfbcc2000-07-09 06:21:27 +0000105range_length(rangeobject *r)
Guido van Rossum12d12c51993-10-26 17:58:25 +0000106{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000107 return (Py_ssize_t)(r->len);
Guido van Rossum7d6aa511993-12-21 22:50:31 +0000108}
109
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000110static PyObject *
Fred Drake45cfbcc2000-07-09 06:21:27 +0000111range_repr(rangeobject *r)
Guido van Rossum12d12c51993-10-26 17:58:25 +0000112{
Barry Warsaw7ce36942001-08-24 18:34:26 +0000113 PyObject *rtn;
Tim Petersd976ab72004-08-08 06:29:10 +0000114
Tim Peters72d421b2000-08-04 03:05:40 +0000115 if (r->start == 0 && r->step == 1)
Barry Warsaw7ce36942001-08-24 18:34:26 +0000116 rtn = PyString_FromFormat("xrange(%ld)",
117 r->start + r->len * r->step);
Tim Peters72d421b2000-08-04 03:05:40 +0000118
119 else if (r->step == 1)
Barry Warsaw7ce36942001-08-24 18:34:26 +0000120 rtn = PyString_FromFormat("xrange(%ld, %ld)",
121 r->start,
122 r->start + r->len * r->step);
Tim Peters72d421b2000-08-04 03:05:40 +0000123
124 else
Barry Warsaw7ce36942001-08-24 18:34:26 +0000125 rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
126 r->start,
127 r->start + r->len * r->step,
128 r->step);
Barry Warsaw7ce36942001-08-24 18:34:26 +0000129 return rtn;
Thomas Woutersefafcea2001-07-09 12:30:54 +0000130}
131
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000132static PySequenceMethods range_as_sequence = {
Martin v. Löwis18e16552006-02-15 17:27:45 +0000133 (lenfunc)range_length, /* sq_length */
Fred Draked9018322002-05-02 19:56:55 +0000134 0, /* sq_concat */
135 0, /* sq_repeat */
Martin v. Löwis18e16552006-02-15 17:27:45 +0000136 (ssizeargfunc)range_item, /* sq_item */
Fred Draked9018322002-05-02 19:56:55 +0000137 0, /* sq_slice */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000138};
139
Jeremy Hylton938ace62002-07-17 16:30:39 +0000140static PyObject * range_iter(PyObject *seq);
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000141static PyObject * range_reverse(PyObject *seq);
142
143PyDoc_STRVAR(reverse_doc,
144"Returns a reverse iterator.");
145
146static PyMethodDef range_methods[] = {
147 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
148 {NULL, NULL} /* sentinel */
149};
Raymond Hettinger48165d42002-06-05 20:08:48 +0000150
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000151PyTypeObject PyRange_Type = {
152 PyObject_HEAD_INIT(&PyType_Type)
Georg Brandl347b3002006-03-30 11:57:00 +0000153 0, /* Number of items for varobject */
154 "xrange", /* Name of this type */
155 sizeof(rangeobject), /* Basic object size */
156 0, /* Item size for varobject */
157 (destructor)PyObject_Del, /* tp_dealloc */
158 0, /* tp_print */
159 0, /* tp_getattr */
160 0, /* tp_setattr */
161 0, /* tp_compare */
162 (reprfunc)range_repr, /* tp_repr */
163 0, /* tp_as_number */
164 &range_as_sequence, /* tp_as_sequence */
165 0, /* tp_as_mapping */
166 0, /* tp_hash */
167 0, /* tp_call */
168 0, /* tp_str */
169 PyObject_GenericGetAttr, /* tp_getattro */
170 0, /* tp_setattro */
171 0, /* tp_as_buffer */
172 Py_TPFLAGS_DEFAULT, /* tp_flags */
173 range_doc, /* tp_doc */
174 0, /* tp_traverse */
175 0, /* tp_clear */
176 0, /* tp_richcompare */
177 0, /* tp_weaklistoffset */
178 range_iter, /* tp_iter */
179 0, /* tp_iternext */
180 range_methods, /* tp_methods */
181 0, /* tp_members */
182 0, /* tp_getset */
183 0, /* tp_base */
184 0, /* tp_dict */
185 0, /* tp_descr_get */
186 0, /* tp_descr_set */
187 0, /* tp_dictoffset */
188 0, /* tp_init */
189 0, /* tp_alloc */
190 range_new, /* tp_new */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000191};
Raymond Hettinger48165d42002-06-05 20:08:48 +0000192
193/*********************** Xrange Iterator **************************/
194
195typedef struct {
196 PyObject_HEAD
197 long index;
198 long start;
199 long step;
200 long len;
201} rangeiterobject;
202
Raymond Hettinger85c20a42003-11-06 14:06:48 +0000203static PyObject *
Raymond Hettinger48165d42002-06-05 20:08:48 +0000204rangeiter_next(rangeiterobject *r)
205{
Tim Petersd976ab72004-08-08 06:29:10 +0000206 if (r->index < r->len)
Raymond Hettinger48165d42002-06-05 20:08:48 +0000207 return PyInt_FromLong(r->start + (r->index++) * r->step);
Raymond Hettinger48165d42002-06-05 20:08:48 +0000208 return NULL;
209}
210
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000211static PyObject *
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000212rangeiter_len(rangeiterobject *r)
213{
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000214 return PyInt_FromLong(r->len - r->index);
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000215}
216
Armin Rigof5b3e362006-02-11 21:32:43 +0000217PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000218
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000219static PyMethodDef rangeiter_methods[] = {
Armin Rigof5b3e362006-02-11 21:32:43 +0000220 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000221 {NULL, NULL} /* sentinel */
222};
Raymond Hettingeref9bf402004-03-10 10:10:42 +0000223
Neal Norwitz56f46f82002-06-06 14:58:21 +0000224static PyTypeObject Pyrangeiter_Type = {
Raymond Hettinger48165d42002-06-05 20:08:48 +0000225 PyObject_HEAD_INIT(&PyType_Type)
226 0, /* ob_size */
Neal Norwitz56f46f82002-06-06 14:58:21 +0000227 "rangeiterator", /* tp_name */
228 sizeof(rangeiterobject), /* tp_basicsize */
Raymond Hettinger48165d42002-06-05 20:08:48 +0000229 0, /* tp_itemsize */
230 /* methods */
231 (destructor)PyObject_Del, /* tp_dealloc */
232 0, /* tp_print */
233 0, /* tp_getattr */
234 0, /* tp_setattr */
235 0, /* tp_compare */
236 0, /* tp_repr */
237 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000238 0, /* tp_as_sequence */
Raymond Hettinger48165d42002-06-05 20:08:48 +0000239 0, /* tp_as_mapping */
240 0, /* tp_hash */
241 0, /* tp_call */
242 0, /* tp_str */
243 PyObject_GenericGetAttr, /* tp_getattro */
244 0, /* tp_setattro */
245 0, /* tp_as_buffer */
246 Py_TPFLAGS_DEFAULT, /* tp_flags */
247 0, /* tp_doc */
248 0, /* tp_traverse */
249 0, /* tp_clear */
250 0, /* tp_richcompare */
251 0, /* tp_weaklistoffset */
Raymond Hettinger1da1dbf2003-03-17 19:46:11 +0000252 PyObject_SelfIter, /* tp_iter */
Raymond Hettinger48165d42002-06-05 20:08:48 +0000253 (iternextfunc)rangeiter_next, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000254 rangeiter_methods, /* tp_methods */
255 0,
Raymond Hettinger48165d42002-06-05 20:08:48 +0000256};
Martin v. Löwis72d20672006-04-11 09:04:12 +0000257
258static PyObject *
259range_iter(PyObject *seq)
260{
261 rangeiterobject *it;
262
263 if (!PyRange_Check(seq)) {
264 PyErr_BadInternalCall();
265 return NULL;
266 }
267 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
268 if (it == NULL)
269 return NULL;
270 it->index = 0;
271 it->start = ((rangeobject *)seq)->start;
272 it->step = ((rangeobject *)seq)->step;
273 it->len = ((rangeobject *)seq)->len;
274 return (PyObject *)it;
275}
276
277static PyObject *
278range_reverse(PyObject *seq)
279{
280 rangeiterobject *it;
281 long start, step, len;
282
283 if (!PyRange_Check(seq)) {
284 PyErr_BadInternalCall();
285 return NULL;
286 }
287 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
288 if (it == NULL)
289 return NULL;
290
291 start = ((rangeobject *)seq)->start;
292 step = ((rangeobject *)seq)->step;
293 len = ((rangeobject *)seq)->len;
294
295 it->index = 0;
296 it->start = start + (len-1) * step;
297 it->step = -step;
298 it->len = len;
299
300 return (PyObject *)it;
301}