Mercurial > cpython-lru_cache-weakref

annotate Lib/test/test_bisect.py @ 78069:a8aa77458e12 3.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add c_size_t and c_ssize_t to the ctypes summary table.
author Antoine Pitrou <solipsis@pitrou.net>
date Thu, 12 Jul 2012 20:31:50 +0200
parents 13900edf13be
children 838e2b19489e
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
1 import sys
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
2 import unittest
47201
9c930a32cebb #2621 rename test.test_support to test.support
Benjamin Peterson <benjamin@python.org>
parents: 45495
diff changeset
3 from test import support
45302
b1cb6b44b798 Move UserList to collections.
Raymond Hettinger <python@rcn.com>
parents: 42142
diff changeset
4 from collections import UserList
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
5
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
6 # We do a bit of trickery here to be able to test both the C implementation
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
7 # and the Python implementation of the module.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
8
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
9 # Make it impossible to import the C implementation anymore.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
10 sys.modules['_bisect'] = 0
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
11 # We must also handle the case that bisect was imported before.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
12 if 'bisect' in sys.modules:
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
13 del sys.modules['bisect']
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
14
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
15 # Now we can import the module and get the pure Python implementation.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
16 import bisect as py_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
17
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
18 # Restore everything to normal.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
19 del sys.modules['_bisect']
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
20 del sys.modules['bisect']
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
21
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
22 # This is now the module with the C implementation.
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
23 import bisect as c_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
24
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
25
76995
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
26 class Range(object):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
27 """A trivial range()-like object without any integer width limitations."""
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
28 def __init__(self, start, stop):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
29 self.start = start
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
30 self.stop = stop
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
31 self.last_insert = None
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
32
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
33 def __len__(self):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
34 return self.stop - self.start
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
35
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
36 def __getitem__(self, idx):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
37 n = self.stop - self.start
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
38 if idx < 0:
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
39 idx += n
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
40 if idx >= n:
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
41 raise IndexError(idx)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
42 return self.start + idx
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
43
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
44 def insert(self, idx, item):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
45 self.last_insert = idx, item
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
46
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
47
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
48 class TestBisect(unittest.TestCase):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
49 module = None
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
50
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
51 def setUp(self):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
52 self.precomputedCases = [
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
53 (self.module.bisect_right, [], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
54 (self.module.bisect_right, [1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
55 (self.module.bisect_right, [1], 1, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
56 (self.module.bisect_right, [1], 2, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
57 (self.module.bisect_right, [1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
58 (self.module.bisect_right, [1, 1], 1, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
59 (self.module.bisect_right, [1, 1], 2, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
60 (self.module.bisect_right, [1, 1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
61 (self.module.bisect_right, [1, 1, 1], 1, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
62 (self.module.bisect_right, [1, 1, 1], 2, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
63 (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
64 (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
65 (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
66 (self.module.bisect_right, [1, 2], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
67 (self.module.bisect_right, [1, 2], 1, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
68 (self.module.bisect_right, [1, 2], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
69 (self.module.bisect_right, [1, 2], 2, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
70 (self.module.bisect_right, [1, 2], 3, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
71 (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
72 (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
73 (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
74 (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
75 (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
76 (self.module.bisect_right, [1, 2, 3], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
77 (self.module.bisect_right, [1, 2, 3], 1, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
78 (self.module.bisect_right, [1, 2, 3], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
79 (self.module.bisect_right, [1, 2, 3], 2, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
80 (self.module.bisect_right, [1, 2, 3], 2.5, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
81 (self.module.bisect_right, [1, 2, 3], 3, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
82 (self.module.bisect_right, [1, 2, 3], 4, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
83 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
84 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
85 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
86 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
87 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
88 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
89 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
90 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
91 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
92
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
93 (self.module.bisect_left, [], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
94 (self.module.bisect_left, [1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
95 (self.module.bisect_left, [1], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
96 (self.module.bisect_left, [1], 2, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
97 (self.module.bisect_left, [1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
98 (self.module.bisect_left, [1, 1], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
99 (self.module.bisect_left, [1, 1], 2, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
100 (self.module.bisect_left, [1, 1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
101 (self.module.bisect_left, [1, 1, 1], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
102 (self.module.bisect_left, [1, 1, 1], 2, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
103 (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
104 (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
105 (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
106 (self.module.bisect_left, [1, 2], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
107 (self.module.bisect_left, [1, 2], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
108 (self.module.bisect_left, [1, 2], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
109 (self.module.bisect_left, [1, 2], 2, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
110 (self.module.bisect_left, [1, 2], 3, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
111 (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
112 (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
113 (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
114 (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
115 (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
116 (self.module.bisect_left, [1, 2, 3], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
117 (self.module.bisect_left, [1, 2, 3], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
118 (self.module.bisect_left, [1, 2, 3], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
119 (self.module.bisect_left, [1, 2, 3], 2, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
120 (self.module.bisect_left, [1, 2, 3], 2.5, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
121 (self.module.bisect_left, [1, 2, 3], 3, 2),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
122 (self.module.bisect_left, [1, 2, 3], 4, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
123 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
124 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
125 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
126 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
127 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
128 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
129 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
130 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
131 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
132 ]
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
133
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
134 def test_precomputed(self):
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
135 for func, data, elem, expected in self.precomputedCases:
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
136 self.assertEqual(func(data, elem), expected)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
137 self.assertEqual(func(UserList(data), elem), expected)
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
138
48499
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
139 def test_negative_lo(self):
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
140 # Issue 3301
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
141 mod = self.module
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
142 self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
143 self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
144 self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
145 self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from
Georg Brandl <georg@python.org>
parents: 47201
diff changeset
146
76323
35a3a7e0d66d Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 55593
diff changeset
147 def test_large_range(self):
35a3a7e0d66d Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 55593
diff changeset
148 # Issue 13496
35a3a7e0d66d Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 55593
diff changeset
149 mod = self.module
76995
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
150 n = sys.maxsize
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
151 data = range(n-1)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
152 self.assertEqual(mod.bisect_left(data, n-3), n-3)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
153 self.assertEqual(mod.bisect_right(data, n-3), n-2)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
154 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
155 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
156
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
157 def test_large_pyrange(self):
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
158 # Same as above, but without C-imposed limits on range() parameters
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
159 mod = self.module
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
160 n = sys.maxsize
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
161 data = Range(0, n-1)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
162 self.assertEqual(mod.bisect_left(data, n-3), n-3)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
163 self.assertEqual(mod.bisect_right(data, n-3), n-2)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
164 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
165 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
166 x = n - 100
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
167 mod.insort_left(data, x, x - 50, x + 50)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
168 self.assertEqual(data.last_insert, (x, x))
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
169 x = n - 200
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
170 mod.insort_right(data, x, x - 50, x + 50)
13900edf13be Forward port additional tests from 2.7 (issue #14829).
Antoine Pitrou <solipsis@pitrou.net>
parents: 76323
diff changeset
171 self.assertEqual(data.last_insert, (x + 1, x))
76323
35a3a7e0d66d Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 55593
diff changeset
172
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
173 def test_random(self, n=25):
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
174 from random import randrange
41642
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
175 for i in range(n):
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
176 data = [randrange(0, n, 2) for j in range(i)]
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
177 data.sort()
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
178 elem = randrange(-1, n+1)
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
179 ip = self.module.bisect_left(data, elem)
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
180 if ip < len(data):
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
181 self.assertTrue(elem <= data[ip])
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
182 if ip > 0:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
183 self.assertTrue(data[ip-1] < elem)
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
184 ip = self.module.bisect_right(data, elem)
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
185 if ip < len(data):
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
186 self.assertTrue(elem < data[ip])
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
187 if ip > 0:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
188 self.assertTrue(data[ip-1] <= elem)
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
189
27268
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
190 def test_optionalSlicing(self):
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
191 for func, data, elem, expected in self.precomputedCases:
41642
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
192 for lo in range(4):
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
193 lo = min(len(data), lo)
41642
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
194 for hi in range(3,8):
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
195 hi = min(len(data), hi)
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
196 ip = func(data, elem, lo, hi)
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
197 self.assertTrue(lo <= ip <= hi)
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
198 if func is self.module.bisect_left and ip < hi:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
199 self.assertTrue(elem <= data[ip])
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
200 if func is self.module.bisect_left and ip > lo:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
201 self.assertTrue(data[ip-1] < elem)
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
202 if func is self.module.bisect_right and ip < hi:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
203 self.assertTrue(elem < data[ip])
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
204 if func is self.module.bisect_right and ip > lo:
55593
0bb232078b8c Merged revisions 73715 via svnmerge from
Georg Brandl <georg@python.org>
parents: 49493
diff changeset
205 self.assertTrue(data[ip-1] <= elem)
27269
dbe4f57e8bb2 Let test_random cover the endpoints.
Raymond Hettinger <python@rcn.com>
parents: 27268
diff changeset
206 self.assertEqual(ip, max(lo, min(hi, expected)))
27268
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
207
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
208 def test_backcompatibility(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
209 self.assertEqual(self.module.bisect, self.module.bisect_right)
27268
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
210
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 33602
diff changeset
211 def test_keyword_args(self):
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 33602
diff changeset
212 data = [10, 20, 30, 40, 50]
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
213 self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
214 self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
215 self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
216 self.module.insort_left(a=data, x=25, lo=1, hi=3)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
217 self.module.insort_right(a=data, x=25, lo=1, hi=3)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
218 self.module.insort(a=data, x=25, lo=1, hi=3)
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 33602
diff changeset
219 self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 33602
diff changeset
220
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
221 class TestBisectPython(TestBisect):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
222 module = py_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
223
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
224 class TestBisectC(TestBisect):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
225 module = c_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
226
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
227 #==============================================================================
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
228
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
229 class TestInsort(unittest.TestCase):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
230 module = None
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
231
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
232 def test_vsBuiltinSort(self, n=500):
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
233 from random import choice
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
234 for insorted in (list(), UserList()):
41642
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
235 for i in range(n):
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
236 digit = choice("0123456789")
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
237 if digit in "02468":
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
238 f = self.module.insort_left
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
239 else:
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
240 f = self.module.insort_right
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
241 f(insorted, digit)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents: 28917
diff changeset
242 self.assertEqual(sorted(insorted), insorted)
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
243
27268
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
244 def test_backcompatibility(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
245 self.assertEqual(self.module.insort, self.module.insort_right)
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
246
49493
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
247 def test_listDerived(self):
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
248 class List(list):
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
249 data = []
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
250 def insert(self, index, item):
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
251 self.data.insert(index, item)
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
252
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
253 lst = List()
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
254 self.module.insort_left(lst, 10)
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
255 self.module.insort_right(lst, 5)
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
256 self.assertEqual([5, 10], lst.data)
bdf4da5d04ad merge from trunk
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
257
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
258 class TestInsortPython(TestInsort):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
259 module = py_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
260
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
261 class TestInsortC(TestInsort):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
262 module = c_bisect
27268
be3d1b7e62dc Test optional slice arguments.
Raymond Hettinger <python@rcn.com>
parents: 27267
diff changeset
263
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
264 #==============================================================================
15673
67b3ac439f64 Fred, THIS NEEDS DOCS! The function docstrings tell the tale.
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
265
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
266
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
267 class LenOnly:
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
268 "Dummy sequence class defining __len__ but not __getitem__."
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
269 def __len__(self):
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
270 return 10
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
271
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
272 class GetOnly:
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
273 "Dummy sequence class defining __getitem__ but not __len__."
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
274 def __getitem__(self, ndx):
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
275 return 10
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
276
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
277 class CmpErr:
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
278 "Dummy element that always raises an error during comparison"
39644
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
279 def __lt__(self, other):
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
280 raise ZeroDivisionError
39644
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
281 __gt__ = __lt__
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
282 __le__ = __lt__
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
283 __ge__ = __lt__
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
284 __eq__ = __lt__
13d5e5f0e993 Restructure comparison dramatically. There is no longer a default
Guido van Rossum <guido@python.org>
parents: 37739
diff changeset
285 __ne__ = __lt__
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
286
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
287 class TestErrorHandling(unittest.TestCase):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
288 module = None
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
289
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
290 def test_non_sequence(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
291 for f in (self.module.bisect_left, self.module.bisect_right,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
292 self.module.insort_left, self.module.insort_right):
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
293 self.assertRaises(TypeError, f, 10, 10)
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
294
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
295 def test_len_only(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
296 for f in (self.module.bisect_left, self.module.bisect_right,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
297 self.module.insort_left, self.module.insort_right):
37739
fb2aff1862e4 Fix test_bisect in the same way as test_itertools: iter() blows up a lot
Thomas Wouters <thomas@python.org>
parents: 35699
diff changeset
298 self.assertRaises(TypeError, f, LenOnly(), 10)
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
299
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
300 def test_get_only(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
301 for f in (self.module.bisect_left, self.module.bisect_right,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
302 self.module.insort_left, self.module.insort_right):
37739
fb2aff1862e4 Fix test_bisect in the same way as test_itertools: iter() blows up a lot
Thomas Wouters <thomas@python.org>
parents: 35699
diff changeset
303 self.assertRaises(TypeError, f, GetOnly(), 10)
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
304
33602
7d6679ee39f9 Rename test for comparision errors.
Raymond Hettinger <python@rcn.com>
parents: 33601
diff changeset
305 def test_cmp_err(self):
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
306 seq = [CmpErr(), CmpErr(), CmpErr()]
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
307 for f in (self.module.bisect_left, self.module.bisect_right,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
308 self.module.insort_left, self.module.insort_right):
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
309 self.assertRaises(ZeroDivisionError, f, seq, 10)
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
310
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
311 def test_arg_parsing(self):
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
312 for f in (self.module.bisect_left, self.module.bisect_right,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
313 self.module.insort_left, self.module.insort_right):
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
314 self.assertRaises(TypeError, f, 10)
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
315
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
316 class TestErrorHandlingPython(TestErrorHandling):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
317 module = py_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
318
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
319 class TestErrorHandlingC(TestErrorHandling):
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
320 module = c_bisect
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
321
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
322 #==============================================================================
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
323
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
324 libreftest = """
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
325 Example from the Library Reference: Doc/library/bisect.rst
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
326
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
327 The bisect() function is generally useful for categorizing numeric data.
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
328 This example uses bisect() to look up a letter grade for an exam total
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
329 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
330 75..84 is a `B', etc.
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
331
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
332 >>> grades = "FEDCBA"
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
333 >>> breakpoints = [30, 44, 66, 75, 85]
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
334 >>> from bisect import bisect
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
335 >>> def grade(total):
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
336 ... return grades[bisect(breakpoints, total)]
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
337 ...
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
338 >>> grade(66)
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
339 'C'
42142
a53e48be6df9 Merged revisions 56125-56153 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 41642
diff changeset
340 >>> list(map(grade, [33, 99, 77, 44, 12, 88]))
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
341 ['E', 'A', 'B', 'D', 'F', 'A']
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
342
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
343 """
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
344
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
345 #------------------------------------------------------------------------------
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
346
27267
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
347 __test__ = {'libreftest' : libreftest}
b744508d5b12 Added doctest for examples in the library reference.
Raymond Hettinger <python@rcn.com>
parents: 27266
diff changeset
348
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
349 def test_main(verbose=None):
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
350 from test import test_bisect
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
351
45495
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
352 test_classes = [TestBisectPython, TestBisectC,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
353 TestInsortPython, TestInsortC,
48488fa50729 Merged revisions 61003-61033 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45302
diff changeset
354 TestErrorHandlingPython, TestErrorHandlingC]
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
355
47201
9c930a32cebb #2621 rename test.test_support to test.support
Benjamin Peterson <benjamin@python.org>
parents: 45495
diff changeset
356 support.run_unittest(*test_classes)
9c930a32cebb #2621 rename test.test_support to test.support
Benjamin Peterson <benjamin@python.org>
parents: 45495
diff changeset
357 support.run_doctest(test_bisect, verbose)
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
358
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
359 # verify reference counting
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
360 if verbose and hasattr(sys, "gettotalrefcount"):
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
361 import gc
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
362 counts = [None] * 5
41642
a6eb6acfe04a Merged revisions 55007-55179 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 40775
diff changeset
363 for i in range(len(counts)):
47201
9c930a32cebb #2621 rename test.test_support to test.support
Benjamin Peterson <benjamin@python.org>
parents: 45495
diff changeset
364 support.run_unittest(*test_classes)
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
365 gc.collect()
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
366 counts[i] = sys.gettotalrefcount()
40775
4cdf21a0dbbc Fix most trivially-findable print statements.
Guido van Rossum <guido@python.org>
parents: 39644
diff changeset
367 print(counts)
33601
7511585f2e6a Beef-up tests for greater coverage and refcount checking.
Raymond Hettinger <python@rcn.com>
parents: 31436
diff changeset
368
27266
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
369 if __name__ == "__main__":
a9ddadf789ea Convert to unittest format so that more tests can be added cleanly.
Raymond Hettinger <python@rcn.com>
parents: 24442
diff changeset
370 test_main(verbose=True)