Testing binary search module, based on bisect

Question

The bisect module can only find the index to insert an element. I created a simple class based on the bisect module for precise searching and covered all the edge cases that came to mind with tests. Could you please check the correctness of the tests for the binary search extension module? I want to make sure that the tests match the function documentation (docstrings). Well, maybe more you could review the code, or suggest optimizations?

---

My code:

from bisect import bisect_left, bisect_right class BisectFinder: ''' This class contains some convenient binary search functions for an element in a list ''' @staticmethod def find_left_lt(a, x, lo=0, hi=None, key=None): '''Finds the index of the leftmost (among duplicates) element that is strictly less than X. A[index] < X A[index] == a2 [ a1{<x}, a1{<x}, A[index], a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if len(a) > 0 and index < len(a) + 1 and a[index - 1] < x: return bisect_left(a, a[index - 1], lo=lo, hi=index-1, key=key) raise ValueError("No elements less than x found.") @staticmethod def find_left_le(a, x, lo=0, hi=None, key=None): '''Finds the index of the leftmost (among duplicates) element that is less than or equal to X. A[index] <= X A[index] == a4 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, A[index], a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_right(a, x, lo=lo, hi=hi, key=key) if len(a) > 0 and index < len(a) + 1 and a[index - 1] <= x: return bisect_left(a, a[index - 1], lo=lo, hi=index-1, key=key) raise ValueError("No elements less than or equal to x found.") @staticmethod def find_left_eq(a, x, lo=0, hi=None, key=None): '''Finds the index of the leftmost (among duplicates) element that is equal to X. A[index] == X A[index] == a5 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, A[index], a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if index != len(a) and a[index] == x: return index raise ValueError("No elements equal to x found.") @staticmethod def find_left_ge(a, x, lo=0, hi=None, key=None): '''Finds the index of the leftmost (among duplicates) element that is greater than or equal to X. A[index] >= X A[index] == a7 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, A[index], a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if index != len(a): return index raise ValueError("No elements greater than or equal to x found.") @staticmethod def find_left_gt(a, x, lo=0, hi=None, key=None): '''Finds the index of the leftmost (among duplicates) element that is strictly greater than X. A[index] > X A[index] == a9 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, A[index], a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_right(a, x, lo=lo, hi=hi, key=key) if index != len(a): return index raise ValueError("No elements greater than x found.") @staticmethod def find_right_lt(a, x, lo=0, hi=None, key=None): '''Finds the index of the rightmost (among duplicates) element that is strictly less than X. A[index] < X A[index] == a2 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, A[index], a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if index: return index-1 raise ValueError("No elements less than x found.") @staticmethod def find_right_le(a, x, lo=0, hi=None, key=None): '''Finds the index of the rightmost (among duplicates) element that is less than or equal to X. A[index] <= X A[index] == a4 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, A[index], a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_right(a, x, lo=lo, hi=hi, key=key) if index: return index-1 raise ValueError("No elements less than or equal to x found.") @staticmethod def find_right_eq(a, x, lo=0, hi=None, key=None): '''Finds the index of the rightmost (among duplicates) element that is equal to X. A[index] == X A[index] == a5 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, A[index], a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if index != len(a) and a[index] == x: return bisect_right(a, a[index], lo=index, hi=hi, key=key) - 1 raise ValueError("No elements equal to x found.") @staticmethod def find_right_ge(a, x, lo=0, hi=None, key=None): '''Finds the index of the rightmost (among duplicates) element that is greater than or equal to X. A[index] >= X A[index] == a7 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, A[index], a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, a10{>x}, a10{>x} ] ''' index = bisect_left(a, x, lo=lo, hi=hi, key=key) if index != len(a): return bisect_right(a, a[index], lo=index, hi=hi, key=key) - 1 raise ValueError("No elements greater than or equal to x found.") @staticmethod def find_right_gt(a, x, lo=0, hi=None, key=None): '''Finds the index of the rightmost (among duplicates) element that is strictly greater than X. A[index] > X A[index] == a9 [ a1{<x}, a1{<x}, a2{<x}, a2{<x}, a3{<=x}, a3{<=x}, a4{<=x}, a4{<=x}, a5{==x}, a5{==x}, a7{>=x}, a7{>=x}, a8{>=x}, a8{>=x}, a9{>x}, a9{>x}, A[index], a10{>x}, a10{>x} ] ''' index = bisect_right(a, x, lo=lo, hi=hi, key=key) if index != len(a): return bisect_right(a, a[index], lo=index, hi=hi, key=key) - 1 raise ValueError("No elements greater than x found.") 

