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
. 1
- 1
In fact, any
collections.abc.Mapping
that provides aninverse
attribute will be considered a virtual subclass ofbidict.BidirectionalMapping
automatically
, enabling interoperability with external implementations.
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
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 mutable BidirectionalMapping
that preserves the order in which its items are inserted.
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 functionality
modeled after OrderedDict
is 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
>>> from collections import OrderedDict
>>> od = OrderedDict(o2)
>>> o1.equals_order_sensitive(od)
False
Note that this differs from the behavior of
collections.OrderedDict
’s __eq__()
,
by recommendation of Raymond Hettinger (the author) himself.
He later said that making OrderedDict’s __eq__()
intransitive was a mistake.
What if my Python version has order-preserving dicts?¶
In PyPy as well as CPython ≥ 3.6,
dict
preserves insertion order.
If you are using one of these versions of Python,
you may wonder whether you can get away with
using a regular bidict.bidict
in places where you need
an insertion order-preserving bidirectional mapping.
In general the answer is no, particularly if you need to be able to change existing associations in the bidirectional mapping while preserving order correctly.
Consider this example using a regular bidict
with an order-preserving dict
version of Python:
>>> b = bidict([(1, -1), (2, -2), (3, -3)])
>>> b[2] = 'UPDATED'
>>> b
bidict({1: -1, 2: 'UPDATED', 3: -3})
>>> b.inverse # oops:
bidict({-1: 1, -3: 3, 'UPDATED': 2})
When the value associated with the key 2
was changed,
the corresponding item stays in place in the forward mapping,
but moves to the end of the inverse mapping.
Since regular bidict
s
provide no guarantees about order preservation
(which allows for a more efficient implementation),
non-order-preserving behavior
(as in the example above)
is exactly what you get.
If you never mutate a bidict
(or are even using a frozenbidict
)
and you’re running a version of Python
with order-preserving dict
s,
then you’ll find that the order of the items
in your bidict and its inverse happens to be preserved.
However, you won’t get the additional order-specific APIs
(such as
move_to_end()
,
equals_order_sensitive()
, and
__reversed__()
–
indeed the lack of a dict.__reversed__
API
is what stops us from making
FrozenOrderedBidict
an alias of
frozenbidict
on dict-order-preserving Pythons,
as this would mean
FrozenOrderedBidict.__reversed__()
would have to be O(n) in space complexity).
If you need order-preserving behavior guaranteed,
then OrderedBidict
is your best choice.
FrozenOrderedBidict
¶
FrozenOrderedBidict
is an immutable ordered bidict type.
It’s like an OrderedBidict
without the mutating APIs,
or equivalently like an order-preserving
frozenbidict
.
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 'an error'
True
>>> noble['C'] = 'carbon' # mutation fails
Traceback (most recent call last):
...
TypeError: ...
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
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.
One thing you might notice is that there is no
Ordered
or OrderedMapping
ABC.
However, Python 3.6 introduced the collections.abc.Reversible
ABC.
Since being reversible implies having an ordering,
you could check for reversibility instead.
For example:
>>> from collections.abc import Reversible
>>> def is_reversible_mapping(cls):
... return issubclass(cls, Reversible) and issubclass(cls, Mapping)
...
>>> is_reversible_mapping(OrderedBidict)
True
>>> is_reversible_mapping(OrderedDict)
True
For more you can do with bidict
,
check out Extending bidict next.