Implementacja i używanie wielosłowników w języku Scala
Author
Piotr Kolaczkowski
blog_date_icon
19 grudnia

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 (<code>HashMap</code>) oraz drzewa czerwono-czarne (<code>TreeMap</code>). 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:

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

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

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

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

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

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:

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

Jak widać, jest trochę za dużo kodu, jak na tak prostą czynność. Z pomocą przychodzi nam <code>scala.collection.mutable.MultiMap</code>. Dzięki <code>MultiMap</code> 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:

<pre> 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")) </pre>

Prawda, że dużo prościej? Należy jednak przy tym zwrócić wagę na dwie rzeczy: <code>Set</code> musi być zaimportowany z pakietu <code>mutable</code>, a nie domyślnego oraz <code>MultiMap</code> parametryzujemy bezpośrednio klasą <code>Role</code> a nie <code>Set[Role]</code>. 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 <code> scala.collection.immutable.MultiMap </code>. Ponadto, jeśli nie kontrolujemy kodu tworzącego słownik, to nie mamy jak udekorować go dobrodziejstwami <code>MultiMap</code>. 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 <code>addBinding</code> i <code>removeBinding</code> do dowolnego obiektu klasy <code>Map[, Set[]]</code>:

<pre> 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) } </pre>

Co tu się dzieje? Definiujemy nową klasę MultiMap, która dostarcza pożądane metody <code>addBinding</code> i <code>removeBinding</code>, 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 <code>Set.empty</code>, ponieważ użytkownik może chcieć operować na innej implementacji zbioru np. <code>TreeSet</code>.

Za tworzenie obiektów naszej klasy MultiMap na podstawie obiektów dowolnej podklasy <code>Map</code> odpowiada metoda implicit <code>mapToMultiMap</code>. 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 <code>mapToMultiMap</code> to obiekt implementujący interfejs <code>CanBuildFrom</code>. Obiekty CanBuildFrom dostarczają fabryki służące do produkowania kolekcji - w tym przypadku obiekt ten został użyty do utworzenia pustego zbioru typu <code>S[V]</code>. Biblioteka standardowa Scali zawiera implementacje <code>CanBuildFrom</code> dla wszystkich standardowych typów kolekcji. Ponieważ argument został oznaczony jako implicit, to odpowiednia implementacja <code>CanBuildFrom</code> 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:

<pre> 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)))) </pre>

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

<pre> 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))) </pre>

Przeczytaj także