Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/utils/tests/test_mapped_queue.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 from networkx.utils.mapped_queue import MappedQueue | |
2 | |
3 | |
4 class TestMappedQueue: | |
5 def setup(self): | |
6 pass | |
7 | |
8 def _check_map(self, q): | |
9 d = {elt: pos for pos, elt in enumerate(q.h)} | |
10 assert d == q.d | |
11 | |
12 def _make_mapped_queue(self, h): | |
13 q = MappedQueue() | |
14 q.h = h | |
15 q.d = {elt: pos for pos, elt in enumerate(h)} | |
16 return q | |
17 | |
18 def test_heapify(self): | |
19 h = [5, 4, 3, 2, 1, 0] | |
20 q = self._make_mapped_queue(h) | |
21 q._heapify() | |
22 self._check_map(q) | |
23 | |
24 def test_init(self): | |
25 h = [5, 4, 3, 2, 1, 0] | |
26 q = MappedQueue(h) | |
27 self._check_map(q) | |
28 | |
29 def test_len(self): | |
30 h = [5, 4, 3, 2, 1, 0] | |
31 q = MappedQueue(h) | |
32 self._check_map(q) | |
33 assert len(q) == 6 | |
34 | |
35 def test_siftup_leaf(self): | |
36 h = [2] | |
37 h_sifted = [2] | |
38 q = self._make_mapped_queue(h) | |
39 q._siftup(0) | |
40 assert q.h == h_sifted | |
41 self._check_map(q) | |
42 | |
43 def test_siftup_one_child(self): | |
44 h = [2, 0] | |
45 h_sifted = [0, 2] | |
46 q = self._make_mapped_queue(h) | |
47 q._siftup(0) | |
48 assert q.h == h_sifted | |
49 self._check_map(q) | |
50 | |
51 def test_siftup_left_child(self): | |
52 h = [2, 0, 1] | |
53 h_sifted = [0, 2, 1] | |
54 q = self._make_mapped_queue(h) | |
55 q._siftup(0) | |
56 assert q.h == h_sifted | |
57 self._check_map(q) | |
58 | |
59 def test_siftup_right_child(self): | |
60 h = [2, 1, 0] | |
61 h_sifted = [0, 1, 2] | |
62 q = self._make_mapped_queue(h) | |
63 q._siftup(0) | |
64 assert q.h == h_sifted | |
65 self._check_map(q) | |
66 | |
67 def test_siftup_multiple(self): | |
68 h = [0, 1, 2, 4, 3, 5, 6] | |
69 h_sifted = [1, 3, 2, 4, 0, 5, 6] | |
70 q = self._make_mapped_queue(h) | |
71 q._siftup(0) | |
72 assert q.h == h_sifted | |
73 self._check_map(q) | |
74 | |
75 def test_siftdown_leaf(self): | |
76 h = [2] | |
77 h_sifted = [2] | |
78 q = self._make_mapped_queue(h) | |
79 q._siftdown(0) | |
80 assert q.h == h_sifted | |
81 self._check_map(q) | |
82 | |
83 def test_siftdown_single(self): | |
84 h = [1, 0] | |
85 h_sifted = [0, 1] | |
86 q = self._make_mapped_queue(h) | |
87 q._siftdown(len(h) - 1) | |
88 assert q.h == h_sifted | |
89 self._check_map(q) | |
90 | |
91 def test_siftdown_multiple(self): | |
92 h = [1, 2, 3, 4, 5, 6, 7, 0] | |
93 h_sifted = [0, 1, 3, 2, 5, 6, 7, 4] | |
94 q = self._make_mapped_queue(h) | |
95 q._siftdown(len(h) - 1) | |
96 assert q.h == h_sifted | |
97 self._check_map(q) | |
98 | |
99 def test_push(self): | |
100 to_push = [6, 1, 4, 3, 2, 5, 0] | |
101 h_sifted = [0, 2, 1, 6, 3, 5, 4] | |
102 q = MappedQueue() | |
103 for elt in to_push: | |
104 q.push(elt) | |
105 assert q.h == h_sifted | |
106 self._check_map(q) | |
107 | |
108 def test_push_duplicate(self): | |
109 to_push = [2, 1, 0] | |
110 h_sifted = [0, 2, 1] | |
111 q = MappedQueue() | |
112 for elt in to_push: | |
113 inserted = q.push(elt) | |
114 assert inserted | |
115 assert q.h == h_sifted | |
116 self._check_map(q) | |
117 inserted = q.push(1) | |
118 assert not inserted | |
119 | |
120 def test_pop(self): | |
121 h = [3, 4, 6, 0, 1, 2, 5] | |
122 h_sorted = sorted(h) | |
123 q = self._make_mapped_queue(h) | |
124 q._heapify() | |
125 popped = [] | |
126 for elt in sorted(h): | |
127 popped.append(q.pop()) | |
128 assert popped == h_sorted | |
129 self._check_map(q) | |
130 | |
131 def test_remove_leaf(self): | |
132 h = [0, 2, 1, 6, 3, 5, 4] | |
133 h_removed = [0, 2, 1, 6, 4, 5] | |
134 q = self._make_mapped_queue(h) | |
135 removed = q.remove(3) | |
136 assert q.h == h_removed | |
137 | |
138 def test_remove_root(self): | |
139 h = [0, 2, 1, 6, 3, 5, 4] | |
140 h_removed = [1, 2, 4, 6, 3, 5] | |
141 q = self._make_mapped_queue(h) | |
142 removed = q.remove(0) | |
143 assert q.h == h_removed | |
144 | |
145 def test_update_leaf(self): | |
146 h = [0, 20, 10, 60, 30, 50, 40] | |
147 h_updated = [0, 15, 10, 60, 20, 50, 40] | |
148 q = self._make_mapped_queue(h) | |
149 removed = q.update(30, 15) | |
150 assert q.h == h_updated | |
151 | |
152 def test_update_root(self): | |
153 h = [0, 20, 10, 60, 30, 50, 40] | |
154 h_updated = [10, 20, 35, 60, 30, 50, 40] | |
155 q = self._make_mapped_queue(h) | |
156 removed = q.update(0, 35) | |
157 assert q.h == h_updated |