My tests:

import unittest from unittest import TestCase from implements import BisectFinder class TestBisectFinder(TestCase): def setUp(self): self.empty_list = [] # 10 self.one_element_list = [5] # 2, 5, 7 self.two_element_list = [3, 8] # 2, 3, 6, 8, 9 self.three_element_list = [2, 7, 7] # 1, 2, 4, 7, 8 self.four_element_list = [2, 2, 2, 5] # 1, 2, 4, 5, 6 self.five_element_list = [1, 5, 5, 5, 9] # 0, 1, 2, 5, 7, 9, 10 # Tests for the find_left_lt function def test_find_left_lt_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.empty_list, 10) def test_find_left_lt_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.one_element_list, 2) self.assertRaises(ValueError, BisectFinder.find_left_lt, self.one_element_list, 5) self.assertEqual(BisectFinder.find_left_lt(self.one_element_list, 7), 0) def test_find_left_lt_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.two_element_list, 2) self.assertRaises(ValueError, BisectFinder.find_left_lt, self.two_element_list, 3) self.assertEqual(BisectFinder.find_left_lt(self.two_element_list, 6), 0) self.assertEqual(BisectFinder.find_left_lt(self.two_element_list, 8), 0) self.assertEqual(BisectFinder.find_left_lt(self.two_element_list, 9), 1) def test_find_left_lt_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.three_element_list, 1) self.assertRaises(ValueError, BisectFinder.find_left_lt, self.three_element_list, 2) self.assertEqual(BisectFinder.find_left_lt(self.three_element_list, 4), 0) self.assertEqual(BisectFinder.find_left_lt(self.three_element_list, 7), 0) self.assertEqual(BisectFinder.find_left_lt(self.three_element_list, 8), 1) def test_find_left_lt_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.four_element_list, 1) self.assertRaises(ValueError, BisectFinder.find_left_lt, self.four_element_list, 2) self.assertEqual(BisectFinder.find_left_lt(self.four_element_list, 4), 0) self.assertEqual(BisectFinder.find_left_lt(self.four_element_list, 5), 0) self.assertEqual(BisectFinder.find_left_lt(self.four_element_list, 6), 3) def test_find_left_lt_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_lt, self.five_element_list, 0) self.assertRaises(ValueError, BisectFinder.find_left_lt, self.five_element_list, 1) self.assertEqual(BisectFinder.find_left_lt(self.five_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_lt(self.five_element_list, 5), 0) self.assertEqual(BisectFinder.find_left_lt(self.five_element_list, 7), 1) self.assertEqual(BisectFinder.find_left_lt(self.five_element_list, 9), 1) self.assertEqual(BisectFinder.find_left_lt(self.five_element_list, 10), 4) # Tests for the find_left_le function def test_find_left_le_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.empty_list, 10) def test_find_left_le_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.one_element_list, 2) self.assertEqual(BisectFinder.find_left_le(self.one_element_list, 5), 0) self.assertEqual(BisectFinder.find_left_le(self.one_element_list, 7), 0) def test_find_left_le_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.two_element_list, 2) self.assertEqual(BisectFinder.find_left_le(self.two_element_list, 3), 0) self.assertEqual(BisectFinder.find_left_le(self.two_element_list, 6), 0) self.assertEqual(BisectFinder.find_left_le(self.two_element_list, 8), 1) self.assertEqual(BisectFinder.find_left_le(self.two_element_list, 9), 1) def test_find_left_le_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.three_element_list, 1) self.assertEqual(BisectFinder.find_left_le(self.three_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_le(self.three_element_list, 4), 0) self.assertEqual(BisectFinder.find_left_le(self.three_element_list, 7), 1) self.assertEqual(BisectFinder.find_left_le(self.three_element_list, 8), 1) def test_find_left_le_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.four_element_list, 1) self.assertEqual(BisectFinder.find_left_le(self.four_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_le(self.four_element_list, 4), 0) self.assertEqual(BisectFinder.find_left_le(self.four_element_list, 5), 3) self.assertEqual(BisectFinder.find_left_le(self.four_element_list, 6), 3) def test_find_left_le_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_le, self.five_element_list, 0) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 5), 1) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 7), 1) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 9), 4) self.assertEqual(BisectFinder.find_left_le(self.five_element_list, 10), 4) # Tests for the find_left_eq function def test_find_left_eq_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.empty_list, 10) def test_find_left_eq_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.one_element_list, 2) self.assertEqual(BisectFinder.find_left_eq(self.one_element_list, 5), 0) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.one_element_list, 7) def test_find_left_eq_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.two_element_list, 2) self.assertEqual(BisectFinder.find_left_eq(self.two_element_list, 3), 0) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.two_element_list, 6) self.assertEqual(BisectFinder.find_left_eq(self.two_element_list, 8), 1) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.two_element_list, 9) def test_find_left_eq_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.three_element_list, 1) self.assertEqual(BisectFinder.find_left_eq(self.three_element_list, 2), 0) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.three_element_list, 4) self.assertEqual(BisectFinder.find_left_eq(self.three_element_list, 7), 1) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.three_element_list, 8) def test_find_left_eq_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.four_element_list, 1) self.assertEqual(BisectFinder.find_left_eq(self.four_element_list, 2), 0) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.four_element_list, 4) self.assertEqual(BisectFinder.find_left_eq(self.four_element_list, 5), 3) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.four_element_list, 6) def test_find_left_eq_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_left_eq, self.five_element_list, 0) self.assertEqual(BisectFinder.find_left_eq(self.five_element_list, 1), 0) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.five_element_list, 2) self.assertEqual(BisectFinder.find_left_eq(self.five_element_list, 5), 1) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.five_element_list, 7) self.assertEqual(BisectFinder.find_left_eq(self.five_element_list, 9), 4) self.assertRaises(ValueError, BisectFinder.find_left_eq, self.five_element_list, 10) # Tests for the find_left_ge function def test_find_left_ge_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_left_ge, self.empty_list, 10) def test_find_left_ge_one_element_list(self): self.assertEqual(BisectFinder.find_left_ge(self.one_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_ge(self.one_element_list, 5), 0) self.assertRaises(ValueError, BisectFinder.find_left_ge, self.one_element_list, 7) def test_find_left_ge_two_element_list(self): self.assertEqual(BisectFinder.find_left_ge(self.two_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_ge(self.two_element_list, 3), 0) self.assertEqual(BisectFinder.find_left_ge(self.two_element_list, 6), 1) self.assertEqual(BisectFinder.find_left_ge(self.two_element_list, 8), 1) self.assertRaises(ValueError, BisectFinder.find_left_ge, self.two_element_list, 9) def test_find_left_ge_three_element_list(self): self.assertEqual(BisectFinder.find_left_ge(self.three_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_ge(self.three_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_ge(self.three_element_list, 4), 1) self.assertEqual(BisectFinder.find_left_ge(self.three_element_list, 7), 1) self.assertRaises(ValueError, BisectFinder.find_left_ge, self.three_element_list, 8) def test_find_left_ge_four_element_list(self): self.assertEqual(BisectFinder.find_left_ge(self.four_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_ge(self.four_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_ge(self.four_element_list, 4), 3) self.assertEqual(BisectFinder.find_left_ge(self.four_element_list, 5), 3) self.assertRaises(ValueError, BisectFinder.find_left_ge, self.four_element_list, 6) def test_find_left_ge_five_element_list(self): self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 0), 0) self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 2), 1) self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 5), 1) self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 7), 4) self.assertEqual(BisectFinder.find_left_ge(self.five_element_list, 9), 4) self.assertRaises(ValueError, BisectFinder.find_left_ge, self.five_element_list, 10) # Tests for the find_left_gt function def test_find_left_gt_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_left_gt, self.empty_list, 10) def test_find_left_gt_one_element_list(self): self.assertEqual(BisectFinder.find_left_gt(self.one_element_list, 2), 0) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.one_element_list, 5) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.one_element_list, 7) def test_find_left_gt_two_element_list(self): self.assertEqual(BisectFinder.find_left_gt(self.two_element_list, 2), 0) self.assertEqual(BisectFinder.find_left_gt(self.two_element_list, 3), 1) self.assertEqual(BisectFinder.find_left_gt(self.two_element_list, 6), 1) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.two_element_list, 8) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.two_element_list, 9) def test_find_left_gt_three_element_list(self): self.assertEqual(BisectFinder.find_left_gt(self.three_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_gt(self.three_element_list, 2), 1) self.assertEqual(BisectFinder.find_left_gt(self.three_element_list, 4), 1) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.three_element_list, 7) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.three_element_list, 8) def test_find_left_gt_four_element_list(self): self.assertEqual(BisectFinder.find_left_gt(self.four_element_list, 1), 0) self.assertEqual(BisectFinder.find_left_gt(self.four_element_list, 2), 3) self.assertEqual(BisectFinder.find_left_gt(self.four_element_list, 4), 3) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.four_element_list, 5) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.four_element_list, 6) def test_find_left_gt_five_element_list(self): self.assertEqual(BisectFinder.find_left_gt(self.five_element_list, 0), 0) self.assertEqual(BisectFinder.find_left_gt(self.five_element_list, 1), 1) self.assertEqual(BisectFinder.find_left_gt(self.five_element_list, 2), 1) self.assertEqual(BisectFinder.find_left_gt(self.five_element_list, 5), 4) self.assertEqual(BisectFinder.find_left_gt(self.five_element_list, 7), 4) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.five_element_list, 9) self.assertRaises(ValueError, BisectFinder.find_left_gt, self.five_element_list, 10) # Tests for the find_right_lt function def test_find_right_lt_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.empty_list, 10) def test_find_right_lt_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.one_element_list, 2) self.assertRaises(ValueError, BisectFinder.find_right_lt, self.one_element_list, 5) self.assertEqual(BisectFinder.find_right_lt(self.one_element_list, 7), 0) def test_find_right_lt_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.two_element_list, 2) self.assertRaises(ValueError, BisectFinder.find_right_lt, self.two_element_list, 3) self.assertEqual(BisectFinder.find_right_lt(self.two_element_list, 6), 0) self.assertEqual(BisectFinder.find_right_lt(self.two_element_list, 8), 0) self.assertEqual(BisectFinder.find_right_lt(self.two_element_list, 9), 1) def test_find_right_lt_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.three_element_list, 1) self.assertRaises(ValueError, BisectFinder.find_right_lt, self.three_element_list, 2) self.assertEqual(BisectFinder.find_right_lt(self.three_element_list, 4), 0) self.assertEqual(BisectFinder.find_right_lt(self.three_element_list, 7), 0) self.assertEqual(BisectFinder.find_right_lt(self.three_element_list, 8), 2) def test_find_right_lt_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.four_element_list, 1) self.assertRaises(ValueError, BisectFinder.find_right_lt, self.four_element_list, 2) self.assertEqual(BisectFinder.find_right_lt(self.four_element_list, 4), 2) self.assertEqual(BisectFinder.find_right_lt(self.four_element_list, 5), 2) self.assertEqual(BisectFinder.find_right_lt(self.four_element_list, 6), 3) def test_find_right_lt_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_lt, self.five_element_list, 0) self.assertRaises(ValueError, BisectFinder.find_right_lt, self.five_element_list, 1) self.assertEqual(BisectFinder.find_right_lt(self.five_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_lt(self.five_element_list, 5), 0) self.assertEqual(BisectFinder.find_right_lt(self.five_element_list, 7), 3) self.assertEqual(BisectFinder.find_right_lt(self.five_element_list, 9), 3) self.assertEqual(BisectFinder.find_right_lt(self.five_element_list, 10), 4) # Tests for the find_right_le function def test_find_right_le_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.empty_list, 10) def test_find_right_le_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.one_element_list, 2) self.assertEqual(BisectFinder.find_right_le(self.one_element_list, 5), 0) self.assertEqual(BisectFinder.find_right_le(self.one_element_list, 7), 0) def test_find_right_le_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.two_element_list, 2) self.assertEqual(BisectFinder.find_right_le(self.two_element_list, 3), 0) self.assertEqual(BisectFinder.find_right_le(self.two_element_list, 6), 0) self.assertEqual(BisectFinder.find_right_le(self.two_element_list, 8), 1) self.assertEqual(BisectFinder.find_right_le(self.two_element_list, 9), 1) def test_find_right_le_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.three_element_list, 1) self.assertEqual(BisectFinder.find_right_le(self.three_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_le(self.three_element_list, 4), 0) self.assertEqual(BisectFinder.find_right_le(self.three_element_list, 7), 2) self.assertEqual(BisectFinder.find_right_le(self.three_element_list, 8), 2) def test_find_right_le_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.four_element_list, 1) self.assertEqual(BisectFinder.find_right_le(self.four_element_list, 2), 2) self.assertEqual(BisectFinder.find_right_le(self.four_element_list, 4), 2) self.assertEqual(BisectFinder.find_right_le(self.four_element_list, 5), 3) self.assertEqual(BisectFinder.find_right_le(self.four_element_list, 6), 3) def test_find_right_le_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_le, self.five_element_list, 0) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 1), 0) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 5), 3) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 7), 3) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 9), 4) self.assertEqual(BisectFinder.find_right_le(self.five_element_list, 10), 4) # Tests for the find_right_eq function def test_find_right_eq_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.empty_list, 10) def test_find_right_eq_one_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.one_element_list, 2) self.assertEqual(BisectFinder.find_right_eq(self.one_element_list, 5), 0) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.one_element_list, 7) def test_find_right_eq_two_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.two_element_list, 2) self.assertEqual(BisectFinder.find_right_eq(self.two_element_list, 3), 0) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.two_element_list, 6) self.assertEqual(BisectFinder.find_right_eq(self.two_element_list, 8), 1) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.two_element_list, 9) def test_find_right_eq_three_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.three_element_list, 1) self.assertEqual(BisectFinder.find_right_eq(self.three_element_list, 2), 0) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.three_element_list, 4) self.assertEqual(BisectFinder.find_right_eq(self.three_element_list, 7), 2) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.three_element_list, 8) def test_find_right_eq_four_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.four_element_list, 1) self.assertEqual(BisectFinder.find_right_eq(self.four_element_list, 2), 2) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.four_element_list, 4) self.assertEqual(BisectFinder.find_right_eq(self.four_element_list, 5), 3) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.four_element_list, 6) def test_find_right_eq_five_element_list(self): self.assertRaises(ValueError, BisectFinder.find_right_eq, self.five_element_list, 0) self.assertEqual(BisectFinder.find_right_eq(self.five_element_list, 1), 0) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.five_element_list, 2) self.assertEqual(BisectFinder.find_right_eq(self.five_element_list, 5), 3) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.five_element_list, 7) self.assertEqual(BisectFinder.find_right_eq(self.five_element_list, 9), 4) self.assertRaises(ValueError, BisectFinder.find_right_eq, self.five_element_list, 10) # Tests for the find_right_ge function def test_find_right_ge_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_right_ge, self.empty_list, 10) def test_find_right_ge_one_element_list(self): self.assertEqual(BisectFinder.find_right_ge(self.one_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_ge(self.one_element_list, 5), 0) self.assertRaises(ValueError, BisectFinder.find_right_ge, self.one_element_list, 7) def test_find_right_ge_two_element_list(self): self.assertEqual(BisectFinder.find_right_ge(self.two_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_ge(self.two_element_list, 3), 0) self.assertEqual(BisectFinder.find_right_ge(self.two_element_list, 6), 1) self.assertEqual(BisectFinder.find_right_ge(self.two_element_list, 8), 1) self.assertRaises(ValueError, BisectFinder.find_right_ge, self.two_element_list, 9) def test_find_right_ge_three_element_list(self): self.assertEqual(BisectFinder.find_right_ge(self.three_element_list, 1), 0) self.assertEqual(BisectFinder.find_right_ge(self.three_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_ge(self.three_element_list, 4), 2) self.assertEqual(BisectFinder.find_right_ge(self.three_element_list, 7), 2) self.assertRaises(ValueError, BisectFinder.find_right_ge, self.three_element_list, 8) def test_find_right_ge_four_element_list(self): self.assertEqual(BisectFinder.find_right_ge(self.four_element_list, 1), 2) self.assertEqual(BisectFinder.find_right_ge(self.four_element_list, 2), 2) self.assertEqual(BisectFinder.find_right_ge(self.four_element_list, 4), 3) self.assertEqual(BisectFinder.find_right_ge(self.four_element_list, 5), 3) self.assertRaises(ValueError, BisectFinder.find_right_ge, self.four_element_list, 6) def test_find_right_ge_five_element_list(self): self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 0), 0) self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 1), 0) self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 2), 3) self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 5), 3) self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 7), 4) self.assertEqual(BisectFinder.find_right_ge(self.five_element_list, 9), 4) self.assertRaises(ValueError, BisectFinder.find_right_ge, self.five_element_list, 10) # Tests for the find_right_gt function def test_find_right_gt_empty_list(self): self.assertRaises(ValueError, BisectFinder.find_right_gt, self.empty_list, 10) def test_find_right_gt_one_element_list(self): self.assertEqual(BisectFinder.find_right_gt(self.one_element_list, 2), 0) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.one_element_list, 5) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.one_element_list, 7) def test_find_right_gt_two_element_list(self): self.assertEqual(BisectFinder.find_right_gt(self.two_element_list, 2), 0) self.assertEqual(BisectFinder.find_right_gt(self.two_element_list, 3), 1) self.assertEqual(BisectFinder.find_right_gt(self.two_element_list, 6), 1) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.two_element_list, 8) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.two_element_list, 9) def test_find_right_gt_three_element_list(self): self.assertEqual(BisectFinder.find_right_gt(self.three_element_list, 1), 0) self.assertEqual(BisectFinder.find_right_gt(self.three_element_list, 2), 2) self.assertEqual(BisectFinder.find_right_gt(self.three_element_list, 4), 2) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.three_element_list, 7) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.three_element_list, 8) def test_find_right_gt_four_element_list(self): self.assertEqual(BisectFinder.find_right_gt(self.four_element_list, 1), 2) self.assertEqual(BisectFinder.find_right_gt(self.four_element_list, 2), 3) self.assertEqual(BisectFinder.find_right_gt(self.four_element_list, 4), 3) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.four_element_list, 5) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.four_element_list, 6) def test_find_right_gt_five_element_list(self): self.assertEqual(BisectFinder.find_right_gt(self.five_element_list, 0), 0) self.assertEqual(BisectFinder.find_right_gt(self.five_element_list, 1), 3) self.assertEqual(BisectFinder.find_right_gt(self.five_element_list, 2), 3) self.assertEqual(BisectFinder.find_right_gt(self.five_element_list, 5), 4) self.assertEqual(BisectFinder.find_right_gt(self.five_element_list, 7), 4) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.five_element_list, 9) self.assertRaises(ValueError, BisectFinder.find_right_gt, self.five_element_list, 10) if __name__ == '__main__': unittest.main() 

