summaryrefslogtreecommitdiffstats
path: root/Lib/test/test_heapq.py
Commit message (Collapse)AuthorAgeFilesLines
* Restructure comparison dramatically. There is no longer a defaultGuido van Rossum2006-08-241-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | *ordering* between objects; there is only a default equality test (defined by an object being equal to itself only). Read the comment in object.c. The current implementation never uses a three-way comparison to compute a rich comparison, but it does use a rich comparison to compute a three-way comparison. I'm not quite done ripping out all the calls to PyObject_Compare/Cmp, or replacing tp_compare implementations with tp_richcompare implementations; but much of that has happened (to make most unit tests pass). The following tests still fail, because I need help deciding or understanding: test_codeop -- depends on comparing code objects test_datetime -- need Tim Peters' opinion test_marshal -- depends on comparing code objects test_mutants -- need help understanding it The problem with test_codeop and test_marshal is this: these tests compare two different code objects and expect them to be equal. Is that still a feature we'd like to support? I've temporarily removed the comparison and hash code from code objects, so they use the default (equality by pointer only) comparison. For the other two tests, run them to see for yourself. (There may be more failing test with "-u all".) A general problem with getting lots of these tests to pass is the reality that for object types that have a natural total ordering, implementing __cmp__ is much more convenient than implementing __eq__, __ne__, __lt__, and so on. Should we go back to allowing __cmp__ to provide a total ordering? Should we provide some other way to implement rich comparison with a single method override? Alex proposed a __key__() method; I've considered a __richcmp__() method. Or perhaps __cmp__() just shouldn't be killed off...
* Add key= argument to heapq.nsmallest() and heapq.nlargest().Raymond Hettinger2004-12-021-1/+7
|
* Fix argument order in pure python version of nsmallest() and nlargest().Raymond Hettinger2004-11-291-2/+5
|
* Plug a leak and beef-up test coverage.Raymond Hettinger2004-09-281-0/+149
|
* Whitespace normalization.Tim Peters2004-07-081-1/+0
|
* Exercise some error conditionsNeal Norwitz2004-07-081-0/+10
|
* Reverse argument order for nsmallest() and nlargest().Raymond Hettinger2004-06-151-4/+4
| | | | Reads better when the iterable is a generator expression.
* Install C version of heapq.nsmallest().Raymond Hettinger2004-06-131-6/+19
|
* Improve the memory performance and speed of heapq.nsmallest() by usingRaymond Hettinger2004-06-121-0/+1
| | | | | an alternate algorithm when the number of selected items is small relative to the full iterable.
* Convert test_heapq.py to unittests.Raymond Hettinger2004-06-101-86/+90
|
* SF patch #969791: Add nlargest() and nsmallest() to heapq.Raymond Hettinger2004-06-101-1/+10
|
* Add another test which exercises the whole suite with aRaymond Hettinger2002-12-071-0/+14
| | | | heapsort and verifies the result against list.sort().
* Added new heapreplace(heap, item) function, to pop (and return) theTim Peters2002-08-031-3/+2
| | | | | currently-smallest value, and add item, in one gulp. See the second N-Best algorithm in the test suite for a natural use.
* Minor fiddling, including a simple class to implement a heap iteratorTim Peters2002-08-031-5/+18
| | | | | in the test file. I have docs for heapq.heapify ready to check in, but Jack appears to have left behind a stale lock in the Doc/lib directory.
* Hmm! I thought I checked this in before! Oh well.Tim Peters2002-08-021-1/+19
| | | | | | | | | | | | Added new heapify() function, which transforms an arbitrary list into a heap in linear time; that's a fundamental tool for using heaps in real life <wink>. Added heapyify() test. Added a "less naive" N-best algorithm to the test suite, and noted that this could actually go much faster (building on heapify()) if we had max-heaps instead of min-heaps (the iterative method is appropriate when all the data isn't known in advance, but when it is known in advance the tradeoffs get murkier).
* check_invariant(): Use the same child->parent "formula" used by heapq.py.Tim Peters2002-08-021-2/+2
|
* Don't use true division where int division was intended. For that matter,Tim Peters2002-08-021-1/+1
| | | | don't use division at all.
* Adding the heap queue algorithm, per discussion in python-dev lastGuido van Rossum2002-08-021-0/+48
week.
generated by cgit v0.12 at 2025-03-02 07:29:25 (GMT)