API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
203
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 19.63 KB | None | 0 0
raw download clone embed print report
  1. """Module containing the unit tests for all questions."""
  2. import signal
  3. from stats import IS_MARKING_MODE
  4. import unittest
  5. import random
  6. import string
  7. from classes import *
  8. from top_k import top_k_select
  9. from top_k import top_k_heap
  10. from stats import StatCounter, KEY_COMPS
  11. from basic_priority_queue import BasicPriorityQueue
  12. from change_priority_queue import ChangePriorityQueue
  13. from dheap_priority_queue import DheapPriorityQueue
  14. from fast_priority_queue import FastPriorityQueue
  15.  
  16.  
  17. real_comparisons = StatCounter.get_count
  18.  
  19.  
  20.  
  21. class BaseTester(unittest.TestCase):
  22. """ Very simple base class that defines the setUp method """
  23.  
  24. def setUp(self):
  25. """ Resets the internal counter """
  26. StatCounter.unlock_counters() # in case it was left locked after a failed test
  27. StatCounter.reset_counts()
  28.  
  29.  
  30. class TestTopKTrivial(BaseTester):
  31. """Trivial submission tests"""
  32.  
  33. def test_top_k_select_trivial(self):
  34. """Tests the top_k_select function on a list of 10 integers."""
  35. test_data = list(range(10))
  36. random.shuffle(test_data)
  37. top_5, _ = top_k_select(test_data, 5)
  38. self.assertEqual(top_5, list(range(9, 4, -1)))
  39.  
  40. def test_top_k_select_trivial_real_comparisons(self):
  41. """Tests the number of comparisons the top_k_select function makes
  42. on a list of 10 integers.
  43. """
  44. test_data = list_of_keys(range(10))
  45. random.shuffle(test_data)
  46. _, comparisons = top_k_select(test_data, 5)
  47. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  48.  
  49. def test_top_k_heap_trivial(self):
  50. """Tests the top_k_select function on a list of 10 integers."""
  51. test_data = list(range(10))
  52. random.shuffle(test_data)
  53. top_5, _ = top_k_heap(test_data, 5)
  54. self.assertEqual(top_5, list(range(9, 4, -1)))
  55.  
  56.  
  57. class TestTopK(BaseTester):
  58. """Tests for Task 1 on finding the top k items."""
  59.  
  60. def test_top_k_select(self):
  61. """Tests the top_k_select function on a list of 1000 integers."""
  62. test_data = list(range(1000))
  63. random.shuffle(test_data)
  64. top_40, _ = top_k_select(test_data, 40)
  65. self.assertEqual(top_40, list(range(999, 959, -1)))
  66.  
  67. def test_top_k_select_comparisons(self):
  68. """Tests the number of comparisons the top_k_select function makes
  69. on a list of 1000 integers.
  70. """
  71. test_data = list_of_keys(range(1000))
  72. random.shuffle(test_data)
  73. _, comparisons = top_k_select(test_data, 40)
  74. self.assertLess(comparisons, 40000)
  75. self.assertGreater(comparisons, 30000)
  76.  
  77. def test_top_k_select_real_comparisons(self):
  78. """Tests the number of comparisons the top_k_select function makes
  79. on a list of 1000 integers.
  80. """
  81. test_data = list_of_keys(range(1000))
  82. random.shuffle(test_data)
  83. _, comparisons = top_k_select(test_data, 40)
  84. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  85.  
  86. def test_top_k_heap(self):
  87. """Tests the top_k_heap function on a list of 1000 integers."""
  88. test_data = list(range(1000))
  89. random.shuffle(test_data)
  90. top_40, _ = top_k_heap(test_data, 40)
  91. expected_top_40 = list(range(999, 959, -1))
  92. self.assertEqual(top_40, expected_top_40)
  93.  
  94. def test_top_k_heap_comparisons(self):
  95. """Tests the number of comparisons made by the top_k_heap function
  96. on a list of 1000 integers.
  97. """
  98. test_data = list(range(1000))
  99. random.shuffle(test_data)
  100. _, comparisons = top_k_heap(test_data, 40)
  101. self.assertLess(comparisons, 10400)
  102. self.assertGreater(comparisons, 1040)
  103.  
  104. def test_top_k_heap_real_comparisons(self):
  105. """Tests the number of comparisons made by the top_k_heap function
  106. on a list of 1000 integers.
  107. """
  108. test_data = list_of_keys(range(1000))
  109. random.shuffle(test_data)
  110. _, comparisons = top_k_heap(test_data, 40)
  111. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  112.  
  113.  
  114. class TestFastPriorityQueueTrivial(BaseTester):
  115. """Tests for Task 2 on fast heapify."""
  116.  
  117. def test_fast_heapify_trivial(self):
  118. """Tests that heapify works on a trivial test case in sorted order."""
  119. fpq = FastPriorityQueue(list(range(6)))
  120. self.assertEqual(len(fpq), 6)
  121. self.assertEqual(fpq.validate(), True)
  122.  
  123. def test_fast_heapify_random_data_trivial(self):
  124. """Tests that heapify works on a trivial test case in random order."""
  125. test_data = list(range(6))
  126. random.shuffle(test_data)
  127. fpq = FastPriorityQueue(test_data)
  128. self.assertEqual(len(fpq), 6)
  129. self.assertEqual(fpq.validate(), True)
  130.  
  131.  
  132. class TestFastPriorityQueue(BaseTester):
  133. """Tests for Task 2 on fast heapify."""
  134.  
  135. def test_fast_heapify_small(self):
  136. """Tests that heapify works on a small test case in sorted order."""
  137. fpq = FastPriorityQueue(list(range(10)))
  138. self.assertEqual(len(fpq), 10)
  139. self.assertEqual(fpq.validate(), True)
  140.  
  141. def test_fast_heapify_random_data_small(self):
  142. """Tests that heapify works on a small test case in random order."""
  143. test_data = list(range(100))
  144. random.shuffle(test_data)
  145. fpq = FastPriorityQueue(test_data)
  146. self.assertEqual(len(fpq), 100)
  147. self.assertEqual(fpq.validate(), True)
  148.  
  149. def test_fast_heapify_medium(self):
  150. """Tests that heapify works on a range of sizes - with sorted data"""
  151. max_depth = 16
  152. for size in [2**n for n in range(2, max_depth+1, 2)]:
  153. fpq = FastPriorityQueue(list(range(size)))
  154. self.assertEqual(len(fpq), size)
  155. self.assertEqual(fpq.validate(), True)
  156.  
  157. def test_fast_heapify_random_data_medium(self):
  158. """Tests that heapify works on a range of sizes - with random data"""
  159. max_depth = 16
  160. for size in [2**n for n in range(2, max_depth+1, 2)]:
  161. test_data = list(range(1000))
  162. random.shuffle(test_data)
  163. fpq = FastPriorityQueue(test_data)
  164. self.assertEqual(len(fpq), 1000)
  165. self.assertEqual(fpq.validate(), True)
  166.  
  167. # Your tests for testing the number of comparisons should go here if
  168. # you choose to use the unit testing framework.
  169. # Your code here is not marked but we will check that
  170. # your FastPriorityQueue manages to heapify with O(n) key comparisons
  171. # and that your FastPriorityQueue counts any key comparisons correctly.
  172.  
  173.  
  174. class TestFastPriorityQueueHugemongous(BaseTester):
  175. """Tests for Task 2 on fast heapify."""
  176.  
  177. def test_fast_heapify_hugemongous(self):
  178. """Tests that heapify works on a range of sizes - with sorted data"""
  179. min_depth = 8
  180. max_depth = 12
  181. for size in [2**n for n in range(min_depth, max_depth+1, 2)]:
  182. fpq = FastPriorityQueue(list(range(size)))
  183. self.assertEqual(len(fpq), size)
  184. self.assertEqual(fpq.validate(), True)
  185.  
  186. def test_fast_heapify_random_data_hugemongous(self):
  187. """Tests that heapify works on a range of sizes - with random data"""
  188. min_depth = 8
  189. max_depth = 12
  190. for size in [2**n for n in range(min_depth, max_depth+1, 2)]:
  191. test_data = list(range(1000))
  192. random.shuffle(test_data)
  193. fpq = FastPriorityQueue(test_data)
  194. self.assertEqual(len(fpq), 1000)
  195. self.assertEqual(fpq.validate(), True)
  196.  
  197.  
  198. class TestChangePriorityQueueTrivial(BaseTester):
  199. """Trivial test for pre-check on quiz server."""
  200.  
  201. def test_cpq_trivial(self):
  202. """Tests the pop_max method on a small 3 item example."""
  203. test_priorities = list_of_keys([3, 2, 1])
  204. test_data = list(string.ascii_lowercase)[:len(test_priorities)]
  205. cpq = ChangePriorityQueue(test_data, test_priorities)
  206. self.assertEqual(len(cpq), 3)
  207. self.assertEqual(cpq._item_indices['c'], 2)
  208. self.assertEqual(cpq.pop_max(), 'a')
  209. self.assertEqual(len(cpq), 2)
  210. self.assertEqual(cpq._item_indices['b'], 0)
  211. self.assertEqual(cpq.validate(), True)
  212. cpq.remove_item('c')
  213. self.assertEqual(cpq.validate(), True)
  214.  
  215.  
  216. class TestChangePriorityQueue(BaseTester):
  217. """Tests for Task 3 on removing from a priority queue."""
  218.  
  219. def test_cpq_heapify(self):
  220. """Tests that heapify still works correctly. Note this effectively
  221. tests whether swap items is swapping the items correctly and that
  222. the __init__ function has not been modified.
  223. """
  224. test_data = [str(digit) for digit in range(1000)]
  225. test_priorities = list_of_keys(list(range(1000)))
  226. random.shuffle(test_priorities)
  227. cpq = ChangePriorityQueue(test_data, test_priorities)
  228. self.assertEqual(len(cpq), 1000)
  229. self.assertEqual(cpq.validate(), True)
  230.  
  231. def test_cpq_peek_max(self):
  232. """Tests the peek_max method on a small example."""
  233. cpq = ChangePriorityQueue()
  234. cpq.insert_with_priority(Key(1), 'a')
  235. cpq.insert_with_priority(Key(3), 'b')
  236. cpq.insert_with_priority(Key(8), 'c')
  237. cpq.insert_with_priority(Key(0), 'd')
  238. cpq.insert_with_priority(Key(4), 'e')
  239. self.assertEqual(cpq.peek_max(), 'c')
  240.  
  241. def test_cpq_pop_max(self):
  242. """Tests the pop_max method on a small 7 item example."""
  243. test_priorities = list_of_keys([3, 67, 65, 8, 412, 1, 22])
  244. test_data = list(string.ascii_lowercase)[:len(test_priorities)]
  245. cpq = ChangePriorityQueue(test_data, test_priorities)
  246. self.assertEqual(len(cpq), 7)
  247. self.assertEqual(cpq._item_indices['g'], 6)
  248. self.assertEqual(cpq.pop_max(), 'e')
  249. self.assertEqual(len(cpq), 6)
  250. self.assertEqual(cpq._item_indices['g'], 1)
  251. self.assertEqual(cpq.validate(), True)
  252.  
  253. def test_cpq_pop_max_comparisons(self):
  254. """Tests the pop_max method on a small 7 item example."""
  255. test_priorities = list_of_keys([3, 67, 65, 8, 412, 1, 22])
  256. test_data = list(string.ascii_lowercase)[:len(test_priorities)]
  257. cpq = ChangePriorityQueue(test_data, test_priorities)
  258. self.assertEqual(len(cpq), 7)
  259. self.assertEqual(cpq._item_indices['g'], 6)
  260. # reset counters so only comparisons used during pop max are counted
  261. StatCounter.reset_counts()
  262. cpq.reset_comparisons()
  263. self.assertEqual(cpq.pop_max(), 'e')
  264. comparisons = cpq.get_comparisons()
  265. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  266. self.assertEqual(len(cpq), 6)
  267. self.assertEqual(cpq._item_indices['g'], 1)
  268. self.assertEqual(cpq.validate(), True)
  269.  
  270. def test_cpq_real_comps_insert_with_priority(self):
  271. """Tests the insert_with_priority method on a small example."""
  272. cpq = ChangePriorityQueue()
  273. cpq.insert_with_priority(Key(1), 'a')
  274. cpq.insert_with_priority(Key(3), 'b')
  275. cpq.insert_with_priority(Key(8), 'c')
  276. cpq.insert_with_priority(Key(0), 'd')
  277. cpq.insert_with_priority(Key(0), 'e')
  278. comparisons = cpq.get_comparisons()
  279. self.assertEqual(len(cpq), 5)
  280. self.assertEqual(cpq.validate(), True)
  281. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  282.  
  283. def test_cpq_remove_item(self):
  284. """Tests the remove_item method on a small 7 item example."""
  285. test_priorities = list_of_keys([3, 67, 65, 8, 412, 1, 22])
  286. test_data = list(string.ascii_lowercase)[:len(test_priorities)]
  287. cpq = ChangePriorityQueue(test_data, test_priorities)
  288. self.assertEqual(len(cpq), 7)
  289. self.assertEqual(cpq.pop_max(), 'e')
  290. self.assertEqual(len(cpq), 6)
  291. # reset counters so only comparisons used during pop max are counted
  292. StatCounter.reset_counts()
  293. cpq.reset_comparisons()
  294. cpq.remove_item('g')
  295. comparisons = cpq.get_comparisons()
  296. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  297. cpq.remove_item('g') # g no longer in heap should do nothing
  298. self.assertEqual(cpq.remove_item(3), None) # 3 isn't a value ...
  299. self.assertEqual(cpq.validate(), True)
  300. self.assertEqual(len(cpq), 5)
  301. self.assertEqual(cpq.pop_max(), 'b')
  302. self.assertEqual(cpq.validate(), True)
  303. self.assertEqual(cpq.pop_max(), 'c')
  304. self.assertEqual(cpq.validate(), True)
  305. # reset counters so only comparisons used during remove are counted
  306. StatCounter.reset_counts()
  307. cpq.reset_comparisons()
  308. cpq.remove_item('d')
  309. comparisons = cpq.get_comparisons()
  310. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  311. self.assertEqual(cpq.validate(), True)
  312. # reset counters so only comparisons used during remove are counted
  313. StatCounter.reset_counts()
  314. cpq.reset_comparisons()
  315. cpq.remove_item('d')
  316. comparisons = cpq.get_comparisons()
  317. self.assertEqual(comparisons, real_comparisons(KEY_COMPS))
  318. self.assertEqual(cpq.validate(), True)
  319. self.assertEqual(len(cpq._item_indices), 2)
  320. self.assertEqual(cpq._item_indices['a'], 0)
  321. self.assertEqual(cpq._item_indices['f'], 1)
  322. self.assertEqual(cpq.validate(), True)
  323.  
  324.  
  325. class TestDheapPriorityQueueTrivial(BaseTester):
  326. """Trivial tests used for pre-testing on quiz server"""
  327.  
  328. def test_insert_trivial_d5(self):
  329. """Tests whether insert still works correctly with a few items and d=5."""
  330. dpq = DheapPriorityQueue(branch_factor=5)
  331. for key in list_of_keys([5, 4, 6, 3, 2, 7]):
  332. dpq.insert(key)
  333. self.assertEqual(dpq.validate(), True)
  334. self.assertEqual(len(dpq), 6)
  335. self.assertEqual(dpq.validate(), True)
  336.  
  337.  
  338. class TestDheapPriorityQueue(BaseTester):
  339. """Some tests for d-heaps. You should write some more, of course!"""
  340.  
  341. def test_parent_index(self):
  342. """Tests whether the correct parent index is found with d=5."""
  343. dpq = DheapPriorityQueue(list_of_keys(range(100)), 5)
  344. self.assertEqual(dpq._parent_index(6), 1)
  345. self.assertEqual(dpq._parent_index(10), 1)
  346. self.assertEqual(dpq._parent_index(30), 5)
  347. # index 0 has no parent node.
  348. self.assertEqual(dpq._parent_index(0), -1)
  349. # 100 is not in the d-heap.
  350. self.assertEqual(dpq._parent_index(100), -1)
  351.  
  352. def test_children_indices(self):
  353. """Tests whether the correct children indices are found with d=7."""
  354. dpq = DheapPriorityQueue(list_of_keys(range(100)), 7)
  355. self.assertEqual(sorted(dpq._children_indices(0)), list(range(1, 8)))
  356. self.assertEqual(sorted(dpq._children_indices(10)),
  357. list(range(71, 78)))
  358.  
  359. def test_heapify(self):
  360. """Tests whether heapify still works correctly in a large case with d=7."""
  361. dpq = DheapPriorityQueue(list_of_keys(range(10000)), 7)
  362. self.assertEqual(len(dpq), 10000)
  363. self.assertEqual(dpq.validate(), True)
  364.  
  365. def test_insert_small_d6(self):
  366. """Tests whether insert still works correctly with a few items and d=6."""
  367. dpq = DheapPriorityQueue(branch_factor=6)
  368. for key in list_of_keys([5, 4, 6, 3, 2, 7]):
  369. dpq.insert(key)
  370. self.assertEqual(dpq.validate(), True)
  371. self.assertEqual(len(dpq), 6)
  372. self.assertEqual(dpq.validate(), True)
  373.  
  374. def test_insert_medium_d6(self):
  375. """Tests whether insert still works correctly with a few items and d=6."""
  376. dpq = DheapPriorityQueue(branch_factor=6)
  377. test_data = list_of_keys(range(1000))
  378. random.shuffle(test_data)
  379. for item in test_data:
  380. dpq.insert(item)
  381. self.assertEqual(dpq.validate(), True)
  382. self.assertEqual(len(dpq), 1000)
  383.  
  384. def test_pop_max_small(self):
  385. """Tests whether pop_max still works correctly in a small case with d=3."""
  386. dpq = DheapPriorityQueue(list_of_keys([3, 67, 65, 8, 412, 1, 22]), 3)
  387. self.assertEqual(len(dpq), 7)
  388. self.assertEqual(dpq.pop_max(), Key(412))
  389. self.assertEqual(len(dpq), 6)
  390. self.assertEqual(dpq.validate(), True)
  391.  
  392. def test_pop_max_medium(self):
  393. """Tests whether pop_max still works correctly in a medium case with d=13."""
  394. start_data = list_of_keys((range(1000)))
  395. random.shuffle(start_data)
  396. dpq = DheapPriorityQueue(start_data, 13)
  397. for item in list_of_keys(range(999, 800, -1)):
  398. self.assertEqual(dpq.pop_max(), item)
  399. self.assertEqual(dpq.validate(), True)
  400. self.assertEqual(len(dpq), 801)
  401. self.assertEqual(dpq.validate(), True)
  402.  
  403.  
  404. class TestDheapPriorityQueueLarge(BaseTester):
  405. """Some large tests for d-heaps. You should write some more, of course!"""
  406.  
  407. def test_insert_large_d6(self):
  408. """Tests whether insert still works correctly with a few items and d=6."""
  409. d = 6
  410. n_items = 2048
  411. dpq = DheapPriorityQueue(branch_factor=d)
  412. test_data = list_of_keys(range(n_items))
  413. random.shuffle(test_data)
  414. for item in test_data:
  415. dpq.insert(item)
  416. self.assertEqual(dpq.validate(), True)
  417. self.assertEqual(len(dpq), n_items)
  418.  
  419. def test_pop_max_large_d13(self):
  420. """Tests whether pop_max still works correctly in a large case with d=13."""
  421. dpq = DheapPriorityQueue(list_of_keys(range(10000)), 13)
  422. for item in list_of_keys(range(9999, 8000, -1)):
  423. self.assertEqual(dpq.pop_max(), item)
  424. self.assertEqual(dpq.validate(), True)
  425. self.assertEqual(len(dpq), 8001)
  426. self.assertEqual(dpq.validate(), True)
  427.  
  428.  
  429.  
  430.  
  431. def make_all_tests_suite():
  432. """Returns a unit_test suite containing all desired tests."""
  433. suite = unittest.TestSuite()
  434.  
  435. # TopK tests - write some more of your own :)
  436. suite.addTest(unittest.makeSuite(TestTopKTrivial))
  437. suite.addTest(unittest.makeSuite(TestTopK))
  438.  
  439. # uncomment the next lines when ready to rumble with those tests
  440. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueTrivial))
  441. # suite.addTest(unittest.makeSuite(TestFastPriorityQueue))
  442. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueHugemongous))
  443.  
  444. # suite.addTest(unittest.makeSuite(TestChangePriorityQueueTrivial))
  445. # suite.addTest(unittest.makeSuite(TestChangePriorityQueue))
  446.  
  447. # suite.addTest(unittest.makeSuite(TestDheapPriorityQueueTrivial))
  448. # suite.addTest(unittest.makeSuite(TestDheapPriorityQueue))
  449. # suite.addTest(unittest.makeSuite(TestDheapPriorityQueueLarge))
  450.  
  451. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueComparisons))
  452. # suite.addTest(unittest.makeSuite(TestBasicPriorityQueue))
  453. return suite
  454.  
  455.  
  456. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueTrivial))
  457. # suite.addTest(unittest.makeSuite(TestFastPriorityQueue))
  458. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueHugemongous))
  459. # suite.addTest(unittest.makeSuite(TestChangePriorityQueueTrivial))
  460. # suite.addTest(unittest.makeSuite(TestChangePriorityQueue))
  461. # suite.addTest(unittest.makeSuite(TestDheapPriorityQueueTrivial))
  462. # suite.addTest(unittest.makeSuite(TestDheapPriorityQueue))
  463. # # suite.addTest(unittest.makeSuite(TestDheapPriorityQueueLarge))
  464. # suite.addTest(unittest.makeSuite(TestFastPriorityQueueComparisons))
  465. return suite
  466.  
  467.  
  468. def main():
  469. """Runs all tests returned by all_tests_suite()."""
  470. test_runner = unittest.TextTestRunner(verbosity=2)
  471. test_suite = make_all_tests_suite()
  472. test_runner.run(test_suite)
  473.  
  474.  
  475. if __name__ == '__main__':
  476. main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!