Answer 1

testing approach

from unittest import TestCase 

Good!

You may wish to consider using hypothesis, as well. It does an amazing job of thinking up random test cases that you never would have, and then tries to distill them down to "simplest input which still produces Red bar".

BTW, implements seems an odd module name, which the Review Context never mentions.

AAA

The "arrange" part has been moved out to setUp, and the tests focus on "act, assert".

This can be good, if arranging is "hard" or tediously long, and especially if we arrange a common data structure which is used by multiple independent tests.

But here the separation is slightly distracting. I have a weak preference for seeing the one-line "arrange" setting a local variable which we use on the next line.

edge cases

I will focus on just one test; others follow a similar pattern.

In test_find_left_lt_one_element_list the element to be found is 5, and we systematically test {2, 5, 7}. I would rather have seen {4, 5, 6} being tested. When we wrote the target code we tried to correctly use < vs <= operators. The point of test code is to verify the right thing happened.

verbose tests

Oh my goodness, the tests just go on, cycling through {left, right} × {<, <=, ==, >=, >}. Humans aren't great at going through such enumerations. My eyes glaze over.

OK, you win, I guess factoring out all the "arrange" into setUpwas the right call, for these particular tests.

Yes, test code should be "very simple", and we embrace copy-n-paste for it. But after ten stanzas, I'm not sure these are exactly "simple", in the sense that I'm not doing a good job of eye-balling each one and deciding "oh yeah, this is the right answer" before reading what the assertion says.

Instead of these, or in addition to these, I would like to see some test logic that constructs a list so it knows the right answer, then verifies that the right answer is returned. It would accept list_length as a parameter.

And then add some hypothesis testing on top of that.

I'm starting to wish there was a (possibly _private) method that accepts a comparison operator. It would simplify cycling through the variants.

@staticmethod

There's nothing exactly wrong with using that decorator. But introducing a "container" class to organize the namespace is unnecessary, a module can certainly do that.

Consider using simple defs in a bisectfinder module.

signature

 def find_left_lt(a, x, lo=0, hi=None, key=None): 

Leaving a and x as type Any is fine, and caller will soon figure out that the Sequencea should contain elements of x's type, and the elements should support comparison.

Neglecting to point out that we return def ... ) -> int: seems like a missed opportunity. Plus, it makes mypy linting slightly harder for callers.

docstring

 '''Finds the index of the leftmost (among duplicates) element that is strictly less than X. A[index] < X A[index] == a2 

I appreciate the pithiness of that sentence.

The < X postcondition could clarify that it's a contract, it shall be true upon return. The notation upcases a and x where that doesn't seem necessary. I don't know where a2 came from, and if the intent is to promise some postcondition, I'm afraid I'm not quite getting it. The [ list ] which follows I found entirely obscure.

I was a little surprised to see no mention of the familiar bisect_left, for example to contrast their behavior. Plus, the meaning of key here matches its behavior in every way.

That familiar function is a total function. The docstring makes no mention that find_left_lt is a partial function which could very well raise. This is a serious omission and should be remedied.

custom exception

I'm not entirely comfortable with using ValueError for failures. It feels more like an IndexError happened -- "bad index", no matching index exists.

Consider defining your own exception, and have it inherit from IndexError. Then a caller a few levels up the call stack can focus on your specific exception if desired, or can choose to catch just IndexError or Exception if that's sufficient for caller's need.

 raise ValueError("No elements less than or equal to x found.") 

This is less informative than it could be. Put yourself in the shoes of some maintenance engineer who is staring at this message. First question is going to be "what was x?", right? Consider using an f-string to put the value of x in there.

I find it interesting that only the message changes between e.g. `find_right_ge` and `find_right_gt`. Perhaps the message template might become a keyword parameter.

simple comparisons

 if len(a) > 0 and index < len(a) + 1 and a[index - 1] < x: 

I find those three conjuncts harder to read than necessary. And I believe you do, too.

Let's tackle the middle one. It's a guard, but it's more obscure than needed. It could be:

 if ... and index - 1 < len(a) and a[index - 1] < x: 

which makes it transparently obvious that we're avoiding running off the end.

But bisect_left() is perfectly happy to return an index of 0. Don't we want to verify that index - 1 hasn't walked off the other end of the array?!?

I confess it is not completely clear to me how lo and hi figure into this. The test suite did not consider them, but it should.

The underlying bisect_left uses lo and hi, so there's a good case for keeping them as-is. Let me float a radical proposal. Consider accepting a single range argument, and then you pass .start and .stop to bisect_left. Or not, whatever. It slightly simplifies the promises and is perhaps a little easier to reason about in the presence of potential OBOBs.

postcondition

I really liked how the one sentence ("Finds the index...") states a contract. I would like it even more if it was believable, if I knew for certain it was always true after my call. There's an easy way to do that: use assert before returning.