Struktury danych w JavaScripcie – Zbiór

W dzisiejszym wpisie pokazuję kolejną strukturę danych. Zaczynam powoli zbliżać się do końca tej serii postów 🙂

Tym razem na tapetę idzie zbiór. Jest to struktura, która powinna być wszystkim znana, choćby z lekcji matematyki w podstawówce 🙂 Według mnie to jedna z prostszych struktur danych do opisania, więc powinno być lekko.

Co ciekawe w najnowszej wersji języka JavaScript, ECMAScript6 istnieje wbudowana klasa zbioru. Można poczytaj o niej więcej na przykład tutaj (niestety nie ma polskiej wersji językowej artykułu). Mimo to pokażę jak stworzyć własną implementację. Tak jak w przypadku innych struktur opisywanych na blogu, nie chodzi o użyteczność kod a o to ile można się dzięki stworzeniu go nauczyć.

Struktury danych w JavaScripcie – Zbiór. Teoria

Zbiór różni się od wcześniej prezentowanych struktur, przede wszystkim tym, że przechowywane w nim dane mogą wystąpić tylko raz. To znaczy, że każda informacja w zbiorze jest dla tego zbioru unikatowa.

Na przykład znany nam z matematyki, zbiór liczb całkowitych zawiera liczby od jeden do nieskończoności, każda po razie. liczba 5 pojawia się w nim tylko raz.

Dla ludzi wartości z tego przykładu są ustawione w konkretnej kolejności. Jednak w zbiorach nie ma zasady, według której dane miałyby być posortowane. Ich kolejność nie ma znaczenia, w przeciwieństwie do na przykład listy.

Na zbiorze wykonywać można następujące operacje:

• Wstawianie wartości – Nic skomplikowanego, wstawianie nowej wartości do zbioru.
• Usuwanie wartości – Jak wyżej. Usuwanie konkretnej wartości ze zbioru.
• Łączenie zbiorów – Operacja na dwóch zbiorach, w wyniku której powstaje nowy zbiór. Zawiera on wszystkie wartości z pierwszego i drugiego zbioru.
• Znajdowanie różnicy zbiorów – Operacja na dwóch zbiorach. Jej wynikiem jest zbiór zawierający wszystkie te wartości z pierwszego zbioru, które nie pojawiają się w drugim zbiorze.
• Znajdowanie części wspólnej zbiorów – To również jest operacja, którą wykonuje się na dwóch zbiorach. Jej wynikiem jest zbiór zawierający te wartości, które pojawiają się zarówno w pierwszym jak i w drugim zbiorze.

To cała potrzebna do stworzenia implementacji teoria. Czas na trochę kodu.

Struktury danych w JavaScripcie – Zbiór. Teoria

Klasa zbioru wygląda w taki sposób:

Pierwsze pole klasy to tablica data. W tej tablicy przechowywane będą wartości znajdujące się w zbiorze. Nie używam obiektu, ponieważ dane w zbiorze nie są uporządkowane. Nie potrzebuję kluczy aby je odczytywać.

Kolejne pole to metoda pomocnicza has. Służy ona do sprawdzania czy wartość przekazana jej w argumencie znajduje się w tablicy data zbioru. Aby to sprawdzić używam metody tablicowej indexOf. Ta metoda zwraca indeks elementu podanego w parametrze w tablicy na której jest wywoływana. Jeżeli element nie znajduje się w tablicy, zwracane jest -1.

Metoda has zwraca true, jeżeli wartość znajduje się w danych zbioru, w przeciwnym wypadku zwracane jest false.

Kolejna metoda to insert. Służy ona do dodania nowej wartości do zbioru. Nowa wartość przekazywana jest w argumencie metody. Korzystając z metody has sprawdzam czy wartość znajduje się już w zbiorze, jeżeli tak, zwracane jest false, jeżeli nie, nowa wartość dodawana jest do zbioru.

Sprawdzenie to jest koniecznie i będzie pojawiać się w kolejnych metodach. Nie chcę dopuścić do sytuacji, w której w zbiorze znajdywały się dwie identyczne wartości.

Kolejna metoda to remove. Jej działanie jest bardzo proste. Przy pomocy indexOf, znajduje indeks wartości do usunięcia. Jeżeli jest on większy niż -1 (wartość znajduje się w zbiorze), usuwam wartość przy pomocy metody tablicowej splice.

Kolejna metoda to union. Jako argument, przyjmuje ona instancje klasy Set, czyli inny zbiór. W wyniku działania tej metody zwracany jest nowy zbiór, który zawiera wszystkie elementy ze zbioru, na którym wywołano union, oraz elementy ze zbioru, przekazanego w argumencie.

Wewnątrz metody tworzę nowy zbiór i przypisuję go do tymczasowej zmiennej toReturn. Następnie używając pętli for, przepisuje do nowego zbioru wszystkie elementy z aktualnego zbioru do toReturn. Drugi krok, to kolejna pętla for. Tym razem przechodzę przez dane zbioru przekazanego w argumencie. Każdą wartość sprawdzam, przy pomocy metody has, czy nie znajduje się już w toReturn, jeżeli nie, dodaję ją do toReturn. Na koniec zwracam nowy zbiór.

Następna metoda klasy Set to intersect. Ona również przyjmuje inny zbiór jako argument i zwraca zupełnie nowy zbiór. Zawartość zwracanego zbioru, to elementy, które pojawiają się zarówno w aktualnym zbiorze jak i tym z argumentu metody.

Pierwszym krokiem, jest stworzenie nowego zbioru tymczasowego toReturn. Następnie, przy pomocy pętli for, przechodzę przez każdy element aktualnego zbioru i sprawdzam, czy znajduje się on w zbiorze podanym w argumencie. Jeżeli tak, dodaje tę wartość do toReturn. Na koniec toReturn jest zwracane.

Ostatnia metoda to difference, służy ona do odejmowania zbiorów. Przyjmuje ona jeden argument – inny zbiór. tak jak dwie poprzednie metody, ta również zwraca zupełnie nowy zbiór. Zwracany zbiór zawiera te wartości aktualnego zbioru, które nie znajdują się w zbiorze z argumentu metody.

Działa ona dokładnie tak samo jak metoda intersect, z tą różnicą, że w pętli for sprawdzam czy dany element nie znajduje się w drugim zbiorze i wtedy dodaje go do zwracanego zbioru.

Na koniec warto przeprowadzić parę testów w konsoli, moje wyglądają tak:

Wszystko się zgadza. Nowa struktura danych gotowa 🙂

Jeżeli masz jakieś pytania odnośnie zbioru, lub którejś z poprzednio opisanych struktur danych, może śmiało je zadać w komentarzach poniżej. Oczywiście świetnym miejscem na kontakt ze mną jest też moja strona na facebooku. Zachęcam przy okazji do polubienia jej, dzięki temu będziesz na bieżąco ze wszystkimi nowościami, które pojawiają się na blogu 🙂