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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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