bidict¶
The bidirectional mapping library for Python.
Status¶
bidict:¶
- has been used for many years by several teams at Google, Venmo, CERN, Bank of America Merrill Lynch, Bloomberg, Two Sigma, and many others
- has carefully designed APIs for safety, simplicity, flexibility, and ergonomics
- is fast, lightweight, and has no runtime dependencies other than Python’s standard library
- integrates natively with Python’s
collections.abc
interfaces - provides type hints for all public APIs
- is implemented in concise, well-factored, pure (PyPy-compatible) Python code that is optimized for running efficiently as well as for reading and learning [1]
- has extensive docs and test coverage (including property-based tests and benchmarks) run continuously on all supported Python versions
Installation¶
pip install bidict
Quick Start¶
>>> from bidict import bidict
>>> element_by_symbol = bidict({'H': 'hydrogen'})
>>> element_by_symbol['H']
'hydrogen'
>>> element_by_symbol.inverse['hydrogen']
'H'
For more usage documentation, head to the Introduction [3] and proceed from there.
Voluntary Community Support¶
Please feel free to leave a message in the bidict chatroom or open a new issue on GitHub for voluntary community support. You can search through existing issues before creating a new one in case your issue has been addressed already.
Enterprise Support¶
Enterprise-level support for bidict can be obtained via the Tidelift subscription.
Notice of Usage¶
If you use bidict, and especially if your usage or your organization is significant in some way, please let me know in any of the following ways:
- star bidict on GitHub
- create an issue
- leave a message in the chat room
- email me
Release Notifications¶
Watch releases on GitHub or libraries.io to be notified when new versions of bidict are released.
Learning from bidict¶
One of the best things about bidict is that it touches a surprising number of interesting Python corners, especially given its small size and scope.
Check out Learning from bidict [1] if you’re interested in learning more.
Contributing¶
bidict is currently a one-person operation maintained on a voluntary basis.
Your help would be most welcome! See the Contributors’ Guide [4] for more information.
Sponsoring¶
Bidict is the product of thousands of hours of my unpaid work over the 12+ years I’ve been maintaining it.
If bidict has helped you accomplish your work, especially work you’ve been paid for, it’s easy to sponsor me through GitHub.
Choose a tier and GitHub handles everything else. The sponsorship just goes on your regular GitHub bill; there’s nothing extra to do. You can also sponsor me through Gumroad or PayPal.
Read more about companies supporting open source developers.
Finding Documentation¶
If you’re viewing this on https://bidict.readthedocs.io, note that multiple versions of the documentation are available, and you can choose a different version using the popup menu at the bottom-right. Please make sure you’re viewing the version of the documentation that corresponds to the version of bidict you’d like to use.
If you’re viewing this on GitHub, PyPI, or some other place that can’t render and link this documentation properly and are seeing broken links, try these alternate links instead:
[1] | (1, 2) docs/learning-from-bidict.rst | https://bidict.readthedocs.io/learning-from-bidict.html |
[2] | CHANGELOG.rst | https://bidict.readthedocs.io/changelog.html |
[3] | (1, 2) docs/intro.rst | https://bidict.readthedocs.io/intro.html |
[4] | docs/contributors-guide.rst | https://bidict.readthedocs.io/contributors-guide.html |
Next: Introduction [3]
Introduction¶
The bidict
library provides
several friendly, efficient data structures
for working with
bidirectional mappings
in Python.
bidict.bidict¶
bidict.bidict
is the main bidirectional mapping data structure provided.
It allows looking up the value associated with a key,
just like a dict
:
>>> element_by_symbol = bidict({'H': 'hydrogen'})
>>> element_by_symbol['H']
'hydrogen'
But it also allows looking up the key associated with a value,
via the special inverse
attribute:
>>> element_by_symbol.inverse['hydrogen']
'H'
The inverse
attribute actually
references the entire inverse bidirectional mapping:
>>> element_by_symbol
bidict({'H': 'hydrogen'})
>>> element_by_symbol.inverse
bidict({'hydrogen': 'H'})
…which is automatically kept in sync as the original mapping is updated:
>>> element_by_symbol['H'] = 'hydrogène'
>>> element_by_symbol.inverse
bidict({'hydrogène': 'H'})
If you’re used to working with dict
s,
you’ll feel right at home using bidict
:
>>> dir(element_by_symbol)
[..., '__getitem__', ..., '__setitem__', ..., 'items', 'keys', ...]
Familiar, concise, Pythonic.
Why can’t I just use a dict?¶
A skeptic writes:
If I want a mapping associating a → b and b → a, I can just create the dict{a: b, b: a}
. Why bother usingbidict
?
One answer is better ergonomics
for maintaining a correct representation.
For example, to get the correct length,
you’d have to take the number reported by len()
and cut it in half.
But now consider what happens when we need to store a new association, and we try to do so naively:
>>> el_by_sym = {'H': 'hydrogen', 'hydrogen': 'H'}
>>> # Later we need to associate 'H' with a different value
>>> el_by_sym.update({'H': 'hydrogène', 'hydrogène': 'H'} # Too naive
Here is what we’re left with:
>>> el_by_sym
{'H': 'hydrogène', 'hydrogène': 'H', 'hydrogen': 'H'}
Oops.
We forgot to look up whether the key and value we wanted to set already had any previous associations and remove them as necessary.
In general, if we want to store the association k ⟷ v, but we may have already stored the associations k ⟷ v′ or k′ ⟷ v, a correct implementation using the single-dict approach would require code like this:
>>> d = {'H': 'hydrogen', 'hydrogen': 'H'}
>>> def update(d, key, val):
... oldval = d.pop(key, object())
... d.pop(oldval, None)
... oldkey = d.pop(val, object())
... d.pop(oldkey, None)
... d.update({key: val, val: key})
>>> update(d, 'H', 'hydrogène')
>>> d == {'H': 'hydrogène', 'hydrogène': 'H'}
True
With bidict
, we can instead just write:
>>> b = bidict({'H': 'hydrogen'})
>>> b['H'] = 'hydrogène'
And bidict
takes care of all the fussy details,
leaving us with just what we wanted:
>>> b
bidict({'H': 'hydrogène'})
>>> b.inverse
bidict({'hydrogène': 'H'})
Even more important…¶
Beyond this, consider what would happen if we needed to work with just the keys, values, or items that we have associated.
Since the single-dict approach inserts values as keys into the same dict that it inserts keys into, we’d never be able to tell our keys and values apart.
So iterating over the keys would also yield the values (and vice versa), with no way to tell which was which.
Iterating over the items would yield twice as many as we wanted, with a (v, k) item that we’d have to ignore for each (k, v) item that we expect, and no way to tell which was which.
>>> # Compare the single-dict approach:
>>> set(d.keys()) == {'H', 'hydrogène'} # .keys() also gives values
True
>>> set(d.values()) == {'H', 'hydrogène'} # .values() also gives keys
True
>>> # ...to using a bidict:
>>> b.keys() == {'H'} # just the keys
True
>>> b.values() == {'hydrogène'} # just the values
True
In short, to model a bidirectional mapping correctly and unambiguously, we need two separate one-directional mappings, one for the forward associations and one for the inverse, that are kept in sync as the associations change.
This is exactly what bidict
does under the hood,
abstracting it into a clean and ergonomic interface.
bidict
’s APIs also provide power, flexibility, and safety,
making sure the one-to-one invariant is maintained
and inverse mappings are kept consistent,
while also helping make sure you don’t accidentally
shoot yourself in the foot.
Additional Functionality¶
Besides the standard bidict.bidict
type,
the bidict
module provides other bidirectional mapping variants:
frozenbidict
,
OrderedBidict
,
FrozenOrderedBidict
, and
namedbidict()
.
These, and bidict
’s other functionality,
will be covered in later sections.
But first, let’s look at a few more details of Basic Usage.
Basic Usage¶
Let’s return to the example from the Introduction:
>>> element_by_symbol = bidict(H='hydrogen')
As we saw, this behaves just like a dict,
but maintains a special
inverse
attribute
giving access to inverse items:
>>> element_by_symbol.inverse['helium'] = 'He'
>>> del element_by_symbol.inverse['hydrogen']
>>> element_by_symbol
bidict({'He': 'helium'})
bidict.bidict
supports the rest of the
collections.abc.MutableMapping
interface
as well:
>>> 'C' in element_by_symbol
False
>>> element_by_symbol.get('C', 'carbon')
'carbon'
>>> element_by_symbol.pop('He')
'helium'
>>> element_by_symbol
bidict()
>>> element_by_symbol.update(Hg='mercury')
>>> element_by_symbol
bidict({'Hg': 'mercury'})
>>> 'mercury' in element_by_symbol.inverse
True
>>> element_by_symbol.inverse.pop('mercury')
'Hg'
Because inverse items are maintained alongside forward items,
referencing a bidict
’s inverse
is always a constant-time operation.
Values Must Be Hashable¶
Because you must be able to look up keys by value as well as values by key, values must also be hashable.
Attempting to insert an unhashable value will result in an error:
>>> anagrams_by_alphagram = dict(opt=['opt', 'pot', 'top'])
>>> bidict(anagrams_by_alphagram)
Traceback (most recent call last):
...
TypeError: ...
So in this example, using a tuple or a frozenset instead of a list would do the trick:
>>> bidict(opt=('opt', 'pot', 'top'))
bidict({'opt': ('opt', 'pot', 'top')})
Values Must Be Unique¶
As we know,
in a bidirectional map,
not only must keys be unique,
but values must be unique as well.
This has immediate implications for bidict
’s API.
Consider the following:
>>> b = bidict({'one': 1})
>>> b['two'] = 1
What should happen next?
If the bidict allowed this to succeed, because of the uniqueness-of-values constraint, it would silently clobber the existing item, resulting in:
>>> b
bidict({'two': 1})
This could result in surprises or problems down the line.
Instead, bidict raises a
ValueDuplicationError
so you have an opportunity to catch this early
and resolve the conflict before it causes problems later on:
>>> b['two'] = 1
Traceback (most recent call last):
...
ValueDuplicationError: 1
The purpose of this is to be more in line with the Zen of Python, which advises,
So if you really just want to clobber any existing items, all you have to do is say so explicitly:
>>> b.forceput('two', 1)
>>> b
bidict({'two': 1})
Similarly, initializations and update()
calls
that would overwrite the key of an existing value
raise an exception too:
>>> bidict({'one': 1, 'uno': 1})
Traceback (most recent call last):
...
ValueDuplicationError: 1
>>> b = bidict({'one': 1})
>>> b.update([('uno', 1)])
Traceback (most recent call last):
...
ValueDuplicationError: 1
>>> b
bidict({'one': 1})
Setting an existing key to a new value does not cause an error, and is considered an intentional overwrite of the value associated with the existing key, in keeping with dict’s behavior:
>>> b = bidict({'one': 1})
>>> b['one'] = 2 # succeeds
>>> b
bidict({'one': 2})
>>> b.update([('one', 3), ('one', 4), ('one', 5)])
>>> b
bidict({'one': 5})
>>> bidict([('one', 1), ('one', 2)])
bidict({'one': 2})
In summary,
when attempting to insert an item whose key duplicates an existing item’s,
bidict
’s default behavior is to allow the insertion,
overwriting the existing item with the new one.
When attempting to insert an item whose value duplicates an existing item’s,
bidict
’s default behavior is to raise.
This design naturally falls out of the behavior of Python’s built-in dict,
and protects against unexpected data loss.
One set of alternatives to this behavior is provided by
forceput()
(mentioned above)
and forceupdate()
,
which allow you to explicitly overwrite existing keys and values:
>>> b = bidict({'one': 1})
>>> b.forceput('two', 1)
>>> b
bidict({'two': 1})
>>> b.forceupdate([('three', 1), ('four', 1)])
>>> b
bidict({'four': 1})
For even more control,
you can use put()
and putall()
.
These variants allow you to pass
an OnDup
instance
to specify custom OnDupAction
s
for each type of duplication that can occur.
>>> from bidict import OnDup, RAISE
>>> b = bidict({1: 'one'})
>>> b.put(1, 'uno', OnDup(key=RAISE))
Traceback (most recent call last):
...
KeyDuplicationError: 2
>>> b
bidict({1: 'one'})
bidict
provides the
ON_DUP_DEFAULT
,
ON_DUP_RAISE
, and
ON_DUP_DROP_OLD
OnDup
instances
for convenience.
If no on_dup argument is passed,
put()
and
putall()
will use ON_DUP_RAISE
,
providing stricter-by-default alternatives to
__setitem__()
and
update()
.
(These defaults complement the looser alternatives
provided by forceput()
and forceupdate()
.)
Key and Value Duplication¶
Note that it’s possible for a given item to duplicate the key of one existing item, and the value of another existing item. In the following example, the key of the third item duplicates the first item’s key, and the value of the third item dulicates the second item’s value:
>>> b.putall([(1, 2), (3, 4), (1, 4)], OnDup(key=...))
What should happen next?
Keep in mind, the active OnDup
may specify one OnDupAction
for key duplication
and a different OnDupAction
for value duplication
.
To account for this,
OnDup
allows you to use its
kv
field
to indicate how you want to handle this case
without ambiguity:
>>> from bidict import DROP_OLD
>>> on_dup = OnDup(key=DROP_OLD, val=RAISE, kv=RAISE)
>>> b.putall([(1, 2), (3, 4), (1, 4)], on_dup)
Traceback (most recent call last):
...
KeyAndValueDuplicationError: (1, 4)
If not specified, kv defaults to whatever was provided for val.
Note that repeated insertions of the same item
are construed as a no-op and will not raise,
no matter what the active OnDup
is:
>>> b = bidict({1: 'one'})
>>> b.put(1, 'one') # no-op, not a DuplicationError
>>> b.putall([(2, 'two'), (2, 'two')]) # The repeat (2, 'two') is also a no-op.
>>> sorted(b.items())
[(1, 'one'), (2, 'two')]
See the YoloBidict Recipe for another way to customize this behavior.
Updates Fail Clean¶
If an update to a bidict
fails,
you can be sure that it fails clean.
In other words, a bidict
will never
apply only part of an update that ultimately fails,
without restoring itself to the state it was in
before processing the update:
>>> b = bidict({1: 'one', 2: 'two'})
>>> b.putall([(3, 'three'), (1, 'uno')])
Traceback (most recent call last):
...
KeyDuplicationError: 1
>>> # (1, 'uno') was the problem...
>>> b # ...but (3, 'three') was not added either:
bidict({1: 'one', 2: 'two'})
Order Matters¶
Performing a bulk insert operation –
i.e. passing multiple items to
__init__()
,
update()
,
forceupdate()
,
or putall()
–
is like inserting each of those items individually in sequence.
[1]
Therefore, the order of the items provided to the bulk insert operation is significant to the result:
>>> b = bidict({0: 0, 1: 2})
>>> b.forceupdate([(2, 0), (0, 1), (0, 0)])
>>> # 1. (2, 0) overwrites (0, 0) -> bidict({2: 0, 1: 2})
>>> # 2. (0, 1) is added -> bidict({2: 0, 1: 2, 0: 1})
>>> # 3. (0, 0) overwrites (0, 1) and (2, 0) -> bidict({0: 0, 1: 2})
>>> sorted(b.items())
[(0, 0), (1, 2)]
>>> b = bidict({0: 0, 1: 2}) # as before
>>> # Give the same items to forceupdate() but in a different order:
>>> b.forceupdate([(0, 1), (0, 0), (2, 0)])
>>> # 1. (0, 1) overwrites (0, 0) -> bidict({0: 1, 1: 2})
>>> # 2. (0, 0) overwrites (0, 1) -> bidict({0: 0, 1: 2})
>>> # 3. (2, 0) overwrites (0, 0) -> bidict({1: 2, 2: 0})
>>> sorted(b.items()) # different items!
[(1, 2), (2, 0)]
[1] | Albeit with the extremely important advantage of failing clean. |
Interop¶
bidict
s interoperate well with other types of mappings.
For example, they support (efficient) polymorphic equality testing:
>>> bidict(a=1) == dict(a=1)
True
And converting back and forth works as expected (assuming no value duplication):
>>> dict(bidict(a=1))
{'a': 1}
>>> bidict(dict(a=1))
bidict({'a': 1})
See the Polymorphism section for more interoperability documentation.
Hopefully bidict
feels right at home
among the Python built-ins you already know.
Proceed to Other bidict Types
for documentation on the remaining bidict variants.
Other bidict
Types¶
Now that we’ve covered
Basic Usage with the bidict.bidict
type,
let’s look at some other bidirectional mapping types.
Bidict Types Diagram¶
All bidirectional mapping types that bidict
provides
are subclasses of bidict.BidirectionalMapping
.
This abstract base class
extends collections.abc.Mapping
by adding the
“inverse
”
abstractproperty
.
As you may have noticed,
bidict.bidict
is also
a collections.abc.MutableMapping
.
But bidict
provides
immutable bidirectional mapping types as well.
frozenbidict
¶
frozenbidict
is an immutable, hashable bidirectional mapping type.
As you would expect,
attempting to mutate a
frozenbidict
causes an error:
>>> from bidict import frozenbidict
>>> f = frozenbidict({'H': 'hydrogen'})
>>> f['C'] = 'carbon'
Traceback (most recent call last):
...
TypeError: 'frozenbidict' object does not support item assignment
frozenbidict
also implements collections.abc.Hashable
,
so it’s suitable for insertion into sets or other mappings:
>>> my_set = {f} # not an error
>>> my_dict = {f: 1} # also not an error
See the frozenbidict
API documentation for more information.
OrderedBidict
¶
bidict.OrderedBidict
is a MutableBidirectionalMapping
that preserves the ordering of its items,
and offers some additional ordering-related APIs
that non-ordered bidicts can’t offer.
It’s like a bidirectional version of collections.OrderedDict
.
>>> from bidict import OrderedBidict
>>> element_by_symbol = OrderedBidict([
... ('H', 'hydrogen'), ('He', 'helium'), ('Li', 'lithium')])
>>> element_by_symbol.inverse
OrderedBidict([('hydrogen', 'H'), ('helium', 'He'), ('lithium', 'Li')])
>>> first, second, third = element_by_symbol.values()
>>> first, second, third
('hydrogen', 'helium', 'lithium')
>>> # Insert an additional item and verify it now comes last:
>>> element_by_symbol['Be'] = 'beryllium'
>>> last_item = list(element_by_symbol.items())[-1]
>>> last_item
('Be', 'beryllium')
Additional ordering-related, mutating APIs
modeled after OrderedDict
, e.g.
popitem(last=False)
and
move_to_end()
,
are provided as well:
>>> element_by_symbol.popitem(last=True) # Remove the last item
('Be', 'beryllium')
>>> element_by_symbol.popitem(last=False) # Remove the first item
('H', 'hydrogen')
>>> # Re-adding hydrogen after it's been removed moves it to the end:
>>> element_by_symbol['H'] = 'hydrogen'
>>> element_by_symbol
OrderedBidict([('He', 'helium'), ('Li', 'lithium'), ('H', 'hydrogen')])
>>> # But there's also a `move_to_end` method just for this purpose:
>>> element_by_symbol.move_to_end('Li')
>>> element_by_symbol
OrderedBidict([('He', 'helium'), ('H', 'hydrogen'), ('Li', 'lithium')])
>>> element_by_symbol.move_to_end('H', last=False) # move to front
>>> element_by_symbol
OrderedBidict([('H', 'hydrogen'), ('He', 'helium'), ('Li', 'lithium')])
As with OrderedDict
,
updating an existing item preserves its position in the order:
>>> element_by_symbol['He'] = 'updated in place!'
>>> element_by_symbol
OrderedBidict([('H', 'hydrogen'), ('He', 'updated in place!'), ('Li', 'lithium')])
Collapsing overwrites¶
When setting an item in an ordered bidict whose key duplicates that of an existing item, and whose value duplicates that of a different existing item, the existing item whose value is duplicated will be dropped, and the existing item whose key is duplicated will have its value overwritten in place:
>>> o = OrderedBidict([(1, 2), (3, 4), (5, 6), (7, 8)])
>>> o.forceput(3, 8) # item with duplicated value (7, 8) is dropped...
>>> o # and the item with duplicated key (3, 4) is updated in place:
OrderedBidict([(1, 2), (3, 8), (5, 6)])
>>> # (3, 8) took the place of (3, 4), not (7, 8)
>>> o = OrderedBidict([(1, 2), (3, 4), (5, 6), (7, 8)]) # as before
>>> o.forceput(5, 2) # another example
>>> o
OrderedBidict([(3, 4), (5, 2), (7, 8)])
>>> # (5, 2) took the place of (5, 6), not (1, 2)
__eq__()
is order-insensitive¶
To ensure that equality of bidicts is transitive (and to uphold the Liskov substitution principle), equality tests between an ordered bidict and other mappings are always order-insensitive:
>>> b = bidict([('one', 1), ('two', 2)])
>>> o1 = OrderedBidict([('one', 1), ('two', 2)])
>>> o2 = OrderedBidict([('two', 2), ('one', 1)])
>>> b == o1
True
>>> b == o2
True
>>> o1 == o2
True
For order-sensitive equality tests, use
equals_order_sensitive()
:
>>> o1.equals_order_sensitive(o2)
False
Note that this differs from the behavior of
collections.OrderedDict
’s __eq__()
,
by recommendation of Raymond Hettinger
(the author of OrderedDict
) himself.
He later said that making OrderedDict’s __eq__()
intransitive was a mistake.
What about order-preserving dicts?¶
In CPython 3.6+ and all versions of PyPy,
dict
(which bidicts are built on)
preserves insertion order.
Given that, can you get away with
using a non-ordered bidict
in places where you need
an order-preserving bidirectional mapping
(assuming you don’t need the additional ordering-related, mutating APIs
offered by OrderedBidict
like move_to_end()
)?
Consider this example:
>>> ob = OrderedBidict([(1, -1), (2, -2), (3, -3)])
>>> b = bidict(ob)
>>> ob[2] = b[2] = 'UPDATED'
>>> ob
OrderedBidict([(1, -1), (2, 'UPDATED'), (3, -3)])
>>> b # so far so good:
bidict({1: -1, 2: 'UPDATED', 3: -3})
>>> b.inverse # but look what happens here:
bidict({-1: 1, -3: 3, 'UPDATED': 2})
>>> ob.inverse # need an OrderedBidict for full order preservation
OrderedBidict([(-1, 1), ('UPDATED', 2), (-3, 3)])
When the value associated with the key 2
in the non-ordered bidict b
was changed,
the corresponding item stays in place in the forward mapping,
but moves to the end of the inverse mapping.
Since non-ordered bidicts
provide weaker ordering guarantees
(which allows for a more efficient implementation),
it’s possible to see behavior like in the example above
after certain sequences of mutations.
That said, if you depend on preserving insertion order, a non-ordered bidict may be sufficient if:
- you’ll never mutate it
(in which case, use a
frozenbidict
), or: - you only mutate by removing and/or adding whole new items, never changing just the key or value of an existing item, or:
- you’re only changing existing items in the forward direction (i.e. changing values by key, rather than changing keys by value), and only depend on the order in the forward bidict, not the order of the items in its inverse.
On the other hand, if your code is actually depending on the order, using an explicitly-ordered bidict type makes for clearer code.
OrderedBidict
also gives you
additional ordering-related mutating APIs, such as
move_to_end()
and
popitem(last=False)
,
should you ever need them.
(And on Python < 3.8,
OrderedBidict
also gives you
__reversed__()
.
On Python 3.8+, all bidicts are reversible
as of v0.21.3.)
FrozenOrderedBidict
¶
FrozenOrderedBidict
is an immutable ordered bidict type.
It’s like a hashable
OrderedBidict
without the mutating APIs,
or like a reversible
frozenbidict
even on Python < 3.8.
(All bidict
s are
order-preserving when never mutated,
so frozenbidict
is already order-preserving,
but only on Python 3.8+, where dict
s
are reversible
,
are all bidict
s (including frozenbidict
)
also reversible
.)
If you are using Python 3.8+,
frozenbidict
gives you everything that
FrozenOrderedBidict
gives you,
but with less space overhead.
namedbidict()
¶
bidict.namedbidict()
,
inspired by collections.namedtuple()
,
allows you to easily generate
a new bidirectional mapping type
with custom attribute-based access to forward and inverse mappings:
>>> from bidict import namedbidict
>>> ElementMap = namedbidict('ElementMap', 'symbol', 'name')
>>> noble_gases = ElementMap(He='helium')
>>> noble_gases.name_for['He']
'helium'
>>> noble_gases.symbol_for['helium']
'He'
>>> noble_gases.name_for['Ne'] = 'neon'
>>> del noble_gases.symbol_for['helium']
>>> noble_gases
ElementMap({'Ne': 'neon'})
Using the base_type keyword arg –
whose default value is bidict.bidict
–
you can override the bidict type used as the base class,
allowing the creation of e.g. a named frozenbidict type:
>>> ElMap = namedbidict('ElMap', 'symbol', 'name', base_type=frozenbidict)
>>> noble = ElMap(He='helium')
>>> noble.symbol_for['helium']
'He'
>>> hash(noble) is not TypeError # does not raise TypeError: unhashable type
True
>>> noble['C'] = 'carbon' # mutation fails
Traceback (most recent call last):
...
TypeError: 'ElMap' object does not support item assignment
Polymorphism¶
(Or: ABCs ftw!)
You may be tempted to write something like isinstance(obj, dict)
to check whether obj
is a Mapping
.
However, this check is too specific, and will fail for many
types that implement the Mapping
interface:
>>> from collections import ChainMap
>>> issubclass(ChainMap, dict)
False
The same is true for all the bidict types:
>>> issubclass(bidict, dict)
False
The proper way to check whether an object
is a Mapping
is to use the abstract base classes (ABCs)
from the collections.abc
module
that are provided for this purpose:
>>> issubclass(ChainMap, Mapping)
True
>>> isinstance(bidict(), Mapping)
True
Also note that the proper way to check whether an object
is an (im)mutable mapping is to use the
MutableMapping
ABC:
>>> from bidict import BidirectionalMapping
>>> def is_immutable_bimap(obj):
... return (isinstance(obj, BidirectionalMapping)
... and not isinstance(obj, MutableMapping))
>>> is_immutable_bimap(bidict())
False
>>> is_immutable_bimap(frozenbidict())
True
Checking for isinstance(obj, frozenbidict)
is too specific
and could fail in some cases.
For example, FrozenOrderedBidict
is an immutable mapping
but it does not subclass frozenbidict
:
>>> from bidict import FrozenOrderedBidict
>>> obj = FrozenOrderedBidict()
>>> is_immutable_bimap(obj)
True
>>> isinstance(obj, frozenbidict)
False
Besides the above, there are several other collections ABCs
whose interfaces are implemented by various bidict types.
Have a look through the collections.abc
documentation
if you’re interested.
For more you can do with bidict
,
check out Extending bidict next.
Extending bidict
¶
Although bidict
provides the various bidirectional mapping types covered already,
it’s possible that some use case might require something more than what’s provided.
For this reason,
bidict
was written with extensibility in mind.
Let’s look at some examples.
YoloBidict
Recipe¶
If you’d like
ON_DUP_DROP_OLD
to be the default on_dup
behavior
(for __init__()
,
__setitem__()
, and
update()
),
you can use the following recipe:
>>> from bidict import bidict, ON_DUP_DROP_OLD
>>> class YoloBidict(bidict):
... __slots__ = ()
... on_dup = ON_DUP_DROP_OLD
>>> b = YoloBidict({'one': 1})
>>> b['two'] = 1 # succeeds, no ValueDuplicationError
>>> b
YoloBidict({'two': 1})
>>> b.update({'three': 1}) # ditto
>>> b
YoloBidict({'three': 1})
Of course, YoloBidict
’s inherited
put()
and
putall()
methods
still allow specifying a custom OnDup
per call via the on_dup argument,
and will both still default to raising for all duplication types.
Further demonstrating bidict
’s extensibility,
to make an OrderedYoloBidict
,
simply have the subclass above inherit from
bidict.OrderedBidict
rather than bidict.bidict
.
Beware of ON_DUP_DROP_OLD
¶
There’s a good reason that bidict
does not provide a YoloBidict
out of the box.
Before you decide to use a YoloBidict
in your own code,
beware of the following potentially unexpected, dangerous behavior:
>>> b = YoloBidict({'one': 1, 'two': 2}) # contains two items
>>> b['one'] = 2 # update one of the items
>>> b # now only has one item!
YoloBidict({'one': 2})
As covered in Key and Value Duplication, setting an existing key to the value of a different existing item causes both existing items to quietly collapse into a single new item.
A safer example of this type of customization would be something like:
>>> from bidict import ON_DUP_RAISE
>>> class YodoBidict(bidict):
... __slots__ = ()
... on_dup = ON_DUP_RAISE
>>> b = YodoBidict({'one': 1})
>>> b['one'] = 2 # Works with a regular bidict, but Yodo plays it safe.
Traceback (most recent call last):
...
KeyDuplicationError: one
>>> b
YodoBidict({'one': 1})
>>> b.forceput('one', 2) # Any destructive change requires more force.
>>> b
YodoBidict({'one': 2})
SortedBidict
Recipes¶
Suppose you need a bidict that maintains its items in sorted order. The Python standard library does not include any sorted dict types, but the excellent sortedcontainers and sortedcollections libraries do.
Armed with these, along with BidictBase
’s
_fwdm_cls
(forward mapping class) and
_invm_cls
(inverse mapping class) attributes,
creating a sorted bidict is simple:
>>> from bidict import MutableBidict
>>> from sortedcontainers import SortedDict
>>> class SortedBidict(MutableBidict):
... """A sorted bidict whose forward items stay sorted by their keys,
... and whose inverse items stay sorted by *their* keys.
... Note: As a result, an instance and its inverse yield their items
... in different orders.
... """
... __slots__ = ()
... _fwdm_cls = SortedDict
... _invm_cls = SortedDict
... _repr_delegate = list # only used for list-style repr
>>> b = SortedBidict({'Tokyo': 'Japan', 'Cairo': 'Egypt'})
>>> b
SortedBidict([('Cairo', 'Egypt'), ('Tokyo', 'Japan')])
>>> b['Lima'] = 'Peru'
>>> list(b.items()) # stays sorted by key
[('Cairo', 'Egypt'), ('Lima', 'Peru'), ('Tokyo', 'Japan')]
>>> list(b.inverse.items()) # .inverse stays sorted by *its* keys (b's values)
[('Egypt', 'Cairo'), ('Japan', 'Tokyo'), ('Peru', 'Lima')]
Here’s a recipe for a sorted bidict whose forward items stay sorted by their keys, and whose inverse items stay sorted by their values. i.e. An instance and its inverse will yield their items in the same order:
>>> from sortedcollections import ValueSortedDict
>>> class KeySortedBidict(MutableBidict):
... __slots__ = ()
... _fwdm_cls = SortedDict
... _invm_cls = ValueSortedDict
... _repr_delegate = list
>>> elem_by_atomicnum = KeySortedBidict({
... 6: 'carbon', 1: 'hydrogen', 2: 'helium'})
>>> list(elem_by_atomicnum.items()) # stays sorted by key
[(1, 'hydrogen'), (2, 'helium'), (6, 'carbon')]
>>> list(elem_by_atomicnum.inverse.items()) # .inverse stays sorted by value
[('hydrogen', 1), ('helium', 2), ('carbon', 6)]
>>> elem_by_atomicnum[4] = 'beryllium'
>>> list(elem_by_atomicnum.inverse.items())
[('hydrogen', 1), ('helium', 2), ('beryllium', 4), ('carbon', 6)]
Dynamic Inverse Class Generation¶
When a bidict class’s
_fwdm_cls
and
_invm_cls
are the same,
the bidict class is its own inverse class.
(This is the case for all the
bidict classes
that come with bidict
.)
However, when a bidict’s
_fwdm_cls
and
_invm_cls
differ,
as in the KeySortedBidict
example above,
the inverse class of the bidict
needs to have its
_fwdm_cls
and
_invm_cls
swapped.
BidictBase
detects this
and dynamically computes the correct inverse class for you automatically.
You can see this if you inspect KeySortedBidict
’s inverse bidict:
>>> elem_by_atomicnum.inverse.__class__.__name__
'KeySortedBidictInv'
Notice that BidictBase
automatically created a
KeySortedBidictInv
class and used it for the inverse bidict.
As expected, KeySortedBidictInv
’s
_fwdm_cls
and
_invm_cls
are the opposite of KeySortedBidict
’s:
>>> elem_by_atomicnum.inverse._fwdm_cls.__name__
'ValueSortedDict'
>>> elem_by_atomicnum.inverse._invm_cls.__name__
'SortedDict'
BidictBase
also ensures that round trips work as expected:
>>> KeySortedBidictInv = elem_by_atomicnum.inverse.__class__ # i.e. a value-sorted bidict
>>> atomicnum_by_elem = KeySortedBidictInv(elem_by_atomicnum.inverse)
>>> atomicnum_by_elem
KeySortedBidictInv([('hydrogen', 1), ('helium', 2), ('beryllium', 4), ('carbon', 6)])
>>> KeySortedBidict(atomicnum_by_elem.inverse) == elem_by_atomicnum
True
You can even play tricks with attribute lookup redirection here too.
For example, to pass attribute access through to the backing _fwdm
mapping
when an attribute is not provided by the bidict class itself,
you can override __getattribute__()
as follows:
>>> def __getattribute__(self, name):
... try:
... return object.__getattribute__(self, name)
... except AttributeError as e:
... return getattr(self._fwdm, name)
>>> KeySortedBidict.__getattribute__ = __getattribute__
Now, even though this KeySortedBidict
itself provides no peekitem
attribute,
the following call still succeeds
because it’s passed through to the backing SortedDict
:
>>> elem_by_atomicnum.peekitem()
(6, 'carbon')
This goes to show how simple it can be
to compose your own bidirectional mapping types
out of the building blocks that bidict
provides.
Next proceed to Other Functionality.
Other Functionality¶
bidict.inverted()
¶
bidict provides the inverted
iterator
to help you get inverse items from various types of objects.
Pass in a mapping to get the inverse mapping:
>>> from bidict import inverted
>>> it = inverted({1: 'one'})
>>> {k: v for (k, v) in it}
{'one': 1}
…an iterable of pairs to get the pairs’ inverses:
>>> list(inverted([(1, 'one'), (2, 'two')]))
[('one', 1), ('two', 2)]
>>> list(inverted((i*i, i) for i in range(2, 5)))
[(2, 4), (3, 9), (4, 16)]
…or any object implementing an __inverted__
method,
which objects that already know their own inverses (such as bidicts)
can implement themselves:
>>> dict(inverted(bidict({1: 'one'})))
{'one': 1}
>>> list(inverted(OrderedBidict([(2, 4), (3, 9)])))
[(4, 2), (9, 3)]
Perhaps you’d be interested in taking a look at the Addendum next.
Addendum¶
Performance¶
bidict
strives to be as performant as possible
while being faithful to its purpose.
The need for speed
is balanced with the responsibility
to protect users from shooting themselves in the foot.
In general,
accomplishing some task using bidict
should have about the same performance
as keeping two inverse dicts in sync manually.
The test suite includes benchmarks for common workloads
to catch any performance regressions.
If you spot a case where bidict
’s performance could be improved,
please don’t hesitate to
file an issue or submit a pull request.
bidict
Avoids Reference Cycles¶
A careful reader might notice the following…
>>> fwd = bidict(one=1)
>>> inv = fwd.inverse
>>> inv.inverse is fwd
True
…and worry that a bidict
and its inverse
create a reference cycle.
If this were true,
in CPython this would mean that the memory for a bidict
could not be immediately reclaimed when you retained no more references to it,
but rather would have to wait for the next garbage collection to kick in
before it could be reclaimed.
However, bidict
s use a weakref.ref
to store the inverse reference in one direction,
avoiding the strong reference cycle.
As a result, when you no longer retain
any references to a bidict
you create,
you can be sure that its refcount in CPython drops to zero,
and that its memory will therefore be reclaimed immediately.
Note
In PyPy this is not an issue, as PyPy doesn’t use reference counts. The memory for unreferenced objects in PyPy is only reclaimed when GC kicks in, which is unpredictable.
Terminology¶
It’s intentional that the term “inverse” is used rather than “reverse”.
Consider a collection of (k, v) pairs. Taking the reverse of the collection can only be done if it is ordered, and (as you’d expect) reverses the order of the pairs in the collection. But each original (k, v) pair remains in the resulting collection.
By contrast, taking the inverse of such a collection neither requires the collection to be ordered nor guarantees any ordering in the result, but rather just replaces every (k, v) pair with the inverse pair (v, k).
“keys” and “values” could perhaps more properly be called “primary keys” and “secondary keys” (as in a database), or even “forward keys” and “inverse keys”, respectively.
bidict
sticks with the terms “keys” and “values” for the sake of familiarity and to avoid potential confusion, but technically values are also keys themselves.Concretely, this allows
bidict
s to return a set-like (dict_keys) object forvalues()
, rather than a non-set-like dict_values object.
Missing bidict
s in the Standard Library¶
The Python standard library actually contains some examples
where bidict
s could be used for fun and profit
(depending on your ideas of fun and profit):
- The
logging
module contains a private_levelToName
dict which maps integer levels like 10 to their string names like DEBUG. If I had a nickel for every time I wanted that exposed in a bidirectional map (and as a public attribute, no less), I bet I could afford some better turns of phrase. - The
dis
module maintains a mapping from opnames to opcodesdis.opmap
and a separate list of opnames indexed by opcodedis.opnames
. These could be combined into a single bidict. - Python 3’s
html.entities
module maintains separatehtml.entities.name2codepoint
andhtml.entities.codepoint2name
dicts. These could be combined into a single bidict.
Caveats¶
Non-Atomic Mutation¶
As with built-in dicts,
mutating operations on a bidict
are not atomic.
If you need to mutate the same bidict
from different threads,
use a
synchronization primitive
to coordinate access. [1]
[1] | See also: [2], [3] |
Equivalent but distinct Hashable
s¶
Consider the following:
>>> d = {1: int, 1.0: float}
How many items do you expect d to contain? The actual result might surprise you:
>>> len(d)
1
And similarly,
>>> dict([(1, int), (1.0, float), (1+0j, complex), (True, bool)])
{1: <... 'bool'>}
>>> 1.0 in {True}
True
(Note that 1 == 1.0 == 1+0j == True
.)
This illustrates that a mapping cannot contain two items with equivalent but distinct keys (and likewise a set cannot contain two equivalent but distinct elements). If an object that is being looked up in a set or mapping is equal to a contained object, the contained object will be found, even if it is distinct.
With a bidict
,
since values function as keys in the inverse mapping,
this behavior occurs in the inverse direction too,
and means that a bidict
can end up with a different
but equivalent key from the corresponding value
in its own inverse:
>>> b = bidict({'false': 0})
>>> b.forceput('FALSE', False)
>>> b
bidict({'FALSE': False})
>>> b.inverse
bidict({0: 'FALSE'})
nan as a Key¶
In CPython, nan is especially tricky when used as a dictionary key:
>>> d = {float('nan'): 'nan'}
>>> d
{nan: 'nan'}
>>> d[float('nan')]
Traceback (most recent call last):
...
KeyError: nan
>>> d[float('nan')] = 'not overwritten'
>>> d
{nan: 'nan', nan: 'not overwritten'}
In other Python implementations such as PyPy,
nan behaves just like any other dictionary key.
But in CPython, beware of this unexpected behavior,
which applies to bidict
s too.
bidict
contains no special-case logic
for dealing with nan as a key,
so the behavior will match dict
’s
wherever bidict
is running.
See e.g. these docs for more info (search the page for “nan”).
For more in this vein, check out Learning from bidict.
Changelog¶
Release Notifications¶
Tip: Subscribe to releases
on GitHub or
libraries.io
to be notified when new versions of bidict
are released.
0.21.4 (2021-10-23)¶
Explicitly declare support for Python 3.10 as well as some minor internal improvements.
0.21.3 (2021-09-05)¶
All bidicts now provide the
equals_order_sensitive()
method, not justOrderedBidict
s.Since support for Python < 3.6 was dropped in v0.21.0,
dict
s provide a deterministic ordering on all supported Python versions, and as a result, all bidicts do too. So now even non-Ordered
bidicts might as well provideequals_order_sensitive()
.See the updated What about order-preserving dicts? docs for more info.
Take better advantage of the fact that dicts became
reversible
in Python 3.8.Specifically, now even non-
Ordered
bidicts provide a__reversed__()
implementation on Python 3.8+, since it can piggyback off the efficientdict.__reversed__()
implementation.As a result, if you are using Python 3.8+,
frozenbidict
now gives you everything thatFrozenOrderedBidict
gives you, but with less space overhead.Drop setuptools_scm as a
setup_requires
dependency.Remove the
bidict.__version_info__
attribute.
0.21.1 (2020-09-07)¶
This release was yanked and replaced with the 0.21.2 release, which actually provides the intended changes.
0.21.0 (2020-08-22)¶
bidict
now provides type hints! ⌨️ ✅Adding type hints to
bidict
poses particularly interesting challenges due to the combination of generic types, dynamically-generated types (such as inverse bidict classes andnamedbidicts
), and complicating optimizations such as the use of slots and weakrefs.It didn’t take long to hit bugs and missing features in the state of the art for type hinting in Python today, e.g. missing higher-kinded types support (python/typing#548), too-narrow type hints for
collections.abc.Mapping
(python/typeshed#4435), atyping.Generic
bug in Python 3.6 (BPO-41451), etc.That said, this release should provide a solid foundation for code using
bidict
that enables static type checking.As always, if you spot any opportunities to improve
bidict
(including its new type hints), please don’t hesitate to submit a PR!Add
bidict.MutableBidirectionalMapping
ABC.The Bidict Types Diagram has been updated accordingly.
Drop support for Python 3.5, which reaches end of life on 2020-09-13, represents a tiny percentage of bidict downloads on PyPI Stats, and lacks support for variable type hint syntax, ordered dicts, and
object.__init_subclass__
.Remove the no-longer-needed
bidict.compat
module.Move inverse bidict class access from a property to an attribute set in
__init_subclass__
, to save function call overhead on repeated access.bidict.OrderedBidictBase.__iter__()
no longer accepts areverse
keyword argument so that it matches the signature ofcontainer.__iter__()
.Set the
__module__
attribute of variousbidict
types (usingsys._getframe()
when necessary) so that private, internal modules are not exposed e.g. in classes’ repr strings.namedbidict()
now immediately raisesTypeError
if the providedbase_type
does not provide_isinv
or__getstate__()
, rather than succeeding with a class whose instances may raiseAttributeError
when these attributes are accessed.
0.20.0 (2020-07-23)¶
The following breaking changes are expected to affect few if any users.
Remove APIs deprecated in the previous release:
bidict.OVERWRITE
andbidict.IGNORE
.The
on_dup_key
,on_dup_val
, andon_dup_kv
arguments ofput()
andputall()
.The
on_dup_key
,on_dup_val
, andon_dup_kv
bidict
class attributes.Remove
bidict.BidirectionalMapping.__subclasshook__()
due to lack of use and maintenance cost.Fixes a bug introduced in 0.15.0 that caused any class with an
inverse
attribute to be incorrectly considered a subclass ofcollections.abc.Mapping
. #111
0.19.0 (2020-01-09)¶
Drop support for Python 2 as promised in v0.18.2.
The
bidict.compat
module has been pruned accordingly.This makes bidict more efficient on Python 3 and enables further improvement to bidict in the future.
Deprecate
bidict.OVERWRITE
andbidict.IGNORE
. AUserWarning
will now be emitted if these are used.bidict.DROP_OLD
andbidict.DROP_NEW
should be used instead.Rename
DuplicationPolicy
toOnDupAction
(and implement it via anEnum
).An
OnDupAction
may be one ofRAISE
,DROP_OLD
, orDROP_NEW
.Expose the new
OnDup
class to contain the threeOnDupAction
s that should be taken upon encountering the three kinds of duplication that can occur (key, val, kv).Provide the
ON_DUP_DEFAULT
,ON_DUP_RAISE
, andON_DUP_DROP_OLD
OnDup
convenience instances.Deprecate the
on_dup_key
,on_dup_val
, andon_dup_kv
arguments ofput()
andputall()
. AUserWarning
will now be emitted if these are used.These have been subsumed by the new on_dup argument, which takes an
OnDup
instance.Use it like this:
bi.put(1, 2, OnDup(key=RAISE, val=...))
. Or pass one of the instances already provided, such asON_DUP_DROP_OLD
. Or just don’t pass an on_dup argument to use the default value ofON_DUP_RAISE
.The Values Must Be Unique docs have been updated accordingly.
Deprecate the
on_dup_key
,on_dup_val
, andon_dup_kv
bidict
class attributes. AUserWarning
will now be emitted if these are used.These have been subsumed by the new
on_dup
class attribute, which takes anOnDup
instance.See the updated Extending bidict docs for example usage.
Improve the more efficient implementations of
keys()
,values()
, anditems()
, and now also provide a more efficient implementation of__iter__()
by delegating to backingdict
s in the bidict types for which this is possible.Move
bidict.BidictBase.values()
tobidict.BidirectionalMapping.values()
, since the implementation is generic.No longer use
__all__
inbidict
’s__init__.py
.
0.18.4 (2020-11-02)¶
- Backport fix from v0.20.0
that removes
bidict.BidirectionalMapping.__subclasshook__()
due to lack of use and maintenance cost.
0.18.3 (2019-09-22)¶
- Improve validation of names passed to
namedbidict()
: Usestr.isidentifier()
on Python 3, and a better regex on Python 2. - On Python 3,
set
__qualname__
onnamedbidict()
classes based on the providedtypename
argument.
0.18.2 (2019-09-08)¶
- Warn that Python 2 support will be dropped in a future release when Python 2 is detected.
0.18.1 (2019-09-03)¶
- Fix a regression introduced by the memory optimizations added in 0.15.0
which caused
deepcopied
andunpickled
bidicts to have their inverses set incorrectly. #94
0.18.0 (2019-02-14)¶
Rename
bidict.BidirectionalMapping.inv
toinverse
and makebidict.BidictBase.inv
an alias forinverse
. #86bidict.BidirectionalMapping.__subclasshook__()
now requires aninverse
attribute rather than aninv
attribute for a class to qualify as a virtual subclass. This breaking change is expected to affect few if any users.Add Python 2/3-compatible
bidict.compat.collections_abc
alias.Stop testing Python 3.4 on CI, and warn when Python 3 < 3.5 is detected rather than Python 3 < 3.3.
Python 3.4 reaches end of life on 2019-03-18. As of January 2019, 3.4 represents only about 3% of bidict downloads on PyPI Stats.
0.17.5 (2018-11-19)¶
Improvements to performance and delegation logic, with minor breaking changes to semi-private APIs.
Remove the
__delegate__
instance attribute added in the previous release. It was overly general and not worth the cost.Instead of checking
self.__delegate__
and delegating accordingly each time a possibly-delegating method is called, revert back to using “delegated-to-fwdm” mixin classes (now found inbidict._delegating_mixins
), and resurrect a mutable bidict parent class that omits the mixins asbidict.MutableBidict
.Rename
__repr_delegate__
to_repr_delegate
.
0.17.4 (2018-11-14)¶
Minor code, interop, and (semi-)private API improvements.
OrderedBidict
optimizations and code improvements.Use
bidict
s for the backing_fwdm
and_invm
mappings, obviating the need to store key and value data in linked list nodes.Refactor proxied- (i.e. delegated-) to-
_fwdm
logic for better composability and interoperability.Drop the
_Proxied*
mixin classes and instead move their methods intoBidictBase
, which now checks for an object defined by theBidictBase.__delegate__
attribute. TheBidictBase.__delegate__
object will be delegated to if the method is available on it, otherwise a default implementation (e.g. inherited fromMapping
) will be used otherwise. Subclasses may set__delegate__ = None
to opt out.Consolidate
_MutableBidict
intobidict.bidict
now that the dropped mixin classes make it unnecessary.Change
__repr_delegate__
to simply take a type likedict
orlist
.Upgrade to latest major sortedcontainers version (from v1 to v2) for the SortedBidict Recipes.
bidict.compat.{view,iter}{keys,values,items}
on Python 2 no longer assumes the target object implements these methods, as they’re not actually part of theMapping
interface, and provides fallback implementations when the methods are unavailable. This allows the SortedBidict Recipes to continue to work with sortedcontainers v2 on Python 2.
0.17.3 (2018-09-18)¶
- Improve packaging by adding a pyproject.toml and by including more supporting files in the distribution. #81
- Drop pytest-runner and support for running tests via
python setup.py test
in preference topytest
orpython -m pytest
.
0.17.2 (2018-04-30)¶
Memory usage improvements¶
- Use less memory in the linked lists that back
OrderedBidict
s by storing node data unpacked rather than in (key, value) tuple objects.
0.17.1 (2018-04-28)¶
Bugfix Release¶
Fix a regression in 0.17.0 that could cause erroneous behavior
when updating items of an Orderedbidict
’s inverse,
e.g. some_ordered_bidict.inv[foo] = bar
.
0.17.0 (2018-04-25)¶
Speedups and memory usage improvements¶
Pass
keys()
,values()
, anditems()
calls (as well as theiriter*
andview*
counterparts on Python 2) through to the backing_fwdm
and_invm
dicts so that they run as fast as possible (i.e. at C speed on CPython), rather than using the slower implementations inherited fromcollections.abc.Mapping
.Use weakrefs in the linked lists that back
OrderedBidict
s to avoid creating strong reference cycles.Memory for an ordered bidict that you create can now be reclaimed in CPython as soon as you no longer hold any references to it, rather than having to wait until the next garbage collection. #71
Misc¶
- Add
bidict.__version_info__
attribute to complementbidict.__version__
.
0.16.0 (2018-04-06)¶
Minor code and efficiency improvements to
inverted()
and
_iteritems_args_kw()
(formerly bidict.pairs()
).
Minor Breaking API Changes¶
The following breaking changes are expected to affect few if any users.
- Rename
bidict.pairs()
→bidict._util._iteritems_args_kw
.
0.15.0 (2018-03-29)¶
Speedups and memory usage improvements¶
- Use __slots__ to speed up bidict attribute access and reduce memory usage. On Python 3, instantiating a large number of bidicts now uses ~57% the amount of memory that it used before, and on Python 2 only ~33% the amount of memory that it used before, in a simple but representative benchmark.
- Use weakrefs to refer to a bidict’s inverse internally, no longer creating a strong reference cycle. Memory for a bidict that you create can now be reclaimed in CPython as soon as you no longer hold any references to it, rather than having to wait for the next garbage collection. See the new bidict Avoids Reference Cycles documentation. #24
- Make
bidict.BidictBase.__eq__()
significantly more speed- and memory-efficient when comparing to a non-dict
Mapping
. (Mapping.__eq__()
’s inefficient implementation will now never be used.) The implementation is now more reusable as well. - Make
bidict.OrderedBidictBase.__iter__()
as well as equality comparison slightly faster for ordered bidicts.
Minor Bugfixes¶
namedbidict()
now verifies that the providedkeyname
andvalname
are distinct, raisingValueError
if they are equal.namedbidict()
now raisesTypeError
if the providedbase_type
is not aBidirectionalMapping
.- If you create a custom bidict subclass whose
_fwdm_cls
differs from its_invm_cls
(as in theFwdKeySortedBidict
example from the SortedBidict Recipes), the inverse bidirectional mapping type (with_fwdm_cls
and_invm_cls
swapped) is now correctly computed and used automatically for your custom bidict’sinverse
bidict.
Miscellaneous¶
- Classes no longer have to provide an
__inverted__
attribute to be considered virtual subclasses ofBidirectionalMapping
. - If
bidict.inverted()
is passed an object with an__inverted__
attribute, it now ensures it iscallable()
before returning the result of calling it. __repr__()
no longer checks for a__reversed__
method to determine whether to use an ordered or unordered-style repr. It now calls the new__repr_delegate__
instead (which may be overridden if needed), for better composability.
Minor Breaking API Changes¶
The following breaking changes are expected to affect few if any users.
Split back out the
BidictBase
class fromfrozenbidict
andOrderedBidictBase
fromFrozenOrderedBidict
, reverting the merging of these in 0.14.0. Having e.g.issubclass(bidict, frozenbidict) == True
was confusing, so this change restoresissubclass(bidict, frozenbidict) == False
.See the updated Bidict Types Diagram and Polymorphism documentation.
Rename:
bidict.BidictBase.fwdm
→._fwdm
bidict.BidictBase.invm
→._invm
bidict.BidictBase.fwd_cls
→._fwdm_cls
bidict.BidictBase.inv_cls
→._invm_cls
bidict.BidictBase.isinv
→._isinv
Though overriding
_fwdm_cls
and_invm_cls
remains supported (see Extending bidict), this is not a common enough use case to warrant public names. Most users do not need to know or care about any of these.The
RAISE
,OVERWRITE
, andIGNORE
duplication policies are no longer available as attributes ofDuplicationPolicy
, and can now only be accessed as attributes of thebidict
module namespace, which was the canonical way to refer to them anyway. It is now no longer possible to create an infinite chain likeDuplicationPolicy.RAISE.RAISE.RAISE...
Make
bidict.pairs()
andbidict.inverted()
no longer importable frombidict.util
, and now only importable from the top-levelbidict
module. (bidict.util
was renamedbidict._util
.)Pickling ordered bidicts now requires at least version 2 of the pickle protocol. If you are using Python 3,
pickle.DEFAULT_PROTOCOL
is 3 anyway, so this will not affect you. However if you are using in Python 2,DEFAULT_PROTOCOL
is 0, so you must now explicitly specify the version in yourpickle.dumps()
calls, e.g.pickle.dumps(ob, 2)
.
0.14.2 (2017-12-06)¶
- Make initializing (or updating an empty bidict) from only another
BidirectionalMapping
more efficient by skipping unnecessary duplication checking. - Fix accidental ignoring of specified
base_type
argument when (un)pickling anamedbidict()
. - Fix incorrect inversion of
some_named_bidict.inv.<fwdname>_for
andsome_named_bidict.inv.<invname>_for
. - Only warn when an unsupported Python version is detected
(e.g. Python < 2.7) rather than raising
AssertionError
.
0.14.1 (2017-11-28)¶
- Fix a bug introduced in 0.14.0 where hashing a
frozenbidict
’s inverse (e.g.f = frozenbidict(); {f.inv: '...'}
) would cause anAttributeError
. - Fix a bug introduced in 0.14.0 for Python 2 users
where attempting to call
viewitems()
would cause aTypeError
. #48
0.14.0 (2017-11-20)¶
- Fix a bug where
bidict
’s default on_dup_kv policy was set toRAISE
, rather than matching whatever on_dup_val policy was in effect as was documented. - Fix a bug that could happen when using Python’s optimization (
-O
) flag that could leave an ordered bidict in an inconsistent state when dealing with duplicated, overwritten keys or values. If you do not use optimizations (specifically, skippingassert
statements), this would not have affected you. - Fix a bug introduced by the optimizations in 0.13.0 that could cause a frozen bidict that compared equal to another mapping to have a different hash value from the other mapping, violating Python’s object model. This would only have affected you if you were inserting a frozen bidict and some other immutable mapping that it compared equal to into the same set or mapping.
- Add
equals_order_sensitive()
. - Reduce the memory usage of ordered bidicts.
- Make copying of ordered bidicts faster.
- Improvements to tests and CI, including:
- Test on Windows
- Test with PyPy3
- Test with CPython 3.7-dev
- Test with optimization flags
- Require pylint to pass
Breaking API Changes¶
This release includes multiple API simplifications and improvements.
Rename:
orderedbidict
→OrderedBidict
frozenorderedbidict
→FrozenOrderedBidict
so that these now match the case of
collections.OrderedDict
.The names of the
bidict
,namedbidict()
, andfrozenbidict
classes have been retained as all-lowercase so that they continue to match the case ofdict
,namedtuple()
, andfrozenset
, respectively.The
ON_DUP_VAL
duplication policy value for on_dup_kv has been removed. UseNone
instead.Merge
frozenbidict
andBidictBase
together and removeBidictBase
.frozenbidict
is now the concrete base class that all other bidict types derive from. See the updated Bidict Types Diagram.Merge
frozenbidict
andFrozenBidictBase
together and removeFrozenBidictBase
. See the updated Bidict Types Diagram.Merge
frozenorderedbidict
andOrderedBidictBase
together into a singleFrozenOrderedBidict
class and removeOrderedBidictBase
.OrderedBidict
now extendsFrozenOrderedBidict
to add mutable behavior. See the updated Bidict Types Diagram.Make
__eq__()
always perform an order-insensitive equality test, even if the other mapping is ordered.Previously,
__eq__()
was only order-sensitive for otherOrderedBidictBase
subclasses, and order-insensitive otherwise.Use the new
equals_order_sensitive()
method for order-sensitive equality comparison.orderedbidict._should_compare_order_sensitive()
has been removed.frozenorderedbidict._HASH_NITEMS_MAX
has been removed. Since its hash value must be computed from all contained items (so that hash results are consistent with equality comparisons against unordered mappings), the number of items that influence the hash value should not be limitable.frozenbidict._USE_ITEMSVIEW_HASH
has been removed, andfrozenbidict.compute_hash()
now usescollections.ItemsView._hash()
to compute the hash always, not just when running on PyPy.Override
frozenbidict.compute_hash()
to returnhash(frozenset(iteritems(self)))
if you prefer the old default behavior on CPython, which takes linear rather than constant space, but which uses thefrozenset_hash
routine (implemented insetobject.c
) rather than the pure PythonItemsView._hash()
routine.loosebidict
andlooseorderedbidict
have been removed. A simple recipe to implement equivalents yourself is now given in Extending bidict.Rename
FrozenBidictBase._compute_hash()
→frozenbidict.compute_hash()
.Rename
DuplicationBehavior
→DuplicationPolicy
.Rename:
BidictBase._fwd_class
→.fwd_cls
BidictBase._inv_class
→.inv_cls
BidictBase._on_dup_key
→on_dup_key
BidictBase._on_dup_val
→on_dup_val
BidictBase._on_dup_kv
→on_dup_kv
0.13.1 (2017-03-15)¶
- Fix regression introduced by the new
__subclasshook__()
functionality in 0.13.0 so thatissubclass(OldStyleClass, BidirectionalMapping)
once again works with old-style classes, returningFalse
rather than raisingAttributeError
#41
0.13.0 (2017-01-19)¶
Support Python 3.6.
(Earlier versions of bidict should work fine on 3.6, but it is officially supported starting in this version.)
BidirectionalMapping
has been refactored into an abstract base class, following the waycollections.abc.Mapping
works. The concrete method implementations it used to provide have been moved into a newBidictBase
subclass.BidirectionalMapping
now also implements__subclasshook__()
, so any class that provides a conforming set of attributes (enumerated in_subclsattrs
) will be considered aBidirectionalMapping
subclass automatically.OrderedBidirectionalMapping
has been renamed toOrderedBidictBase
, to better reflect its function. (It is not an ABC.)A new
FrozenBidictBase
class has been factored out offrozenbidict
andfrozenorderedbidict
. This implements common behavior such as caching the result of__hash__
after the first call.The hash implementations of
frozenbidict
andfrozenorderedbidict
. have been reworked to improve performance and flexibility.frozenorderedbidict
’s hash implementation is now order-sensitive.See
frozenbidict._compute_hash()
andfrozenorderedbidict._compute_hash
for more documentation of the changes, including the newfrozenbidict._USE_ITEMSVIEW_HASH
andfrozenorderedbidict._HASH_NITEMS_MAX
attributes. If you have an interesting use case that requires overriding these, or suggestions for an alternative implementation, please share your feedback.Add
_fwd_class
and_inv_class
attributes representing the backingMapping
types used internally to store the forward and inverse dictionaries, respectively.This allows creating custom bidict types with extended functionality simply by overriding these attributes in a subclass.
See the new Extending bidict documentation for examples.
Pass any parameters passed to
popitem()
through to_fwd.popitem
for greater extensibility.More concise repr strings for empty bidicts.
e.g.
bidict()
rather thanbidict({})
andorderedbidict()
rather thanorderedbidict([])
.Add
bidict.compat.PYPY
and remove unusedbidict.compat.izip_longest
.
0.12.0 (2016-07-03)¶
New/renamed exceptions:
KeyDuplicationError
ValueDuplicationError
KeyAndValueDuplicationError
DuplicationError
(base class for the above)
put()
now acceptson_dup_key
,on_dup_val
, andon_dup_kv
keyword args which allow you to override the default policy when the key or value of a given item duplicates any existing item’s. These can take the following values:RAISE
OVERWRITE
IGNORE
on_dup_kv
can also takeON_DUP_VAL
.New
putall()
method provides a bulkput()
API, allowing you to override the default duplication handling policy thatupdate()
uses.update()
now fails clean, so if anupdate()
call raises aDuplicationError
, you can now be sure that none of the given items was inserted.Previously, all of the given items that were processed before the one causing the failure would have been inserted, and no facility was provided to recover which items were inserted and which weren’t, nor to revert any changes made by the failed
update()
call. The new behavior makes it easier to reason about and control the effects of failedupdate()
calls.The new
putall()
method also fails clean.Internally, this is implemented by storing a log of changes made while an update is being processed, and rolling back the changes when one of them is found to cause an error. This required reimplementing
orderedbidict
on top of two dicts and a linked list, rather than two OrderedDicts, sinceOrderedDict
does not expose its backing linked list.orderedbidict.move_to_end()
now works on Python < 3.2 as a result of the neworderedbidict
implementation.Add
bidict.compat.viewkeys
bidict.compat.viewvalues
bidict.compat.iterkeys
bidict.compat.itervalues
bidict.compat.izip
bidict.compat.izip_longest
to complement the existing
bidict.compat.iteritems
andbidict.compat.viewitems
compatibility helpers.More efficient implementations of
bidict.pairs()
,inverted()
, andcopy()
.Implement
__copy__()
for use with thecopy
module.Fix issue preventing a client class from inheriting from
loosebidict
. #34Add benchmarking to tests.
Drop official support for CPython 3.3. (It may continue to work, but is no longer being tested.)
Breaking API Changes¶
Rename
KeyExistsException
→KeyDuplicationError
andValueExistsException
→ValueDuplicationError
.When overwriting the key of an existing value in an
orderedbidict
, the position of the existing item is now preserved, overwriting the key of the existing item in place, rather than moving the item to the end. This now matches the behavior of overwriting the value of an existing key, which has always preserved the position of the existing item. (If inserting an item whose key duplicates that of one existing item and whose value duplicates that of another, the existing item whose value is duplicated is still dropped, and the existing item whose key is duplicated still gets its value overwritten in place, as before.)For example:
>>> from bidict import orderedbidict >>> o = orderedbidict([(0, 1), (2, 3)]) >>> o.forceput(4, 1)
previously would have resulted in:
>>> o orderedbidict([(2, 3), (4, 1)])
but now results in:
>>> o orderedbidict([(4, 1), (2, 3)])
0.11.0 (2016-02-05)¶
- Add
orderedbidict
,looseorderedbidict
, andfrozenorderedbidict
. - Add Code of Conduct.
- Drop official support for pypy3. (It still may work but is no longer being tested. Support may be added back once pypy3 has made more progress.)
0.10.0.post1 (2015-12-23)¶
- Minor documentation fixes and improvements.
0.10.0 (2015-12-23)¶
- Remove several features in favor of keeping the API simpler and the code more maintainable.
- In the interest of protecting data safety more proactively, by default bidict now raises an error on attempting to insert a non-unique value, rather than allowing its associated key to be silently overwritten. See discussion in #21.
- New
forceupdate()
method provides a bulkforceput()
operation. - Fix bugs in
pop
andsetdefault
which could leave a bidict in an inconsistent state.
Breaking API Changes¶
- Remove
bidict.__invert__
, and with it, support for the~b
syntax. Useinv
instead. #19 - Remove support for the slice syntax.
Use
b.inv[val]
rather thanb[:val]
. #19 - Remove
bidict.invert
. Useinv
rather than inverting a bidict in place. #20 - Raise
ValueExistsException
when attempting to insert a mapping with a non-unique key. #21 - Rename
collapsingbidict
→loosebidict
now that it suppressesValueExistsException
rather than the less generalCollapseException
. #21 CollapseException
has been subsumed byValueExistsException
. #21put()
now raisesKeyExistsException
when attempting to insert an already-existing key, andValueExistsException
when attempting to insert an already-existing value.
0.9.0.post1 (2015-06-06)¶
- Fix metadata missing in the 0.9.0rc0 release.
0.9.0rc0 (2015-05-30)¶
- Add this changelog, Contributors’ Guide, Gitter chat room, and other community-oriented improvements.
- Adopt Pytest.
- Add property-based tests via hypothesis.
- Other code, tests, and docs improvements.
Breaking API Changes¶
- Move
bidict.iteritems()
andbidict.viewitems()
to newbidict.compat
module. - Move
bidict.inverted
to newbidict.util
module (still available from top-levelbidict
module as well). - Move
bidict.fancy_iteritems()
→bidict.util.pairs()
(also available from top level asbidict.pairs()
). - Rename
bidict.namedbidict()
’sbidict_type
argument →base_type
.
API¶
This page contains auto-generated documentation from the bidict source code.
bidict¶
The bidirectional mapping library for Python.
bidict by example:
>>> from bidict import bidict
>>> element_by_symbol = bidict({'H': 'hydrogen'})
>>> element_by_symbol['H']
'hydrogen'
>>> element_by_symbol.inverse['hydrogen']
'H'
Please see https://github.com/jab/bidict for the most up-to-date code and https://bidict.readthedocs.io for the most up-to-date documentation if you are reading this elsewhere.
-
class
bidict.
BidictBase
(*args, **kw)¶ Bases:
bidict.BidirectionalMapping
Base class implementing
BidirectionalMapping
.-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm_cls': typing.Type[typing.MutableMapping[~KT, ~VT]], '_inv': 'BidictBase[VT, KT]', '_inv_cls': '_t.Type[BidictBase[VT, KT]]', '_invm_cls': typing.Type[typing.MutableMapping[~VT, ~KT]], '_repr_delegate': typing.Callable}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool[source]¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getstate__
() → dict[source]¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
(*args, **kw) → None[source]¶ Make a new bidirectional dictionary. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.
-
classmethod
__init_subclass__
(**kw)[source]¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.BidirectionalMapping[~KT, ~VT],)¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
(state: dict) → None[source]¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ['_fwdm', '_invm', '_inv', '_invweak']¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, oldkey: Union[KT, bidict._typing._NONE], oldval: Union[VT, bidict._typing._NONE]) → bool[source]¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult][source]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_fwdm_cls
¶ alias of
builtins.dict
-
_inv
¶
-
_invm
¶
-
_invm_cls
¶ alias of
builtins.dict
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_repr_delegate
¶ alias of
builtins.dict
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None[source]¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None[source]¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult[source]¶
-
equals_order_sensitive
(other: object) → bool[source]¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
exception
bidict.
BidictException
¶ Bases:
Exception
Base class for bidict exceptions.
-
__cause__
¶ exception cause
-
__class__
¶ alias of
builtins.type
-
__context__
¶ exception context
-
__delattr__
¶ Implement delattr(self, name).
-
__dict__
= mappingproxy({'__module__': 'bidict', '__doc__': 'Base class for bidict exceptions.', '__weakref__': <attribute '__weakref__' of 'BidictException' objects>})¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
__new__
()¶ Create and return a new object. See help(type) for accurate signature.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
()¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__suppress_context__
¶
-
__traceback__
¶
-
__weakref__
¶ list of weak references to the object (if defined)
-
args
¶
-
with_traceback
()¶ Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.
-
-
class
bidict.
BidirectionalMapping
¶ Bases:
collections.abc.Mapping
,typing.Generic
Abstract base class (ABC) for bidirectional mapping types.
Extends
collections.abc.Mapping
primarily by adding the (abstract)inverse
property, which implementors ofBidirectionalMapping
should override to return a reference to the inverseBidirectionalMapping
instance.-
__abstractmethods__
= frozenset({'inverse', '__iter__', '__getitem__', '__len__'})¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other)¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key)¶
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
classmethod
__init_subclass__
(*args, **kwargs)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]][source]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
()¶
-
__le__
¶ Return self<=value.
-
__len__
()¶
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (typing.Mapping[~KT, ~VT],)¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__reversed__
= None¶
-
__setattr__
¶ Implement setattr(self, name, value).
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
_abc_impl
= <_abc_data object>¶
-
_is_protocol
= False¶
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inverse
¶ The inverse of this bidirectional mapping instance.
See also
bidict.BidictBase.inverse
,bidict.BidictBase.inv
Raises: NotImplementedError – Meant to be overridden in subclasses.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
values
() → KeysView[VT][source]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
exception
bidict.
DuplicationError
¶ Bases:
bidict.BidictException
Base class for exceptions raised when uniqueness is violated as per the :attr:~bidict.RAISE`
OnDupAction
.-
__cause__
¶ exception cause
-
__class__
¶ alias of
builtins.type
-
__context__
¶ exception context
-
__delattr__
¶ Implement delattr(self, name).
-
__dict__
= mappingproxy({'__module__': 'bidict', '__doc__': 'Base class for exceptions raised when uniqueness is violated\n as per the :attr:~bidict.RAISE` :class:`~bidict.OnDupAction`.\n '})¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
__new__
()¶ Create and return a new object. See help(type) for accurate signature.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
()¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__suppress_context__
¶
-
__traceback__
¶
-
__weakref__
¶ list of weak references to the object (if defined)
-
args
¶
-
with_traceback
()¶ Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.
-
-
class
bidict.
FrozenOrderedBidict
(*args, **kw)¶ Bases:
bidict.OrderedBidictBase
Hashable, immutable, ordered bidict type.
Like a hashable
bidict.OrderedBidict
without the mutating APIs, or like a reversiblebidict.frozenbidict
even on Python < 3.8. (All bidicts are order-preserving when never mutated, so frozenbidict is already order-preserving, but only on Python 3.8+, where dicts are reversible, are all bidicts (including frozenbidict) also reversible.)If you are using Python 3.8+, frozenbidict gives you everything that FrozenOrderedBidict gives you, but with less space overhead.
-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm': bidict.bidict[~KT, bidict._orderedbase._Node], '_fwdm_cls': typing.Type[bidict.MutableBidirectionalMapping[~KT, bidict._orderedbase._Node]], '_invm': bidict.bidict[~VT, bidict._orderedbase._Node], '_invm_cls': typing.Type[bidict.MutableBidirectionalMapping[~VT, bidict._orderedbase._Node]]}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy of this ordered bidict.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key: KT) → VT¶ x.__getitem__(key) ⟺ x[key]
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
() → int¶ The hash of this bidict as determined by its items.
-
__init__
(*args, **kw) → None¶ Make a new ordered bidirectional mapping. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.The order in which items are inserted is remembered, similar to
collections.OrderedDict
.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
() → Iterator[KT]¶ Iterator over the contained keys in insertion order.
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.OrderedBidictBase[~KT, ~VT],)¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__reversed__
() → Iterator[KT]¶ Iterator over the contained keys in reverse insertion order.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ('_hash',)¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, nodeinv: bidict._orderedbase._Node, nodefwd: bidict._orderedbase._Node) → bool¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_hash
¶
-
_init_inv
() → None¶
-
_inv
¶
-
_inv_cls
¶ alias of
FrozenOrderedBidict
-
_invm
¶
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_pop
(key: KT) → VT¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.list
-
_sntl
¶
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult¶
-
copy
() → BT¶ A shallow copy of this ordered bidict.
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → a set-like object providing a view on D's items¶
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
-
exception
bidict.
KeyAndValueDuplicationError
¶ Bases:
bidict.KeyDuplicationError
,bidict.ValueDuplicationError
Raised when a given item’s key and value are not unique.
That is, its key duplicates that of another item, and its value duplicates that of a different other item.
-
__cause__
¶ exception cause
-
__class__
¶ alias of
builtins.type
-
__context__
¶ exception context
-
__delattr__
¶ Implement delattr(self, name).
-
__dict__
= mappingproxy({'__module__': 'bidict', '__doc__': "Raised when a given item's key and value are not unique.\n\n That is, its key duplicates that of another item,\n and its value duplicates that of a different other item.\n "})¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
__new__
()¶ Create and return a new object. See help(type) for accurate signature.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
()¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__suppress_context__
¶
-
__traceback__
¶
-
__weakref__
¶ list of weak references to the object (if defined)
-
args
¶
-
with_traceback
()¶ Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.
-
-
exception
bidict.
KeyDuplicationError
¶ Bases:
bidict.DuplicationError
Raised when a given key is not unique.
-
__cause__
¶ exception cause
-
__class__
¶ alias of
builtins.type
-
__context__
¶ exception context
-
__delattr__
¶ Implement delattr(self, name).
-
__dict__
= mappingproxy({'__module__': 'bidict', '__doc__': 'Raised when a given key is not unique.'})¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
__new__
()¶ Create and return a new object. See help(type) for accurate signature.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
()¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__suppress_context__
¶
-
__traceback__
¶
-
__weakref__
¶ list of weak references to the object (if defined)
-
args
¶
-
with_traceback
()¶ Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.
-
-
class
bidict.
MutableBidict
(*args, **kw)¶ Bases:
bidict.BidictBase
,bidict.MutableBidirectionalMapping
Base class for mutable bidirectional mappings.
-
_MutableMapping__marker
= <object object>¶
-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm_cls': typing.Type[typing.MutableMapping[~KT, ~VT]], '_inv': 'BidictBase[VT, KT]', '_inv_cls': '_t.Type[BidictBase[VT, KT]]', '_invm_cls': typing.Type[typing.MutableMapping[~VT, ~KT]], '_repr_delegate': typing.Callable}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key: KT) → VT¶ x.__getitem__(key) ⟺ x[key]
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
(*args, **kw) → None¶ Make a new bidirectional dictionary. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
() → Iterator[KT]¶ Iterator over the contained keys.
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.BidictBase[~KT, ~VT], bidict.MutableBidirectionalMapping[~KT, ~VT])¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__reversed__
() → Iterator[KT]¶ Iterator over the contained keys in reverse order.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setitem__
(key: KT, val: VT) → None[source]¶ Set the value for key to val.
If key is already associated with val, this is a no-op.
If key is already associated with a different value, the old value will be replaced with val, as with dict’s
__setitem__()
.If val is already associated with a different key, an exception is raised to protect against accidental removal of the key that’s currently associated with val.
Use
put()
instead if you want to specify different behavior in the case that the provided key or value duplicates an existing one. Or useforceput()
to unconditionally associate key with val, replacing any existing items as necessary to preserve uniqueness.Raises: - bidict.ValueDuplicationError – if val duplicates that of an existing item.
- bidict.KeyAndValueDuplicationError – if key duplicates the key of an existing item and val duplicates the value of a different existing item.
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, oldkey: Union[KT, bidict._typing._NONE], oldval: Union[VT, bidict._typing._NONE]) → bool¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_fwdm_cls
¶ alias of
builtins.dict
-
_init_inv
() → None¶
-
_inv
¶
-
_inv_cls
¶ alias of
MutableBidict
-
_invm
¶
-
_invm_cls
¶ alias of
builtins.dict
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_pop
(key: KT) → VT¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.dict
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult¶
-
copy
() → BT¶ A shallow copy.
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
forceput
(key: KT, val: VT) → None[source]¶ Associate key with val unconditionally.
Replace any existing mappings containing key key or value val as necessary to preserve uniqueness.
-
forceupdate
(*args, **kw) → None[source]¶ Like a bulk
forceput()
.
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
pop
(key: KT, default: Union[VT, DT] = <_NONE>) → Union[VT, DT][source]¶ x.pop(k[, d]) → v
Remove specified key and return the corresponding value.
Raises: KeyError – if key is not found and no default is provided.
-
popitem
() → Tuple[KT, VT][source]¶ x.popitem() → (k, v)
Remove and return some item as a (key, value) pair.
Raises: KeyError – if x is empty.
-
put
(key: KT, val: VT, on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None[source]¶ Associate key with val, honoring the
OnDup
given in on_dup.For example, if on_dup is
ON_DUP_RAISE
, then key will be associated with val if and only if key is not already associated with an existing value and val is not already associated with an existing key, otherwise an exception will be raised.If key is already associated with val, this is a no-op.
Raises: - bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
RAISE
. - bidict.ValueDuplicationError – if attempting to insert an item
whose value only duplicates an existing item’s, and on_dup.val is
RAISE
. - bidict.KeyAndValueDuplicationError – if attempting to insert an
item whose key duplicates one existing item’s, and whose value
duplicates another existing item’s, and on_dup.kv is
RAISE
.
- bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
-
putall
(items: Union[Mapping[KT, VT], Iterable[Tuple[KT, VT]]], on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None[source]¶ Like a bulk
put()
.If one of the given items causes an exception to be raised, none of the items is inserted.
-
setdefault
(k[, d]) → D.get(k,d), also set D[k]=d if k not in D¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
class
bidict.
MutableBidirectionalMapping
¶ Bases:
bidict.BidirectionalMapping
,collections.abc.MutableMapping
,typing.Generic
Abstract base class (ABC) for mutable bidirectional mapping types.
-
_MutableMapping__marker
= <object object>¶
-
__abstractmethods__
= frozenset({'inverse', '__getitem__', '__len__', '__setitem__', '__iter__', '__delitem__'})¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__delattr__
¶ Implement delattr(self, name).
-
__delitem__
(key)¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other)¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key)¶
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
classmethod
__init_subclass__
(*args, **kwargs)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
()¶
-
__le__
¶ Return self<=value.
-
__len__
()¶
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.BidirectionalMapping[~KT, ~VT], typing.MutableMapping[~KT, ~VT])¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__reversed__
= None¶
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setitem__
(key, value)¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
_abc_impl
= <_abc_data object>¶
-
_is_protocol
= False¶
-
clear
() → None. Remove all items from D.¶
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inverse
¶ The inverse of this bidirectional mapping instance.
See also
bidict.BidictBase.inverse
,bidict.BidictBase.inv
Raises: NotImplementedError – Meant to be overridden in subclasses.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
pop
(k[, d]) → v, remove specified key and return the corresponding value.¶ If key is not found, d is returned if given, otherwise KeyError is raised.
-
popitem
() → (k, v), remove and return some (key, value) pair¶ as a 2-tuple; but raise KeyError if D is empty.
-
setdefault
(k[, d]) → D.get(k,d), also set D[k]=d if k not in D¶
-
update
([E, ]**F) → None. Update D from mapping/iterable E and F.¶ If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
class
bidict.
OnDup
¶ Bases:
bidict._dup._OnDup
A 3-tuple of
OnDupAction
s specifying how to handle the 3 kinds of duplication.See also Values Must Be Unique
If kv is not specified, val will be used for kv.
-
__add__
¶ Return self+value.
-
__class__
¶ alias of
builtins.type
-
__contains__
¶ Return key in self.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
¶ Return self[key].
-
__getnewargs__
()¶ Return self as a plain tuple. Used by copy and pickle.
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__iter__
¶ Implement iter(self).
-
__le__
¶ Return self<=value.
-
__len__
¶ Return len(self).
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__mul__
¶ Return self*value.
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, key: bidict.OnDupAction = <DROP_OLD>, val: bidict.OnDupAction = <RAISE>, kv: bidict.OnDupAction = <RAISE>) → bidict.OnDup[source]¶ Override to provide user-friendly default values.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
()¶ Return a nicely formatted representation string
-
__rmul__
¶ Return value*self.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
_asdict
()¶ Return a new dict which maps field names to their values.
-
_field_defaults
= {}¶
-
_fields
= ('key', 'val', 'kv')¶
-
_fields_defaults
= {}¶
-
classmethod
_make
(iterable)¶ Make a new _OnDup object from a sequence or iterable
-
_replace
(**kwds)¶ Return a new _OnDup object replacing specified fields with new values
-
count
()¶ Return number of occurrences of value.
-
index
()¶ Return first index of value.
Raises ValueError if the value is not present.
-
key
¶ Alias for field number 0
-
kv
¶ Alias for field number 2
-
val
¶ Alias for field number 1
-
-
class
bidict.
OnDupAction
¶ Bases:
enum.Enum
An action to take to prevent duplication from occurring.
-
DROP_NEW
= 'DROP_NEW'¶
-
DROP_OLD
= 'DROP_OLD'¶
-
RAISE
= 'RAISE'¶
-
__class__
¶ alias of
enum.EnumMeta
-
__members__
= mappingproxy({'RAISE': <RAISE>, 'DROP_OLD': <DROP_OLD>, 'DROP_NEW': <DROP_NEW>})¶
-
__module__
= 'bidict'¶
-
-
class
bidict.
OrderedBidict
(*args, **kw)¶ Bases:
bidict.OrderedBidictBase
,bidict.MutableBidict
Mutable bidict type that maintains items in insertion order.
-
_MutableMapping__marker
= <object object>¶
-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm': bidict.bidict[~KT, bidict._orderedbase._Node], '_fwdm_cls': typing.Type[bidict.MutableBidirectionalMapping[~KT, bidict._orderedbase._Node]], '_invm': bidict.bidict[~VT, bidict._orderedbase._Node], '_invm_cls': typing.Type[bidict.MutableBidirectionalMapping[~VT, bidict._orderedbase._Node]]}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy of this ordered bidict.
-
__delattr__
¶ Implement delattr(self, name).
-
__delitem__
(key: KT) → None¶ x.__delitem__(y) ⟺ del x[y]
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key: KT) → VT¶ x.__getitem__(key) ⟺ x[key]
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
(*args, **kw) → None¶ Make a new ordered bidirectional mapping. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.The order in which items are inserted is remembered, similar to
collections.OrderedDict
.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
() → Iterator[KT]¶ Iterator over the contained keys in insertion order.
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.OrderedBidictBase[~KT, ~VT], bidict.MutableBidict[~KT, ~VT])¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__reversed__
() → Iterator[KT]¶ Iterator over the contained keys in reverse insertion order.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setitem__
(key: KT, val: VT) → None¶ Set the value for key to val.
If key is already associated with val, this is a no-op.
If key is already associated with a different value, the old value will be replaced with val, as with dict’s
__setitem__()
.If val is already associated with a different key, an exception is raised to protect against accidental removal of the key that’s currently associated with val.
Use
put()
instead if you want to specify different behavior in the case that the provided key or value duplicates an existing one. Or useforceput()
to unconditionally associate key with val, replacing any existing items as necessary to preserve uniqueness.Raises: - bidict.ValueDuplicationError – if val duplicates that of an existing item.
- bidict.KeyAndValueDuplicationError – if key duplicates the key of an existing item and val duplicates the value of a different existing item.
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, nodeinv: bidict._orderedbase._Node, nodefwd: bidict._orderedbase._Node) → bool¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_init_inv
() → None¶
-
_inv
¶
-
_inv_cls
¶ alias of
OrderedBidict
-
_invm
¶
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_iter
(*, reverse: bool = False) → Iterator[KT]¶
-
_pop
(key: KT) → VT¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.list
-
_sntl
¶
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult¶
-
copy
() → BT¶ A shallow copy of this ordered bidict.
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
forceput
(key: KT, val: VT) → None¶ Associate key with val unconditionally.
Replace any existing mappings containing key key or value val as necessary to preserve uniqueness.
-
forceupdate
(*args, **kw) → None¶ Like a bulk
forceput()
.
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
move_to_end
(key: KT, last: bool = True) → None[source]¶ Move an existing key to the beginning or end of this ordered bidict.
The item is moved to the end if last is True, else to the beginning.
Raises: KeyError – if the key does not exist
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
pop
(key: KT, default: Union[VT, DT] = <_NONE>) → Union[VT, DT]¶ x.pop(k[, d]) → v
Remove specified key and return the corresponding value.
Raises: KeyError – if key is not found and no default is provided.
-
popitem
(last: bool = True) → Tuple[KT, VT][source]¶ x.popitem() → (k, v)
Remove and return the most recently added item as a (key, value) pair if last is True, else the least recently added item.
Raises: KeyError – if x is empty.
-
put
(key: KT, val: VT, on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None¶ Associate key with val, honoring the
OnDup
given in on_dup.For example, if on_dup is
ON_DUP_RAISE
, then key will be associated with val if and only if key is not already associated with an existing value and val is not already associated with an existing key, otherwise an exception will be raised.If key is already associated with val, this is a no-op.
Raises: - bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
RAISE
. - bidict.ValueDuplicationError – if attempting to insert an item
whose value only duplicates an existing item’s, and on_dup.val is
RAISE
. - bidict.KeyAndValueDuplicationError – if attempting to insert an
item whose key duplicates one existing item’s, and whose value
duplicates another existing item’s, and on_dup.kv is
RAISE
.
- bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
-
putall
(items: Union[Mapping[KT, VT], Iterable[Tuple[KT, VT]]], on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None¶ Like a bulk
put()
.If one of the given items causes an exception to be raised, none of the items is inserted.
-
setdefault
(k[, d]) → D.get(k,d), also set D[k]=d if k not in D¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
class
bidict.
OrderedBidictBase
(*args, **kw)¶ Bases:
bidict.BidictBase
Base class implementing an ordered
BidirectionalMapping
.-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm': bidict.bidict[~KT, bidict._orderedbase._Node], '_fwdm_cls': typing.Type[bidict.MutableBidirectionalMapping[~KT, bidict._orderedbase._Node]], '_invm': bidict.bidict[~VT, bidict._orderedbase._Node], '_invm_cls': typing.Type[bidict.MutableBidirectionalMapping[~VT, bidict._orderedbase._Node]]}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy of this ordered bidict.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
(*args, **kw) → None[source]¶ Make a new ordered bidirectional mapping. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.The order in which items are inserted is remembered, similar to
collections.OrderedDict
.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict.BidictBase[~KT, ~VT],)¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ('_sntl',)¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, nodeinv: bidict._orderedbase._Node, nodefwd: bidict._orderedbase._Node) → bool[source]¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_inv
¶
-
_inv_cls
¶ alias of
OrderedBidictBase
-
_invm
¶
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.list
-
_sntl
¶
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None[source]¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult[source]¶
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → a set-like object providing a view on D's items¶
-
keys
() → a set-like object providing a view on D's keys¶
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
Override the implementation inherited from
Mapping
. Because the values of aBidirectionalMapping
are the keys of its inverse, this returns aKeysView
rather than aValuesView
, which has the advantages of constant-time containment checks and supporting set operations.
-
-
exception
bidict.
ValueDuplicationError
¶ Bases:
bidict.DuplicationError
Raised when a given value is not unique.
-
__cause__
¶ exception cause
-
__class__
¶ alias of
builtins.type
-
__context__
¶ exception context
-
__delattr__
¶ Implement delattr(self, name).
-
__dict__
= mappingproxy({'__module__': 'bidict', '__doc__': 'Raised when a given value is not unique.'})¶
-
__dir__
()¶ Default dir() implementation.
-
__eq__
¶ Return self==value.
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__gt__
¶ Return self>value.
-
__hash__
¶ Return hash(self).
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
__init_subclass__
()¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__le__
¶ Return self<=value.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
__new__
()¶ Create and return a new object. See help(type) for accurate signature.
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__repr__
¶ Return repr(self).
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
()¶
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__str__
¶ Return str(self).
-
__subclasshook__
()¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__suppress_context__
¶
-
__traceback__
¶
-
__weakref__
¶ list of weak references to the object (if defined)
-
args
¶
-
with_traceback
()¶ Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.
-
-
class
bidict.
bidict
(*args, **kw)¶ Bases:
bidict._delegating._DelegatingBidict
,bidict.MutableBidict
Base class for mutable bidirectional mappings.
-
_MutableMapping__marker
= <object object>¶
-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_fwdm_cls': typing.Type[typing.MutableMapping[~KT, ~VT]], '_inv': 'BidictBase[VT, KT]', '_inv_cls': '_t.Type[BidictBase[VT, KT]]', '_invm_cls': typing.Type[typing.MutableMapping[~VT, ~KT]], '_repr_delegate': typing.Callable}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy.
-
__delattr__
¶ Implement delattr(self, name).
-
__delitem__
(key: KT) → None¶ x.__delitem__(y) ⟺ del x[y]
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key: KT) → VT¶ x.__getitem__(key) ⟺ x[key]
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__hash__
= None¶
-
__init__
(*args, **kw) → None¶ Make a new bidirectional dictionary. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
() → Iterator[KT]¶ Iterator over the contained keys.
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict._delegating._DelegatingBidict[~KT, ~VT], bidict.MutableBidict[~KT, ~VT])¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__reversed__
() → Iterator[KT]¶ Iterator over the contained keys in reverse order.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setitem__
(key: KT, val: VT) → None¶ Set the value for key to val.
If key is already associated with val, this is a no-op.
If key is already associated with a different value, the old value will be replaced with val, as with dict’s
__setitem__()
.If val is already associated with a different key, an exception is raised to protect against accidental removal of the key that’s currently associated with val.
Use
put()
instead if you want to specify different behavior in the case that the provided key or value duplicates an existing one. Or useforceput()
to unconditionally associate key with val, replacing any existing items as necessary to preserve uniqueness.Raises: - bidict.ValueDuplicationError – if val duplicates that of an existing item.
- bidict.KeyAndValueDuplicationError – if key duplicates the key of an existing item and val duplicates the value of a different existing item.
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ()¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, oldkey: Union[KT, bidict._typing._NONE], oldval: Union[VT, bidict._typing._NONE]) → bool¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_fwdm_cls
¶ alias of
builtins.dict
-
_init_inv
() → None¶
-
_inv
¶
-
_invm
¶
-
_invm_cls
¶ alias of
builtins.dict
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_pop
(key: KT) → VT¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.dict
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult¶
-
clear
() → None¶ Remove all items.
-
copy
() → BT¶ A shallow copy.
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
forceput
(key: KT, val: VT) → None¶ Associate key with val unconditionally.
Replace any existing mappings containing key key or value val as necessary to preserve uniqueness.
-
forceupdate
(*args, **kw) → None¶ Like a bulk
forceput()
.
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → ItemsView[KT, VT]¶ A set-like object providing a view on the contained items.
-
keys
() → KeysView[KT]¶ A set-like object providing a view on the contained keys.
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
pop
(key: KT, default: Union[VT, DT] = <_NONE>) → Union[VT, DT]¶ x.pop(k[, d]) → v
Remove specified key and return the corresponding value.
Raises: KeyError – if key is not found and no default is provided.
-
popitem
() → Tuple[KT, VT]¶ x.popitem() → (k, v)
Remove and return some item as a (key, value) pair.
Raises: KeyError – if x is empty.
-
put
(key: KT, val: VT, on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None¶ Associate key with val, honoring the
OnDup
given in on_dup.For example, if on_dup is
ON_DUP_RAISE
, then key will be associated with val if and only if key is not already associated with an existing value and val is not already associated with an existing key, otherwise an exception will be raised.If key is already associated with val, this is a no-op.
Raises: - bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
RAISE
. - bidict.ValueDuplicationError – if attempting to insert an item
whose value only duplicates an existing item’s, and on_dup.val is
RAISE
. - bidict.KeyAndValueDuplicationError – if attempting to insert an
item whose key duplicates one existing item’s, and whose value
duplicates another existing item’s, and on_dup.kv is
RAISE
.
- bidict.KeyDuplicationError – if attempting to insert an item
whose key only duplicates an existing item’s, and on_dup.key is
-
putall
(items: Union[Mapping[KT, VT], Iterable[Tuple[KT, VT]]], on_dup: bidict.OnDup = OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)) → None¶ Like a bulk
put()
.If one of the given items causes an exception to be raised, none of the items is inserted.
-
setdefault
(k[, d]) → D.get(k,d), also set D[k]=d if k not in D¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
-
-
class
bidict.
frozenbidict
(*args, **kw)¶ Bases:
bidict._delegating._DelegatingBidict
Immutable, hashable bidict type.
-
__abstractmethods__
= frozenset()¶
-
__annotations__
= {'_hash': <class 'int'>}¶
-
__class__
¶ alias of
abc.ABCMeta
-
classmethod
__class_getitem__
(params)¶
-
__contains__
(key)¶
-
__copy__
() → BT¶ A shallow copy.
-
__delattr__
¶ Implement delattr(self, name).
-
__dir__
()¶ Default dir() implementation.
-
__eq__
(other: object) → bool¶ x.__eq__(other) ⟺ x == other
Equivalent to dict(x.items()) == dict(other.items()) but more efficient.
Note that
bidict's __eq__()
implementation is inherited by subclasses, in particular by the ordered bidict subclasses, so even with ordered bidicts, == comparison is order-insensitive.See also
bidict.FrozenOrderedBidict.equals_order_sensitive()
-
__format__
()¶ Default object formatter.
-
__ge__
¶ Return self>=value.
-
__getattribute__
¶ Return getattr(self, name).
-
__getitem__
(key: KT) → VT¶ x.__getitem__(key) ⟺ x[key]
-
__getstate__
() → dict¶ Needed to enable pickling due to use of
__slots__
and weakrefs.See also
object.__getstate__()
-
__gt__
¶ Return self>value.
-
__init__
(*args, **kw) → None¶ Make a new bidirectional dictionary. The signature behaves like that of
dict
. Items passed in are added in the order they are passed, respecting theon_dup
class attribute in the process.
-
classmethod
__init_subclass__
(**kw)¶ This method is called when a class is subclassed.
The default implementation does nothing. It may be overridden to extend subclasses.
-
__inverted__
() → Iterator[Tuple[VT, KT]]¶ Get an iterator over the items in
inverse
.This is functionally equivalent to iterating over the items in the forward mapping and inverting each one on the fly, but this provides a more efficient implementation: Assuming the already-inverted items are stored in
inverse
, just return an iterator over them directly.Providing this default implementation enables external functions, particularly
inverted()
, to use this optimized implementation when available, instead of having to invert on the fly.See also
bidict.inverted()
-
__iter__
() → Iterator[KT]¶ Iterator over the contained keys.
-
__le__
¶ Return self<=value.
-
__len__
() → int¶ The number of contained items.
-
__lt__
¶ Return self<value.
-
__module__
= 'bidict'¶
-
__ne__
¶ Return self!=value.
-
static
__new__
(cls, *args, **kwds)¶ Create and return a new object. See help(type) for accurate signature.
-
__orig_bases__
= (bidict._delegating._DelegatingBidict[~KT, ~VT],)¶
-
__parameters__
= (~KT, ~VT)¶
-
__reduce__
()¶ Helper for pickle.
-
__reduce_ex__
()¶ Helper for pickle.
-
__reversed__
() → Iterator[KT]¶ Iterator over the contained keys in reverse order.
-
__setattr__
¶ Implement setattr(self, name, value).
-
__setstate__
(state: dict) → None¶ Implemented because use of
__slots__
would prevent unpickling otherwise.See also
object.__setstate__()
-
__sizeof__
()¶ Size of object in memory, in bytes.
-
__slots__
= ('_hash',)¶
-
__str__
¶ Return str(self).
-
classmethod
__subclasshook__
(C)¶ Abstract classes can override this to customize issubclass().
This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).
-
__weakref__
¶ list of weak references to the object (if defined)
-
_abc_impl
= <_abc_data object>¶
-
static
_already_have
(key: KT, val: VT, oldkey: Union[KT, bidict._typing._NONE], oldval: Union[VT, bidict._typing._NONE]) → bool¶
-
_dedup_item
(key: KT, val: VT, on_dup: bidict.OnDup) → Optional[bidict._base._DedupResult]¶ Check key and val for any duplication in self.
Handle any duplication as per the passed in on_dup.
(key, val) already present is construed as a no-op, not a duplication.
If duplication is found and the corresponding
OnDupAction
isDROP_NEW
, return None.If duplication is found and the corresponding
OnDupAction
isRAISE
, raise the appropriate error.If duplication is found and the corresponding
OnDupAction
isDROP_OLD
, or if no duplication is found, return the_DedupResult
(isdupkey, isdupval, oldkey, oldval).
-
_fwdm
¶
-
_fwdm_cls
¶ alias of
builtins.dict
-
_hash
¶
-
_init_inv
() → None¶
-
_inv
¶
-
_inv_cls
¶ alias of
frozenbidict
-
_invm
¶
-
_invm_cls
¶ alias of
builtins.dict
-
_invweak
¶
-
_is_protocol
= False¶
-
_isinv
¶
-
_pop
(key: KT) → VT¶
-
_put
(key: KT, val: VT, on_dup: bidict.OnDup) → None¶
-
_repr_delegate
¶ alias of
builtins.dict
-
_undo_write
(dedup_result: bidict._base._DedupResult, write_result: bidict._base._WriteResult) → None¶
-
_update
(init: bool, on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_no_dup_check
(other: bidict.BidirectionalMapping[~KT, ~VT][KT, VT]) → None¶
-
_update_no_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶
-
_update_with_rollback
(on_dup: bidict.OnDup, *args, **kw) → None¶ Update, rolling back on failure.
-
_write_item
(key: KT, val: VT, dedup_result: bidict._base._DedupResult) → bidict._base._WriteResult¶
-
copy
() → BT¶ A shallow copy.
-
equals_order_sensitive
(other: object) → bool¶ Order-sensitive equality check.
See also __eq__() is order-insensitive
-
get
(k[, d]) → D[k] if k in D, else d. d defaults to None.¶
-
inv
¶ The inverse of this bidict.
-
inverse
¶ The inverse of this bidict.
-
items
() → ItemsView[KT, VT]¶ A set-like object providing a view on the contained items.
-
keys
() → KeysView[KT]¶ A set-like object providing a view on the contained keys.
-
on_dup
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶
-
values
() → KeysView[VT]¶ A set-like object providing a view on the contained values.
-
-
bidict.
inverted
(arg: Union[Mapping[KT, VT], Iterable[Tuple[KT, VT]]]) → Iterable[Tuple[VT, KT]]¶ Yield the inverse items of the provided object.
If arg has a
callable()
__inverted__
attribute, return the result of calling it.Otherwise, return an iterator over the items in arg, inverting each item on the fly.
-
bidict.
namedbidict
(typename: str, keyname: str, valname: str, *, base_type: Type[bidict.BidirectionalMapping[~KT, ~VT][KT, VT]] = <class 'bidict.bidict'>) → Type[bidict.BidirectionalMapping[~KT, ~VT][KT, VT]]¶ Create a new subclass of base_type with custom accessors.
Like
collections.namedtuple()
for bidicts.The new class’s
__name__
and__qualname__
will be set to typename, and its__module__
will be set to the caller’s module.Instances of the new class will provide access to their
inverse
instances via the custom keyname_for property, and access to themselves via the custom valname_for property.See also the namedbidict usage documentation
Raises: - ValueError – if any of the typename, keyname, or valname strings is not a valid Python identifier, or if keyname == valname.
- TypeError – if base_type is not a
BidirectionalMapping
subclass that provides_isinv
and__getstate__()
attributes. (AnyBidictBase
subclass can be passed in, including all the concrete bidict types pictured in the Bidict Types Diagram.
-
bidict.
RAISE
= <RAISE>¶ An action to take to prevent duplication from occurring.
-
bidict.
DROP_OLD
= <DROP_OLD>¶ An action to take to prevent duplication from occurring.
-
bidict.
DROP_NEW
= <DROP_NEW>¶ An action to take to prevent duplication from occurring.
-
bidict.
ON_DUP_DEFAULT
= OnDup(key=<DROP_OLD>, val=<RAISE>, kv=<RAISE>)¶ A 3-tuple of
OnDupAction
s specifying how to handle the 3 kinds of duplication.See also Values Must Be Unique
If kv is not specified, val will be used for kv.
-
bidict.
ON_DUP_RAISE
= OnDup(key=<RAISE>, val=<RAISE>, kv=<RAISE>)¶ A 3-tuple of
OnDupAction
s specifying how to handle the 3 kinds of duplication.See also Values Must Be Unique
If kv is not specified, val will be used for kv.
-
bidict.
ON_DUP_DROP_OLD
= OnDup(key=<DROP_OLD>, val=<DROP_OLD>, kv=<DROP_OLD>)¶ A 3-tuple of
OnDupAction
s specifying how to handle the 3 kinds of duplication.See also Values Must Be Unique
If kv is not specified, val will be used for kv.
-
bidict._iter.
_iteritems_mapping_or_iterable
(arg: Union[Mapping[KT, VT], Iterable[Tuple[KT, VT]]]) → Iterable[Tuple[KT, VT]][source]¶ Yield the items in arg.
If arg is a
Mapping
, return an iterator over its items. Otherwise return an iterator over arg itself.
-
bidict._iter.
_iteritems_args_kw
(*args, **kw) → Iterable[Tuple[KT, VT]][source]¶ Yield the items from the positional argument (if given) and then any from kw.
Raises: TypeError – if more than one positional argument is given.
-
bidict.
__version__
¶ The version of bidict represented as a string.
Learning from bidict
¶
Below is an outline of some of the more fascinating
and lesser-known Python corners I got to explore further
thanks to working on bidict
.
If you would like to learn more about any of the topics below, you may find reading bidict’s code particularly interesting.
I’ve sought to optimize the code not just for correctness and performance, but also to make for a clear and enjoyable read, illuminating anything that could otherwise be obscure or subtle.
I hope it brings you some of the joy it’s brought me. 😊
Python syntax hacks¶
bidict
used to support
(ab)using a specialized form of Python’s slice syntax
for getting and setting keys by value:
>>> element_by_symbol = bidict(H='hydrogen')
>>> element_by_symbol['H'] # [normal] syntax for the forward mapping
'hydrogen'
>>> element_by_symbol[:'hydrogen'] # [:slice] syntax for the inverse (no longer supported)
'H'
See this code for how this was implemented, and #19 for why this was dropped.
Code structure¶
bidict
s come in every combination of
mutable, immutable, ordered, and unordered types,
implementing Python’s various
relevant
collections
interfaces
as appropriate.
Factoring the code to maximize reuse, modularity, and adherence to SOLID design principles (while not missing any chances for special-case optimizations) has been one of the most fun parts of working on bidict.
To see how this is done, check out this code:
Data structures are amazing¶
Data structures are one of the most fascinating and important building blocks of programming and computer science.
It’s all too easy to lose sight of the magic when having to implement them for computer science courses or job interview questions. Part of this is because many of the most interesting real-world details get left out, and you miss all the value that comes from ongoing, direct practical application.
Bidict shows how fundamental data structures can be implemented in Python for important real-world usage, with practical concerns at top of mind. Come to catch sight of a real, live, industrial-strength linked list in the wild. Stay for the rare, exotic bidirectional mapping breeds you’ll rarely see at home. [1]
[1] | To give you a taste: A regular We’ll still need two backing mappings to store the forward and inverse associations. To store the ordering, we use a (circular, doubly-) linked list. This allows us to e.g. delete an item in any position in O(1) time. Interestingly, the nodes of the linked list encode only the ordering of the items; the nodes themselves contain no key or value data. The two backing mappings associate the key and value data with the nodes, providing the final pieces of the puzzle. Can we use dicts for the backing mappings, as we did for the unordered bidict? It turns out that dicts aren’t enough—the backing mappings must actually be (unordered) bidicts themselves! |
Check out _orderedbase.py to see this in action.
Property-based testing is revolutionary¶
When your automated tests run, are they only checking the test cases you happened to hard-code into your test suite? How do you know these test cases aren’t missing some important edge cases?
With property-based testing, you describe the types of test case inputs your functions accept, along with the properties that should hold for all inputs. Rather than having to think up your test case inputs manually and hard-code them into your test suite, they get generated for you dynamically, in much greater quantity and edge case-exercising diversity than you could come up with by hand. This dramatically increases test coverage and confidence that your code is correct.
Bidict never would have survived so many refactorings with so few bugs if it weren’t for property-based testing, enabled by the amazing Hypothesis library. It’s game-changing.
Check out bidict’s property-based tests to see this in action.
Python surprises, gotchas, regrets¶
See nan as a Key.
What should happen when checking equality of several ordered mappings that contain the same items but in a different order? What about when comparing with an unordered mapping?
Check out what Python’s
collections.OrderedDict
does, and the surprising results:>>> from collections import OrderedDict >>> d = dict([(0, 1), (2, 3)]) >>> od = OrderedDict([(0, 1), (2, 3)]) >>> od2 = OrderedDict([(2, 3), (0, 1)]) >>> d == od True >>> d == od2 True >>> od == od2 False >>> class MyDict(dict): ... __hash__ = lambda self: 0 ... >>> class MyOrderedDict(OrderedDict): ... __hash__ = lambda self: 0 ... >>> d = MyDict([(0, 1), (2, 3)]) >>> od = MyOrderedDict([(0, 1), (2, 3)]) >>> od2 = MyOrderedDict([(2, 3), (0, 1)]) >>> len({d, od, od2}) 1 >>> len({od, od2, d}) 2
According to Raymond Hettinger (Python core developer responsible for much of Python’s collections), this design was a mistake (e.g. it violates the Liskov substitution principle and the transitive property of equality), but it’s too late now to fix.
Fortunately, it wasn’t too late for bidict to learn from this. Hence __eq__() is order-insensitive even for ordered bidicts. For an order-sensitive equality check, bidict provides the separate
equals_order_sensitive()
method.If you define a custom
__eq__()
on a class, it will not be used for!=
comparisons on Python 2 automatically; you must explicitly add an__ne__()
implementation that calls your__eq__()
implementation. If you don’t,object.__ne__()
will be used instead, which behaves likeis not
. Python 3 thankfully fixes this.
Better memory usage through __slots__
¶
Using __slots__ dramatically reduces memory usage in CPython and speeds up attribute access to boot. Must be careful with pickling and weakrefs though! See BidictBase.__getstate__().
Better memory usage through weakref
¶
A bidict
and its inverse use weakref
to avoid creating a strong reference cycle,
so that when you release your last reference to a bidict,
its memory is reclaimed immediately in CPython
rather than having to wait for the next garbage collection.
See bidict Avoids Reference Cycles.
The (doubly) linked lists that back ordered bidicts also use weakrefs to avoid creating strong reference cycles.
Subclassing namedtuple()
classes¶
To get the performance benefits, intrinsic sortability, etc.
of namedtuple()
while customizing behavior, state, API, etc.,
you can subclass a namedtuple()
class.
Just make sure to include __slots__ = ()
,
or you’ll lose a lot of the performance benefits.
Here’s an example:
>>> from collections import namedtuple
>>> from itertools import count
>>> class Node(namedtuple('_Node', 'cost tiebreaker data parent depth')):
... """Represent nodes in a graph traversal. Suitable for use with e.g. heapq."""
...
... __slots__ = ()
... _counter = count() # break ties between equal-cost nodes, avoid comparing data
...
... # Give call sites a cleaner API for creating new Nodes
... def __new__(cls, cost, data, parent=None):
... tiebreaker = next(cls._counter)
... depth = parent.depth + 1 if parent else 0
... return super().__new__(cls, cost, tiebreaker, data, parent, depth)
...
... def __repr__(self):
... return 'Node(cost={cost}, data={data!r})'.format(**self._asdict())
>>> start = Node(cost=0, data='foo')
>>> child = Node(cost=5, data='bar', parent=start)
>>> child
Node(cost=5, data='bar')
>>> child.parent
Node(cost=0, data='foo')
>>> child.depth
1
namedtuple()
-style dynamic class generation¶
See the implementation
of namedbidict()
.
API Design¶
How to deeply integrate with Python’s collections
and other built-in APIs?
- Beyond implementing
collections.abc.Mapping
, bidicts implement additional APIs thatdict
andOrderedDict
implement (e.g.setdefault()
,popitem()
, etc.).- When creating a new API, making it familiar, memorable, and intuitive is hugely important to a good user experience.
- Thanks to
Hashable
’s implementingabc.ABCMeta.__subclasshook__()
, any class that implements the required methods of theHashable
interface (namely,__hash__()
) makes it a virtual subclass already, no need to explicitly extend. I.e. As long asFoo
implements a__hash__()
method,issubclass(Foo, Hashable)
will always be True, no need to explicitly subclass viaclass Foo(Hashable): ...
- How to make your own open ABC like
Hashable
?- Override
__subclasshook__()
to check for the interface you require. SeeBidirectionalMapping
’s old (correct) implementation (this was later removed due to lack of use and maintenance cost when it was discovered that a bug was introduced in v0.15.0). - Interesting consequence of the
__subclasshook__()
design: the “subclass” relation becomes intransitive. e.g.object
is a subclass ofHashable
,list
is a subclass ofobject
, butlist
is not a subclass ofHashable
.
- Override
- What if you needed to derive from a second metaclass? Be careful to avoid “TypeError: metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases”. See the great write-up in https://blog.ionelmc.ro/2015/02/09/understanding-python-metaclasses/.
collections.abc.Mapping
andcollections.abc.MutableMapping
don’t implement__subclasshook__()
, so you must either explicitly subclass them (in which case you inherit their concrete method implementations) or useabc.ABCMeta.register()
(to register as a virtual subclass without inheriting any of the implementation).- Notice that Python provides
collections.abc.Reversible
but nocollections.abc.Ordered
orcollections.abc.OrderedMapping
. This was proposed in bpo-28912 but rejected. Would have been useful for bidict’s__repr__()
implementation (see_base.py
), and potentially for interop with other ordered mapping implementations such as SortedDict.
How to make APIs Pythonic?
See the Zen of Python.
“Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.”
Manifested in bidict’s default
on_dup
class attribute (seeON_DUP_DEFAULT
).“Readability counts.”
“There should be one – and preferably only one – obvious way to do it.”
An early version of bidict allowed using the
~
operator to access.inverse
and a special slice syntax likeb[:val]
to look up a key by value, but these were removed in preference to the more obvious and readable.inverse
-based spellings.
Python’s data model¶
What happens when you implement a custom
__eq__()
? e.g. What’s the difference betweena == b
andb == a
when onlya
is an instance of your class? See the great write-up in https://eev.ee/blog/2012/03/24/python-faq-equality/ for the answer.If an instance of your special mapping type is being compared against a mapping of some foreign mapping type that contains the same items, should your
__eq__()
method return true?Bidict says yes, again based on the Liskov substitution principle. Only returning true when the types matched exactly would violate this. And returning
NotImplemented
would cause Python to fall back on using identity comparison, which is not what is being asked for.(Just for fun, suppose you did only return true when the types matched exactly, and suppose your special mapping type were also hashable. Would it be worth having your
__hash__()
method include your type as well as your items? The only point would be to reduce collisions when multiple instances of different types contained the same items and were going to be inserted into the samedict
orset
, since they’d now be unequal but would hash to the same value otherwise.)Making an immutable type hashable (so it can be inserted into
dict
s andset
s): Must implement__hash__()
such thata == b ⇒ hash(a) == hash(b)
. See theobject.__hash__()
andobject.__eq__()
docs, and the implementation offrozenbidict
.Consider
FrozenOrderedBidict
: its__eq__()
is order-insensitive. So all contained items must participate in the hash order-insensitively.Can use collections.abc.Set._hash which provides a pure Python implementation of the same hash algorithm used to hash
frozenset
s. (SinceItemsView
extendsSet
,bidict.frozenbidict.__hash__()
just callsItemsView(self)._hash()
.)- Does this argue for making
collections.abc.Set._hash()
non-private? - Why isn’t the C implementation of this algorithm directly exposed in
CPython? The only way to use it is to call
hash(frozenset(self.items()))
, which wastes memory allocating the ephemeral frozenset, and time copying all the items into it before they’re hashed.
- Does this argue for making
Unlike other attributes, if a class implements
__hash__()
, any subclasses of that class will not inherit it. It’s like Python implicitly adds__hash__ = None
to the body of every class that doesn’t explicitly define__hash__
. So if you do want a subclass to inherit a base class’s__hash__()
implementation, you have to set that manually, e.g. by adding__hash__ = BaseClass.__hash__
in the class body. SeeFrozenOrderedBidict
.This is consistent with the fact that
object
implements__hash__()
, but subclasses ofobject
that override__eq__()
are not hashable by default.
Using
__new__()
to bypass default object initialization, e.g. for bettercopy()
performance. See _base.py.Overriding
object.__getattribute__()
for custom attribute lookup. See SortedBidict Recipes.Using
object.__getstate__()
,object.__setstate__()
, andobject.__reduce__()
to make an object pickleable that otherwise wouldn’t be, due to e.g. using weakrefs, as bidicts do (covered further below).
Portability¶
Python 2 vs. Python 3
As affects bidict, mostly
dict
API changes, but also functions likezip()
,map()
,filter()
, etc.See the
__ne__()
gotcha for Python 2 above.Borrowing methods from other classes:
In Python 2, must grab the
.im_func
/__func__
attribute off the borrowed method to avoid gettingTypeError: unbound method ...() must be called with ... instance as first argument
See the old implementation of
FrozenOrderedBidict
.
CPython vs. PyPy (and other Python implementations)
- See https://doc.pypy.org/en/latest/cpython_differences.html
- gc / weakref
- Hence
test_bidicts_freed_on_zero_refcount()
in test_properties.py is skipped outside CPython. - primitives’ identities, nan, etc.
Other interesting stuff in the standard library¶
reprlib
andreprlib.recursive_repr()
(but not needed for bidict because there’s no way to insert a bidict into itself)operator.methodcaller()
- See Missing bidicts in the Standard Library
Contributors’ Guide¶
Bug reports, feature requests, patches, and other contributions are warmly welcomed. Contribution should be as easy and friendly as possible. Below are a few guidelines contributors should follow to facilitate the process.
Getting Started¶
- Create a GitHub account if you don’t have one already.
- Search through the issue tracker
to see if an issue or pull request has already been created for what you’re interested in.
If so, feel free to add comments to it or just hit the “subscribe” button to follow progress.
If not, you can join the chat room to discuss there,
or go ahead and create a new issue:
- Clearly describe the issue giving as much relevant context as possible.
- If it is a bug, include reproduction steps, all known environments in which the bug is exhibited, and ideally a failing test case.
- If you would like to contribute a patch, make sure you’ve created your own fork and have cloned it to your computer.
Making Changes¶
Before making changes, please (create a virtualenv and) install the extra packages required for development:
pip install -r requirements/dev.txt
We use EditorConfig and pre-commit to help achieve uniform style and quality standards across a diversity of development environments.
pre-commit gets installed when you run the command above and ensures that various code checks are run before every commit (look in
.pre-commit-config.yaml
to see which hooks are run). Ensure the configured hooks are installed by runningpre-commit install --install-hooks
.EditorConfig allows us to provide a single
.editorconfig
file to configure settings like indentation consistently across a variety of supported editors. See https://editorconfig.org/#download to install the plugin for your editor.Create a topic branch off of main for your changes:
git checkout -b <topic> main
Make commits of logical units.
Match the existing code style and quality standards. If you’re adding a feature, include accompanying tests and documentation demonstrating its correctness and usage.
Run the tests locally with tox to make sure they pass for all supported Python versions (see
envlist
intox.ini
for the complete list). If you do not have all the referenced Python versions available locally, you can also push the changes on your branch to GitHub to automatically trigger a new GitHub Actions build, which should run the tests for all supported Python versions.Create a concise but comprehensive commit message in the following style:
Include an example commit message in CONTRIBUTING guide #9999 Without this patch the CONTRIBUTING guide would contain no examples of a model commit message. This is a problem because the contributor is left to imagine what the commit message should look like and may not get it right. This patch fixes the problem by providing a concrete example. The first line is an imperative statement summarizing the changes with an issue number from the tracker. The body describes the behavior without the patch, why it's a problem, and how the patch fixes the problem.
Submitting Changes¶
- Push your changes to a topic branch in your fork of the repository:
git push --set-upstream origin <topic>
- Submit a pull request providing any additional relevant details necessary.
- Acknowledgment should typically be fast but please allow 1-2 weeks for a full response / code review.
- The code review process often involves some back-and-forth to get everything right before merging. This is typical of quality software projects that accept patches.
- All communication should be supportive and appreciative of good faith efforts to contribute, creating a welcoming and inclusive community. Expect nothing less of any project.
Sponsoring¶
Bidict is the product of thousands of hours of my unpaid work over the 12+ years I’ve been maintaining it.
If bidict has helped you accomplish your work, especially work you’ve been paid for, it’s easy to sponsor me through GitHub.
Choose a tier and GitHub handles everything else. The sponsorship just goes on your regular GitHub bill; there’s nothing extra to do. You can also sponsor me through Gumroad or PayPal.
Read more about companies supporting open source developers.
Code of Conduct¶
All participation in this project should respect the Code of Conduct. [2]
By participating, you are expected to honor this code.
[1] | https://bidict.readthedocs.io/#notice-of-usage |
[2] | CODE_OF_CONDUCT.rst | https://bidict.readthedocs.io/code-of-conduct.html |
Code of Conduct¶
Our Pledge¶
In the interest of fostering an open and welcoming environment, we as contributors and maintainers pledge to making participation in our project and our community a harassment-free experience for everyone, regardless of age, body size, disability, ethnicity, gender identity and expression, level of experience, nationality, personal appearance, race, religion, or sexual identity and orientation.
Our Standards¶
Examples of behavior that contributes to creating a positive environment include:
- Using welcoming and inclusive language
- Being respectful of differing viewpoints and experiences
- Gracefully accepting constructive criticism
- Focusing on what is best for the community
- Showing empathy towards other community members
Examples of unacceptable behavior by participants include:
- The use of sexualized language or imagery and unwelcome sexual attention or advances
- Trolling, insulting/derogatory comments, and personal or political attacks
- Public or private harassment
- Publishing others’ private information, such as a physical or electronic address, without explicit permission
- Other conduct which could reasonably be considered inappropriate in a professional setting
Our Responsibilities¶
Project maintainers are responsible for clarifying the standards of acceptable behavior and are expected to take appropriate and fair corrective action in response to any instances of unacceptable behavior.
Project maintainers have the right and responsibility to remove, edit, or reject comments, commits, code, wiki edits, issues, and other contributions that are not aligned to this Code of Conduct, or to ban temporarily or permanently any contributor for other behaviors that they deem inappropriate, threatening, offensive, or harmful.
Scope¶
This Code of Conduct applies both within project spaces and in public spaces when an individual is representing the project or its community. Examples of representing a project or community include using an official project e-mail address, posting via an official social media account, or acting as an appointed representative at an online or offline event. Representation of a project may be further defined and clarified by project maintainers.
Enforcement¶
Instances of abusive, harassing, or otherwise unacceptable behavior may be reported by contacting the project team at <jabronson@gmail.com>. All complaints will be reviewed and investigated and will result in a response that is deemed necessary and appropriate to the circumstances. The project team is obligated to maintain confidentiality with regard to the reporter of an incident. Further details of specific enforcement policies may be posted separately.
Project maintainers who do not follow or enforce the Code of Conduct in good faith may face temporary or permanent repercussions as determined by other members of the project’s leadership.
Attribution¶
This Code of Conduct is adapted from the Contributor Covenant, version 1.4, available at https://www.contributor-covenant.org/version/1/4.
Thanks¶
Bidict has benefited from the assistance of many people and projects.
People¶
- Gregory Ewing for the name.
- Terry Reedy for suggesting the slice syntax (it was fun while it lasted).
- Raymond Hettinger for suggesting namedbidict and pointing out various caveats.
- Francis Carr for the idea of storing the inverse bidict.
- Adopt Pytest Month 2015 for choosing bidict, Tom Viner for being bidict’s Adopt Pytest helper for the month, and Brianna Laugher for coordinating.
- Daniel Pope for suggestions, code reviews, and design discussion.
- David Turner for code reviews and design discussion.
- Michael Arntzenius for design discussion.
- Jozef Knaperek for the bugfix.
- Igor Nehoroshev for contributing the py.typed marker.
- Bernát Gábor for pyproject.toml support.
- Muhammad Faisal for the CC BY 3.0 icon that bidict’s logo was derived from.
- Richard Sanger, Zeyi Wang, and Amol Sahsrabudhe for reporting bugs.
bidict¶
The bidirectional mapping library for Python.
Status¶
bidict:¶
- has been used for many years by several teams at Google, Venmo, CERN, Bank of America Merrill Lynch, Bloomberg, Two Sigma, and many others
- has carefully designed APIs for safety, simplicity, flexibility, and ergonomics
- is fast, lightweight, and has no runtime dependencies other than Python’s standard library
- integrates natively with Python’s
collections.abc
interfaces - provides type hints for all public APIs
- is implemented in concise, well-factored, pure (PyPy-compatible) Python code that is optimized for running efficiently as well as for reading and learning [1]
- has extensive docs and test coverage (including property-based tests and benchmarks) run continuously on all supported Python versions
Installation¶
pip install bidict
Quick Start¶
>>> from bidict import bidict
>>> element_by_symbol = bidict({'H': 'hydrogen'})
>>> element_by_symbol['H']
'hydrogen'
>>> element_by_symbol.inverse['hydrogen']
'H'
For more usage documentation, head to the Introduction [3] and proceed from there.
Voluntary Community Support¶
Please feel free to leave a message in the bidict chatroom or open a new issue on GitHub for voluntary community support. You can search through existing issues before creating a new one in case your issue has been addressed already.
Enterprise Support¶
Enterprise-level support for bidict can be obtained via the Tidelift subscription.
Notice of Usage¶
If you use bidict, and especially if your usage or your organization is significant in some way, please let me know in any of the following ways:
- star bidict on GitHub
- create an issue
- leave a message in the chat room
- email me
Release Notifications¶
Watch releases on GitHub or libraries.io to be notified when new versions of bidict are released.
Learning from bidict¶
One of the best things about bidict is that it touches a surprising number of interesting Python corners, especially given its small size and scope.
Check out Learning from bidict [1] if you’re interested in learning more.
Contributing¶
bidict is currently a one-person operation maintained on a voluntary basis.
Your help would be most welcome! See the Contributors’ Guide [4] for more information.
Sponsoring¶
Bidict is the product of thousands of hours of my unpaid work over the 12+ years I’ve been maintaining it.
If bidict has helped you accomplish your work, especially work you’ve been paid for, it’s easy to sponsor me through GitHub.
Choose a tier and GitHub handles everything else. The sponsorship just goes on your regular GitHub bill; there’s nothing extra to do. You can also sponsor me through Gumroad or PayPal.
Read more about companies supporting open source developers.
Finding Documentation¶
If you’re viewing this on https://bidict.readthedocs.io, note that multiple versions of the documentation are available, and you can choose a different version using the popup menu at the bottom-right. Please make sure you’re viewing the version of the documentation that corresponds to the version of bidict you’d like to use.
If you’re viewing this on GitHub, PyPI, or some other place that can’t render and link this documentation properly and are seeing broken links, try these alternate links instead:
[1] | (1, 2) docs/learning-from-bidict.rst | https://bidict.readthedocs.io/learning-from-bidict.html |
[2] | CHANGELOG.rst | https://bidict.readthedocs.io/changelog.html |
[3] | (1, 2) docs/intro.rst | https://bidict.readthedocs.io/intro.html |
[4] | docs/contributors-guide.rst | https://bidict.readthedocs.io/contributors-guide.html |
Next: Introduction [3]