Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/boltons/queueutils.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
1 # -*- coding: utf-8 -*-
2 """Python comes with a many great data structures, from :class:`dict`
3 to :class:`collections.deque`, and no shortage of serviceable
4 algorithm implementations, from :func:`sorted` to :mod:`bisect`. But
5 priority queues are curiously relegated to an example documented in
6 :mod:`heapq`. Even there, the approach presented is not full-featured
7 and object-oriented. There is a built-in priority queue,
8 :class:`Queue.PriorityQueue`, but in addition to its austere API, it
9 carries the double-edged sword of threadsafety, making it fine for
10 multi-threaded, multi-consumer applications, but high-overhead for
11 cooperative/single-threaded use cases.
12
13 The ``queueutils`` module currently provides two Queue
14 implementations: :class:`HeapPriorityQueue`, based on a heap, and
15 :class:`SortedPriorityQueue`, based on a sorted list. Both use a
16 unified API based on :class:`BasePriorityQueue` to facilitate testing
17 the slightly different performance characteristics on various
18 application use cases.
19
20 >>> pq = PriorityQueue()
21 >>> pq.add('low priority task', 0)
22 >>> pq.add('high priority task', 2)
23 >>> pq.add('medium priority task 1', 1)
24 >>> pq.add('medium priority task 2', 1)
25 >>> len(pq)
26 4
27 >>> pq.pop()
28 'high priority task'
29 >>> pq.peek()
30 'medium priority task 1'
31 >>> len(pq)
32 3
33
34 """
35
36
37 from heapq import heappush, heappop
38 from bisect import insort
39 import itertools
40
41 try:
42 from typeutils import make_sentinel
43 _REMOVED = make_sentinel(var_name='_REMOVED')
44 except ImportError:
45 _REMOVED = object()
46
47 try:
48 from listutils import BList
49 # see BarrelList docstring for notes
50 except ImportError:
51 BList = list
52
53
54 __all__ = ['PriorityQueue', 'BasePriorityQueue',
55 'HeapPriorityQueue', 'SortedPriorityQueue']
56
57
58 # TODO: make Base a real abstract class
59 # TODO: add uniqueification
60
61
62 class BasePriorityQueue(object):
63 """The abstract base class for the other PriorityQueues in this
64 module. Override the ``_backend_type`` class attribute, as well as
65 the :meth:`_push_entry` and :meth:`_pop_entry` staticmethods for
66 custom subclass behavior. (Don't forget to use
67 :func:`staticmethod`).
68
69 Args:
70 priority_key (callable): A function that takes *priority* as
71 passed in by :meth:`add` and returns a real number
72 representing the effective priority.
73
74 """
75 # negating priority means larger numbers = higher priority
76 _default_priority_key = staticmethod(lambda p: -float(p or 0))
77 _backend_type = list
78
79 def __init__(self, **kw):
80 self._pq = self._backend_type()
81 self._entry_map = {}
82 self._counter = itertools.count()
83 self._get_priority = kw.pop('priority_key', self._default_priority_key)
84 if kw:
85 raise TypeError('unexpected keyword arguments: %r' % kw.keys())
86
87 @staticmethod
88 def _push_entry(backend, entry):
89 pass # abstract
90
91 @staticmethod
92 def _pop_entry(backend):
93 pass # abstract
94
95 def add(self, task, priority=None):
96 """
97 Add a task to the queue, or change the *task*'s priority if *task*
98 is already in the queue. *task* can be any hashable object,
99 and *priority* defaults to ``0``. Higher values representing
100 higher priority, but this behavior can be controlled by
101 setting *priority_key* in the constructor.
102 """
103 priority = self._get_priority(priority)
104 if task in self._entry_map:
105 self.remove(task)
106 count = next(self._counter)
107 entry = [priority, count, task]
108 self._entry_map[task] = entry
109 self._push_entry(self._pq, entry)
110
111 def remove(self, task):
112 """Remove a task from the priority queue. Raises :exc:`KeyError` if
113 the *task* is absent.
114 """
115 entry = self._entry_map.pop(task)
116 entry[-1] = _REMOVED
117
118 def _cull(self, raise_exc=True):
119 "Remove entries marked as removed by previous :meth:`remove` calls."
120 while self._pq:
121 priority, count, task = self._pq[0]
122 if task is _REMOVED:
123 self._pop_entry(self._pq)
124 continue
125 return
126 if raise_exc:
127 raise IndexError('empty priority queue')
128
129 def peek(self, default=_REMOVED):
130 """Read the next value in the queue without removing it. Returns
131 *default* on an empty queue, or raises :exc:`KeyError` if
132 *default* is not set.
133 """
134 try:
135 self._cull()
136 _, _, task = self._pq[0]
137 except IndexError:
138 if default is not _REMOVED:
139 return default
140 raise IndexError('peek on empty queue')
141 return task
142
143 def pop(self, default=_REMOVED):
144 """Remove and return the next value in the queue. Returns *default* on
145 an empty queue, or raises :exc:`KeyError` if *default* is not
146 set.
147 """
148 try:
149 self._cull()
150 _, _, task = self._pop_entry(self._pq)
151 del self._entry_map[task]
152 except IndexError:
153 if default is not _REMOVED:
154 return default
155 raise IndexError('pop on empty queue')
156 return task
157
158 def __len__(self):
159 "Return the number of tasks in the queue."
160 return len(self._entry_map)
161
162
163 class HeapPriorityQueue(BasePriorityQueue):
164 """A priority queue inherited from :class:`BasePriorityQueue`,
165 backed by a list and based on the :func:`heapq.heappop` and
166 :func:`heapq.heappush` functions in the built-in :mod:`heapq`
167 module.
168 """
169 @staticmethod
170 def _pop_entry(backend):
171 return heappop(backend)
172
173 @staticmethod
174 def _push_entry(backend, entry):
175 heappush(backend, entry)
176
177
178 class SortedPriorityQueue(BasePriorityQueue):
179 """A priority queue inherited from :class:`BasePriorityQueue`, based
180 on the :func:`bisect.insort` approach for in-order insertion into
181 a sorted list.
182 """
183 _backend_type = BList
184
185 @staticmethod
186 def _pop_entry(backend):
187 return backend.pop(0)
188
189 @staticmethod
190 def _push_entry(backend, entry):
191 insort(backend, entry)
192
193
194 PriorityQueue = SortedPriorityQueue