Vehicle-cpp/hkpc/software/networkx/utils/tests/test_mapped_queue.py

import pytest

from networkx.utils.mapped_queue import MappedQueue, _HeapElement


def test_HeapElement_gtlt():
    bar = _HeapElement(1.1, "a")
    foo = _HeapElement(1, "b")
    assert foo < bar
    assert bar > foo
    assert foo < 1.1
    assert 1 < bar


def test_HeapElement_gtlt_tied_priority():
    bar = _HeapElement(1, "a")
    foo = _HeapElement(1, "b")
    assert foo > bar
    assert bar < foo


def test_HeapElement_eq():
    bar = _HeapElement(1.1, "a")
    foo = _HeapElement(1, "a")
    assert foo == bar
    assert bar == foo
    assert foo == "a"


def test_HeapElement_iter():
    foo = _HeapElement(1, "a")
    bar = _HeapElement(1.1, (3, 2, 1))
    assert list(foo) == [1, "a"]
    assert list(bar) == [1.1, 3, 2, 1]


def test_HeapElement_getitem():
    foo = _HeapElement(1, "a")
    bar = _HeapElement(1.1, (3, 2, 1))
    assert foo[1] == "a"
    assert foo[0] == 1
    assert bar[0] == 1.1
    assert bar[2] == 2
    assert bar[3] == 1
    pytest.raises(IndexError, bar.__getitem__, 4)
    pytest.raises(IndexError, foo.__getitem__, 2)


