Efficient both ways mapping in Python with flag values

Question

What is the best data structure to have a both-ways mapping of object, with flag values for each couple, in Python ? For instance, let's imagine I have two pools of men and women I want to match together. I want a datastructure to store de matches so I can access the corresponding man of each woman, the corresponding woman of each man and, let's say, a number representing the value of this couple.

The key feature is that I want to access all of these data with a constant time (about the time of a key-access in a dictionary) without wasting resources for the construction.

If there wasn't for the particularity of the "flag value", a bidict from the library suggested in this post would be absolutely perfect. Indeed, every time I add a couple in my all-stars-couples datastructure, it automatically updates to avoid polygamy :

couples = bidict({ 
    'leonard' : 'penny',
    'howard'  : 'bernadette',
    'sheldon' : 'amy'
})
couples.forceput('stephen', 'amy')
print couples

>> bidict({'stephen': 'amy', 'leonard': 'penny', 'howard': 'bernadette'})

I am now asking for advice on the most efficient and pythonic way to implement a quality feature such that, for instance :

quality('stephen', 'amy')

>> 0.4

couples.forceput('sheldon', 'amy', quality = 1.0)
quality('sheldon', 'amy')

>> 1.0

quality('stephen', 'amy')

>> Raise KeyError

Answer 1

Consider that tuples are hashable. You can create a dict that maps from a couple to whatever data you want, including quality:

quality = dict()
quality[ ('stephen', 'amy') ] = 0.4

Answer 2

Solution 1 : Quick and dirty

Here is a trivial implementation built on top of bidict, done on the suggestions made by adrin and Austin :

class couple ( bidict ) :

    self._flags = {}

    def add ( self, key, val, flag ) :
        try :
            del self._flags[ self._inv[ val ] ]
        except KeyError :
            pass
        self._put(key, val, overwrite_key=True, overwrite_val=True)
        self._flags[ key ] = flag

    def flag ( self, key, val ) :
        if ( self._fwd.get( key ) == val ) :
            return self._flags[ key ]
        else :
            raise KeyError( key, val )

This way, one can obtain the following behaviour :

bbt = couple()
bbt.add( 'stephen', 'amy', 0.4 )
bbt.flag( 'stephen', 'amy' )

>> 0.4

bbt.add( 'sheldon', 'amy', 1.0 )
bbt.flag( 'sheldon', 'amy' )

>> 1.0

bbt.flag( 'stephen', 'amy' )

>> KeyError: ('stephen', 'amy')

Solution 2 : Specific and standalone

Since I finally ended up coding my own structure. It is standalone and can be c/c if needed by anyone passing here :

class FlaggedDoubleMapper :
    """Flagged Double Mapper"""

    def __init__ ( self, keys = [], vals = [], flags = [] ) :
        """Initializes a flagged double mapper with lists of keys, values and
        flags.
        """

        self._flg = {}     # Flags dictionary
        self._fwd = {}     # Forward dictionary
        self._bwd = {}     # Backward dictionary

        for key, val, flag in zip( keys, vals, flags ) :
            self.add( key, val, flag )

    def __repr__ ( self ) :
        """Representation bidict-style."""

        return 'fdm({})'.format( self._fwd )

    def contains ( self, key, val ) :
        """Returns True if and only if self contains the key-val binding."""

        try :
            return ( self._fwd[ key ] == val )
        except KeyError :
            return False

    def add ( self, key, val, flag ) :
        """Adds a flagged binding, overwriting all corresponding bindings."""

        try :
            _val = self._fwd[ key ]
            del self._bwd[ _val ]
        except KeyError :
            pass

        try :
            _key = self._bwd[ val ]
            del self._flg[ _key ]
            del self._fwd[ _key ]
        except KeyError :
            pass

        self._flg[ key ] = flag
        self._fwd[ key ] = val
        self._bwd[ val ] = key

    def remove ( self, key, *args ) :
        """Removes a binding.
         - remove( key ) will send a KeyError( key ) if no binding with key as a
         forward key is found.
         - remove( key, val ) will send a KeyError( key, val ) if no forward
         key-val binding is found.
        """

        try :
            _val = args[0]
            if ( _val != self._fwd[ key ] ) :   # Can raise a KeyError( key )
                raise KeyError( key, _val )
        except IndexError :
            _val = self._fwd[ key ]             # Can raise a KeyError( key )

        del self._flg[ key ]
        del self._fwd[ key ]
        del self._bwd[ _val ]

    def flag ( self, key, *args ) :
        """Returns the flag of a binding.
         - flag( key ) will send a KeyError( key ) if no binding with key as a
         forward key is found.
         - flag( key, val ) will send a KeyError( key, val ) if no forward
         key-val binding is found.
        """

        try :
            _val = args[0]
            if ( _val != self._fwd[ key ] ) :   # Can raise a KeyError( key )
                raise KeyError( key, _val )
        except IndexError :
            pass

        return self._flg[ key ]