Implementacja i używanie wielosłowników w języku Scala

Większość języków programowania wysokiego poziomu dostarcza struktury implementujące tablice asocjacyjne, inaczej zwane słownikami. Struktury te umożliwiają przechowywanie zbioru wartości skojarzonych z obiektami - kluczami - w taki sposób, że wyszukiwanie wartości na podstawie klucza jest bardzo szybkie. Scala dysponuje standardowo słownikami wykorzystującymi tablice haszujące (HashMap) oraz drzewa czerwono-czarne (TreeMap). Obie implementacje są dostępne w wersjach mutowalnej i niemutowalnej.

Co jednak zrobić, jeśli chcemy z jednym kluczem skojarzyć więcej niż jeden obiekt-wartość? Najprościej użyć zwykłego słownika ale zamiast pojedynczego obiektu wartości użyć zbioru wartości. Np. chcemy skonstruować wielosłownik przechowujący informacje o rolach użytkowników:

import scala.collection.mutable.HashMap
case class User(name: String)
case class Role(name: String)
val roles = new HashMap[User, Set[Role]]

Żeby dodać do takiego słownika jakieś dane, możemy napisać:

roles += (User("Bob") -> Set(Role("User")))
roles += (User("Mike") -> Set(Role("User")))

Co jeśli teraz chcemy Boba awansować na Admina, ale zachowując wszystkie pozostałe role?

roles += (User("Bob") -> (roles(User("Bob")) + Role("Admin")))

Niestety takie proste rozwiązanie ma wadę. Co się stanie jeśli użytkownika Bob nie było wcześniej w kolekcji? Dostaniemy wyjątek. Poniżej poprawiona wersja:

roles += (User("Bob") -> (roles.getOrElse(User("Bob"), Set.empty)
  + Role("Admin")))

Jak widać, jest trochę za dużo kodu, jak na tak prostą czynność. Z pomocą przychodzi nam scala.collection.mutable.MultiMap. Dzięki MultiMap będziemy mogli dodawać nowe obiekty wprost i, co najważniejsze, nie zapomnimy obsłużyć sytuacji, gdy nie było w kolekcji wcześniej klucza:

import scala.collection.mutable.{MultiMap, Set}

val roles = new HashMap[User, Set[Role]] with MultiMap[User, Role]
roles.addBinding(User("Bob"), Role("User"))
roles.addBinding(User("Bob"), Role("Admin"))

Prawda, że dużo prościej? Należy jednak przy tym zwrócić wagę na dwie rzeczy: Set musi być zaimportowany z pakietu mutable, a nie domyślnego oraz MultiMap parametryzujemy bezpośrednio klasą Role a nie Set[Role]. W przeciwnym przypadku dostaniemy błąd kompilacji.

Można powiedzieć, że to już koniec tego wpisu, bo przecież w końcu tytułowy wielosłownik udało się utworzyć. Jednak przeoczyliśmy pewien szczegół: wszystkie przykłady tu przedstawione opierają się na kolekcjach mutowalnych. Natomiast w Scali zalecanym sposobem jest programowanie z użyciem kolekcji niemutowalnych (czemu tak jest i czemu jest to ogólnie lepsza strategia projektowania aplikacji, to już temat na osobny wpis). Niestety jak zajrzymy dokładniej do API, to nie znajdziemy tam interfejsu scala.collection.immutable.MultiMap . Ponadto, jeśli nie kontrolujemy kodu tworzącego słownik, to nie mamy jak udekorować go dobrodziejstwami MultiMap. Czy jesteśmy zatem zdani na niewygodne operowanie zwykłym słownikiem tak jakby był wielosłownikiem? Na szczęście nie. Tylko tym razem musimy się nieco bardziej napracować.

Scala posiada bardzo potężny mechanizm automatycznych konwersji. W momencie, gdy potrzebujemy wywołać na obiekcie nieistniejącą metodę, to nastąpi próba przekonwertowania tego obiektu do innego obiektu, który ową metodę posiada. W ten sposób można dodawać nowe metody do klas, bez konieczności modyfikacji ich kodu, poprzez dostarczenie odpowiednich konwersji. Czyli można dodać też metody addBinding i removeBinding do dowolnego obiektu klasy Map[, Set[]]:

import collection.generic.CanBuildFrom

object MultiMapUtil {

  class MultiMap[K, V, M <: Map[K, Set[V]]](map: M, emptySet: Set[V])
  {

    def addBinding(k: K, v: V): M =
      (map + (k -> (map.getOrElse(k, emptySet) + v))).asInstanceOf[M]


    def removeBinding(k: K, v: V): M = {
      val r = (map.getOrElse(k, emptySet) - v)
      (if (r.isEmpty) map - k else map + (k -> r)).asInstanceOf[M]
    }
  }

  implicit def mapToMultiMap[K, V, S[V] <: Set[V], M[K, S] <:
      Map[K, S]] (map: M[K, S[V]])(implicit bf:
      CanBuildFrom[Nothing, V, S[V]]) =
      new MultiMap[K, V, M[K, S[V]]](map, bf.apply.result)
}

Co tu się dzieje? Definiujemy nową klasę MultiMap, która dostarcza pożądane metody addBinding i removeBinding, operujące na obiekcie słownika przekazanym w konstruktorze obiektu. Konstruktor dodatkowo potrzebuje obiektu reprezentującego pusty zbiór. Nie można wpisać w kodzie na stałe domyślnego zbioru pustego Set.empty, ponieważ użytkownik może chcieć operować na innej implementacji zbioru np. TreeSet.

Za tworzenie obiektów naszej klasy MultiMap na podstawie obiektów dowolnej podklasy Map odpowiada metoda implicit mapToMultiMap. Słowo kluczowe implicit mówi kompilatorowi, że może samodzielnie wstawić wywołanie tej metody w celu dokonania odpowiedniej konwersji. Parametry typów K, V, S i M oznaczają kolejno: typ klucza, typ wartości, typ zbioru użytego do przechowywania wartości i typ słownika. Nie trzeba ich podawać, kompilator sam dopasuje odpowiednie typy na podstawie typu obiektu podanego jako argument metody.

Drugi argument metody mapToMultiMap to obiekt implementujący interfejs CanBuildFrom. Obiekty CanBuildFrom dostarczają fabryki służące do produkowania kolekcji - w tym przypadku obiekt ten został użyty do utworzenia pustego zbioru typu S[V]. Biblioteka standardowa Scali zawiera implementacje CanBuildFrom dla wszystkich standardowych typów kolekcji. Ponieważ argument został oznaczony jako implicit, to odpowiednia implementacja CanBuildFrom zostanie podstawiona przez kompilator automatycznie. Warto zapoznać się z tym mechanizmem dokładniej, bo wiele metod w bibliotece standardowej z niego korzysta.

Na zakończenie sesja REPL pokazująca użycie powyższego kodu:

scala> import MultiMapUtil._
import MultiMapUtil._

scala> val roles1 = Map.empty[User, Set[Role]]
roles1: scala.collection.immutable.Map[User,Set[Role]] = Map()

scala> val roles2 = roles1.addBinding(User("Kowalski"), Role("User"))
roles2: scala.collection.immutable.Map[User,Set[Role]] =
  Map((User(Kowalski),Set(Role(User))))

scala> val roles3 = roles2.addBinding(User("Kowalski"), Role("Admin"))
roles3: scala.collection.immutable.Map[User,Set[Role]] =
  Map((User(Kowalski),Set(Role(User), Role(Admin))))

Z innymi klasami słowników i zbiorów też działa - proszę zwrócić uwagę na typ wyniku oraz kolejność kluczy:

import scala.collection.immutable.TreeMap
import scala.collection.immutable.TreeSet

scala> val m = TreeMap[String, TreeSet[Int]]()
m: scala.collection.immutable.TreeMap[String,
  scala.collection.immutable.TreeSet[Int]] = Map()

scala> m.addBinding("a", 10).addBinding("b", 20).addBinding("a", 15)
res3: scala.collection.immutable.TreeMap[String,
  scala.collection.immutable.TreeSet[Int]] =
  Map((a,TreeSet(10, 15)), (b,TreeSet(20)))