class TestMappedQueue:
    def setup_method(self):
        pass

    def _check_map(self, q):
        assert q.position == {elt: pos for pos, elt in enumerate(q.heap)}

    def _make_mapped_queue(self, h):
        q = MappedQueue()
        q.heap = h
        q.position = {elt: pos for pos, elt in enumerate(h)}
        return q

    def test_heapify(self):
        h = [5, 4, 3, 2, 1, 0]
        q = self._make_mapped_queue(h)
        q._heapify()
        self._check_map(q)

    def test_init(self):
        h = [5, 4, 3, 2, 1, 0]
        q = MappedQueue(h)
        self._check_map(q)

    def test_incomparable(self):
        h = [5, 4, "a", 2, 1, 0]
        pytest.raises(TypeError, MappedQueue, h)

    def test_len(self):
        h = [5, 4, 3, 2, 1, 0]
        q = MappedQueue(h)
        self._check_map(q)
        assert len(q) == 6

    def test_siftup_leaf(self):
        h = [2]
        h_sifted = [2]
        q = self._make_mapped_queue(h)
        q._siftup(0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftup_one_child(self):
        h = [2, 0]
        h_sifted = [0, 2]
        q = self._make_mapped_queue(h)
        q._siftup(0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftup_left_child(self):
        h = [2, 0, 1]
        h_sifted = [0, 2, 1]
        q = self._make_mapped_queue(h)
        q._siftup(0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftup_right_child(self):
        h = [2, 1, 0]
        h_sifted = [0, 1, 2]
        q = self._make_mapped_queue(h)
        q._siftup(0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftup_multiple(self):
        h = [0, 1, 2, 4, 3, 5, 6]
        h_sifted = [0, 1, 2, 4, 3, 5, 6]
        q = self._make_mapped_queue(h)
        q._siftup(0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftdown_leaf(self):
        h = [2]
        h_sifted = [2]
        q = self._make_mapped_queue(h)
        q._siftdown(0, 0)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftdown_single(self):
        h = [1, 0]
        h_sifted = [0, 1]
        q = self._make_mapped_queue(h)
        q._siftdown(0, len(h) - 1)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_siftdown_multiple(self):
        h = [1, 2, 3, 4, 5, 6, 7, 0]
        h_sifted = [0, 1, 3, 2, 5, 6, 7, 4]
        q = self._make_mapped_queue(h)
        q._siftdown(0, len(h) - 1)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_push(self):
        to_push = [6, 1, 4, 3, 2, 5, 0]
        h_sifted = [0, 2, 1, 6, 3, 5, 4]
        q = MappedQueue()
        for elt in to_push:
            q.push(elt)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_push_duplicate(self):
        to_push = [2, 1, 0]
        h_sifted = [0, 2, 1]
        q = MappedQueue()
        for elt in to_push:
            inserted = q.push(elt)
            assert inserted
        assert q.heap == h_sifted
        self._check_map(q)
        inserted = q.push(1)
        assert not inserted

    def test_pop(self):
        h = [3, 4, 6, 0, 1, 2, 5]
        h_sorted = sorted(h)
        q = self._make_mapped_queue(h)
        q._heapify()
        popped = [q.pop() for _ in range(len(h))]
        assert popped == h_sorted
        self._check_map(q)

    def test_remove_leaf(self):
        h = [0, 2, 1, 6, 3, 5, 4]
        h_removed = [0, 2, 1, 6, 4, 5]
        q = self._make_mapped_queue(h)
        removed = q.remove(3)
        assert q.heap == h_removed

    def test_remove_root(self):
        h = [0, 2, 1, 6, 3, 5, 4]
        h_removed = [1, 2, 4, 6, 3, 5]
        q = self._make_mapped_queue(h)
        removed = q.remove(0)
        assert q.heap == h_removed

    def test_update_leaf(self):
        h = [0, 20, 10, 60, 30, 50, 40]
        h_updated = [0, 15, 10, 60, 20, 50, 40]
        q = self._make_mapped_queue(h)
        removed = q.update(30, 15)
        assert q.heap == h_updated

    def test_update_root(self):
        h = [0, 20, 10, 60, 30, 50, 40]
        h_updated = [10, 20, 35, 60, 30, 50, 40]
        q = self._make_mapped_queue(h)
        removed = q.update(0, 35)
        assert q.heap == h_updated


class TestMappedDict(TestMappedQueue):
    def _make_mapped_queue(self, h):
        priority_dict = {elt: elt for elt in h}
        return MappedQueue(priority_dict)

    def test_init(self):
        d = {5: 0, 4: 1, "a": 2, 2: 3, 1: 4}
        q = MappedQueue(d)
        assert q.position == d

    def test_ties(self):
        d = {5: 0, 4: 1, 3: 2, 2: 3, 1: 4}
        q = MappedQueue(d)
        assert q.position == {elt: pos for pos, elt in enumerate(q.heap)}

    def test_pop(self):
        d = {5: 0, 4: 1, 3: 2, 2: 3, 1: 4}
        q = MappedQueue(d)
        assert q.pop() == _HeapElement(0, 5)
        assert q.position == {elt: pos for pos, elt in enumerate(q.heap)}

    def test_empty_pop(self):
        q = MappedQueue()
        pytest.raises(IndexError, q.pop)

    def test_incomparable_ties(self):
        d = {5: 0, 4: 0, "a": 0, 2: 0, 1: 0}
        pytest.raises(TypeError, MappedQueue, d)

    def test_push(self):
        to_push = [6, 1, 4, 3, 2, 5, 0]
        h_sifted = [0, 2, 1, 6, 3, 5, 4]
        q = MappedQueue()
        for elt in to_push:
            q.push(elt, priority=elt)
        assert q.heap == h_sifted
        self._check_map(q)

    def test_push_duplicate(self):
        to_push = [2, 1, 0]
        h_sifted = [0, 2, 1]
        q = MappedQueue()
        for elt in to_push:
            inserted = q.push(elt, priority=elt)
            assert inserted
        assert q.heap == h_sifted
        self._check_map(q)
        inserted = q.push(1, priority=1)
        assert not inserted

    def test_update_leaf(self):
        h = [0, 20, 10, 60, 30, 50, 40]
        h_updated = [0, 15, 10, 60, 20, 50, 40]
        q = self._make_mapped_queue(h)
        removed = q.update(30, 15, priority=15)
        assert q.heap == h_updated

    def test_update_root(self):
        h = [0, 20, 10, 60, 30, 50, 40]
        h_updated = [10, 20, 35, 60, 30, 50, 40]
        q = self._make_mapped_queue(h)
        removed = q.update(0, 35, priority=35)
        assert q.heap == h_updated