This is a pre-production deployment of Warehouse, however changes made here WILL affect the production instance of PyPI.
Latest Version Dependencies status unknown Test status unknown Test coverage unknown
Project Description

depq - Double-ended priority queue

  • Python implementation of a thread-safe and efficient double-ended priority queue (DEPQ) in which items and their priority values are stored in a deque object as tuples.
  • This of course can also be used as a regular priority queue, or simply a FIFO/LIFO queue.
  • Priority queues have many uses such as scheduling, event driven simulation, heuristic analysis, spam filtering, graph searching, etc.

Features & advantages of this implementation:

  • Completely thread-safe
  • Serializable via pickling or JSON
  • Priority values can be ints/floats, numpy types, strings, or any other comparable type you choose!
  • popfirst() and poplast() have O(1) performance instead of running in logarithmic time like in a standard DEPQ or other heap-derived structure
  • Naturally fast also because deque object is implemented in C
  • Items with equal priorities are sorted in the order they were originally added
  • Specific items can be deleted or their priorities changed
  • Membership testing with ‘in’ operator occurs in O(1) as does getting an item’s frequency in DEPQ via count(item)

Implementation:

  • Priorities are always in proper order, thus, a binary search is performed to find the right index with which to insert new items when specifying priority. Normally, this would result in O(n log n) performance when adding items via insert(item, priority) where self.high() > priority > self.low() because deque (as a doubly linked list) random access is O(n).

    Though, ACTUALLY that is not the case here as I’ve been able to reduce that to O(n) by modifying the binary search to operate while the internal deque is concurrently rotating.

Examples:

>>> from textwrap import fill  # For nice wrapped printing
>>> from depq import DEPQ
>>>
>>> # Defaults. If iterable is not None, extend(iterable) will be
>>> # called (example below). If maxlen is not None, abs(int(maxlen))
>>> # will become the length limit. If a maxlen is set and an item
>>> # is added with a priority > lowest prioritized item, it will be
>>> # added and the last item will be popped. After instantiation, the
>>> # maxlen can be retrieved with maxlen() and set with set_maxlen(length).
>>> depq = DEPQ(iterable=None, maxlen=None)
>>>
>>> # Add some characters with their ordinal
>>> # values as priority and keep count
>>> for c in 'AN_ERRONEOUS_STRING':
...     count = list(  # This is hacky and not important, skip next 4 lines :)
...         x + 1 if '{} #{}'.format(c, x + 1) in depq
...         else next(iter(())) if x != 0 else 0
...         for x in range(len(depq) + 1)
...     )[-1]
...
...     depq.insert('{} #{}'.format(c, count + 1), ord(c))  # item, priority
...
>>> print(fill(str(depq), 77))
DEPQ([('_ #1', 95), ('_ #2', 95), ('U #1', 85), ('T #1', 84), ('S #1', 83),
('S #2', 83), ('R #1', 82), ('R #2', 82), ('R #3', 82), ('O #1', 79), ('O
#2', 79), ('N #1', 78), ('N #2', 78), ('N #3', 78), ('I #1', 73), ('G #1',
71), ('E #1', 69), ('E #2', 69), ('A #1', 65)])
>>>
>>> # As you can see items with equal priorities are sorted in the order
>>> # they were originally added. Also note DEPQ root (depq[0]) is highest
>>> # priority like a max heap.
>>>
>>> depq.first()
'_ #1'
>>> depq.last()
'A #1'
>>> depq.high()
95
>>> depq.low()
65
>>> depq[7]  # Returns tuple(item, priority)
('R #2', 82)
>>>
>>> depq.poplast()
('A #1', 65)
>>> depq.last()
'E #2'
>>>
>>> depq.size()  # Alias for len(DEPQ)
18
>>> depq.is_empty()
False
>>> depq.clear()
>>> depq.is_empty()
True
>>>
>>> # Extend any length iterable of iterables of length >= 2
>>> depq.extend([('bar', 1, 'arbitrary'), (None, 5), ('foo', 2, 'blah')])
>>> depq
DEPQ([(None, 5), ('foo', 2), ('bar', 1)])
>>>
>>> depq.clear()
>>>
>>> depq.addfirst('starter')  # For an empty DEPQ, addfirst & addlast are
>>>                           # functionally identical; they add item to DEPQ
>>> depq                      # with given priority, or default 0
DEPQ([('starter', 0)])
>>>
>>> depq.addfirst('high', depq.high() + 1)
>>> depq.addlast('low', depq.low() - 1)
>>> depq
DEPQ([('high', 1), ('starter', 0), ('low', -1)])
>>>
>>> depq.addfirst('higher')  # Default priority DEPQ.high()
>>> depq.addlast('lower')  # Default priority DEPQ.low()
>>> depq
DEPQ([('higher', 1), ('high', 1), ('starter', 0), ('low', -1), ('lower', -1)])
>>>
>>> depq.addfirst('highest', 0)  # Invalid priority raises exception
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python34\lib\depq.py", line 340, in addfirst
    raise ValueError('Priority must be >= '
ValueError: Priority must be >= highest priority.
>>>
>>> del depq[0]  # As does del
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python34\lib\depq.py", line 639, in __delitem__
    raise NotImplementedError('Items cannot be deleted by '
NotImplementedError: Items cannot be deleted by referencing arbitrary indices.
>>>
>>> depq.clear()
>>> depq.count(None)
0
>>> for i in range(10):
...     depq.insert(None, i)
...
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5), (None, 4),
(None, 3), (None, 2), (None, 1), (None, 0)])
>>>
>>> None in depq
True
>>> depq.count(None)
10
>>> depq.remove(None)  # Removes item from DEPQ, default # of removals is 1
[(None, 0)]
>>>
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5), (None, 4),
(None, 3), (None, 2), (None, 1)])
>>>
>>> depq.remove(None, 4)  # As you see, returns list of tuple(item, priority)
[(None, 1), (None, 2), (None, 3), (None, 4)]
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 6), (None, 5)])
>>>
>>> depq[None] = 7  # Alias for DEPQ.insert(item, priority)
>>> print(fill(str(depq), 77))
DEPQ([(None, 9), (None, 8), (None, 7), (None, 7), (None, 6), (None, 5)])
>>>
>>> depq.elim(None)  # This simply calls DEPQ.remove(item, -1)
[(None, 5), (None, 6), (None, 7), (None, 7), (None, 8), (None, 9)]
>>> print(fill(str(depq), 77))
DEPQ([])
>>>
>>> import pickle  # Pickling won't work if items aren't picklable
>>> import json  # JSON won't work if items aren't JSON serializable
>>>
>>> for i in range(5):
...     depq.insert([i], i)  # Unhashable types allowed but don't mutate them!
...
>>> depq
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>>
>>> binary_depq = pickle.dumps(depq)
>>> print(fill(str(binary_depq), 77))
b'\x80\x03cdepq\nDEPQ\nq\x00)\x81q\x01}q\x02(X\x05\x00\x00\x00itemsq\x03}q\x0
4(X\x03\x00\x00\x00[1]q\x05K\x01X\x03\x00\x00\x00[3]q\x06K\x01X\x03\x00\x00\x
00[2]q\x07K\x01X\x03\x00\x00\x00[4]q\x08K\x01X\x03\x00\x00\x00[0]q\tK\x01uX\x
04\x00\x00\x00dataq\nccollections\ndeque\nq\x0b]q\x0c(]q\rK\x04aK\x04\x86q\x0
e]q\x0fK\x03aK\x03\x86q\x10]q\x11K\x02aK\x02\x86q\x12]q\x13K\x01aK\x01\x86q\x
14]q\x15K\x00aK\x00\x86q\x16e\x85q\x17Rq\x18X\x05\x00\x00\x00startq\x19K\x00u
b.'
>>>
>>> json_depq = json.dumps(depq.to_json())
>>> print(fill(json_depq, 77))
{"items": {"[1]": 1, "[3]": 1, "[2]": 1, "[4]": 1, "[0]": 1}, "data": [[[4],
4], [[3], 3], [[2], 2], [[1], 1], [[0], 0]], "start": 0}
>>>
>>> depq_from_pickle = pickle.loads(binary_depq)
>>> depq_from_json = DEPQ.from_json(json_depq)  # Classmethod returns new DEPQ
>>>
>>> depq
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>> depq_from_pickle
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>> depq_from_json
DEPQ([([4], 4), ([3], 3), ([2], 2), ([1], 1), ([0], 0)])
>>>

Notes:

  • The items in DEPQ are also stored along with their frequency in a separate dict for O(1) lookup. If item is un-hashable, the repr() of that item is stored instead. So ‘item in DEPQ’ would check the dict for item and if TypeError is raised it would try repr(item).
  • This implementation inserts in the middle in linear time whereas a textbook DEPQ is O(log n). In actual use cases though, this infinitesimal increase in run time is irrelevant, especially when one considers the extra functionality gained coupled with the fact that the other 2 main operations popfirst() and poplast() now occur in constant time.
Release History

Release History

1.5.3

This version

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

1.5.2

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

1.5.1

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

Download Files

Download Files

TODO: Brief introduction on what you do with files - including link to relevant help section.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
depq-1.5.3-py2.py3-none-any.whl (13.7 kB) Copy SHA256 Checksum SHA256 py2.py3 Wheel Mar 26, 2016

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS HPE HPE Development Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting