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