| | | 1 | | #include <stdio.h> |
| | | 2 | | #include <assert.h> |
| | | 3 | | #include <stdbool.h> |
| | | 4 | | #include "../../core/data_structures/heap.h" |
| | | 5 | | |
| | 1 | 6 | | void test_heap_init() { |
| | | 7 | | Heap h; |
| | 1 | 8 | | initHeap(&h); |
| | 1 | 9 | | assert(h.count == 0); |
| | 1 | 10 | | assert(getHeapSize(&h) == 0); |
| | 1 | 11 | | printf("[PASS] test_heap_init\n"); |
| | 1 | 12 | | } |
| | | 13 | | |
| | 1 | 14 | | void test_heap_insert_extract() { |
| | | 15 | | Heap h; |
| | 1 | 16 | | initHeap(&h); |
| | | 17 | | |
| | 1 | 18 | | Task t1 = {1, 10, 1000}; |
| | 1 | 19 | | Task t2 = {2, 50, 1001}; // Highest priority |
| | 1 | 20 | | Task t3 = {3, 30, 1002}; |
| | | 21 | | |
| | 1 | 22 | | assert(insertHeap(&h, t1) == true); |
| | 1 | 23 | | assert(insertHeap(&h, t2) == true); |
| | 1 | 24 | | assert(insertHeap(&h, t3) == true); |
| | 1 | 25 | | assert(getHeapSize(&h) == 3); |
| | | 26 | | |
| | | 27 | | Task out; |
| | | 28 | | // Should get t2 (priority 50) |
| | 1 | 29 | | assert(extractMax(&h, &out) == true); |
| | 1 | 30 | | assert(out.id == 2); |
| | | 31 | | |
| | | 32 | | // Should get t3 (priority 30) |
| | 1 | 33 | | assert(extractMax(&h, &out) == true); |
| | 1 | 34 | | assert(out.id == 3); |
| | | 35 | | |
| | | 36 | | // Should get t1 (priority 10) |
| | 1 | 37 | | assert(extractMax(&h, &out) == true); |
| | 1 | 38 | | assert(out.id == 1); |
| | | 39 | | |
| | | 40 | | // Empty extract |
| | 1 | 41 | | assert(extractMax(&h, &out) == false); |
| | 1 | 42 | | printf("[PASS] test_heap_insert_extract\n"); |
| | 1 | 43 | | } |
| | | 44 | | |
| | 1 | 45 | | void test_heap_priority_updates() { |
| | | 46 | | Heap h; |
| | 1 | 47 | | initHeap(&h); |
| | | 48 | | |
| | 1 | 49 | | Task t1 = {1, 10, 1000}; |
| | 1 | 50 | | Task t2 = {2, 20, 1001}; |
| | 1 | 51 | | Task t3 = {3, 30, 1002}; |
| | | 52 | | |
| | 1 | 53 | | insertHeap(&h, t1); |
| | 1 | 54 | | insertHeap(&h, t2); |
| | 1 | 55 | | insertHeap(&h, t3); |
| | | 56 | | |
| | | 57 | | // Root is t3 (30). Update t1 (10) -> 40. |
| | 1 | 58 | | assert(updatePriority(&h, 1, 40) == true); |
| | | 59 | | Task out; |
| | 1 | 60 | | extractMax(&h, &out); |
| | 1 | 61 | | assert(out.id == 1); // t1 moved to top |
| | | 62 | | |
| | | 63 | | // Now root is t3 (30). Update t3 (30) -> 5. |
| | 1 | 64 | | assert(updatePriority(&h, 3, 5) == true); |
| | 1 | 65 | | extractMax(&h, &out); |
| | 1 | 66 | | assert(out.id == 2); // t2 (20) moved to top |
| | | 67 | | |
| | | 68 | | // Update non-existent |
| | 1 | 69 | | assert(updatePriority(&h, 999, 100) == false); |
| | | 70 | | |
| | 1 | 71 | | printf("[PASS] test_heap_priority_updates\n"); |
| | 1 | 72 | | } |
| | | 73 | | |
| | 1 | 74 | | void test_heap_tie_breaker() { |
| | | 75 | | Heap h; |
| | 1 | 76 | | initHeap(&h); |
| | | 77 | | |
| | | 78 | | // Same priority, t1 is older (smaller timestamp) |
| | 1 | 79 | | Task t1 = {1, 50, 1000}; |
| | 1 | 80 | | Task t2 = {2, 50, 2000}; |
| | | 81 | | |
| | 1 | 82 | | insertHeap(&h, t2); |
| | 1 | 83 | | insertHeap(&h, t1); // Order shouldn't matter for insert |
| | | 84 | | |
| | | 85 | | Task out; |
| | 1 | 86 | | extractMax(&h, &out); |
| | 1 | 87 | | assert(out.id == 1); // Older wins tie-break (smaller timestamp) |
| | | 88 | | |
| | 1 | 89 | | extractMax(&h, &out); |
| | 1 | 90 | | assert(out.id == 2); |
| | | 91 | | |
| | 1 | 92 | | printf("[PASS] test_heap_tie_breaker\n"); |
| | 1 | 93 | | } |
| | | 94 | | |
| | 1 | 95 | | void test_heap_edge_cases() { |
| | | 96 | | Heap h; |
| | 1 | 97 | | initHeap(&h); |
| | | 98 | | |
| | | 99 | | // Fill heap |
| | 101 | 100 | | for (int i = 0; i < MAX_HEAP_SIZE; i++) { |
| | 100 | 101 | | Task t = {i, 10, 1000}; |
| | 100 | 102 | | assert(insertHeap(&h, t) == true); |
| | | 103 | | } |
| | | 104 | | |
| | | 105 | | // Try to overflow |
| | 1 | 106 | | Task over = {999, 99, 999}; |
| | 1 | 107 | | assert(insertHeap(&h, over) == false); |
| | | 108 | | |
| | 1 | 109 | | printf("[PASS] test_heap_edge_cases\n"); |
| | 1 | 110 | | } |
| | | 111 | | |
| | 1 | 112 | | int main() { |
| | 1 | 113 | | printf("=== Heap Logic Unit Tests ===\n"); |
| | 1 | 114 | | test_heap_init(); |
| | 1 | 115 | | test_heap_insert_extract(); |
| | 1 | 116 | | test_heap_priority_updates(); |
| | 1 | 117 | | test_heap_tie_breaker(); |
| | 1 | 118 | | test_heap_edge_cases(); |
| | 1 | 119 | | printf("\n✅ All Heap tests passed!\n"); |
| | 1 | 120 | | return 0; |
| | | 121 | | } |