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)
