from test
import test_support
from bisect
import bisect_right
, bisect_left
, insort_left
, insort_right
, insort
, bisect
from UserList
import UserList
class TestBisect(unittest
.TestCase
):
(bisect_right
, [], 1, 0),
(bisect_right
, [1], 0, 0),
(bisect_right
, [1], 1, 1),
(bisect_right
, [1], 2, 1),
(bisect_right
, [1, 1], 0, 0),
(bisect_right
, [1, 1], 1, 2),
(bisect_right
, [1, 1], 2, 2),
(bisect_right
, [1, 1, 1], 0, 0),
(bisect_right
, [1, 1, 1], 1, 3),
(bisect_right
, [1, 1, 1], 2, 3),
(bisect_right
, [1, 1, 1, 1], 0, 0),
(bisect_right
, [1, 1, 1, 1], 1, 4),
(bisect_right
, [1, 1, 1, 1], 2, 4),
(bisect_right
, [1, 2], 0, 0),
(bisect_right
, [1, 2], 1, 1),
(bisect_right
, [1, 2], 1.5, 1),
(bisect_right
, [1, 2], 2, 2),
(bisect_right
, [1, 2], 3, 2),
(bisect_right
, [1, 1, 2, 2], 0, 0),
(bisect_right
, [1, 1, 2, 2], 1, 2),
(bisect_right
, [1, 1, 2, 2], 1.5, 2),
(bisect_right
, [1, 1, 2, 2], 2, 4),
(bisect_right
, [1, 1, 2, 2], 3, 4),
(bisect_right
, [1, 2, 3], 0, 0),
(bisect_right
, [1, 2, 3], 1, 1),
(bisect_right
, [1, 2, 3], 1.5, 1),
(bisect_right
, [1, 2, 3], 2, 2),
(bisect_right
, [1, 2, 3], 2.5, 2),
(bisect_right
, [1, 2, 3], 3, 3),
(bisect_right
, [1, 2, 3], 4, 3),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
(bisect_right
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
(bisect_left
, [1], 0, 0),
(bisect_left
, [1], 1, 0),
(bisect_left
, [1], 2, 1),
(bisect_left
, [1, 1], 0, 0),
(bisect_left
, [1, 1], 1, 0),
(bisect_left
, [1, 1], 2, 2),
(bisect_left
, [1, 1, 1], 0, 0),
(bisect_left
, [1, 1, 1], 1, 0),
(bisect_left
, [1, 1, 1], 2, 3),
(bisect_left
, [1, 1, 1, 1], 0, 0),
(bisect_left
, [1, 1, 1, 1], 1, 0),
(bisect_left
, [1, 1, 1, 1], 2, 4),
(bisect_left
, [1, 2], 0, 0),
(bisect_left
, [1, 2], 1, 0),
(bisect_left
, [1, 2], 1.5, 1),
(bisect_left
, [1, 2], 2, 1),
(bisect_left
, [1, 2], 3, 2),
(bisect_left
, [1, 1, 2, 2], 0, 0),
(bisect_left
, [1, 1, 2, 2], 1, 0),
(bisect_left
, [1, 1, 2, 2], 1.5, 2),
(bisect_left
, [1, 1, 2, 2], 2, 2),
(bisect_left
, [1, 1, 2, 2], 3, 4),
(bisect_left
, [1, 2, 3], 0, 0),
(bisect_left
, [1, 2, 3], 1, 0),
(bisect_left
, [1, 2, 3], 1.5, 1),
(bisect_left
, [1, 2, 3], 2, 1),
(bisect_left
, [1, 2, 3], 2.5, 2),
(bisect_left
, [1, 2, 3], 3, 2),
(bisect_left
, [1, 2, 3], 4, 3),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
(bisect_left
, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
def test_precomputed(self
):
for func
, data
, elem
, expected
in self
.precomputedCases
:
self
.assertEqual(func(data
, elem
), expected
)
self
.assertEqual(func(UserList(data
), elem
), expected
)
def test_random(self
, n
=25):
from random
import randrange
data
= [randrange(0, n
, 2) for j
in xrange(i
)]
elem
= randrange(-1, n
+1)
ip
= bisect_left(data
, elem
)
self
.failUnless(elem
<= data
[ip
])
self
.failUnless(data
[ip
-1] < elem
)
ip
= bisect_right(data
, elem
)
self
.failUnless(elem
< data
[ip
])
self
.failUnless(data
[ip
-1] <= elem
)
def test_optionalSlicing(self
):
for func
, data
, elem
, expected
in self
.precomputedCases
:
ip
= func(data
, elem
, lo
, hi
)
self
.failUnless(lo
<= ip
<= hi
)
if func
is bisect_left
and ip
< hi
:
self
.failUnless(elem
<= data
[ip
])
if func
is bisect_left
and ip
> lo
:
self
.failUnless(data
[ip
-1] < elem
)
if func
is bisect_right
and ip
< hi
:
self
.failUnless(elem
< data
[ip
])
if func
is bisect_right
and ip
> lo
:
self
.failUnless(data
[ip
-1] <= elem
)
self
.assertEqual(ip
, max(lo
, min(hi
, expected
)))
def test_backcompatibility(self
):
self
.assertEqual(bisect
, bisect_right
)
#==============================================================================
class TestInsort(unittest
.TestCase
):
def test_vsBuiltinSort(self
, n
=500):
from random
import choice
for insorted
in (list(), UserList()):
digit
= choice("0123456789")
self
.assertEqual(sorted(insorted
), insorted
)
def test_backcompatibility(self
):
self
.assertEqual(insort
, insort_right
)
#==============================================================================
"Dummy sequence class defining __len__ but not __getitem__."
"Dummy sequence class defining __getitem__ but not __len__."
def __getitem__(self
, ndx
):
"Dummy element that always raises an error during comparison"
def __cmp__(self
, other
):
class TestErrorHandling(unittest
.TestCase
):
def test_non_sequence(self
):
for f
in (bisect_left
, bisect_right
, insort_left
, insort_right
):
self
.assertRaises(TypeError, f
, 10, 10)
for f
in (bisect_left
, bisect_right
, insort_left
, insort_right
):
self
.assertRaises(AttributeError, f
, LenOnly(), 10)
for f
in (bisect_left
, bisect_right
, insort_left
, insort_right
):
self
.assertRaises(AttributeError, f
, GetOnly(), 10)
seq
= [CmpErr(), CmpErr(), CmpErr()]
for f
in (bisect_left
, bisect_right
, insort_left
, insort_right
):
self
.assertRaises(ZeroDivisionError, f
, seq
, 10)
def test_arg_parsing(self
):
for f
in (bisect_left
, bisect_right
, insort_left
, insort_right
):
self
.assertRaises(TypeError, f
, 10)
#==============================================================================
Example from the Library Reference: Doc/lib/libbisect.tex
The bisect() function is generally useful for categorizing numeric data.
This example uses bisect() to look up a letter grade for an exam total
(say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
>>> breakpoints = [30, 44, 66, 75, 85]
>>> from bisect import bisect
... return grades[bisect(breakpoints, total)]
>>> map(grade, [33, 99, 77, 44, 12, 88])
['E', 'A', 'B', 'D', 'F', 'A']
#------------------------------------------------------------------------------
__test__
= {'libreftest' : libreftest
}
def test_main(verbose
=None):
from test
import test_bisect
from types
import BuiltinFunctionType
test_classes
= [TestBisect
, TestInsort
]
if isinstance(bisect_left
, BuiltinFunctionType
):
test_classes
.append(TestErrorHandling
)
test_support
.run_unittest(*test_classes
)
test_support
.run_doctest(test_bisect
, verbose
)
# verify reference counting
if verbose
and hasattr(sys
, "gettotalrefcount"):
for i
in xrange(len(counts
)):
test_support
.run_unittest(*test_classes
)
counts
[i
] = sys
.gettotalrefcount()
if __name__
== "__main__":