Hello community, here is the log from the commit of package python-HeapDict for openSUSE:Factory checked in at 2019-09-26 20:40:03 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/python-HeapDict (Old) and /work/SRC/openSUSE:Factory/.python-HeapDict.new.2352 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "python-HeapDict" Thu Sep 26 20:40:03 2019 rev:3 rq:732884 version:1.0.1 Changes: -------- --- /work/SRC/openSUSE:Factory/python-HeapDict/python-HeapDict.changes 2018-12-07 14:39:11.314789524 +0100 +++ /work/SRC/openSUSE:Factory/.python-HeapDict.new.2352/python-HeapDict.changes 2019-09-26 20:40:17.918692449 +0200 @@ -1,0 +2,6 @@ +Tue Sep 24 09:15:23 UTC 2019 - Tomáš Chvátal <tchva...@suse.com> + +- Update to 1.0.1: + * no upstream changelog + +------------------------------------------------------------------- Old: ---- HeapDict-1.0.0.tar.gz New: ---- HeapDict-1.0.1.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ python-HeapDict.spec ++++++ --- /var/tmp/diff_new_pack.jbHckN/_old 2019-09-26 20:40:18.662690461 +0200 +++ /var/tmp/diff_new_pack.jbHckN/_new 2019-09-26 20:40:18.666690451 +0200 @@ -1,7 +1,7 @@ # # spec file for package python-HeapDict # -# Copyright (c) 2018 SUSE LINUX GmbH, Nuernberg, Germany. +# Copyright (c) 2019 SUSE LINUX GmbH, Nuernberg, Germany. # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -17,14 +17,8 @@ %{?!python_module:%define python_module() python-%{**} python3-%{**}} -# required test package not available on SLE -%if 0%{?is_opensuse} -%bcond_without test -%else -%bcond_with test -%endif Name: python-HeapDict -Version: 1.0.0 +Version: 1.0.1 Release: 0 Summary: A heap with decrease-key and increase-key operations License: BSD-3-Clause @@ -34,13 +28,11 @@ BuildRequires: %{python_module setuptools} BuildRequires: fdupes BuildRequires: python-rpm-macros -BuildArch: noarch -%if %{with test} # These packages contain module test from stdlib, # it has nothing to do with this package being noarch BuildRequires: python2-devel BuildRequires: python3-testsuite -%endif +BuildArch: noarch %python_subpackages %description @@ -63,10 +55,8 @@ %python_install %python_expand %fdupes %{buildroot}%{$python_sitelib} -%if %{with test} %check %python_exec test_heap.py -%endif %files %{python_files} %license LICENSE ++++++ HeapDict-1.0.0.tar.gz -> HeapDict-1.0.1.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/HeapDict.egg-info/PKG-INFO new/HeapDict-1.0.1/HeapDict.egg-info/PKG-INFO --- old/HeapDict-1.0.0/HeapDict.egg-info/PKG-INFO 2009-10-16 17:37:51.000000000 +0200 +++ new/HeapDict-1.0.1/HeapDict.egg-info/PKG-INFO 2019-09-09 20:56:37.000000000 +0200 @@ -1,6 +1,6 @@ Metadata-Version: 1.1 Name: HeapDict -Version: 1.0.0 +Version: 1.0.1 Summary: a heap with decrease-key and increase-key operations Home-page: http://stutzbachenterprises.com/ Author: Stutzbach Enterprises, LLC @@ -15,21 +15,21 @@ :: - hd = heapdict() - hd[obj1] = priority1 - hd[obj2] = priority2 - # ... - obj = hd.pop() + hd = heapdict() + hd[obj1] = priority1 + hd[obj2] = priority2 + # ... + (obj, priority) = hd.popitem() Compared to an ordinary dict, a heapdict has the following differences: popitem(): - Remove and return the (key, priority) pair with the lowest - priority, instead of a random object. + Remove and return the (key, priority) pair with the lowest + priority, instead of a random object. peekitem(): - Return the (key, priority) pair with the lowest priority, without - removing it. + Return the (key, priority) pair with the lowest priority, without + removing it. Unlike the Python standard library's heapq module, the heapdict supports efficiently changing the priority of an existing object diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/HeapDict.egg-info/SOURCES.txt new/HeapDict-1.0.1/HeapDict.egg-info/SOURCES.txt --- old/HeapDict-1.0.0/HeapDict.egg-info/SOURCES.txt 2009-10-16 17:37:51.000000000 +0200 +++ new/HeapDict-1.0.1/HeapDict.egg-info/SOURCES.txt 2019-09-09 20:56:37.000000000 +0200 @@ -1,7 +1,6 @@ LICENSE MANIFEST.in README.rst -ez_setup.py heapdict.py setup.py test_heap.py @@ -9,5 +8,4 @@ HeapDict.egg-info/SOURCES.txt HeapDict.egg-info/dependency_links.txt HeapDict.egg-info/top_level.txt -HeapDict.egg-info/zip-safe -heapdict.egg-info/SOURCES.txt \ No newline at end of file +HeapDict.egg-info/zip-safe \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/MANIFEST.in new/HeapDict-1.0.1/MANIFEST.in --- old/HeapDict-1.0.0/MANIFEST.in 2009-10-16 16:18:02.000000000 +0200 +++ new/HeapDict-1.0.1/MANIFEST.in 2019-09-09 20:39:58.000000000 +0200 @@ -1,5 +1,4 @@ include heapdict.py -include ez_setup.py include LICENSE include test_heap.py include setup.py diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/PKG-INFO new/HeapDict-1.0.1/PKG-INFO --- old/HeapDict-1.0.0/PKG-INFO 2009-10-16 17:37:51.000000000 +0200 +++ new/HeapDict-1.0.1/PKG-INFO 2019-09-09 20:56:38.000000000 +0200 @@ -1,6 +1,6 @@ Metadata-Version: 1.1 Name: HeapDict -Version: 1.0.0 +Version: 1.0.1 Summary: a heap with decrease-key and increase-key operations Home-page: http://stutzbachenterprises.com/ Author: Stutzbach Enterprises, LLC @@ -15,21 +15,21 @@ :: - hd = heapdict() - hd[obj1] = priority1 - hd[obj2] = priority2 - # ... - obj = hd.pop() + hd = heapdict() + hd[obj1] = priority1 + hd[obj2] = priority2 + # ... + (obj, priority) = hd.popitem() Compared to an ordinary dict, a heapdict has the following differences: popitem(): - Remove and return the (key, priority) pair with the lowest - priority, instead of a random object. + Remove and return the (key, priority) pair with the lowest + priority, instead of a random object. peekitem(): - Return the (key, priority) pair with the lowest priority, without - removing it. + Return the (key, priority) pair with the lowest priority, without + removing it. Unlike the Python standard library's heapq module, the heapdict supports efficiently changing the priority of an existing object diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/README.rst new/HeapDict-1.0.1/README.rst --- old/HeapDict-1.0.0/README.rst 2009-10-16 17:37:24.000000000 +0200 +++ new/HeapDict-1.0.1/README.rst 2019-09-09 19:47:12.000000000 +0200 @@ -11,7 +11,7 @@ hd[obj1] = priority1 hd[obj2] = priority2 # ... - obj = hd.pop() + (obj, priority) = hd.popitem() Compared to an ordinary dict, a heapdict has the following differences: diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/ez_setup.py new/HeapDict-1.0.1/ez_setup.py --- old/HeapDict-1.0.0/ez_setup.py 2009-03-30 23:21:25.000000000 +0200 +++ new/HeapDict-1.0.1/ez_setup.py 1970-01-01 01:00:00.000000000 +0100 @@ -1,276 +0,0 @@ -#!python -"""Bootstrap setuptools installation - -If you want to use setuptools in your package's setup.py, just include this -file in the same directory with it, and add this to the top of your setup.py:: - - from ez_setup import use_setuptools - use_setuptools() - -If you want to require a specific version of setuptools, set a download -mirror, or use an alternate download directory, you can do so by supplying -the appropriate options to ``use_setuptools()``. - -This file can also be run as a script to install or upgrade setuptools. -""" -import sys -DEFAULT_VERSION = "0.6c9" -DEFAULT_URL = "http://pypi.python.org/packages/%s/s/setuptools/" % sys.version[:3] - -md5_data = { - 'setuptools-0.6b1-py2.3.egg': '8822caf901250d848b996b7f25c6e6ca', - 'setuptools-0.6b1-py2.4.egg': 'b79a8a403e4502fbb85ee3f1941735cb', - 'setuptools-0.6b2-py2.3.egg': '5657759d8a6d8fc44070a9d07272d99b', - 'setuptools-0.6b2-py2.4.egg': '4996a8d169d2be661fa32a6e52e4f82a', - 'setuptools-0.6b3-py2.3.egg': 'bb31c0fc7399a63579975cad9f5a0618', - 'setuptools-0.6b3-py2.4.egg': '38a8c6b3d6ecd22247f179f7da669fac', - 'setuptools-0.6b4-py2.3.egg': '62045a24ed4e1ebc77fe039aa4e6f7e5', - 'setuptools-0.6b4-py2.4.egg': '4cb2a185d228dacffb2d17f103b3b1c4', - 'setuptools-0.6c1-py2.3.egg': 'b3f2b5539d65cb7f74ad79127f1a908c', - 'setuptools-0.6c1-py2.4.egg': 'b45adeda0667d2d2ffe14009364f2a4b', - 'setuptools-0.6c2-py2.3.egg': 'f0064bf6aa2b7d0f3ba0b43f20817c27', - 'setuptools-0.6c2-py2.4.egg': '616192eec35f47e8ea16cd6a122b7277', - 'setuptools-0.6c3-py2.3.egg': 'f181fa125dfe85a259c9cd6f1d7b78fa', - 'setuptools-0.6c3-py2.4.egg': 'e0ed74682c998bfb73bf803a50e7b71e', - 'setuptools-0.6c3-py2.5.egg': 'abef16fdd61955514841c7c6bd98965e', - 'setuptools-0.6c4-py2.3.egg': 'b0b9131acab32022bfac7f44c5d7971f', - 'setuptools-0.6c4-py2.4.egg': '2a1f9656d4fbf3c97bf946c0a124e6e2', - 'setuptools-0.6c4-py2.5.egg': '8f5a052e32cdb9c72bcf4b5526f28afc', - 'setuptools-0.6c5-py2.3.egg': 'ee9fd80965da04f2f3e6b3576e9d8167', - 'setuptools-0.6c5-py2.4.egg': 'afe2adf1c01701ee841761f5bcd8aa64', - 'setuptools-0.6c5-py2.5.egg': 'a8d3f61494ccaa8714dfed37bccd3d5d', - 'setuptools-0.6c6-py2.3.egg': '35686b78116a668847237b69d549ec20', - 'setuptools-0.6c6-py2.4.egg': '3c56af57be3225019260a644430065ab', - 'setuptools-0.6c6-py2.5.egg': 'b2f8a7520709a5b34f80946de5f02f53', - 'setuptools-0.6c7-py2.3.egg': '209fdf9adc3a615e5115b725658e13e2', - 'setuptools-0.6c7-py2.4.egg': '5a8f954807d46a0fb67cf1f26c55a82e', - 'setuptools-0.6c7-py2.5.egg': '45d2ad28f9750e7434111fde831e8372', - 'setuptools-0.6c8-py2.3.egg': '50759d29b349db8cfd807ba8303f1902', - 'setuptools-0.6c8-py2.4.egg': 'cba38d74f7d483c06e9daa6070cce6de', - 'setuptools-0.6c8-py2.5.egg': '1721747ee329dc150590a58b3e1ac95b', - 'setuptools-0.6c9-py2.3.egg': 'a83c4020414807b496e4cfbe08507c03', - 'setuptools-0.6c9-py2.4.egg': '260a2be2e5388d66bdaee06abec6342a', - 'setuptools-0.6c9-py2.5.egg': 'fe67c3e5a17b12c0e7c541b7ea43a8e6', - 'setuptools-0.6c9-py2.6.egg': 'ca37b1ff16fa2ede6e19383e7b59245a', -} - -import sys, os -try: from hashlib import md5 -except ImportError: from md5 import md5 - -def _validate_md5(egg_name, data): - if egg_name in md5_data: - digest = md5(data).hexdigest() - if digest != md5_data[egg_name]: - print >>sys.stderr, ( - "md5 validation of %s failed! (Possible download problem?)" - % egg_name - ) - sys.exit(2) - return data - -def use_setuptools( - version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir, - download_delay=15 -): - """Automatically find/download setuptools and make it available on sys.path - - `version` should be a valid setuptools version number that is available - as an egg for download under the `download_base` URL (which should end with - a '/'). `to_dir` is the directory where setuptools will be downloaded, if - it is not already available. If `download_delay` is specified, it should - be the number of seconds that will be paused before initiating a download, - should one be required. If an older version of setuptools is installed, - this routine will print a message to ``sys.stderr`` and raise SystemExit in - an attempt to abort the calling script. - """ - was_imported = 'pkg_resources' in sys.modules or 'setuptools' in sys.modules - def do_download(): - egg = download_setuptools(version, download_base, to_dir, download_delay) - sys.path.insert(0, egg) - import setuptools; setuptools.bootstrap_install_from = egg - try: - import pkg_resources - except ImportError: - return do_download() - try: - pkg_resources.require("setuptools>="+version); return - except pkg_resources.VersionConflict, e: - if was_imported: - print >>sys.stderr, ( - "The required version of setuptools (>=%s) is not available, and\n" - "can't be installed while this script is running. Please install\n" - " a more recent version first, using 'easy_install -U setuptools'." - "\n\n(Currently using %r)" - ) % (version, e.args[0]) - sys.exit(2) - else: - del pkg_resources, sys.modules['pkg_resources'] # reload ok - return do_download() - except pkg_resources.DistributionNotFound: - return do_download() - -def download_setuptools( - version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir, - delay = 15 -): - """Download setuptools from a specified location and return its filename - - `version` should be a valid setuptools version number that is available - as an egg for download under the `download_base` URL (which should end - with a '/'). `to_dir` is the directory where the egg will be downloaded. - `delay` is the number of seconds to pause before an actual download attempt. - """ - import urllib2, shutil - egg_name = "setuptools-%s-py%s.egg" % (version,sys.version[:3]) - url = download_base + egg_name - saveto = os.path.join(to_dir, egg_name) - src = dst = None - if not os.path.exists(saveto): # Avoid repeated downloads - try: - from distutils import log - if delay: - log.warn(""" ---------------------------------------------------------------------------- -This script requires setuptools version %s to run (even to display -help). I will attempt to download it for you (from -%s), but -you may need to enable firewall access for this script first. -I will start the download in %d seconds. - -(Note: if this machine does not have network access, please obtain the file - - %s - -and place it in this directory before rerunning this script.) ----------------------------------------------------------------------------""", - version, download_base, delay, url - ); from time import sleep; sleep(delay) - log.warn("Downloading %s", url) - src = urllib2.urlopen(url) - # Read/write all in one block, so we don't create a corrupt file - # if the download is interrupted. - data = _validate_md5(egg_name, src.read()) - dst = open(saveto,"wb"); dst.write(data) - finally: - if src: src.close() - if dst: dst.close() - return os.path.realpath(saveto) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -def main(argv, version=DEFAULT_VERSION): - """Install or upgrade setuptools and EasyInstall""" - try: - import setuptools - except ImportError: - egg = None - try: - egg = download_setuptools(version, delay=0) - sys.path.insert(0,egg) - from setuptools.command.easy_install import main - return main(list(argv)+[egg]) # we're done here - finally: - if egg and os.path.exists(egg): - os.unlink(egg) - else: - if setuptools.__version__ == '0.0.1': - print >>sys.stderr, ( - "You have an obsolete version of setuptools installed. Please\n" - "remove it from your system entirely before rerunning this script." - ) - sys.exit(2) - - req = "setuptools>="+version - import pkg_resources - try: - pkg_resources.require(req) - except pkg_resources.VersionConflict: - try: - from setuptools.command.easy_install import main - except ImportError: - from easy_install import main - main(list(argv)+[download_setuptools(delay=0)]) - sys.exit(0) # try to force an exit - else: - if argv: - from setuptools.command.easy_install import main - main(argv) - else: - print "Setuptools version",version,"or greater has been installed." - print '(Run "ez_setup.py -U setuptools" to reinstall or upgrade.)' - -def update_md5(filenames): - """Update our built-in md5 registry""" - - import re - - for name in filenames: - base = os.path.basename(name) - f = open(name,'rb') - md5_data[base] = md5(f.read()).hexdigest() - f.close() - - data = [" %r: %r,\n" % it for it in md5_data.items()] - data.sort() - repl = "".join(data) - - import inspect - srcfile = inspect.getsourcefile(sys.modules[__name__]) - f = open(srcfile, 'rb'); src = f.read(); f.close() - - match = re.search("\nmd5_data = {\n([^}]+)}", src) - if not match: - print >>sys.stderr, "Internal error!" - sys.exit(2) - - src = src[:match.start(1)] + repl + src[match.end(1):] - f = open(srcfile,'w') - f.write(src) - f.close() - - -if __name__=='__main__': - if len(sys.argv)>2 and sys.argv[1]=='--md5update': - update_md5(sys.argv[2:]) - else: - main(sys.argv[1:]) - - - - - - diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/heapdict.py new/HeapDict-1.0.1/heapdict.py --- old/HeapDict-1.0.0/heapdict.py 2009-10-16 16:52:50.000000000 +0200 +++ new/HeapDict-1.0.1/heapdict.py 2019-09-09 19:42:13.000000000 +0200 @@ -1,28 +1,22 @@ -import collections +try: + from collections.abc import MutableMapping +except ImportError: + from collections import MutableMapping + def doc(s): if hasattr(s, '__call__'): s = s.__doc__ + def f(g): g.__doc__ = s return g return f -class heapdict(collections.MutableMapping): + +class heapdict(MutableMapping): __marker = object() - @staticmethod - def _parent(i): - return ((i - 1) >> 1) - - @staticmethod - def _left(i): - return ((i << 1) + 1) - - @staticmethod - def _right(i): - return ((i+1) << 1) - def __init__(self, *args, **kw): self.heap = [] self.d = {} @@ -30,7 +24,7 @@ @doc(dict.clear) def clear(self): - self.heap.clear() + del self.heap[:] self.d.clear() @doc(dict.__setitem__) @@ -43,37 +37,47 @@ self._decrease_key(len(self.heap)-1) def _min_heapify(self, i): - l = self._left(i) - r = self._right(i) n = len(self.heap) - if l < n and self.heap[l][0] < self.heap[i][0]: - low = l - else: - low = i - if r < n and self.heap[r][0] < self.heap[low][0]: - low = r + h = self.heap + while True: + # calculate the offset of the left child + l = (i << 1) + 1 + # calculate the offset of the right child + r = (i + 1) << 1 + if l < n and h[l][0] < h[i][0]: + low = l + else: + low = i + if r < n and h[r][0] < h[low][0]: + low = r + + if low == i: + break - if low != i: self._swap(i, low) - self._min_heapify(low) + i = low def _decrease_key(self, i): while i: - parent = self._parent(i) - if self.heap[parent][0] < self.heap[i][0]: break + # calculate the offset of the parent + parent = (i - 1) >> 1 + if self.heap[parent][0] < self.heap[i][0]: + break self._swap(i, parent) i = parent def _swap(self, i, j): - self.heap[i], self.heap[j] = self.heap[j], self.heap[i] - self.heap[i][2] = i - self.heap[j][2] = j + h = self.heap + h[i], h[j] = h[j], h[i] + h[i][2] = i + h[j][2] = j @doc(dict.__delitem__) def __delitem__(self, key): wrapper = self.d[key] while wrapper[2]: - parentpos = self._parent(wrapper[2]) + # calculate the offset of the parent + parentpos = (wrapper[2] - 1) >> 1 parent = self.heap[parentpos] self._swap(wrapper[2], parent[2]) self.popitem() @@ -92,11 +96,11 @@ if len(self.heap) == 1: self.heap.pop() else: - self.heap[0] = self.heap.pop(-1) + self.heap[0] = self.heap.pop() self.heap[0][2] = 0 self._min_heapify(0) del self.d[wrapper[1]] - return wrapper[1], wrapper[0] + return wrapper[1], wrapper[0] @doc(dict.__len__) def __len__(self): @@ -106,5 +110,6 @@ """D.peekitem() -> (k, v), return the (key, value) pair with lowest value;\n but raise KeyError if D is empty.""" return (self.heap[0][1], self.heap[0][0]) + del doc __all__ = ['heapdict'] diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/setup.cfg new/HeapDict-1.0.1/setup.cfg --- old/HeapDict-1.0.0/setup.cfg 2009-10-16 17:37:51.000000000 +0200 +++ new/HeapDict-1.0.1/setup.cfg 2019-09-09 20:56:38.000000000 +0200 @@ -1,5 +1,4 @@ [egg_info] tag_build = tag_date = 0 -tag_svn_revision = 0 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/setup.py new/HeapDict-1.0.1/setup.py --- old/HeapDict-1.0.0/setup.py 2009-10-16 17:37:24.000000000 +0200 +++ new/HeapDict-1.0.1/setup.py 2019-09-09 20:56:17.000000000 +0200 @@ -1,15 +1,9 @@ #!/usr/bin/env -import sys -if sys.version_info[0] <= 2: - import ez_setup - ez_setup.use_setuptools() - from setuptools import setup, Extension -else: - from distutils.core import setup, Extension +from setuptools import setup setup(name='HeapDict', - version='1.0.0', + version='1.0.1', description='a heap with decrease-key and increase-key operations', author='Stutzbach Enterprises, LLC', author_email='dan...@stutzbachenterprises.com', @@ -35,5 +29,4 @@ ], long_description=open('README.rst').read(), - ) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/HeapDict-1.0.0/test_heap.py new/HeapDict-1.0.1/test_heap.py --- old/HeapDict-1.0.0/test_heap.py 2009-10-16 17:13:56.000000000 +0200 +++ new/HeapDict-1.0.1/test_heap.py 2019-09-09 19:42:13.000000000 +0200 @@ -1,22 +1,29 @@ #!/usr/bin/python from __future__ import print_function -from heapdict import heapdict import random -import unittest import sys +import unittest +from heapdict import heapdict try: - import test.support as test_support # Python 3 + # Python 3 + import test.support as test_support except ImportError: - import test.test_support as test_support # Python 2 + # Python 2 + import test.test_support as test_support N = 100 + class TestHeap(unittest.TestCase): + def check_invariants(self, h): - for i in range(len(h)): - self.assertEqual(h.heap[i][2], i) - if i > 0: - self.assertTrue(h.heap[h._parent(i)][0] <= h.heap[i][0]) + # the 3rd entry of each heap entry is the position in the heap + for i, e in enumerate(h.heap): + self.assertEqual(e[2], i) + # the parent of each heap element must not be larger than the element + for i in range(1, len(h.heap)): + parent = (i - 1) >> 1 + self.assertLessEqual(h.heap[parent][0], h.heap[i][0]) def make_data(self): pairs = [(random.random(), random.random()) for i in range(N)] @@ -28,9 +35,9 @@ pairs.sort(key=lambda x: x[1], reverse=True) return h, pairs, d - + def test_popitem(self): - h, pairs, d = self.make_data() + h, pairs, _ = self.make_data() while pairs: v = h.popitem() v2 = pairs.pop(-1) @@ -42,12 +49,12 @@ for i in range(N): h[i] = 0 for i in range(N): - k, v = h.popitem() + _, v = h.popitem() self.assertEqual(v, 0) self.check_invariants(h) def test_peek(self): - h, pairs, d = self.make_data() + h, pairs, _ = self.make_data() while pairs: v = h.peekitem()[0] h.popitem() @@ -56,19 +63,19 @@ self.assertEqual(len(h), 0) def test_iter(self): - h, pairs, d = self.make_data() + h, _, d = self.make_data() self.assertEqual(list(h), list(d)) def test_keys(self): - h, pairs, d = self.make_data() + h, _, d = self.make_data() self.assertEqual(list(sorted(h.keys())), list(sorted(d.keys()))) def test_values(self): - h, pairs, d = self.make_data() + h, _, d = self.make_data() self.assertEqual(list(sorted(h.values())), list(sorted(d.values()))) def test_del(self): - h, pairs, d = self.make_data() + h, pairs, _ = self.make_data() k, v = pairs.pop(N//2) del h[k] while pairs: @@ -78,22 +85,24 @@ self.assertEqual(len(h), 0) def test_change(self): - h, pairs, d = self.make_data() + h, pairs, _ = self.make_data() k, v = pairs[N//2] h[k] = 0.5 pairs[N//2] = (k, 0.5) - pairs.sort(key = lambda x: x[1], reverse=True) + pairs.sort(key=lambda x: x[1], reverse=True) while pairs: v = h.popitem() v2 = pairs.pop(-1) self.assertEqual(v, v2) self.assertEqual(len(h), 0) -#============================================================================== + def test_clear(self): + h, _, _ = self.make_data() + h.clear() + self.assertEqual(len(h), 0) + def test_main(verbose=None): - from types import BuiltinFunctionType - test_classes = [TestHeap] test_support.run_unittest(*test_classes) @@ -101,11 +110,12 @@ if verbose and hasattr(sys, "gettotalrefcount"): import gc counts = [None] * 5 - for i in xrange(len(counts)): + for i in range(len(counts)): test_support.run_unittest(*test_classes) gc.collect() counts[i] = sys.gettotalrefcount() print(counts) + if __name__ == "__main__": test_main(verbose=True)