Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / utils / tests / test_mapped_queue.py @ 5cef0f13

History | View | Annotate | Download (4.58 KB)

1
# -*- coding: utf-8 -*-
2
#
3
# priorityq: An object-oriented priority queue with updatable priorities.
4
#
5
# Copyright 2018 Edward L. Platt
6
#
7
# This file is part of NetworkX
8
#
9
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
10
# information.
11
#
12
# Authors:
13
#   Edward L. Platt <ed@elplatt.com>
14

    
15
from nose.tools import assert_equal
16
from nose.tools import raises
17

    
18
from networkx.utils.mapped_queue import MappedQueue
19

    
20

    
21
class TestMappedQueue(object):
22

    
23
    def setup(self):
24
        pass
25

    
26
    def _check_map(self, q):
27
        d = dict((elt, pos) for pos, elt in enumerate(q.h))
28
        assert_equal(d, q.d)
29

    
30
    def _make_mapped_queue(self, h):
31
        q = MappedQueue()
32
        q.h = h
33
        q.d = dict((elt, pos) for pos, elt in enumerate(h))
34
        return q
35

    
36
    def test_heapify(self):
37
        h = [5, 4, 3, 2, 1, 0]
38
        q = self._make_mapped_queue(h)
39
        q._heapify()
40
        self._check_map(q)
41

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

    
47
    def test_len(self):
48
        h = [5, 4, 3, 2, 1, 0]
49
        q = MappedQueue(h)
50
        self._check_map(q)
51
        assert_equal(len(q), 6)
52

    
53
    def test_siftup_leaf(self):
54
        h = [2]
55
        h_sifted = [2]
56
        q = self._make_mapped_queue(h)
57
        q._siftup(0)
58
        assert_equal(q.h, h_sifted)
59
        self._check_map(q)
60

    
61
    def test_siftup_one_child(self):
62
        h = [2, 0]
63
        h_sifted = [0, 2]
64
        q = self._make_mapped_queue(h)
65
        q._siftup(0)
66
        assert_equal(q.h, h_sifted)
67
        self._check_map(q)
68

    
69
    def test_siftup_left_child(self):
70
        h = [2, 0, 1]
71
        h_sifted = [0, 2, 1]
72
        q = self._make_mapped_queue(h)
73
        q._siftup(0)
74
        assert_equal(q.h, h_sifted)
75
        self._check_map(q)
76

    
77
    def test_siftup_right_child(self):
78
        h = [2, 1, 0]
79
        h_sifted = [0, 1, 2]
80
        q = self._make_mapped_queue(h)
81
        q._siftup(0)
82
        assert_equal(q.h, h_sifted)
83
        self._check_map(q)
84

    
85
    def test_siftup_multiple(self):
86
        h = [0, 1, 2, 4, 3, 5, 6]
87
        h_sifted = [1, 3, 2, 4, 0, 5, 6]
88
        q = self._make_mapped_queue(h)
89
        q._siftup(0)
90
        assert_equal(q.h, h_sifted)
91
        self._check_map(q)
92

    
93
    def test_siftdown_leaf(self):
94
        h = [2]
95
        h_sifted = [2]
96
        q = self._make_mapped_queue(h)
97
        q._siftdown(0)
98
        assert_equal(q.h, h_sifted)
99
        self._check_map(q)
100

    
101
    def test_siftdown_single(self):
102
        h = [1, 0]
103
        h_sifted = [0, 1]
104
        q = self._make_mapped_queue(h)
105
        q._siftdown(len(h) - 1)
106
        assert_equal(q.h, h_sifted)
107
        self._check_map(q)
108

    
109
    def test_siftdown_multiple(self):
110
        h = [1, 2, 3, 4, 5, 6, 7, 0]
111
        h_sifted = [0, 1, 3, 2, 5, 6, 7, 4]
112
        q = self._make_mapped_queue(h)
113
        q._siftdown(len(h) - 1)
114
        assert_equal(q.h, h_sifted)
115
        self._check_map(q)
116

    
117
    def test_push(self):
118
        to_push = [6, 1, 4, 3, 2, 5, 0]
119
        h_sifted = [0, 2, 1, 6, 3, 5, 4]
120
        q = MappedQueue()
121
        for elt in to_push:
122
            q.push(elt)
123
        assert_equal(q.h, h_sifted)
124
        self._check_map(q)
125

    
126
    def test_push_duplicate(self):
127
        to_push = [2, 1, 0]
128
        h_sifted = [0, 2, 1]
129
        q = MappedQueue()
130
        for elt in to_push:
131
            inserted = q.push(elt)
132
            assert_equal(inserted, True)
133
        assert_equal(q.h, h_sifted)
134
        self._check_map(q)
135
        inserted = q.push(1)
136
        assert_equal(inserted, False)
137

    
138
    def test_pop(self):
139
        h = [3, 4, 6, 0, 1, 2, 5]
140
        h_sorted = sorted(h)
141
        q = self._make_mapped_queue(h)
142
        q._heapify()
143
        popped = []
144
        for elt in sorted(h):
145
            popped.append(q.pop())
146
        assert_equal(popped, h_sorted)
147
        self._check_map(q)
148

    
149
    def test_remove_leaf(self):
150
        h = [0, 2, 1, 6, 3, 5, 4]
151
        h_removed = [0, 2, 1, 6, 4, 5]
152
        q = self._make_mapped_queue(h)
153
        removed = q.remove(3)
154
        assert_equal(q.h, h_removed)
155

    
156
    def test_remove_root(self):
157
        h = [0, 2, 1, 6, 3, 5, 4]
158
        h_removed = [1, 2, 4, 6, 3, 5]
159
        q = self._make_mapped_queue(h)
160
        removed = q.remove(0)
161
        assert_equal(q.h, h_removed)
162

    
163
    def test_update_leaf(self):
164
        h = [0, 20, 10, 60, 30, 50, 40]
165
        h_updated = [0, 15, 10, 60, 20, 50, 40]
166
        q = self._make_mapped_queue(h)
167
        removed = q.update(30, 15)
168
        assert_equal(q.h, h_updated)
169

    
170
    def test_update_root(self):
171
        h = [0, 20, 10, 60, 30, 50, 40]
172
        h_updated = [10, 20, 35, 60, 30, 50, 40]
173
        q = self._make_mapped_queue(h)
174
        removed = q.update(0, 35)
175
        assert_equal(q.h, h_updated)