Added updates with respect to recent changes to TimedRotatingFileHandler.
[python.git] / Modules / _heapqmodule.c
blob06ed74320ad7e427123b557e467fb0b411ad380f
1 /* Drop in replacement for heapq.py
3 C implementation derived directly from heapq.py in Py2.3
4 which was written by Kevin O'Connor, augmented by Tim Peters,
5 annotated by François Pinard, and converted to C by Raymond Hettinger.
7 */
9 #include "Python.h"
11 static int
12 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
14 PyObject *newitem, *parent;
15 int cmp;
16 Py_ssize_t parentpos;
18 assert(PyList_Check(heap));
19 if (pos >= PyList_GET_SIZE(heap)) {
20 PyErr_SetString(PyExc_IndexError, "index out of range");
21 return -1;
24 newitem = PyList_GET_ITEM(heap, pos);
25 Py_INCREF(newitem);
26 /* Follow the path to the root, moving parents down until finding
27 a place newitem fits. */
28 while (pos > startpos){
29 parentpos = (pos - 1) >> 1;
30 parent = PyList_GET_ITEM(heap, parentpos);
31 cmp = PyObject_RichCompareBool(parent, newitem, Py_LE);
32 if (cmp == -1) {
33 Py_DECREF(newitem);
34 return -1;
36 if (cmp == 1)
37 break;
38 Py_INCREF(parent);
39 Py_DECREF(PyList_GET_ITEM(heap, pos));
40 PyList_SET_ITEM(heap, pos, parent);
41 pos = parentpos;
43 Py_DECREF(PyList_GET_ITEM(heap, pos));
44 PyList_SET_ITEM(heap, pos, newitem);
45 return 0;
48 static int
49 _siftup(PyListObject *heap, Py_ssize_t pos)
51 Py_ssize_t startpos, endpos, childpos, rightpos;
52 int cmp;
53 PyObject *newitem, *tmp;
55 assert(PyList_Check(heap));
56 endpos = PyList_GET_SIZE(heap);
57 startpos = pos;
58 if (pos >= endpos) {
59 PyErr_SetString(PyExc_IndexError, "index out of range");
60 return -1;
62 newitem = PyList_GET_ITEM(heap, pos);
63 Py_INCREF(newitem);
65 /* Bubble up the smaller child until hitting a leaf. */
66 childpos = 2*pos + 1; /* leftmost child position */
67 while (childpos < endpos) {
68 /* Set childpos to index of smaller child. */
69 rightpos = childpos + 1;
70 if (rightpos < endpos) {
71 cmp = PyObject_RichCompareBool(
72 PyList_GET_ITEM(heap, rightpos),
73 PyList_GET_ITEM(heap, childpos),
74 Py_LE);
75 if (cmp == -1) {
76 Py_DECREF(newitem);
77 return -1;
79 if (cmp == 1)
80 childpos = rightpos;
82 /* Move the smaller child up. */
83 tmp = PyList_GET_ITEM(heap, childpos);
84 Py_INCREF(tmp);
85 Py_DECREF(PyList_GET_ITEM(heap, pos));
86 PyList_SET_ITEM(heap, pos, tmp);
87 pos = childpos;
88 childpos = 2*pos + 1;
91 /* The leaf at pos is empty now. Put newitem there, and and bubble
92 it up to its final resting place (by sifting its parents down). */
93 Py_DECREF(PyList_GET_ITEM(heap, pos));
94 PyList_SET_ITEM(heap, pos, newitem);
95 return _siftdown(heap, startpos, pos);
98 static PyObject *
99 heappush(PyObject *self, PyObject *args)
101 PyObject *heap, *item;
103 if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
104 return NULL;
106 if (!PyList_Check(heap)) {
107 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
108 return NULL;
111 if (PyList_Append(heap, item) == -1)
112 return NULL;
114 if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
115 return NULL;
116 Py_INCREF(Py_None);
117 return Py_None;
120 PyDoc_STRVAR(heappush_doc,
121 "Push item onto heap, maintaining the heap invariant.");
123 static PyObject *
124 heappop(PyObject *self, PyObject *heap)
126 PyObject *lastelt, *returnitem;
127 Py_ssize_t n;
129 if (!PyList_Check(heap)) {
130 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
131 return NULL;
134 /* # raises appropriate IndexError if heap is empty */
135 n = PyList_GET_SIZE(heap);
136 if (n == 0) {
137 PyErr_SetString(PyExc_IndexError, "index out of range");
138 return NULL;
141 lastelt = PyList_GET_ITEM(heap, n-1) ;
142 Py_INCREF(lastelt);
143 PyList_SetSlice(heap, n-1, n, NULL);
144 n--;
146 if (!n)
147 return lastelt;
148 returnitem = PyList_GET_ITEM(heap, 0);
149 PyList_SET_ITEM(heap, 0, lastelt);
150 if (_siftup((PyListObject *)heap, 0) == -1) {
151 Py_DECREF(returnitem);
152 return NULL;
154 return returnitem;
157 PyDoc_STRVAR(heappop_doc,
158 "Pop the smallest item off the heap, maintaining the heap invariant.");
160 static PyObject *
161 heapreplace(PyObject *self, PyObject *args)
163 PyObject *heap, *item, *returnitem;
165 if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
166 return NULL;
168 if (!PyList_Check(heap)) {
169 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
170 return NULL;
173 if (PyList_GET_SIZE(heap) < 1) {
174 PyErr_SetString(PyExc_IndexError, "index out of range");
175 return NULL;
178 returnitem = PyList_GET_ITEM(heap, 0);
179 Py_INCREF(item);
180 PyList_SET_ITEM(heap, 0, item);
181 if (_siftup((PyListObject *)heap, 0) == -1) {
182 Py_DECREF(returnitem);
183 return NULL;
185 return returnitem;
188 PyDoc_STRVAR(heapreplace_doc,
189 "Pop and return the current smallest value, and add the new item.\n\
191 This is more efficient than heappop() followed by heappush(), and can be\n\
192 more appropriate when using a fixed-size heap. Note that the value\n\
193 returned may be larger than item! That constrains reasonable uses of\n\
194 this routine unless written as part of a conditional replacement:\n\n\
195 if item > heap[0]:\n\
196 item = heapreplace(heap, item)\n");
198 static PyObject *
199 heappushpop(PyObject *self, PyObject *args)
201 PyObject *heap, *item, *returnitem;
202 int cmp;
204 if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
205 return NULL;
207 if (!PyList_Check(heap)) {
208 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
209 return NULL;
212 if (PyList_GET_SIZE(heap) < 1) {
213 Py_INCREF(item);
214 return item;
217 cmp = PyObject_RichCompareBool(item, PyList_GET_ITEM(heap, 0), Py_LE);
218 if (cmp == -1)
219 return NULL;
220 if (cmp == 1) {
221 Py_INCREF(item);
222 return item;
225 returnitem = PyList_GET_ITEM(heap, 0);
226 Py_INCREF(item);
227 PyList_SET_ITEM(heap, 0, item);
228 if (_siftup((PyListObject *)heap, 0) == -1) {
229 Py_DECREF(returnitem);
230 return NULL;
232 return returnitem;
235 PyDoc_STRVAR(heappushpop_doc,
236 "Push item on the heap, then pop and return the smallest item\n\
237 from the heap. The combined action runs more efficiently than\n\
238 heappush() followed by a separate call to heappop().");
240 static PyObject *
241 heapify(PyObject *self, PyObject *heap)
243 Py_ssize_t i, n;
245 if (!PyList_Check(heap)) {
246 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
247 return NULL;
250 n = PyList_GET_SIZE(heap);
251 /* Transform bottom-up. The largest index there's any point to
252 looking at is the largest with a child index in-range, so must
253 have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
254 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
255 n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
256 and that's again n//2-1.
258 for (i=n/2-1 ; i>=0 ; i--)
259 if(_siftup((PyListObject *)heap, i) == -1)
260 return NULL;
261 Py_INCREF(Py_None);
262 return Py_None;
265 PyDoc_STRVAR(heapify_doc,
266 "Transform list into a heap, in-place, in O(len(heap)) time.");
268 static PyObject *
269 nlargest(PyObject *self, PyObject *args)
271 PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
272 Py_ssize_t i, n;
274 if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
275 return NULL;
277 it = PyObject_GetIter(iterable);
278 if (it == NULL)
279 return NULL;
281 heap = PyList_New(0);
282 if (heap == NULL)
283 goto fail;
285 for (i=0 ; i<n ; i++ ){
286 elem = PyIter_Next(it);
287 if (elem == NULL) {
288 if (PyErr_Occurred())
289 goto fail;
290 else
291 goto sortit;
293 if (PyList_Append(heap, elem) == -1) {
294 Py_DECREF(elem);
295 goto fail;
297 Py_DECREF(elem);
299 if (PyList_GET_SIZE(heap) == 0)
300 goto sortit;
302 for (i=n/2-1 ; i>=0 ; i--)
303 if(_siftup((PyListObject *)heap, i) == -1)
304 goto fail;
306 sol = PyList_GET_ITEM(heap, 0);
307 while (1) {
308 elem = PyIter_Next(it);
309 if (elem == NULL) {
310 if (PyErr_Occurred())
311 goto fail;
312 else
313 goto sortit;
315 if (PyObject_RichCompareBool(elem, sol, Py_LE)) {
316 Py_DECREF(elem);
317 continue;
319 oldelem = PyList_GET_ITEM(heap, 0);
320 PyList_SET_ITEM(heap, 0, elem);
321 Py_DECREF(oldelem);
322 if (_siftup((PyListObject *)heap, 0) == -1)
323 goto fail;
324 sol = PyList_GET_ITEM(heap, 0);
326 sortit:
327 if (PyList_Sort(heap) == -1)
328 goto fail;
329 if (PyList_Reverse(heap) == -1)
330 goto fail;
331 Py_DECREF(it);
332 return heap;
334 fail:
335 Py_DECREF(it);
336 Py_XDECREF(heap);
337 return NULL;
340 PyDoc_STRVAR(nlargest_doc,
341 "Find the n largest elements in a dataset.\n\
343 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
345 static int
346 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
348 PyObject *newitem, *parent;
349 int cmp;
350 Py_ssize_t parentpos;
352 assert(PyList_Check(heap));
353 if (pos >= PyList_GET_SIZE(heap)) {
354 PyErr_SetString(PyExc_IndexError, "index out of range");
355 return -1;
358 newitem = PyList_GET_ITEM(heap, pos);
359 Py_INCREF(newitem);
360 /* Follow the path to the root, moving parents down until finding
361 a place newitem fits. */
362 while (pos > startpos){
363 parentpos = (pos - 1) >> 1;
364 parent = PyList_GET_ITEM(heap, parentpos);
365 cmp = PyObject_RichCompareBool(newitem, parent, Py_LE);
366 if (cmp == -1) {
367 Py_DECREF(newitem);
368 return -1;
370 if (cmp == 1)
371 break;
372 Py_INCREF(parent);
373 Py_DECREF(PyList_GET_ITEM(heap, pos));
374 PyList_SET_ITEM(heap, pos, parent);
375 pos = parentpos;
377 Py_DECREF(PyList_GET_ITEM(heap, pos));
378 PyList_SET_ITEM(heap, pos, newitem);
379 return 0;
382 static int
383 _siftupmax(PyListObject *heap, Py_ssize_t pos)
385 Py_ssize_t startpos, endpos, childpos, rightpos;
386 int cmp;
387 PyObject *newitem, *tmp;
389 assert(PyList_Check(heap));
390 endpos = PyList_GET_SIZE(heap);
391 startpos = pos;
392 if (pos >= endpos) {
393 PyErr_SetString(PyExc_IndexError, "index out of range");
394 return -1;
396 newitem = PyList_GET_ITEM(heap, pos);
397 Py_INCREF(newitem);
399 /* Bubble up the smaller child until hitting a leaf. */
400 childpos = 2*pos + 1; /* leftmost child position */
401 while (childpos < endpos) {
402 /* Set childpos to index of smaller child. */
403 rightpos = childpos + 1;
404 if (rightpos < endpos) {
405 cmp = PyObject_RichCompareBool(
406 PyList_GET_ITEM(heap, childpos),
407 PyList_GET_ITEM(heap, rightpos),
408 Py_LE);
409 if (cmp == -1) {
410 Py_DECREF(newitem);
411 return -1;
413 if (cmp == 1)
414 childpos = rightpos;
416 /* Move the smaller child up. */
417 tmp = PyList_GET_ITEM(heap, childpos);
418 Py_INCREF(tmp);
419 Py_DECREF(PyList_GET_ITEM(heap, pos));
420 PyList_SET_ITEM(heap, pos, tmp);
421 pos = childpos;
422 childpos = 2*pos + 1;
425 /* The leaf at pos is empty now. Put newitem there, and and bubble
426 it up to its final resting place (by sifting its parents down). */
427 Py_DECREF(PyList_GET_ITEM(heap, pos));
428 PyList_SET_ITEM(heap, pos, newitem);
429 return _siftdownmax(heap, startpos, pos);
432 static PyObject *
433 nsmallest(PyObject *self, PyObject *args)
435 PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
436 Py_ssize_t i, n;
438 if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
439 return NULL;
441 it = PyObject_GetIter(iterable);
442 if (it == NULL)
443 return NULL;
445 heap = PyList_New(0);
446 if (heap == NULL)
447 goto fail;
449 for (i=0 ; i<n ; i++ ){
450 elem = PyIter_Next(it);
451 if (elem == NULL) {
452 if (PyErr_Occurred())
453 goto fail;
454 else
455 goto sortit;
457 if (PyList_Append(heap, elem) == -1) {
458 Py_DECREF(elem);
459 goto fail;
461 Py_DECREF(elem);
463 n = PyList_GET_SIZE(heap);
464 if (n == 0)
465 goto sortit;
467 for (i=n/2-1 ; i>=0 ; i--)
468 if(_siftupmax((PyListObject *)heap, i) == -1)
469 goto fail;
471 los = PyList_GET_ITEM(heap, 0);
472 while (1) {
473 elem = PyIter_Next(it);
474 if (elem == NULL) {
475 if (PyErr_Occurred())
476 goto fail;
477 else
478 goto sortit;
480 if (PyObject_RichCompareBool(los, elem, Py_LE)) {
481 Py_DECREF(elem);
482 continue;
485 oldelem = PyList_GET_ITEM(heap, 0);
486 PyList_SET_ITEM(heap, 0, elem);
487 Py_DECREF(oldelem);
488 if (_siftupmax((PyListObject *)heap, 0) == -1)
489 goto fail;
490 los = PyList_GET_ITEM(heap, 0);
493 sortit:
494 if (PyList_Sort(heap) == -1)
495 goto fail;
496 Py_DECREF(it);
497 return heap;
499 fail:
500 Py_DECREF(it);
501 Py_XDECREF(heap);
502 return NULL;
505 PyDoc_STRVAR(nsmallest_doc,
506 "Find the n smallest elements in a dataset.\n\
508 Equivalent to: sorted(iterable)[:n]\n");
510 static PyMethodDef heapq_methods[] = {
511 {"heappush", (PyCFunction)heappush,
512 METH_VARARGS, heappush_doc},
513 {"heappushpop", (PyCFunction)heappushpop,
514 METH_VARARGS, heappushpop_doc},
515 {"heappop", (PyCFunction)heappop,
516 METH_O, heappop_doc},
517 {"heapreplace", (PyCFunction)heapreplace,
518 METH_VARARGS, heapreplace_doc},
519 {"heapify", (PyCFunction)heapify,
520 METH_O, heapify_doc},
521 {"nlargest", (PyCFunction)nlargest,
522 METH_VARARGS, nlargest_doc},
523 {"nsmallest", (PyCFunction)nsmallest,
524 METH_VARARGS, nsmallest_doc},
525 {NULL, NULL} /* sentinel */
528 PyDoc_STRVAR(module_doc,
529 "Heap queue algorithm (a.k.a. priority queue).\n\
531 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
532 all k, counting elements from 0. For the sake of comparison,\n\
533 non-existing elements are considered to be infinite. The interesting\n\
534 property of a heap is that a[0] is always its smallest element.\n\
536 Usage:\n\
538 heap = [] # creates an empty heap\n\
539 heappush(heap, item) # pushes a new item on the heap\n\
540 item = heappop(heap) # pops the smallest item from the heap\n\
541 item = heap[0] # smallest item on the heap without popping it\n\
542 heapify(x) # transforms list into a heap, in-place, in linear time\n\
543 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
544 # new item; the heap size is unchanged\n\
546 Our API differs from textbook heap algorithms as follows:\n\
548 - We use 0-based indexing. This makes the relationship between the\n\
549 index for a node and the indexes for its children slightly less\n\
550 obvious, but is more suitable since Python uses 0-based indexing.\n\
552 - Our heappop() method returns the smallest item, not the largest.\n\
554 These two make it possible to view the heap as a regular Python list\n\
555 without surprises: heap[0] is the smallest item, and heap.sort()\n\
556 maintains the heap invariant!\n");
559 PyDoc_STRVAR(__about__,
560 "Heap queues\n\
562 [explanation by François Pinard]\n\
564 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
565 all k, counting elements from 0. For the sake of comparison,\n\
566 non-existing elements are considered to be infinite. The interesting\n\
567 property of a heap is that a[0] is always its smallest element.\n"
568 "\n\
569 The strange invariant above is meant to be an efficient memory\n\
570 representation for a tournament. The numbers below are `k', not a[k]:\n\
572 0\n\
574 1 2\n\
576 3 4 5 6\n\
578 7 8 9 10 11 12 13 14\n\
580 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
583 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
584 an usual binary tournament we see in sports, each cell is the winner\n\
585 over the two cells it tops, and we can trace the winner down the tree\n\
586 to see all opponents s/he had. However, in many computer applications\n\
587 of such tournaments, we do not need to trace the history of a winner.\n\
588 To be more memory efficient, when a winner is promoted, we try to\n\
589 replace it by something else at a lower level, and the rule becomes\n\
590 that a cell and the two cells it tops contain three different items,\n\
591 but the top cell \"wins\" over the two topped cells.\n"
592 "\n\
593 If this heap invariant is protected at all time, index 0 is clearly\n\
594 the overall winner. The simplest algorithmic way to remove it and\n\
595 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
596 diagram above) into the 0 position, and then percolate this new 0 down\n\
597 the tree, exchanging values, until the invariant is re-established.\n\
598 This is clearly logarithmic on the total number of items in the tree.\n\
599 By iterating over all items, you get an O(n ln n) sort.\n"
600 "\n\
601 A nice feature of this sort is that you can efficiently insert new\n\
602 items while the sort is going on, provided that the inserted items are\n\
603 not \"better\" than the last 0'th element you extracted. This is\n\
604 especially useful in simulation contexts, where the tree holds all\n\
605 incoming events, and the \"win\" condition means the smallest scheduled\n\
606 time. When an event schedule other events for execution, they are\n\
607 scheduled into the future, so they can easily go into the heap. So, a\n\
608 heap is a good structure for implementing schedulers (this is what I\n\
609 used for my MIDI sequencer :-).\n"
610 "\n\
611 Various structures for implementing schedulers have been extensively\n\
612 studied, and heaps are good for this, as they are reasonably speedy,\n\
613 the speed is almost constant, and the worst case is not much different\n\
614 than the average case. However, there are other representations which\n\
615 are more efficient overall, yet the worst cases might be terrible.\n"
616 "\n\
617 Heaps are also very useful in big disk sorts. You most probably all\n\
618 know that a big sort implies producing \"runs\" (which are pre-sorted\n\
619 sequences, which size is usually related to the amount of CPU memory),\n\
620 followed by a merging passes for these runs, which merging is often\n\
621 very cleverly organised[1]. It is very important that the initial\n\
622 sort produces the longest runs possible. Tournaments are a good way\n\
623 to that. If, using all the memory available to hold a tournament, you\n\
624 replace and percolate items that happen to fit the current run, you'll\n\
625 produce runs which are twice the size of the memory for random input,\n\
626 and much better for input fuzzily ordered.\n"
627 "\n\
628 Moreover, if you output the 0'th item on disk and get an input which\n\
629 may not fit in the current tournament (because the value \"wins\" over\n\
630 the last output value), it cannot fit in the heap, so the size of the\n\
631 heap decreases. The freed memory could be cleverly reused immediately\n\
632 for progressively building a second heap, which grows at exactly the\n\
633 same rate the first heap is melting. When the first heap completely\n\
634 vanishes, you switch heaps and start a new run. Clever and quite\n\
635 effective!\n\
637 In a word, heaps are useful memory structures to know. I use them in\n\
638 a few applications, and I think it is good to keep a `heap' module\n\
639 around. :-)\n"
640 "\n\
641 --------------------\n\
642 [1] The disk balancing algorithms which are current, nowadays, are\n\
643 more annoying than clever, and this is a consequence of the seeking\n\
644 capabilities of the disks. On devices which cannot seek, like big\n\
645 tape drives, the story was quite different, and one had to be very\n\
646 clever to ensure (far in advance) that each tape movement will be the\n\
647 most effective possible (that is, will best participate at\n\
648 \"progressing\" the merge). Some tapes were even able to read\n\
649 backwards, and this was also used to avoid the rewinding time.\n\
650 Believe me, real good tape sorts were quite spectacular to watch!\n\
651 From all times, sorting has always been a Great Art! :-)\n");
653 PyMODINIT_FUNC
654 init_heapq(void)
656 PyObject *m;
658 m = Py_InitModule3("_heapq", heapq_methods, module_doc);
659 if (m == NULL)
660 return;
661 PyModule_AddObject(m, "__about__", PyString_FromString(__about__));