Invercargill/src/tests/Integration/PriorityQueue.vala

using Invercargill;
using Invercargill.DataStructures;

void priority_queue_tests() {

    Test.add_func("/invercargill/priority_queue/basic_push_pop", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap (smaller values have higher priority)
        
        // Push items
        pq.push(5);
        pq.push(1);
        pq.push(3);
        pq.push(2);
        pq.push(4);
        
        // Pop in priority order (smallest first)
        assert_cmpint(1, CompareOperator.EQ, pq.pop());
        assert_cmpint(2, CompareOperator.EQ, pq.pop());
        assert_cmpint(3, CompareOperator.EQ, pq.pop());
        assert_cmpint(4, CompareOperator.EQ, pq.pop());
        assert_cmpint(5, CompareOperator.EQ, pq.pop());
    });

    Test.add_func("/invercargill/priority_queue/max_heap", () => {
        var pq = new PriorityQueue<int>((a, b) => b - a); // Max-heap (larger values have higher priority)
        
        // Push items
        pq.push(5);
        pq.push(1);
        pq.push(3);
        pq.push(2);
        pq.push(4);
        
        // Pop in priority order (largest first)
        assert_cmpint(5, CompareOperator.EQ, pq.pop());
        assert_cmpint(4, CompareOperator.EQ, pq.pop());
        assert_cmpint(3, CompareOperator.EQ, pq.pop());
        assert_cmpint(2, CompareOperator.EQ, pq.pop());
        assert_cmpint(1, CompareOperator.EQ, pq.pop());
    });

    Test.add_func("/invercargill/priority_queue/peek functionality", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap
        
        pq.push(5);
        pq.push(1);
        pq.push(3);
        
        // Peek should return highest priority item without removing
        var top = pq.peek();
        assert_cmpint(1, CompareOperator.EQ, top);
        
        // Pop should still return 1
        var popped = pq.pop();
        assert_cmpint(1, CompareOperator.EQ, popped);
        
        // Peek now should return 3 (next highest priority)
        var new_top = pq.peek();
        assert_cmpint(3, CompareOperator.EQ, new_top);
    });

    Test.add_func("/invercargill/priority_queue/empty_priority_queue_behavior", () => {
        // Test peek on empty priority queue
        var pq1 = new PriorityQueue<string>((a, b) => a.collate(b));
        try {
            pq1.peek();
            assert_not_reached();
        }
        catch (SequenceError e) {
            assert_cmpstr("No elements in priority queue", CompareOperator.EQ, e.message);
        }
        
        // Test pop on empty priority queue - need to unblock first
        var pq2 = new PriorityQueue<string>((a, b) => a.collate(b));
        pq2.unblock();
        try {
            pq2.pop();
            assert_not_reached();
        }
        catch (SequenceError e) {
            assert_cmpstr("No elements in unblocked priority queue to pop", CompareOperator.EQ, e.message);
        }
    });

    Test.add_func("/invercargill/priority_queue/push_all", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap
        var items = new Series<int>();
        items.add(5);
        items.add(1);
        items.add(3);
        
        // Push all items
        pq.push_all(items);
        
        // Should pop in priority order
        assert_cmpint(1, CompareOperator.EQ, pq.pop());
        assert_cmpint(3, CompareOperator.EQ, pq.pop());
        assert_cmpint(5, CompareOperator.EQ, pq.pop());
    });

    Test.add_func("/invercargill/priority_queue/enumerable_behavior", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap
        
        pq.push(5);
        pq.push(1);
        pq.push(3);
        pq.unblock();
        
        // Iteration should return items in priority order
        var tracker = pq.get_tracker();
        var items = new int[3];
        var index = 0;
        
        while (tracker.has_next()) {
            items[index++] = tracker.get_next();
        }
        
        assert_cmpint(1, CompareOperator.EQ, items[0]);
        assert_cmpint(3, CompareOperator.EQ, items[1]);
        assert_cmpint(5, CompareOperator.EQ, items[2]);
    });

    Test.add_func("/invercargill/priority_queue/blocking_behavior", () => {
        var pq = new PriorityQueue<string>((a, b) => a.collate(b));
        bool thread_started = false;
        bool thread_finished = false;
        
        // Start a thread that will wait for an item
        Thread<void*> thread = new Thread<void*>("test-thread", () => {
            thread_started = true;
            var item = pq.pop();
            assert_cmpstr("test_item", CompareOperator.EQ, item);
            thread_finished = true;
            return null;
        });
        
        // Wait for thread to start and block
        while (!thread_started) {
            Thread.usleep(1000); // 1ms
        }
        // Give additional time for thread to block on pop()
        Thread.usleep(50000); // 50ms
        
        // Push an item to unblock the thread
        pq.push("test_item");
        
        // Wait for thread to finish
        thread.join();
        assert_true(thread_finished);
    });

    Test.add_func("/invercargill/priority_queue/unblock_behavior", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b);
        bool thread_started = false;
        bool exception_thrown = false;
        
        // Start a thread that will wait for an item
        Thread<void*> thread = new Thread<void*>("test-thread", () => {
            thread_started = true;
            try {
                var item = pq.pop(); // This should throw after unblock
                assert_not_reached();
            }
            catch (SequenceError e) {
                assert_cmpstr("No elements in unblocked priority queue to pop", CompareOperator.EQ, e.message);
                exception_thrown = true;
            }
            return null;
        });
        
        // Wait for thread to start and block
        while (!thread_started) {
            Thread.usleep(1000); // 1ms
        }
        // Give additional time for thread to block on pop()
        Thread.usleep(50000); // 50ms
        
        // Unblock the priority queue
        pq.unblock();
        
        // Wait for thread to finish
        thread.join();
        assert_true(exception_thrown);
    });

    Test.add_func("/invercargill/priority_queue/try_peek_and_try_pop", () => {
        var pq = new PriorityQueue<string>((a, b) => a.collate(b));
        
        // Try operations on empty priority queue
        string item;
        assert_false(pq.try_peek(out item));
        assert_null(item);
        
        string popped;
        pq.unblock();
        assert_false(pq.try_pop(out popped));
        assert_null(popped);
        
        // Add an item
        pq.push("test");
        
        // Try operations should now succeed
        assert_true(pq.try_peek(out item));
        assert_cmpstr("test", CompareOperator.EQ, item);
        
        assert_true(pq.try_pop(out popped));
        assert_cmpstr("test", CompareOperator.EQ, popped);
        
        // Should be empty again
        assert_false(pq.try_pop(out popped));
        assert_null(popped);
    });

    Test.add_func("/invercargill/priority_queue/duplicate_values", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap
        
        // Push items with duplicates
        pq.push(3);
        pq.push(1);
        pq.push(3);
        pq.push(2);
        pq.push(1);
        
        // Pop in priority order
        assert_cmpint(1, CompareOperator.EQ, pq.pop());
        assert_cmpint(1, CompareOperator.EQ, pq.pop());
        assert_cmpint(2, CompareOperator.EQ, pq.pop());
        assert_cmpint(3, CompareOperator.EQ, pq.pop());
        assert_cmpint(3, CompareOperator.EQ, pq.pop());
    });

    Test.add_func("/invercargill/priority_queue/peek_count", () => {
        var pq = new PriorityQueue<int>((a, b) => a - b); // Min-heap
        
        // Initially empty
        assert_cmpuint(0, CompareOperator.EQ, pq.peek_count());
        
        // Add items
        pq.push(3);
        assert_cmpuint(1, CompareOperator.EQ, pq.peek_count());
        
        pq.push(1);
        assert_cmpuint(2, CompareOperator.EQ, pq.peek_count());
        
        pq.push(2);
        assert_cmpuint(3, CompareOperator.EQ, pq.peek_count());
        
        // Remove items
        pq.pop();
        assert_cmpuint(2, CompareOperator.EQ, pq.peek_count());
        
        pq.pop();
        assert_cmpuint(1, CompareOperator.EQ, pq.peek_count());
        
        pq.pop();
        assert_cmpuint(0, CompareOperator.EQ, pq.peek_count());
    });

    Test.add_func("/invercargill/priority_queue/string_priority", () => {
        var pq = new PriorityQueue<string>((a, b) => a.collate(b)); // Alphabetical order
        
        // Push items
        pq.push("zebra");
        pq.push("apple");
        pq.push("banana");
        pq.push("cherry");
        
        // Pop in alphabetical order
        assert_cmpstr("apple", CompareOperator.EQ, pq.pop());
        assert_cmpstr("banana", CompareOperator.EQ, pq.pop());
        assert_cmpstr("cherry", CompareOperator.EQ, pq.pop());
        assert_cmpstr("zebra", CompareOperator.EQ, pq.pop());
    });

}