How would one implement a bidirectional map in Swift?

Question

I am currently in need of a performant bidirectional map. In Swift, a dictionary can be reversed, however, that will return a tuple of the types it is made of, not a counterpart dictionary.

Is there a library for that or does someone have ideas on how to address this issue?

Thanks

Vest

There is no in-built DS for bimap. But you can build one yourself. This can give you an idea. You can also look at this . – Chaff

@PuneetSharma To be honest, I've thought of something like that, but it's not really a boost in performance, is it? – Saprogenic

There should not be much difference in time complexity of element retrieval or saving elements as maps are pretty fast anyways. The only concern is using extra space for saving forward/reverse maps. But, I dont see how that can be avoided. – Chaff

Here another example of a bimap in swift – Schweiz

Answer 1

With Swift 4 you could easily make your own using a generic struct:

struct BidiMap<F:Hashable,T:Hashable>
{
   private var _forward  : [F:T]? = nil
   private var _backward : [T:F]? = nil

   var forward:[F:T]  
   { 
      mutating get 
      { 
        _forward = _forward ?? [F:T](uniqueKeysWithValues:_backward?.map{($1,$0)} ?? [] ) 
        return _forward!
      }
      set { _forward = newValue; _backward = nil }
   }

   var backward:[T:F]  
   { 
      mutating get 
      { 
        _backward = _backward ?? [T:F](uniqueKeysWithValues:_forward?.map{($1,$0)} ?? [] ) 
        return _backward!
      }
      set { _backward = newValue; _forward = nil }
   }

   init(_ dict:[F:T] = [:])
   { forward = dict  }

   init(_ values:[(F,T)])
   { forward = [F:T](uniqueKeysWithValues:values) }

   subscript(_ key:T) -> F? 
   { mutating get { return backward[key] } set{ backward[key] = newValue } }

   subscript(_ key:F) -> T?
   { mutating get { return forward[key]  } set{ forward[key]  = newValue } }

   subscript(to key:T) -> F? 
   { mutating get { return backward[key] } set{ backward[key] = newValue } }

   subscript(from key:F) -> T?
   { mutating get { return forward[key]  } set{ forward[key]  = newValue } }

   var count:Int { return _forward?.count ?? _backward?.count ?? 0 }
}

var bd = BidiMap( [1:"A", 2:"B", 3:"C"] )
bd[1] // "A"
bd["B"] // 2
bd[4] = "D"
bd[to:"D"] // 4
bd[from:4] // "D"

var int2int = BidiMap( [1:2, 5:3] )
int2int[from:1] // 2
int2int[to:3] // 5

[EDIT] improved performance a bit by delaying rebuilding of mirror dictionary until it is actually referenced.

Tamatamable

you should .lazy before map, because there's no need to copy the key/value collections into a seperate array only for iteration by uniqueKeysWithValues – Lorenzetti