6. Kolekcje


Programowanie polega na posługiwaniu się strukturami danych i algorytmami. Reprezentowanie struktur danych w programie nie jest łatwe, jeśli wszystko musimy oprogramować sami. Dlatego w wielu językach programowania istnieję swoiste biblioteki gotowych do wykorzystania konkretnych realizacji abstrakcyjnych struktur danych. W Javie nazywa się to Java Collections Framework.


6.1. Pragmatyczne wprowadzenie i podstawowe pojęcia. 

Kolekcja jest obiektem, który grupuje elementy danych (inne obiekty) i pozwala traktować je jak jeden zestaw danych, umożliwiając jednocześnie wykonywanie operacji na zestawie danych np. dodawania i usuwania oraz przeglądania elementów zestawu


W innych językach programowania kolekcje nazywane są często kontenerami . W Javie słowo kontener jest używane w innym znaczeniu (zob. wykłady o  GUI),
Zwykle kolekcje stanowią grupy "podobnych" elementów np. folder poczty elektronicznej (kolekcja e-maili) czy książka teleadresowa (kolekcja osób z przypisanymi im adresami i numerami telefonów) . 

Naturalną, znaną nam już, realizacją koncepcji kolekcji jest w Javie tablica.
Jest ona jednak niewystarczające wobec bogactwa różnych, użytecznych w programowaniu, struktur danych.
Dlatego w Javie, w pakiecie java.util, zdefiniowano interfejsy i klasy, służące do tworzenia i posługiwania się róznymi rodzajami kolekcji.

Uwagi:
  1. Szczegóły konstrukcji użytych w przykładowych programach będą omówione w następnych punktach.
  2. Ze względu na wstępny charakter tego podrozdziału - nie stosujemy właściwych zasad używania kolekcji. Na zasady te zwrócimy szczególną uwagę później.
  3. W przykładowych programach - po to by utrzymać minimalne rozmiary funkcjonującego kodu - nie stosujemy wlaściwych obiektowych konstrukcji (ograniczamy się zwykle do metody main()) i  unikamy obsługi wyjątków. Jest to oczywiście sposób programowania, którego nie wolno stosować w praktyce.
Zanim przejdziemy do omówienia struktury klas kolekcyjnych i zasad ich wykorzystania, warto przyjrzeć się krótkim przykładom, pokazującym użyteczność zastosowanie niektórych z nich.

Wyobraźmy sobie, że wczytujemy z pliku listę firm.
W programie możemy przedstawić ją jako tablicę. Ale jaki rozmiar ma mieć ta tablica? Z góry nie wiemy: w jednym pliku może być 100 firm - w innym 3 miliony.
A tablice w Javie mają ustalone (przy tworzeniu), niezmienne rozmiary, zatem nie nadają się do przedstawienia listy firm (których raz może być kilka, innym razem kilka milionów).

Oczywiście, możemy "ręcznie" dynamicznie realokować tablicę, zwiększając (w miarę potrzeby) jej rozmiary i przepisując zwartość, ale jest lepszy i prostszy sposob.

O liście możemy myśleć jako o zestawie elementów, z których każdy znajduje się na określonej pozycji w zestawie.
Klasa ArrayList z pakietu java.util stanowi latwe rozwiązanie problemu: jest ona konkretną realizacją listy w postaci tablicy o dynamicznie (w miarę potrzeby) zmieniających się rozmiarach. Dodajemy element elt do końca listy za pomocą metody add(elt), uzyskujemy element znajdujący się na pozycji ind za pomocą metody get(ind), możemy też dowiedzieć się ile elementów aktualnie zawiera lista za pomocą metody size().

Zatem krótki ilustracyjny programik, który tworzy listę firm, dodaje do niej dowolną liczbę elementów (nazw firm zapisanych w kolejnych wierszach pliku), po czym wyprowadza zawartość listy na konsolę mógłby wyglądać tak:

import java.util.*;
import java.io.*;

class Intro1 {

  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader( new FileReader(args[0]));
    // Utworzenie obiektu klasy ArrayList
    ArrayList list = new ArrayList();
    String firm;
    while ((firm = in.readLine()) != null)
       // dodanie kolejnego elementu do listy
       list.add(firm);
    // wyprowadzenie zawartości listy
    for (int i=0; i < list.size(); i++) System.out.println(list.get(i));
  }
}

IBM
Sun
Sun
Apple
Jeśli w pliku mamy zapisane w kolejnych wierszach: IBM, Sun, Sun, Apple to wynik będzie jak obok.

Można też użyć innego (bardziej ogólnego i lepszego - dlaczego zobaczymy dalej) sposobu przeglądania elementów listy.

Iterator jest obiektem służącym do przeglądania kolekcji.


Od każdej kolekcji za pomocą metody iterator()  możemy uzyskać obiekt-iterator, służący do jej przeglądania, po czym za pomocą metody next() uzyskiwać dostęp do kolejnych elementów, a za pomocą metody hasNext() - sprawdzać, czy kolejny element można pobrać (czy nie dobiegliśmy do końca kolekcji). W naszym przykładzie listy firm użycie iteratora może wyglądać następująco:

    Iterator iter = list.iterator();
    while( iter.hasNext()) System.out.println(iter.next());
co da taki sam efekt w postaci wyprowadzenia listy firm.

Zauważmy, że w pliku firm dwa razy powtórzono nazwę Sun. Co zrobić, jeśli chcemy mieć
wynikowy zestaw firm bez powtórzeń nazw?
Oczywiście, można własnoręcznie oprogramować sprawdzanie elementów zestawu i usuwać z niego duplikaty.
Zbiór jest kolekcją, reprezentującą zestaw niepowtarzających się elementów
Ale po co, jeśli istnieje prostszy sposób - zastosowanie kolekcji typu zbiór. Możemy np. użyć konkretnej klasy realizująceh koncepcję zbioru - klasy HashSet.

import java.util.*;
import java.io.*;

class Intro2 {

  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader( new FileReader(args[0]));
    HashSet set = new HashSet();
    String firm;
    while ((firm = in.readLine()) != null) set.add(firm);
    Iterator iter = set.iterator();
    while( iter.hasNext()) System.out.println(iter.next());
    }

}
i w efekcie uzyskamy zestaw firm bez duplikatów:
Sun
Apple
IBM





Zwróćmy uwagę, że - ogólnie:
Co zrobić, jeśli od naszego programu wymagane jest wyprowadzenie uporządkowanego zestawu firm np. w alfabetycznym porządku ich nazw?

Możemy zastosować kolekcję stanowiącą zbiór uporządkowany. W zbiorze uporządkowanym kolejność przeglądania jego elementów za pomoca iteratora jest określona (np. w rosnącym porządku alfabetycznym nazw firm, będących elementami zbioru). Konkretną realizacją zbioru uporządkowanego jest w Javie klasa TreeSet.

Zatem następujący program:
import java.util.*;
import java.io.*;

class Intro3 {

  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader( new FileReader(args[0]));
    TreeSet set = new TreeSet();
    String firm;
    while ((firm = in.readLine()) != null) set.add(firm);
    Iterator iter = set.iterator();
    while( iter.hasNext()) System.out.println(iter.next());
    }

}
Apple
IBM
Sun
wyprowadzi nazwy firm, pobrane z pliku, w porządku rosnącym i bez duplikatów.

Okazuje się oto, że mamy dwa rodzaje konkretnych klas dla reprezentacji zbiorów. Każda z nich stanowi jakąś realizację abstrakcyjnej struktury danych, jaką jest zbiór. Tę ogólną wlaściwość swoich obiektów - bycia zbiorem  - obie klasy uzyskują poprzez implementację odpowiedniego interfejsu. Klasa HashSet implementuje interfejs Set. Również klasa TreeSet implementuje ten interfejs (ale pośrednio, poprzez implementację interfejsu SortedSet, który rozszerzając interfejs Set nadaje zbiorowi dodatkową właściwość bycia zbiorem uporządkowanym).

Zatem ważnym elementem architektury kolekcji w Javie (i nie tylko) są interfejsy.

Interfejsy kolekcyjne - określają abstrakcyjne typy danych będące kolekcjami i pozwalają na niezalezne od szczegółów realizacyjnych operowanie na kolekcjach


Konkretne kolekcje, obiekty na których operujemy są obiektami klas implementujących interfejsy kolekcyjne.
Zatem, drugim ważnym elementem architektury kolekcji są implementacje.

Implementacja kolekcji jest konkretną realizacją funkcjonalności, określanej przez interfejs kolekcyjny. Takie realizacje mogą być różne w szczegółach technicznych, np. realizacja listy jako dynamicznej tablicy lub jako listy z dowiązaniami.
 


Jak widzieliśmy, TreeSet zapewnia uporządkowanie elementów kolekcji. Co jednak zrobić, jeśli w naszym przykładowym programie przechowujemy  kolekcję firm jako listę (np. ArrayList) i chcemy ją posortować?
Możemy zastosowac gotowy algorytm sortowania zapisany w postaci statycznej metody klasy Collections.
Poniższy program:
import java.util.*;
import java.io.*;

class Intro4 {

  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader( new FileReader(args[0]));
    ArrayList list = new ArrayList();
    String firm;
    while ((firm = in.readLine()) != null) list.add(firm);
    Collections.sort(list);
    Iterator iter = list.iterator();
    for (int i=1; iter.hasNext(); i++) {
      firm = (String) iter.next();
      System.out.println(i + ": " + firm);
    }
  }

}
Uwaga: elementy kolekcji są obiektami (klasa Object), zatem iterator zwraca wartości ogólnego typu Object i trzeba dokonac konwersji do właściwego typu
wyprowadzi firmy w rosnącym alfabetycznym  porządku ich nazw:
1: Apple
2: IBM
3: Sun
4: Sun




Zatem trzecim ważnym elementem architektury kolekcji są algorytmy.

Algorytmy kolekcyjne są metodami wykonującymi użyteczne operacje obliczeniowe na kolekcjach (np. sortowanie i wyszukiwanie). Metody te są polimorficzne tzn. ta sama metoda może być użyta dla wielu róznych implementacji tego samego interfejsu kolekcyjnego



Architektura kolekcji (Collections Framework)
Zunifikowana architektura, służąca do reprezentacji kolekcji i operowania na nich,
Składa się z:
  • interfejsów,
  • implemnetacji,
  • algorytmów.
Najbardziej znane architektury kolekcji to: STL (Standard Templates Library) w C++, klasy kolekcyjne w SmallTalk'u oraz JCF (Java Collections Framework).  

Kontynuując wątek pragmatycznych zastosowań, wyobraźmy sobie teraz, że w pliku znajdują się  nazwy i adresy firm. Nasz program po wczytaniu pliku ma za zadanie dostarczenie prostego interfejsu wyszukiwania adresu dla podanej nazwy firmy. Jak to zrobić?

Tablica asocjacyjna jest zestawem elementów, do których zapewniono swobodny, bezpośredni (czyli bez konieczności przeglądania elementów zestawu) dostęp za pomocą kluczy. Można sobie wyobrażać, że jest to uogólnienie zwykłej tablicy. W zwykłej tablicy kluczami sa indeksy całkowite. W tablicy asocjacyjnej kluczami mogą być dowolne obiekty, Efektywne realizacje tablic asocjacyjnych opierają się na odpowiedniej implementacji  słowników (odwzorowujących klucze w odpowiadające im wartości). W Javie slownikowe implementacje tablic asocjacyjnych nazywane są słowem map, pochodzącym od terminu mapping , oznaczającego  jednoznaczne odwzorowanie (w tym przypadku zbioru kluczy w zbiór wartości). Również po polsku krótko będziemy nazywać tablice asocjacyjne mapami.
Chwila zastanowienia prowadzi do wniosku, że proste sposoby rozwiązania tego problemu (np. prowadzenie dwóch list - nazw i adresów - i liniowe wyszukiwanie nazwy na liście nazw po to by otrzymać pozycję adresu na liście adresów) są bardzo nieefektywne. No i wymagają od nas pisania kodu. Tym więcej (trudniejszego) programowania czekałoby nas, gdybyśmy "od podstaw" próbowali samodzielnie oprogramować bardziej efektywne podejścia do odnajdywania adresów po nazwach (czyli bardziej efektywnie implementować abstrakcyjną strukturę danych jaką jest tablica asocjacyjna).

Na szczęście w Java Collections Framework mamy odpowiednie klasy, które efektywnie wykonują za nas całą pracę. Należy do nich klasa HashMap, która reprezentuje zestaw par klucz-wartość (ściślej: jednoznaczne odwzorowanie klucze->wartości) i umożliwia - za pomocą metody put(klucz, wartość) dodawanie pary (czyli wartości "pod" podanym kluczem) oraz - za pomocą metody get(klucz) uzyskiwanie wartości, związanej z (znajdującej się "pod") podanym kluczem.

Zatem np., jeśli w każdym wierszu pliku wejściowego mamy nazwy firm i  - oddzielone od nich znakiem '#' adresy, to problem wyszukiwania adresów dla firm podawanych w dialogach wejściowych można oprogramować w następujący sposób.

import java.util.*;
import java.io.*;
import javax.swing.*;

class Intro4 {

  public static void main(String args[]) throws IOException {
    BufferedReader in = new BufferedReader( new FileReader(args[0]));


    String firmName = null;         // nazwa firmy
    String address = null;          // adres firmy
    HashMap map = new HashMap();    // mapa odwzorowań : nazwa -> adres

    // Wczytywanie danych z pliku
    String inp;
    while ((inp = in.readLine()) != null) {
      StringTokenizer st = new StringTokenizer(inp, "#");

      // nazwa firmy będzie kluczem
      // pod którym w mapie odnajdziemy jej adres
      firmName = st.nextToken();
      address = st.nextToken();
      map.put( firmName, address );  // dodanie pary klucz-wartość do mapy
    }

    // Interakcyjna część programu:
    // dla podanej w dialogu nazwy firmy pokazywany jest jej adres
    while ((firmName = JOptionPane.showInputDialog("Nazwa firmy")) != null) {
      address = (String) map.get(firmName);
      if (address == null) address = "Nie ma takiej firmy";
      JOptionPane.showMessageDialog(null, "Firma: " + firmName + '\n' +
                                          "Adres: " + address);

    }
  }
}
Uwaga: klucze i wartości są typu Object, konieczne są więc konwersje do właściwego typu; jeśli w mapie nia ma podanego klucza (i odpowiadającej mu wartości) to metoda get(klucz) zwraca null.

To krótkie wprowadzenie do kolekcji przekonuje nas, że Java Collections Framework (JCF) jest niezwykle użyteczną składową środowiska Javy. Mamy do dyspozycji wiele gotowych, efektywnych, klas i metod, pozwalających łatwo rozwiązywać wiele problemów związanych z reprezentacją w programie bardziej zaawansowanych struktur danych i operowaniem na nich.

W szczególności, widzieliśmy, że:
Zamiast wyważać otwarte drzwi - wykorzystajmy klasy kolekcyjne!

Ale nie tylko na tym polega sila Java Collections Framework. Zastosowana architektura kolekcji sprawia, że można tworzyć metody i programy o uniwersalnym charakterze, operujące na kolekcjach (reprezentujących abstrakcyjne typy danych) w sposób niezależny od implementacji. I, co więcej, architektura kolekcji jest otwarta: korzystając z jej elementów możemy łatwo sami tworzyć nowe rodzaje abstrakcyjnych struktur danych lub nowe implementacje,  niejako wbudowane w istniejącą strukturę kolekcji, co czyni nasze nowe interfejsy i klasy proste w ponownym użytku zgodnie z jednolitymi regułami użycia klas i interfejsów kolekcyjnych.

6.2. Podstawowe rodzaje kolekcji. Interfejsy i implementacje

Klasy Java Collections Framework dostarczają środków do posługiwania się:

Każda z tych abstrakcyjnych struktur danych ma pewne właściwości, które wyróżniają ją od innych struktur danych. Mówimy, że są to abstrakcyjne struktury danych, bowiem w opisie tych właściwości nie przesądza się o tym w jaki sposób konkretnie je zrealizować.

Abstrakcyjne wlaściwości struktur danych opisywane są przez interfejsy, a konkretne realizacje - inaczej implementacje - tych właściwości znajdujemy w konkretnych klasach.

Na przykład, intefejs List określa ogólne właściwości listy (to, że każdy element zestawu danych znajduje się na określonej pozycji) oraz możliwe operacje na liście. Właściwości te i operacje można zrealizować w różny sposób: poprzez użycie tablicy z dynamicznie zmieniającymi się rozmiarami (implementacja tablicowa) lub poprzez implementację podwójnie-dowiązaniową (w której kolejny element listy umieszczony jest w strukturze, która oprócz samego elementu zawiera dowiązania, czyli odniesienia, wskaźniki do następnego i  poprzedniego elementu listy).
Odpowiednio do tego mamy dwie klasy ArrayList (implementacja tablicowa) i LinkedList (implementacja podwójnie dowiązaniowa), każda z których realizuje koncepcję listy.
W obu przypadkach mamy do czynienia z listą, ale pewne operacje na liście w każdej z tych implementacji mają inną efektywność (czas wykonania). Zatem w zależności od potrzeb możemy wybierać odpowiednią implementację listy.

Podobnie jest z innymi - reprezentowanymi w JCF - abstrakcyjnymi strukturami danych.


Podstawowe struktury danych w JCF


Podstawowe
właściwości
implementacji


Lista
Zbiór
Tablica
asocjacyjna
(słownik)
       Interfejsy >>
List
Set
Map
Implementacja
Klasy :
Dynamicznie rozszerzalna tablica
ArrayList


szybki bezpośredni dostęp
Lista liniowa z  podwójnymi dowiązaniami
LinkedList


szybkie wpisywanie i usuwanie elementów poza końcem listy; wolny dostęp bezpośredni
Tablica mieszania
(tablica haszująca)

HashSet
HashMap
szybkie wpisywanie i odnajdywanie elementów; kolejność elementów nieokreślona
Drzewo
czerwono-czarne

TreeSet
TreeMap
uporządkowanie elementów; dostęp i wyszukiwanie wolniejsze niż w implementacji mieszającej
Tablica mieszania
i  lista liniowa z
podwójnymi dowiązaniami

LinkedHashSet
LinkedHashMap
jak w implememntacji mieszającej, z zachowaniem porządku wpisywania elementów


Właściwości struktur danych
zestaw elementów, z których każdy znajduje się na określonej pozycji
zestaw niepowtarzających się elementów
zestaw par: klucz-wartość, przy czym odwzorowanie kluczy w wartości jest jednoznaczne

Uwagi:
  1. Użyte w tablicy pojęcia, dotyczące sposobu implementacji, zostaną wyjasnione w trakcie omawiania konkretnych struktur danych.
  2. Klasa TreeSet implementuje interfejs SortedSet, a klasa TreeMap - interfejs SortedMap. Oba te interfejsy sa rozszerzeniami wymienionych w tablicy interfejsow (odpowiednio Set i Map).
  3. W tabeli pokazano podstawowe, najwazniejsze interfejsy i klasy. O innych mowa będzie w dalszym ciągu dyskusji.
  4. Można (oczywiście) tworzyć inne implementacje interfejsów kolekcyjnych w swoich własnych klasach. Tu podano konkretne klasy, które są gotowe do użytku.
Jak widać, mamy dwie implementacje dla listy i po trzy implementacje dla zbioru i tablicy asocjacyjnej.
Wybór implementacji zależy od potrzeb naszego programu (w tablicy pokazano podstawowe właściwości implementacji).
Oczywiście, jeśli nasz program tworzy konkretne obiekty klas kolekcyjnych, to zawsze musimy dokonać takiego wyboru. Ale ważną rzeczą jest, by wszelkie inne działania na kolekcjach wykonywać w kategoriach interfejsów, a nie konkretnych klas.

Znaczenie tej ważnej zasady ilustrują poniższe fragmenty kodu.
 
r

Mamy tu klasę ListUtils, która dostarcza statycznych metod tworzenia listy z elementów tablicy (metoda create),  dodawania do końca istniejącej listy elementów tablicy (append) oraz wypisywania na konsoli elementów listy (show).
W innej klasie (tu nazywa się - na razie niesłusznie - Independence) posługujemy się metodami klasy ListUtils.

Zobaczmy co jest złego we fragmentach kodu z obu klas.
Metoda append z klasy ListUtils jest przystosowana wyłącznie do tablicowej implementacji listy (bo jej parametrem jest ArrayList). Zatem nie będzie działać dla list z dowiązaniami (LinkedList), ani też dla jakichkolwiek innych konkretnych implementacji listy. A przecież ta metoda nie wymaga przesądzania o implementacji. Wobec każdej kolekcji możemy użyć metody add, w szczegolności taką metodę zawiera również interfejs List. Powinniśmy zatem w sposób ogólniejszy podać typ parametru metody append. Ma ona dodawać elementy tablicy do dowolnej listy, winna zatem wyglądać tak:
  static void append(List list, Object[] items) {
    for (int i=0; i<items.length; i++)
      list.add(items[i]);
  }
To samo dotyczy metody show: również powinniśmy w niej podać jako typ parametru nazwę interfejsu List, a nie konkretnej klasy.
  static void show(List list) {
    for (Iterator iter = list.iterator(); iter.hasNext();)
      System.out.println(iter.next());
  }
Teraz fragment innej klasy (w naszym przypadku pokazanej klasy Indepedence) może elastycznie i uniwersalnie korzystać z tych metod. Możemy użyć ich na rzecz listy implementowanej jako tablica:
    String[] items = { "Kot", "Pies", "Zebra", "Tygrys" };
    List list1 = new ArrayList();
    ListUtils.append(list1, items);
    ListUtils.show(list1);
a jeśli trzeba - dla zmienionej implementacji listy (listy z dowiązaniami - LinkedList):
    String[] items = { "Kot", "Pies", "Zebra", "Tygrys" };
    List list1 = new LinkedList();
    ListUtils.append(list1, items);
    ListUtils.show(list1);
Zwróćmy uwagę, że całkiem świadomie napisaliśmy tu:

        List list1 = new ...

a nie
        ArrayList list1 = new ...
czy
        LinkedList list1 = new ...

Jeśli zdecydujemy się na zmianę implementacji (np. z ArrayList na LinkedList lub odwrotnie), to modyfikacja dotknie tylko jednego miejsca kodu (wywołania konstruktora w wyrażeniu new) i mniejsze będzie prawdopodobieństwo popełnienia błędu.

Gdy w innej klasie (w naszym przypadku - klasie Independence) korzystamy z metody create (klasy ListUtils), która zwraca nowoutworzoną listę z dodanymi do niej elementami przekazanymi w tablicy, również nie powinniśmy "przywiązywać" się do konkretnej implementacji listy zwracanej przez metodę create().
Zamiast pisać:
ArrayList list2 = ListUtils.create(
                            new String[] { "Truskawki", "Banany"}
                            );
powinniśmy napisać:

    List list2 = ListUtils.create(
                           new String[] { "Truskawki", "Banany"}
                           );
Metoda create(...) tworzy nową listę. musi zatem posłużyć się konkretną implementacją. W omawianym tu przypadku jest to klasa ArrayList. Nie byłoby błędu, gdybyśmy napisali:
   
    ArrayList list2 = ListUtils.create(...)

Ale gdyby twórca klasy ListUtils (może my sami) - z jakichś powodów - zmienił implementację nowotworzonej listy w metodzie create(..) z ArrayList na jakąś inną, to nasza klasa korzystająca z metody create(...) musialaby być zmodyfikowana i rekompilowana. Dzięki temu, że napisaliśmy:

    List list2 = ListUtils.create(...)

nasza klasa (tu: klasa Independence) jest gotowa do korzystania z dowolnych implementacji list zwracanych przez metodę create(..) i nie musi być rekompilowana przy zmianie tych implementacji.

Ogólnie więc, przy deklaracji parametrów metod oraz przy deklaracji zmiennych, których wartość jest referencją do kolekcji zwracaną przez jakąś metodę, użycie typu, wyznaczanego przez interfejs kolekcyjny, zamiast typu wyznaczanego przez implementację (klasę implementującą ten interfejs), pozwala na  uniknięcie modyfikacji i rekompilacji klasy przy zmianie implementacji kolekcji.
 

Ale zapisów "w terminach" interfejsów nie należy absolutyzować ani stosować "na ślepo".
Wyobraźmy sobie, że zbudowaliśmy klasę NumberedList, reprezentującą listę z numerami elementów. Klasa ta zawiera m.in. metodę addAuto dodającą do listy napisową reprezentację argumentu, poprzedzoną kolejnym numerem. Metoda ma zwracać tę listę na rzecz ktorej została wywołana (po to, by umożliwić "lańcuchowe" wywolania: list.addAuto(...).addAuto(...).addAuto(...)). Nie ma to może za wiele sensu, ale dobrze ilustruje zagadnienie.

Metoda addAuto(..) może wyglądać tak:

public class NumberedList extends ArrayList {
  // ...
  public NumberedList addAuto(Object o) {
    super.add("Nr." + (size()+1) + " " +o);
    return this;
  }
  // ...
}
Zwróćmy uwagę: typem zwracanego wyniku jest NumberedList, a nie List.
To bardzo słuszne, daje bowiem wołającemu tę metodę odpowiednią elastyczność. Nic nie stoi na przeszkodzie, by użyć jej wyniku w miejscu gdzie wymagane jest wyrażenie typu List (bo NumberedList dziedziczy ArrayList, a przez to implementuje interfejs List). A jednocześnie możliwe jest użycie na rzecz wyniku metody addAuto:
list.addAuto(..).addAuto(...), czego nie moglibyśmy zrobić, gdyby typem wyniku był List (bo interfejs List nie zawiera metody addAuto()).

Podobnie, w programie korzystającym z tej klasy napiszemy raczej:

NumberedList nls = new NumberedList();

a nie:

List nls = new NumberedList();

po to by móc korzystać z metody addAuto(...). Co w niczym nie przeszkadza podać nls jako argument dowolnej metody przyjmującej List.
Np.
    NumberedList nls = new NumberedList();
    nls.addAuto("Pies").addAuto("Kot").addAuto("Wilk");
    ListUtils.show(nls);
 

Omawiane zagadnienie wyboru deklarowanego typu zmiennej oznaczającej kolekcję uzyskuje nowy wymiar, jeśli uwzględnimy fakt, że w Javie istniejące interfejsy kolekcyjne tworzą hierarchiczne struktury i że struktury te możemy rozbudowywać tworząc własne interfejsy i klasy implementujące.

Kolekcje listowe i zbiorowe różnią się od kolekcji słownikowych (map):  w pierwszym przypadku do kolekcji dodawany jest element-obiekt, w drugim para obiektów klucz-wartość. Nie da się zatem w naturalny, prosty dla użytkownika sposób, uogólnić funkcjonalności kolekcji listowych i zbiorowych z jednej strony oraz map z drugiej. Dlatego interfejsy kolekcyjne tworzą dwie rozłączne hierarchie: jedna dla kolekcji listowych i zbiorowych, druga - dla map.

Podstawowe interfejsy listowe i zbiorowe oraz podstawowe implementujące je klasy pokazuje rysunek (o interfejsach map - zob. dalej).

r

Jak widać, wszystkie kolekcje listowe i zbiorowe dają się przedstawić jako typu Collection. Pozwala to wykonywać pewne ogólne operacje na kolekcjach bez względu na ich rodzaj i - tym bardziej - implementację.

Zanim dokładniej przyjrzymy się tym możliwościom, warto zwrócić uwagę, że przy deklarowaniu typów parametrów metod, służących do operowania na kolekcjach, powinniśmy wybierać typy określane przez interfejsy znajdujące się możliwie najwyżej w hierarchii dziedziczenia. To oczywiście zawsze zależy od kontekstu, od funkcjonalności dostarczanej przez nasze metody. Jeśli  przeznaczeniem metody jest operowanie na listach - typem parametru powinno być List, ale jeśli dotyczy ona dowolnych kolekcji - to raczej typem powinno być Collection.

I odwrotnie, typy wyników zwracanych przez metody powinny być jak najbardziej specyficzne, do konkretnej implementacji włącznie. Jeśli np. nasza metoda tworzy zbiór uporządkowany - obiekt klasy TreeSet (co jest bardziej kosztowne niż stworzenie zwykłego zbioru), to powinna zwracać wynik typu TreeSet, po to by użytkownik mógł skorzystać z dodatkowej funkcjonalności (uporządkowania), już przecież okupionej kosztem czasu działania programu.


6.3. Ogólne operacje na kolekcjach. Iteratory.

Interfejs Collection definiuje ogólne, wspólne właściwości i funkcjonalność wszystkich kolekcji (poza mapami).
W szczególności, dotyczy to dowolnych kolekcji listowych i zbiorowych, ale nie tylko: możemy mieć kolekcje, które nie są ani listami, ani zbiorami (sami możemy takie definiować, a w JCF przykładem takiej kolekcji jest zestaw wartości mapy, inaczej słownika, który nie jest listą, ponieważ elementy w zestawie nie są w żaden sposób uporządkowane, ani nie jest zbiorem, bowiem te same elementy mogą występować w kolekcji więcej niż jeden raz).

Typ Collection jest zatem swoistym "najmniejszym wspólnym mianownikiem" wszystkich rodzajów kolekcji i używamy go (szczególnie przy przekazywaniu argumentów) wtedy, gdy potrzebna jest największa ogólność działań.

Bardzo podstawowe, ale zawsze mające sens, operacje na kolekcjach to:
Większą operacyjność dają metody dodawania elementów do kolekcji (metoda add(...)) i usuwania elementów z kolekcji (metoda remove(...) ). Są one zawarte w interfejesie Collection, ale ich działanie musi być zdefiniowane tu bardzo ogólnie, z uwzględnieniem rożnych możliwych rodzajów kolekcji.
Mamy przy tym dwa problemy:
Kolekcja jest modyfikowalna, jeśli można dodawać do niej elemementy, usuwać z niej elementy oraz zmieniać wartości elementów. Niemodyfikowalne kolekcje nie pozwalają na dodawanie, usuwanie, zmianę wartości elementów.


Wobec tego twórcy Java Collection Framework stanęli przed wyborem:

Pierwsze rozwiązanie podważyłoby sens istnienia interfejsu Collection (bylby zapewne zbyt ubogi). Drugie było nie do przyjęcia ze względu na to, iż powodowałoby dalszą rozbudowę i tak już skomplikowanej hierarchii interfejsów i klas kolekcyjnych (a weźmy jeszcze pod uwagę różne możliwe warianty "niemodyfikowalności" np. tylko dodawanie bez usuwania, tylko usuwanie bez dodawania, tylko zabronione zmiany rozmiarów, ale zmiany wartości elementów możliwe itp.)
Wybrano zatem rozwiązanie trzecie, które - niestety - na zastosowanym poziomie ogólności też ma swoje wady.

Mianowicie niektóre metody (operacje) zawarte w interfejsach kolekcyjnych określone są jako operacje opcjonalne . Konkretne klasy kolekcyjne mogą dopuszczać lub nie wykonanie takich operacji. Np. klasa definiująca jakąś kolekcję niemodyfikowalną nie może pozwolić na wykonanie operacji dodawania i usuwania elementów.
Ale ponieważ każda klasa kolekcyjna musi implementować interfejs Collection, to musi też zdefiniować metody add i remove. Zdefiniować coś - co, z punktu widzenia dostępnych w danym przypadku operacji, nie powinno być zdefiniowane!
Sprzeczność tę rozwiązano, przyjmując zasadę, że jeśli operacja ocjonalna dla danej implementacji nie jest dopuszczalna, to odpowiednia metoda zglasza wyjątek UnsupportedOperationException.

Np. dla klas, które implementują kolekcje niemodyfikowalne, metody add i remove z interfejsu Collection powinny być zdefiniowane jako:
        public boolean add(Object o) {
	    throw new UnsupportedOperationException();
        }
	public boolean remove(Object o) {
	    throw new UnsupportedOperationException();
        }
Zwróćmy uwagę, sygnatury metod nie zawierają klauzuli throws..., zatem wyjątek jest niekontrolowany. I nie mogą zawierać: implementacja metod interfejsu nie dopuszcza "dodania" klauzuli throws. Jest to wspomniana słabość wybranego rozwiązania.

Czy zamiast tego nie można byłoby dostarczyć po prostu takich definicji metod add i remove, które nie modyfikują kolekcji?
Niestety, nie. Genaralny kontrakt dla metody add brzmi następująco:

Metoda add gwarantuje, że zaraz po jej użyciu podany jako argument obiekt znajduje się w kolekcji. Zwraca true jeśli kolekcja została zmodyfikowana (obiekt dodano) i false w przeciwnym razie (co oznacza, że obiekt już był w kolekcji typu zbiór, czyli takiej, ktora nie dopuszcza duplikatów).

Zatem w przypadku innego od UnsupportedOperationException rozwiązania nie moglibyśmy wiedzieć, czy false zwrócone przez add oznacza, że obiekt jest w zbiorze, czy też, że zbiór jest niemodyfikowalny.
W tym kontekście należy podkreslić, że wynik zwracany przez metodę add(...) jest rozwiazaniem drugiego, wcześniej wspomnianego, problemu: generalizacji operacji dodawania elementów do kolekcji bez duplikatów.

Podobnie jest z metodą remove. Ma ona usunąć podany jako argument obiekt. Zwraca true, jeśli obiekt był w kolekcji i został usunięty (kolekcja zmodyfikowana) oraz false, gdy podanego obiektu w kolekcji nie bylo. Zatem jedynym sposobem zasygnalizowania, że próbowano usunąć jakiś obiekt z kolekcji niemodyfikowalnej pozostaje zgłoszenie wyjątku.

W interfejsach kolekcyjnych występuje szereg innych operacji opcjonalnych. Opcjonalnośc ich wszystkich ma takie samo znaczenie jak w przypadku omówionych operacji add i remove tzn. wszystkie one zgłaszają wyjątek UnsupportedOperationException, jeśli operacja nie jest dozwolona

Bardzo ważną metodą interfejsu Collection jest metoda iterator(), ktora zwraca iterator.

Iterator jest obiektem klasy implementującej interfejs Iterator i służy do przeglądania elementów kolekcji oraz ew. usuwania ich przy przeglądaniu


Metody interfejsu Iterator
Object next()
Zwraca kolejny element kolekcji lub sygnalizuje wyjątek NoSuchElementExcption, jeśli osiągnięto koniec kolekcji
void remove()
Usuwa element kolekcji, zwrócony przez ostatnie odwolanie do next()  Operacja opcjonalna.
boolean hasNext()
Zwraca true, jeśli  ożliwe jest odwołanie do next() zwracające jakiś element kolekcji.

Klasy iteratorów są  definiowane w klasach kolekcyjnych jako klasy wewnętrzne, implementujące interfejs Iterator. Implementacja metody iterator() z interfejsu Collection zwraca obiekt takiej klasy. Dzięki temu od każdej kolekcji możemy uzyskać iterator za pomocą odwolania:


    Iterator iter = c.iterator();

gdzie:  c - dowolna klasa implementująca interfejs Collection.


Dla tych kolekcji, w których elementy nie zajmują ściśle określonych pozycji iteratory są jedynym sposobem na "przebieganie" po kolekcji. Co więcej, dla kolekcji listowych - niezależnie od implementacji - iteratory są efektywnym narzędziem iterowania, czego nie da się powiedzieć we wszystkich przypadkach o pętlach iteracyjnych pobierających elementy z pozycji wyznaczanych przez podane indeksy.

Warto zauważyć, że narzucająca się analogia pomiędzy kursorem i iteratorem może być myląca. O iteratorze należy raczej myśleć jako o wskaźniku ustawianym nie na elemencie kolekcji, ale pomiędzy elementami. Na początku iterator ustawiony jest przed pierwszym elementem. Odwolanie next() jednocześnie przesuwa iterator za pierwszy element i zwraca ten element. Każde kolejne next() przeskakuje kolejny element i zwraca ten  "przeskoczony" element. Zob. rysunek.

r



Metoda iteratora remove() może być bardzo użyteczna: najczęściej stosowana jest do usuwania z kolekcji elementów, które spełniają (nie spełniają) jakichś warunków. Inne sposoby usuwania takich elementów często mogą okazać się bardziej kosztowne.

Szablon użycia remove()  w trakcie iteracji:
Iterator iter = c.iterator(); // c - dowolna kolekcja, typ Collection
while (iter.hasNext()) {
  Object o = iter.next();
  if (warunek_usunięcia(o)) iter.remove();
}
Powyższy kod jest polimorficzny: nadaje się do zastosowania wobec dowolnych kolekcji dowolnych obiektów. Pod koniec tego punktu zobaczymy nieco bardziej zaawansowany przykład takiego polimorficznego wykorzystania iteratora.

Należy pamiętać, że metoda remove() może usunąć tylko element zwrócony przez next(), i wobec tego może być zastosowana tylko raz dla każdego next().
Zatem nie możemy w jednej iteracji  usunąć kilku elementów:

r
W tym przypadku zostanie zgłoszony wyjątek IllegalStateException.

Istnieją też inne istotne ograniczenia dotyczące modyfikacji kolekcji w trakcie iteracji.

W trakcie iteracji za pomocą iteratora nie wolno modyfikować kolekcji innymi sposobami niż użycie metody remove() na rzecz iteratora. Wyniki takich modyfikacji są nieprzewidywalne


Modyfikacje strukturalne (dodanie, usunięcie elementu) są w trakcie iteracji sprawdzane i wykrywane. Jeżeli w trakcie iteracji zostanie dokonana modyfikacja strukturalna za pomocą innych od remove() dla bieżącego iteratora metod - powstanie wyjątek ConcurrentModificationException.
Dotyczu to zarówno użycia metod add i remove interfejsu Colection, jak i metody remove, aktywowanej na rzecz innego iteratora.

Zatem w takich sytuacjach:
    List l = new ArrayList();
    // .. dodanie do listy jakichś elementów
    Iterator it1 = l.iterator();
    while (it1.hasNext()) {
      it1.next();
      l.add("Coś"); // Błąd fazy wykonania
    }
 
    List l = new ArrayList();
    // dodanie do listy jakichś elementów
    Iterator it1 = l.iterator();
    Iterator it2 = l.iterator();
    while (it1.hasNext()) {
      it1.next();
      it2.next();
      it2.remove();  // Błąd fazy wykonania
    }

w fazie wykonania zostanie zgłoszony wyjątek ConcurrentModificationException.


Interfejs Collection określa również tzw. grupowe operacje na kolekcjach, polegające na wykonywaniu "za jednym razem" pewnych operacji na całych kolekcjach.
Należą do nich:
Ponieważ operacje te mogą modyfikować kolekcje  (a o tym czy naprawdę nastąpiła modyfikacja - świadczą wyniki zwracane przez metody - true albo false), to - oczywiście - są one operacjami opcjonalnymi.

Operacje grupowe są często bardzo użyteczne:  zastępuja one drobne (ale zawsze) fragmenty kodu, które przy braku operacji grupowych musielibyśmy pisać sami. W przypadku zbiorów są one bezpośrednim odzwierciedleniem  operacji na zbiorach: sumy zbiorów, wspólnej częsci itp.
 A - co ważniejsze - są one z reguły bardziej efektywne od tego co moglibyśmy napisać sami, bowiem ich implementacje uwzględniają specyficzne cechy implementacji kolekcji, przy zachowaniu polimorficznego charakteru odwolań.

Niejako kontynuacją operacji grupowych jest możliwość przekształcenia kolekcji danego rodzaju  w dowolną inną kolekcję dowolnego innego rodzaju. Np. listy w zbiór uporządkowany. Co prawda, w interfejsie Collection nie znajdziemy żadnych po temu metod ( i nic dziwnego), ale samo jego istnienie daje taką możliwość.
We wszystkich konkretnych implementacjach kolekcji dostarczono bowiem konstruktorów, mających jako parametr dowolną inną kolekcję (czyli parametr typu Collection).
Jeśli zatem mamy listę, a chcemy z niej zrobić zbiór uporządkowany (w konkretnej implementacji - np. drzewa zrównoważonego), to wystarczy użyć konstruktora odpowiedniej klasy (tu: TreeSet):

  List lista;
  //... utworzenie listy w konkretnej implementacji np.ArrayList lub LinkedList
  Set tset = new  TreeSet(lista);
W ten sposób uzyskamy zbiór (a więc bez powtórzeń elementów), uporządkowany (w naturalnym porządku elementów), którego elementy będą pobrane z dostarczonej listy.


Interfejs Collection dostarcza także metod, służących do uzyskiwania z kolekcji tablic. Ich głównym przeznaczeniem jest zapewnienie komunikacji pomiędzy kolekcjami, a tymi fragmentami kodu, które kolekcji nie wykorzystują (zapewne najczęsciej będą to programy, które powstały przed wprowadzeniem Java Collection Framework).
Metoda toArray() zwraca tablicę obiektów (typu Object), będących elementami kolekcji.
Typ wynku - Object[] - nie zawsze będzie nam odpowiadał. Dodatkowym ułatwieniem (a zarazem ograniczeniem dowolności) jest zatem możliwośc użycia metody o tej samej nazwie, która - poprzez parametr -  specyfikuje typ (ustalany w fazie wykonania) zwracanej tablicy - toArray(Object[]).
Różnicę w zastosowaniu obu metod pokazuje poniższy fragment kodu:

    List list = new ArrayList()
    // ... tu dodawanie elementów do listy

    // Pierwszy sposób
    Object[] tab1 = list.toArray();
    for (int i=0; i<tab1.length; i++) {
      int len = ((String) tab1[i]).length();
      System.out.println(len);
    }
    // Drugi sposób
    String[] tab2 = (String[]) list.toArray(new String[0]);
    for (int i=0; i<tab2.length; i++) {
      int len = tab2[i].length();
      System.out.println(len);
    }
  } 

Niewątpliwie, metody interfejsu Collection stanowią podstawę poslugiwania się wszelkimi kolekcjami. Podsumowująca tablica pokazuje cały zestaw tych metod.

Metody interfejsu Collection
 booleanadd(Object o)
          Operacja opcjonalna.
          Zapewnia, że kolekcja zawiera podany element. Dla kolekcji listowych - dodaje element na końcu. Do zbiorów dodaje element, jeśli go w zbiorze nie ma. Zwraca true jeśli kolekcja została zmodyfikowana, false w przeciwnym razie (ale tylko wtedy, gdy element już jest w kolekcji, która nie dopuszcza duplikatów).
Jeśli dla danej kolekcji  nie jest dozowlone dodanie (danego) obiektu - metoda winna sygnalizować wyjątek.
 booleanaddAll(Collection c)
          Operacja opcjonalna.
          Dodaje do kolekcji wszystkie elementy kolekcji c. Zwraca true, jesli kolekcja została zmodyfikowana
 voidclear()
          Operacja opcjonalna.
          Usuwa wszystkie elementy z kolekcji.
 booleancontains(Object o)
          Zwraca true jeżeli kolekcja zawiera podany element.
 booleancontainsAll(Collection c)
         Zwraca true jeżeli kolekcja zawiera wszystkie elementy podanej kolekcji.
 booleanisEmpty()
          Zwraca true jeżeli kolekcja nie zawiera elementów.
 Iteratoriterator()
          Zwraca iterator dla kolekcji.
 booleanremove(Object o)
          Operacja opcjonalna.
          Usuwa podany element (jeden = pierwszy napotkany) z kolekcji. Zwraca true, jeśli kolekcja została zmodyfikowana (podany element był w kolekcji i został usunięty).
 booleanremoveAll(Collection c)
          Operacja opcjonalna.
          Usuwa z kolekcji wszystkie elementy, które są również w podanej kolekcji c. Zwraca true, jeśli kolekcja została zmodyfikwana.
 booleanretainAll(Collection c)
          Operacja opcjonalna.
          Pozostawia w kolekcji tylko te elemnty, które są zawarte w podanej kolekcji. Zwraca true, jesli kolekcja została zmodyfikoaana

 intsize()
          Zwraca liczbę elementów kolekcji.
 Object[]toArray()
          Zwraca tablicę zawierającą wszystjkie elementy kolekcji.
 Object[]toArray(Object[] a)
          j.w. ze specyfikacją typu elementów


Spójrzmy teraz na dwa nieco bardziej rozbudowane przykłady, pokazujące silę interfejsu Collection, iteratorów i operacji grupowych.

W pierwszym przykladzie stworzymy uniwersalną klasy MKolekt, której metody pozwalają zapelniać dowolne kolekcje obiektami dowolnych klas, tworzonymi na podstawie  informacji z plików tekstowych, wypisywać elementy dowolnych kolekcji oraz usuwać z dowolnych kolekcji elementy spelniające warunki "do usunięcia".
Zadanie jest trudne, bo różnorodność możliwych elementów kolekcji jest nieograniczona. Potrzebna jest zatem swoista współpraca naszej uniwersalnej klasy MKolekt z klasami konretnych obiektów - elementow kolekcji. Umówmy się więc, że każda z klas konkretnych elementów (dowolnych) kolekcji przetwarzanych przez metody klasy MKolekt musi zdefiniować dwie metody: metodę tworzenia swojego obiektu z podanego napisu (informacje o obiekcie będą pobierane z pliku tekstowego) i dodawania go do podanej kolekcji oraz metodę określającą czy obiekt spełnia warunki umożliwiające usunięcie go z kolekcji.
Naturalnym sposobem  zapewnienia tego jest zdefiniowanei odpowiedniego interfejsu i implementowanie go w klasach obiektów-elementów kolekcji. Nazwijmy ten interfejs CollectionHelper.
interface CollectionHelper {

  // Tworzy obiekt z podanego napisu s i dodaje go do kolekcji c
  void makeObjectAndCollect(String s, Collection c);

  // Zwraca true, jeśli obiekt powinien być usunięty z kolekcji
  boolean isReadyToRemove();
}

Zatem elementy kolekcji przetwarzanych przez metody klasy MKolekt "będą typu" CollectionHelper.

Klasa MKolekt może wyglądać tak.

public class MKolekt {

  // Tworzy obiekty klasy
  // określonej przez klasę obiektu mgr
  // na podstawie informacji z pliku tekstowego o nazwie fname
  // i dodaje je do kolekcji c

  public static void makeCollectionFromFile(Collection c, String fname,
                                     CollectionHelper mgr) {
    try {
      BufferedReader in = new BufferedReader(
                            new FileReader(fname)
                        );
      String line;
      while((line = in.readLine()) != null)
        mgr.makeObjectAndCollect(line, c);

      in.close();
    } catch (IOException exc) { System.exit(1); }
  }

  // Usuwa obiekty przeznaczone do usunięcia
  // na podstawie wyniku metodu isReadyToRemove
  // z kolekcji c
  public static void iterRemove(Collection c) {
    Iterator iter = c.iterator();
    while (iter.hasNext()) {
      Object o = iter.next();
      CollectionHelper elt = (CollectionHelper) o;
      if (elt.isReadyToRemove()) iter.remove();
    }
  }

  // Wypisuje na konsoli wszystkie elementy kolekcji c
  public static void show(Collection c) {
    for (Iterator iter = c.iterator(); iter.hasNext(); )
      System.out.println(iter.next().toString());
  }
}

Jest ona uniwersalna, bowiem będzie działać dla obiektów dowolnych klas implementujących CollectionHelper i dla dowolnych kolekcji tych obiektów.
Szczególnej uwadze polecam metodę iterRemove, która w pełni polimorficzny sposób korzysta z całej mocy koncepcji  "usuwania elementów podczas iterowania kolekcji".

Aby przetestowac działanie klasy MKolekt wyobraźmy sobie na przykład, że chcemy stworzyć dwie kolekcje: gazet i studentów.
Elementy kolekcji (obiekty klas Journal i Student) będą tworzone na podstawie informacji zawartych w plikach (gazet i studentów). W pliku gazet podano tytuł i rok wydania, plik studentow zawiera nazwisko i ocenę.
Po stworzeniu kolekcji (gazet i studentów) będziemy chcieli usunąć z nich wszystkie elementy, które spelniają warunek: dla gazet - rok wydania mniejszy od 2000, dla student/ow - ocena mniejsza od 3.
Program, który wykonuje te działania może wyglądać następująco:

class Iter1 {

  public Iter1(String inGaz, String inStud) {
    List gazety = new ArrayList();
    Set  studenci = new HashSet();
    MKolekt.makeCollectionFromFile(gazety, inGaz, new Journal());
    MKolekt.makeCollectionFromFile(studenci, inStud, new Student());
    MKolekt.show(gazety);
    MKolekt.show(studenci);
    // ustalenie minimalnego roku wydania
    // gazety wydane wczesniej będą usunięte z kolekcji
    Journal.setLimitYear(2000);
    MKolekt.iterRemove(gazety);
    // ustalenie minimalnej oceny
    // studenci z oceną niższą będa usunięci z kolekcji   
    Student.setLimitMark(3);
    MKolekt.iterRemove(studenci);
    MKolekt.show(gazety);
    MKolekt.show(studenci);
  }

  public static void main(String args[]) {
    new Iter1(args[0], args[1]);  // argumenty: plik gazet, plik studentów
  }
}
Wynik działania tego programu może być następujacy:

Moja Szkoła 1999   // kolekcja wszystkich gazet
Moja Szkoła 2000
Moja Szkoła 2001
Psy 1997
Psy 1998
Psy 2000
Psy 2001

Stefan Miś 2.0            // kolekcja wszystkich studentów
Joanna Ptaszyna 4.5
Jan Kowalski 3.0
Jan Piesek 2.0

Moja Szkoła 2000      //  po usunięciu z kolekcji gazet sprzed 2000r.
Moja Szkoła 2001
Psy 2000
Psy 2001

Joanna Ptaszyna 4.5   // studenci po usunięciu tych z oceną < 3
Jan Kowalski 3.0


Dzięki wykorzystaniu ogólności architektury kolekcji oraz polimorficznych odwołań podobny - krotki - program możemy napisać dla dowolnych innych klas (nie tylko studentow czy gazet).

Klasy Journal i Student przedstawia poniższy wydruk (potrzeba implementacji interfejsu Comparable oraz zdefiniowania metod equals() i hashCode zostanie wyjaśniona za chwilę, w tym momencie nie ma to znaczenia):

class Journal implements CollectionHelper, Comparable {
  private String title;
  private int year;
  private static int retainAfter = 0;  // rok wydania,
                                       // od ktorego ew. zostawiać gazety

  public Journal() { }
  public Journal(String t, int y) {
    title = t;
    year = y;
  }


  public boolean isReadyToRemove() {
    return year < retainAfter;
  }

  // Tworzy Journal ze Stringu, w którym tytuł jest ujęty w cudzysłow
  // a za tytułem znajduje się rok wydania. Dodaje do kolekcji.
  public void makeObjectAndCollect(String s, Collection c){
    String title = "";
    int year = -1;
    try {
      StringTokenizer st = new StringTokenizer(s, "\"");
      title = st.nextToken();
      year = Integer.parseInt(st.nextToken().trim());
    } catch (Exception exc) { }
    Journal j =  new Journal(title, year);
    c.add(j);
  }

  public static void setLimitYear(int y) { retainAfter = y; }

  public boolean equals(Object obj) {
    return title.equals(obj);
  }

  public int compareTo(Object o) {
    return title.compareTo(o);
  }

  public int hashCode() { return title.hashCode(); }

  public String toString() { return title + " " + year; }
}

class Student implements CollectionHelper, Comparable {
  private String name;
  private double mark;             // ocena
  private static double minMark;   // minimalna ocena

  public Student() {}
  public Student(String nam, double m) {
    name = nam;
    mark = m;
  }

  public void setMark(double m) { mark = m; }

  public boolean isReadyToRemove() {
    return mark < minMark;
  }

  // Tworzy obiekt Student i dodaje do kolekcji
  public void makeObjectAndCollect(String s, Collection c) {
    StringTokenizer st = new StringTokenizer(s);
    String name = "", txt = "";
    double mark = 0;
    while (st.hasMoreTokens()) {
      try {
        txt = st.nextToken();
        mark = Double.parseDouble(txt);
        break;
      } catch (NumberFormatException exc) {
          name += txt + " ";
      }
    }
    Student stud = new Student(name.trim(), mark);
    c.add(stud);
  }

  // Ustalenie minimalnej oceny.
  // Studenci z niższą oceną mogą być usunięci z kolekcji.  
  public static void setLimitMark(double m) {
    minMark = m;
  }

  public boolean equals(Object obj) {
    return name.equals(obj);
  }

  public int compareTo(Object o) {
    return name.compareTo(o);
  }

  public int hashCode() { return name.hashCode(); }

  public String toString() { return name + " " + mark; }
}
Warto jeszcze raz zwrócić uwagę, że metody klasy MKolekt dzialają dla rożnego rodzaju kolekcji (ArrayList i HashSet) elementów dwóch bardzo róznych klas (Student i Journal).
Będą też działać dla dowolnych  innych rodzajów kolekcji (byleby implementowaly interfejs Collection) i dowolnych innych klas elementów (byleby implementowaly interfejs CollectionHelper).


Drugi przykładowy program ilustruje użyteczność operacji grupowych na (dowolnych) kolekcjach. Za jego pomocą analizujemy metody interfejsów kolekcyjnych. Wykorzystujemy przy tym tzw. refleksję, polegającą m.in. na zdolności uzyskiwania informacji o klasach i obiektach w trakcie wykonania programu.
O refleksji dowiemy się więcej w następnym semestrze, teraz komentarze zawarte w programie powinny wystarczyć dla zrozumienia jego działania, a uwagę powinniśmy skupić raczej na operacjach na kolekcjach wykonywanych w metodzie main.

import java.util.*;
import java.lang.reflect.*;

class Bulk1 {

  static ArrayList jcfMethods(String interfaceName) {

    // Uzyakanie obiektu, reprezentującego klasę (interfejs)
    // o podanej nazwie
    Class klasa = null;
    try {
     klasa = Class.forName("java.util." + interfaceName);
    } catch(ClassNotFoundException exc) { System.exit(1); }

    // Uzyskanie tablicy publicnych metod,
    // które mogą być używane wobec typu klasa
    // - zawierają rownież metody z nadklas i nadinterfejsów
  
    Method[] metody = klasa.getMethods();

    ArrayList lista = new ArrayList();  // lista metod

    // przebiegamy przez wszystkie dostępne metody
    for (int i=0; i<metody.length; i++) {

      // Uzyskanie tablicy typów parametrów danej metody
      Class[] param = metody[i].getParameterTypes();

      String opis = metody[i].getName() + "(";  // nazwa metody + znak (
      for (int j=0; j<param.length; j++) {
        String p = param[j].getName();          // nazwa typu parametru

        // ponieważ dla parametrow obiektowych nazwa typu
        // jest pelną kwalifikowaną nazwą klasy - "zdejmujemy kwalifikację"
        int l = p.lastIndexOf(".");
        if (l != -1) p = p.substring(l+1);
        opis += p + ',';
      }
      // ew. ostani przecinek dodany poprzednio - niepotrzebny
      if (opis.endsWith(",")) opis = opis.substring(0, opis.length()-1);
      opis += ")";
      lista.add(opis);
    }
    return lista;
  }

  static void showJcfMethods(String msg, Collection c) {
    System.out.println(msg);
    if (c.isEmpty()) System.out.println("Brak metod");
    for (Iterator it = c.iterator(); it.hasNext();) {
      System.out.println(it.next());
    }
  }

  public static void main(String args[]) {
   List collMet = jcfMethods("Collection");     // metody interfejsu Collection
   List listMet = jcfMethods("List");           // metody interfejsu Liat
   List setMet = jcfMethods("Set");             // metody interfejsu Set
   List sortedSetMet = jcfMethods("SortedSet"); // metody interfejsu SortedSet

   // Metody specyficzne dla list
   Set listOnly = new TreeSet(listMet);
   listOnly.removeAll(collMet);
   showJcfMethods("Metody specyficzne dla list", listOnly);

   // Metody specyficzne dla zbiorów uporządkowanych
   Set ssetOnly = new TreeSet(sortedSetMet);
   ssetOnly.removeAll(setMet);
   showJcfMethods("Metody specyficzne dla zbioru uporządkowanego", ssetOnly);

   // Metody wspólne dla list i zbiorów
   Set commonListAndSet = new TreeSet(listMet);
   commonListAndSet.retainAll(setMet);
   showJcfMethods("Metody wspólne dla listy i zbioru",
                   commonListAndSet);

   // Czy te ostatnie przypadkiem nie są po prostu metodami interfejsu Collection?
   commonListAndSet.removeAll(collMet);
   showJcfMethods("Czy wśród ostatnich są jakieś, ktorych nie ma w Collection?",
                   commonListAndSet);

  }
}
Program wyprowadzi pokazane wyniki.

Metody specyficzne dla list
add(int,Object)
addAll(int,Collection)
get(int)
indexOf(Object)
lastIndexOf(Object)
listIterator()
listIterator(int)
remove(int)
set(int,Object)
subList(int,int)
Metody specyficzne dla zbioru uporządkowanego
comparator()
first()
headSet(Object)
last()
subSet(Object,Object)
tailSet(Object)
Metody wspólne dla listy i zbioru
add(Object)
addAll(Collection)
clear()
contains(Object)
containsAll(Collection)
equals(Object)
hashCode()
isEmpty()
iterator()
remove(Object)
removeAll(Collection)
retainAll(Collection)
size()
toArray()
toArray(Object[])
Czy wśród ostatnich są jakieś, ktorych nie ma w Collection?
Brak metod




6.4. Listy i iteratory listowe


Lista jest ciągiem elementów uporządkowanych w tym sensie, że każdy element zajmuje określoną pozycję na liście.


JCF dostarcza dwoch implemantacji listy: tablicowej (klasa ArrayList) i  liniowej z podwójnymi dowiązaniami (klasa LinkedList).

Implementacja tablicowa polega na realizacji listy w postaci tablicy z dynamicznie (w miare potrzeby) zwiększającymi się rozmiarami. Elementy listy są zapisywane jako elementy takiej tablicy.
Ponieważ tablice w Javie mają określone (niezmienne po utworzeniu) rozmiary utworzenie listy tablicowej wymaga alokacji tablicy z jakimś zadaną rozmiarem. Jest on specyfikowany przez initialCapacity (domyślnie 10), który to parametr możemy podać w konstruktorze ArrayList, jeśli inicjalna pojemnośc nam nie odpowiada. Przy dodawaiuu elementow do listy sprawdzane jest czy pojemność tablicy jest wystarczająca, jeśli nie to rozmiar tablicy jest zwiększany, Służy temu metoda ensureCapacity(minCapacity), któeą zresztą możemy wywolać sami, aby w trakcie działania programu zapewnić podaną jako minCapacity pojemność listy.

Uproszczone fragmenty realizacji klasy  ArrayList (autorem jest Josh Bloch, główny twórca JCF) przedstawiono poniżej.
public class ArrayList implements List // ...
{
    private transient Object elementData[];
    private int size;

    public ArrayList(int initialCapacity) {
      this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
      this(10);
    }

    public void ensureCapacity(int minCapacity) {
      // ,,,
      int oldCapacity = elementData.length;
      if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity) newCapacity = minCapacity;
        elementData = new Object[newCapacity];
        System.arraycopy(oldData, 0, elementData, 0, size);
      }
    }

    public boolean add(Object o) {
      ensureCapacity(size + 1);
      elementData[size++] = o;
      return true;
    }
// ...
}
Źrodło: Josh Blosh, klasa ArrayList (źródła)

Jak widać,  w przypadku braku miejsca na dodanie nowego elementu rozmiary tablicy zwiększają się  nie o 1, ale o pewien współczynnik. Dzięki temu realokacje tablicy i przepisywanie jej elementów nie muszą być wykonywane zbyt często.

Implementacja liniowa z podwójnymi dowiązaniami umieszcza dane w strukturach danych - nazwiemy je wiązaniami (link ) - które zawierają wskaźniki do poprzedniego i następnego elementu listy (dlatego dowiązania są "podwójne", niejako dwukierunkowe). Zatem elementy listy, które z punktu widzenia programisty są elementami umieszczanych danych (np. nazwisk lub jakichś innych obiektów), technicznie są "linkami", zawierającymi nie tylko dane, ale również  wskaźniki na następny i poprzedni element na liście.
Początek listy dowiązaniowej, zwany głową lub wartownikiem zawiera wskazanie na pierwszy element listy (null, jeśli lista jest pusta).

Ilustruje to poniższy rysunek:
r
Objaśnienia:
first - wskazanie na pierwszy element listy,
data - dane elementu,
next - wskazanie na następny element na liście
prev - wskazanie na poprzedni element lsity

Źródło: Cay S. Horstmann, Gary Cornell. Core Java 2. Sun Microsystem Press, 1999


Każda lista (niezależnie od implementacji) umożliwia wykonywanie następujących operacji (ktore są specyfikowane przez interfejs List).

Operacje na liście
wszystkie metody interfejsu Collection
Ogóne operacje właściwe dla wszelkich kolekcji (np. add, remove, contains, operacje gupowe)
boolean add(int p, Object elt)              Dodaje element na pozycji p. Zwraca true jeśli lista została zmodyfikowana.
boolean addAll(int  p, Collection c)                            Dodaje wszystkie elementy kolekcji c do listy poczynając od pozycji p. Zwraca true jeśli lista została zmodyfikwoana.
Object get(int p)Zwraca element na pozycji p
int indexOf(Object elt)Zwraca pozycję (indeks) piewrszego wystapienia elementu elt
int lastIndexOf(Object elt)Zwraca indeks ostatniego wystąpienia elementu elt
ListIterator listIterator()Zwraca iterator listowy, ustawiony na początku listy (przed pierwszym elementem).
ListIterator listIterator(int p)Zwraca iterator listowy ustawiony przed  elementem o indeksie p.
boolean remove(int p)Usuwa element na pozycji p. Zwraca true jeśli lista została zmodyfikwoana.
Object set(int p,Object val)Zastępuje element na pozycji p podanym elementem elt. Zwraca poprzednio znajdujący się na liście  element.
List subList(int f, int l)Zwraca podlistę zawierającą elementy listy od pozycji f włacznie do pozycji l (wyłącznie).
Uwagi:
  1. wszystkie operacje modyfikującę listę strukturalnie lub pod względem zawartości są opcjonalne,
  2. pozycje na liście numerowane są od 0 (tak jak indeksy w tablicy).
Jak widać, operacje na liście rozszerzają możliwości operowania na kolekcjach o operacje pozycyjne - takie, które uzwględniają pozycję elementów.
Ze względu na znajomość pozycji elementów w kolekcji możliwe staje się iterowanie po kolekcji w obie strony: od początku i od końca. Można też ustawić iterator w taki sposób, by iteracje rozpoczynały się od podanej pozycji, a znając pozycję elementu zwracanego przez iterator można nie tylko go usunąc, ale zamienić lub dodać nowy element na pozycji wyznaczanej przez stan iteratora.
Dlatego właśnie oprócz zwyklego (ogólnego dla wszystkich kolekcji) iteratora, listy udostępniają iteratory listowe, które są obiektami klas implementujących interfesj ListIterator. Ten ostatni jest rozszerzeniem interfejsu Iterator.

Operacje iteratora listowego
 voidadd(Object o)
          Dodaje podany element do listy na pozycji wyznaczanej przez iterator. (operacja opcjonalna).
 booleanhasNext()
          Zwraca true, jeśli są jeszcze elementy na liście, w sytuacji iterowania od początku do końca.
 booleanhasPrevious()
          Zwraca true, jeśli są jeszcze elementy na liście w sytuacji iterowania od końca do początku.
 Objectnext()
          Zwraca następny element na liście i przesuwa iterator.
 intnextIndex()
          Zwraca indeks elementu, który byłby zwrócony przez odwołanie do next().
 Objectprevious()
          Zwraca poprzedni element na liście i przesuwa iterator.
 intpreviousIndex()
          Zwraca indeks elementu, któy byłby zwrócony przez odwolanie previous.
 voidremove()
          Usuwa z  listy ostatni element który byl zwrocony przez ostatnie odwołanie next lub previous (operacja opcjonalna).
 voidset(Object o)
          Zastępuje element zwrocony prez next lub previous podanym elementem (operacja opcjonalna).
Uwagi:
  1. konkurencyjne modyfikacje wartości elementów listy w trakcie iteracji za pomocą iteratora listowego nie są wykrywane,
  2. w przeciwieństwie  do metody add z interefejsu Collection metoda add iteratora listowego nie zwraca żadnego wyniku: na liście operacja dodawania zawsze jest skuteczna.

Jak pamiętamy, iterator zajmuje pozycję pomiędzy elementami. Kolejne odwołanie do next() lub previous() powoduje, że iterator "przeskakuje" zwrócony element. W tym miejscu wlaśnie zostanie wpisany element, jeśli użyjemy metody add.
Natomiast metoda remove() usuwa  zawsze element zwrócony przez ostatnie odwolanie do next() lub previous().
 
Szczególnie przy stosowaniu iteratora listowego należy pamiętać o tym, że iterator "zajmuje pozycję" pomiędzy elementami



Ilustruje to poniższy program, który pokazuje kolejne postępy iteracji i zmiany na liście na skutek zastosowania metod add i remove.

import java.util.*;
class ListIter1 {

  static void state(ListIterator it) {
    int pi = it.previousIndex(),
        ni = it.nextIndex();
    System.out.println("Iterator jest pomiędzy indeksami: " + pi + " " + ni);
  }


  public static void main(String args[]) {
    LinkedList list = new LinkedList(Arrays.asList(
                           new String[] { "E0","E1", "E2", "E3" }
                           ));
    ListIterator it = list.listIterator();
    it.next();
    state(it);
    it.add("nowy1");
    System.out.println(list.toString());
    it.next();
    it.next();
    it.previous();
    state(it);
    it.add("nowy2");
    System.out.println(list.toString());
    it.previous();
    it.previous();
    state(it);
    it.remove();
    System.out.println(list.toString());
  }
}
Wydruk:

Iterator jest pomiędzy indeksami: 0 1
[E0, nowy1, E1, E2, E3]
Iterator jest pomiędzy indeksami: 2 3
[E0, nowy1, E1, nowy2, E2, E3]
Iterator jest pomiędzy indeksami: 1 2
[E0, nowy1, nowy2, E2, E3]


Przy okazji tego programu zwróćmy uwagę na wygodną metodę asList z klasy Arrays, która zwraca podaną jako argument tablicę w postaci listy. Wynikiem jest lista nierozszarzalna (bo tablice nie mogą zmieniać swoich rozmiarów), ale ponieważ za pomocą konstruktora klasy LinkedList tworzymy z tej kolekcji normalną listę (implementacja liniowa z podwójnymi dowiązaniami), to będziemy mogli do niej dodawać nowe elementy.
Warte uwagi jest także to, że w klasach kolekcyjnych metoda toString() została zdefiniowana w taki sposob, że zwraca napisową reprezentację zestawu elementów kolekcji. Dzięki temu w tym prostym programiku testującym mogliśmy łatwo śledzieć zmiany zestawu elmentów na liście.


Mimo, że w programach działających na listach posługiwać się będziemy metodami interfejsu List (niejako niezależnie od implementacji), to wybór implementacji listy nie jest obojętny dla efektywności dzialania naszego programu.

Praktycznie implementację liniową z podwójnymi dowiązaniami (LinkedList) powinniśmy wybierać tylko wtedy, gdy na liście będą wykonywane częste operacje wstawiania i/lub usuwania elementów w środku listy (poza końcem listy).
Istotnie na liście typu LinkedList takie operacje polegają na zmianie dwóch dowiązań (prowadzącego do poprzedniego i do następnego elementu) - są więc bardzo szybkie, zaś w implementacji tablicowej (ArrayList) wiążą się z przepisywaniem elementów tablicy, co (zwykle) zabiera więcej  czasu.

Usunięcie elementu na liście LinkedList:
r

Dodanie elementu na liście LinkedList:
r

Źródło: Cay S. Horstmann, Gary Cornell. Core Java 2. Sun Microsystem Press, 1999


Taka sama operacja dodania elmentu na ArrayList jest znacznie bardziej kosztowna, o czym przekonuje nas (uproszczony) fragment realizacji klasy ArrayList:
    public void add(int index, Object element) {
	// ...
	ensureCapacity(size+1);
        // Przesunięcie - czyli przekopiowanie elementów tablicy!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

Źrodło: Josh Blosh, klasa ArrayList (źródła)

Z kolei, operacje  bezpośredniego dostępu do elementów listy są w implementacji tablicowej ArrayList natychmiastowe (polegają na indeksowaniu tablicy), natomiast w implementacji LinkedList są bardzo nieefektywne, gdyż technicznie wymagają przebiegania po elementach listy od samego jej początku lub od końca w kierunku początku (ten ostatni przypadek jest jedyną  optymalizacją dostępu w klasie LinkedList, dokonywaną wtedy, gdy indeks znajduje się "w drugiej polowie" listy).

Poniższy program mierzy czas poszczegolnych operacji dla dwóch implementacji list.
import java.util.*;

class Lists {

  long start;

  void setTimer() { start = System.currentTimeMillis(); }
  long elapsed() { return System.currentTimeMillis() - start; }

  public Lists(int n) {
    ArrayList aList = new ArrayList(n);
    for (int i=0; i < n; i++) aList.add("a");
    LinkedList lList = new LinkedList(aList);
    setTimer();
    randomAccess(aList);
    System.out.println("Swobodny dostęp do ArrayList: " + elapsed() + " ms");
    setTimer();
    randomAccess(lList);
    System.out.println("Swobodny dostęp do LinkedList: " + elapsed() + " ms");
    setTimer();
    insert(aList);
    System.out.println("Wpisywanie na ArrayList: " + elapsed() + " ms");
    setTimer();
    insert(lList);
    System.out.println("Wpisywanie na LinkedList: " + elapsed() + " ms");
  }

  void randomAccess(List l) {
    Random rand = new Random();
    for (int i=0; i<10000; i++) {
      int index = rand.nextInt(l.size());
      String s = (String) l.get(index);
      s = s + "a";
      l.set(index, s);
    }
  }

  void insert(List l) {
    ListIterator iter = l.listIterator();
    int i = 0;
    while (iter.hasNext()) {
      iter.next();
      if (i % 2 != 0) iter.add("b");
      i++;
    }
  }


  public static void main(String args[]) {
    new Lists(Integer.parseInt(args[0]));
  }
}
Metoda randomAccess 10000 razy zmienia elementy pod losowo wybranymi indeksami, a metoda insert() po każdym elemencie o nieparzystym indeksie dopisuje jakiś nowy element.

Wynik dzialania programu (dla list 100000 elementów) pokazano poniżej.

Swobodny dostęp do ArrayList: 330 ms
Swobodny dostęp do LinkedList: 62560 ms
Wpisywanie na ArrayList: 56690 ms
Wpisywanie na LinkedList: 650 ms


Na listach  LinkedList nie należy nigdy stosować operacji get(int index) i set(int index, Object value)


Skoro jednak powinniśmy pisać nasze kody (szczególnie metody) w kategoriach interfejsów kolekcyjnych, a nie konkretnych implementacji, to jak rozpoznać z jaką implementacją mamy do czynienia i czy można wykorzystać jej zalety i uniknąć wad?

Służy temu interfejs znacznikowy RandomAccess. Wszystkie implementacje list, które umozliwiają swobodny dostęp w czasie stałym, a więc szybsze wykonanie pętli:
for (int i=0, n = list.size(); i<n; i++) list.get(i);
niż pętli:
for (Iterator iter = list.iterator(); iter.hasNext(); ) iter.next();
powinny go implementować (np. klasa ArrayList implementuje ten interfejs, a LinkedList - nie)

W naszych kodach możemy sprawdzić, czy implementacja umożliwia efektywny dostęp swobodny poprzez użycie konstrukcji list instanceof RandomAccess.

Klasa LinkedList nadaje się doskonale do implementacji specjalnych rodzajów list - stosów i kolejek.

Stos (ang. stack) jest listą, na której możliwe są tylko następujące operacje wstawiania, pobierania i usuwania elementów:


Dla wykonywania operacji na liście tak jak na stosie w klasie LinkedList zdefiniowano metody o samoobjaśniających się nazwach: addFirst(Object), getFirst(Object) i removeFirst(Object).

Kolejka (ang. queue) jest listą, na której możliwe są tylko następujące operacje wstawiania, pobierania i usuwania elementów:


Dla wykonywania operacji na liście tak jak na kolejce w klasie LinkedList zdefiniowano metody o samoobjaśniających się nazwach: addLast(Object), getLast(Object) i removeLast(Object).

Lista na której możliwe są zarówno w/w operacje stosowe jak i kolejkowe nazywa się kolejką podwójną (ang. dequeue)


Generalnie więc klasa LinkedList jest kolejką podwójną.

Wyszukiwanie elementów na listach (czy to klasy ArrayList czy LinkedList) za pomocą ogólnych metod interfejsu Collection (contains(Object) oraz indexOf(Object)) nie jest efektywne.
Jeśli zależy nam na szybkim odnajdywaniu elementów - powinniśmy albo zastosować inny rodzaj kolekcji (np. zbiory w implementacji tablic mieszania), albo posortować listę (metoda sort) i zastosować wyszukiwanie binarne (metoda binarySearch). Obie te metody są implementacjami algorytmów kolekcyjnych, dostarczanych w klasie Collections.

Obie implementacje list - ArrayList i LinkedList nie są przeznaczone do użycia współbieżnego (nie są wielowątkowo bezpieczne). Zapewnienie możliwości współdzielenia kolekcji przez wiele wątków wymaga synchronizacji, co jest czasowo kosztowne.
Zatem tylko na wyraźne życzenie programisty - poprzez stworzenie synchronizowanego widoku kolekcji (zob. punkt o widokach kolekcji) - można uzyskać listy wielowątkowo bezpieczne.
Istnieje również możliwość wykorzystania klasy Vector, która - od dawna obecna w Javie - jest obecnie niczym innym jak synchronizowaną wersją klasy ArrayList.



6.5. Zbiory. Haszowanie i porządkowanie.


Zbiór jest kolekcją elementów bez ustalonego porządku ich występowania w kolekcji oraz bez duplikatów, tj. kolekcją nie zawierającą dwóch takich samych elementów


Z punktu widzenia operowania na zbiorach mamy do dyspozycji metody interfejsu Set (które są takie same jak omówione wcześniej metody interfejsu Collection). Jedyne uszczegółowienie polega na tym, że w przypadku zbiorów, metody dodające elementy do zbiorów zwracają wartość false, jeśli dodawane elementy już w zbiorze występują.

Zatem przy dodawaniu elementu do zbioru musi nastąpić sprawdzenie czy zbiór nie zawiera już dodawanego elementu. 
Słowo "mieszanie" używane w polskiej literaturze jako tłumaczenie słowa "hash" jest w tej chwili stosowane równolegle lub nawet wypierane przez słowo "haszowanie"
Są przynajmniej dwa sposoby efektywnego sprawdzania tego. Pierwszy (użycie tablicy mieszającej) jest zrealizowany w klasie HashSet, drugi (wyszukiwanie binarne z użyciem drzewa czerwono-czarnego) - w klasie TreeSet.

Tablica mieszania (hashtable) jest strukturą danych specjalnie przystosowaną do szybkiego odnajdywania elementów. Dla każdego elementu danych wyliczany jest kod numeryczny (liczba całkowita) nazywany kodem mieszania (hashcode), na podstawie którego obliczany jest indeks w tablicy, pod którym będzie umieszczony dany element. Może się zdarzyć, że kilka elementów otrzyma ten sam indeks, zatem elementy tablicy mieszającej stanowią listy, na których znajdują się elementy danych o takim samym indeksie, wyliczonym na podstawie ich kodów mieszania.

Każda lista - element tablicy mieszania nazywa się kubełkiem (bucket).
Aby umieścić nowy element w tablicy mieszania, wyliczany jest jego hashcode , po czym na podstawie jego wartości obliczany jest indeks w tablicy mieszania. Indeks taki stanowi resztę z dzielenia wartości kodu mieszania przez liczbę kubełków. Element umieszczany jest w kubełku pod tym indeksem.

Istotne jest w tej procedurze, by:

W Javie można wyliczyć kod mieszania dla każdego obiektu za pomocą zastosowania metody hashCode() . Metoda ta, zdefiniowana w klasie Object, daje - ogólnie - jako wynik adresy obiektów. To, oczywiście, nie jest zbyt użyteczne, bowiem nie bierze pod uwagę zawartości obiektów (wszystkie obiekty mają rożne kody mieszania). Ale w standardowych klasach Javy metoda hashCode() została przedefiniowana, tak, by zwracała kod na podstawie "treści" obiektu, np. napisu stanowiącego "zawartość" obiektu klasy String. Dwa takie same napisy będą miały te same kody mieszania.

Zobaczmy na przykładzie jak wygląda umieszczanie i wyszukiwanie elementow w tablicy mieszania. Napisy "a", "b", "c", "d", "e", "f'", "g", "h", "i" będą umieszczone w tablicy o 7 kubełkach w następujacy sposób.

r

Odpowiednie kody mieszania dla kolejnych napisów, oraz odpowiadające im indeksy  tablicy (reszta z dzialenia kodu przez liczbę kubełków) są następujące:

a kod: 97 indeks: 6
b kod: 98 indeks: 0
c kod: 99 indeks: 1
d kod: 100 indeks: 2
e kod: 101 indeks: 3
f kod: 102 indeks: 4
g kod: 103 indeks: 5
h kod: 104 indeks: 6
i kod: 105 indeks: 0

Jak widać, indeksy dla 'b' oraz 'i', a także dla 'a' oraz 'h' są takie same, wobec tego napisy znajdują się pod tym samym indeksem (w tym samym kubelku) jako kolejne elementy listy.

Łatwo zauważyć, że wyszukanie elementu w tablicy mieszania jest bardzo efektywne. Wystarczy obliczyć indeks tablicy na podstawie kodu mieszania szukanego elementu i jeżeli w danym kubełku jest tylko jeden element, to - nawet nie wykonując żadnych porównań - zwrócić ten element (lub wartość true - że jest). Jeżeli w kubełku jest kilka elementów, to musimy wykonać ich porównanie z szukanym elementem, ale i tak liczba porównań będzie zwykle bardzo niewielka w stosunku do liniowego czy nawet binarnego wyszukiwania.

Prostą, ilustracyjną  implementację zbioru jako tablicy mieszania pokazuje poniższy program, będący jednocześnie narzędziem do śledzenia co dzieje się z elementami, jakie mają kody mieszania, jak są wstawiane i jak mogą być odszukane.

import java.util.*;

public class Hash {

  final int NB = 7; // liczba kubełków

  LinkedList[] hashTab = new LinkedList[NB];	// tablica mieszania

  public Hash() {
    for (int i=0; i<NB; i++) hashTab[i] = new LinkedList();
    String[] napisy = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "a" };
    for (int i=0; i<napisy.length; i++) insert(napisy[i]);
    for (int i=0; i<NB; i++) {
      String report = i + " - ";
      Iterator it = hashTab[i].iterator();
      while (it.hasNext()) {
        report += " - " + it.next();
      }
      System.out.println(report);
    }
    System.out.println("Czy zawiera *a* ? - " + contains("a"));
    System.out.println("Czy zawiera *k* ? - " + contains("k"));
  }

  public void insert(String s) {
    int hashCode = s.hashCode();
    int index = hashCode % NB;
    boolean isThere = isThere(index, s);
    if (!isThere) hashTab[index].add(s);
    System.out.println(s + " kod: " + hashCode +
                           " indeks: " + index +
                           (isThere ? " już tam jest" : " został dodany") );
  }

  public boolean contains(String s) {
     return isThere(s.hashCode() % NB, s);
  }

  private boolean isThere(int index, String s) {
    for (Iterator i = hashTab[index].iterator(); i.hasNext(); )
        if (s.equals(i.next())) return true;
    return false;
  }

  public static void main(String args[]) {
    new Hash();
  }
}
Wyniki działania programu:

a kod: 97 indeks: 6 został dodany
b kod: 98 indeks: 0 został dodany
c kod: 99 indeks: 1 został dodany
d kod: 100 indeks: 2 został dodany
e kod: 101 indeks: 3 został dodany
f kod: 102 indeks: 4 został dodany
g kod: 103 indeks: 5 został dodany
h kod: 104 indeks: 6 został dodany
i kod: 105 indeks: 0 został dodany
a kod: 97 indeks: 6 już tam jest
0 -  - b - i
1 -  - c
2 -  - d
3 -  - e
4 -  - f
5 -  - g
6 -  - a - h
Czy zawiera *a* ? - true
Czy zawiera *k* ? - false


W podobny sposób mógłby być implementowany  HashSet (tak naprawdę mamy tam listę liniową z pojedyńczymi dowiązaniami, w programie ilustracyjnym skorzystaliśmy dla wygody z gotowej klasy LinkedList).

Zwróćmy szczególną uwagę (również na przykładzie ilustracyjnego programu), że oprócz wyliczania kodów mieszania do prawidłowego dodawania i odnajdywania elementów potrzebne jest odpowiednie zdefiniowanie metody equals(), porownującej "treść" dwóch obiektów.


Jeżeli prawdziwe jest a.equals(b),
to musi być spełniony warunek
a.hashCode() == b.hashCode().


Oczywiście, zarowno hashCode() jak i equals() są dobrze zdefiniowane w standardowych klasach Javy.

Tworząc wlasne klasy musimy sami zadbać o właściwe zdefiniowanie metod hashCode() i equals().

Należy pamiętać, że przedefiniowujemy metodę equals z klasy Object. A tam jej parametrem jest Object. Użycie innego typu parametru prowadzi do przeciążenia (a nie przedefiniwonia) metody i uniemożliwia polimorficzne do niej odwołania.


Metodę hashCode definiujemy w klasie jako:

public int hashCode() {
// obliczenie kodu mieszania na podstawie wartości pól klasy (elementów obiektu)
// dla pól obiektowych użyjemy metody hashCode() z ich klas
// staramy się przy tym zapewnić odpowiednie zróżnicowanie kodów
}

Metodę equals definiujemy w następujący sposób:

public boolean equals(Object obj) {  
   // jeżeli porównywane obiekty należą do różnych klas - nie są równe!
    if (obj == null || getClass() != obj.getClass()) return false;
   // tu porównujemy zwartość obiektów i zwracamy true lub false
}


Przykład.

import java.util.*;

class Worker {
  private String lname;
  private String fname;
  private int salary;

  public Worker(String fn, String ln, int sal) {
    lname = ln;
    fname = fn;
    salary = sal;
  }

  public int hashCode() {
    return 11*lname.hashCode() + 19*fname.hashCode();
  }

  public boolean equals(Object obj) {
    if (obj == null || getClass() != obj.getClass()) return false;
    Worker w = (Worker) obj;
    return fname.equals(w.fname) && lname.equals(w.lname);
  }

  public String toString() {
    return fname + " " + lname + " " + salary;
  }


  public static void main(String args[]) {
    Worker[] p = { new Worker("Jan", "Kowalski", 1000),
                   new Worker("Jan", "Malinowski", 1200),
                   new Worker("Jan", "Kowalski", 1400)
                  };
    Set set = new HashSet();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());
  }
}
Obiekty klasy Worker różnią się, jeśli pracownicy mają inne imiona i nazwiska (w realnym programowaniu powinniśmy użyć jakiejś bardziej jednoznacznej identyfikacji). Kod mieszania jest zgodny z equals(), bo równe kody implikują true jako wynik equals. To jednak nie znaczy, że rózne obiekty nie mogą mieć takich samych kodów mieszania. O przynależności do zbioru ostatecznie decyduje metoda equals(), hashcode jest tylko po to by umieścić obiekt w tablicy mieszania.
Podkreślmy też jeszcze raz, że we właściwie skonstruowanej klasie zawsze powinniśmy dostarczyć metody toString(). Gdyby jej nie było w powyższym przykładzie, to program wyprowadziłby niewiele znaczace napisy (wyniki toString z klasy Obejct), a tak daje nam całkiem sensowny rezultat:
[Jan Malinowski 1200, Jan Kowalski 1000]

Widzimy, że do zbioru nie zostały dodane duplikaty (dwa obiekty "Jan Kowalski"), i że o tym zdecydowała metoda equals.

Porządek elementów kolekcji HashSet nie jest okreslony.
Klasa LinkedHashSet, dziedzicząc klasę HashSet udostępnia wygodną często właściwość: zachowania porządku, w jakim elementy dodane były do zbioru. Gdybyśmy zatem w poprzednim programie zmienili kod na:
    Set set = new LinkedHashSet();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());
to otrzymalibyśmy wynik odtwarzający "historię" zapełniania zbioru:
[Jan Kowalski 1000, Jan Malinowski 1200]



Inna podstawowa implementacja koncepcji zbioru - klasa TreeSet, opiera się na strukturze danych zwanej drzewem czerwono-czarnym. Dla potrzeb korzystania z klasy TreeSeet wystarczy wiedzieć, że zapewnia ona szczególne uporządkowanie elementów zbioru, które pozwala szybko odnajdywać w nim podany element.
Sczegółowe omówienie tej struktury danych wykracza poza ramy niniejszego materiału, nie ma też miejsca by przedstawić tu pojęcie drzewa (zainteresowanym można polecić książkę L. Banachowskiego, K.Diksa, W. Ryttera. Algorytmy i struktury danych, WNT 2001).

Zwróćmy tylko uwagę (dla zainteresowanych), że drzewo czerwono-czarne jest drzewem wyszukiwań binarnych (BST) o następujących właściwościach:
  1. Z każdym węzłem drzewa związana jest wartość
  2. Wartość ta jest większa od wartości lewego potomka i mniejsza od wartości prawego potomka
  3. Z każdym węzłem związany jest atrybut koloru - czerwony lub czarny
  4. Każdy czerwony węzeł, ktory nie jest liściem ma tylko czarnych potomków
  5. Każda ścieżka od korzenia do liścia zawiera tyle samo czarnych węzłów
  6. Korzeń jest czarny.
Dzięki tym właściwościom drzewo czerwono-czarne może zachowywać właściwość zrównoważenia przy modyfikacjach (tzn. równoważenie nie jest kosztowne), co w konsekwencji daje szybkie operacje dodawania i wyszukiwania elementów.
Inaczej mówiąc, elementy są dodawane do drzewa w określony sposób, taki mianowicie, że wysokość drzewa nie jest zbyt wielka (zrównoważenie), a jednocześnie wyszukiwanie może korzystać z "porządku symetrycznego", okreslanego przez punkt 2 w/w właściwości drzewa czerwono-czarnego.

Na przykładzie z poniższego rysunku dla odnalezienia elementu 7 potrzebne są tylko 3 porównania.

r
Źrodło: John Morris, Data Structures and Algorithms, University of Western Australia, 1998

Jak widać, struktura ta pozwala na "odtwarzanie" danych w określonym porządku elementów.

Dlatego klasa TreeSet realizuje nie tylko koncepję zbioru "w ogóle" , ale również zbioru uporządkowanego, implementując interfejs SortedSet, który rozszerza interfejs Set.

Widzieliśmy już jak iterowanie po TreeSet zwraca elementy w porządku rosnącym.
Np. poniższy fragment:
    String[] s = {"ala", "pies", "kot" };
    Set set = new TreeSet();
    for (int i=0; i < p.length; i++) set.add(s[i]);
    System.out.println(set.toString());
wypisze:
[ala, kot, pies]



Ale skąd wiadomo jaki ma być porządek elementów? Zapewne zależy to od klasy obiektów, będących elementami zbioru. Dla klasy String było wszystko w porządku (uzyskaliśmy alfabetyczny porządek elementów zbioru). Ale co by się np. stało, gdyby w poprzednim programie (przykład klasy Worker) zmienić implementację zbioru z HashSet na TreeSet?
Cóż, spotkałaby nas niemiła niespodzianka: wyjątek ClassCastException.
Widać czegoś naszej kalsie Worker brakuje.

Dochodziimy w ten sposób do ważnego tematu - porównywania obiektów przy porządkowaniu kolekcji.


6.6. Porównywanie obiektów

Dodawanie elementów do zbiorów uporządkowanych (TreeSet), iterowanie po kolekcjach uporządkowanych,  a także sortowanie kolekcji algorytmami kolekcyjnymi odbywa się w oparciu o:
Naturalny porządek określany jest przez implementację interfejsu Comparable w klasie obiektów i dostarczenie definicji metody compareTo tego interfejsu, porównującej dwa obiekty.

Metoda compareTo ma następującą sygnaturę:

    public int compareTo(Object otherObject)

i zwraca:


Wiele klas standardu Javy implementuje interfejs Comparable (np. klasa String, Date, klasy opakowujące typy pierwotne). We własnych klasach musimy o to zadbać sami.

Zatem, każda nasza klasa, której obiekty mogą być elementami kolekcji uporządkowanych powinna określać naturalny porządek swoich obiektow.

Np. w klasie Worker moglibyśmy ustalić, że naturalną kolejnością obiektów jest alfabetyczna kolejność nazwisk w porządku rosnącym poprzez dostarczenie definicji metody compareTo :

class Worker implements Comparable {
  private String lname;
  private String fname;
  // ...
  public int compareTo(Object otherObj) {
    return this.lname.compareTo(((Worker) otherObj).lname);
  }   
  // ...
}
Zwrócmy uwagę, że typem parametru jest Object i trzeba dokonać zawsze konwersji zawężającej. Jeżeli taka konwersja jest niedozowolona, to powstanie wyjątek ClassCastException. Jest to sensowne zachowanie: cóż miałaby bowiem zwrócić metoda compareTo, jesli porównujemy obiekty niewłaściwych klas?

Po tej modyfikacji klasy i jej wykorzystaniu w poniższym fragmencie:
    Worker[] p = { new Worker("Jan", "Kowalski", 1000),
                   new Worker("Jan", "Malinowski", 1200),
                   new Worker("Jan", "Kowalski", 1400),
                   new Worker("Jab", "Kowalewski", 2000),
                 };

    Set set = new TreeSet();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());
otrzymamy (naturalnie) uporządkowany wynik:
[Jab Kowalewski 2000, Jan Kowalski 1000, Jan Malinowski 1200]


No, dobrze, ale jak uzyskać różne zbiory, uporządkowane wedlug różnych kryteriów, np. według nazwisk lub według pensji? Albo porządek odwrotny do naturalnego (np. w malejącym alfabetycznym porządku nazwisk) ?

Tu przychodzi na pomoc koncepcja komparatora.

Komparator jest obiektem porównującym inne obiekty


Komparatory w Javie są realizowane jako obiekty klas implementujących interfejs Comparator.
Interfejs ten zawiera ważną metodę:

    int compare(Object o1, Object o2)

której implementacja winna  porównywać dwa swoje argumenty i zwracać wynik 0 jeśli oba obiekty są równe, liczbę mniejszą od 0, jeśli o1 jest "mniejszy" od o2 oraz liczbę większą od 0, jeśli o1 jest "większy" od o2.

Uwaga: oprócz tego interfejs Comparator zawiera metodę equals, ale sluży ona do stwierdzania, czy ten obiekt-komaparator jest taki sam jak inny obiekt-komparator i nie należy mylić jej użycia zs stwierdzaniem równości obiektów porównywanych przez komparator. Nb ponieważ metoda ta jest zdefiniowana w klasie Object (a każda klasa dziedziczy klasę Object), to nie jesteśmy zmuszeni do jej implementacji, jeśli nie chcemy porównywać komparatory na równość.

Obiekt komparator może być podany jako argument konstruktora klasy TreeSet (i wtedy to on, a nie naturalny porządek, decyduje o sposobie wpisywania elementów do zbioru) , może rownież występowac jako argument metod sortowania z klasy Collections oraz konstruktorów innych kolekcji uporządkowanych (np. TreeMap).

Specjalny komparator, odwracający naturalny porządek, uzyskiwany jest za pomocą statycznej metody klasy Collections - Collections.reverseOrder().


Zobaczmy to na przykładzie różnego porządkowania zbioru pracownikow (klasa Worker).
import java.util.*;

class Worker implements Comparable {
  private String lname;
  private String fname;
  private int salary;

  public Worker(String fn, String ln, int sal) {
    lname = ln;
    fname = fn;
    salary = sal;
  }

  public int getSalary() { return salary; }

  public int compareTo(Object otherObj) {
    return this.lname.compareTo(((Worker) otherObj).lname);
  }

  public String toString() {
    return fname + " " + lname + " " + salary;
  }


  public static void main(String args[]) {
    Worker[] p = { new Worker("Jan", "Kowalski", 1000),
                   new Worker("Jan", "Malinowski", 1200),
                   new Worker("Jan", "Kowalski", 1400),
                   new Worker("Jan", "Kowalewski", 2000),
                 };
    // Ziór uporządkowany wg porządku naturalnego (rosnąca kolejność nazwisk)
    Set set = new TreeSet();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());

    // Zbiór uporządkowany wg rosnących pensji
    Set set2 = new TreeSet(new Comparator() {
                   public int compare(Object o1, Object o2) {
                     // różnica pensji wystarczy do porownania:
                     return ((Worker) o1).getSalary() -
                            ((Worker) o2).getSalary();
                   }
               });
    for (int i=0; i < p.length; i++) set2.add(p[i]);
    System.out.println(set2);

    // Zbiór uporządkowany w malejącym porządku naturalnym (malejące nazwiska)
    Set set3 = new TreeSet(Collections.reverseOrder());
    for (int i=0; i < p.length; i++) set3.add(p[i]);
    System.out.println(set3);

  }
}
Program wyprowadzi:

[Jan Kowalewski 2000, Jan Kowalski 1000, Jan Malinowski 1200]
[Jan Kowalski 1000, Jan Malinowski 1200, Jan Kowalski 1400, Jan Kowalewski 2000]
[Jan Malinowski 1200, Jan Kowalski 1000, Jan Kowalewski 2000]


Ciekawe, że w powyższym przykładzie w klasie Worker nie było metody equals() ani hashCode(). Po prostu, TreeSet ich nie potrzebuje.
Zwróćmy też uwagę, że komparator przesądza nie tylko o kolejności iterowania po zbiorze, ale również o tym, czy obiekty uznawane są za nierówne i czy wobec tego mogą stanowić elmenty zbioru (przykład z pwotórzeniem nazwiska Jan Kowalski, gdy komparator porównywał pensje),

Należy pamiętać, że:


Oczywiście, nasze klasy powinny być przygotowane do tego, że ich obiekty mogą znaleźć się w zbiorach typu HashSet albo TreeSet, zatem powinny definiować wszystkie wspomniane metody. A do tego w sposob spójny: jeśli equals zwraca true, to compareTo winno zwracać zero, a hashCode te same wartości dla obu porównywanych obiektów.

Warto zauważyć, że dla zbiorów uporządkowanych (naturalnie lub za pomocą komparatora) dostępna jest możliwośc uzyskiwania "pierwszego" lub "ostatniego" (w zdefiniowanym porządku) elementu, a także podzbiorów, które zawierają elementy "od" - "do" (w zdefiniowanym porządku). Służą temu metody interfejsu SortedSet (implementowanego przez TreeSet).

Metody interfejsu SortedSet
 Comparatorcomparator()
          Zwraca komparator ustalony dla tego zbioru lub null, jeśli porządek jest naturalny,
 Objectfirst()
          Zwraca pierwszy elment (w zdefiniowanym dla zbioru porządku)
 SortedSetheadSet(Object toElement)
          Zwraca widok na podzbiór, którego elementy są ściśle mniejsze  od  elementu toElement.
 Objectlast()
          Zwraca ostatni element zbioru (w zdefiniowanym porządku).
 SortedSetsubSet(Object fromElement, Object toElement)
          Zwraca widok na podzbiór, którego elementy znajdują się pomiędzy   elementem fromElement (włącznie) i elementem  toElement (wyłacznie).
 SortedSettailSet(Object fromElement)
          Zwraca widok na podzbiór, którego elementy są większe lub równe elementowi fromElement.
 
Należy też zauważyć ciekawe możliwości jakie daje metoda comparator(). Nie mamy co prawda możliowsci dynamicznych zmian komparatora (już po utworzeniu obiektu klasy TreeSet), ale dzięki dostępowi do obiektu-komparatora i odpowiedniej konstrukcji jego klasy możemy zmieniać charakterystyki jego działania niejako "w locie" (już po utworzeniu obiektu TreeSet i związaniu go z tym komparatorem).

6.7. Mapy

Mapa jest jednoznacznym odwzorowaniem zbioru kluczy w zbiór wartości.


Słowo mapa kojarzy się raczej z mapą geograficzną. Również w języku angielskim znaczenie rzeczownika map jest ograniczone do geografii. Idąc śladem twórców JCF, którzy słowu map przypisują znaczenie wywodzące się od mapping (odwzorowanie), również tutaj zastosujemy zgrabne słowo mapa na oznaczenie odwzorowania zbioru kluczy w zbiór wartości
O mapach możemy myśleć jako o takich kolekcjach par: klucz - wartość, które zapewniają odnajdywanie wartości związanej z podanym kluczem.
Przykladem takiej kolekcji może być zestaw danych, który zawiera nazwiska i numery telefonów i pozwala na odnajdywanie numeru telefonu (poszukiwanej wartości) po nazwisku (kluczu).
Zarówno klucze, jak i wartości mogą być referencjami do dowolnych obiektów (jak również wartościami null).
Oczywiście, wartości kluczy nie mogą się powtarzać (odwzorowanie musi być jednoznaczne). Natomiast pod różnymi kluczami można zapisać te same wartości (odzworowanie nie musi być wzajemnie jednoznaczne).

Aby lepiej zrozumieć możliwe zastosowania map w tablicy podano kilka przykładów.

Klucz
Wartość
NIP
Dane o podatniku
Nazwisko
Numer telefonu
Alias
e-mail
Kraj
Stolica
Port lotniczy, data i pora dnia wylotu (obiekt hipotetycznej klasy Departure)
Lista możliwych polączeń (obiekt klasy, definiującej listę, której elementami są obiekty klasy opisującej połączenia - linie lotnicze, przesiadki, taryfy)

Mapy są niezwykle użytecznym narzędziem programistycznym, pozwalają bowiem prosto i efektywnie programować wiele realnych problemów.

Istotą zastosowania map jest możliwość łatwego i jednocześnie szybkiego odnajdywania informacji w powiązanych zestawach danych


Weźmy najprostszy przyklad: program, który ma pokazywać stolicę podanego przez użytkownika kraju.
Nie stosując w ogóle JFC moglibyśmy napisać go tak (zakładamy, że zestaw krajów i stolic zawarty jest w pliku, a nazwy krajów i stolic oddzielone są znakiem /).

import javax.swing.*;
import java.io.*;
import java.util.*;

class CapitalsNoJFC {

  private final int NC = 300;
  String[] country = new String[NC],
           capital = new String[NC];

  public CapitalsNoJFC() {
    readInfo();
    String in;
    while ((in = JOptionPane.showInputDialog("Kraj")) != null) {
      String cap = getCapital(in);
      if (cap == null) cap = "Brak danych";
      JOptionPane.showMessageDialog(null, "Kraj: " + in + " Stolica: " + cap);
    }
  }

  private void readInfo() {
    try {
      BufferedReader in = new BufferedReader(
                              new FileReader("stolice.txt"));
      String line;
      int i=0;
      while((line = in.readLine()) != null) {
        StringTokenizer st = new StringTokenizer(line, "/");
        country[i] = st.nextToken();
        capital[i] = st.nextToken();
        i++;
      }
      in.close();
    } catch (Exception exc) {
        System.out.println(exc.toString());
        System.exit(1);
      }
  }

  private String getCapital(String kraj) {
    for (int i=0; i<country.length && country[i] != null; i++)
      if (kraj.equals(country[i])) return capital[i];
    return null;
 }

  public static void main(String args[]) {
     new CapitalsNoJFC();
  }
}

To podejście  nie nadaje się do uogólnienia: metoda wyszukiwania informacji (getCapital) zwraca String i ma parametr String (zatem przy innych zestawach danych musimy ją modyfikować), operujemy tablicami, których rozmiary są ustalone, a  wyszukiwanie jest niefektywne (bo liniowe).
Zaważmy jednak przede wszystkim, że  w tym rozwiązaniu musieliśmy trochę czasu poświęcić na oprogramowanie metody getCapital(String kraj), która zwraca stolicę podanego kraju.

Zastosowanie list zamiast tablic zwiększa możliwości uniwersalizacji kodu i nieco oszczędza kodowania (poniżej pokazano tylko fragmenty różniące się od poprzedniego kodu):

class CapitalsList {

  List country = new ArrayList(),
       capital = new ArrayList();

  // ...
 
  private void readInfo() {
      // ...
      String line;
      while((line = in.readLine()) != null) {
        StringTokenizer st = new StringTokenizer(line, "/");
        country.add(st.nextToken());
        capital.add(st.nextToken());
      }
      // ...
  }

  private String getCapital(String kraj) {
    int index = country.indexOf(kraj);
    if (index != -1) return (String) capital.get(index);
    else return null;
 }

Ale to rozwiązanie nadal wymaga dostarczenia własnej metody, która pozwala myśleć w kategoriach klucze-wartości (chodzi o metodę getCapital), a także mnoży struktury danych (mamy dwie listy, powiązane ze sobą tylko dzięki "dobrej woli" programisty), co nie sprzyja zapewnieniu spójności danych.
Rozwiązanie listowe nie usuwa też problemu niefektywności wyszukiwania (metoda indexOf  stosuje wyszukiwanie liniowe). Moglibysmy co prawda uzyskać poprawę efektywności wyszukiwania, ale wymaga to już znaczących nakładów dodatkowej pracy.

Tymczasem wszystko już jest gotowe: uniwersalna struktura danych - mapa - pozwalająca na jednolite, spójne programowanie w kategoriach klucze-wartości i - co również ważne - efektywne odnajdywanie wartości na podstawie podawanych kluczy.

W JCF ze względy na  specyfikę dzialania na mapach (jako zestawach par klucze-wartości)  implementują one interfejs Map, a nie Collection.
Podstawowe operacje na mapie (niezależnie od jej implementacji) są określone przez metody tego interfejsu. Należą do nich: dodawanie pary klucz-wartość do mapy (metoda put), uzyskiwanie wartości "pod" podanym kluczem (metoda get) oraz usuwanie pary klucz-wartośc z mapy (metoda remove).
Zanim przyjzrymy się hierarchii dostępnych map, zobaczmy najpierw jak wyglądałby nasz poprzedni program, gdybyśmy zastosowali mapę (w implementacji HashMap).

import javax.swing.*;
import java.io.*;
import java.util.*;

class CapitalsMap {

  // Mamy teraz jeden spójny zestaw danych: kraje-stolice
  Map countryCapital = new HashMap();

  public CapitalsMap() {
    readInfo();
    String in;
    while ((in = JOptionPane.showInputDialog("Kraj")) != null) {
      // Uzyskiwanie wartości po kluczu
      String cap = (String) countryCapital.get(in);
      if (cap == null) cap = "Brak danych";
      JOptionPane.showMessageDialog(null, "Kraj: " + in + " Stolica: " + cap);
    }
    System.exit(0);
  }

  private void readInfo() {
    try {
      BufferedReader in = new BufferedReader(
                              new FileReader("stolice.txt"));
      String line;
      while((line = in.readLine()) != null) {
        StringTokenizer st = new StringTokenizer(line, "/");
        // Dodawanie do mapy pary: kraj - stolica
        countryCapital.put(st.nextToken(),st.nextToken());
      }
      in.close();
    } catch (Exception exc) {
        System.out.println(exc.toString());
        System.exit(1);
      }
  }

  public static void main(String args[]) {
     new CapitalsMap();
  }
}
Programowanie jest dużo łatwiejsze i mniej zawodne niż poprzednio, a uzyskiwanie informacji bardziej efektywne.

Uwaga: klucze i wartości mapy są typu Object, zatem np. uzyskując wartośc "po kluczu" musimy dokonać konwersji zawężającej do ospoeidniego typu


Hierarchie dostępnych map (interfejsy i gotowe implementacje) pokazuje poniższy rysunek:

r

W mapach istotne jest szybkie odnajdywanie kluczy. Klucze (poprzez umieszczenie ich razem z wartościami w odpowiednie strukturach danych) zwiazane są już bezposrednio i niejako natychniastowo z wartościami.

Podobnie zatem jak w przypadku zbiorów istnieją dwie podstawowe implementacje, pozwalające na szybkie wyszukiwanie kluczy - implementacja oparta na tablicy mieszającej (HashMap) oraz na drzewie czerwono-czarnym (TreeMap).
Niejako ubocznym skutkiem zastosowania tej ostatniej jest możliwość przeglądania  kluczy mapy w naturalnym porządku rosnącym lub w porządku, określanym przez komparator podany przy konstrukcji mapy. Reguły stosowania komparatorów są takie same jak w przypadku zboirów uporządkowanych. Mówimy, że mamy do czynienia z mapą uporządkowaną, a zatem mamy - tak jak w przypadku zbioró uporządkowanych - dodatkowe właściwości takie jak "pierwszy" i "ostatni" klucz lub ich podzbiór "od" -"do" (określane przez mtedoy interfejsu SortedMap) .

Implementacja LinkedHashMap pozwala na odtworzenie kolejności dodawania elementów do mapy, natomiast WeekHashMap (oparta na implementacji mieszającej) ma pewne specyficzne właściwości, o których za chwilę.

Jak już wspomniano, wszystkie w/w klasy implementują interfejs Map. Niewątpliwie warto przyjrzeć się dokładniej jego metodom.

Podstawowe metody interfejsu Map.
 voidclear()
          Usuwa wszystkie elementy mapy (operacja opcjonalna).
 booleancontainsKey(Object key)
          Zwraca true jeżeli mapa zawiera podany klucz (i związaną z nim wartość)
 booleancontainsValue(Object value)
          Zwraca true jeśli mapa zawiera podaną wartość (do ktorej może prowadzić wiele kluczy).
 SetentrySet()
          Zwraca widok na zbiór par klucze-wartości
 Objectget(Object key)
          Zwraca wartość pod podanym kluczem (lub null, co może oznaczać, że odwzorowania dla podanego klucza w mapie nie ma).
 booleanisEmpty()
          Czy pusta?
 SetkeySet()
          Zwraca widok na zbiór kluczy.
 Objectput(Object key, Object value)
          Dodaje od mapy klucz-wartość (lub zastępuje poprzednie odwzorowanie tego klucza w wartość - podanym), zwraca  obiekt, który uprzednio znajdował się pod danym kluiczem lub null (operacja opcjonalna).
 voidputAll(Map t)
    Wszystkie elementy mapy t dodaje do tej mapy         
 (operacja opcjonalna).
 Objectremove(Object key)
          Usuwa odwzorowanie: klucz-wartość z tej mapy (operacja opcjonalna).
 intsize()
          Zwraca liczbę par klucz-wartość w mapie
 Collectionvalues()
          Zwraca widok na kolekcję wartości.

Uwaga. Metody put... powodują zastąpienie istniejących w mapie odwzorowań, które mają takie same klucze jak dodawane odwzorowania. Istotnie - przecież odwzorowania muszą być jednoznaczne!



Jeszcze przed stworzeniem JCF w Javie istniała klasa Hashtable, będąca w zasadzie mapą. Obecnie implementuje ona interfejs Map, ale różni się od innych gotowych implemnetacji tego interfejsu dwoma właściwościami:
 
Ciekawość może wzbudzić w tym zestawie metoda containsKey(..). Na pierwszy rzut oka wydaje się niepotrzebna (duplikuje jakby działanie metody get). Ale pamietajmy, że mapy mogą zwierać pod danym kluczem wartość null. Wtedy metoda get zwraca null i nie wiemy czy oznacza to brak odwzorowania w mapie, czy też odwzorowanie klucza w wartość null. Metoda containsKey  pozwala to rozstrzygnąć: zwróci true jeśli odwzorowanie jest (nawet jeśli wartością "pod" kluczem jest null), natomiast zwrócona wartość false świadczy na pewno o tym, że  w mapie nie ma poszukiwanego odwzorowania.

Drugim ciekawym elementem są tu metody do uzyskiwania widoków na klucze, wartości oraz pary klucze-wartości.
Ze względu na to, że mapy nie implementują interfejsu Collection, nie można od nich uzyskać bezpośrednio iteratorów. Można natomiast uzyskać kolekcje, które są widokami na zestawy kluczy (Set, bo bez powtórzeń), zestawy wartości (Collection, bo bez porządku i z możliwością powtórzeń elementów), oraz par klucze-wartośći (Set, bo bez powtórzeń). Od tych kolekcji - naturalnie - możemy uzyskać iteratory,
Zobaczmy te metody w dzialaniu, przyglądając się jednocześnie różnicom pomiędzy różnymi implementacjami map, zastosowaniu komparatora dla map uporządkowanych oraz - analogicznej jak dla list i zbiorów - możliwości uzyskiwania dowolnej implementacji mapy z jakiejś innej implementacji mapy (poprzez wykorzystanie argumentu konstruktora).
class CapitalsMap2 {

  Map countryCapital = new HashMap();

  public CapitalsMap2() {
    readInfo();
    show("Mapa inicjalna - HashMap", countryCapital);
    show("Mapa w porządku naturalnym - TreeMap",
          new TreeMap(countryCapital)
         );
    // Pusta mapa z komparatorem odwracającym naturalny porządek
    Map mapRo = new TreeMap(Collections.reverseOrder());
    // Wpisujemy do niej pary z mapy countryCapital
    mapRo.putAll(countryCapital);
    show("Mapa w porządku odwrotnym (komparator reverseOrder)",
          mapRo
         );

    // Uzyskanie iteratora po zestawie kluczy
    // Pokazanie wszystkich par, których klucze zawierają r
    // Usunięcie ich
    Iterator it = countryCapital.keySet().iterator();
    while (it.hasNext()) {
      String key = (String) it.next();
      if (key.indexOf("r") != -1) {
        System.out.println(key + " " + countryCapital.get(key));
        it.remove();
      }
    }
    show("Mapa po zmianach", countryCapital);
  }

  public void show(String msg, Map map) {
    System.out.println(msg);
    Set keys = map.keySet();
    System.out.println("Klucze: " + keys);
    Collection vals = map.values();
    System.out.println("Wartości: " + vals);
    Set entries = map.entrySet();
    System.out.println("Pary: " + entries);
  }
//...
}
Ten fragment kodu wyprowadzi następujące informacje:

Mapa inicjalna - HashMap
Klucze: [Malezja, Bali, Polska, Hiszpania, Rosja, Francja]
Wartości: [Kuala Lumpur , Denpasar, Warszawa, Madryt, Moskwa, Paryż]
Pary: [Malezja=Kuala Lumpur , Bali=Denpasar, Polska=Warszawa, Hiszpania=Madryt, Rosja=Moskwa, Francja=Paryż]
Mapa w porządku naturalnym - TreeMap
Klucze: [Bali, Francja, Hiszpania, Malezja, Polska, Rosja]
Wartości: [Denpasar, Paryż, Madryt, Kuala Lumpur , Warszawa, Moskwa]
Pary: [Bali=Denpasar, Francja=Paryż, Hiszpania=Madryt, Malezja=Kuala Lumpur , Polska=Warszawa, Rosja=Moskwa]
Mapa w porządku odwrotnym (komparator reverseOrder)
Klucze: [Rosja, Polska, Malezja, Hiszpania, Francja, Bali]
Wartości: [Moskwa, Warszawa, Kuala Lumpur , Madryt, Paryż, Denpasar]
Pary: [Rosja=Moskwa, Polska=Warszawa, Malezja=Kuala Lumpur , Hiszpania=Madryt, Francja=Paryż, Bali=Denpasar]
Francja Paryż
Mapa po zmianach
Klucze: [Malezja, Bali, Polska, Hiszpania, Rosja]
Wartości: [Kuala Lumpur , Denpasar, Warszawa, Madryt, Moskwa]
Pary: [Malezja=Kuala Lumpur , Bali=Denpasar, Polska=Warszawa, Hiszpania=Madryt, Rosja=Moskwa]


Widok na klucze jest typu wyznaczanego przez klasę, implementującą interfejs Set, ale jest to inna klasa niż znane nam HashSet i TreeSet
Jak widać, uzyskana kolekcja kluczy jest istotnie widokiem (a  nie jakimś nowym obiektem) na klucze mapy. Możemy nie tylko po nich iterować, ale za pomocą metody remove iteratora usuwać odwzorowania z mapy.

Kolekcja par klucze-wartości (widok na klucze wartości) jest typu wyznaczanego przez klasę implementującą interfejs Map.Entry (wewnętrzny interfejs interfejsu Map). Dzięki temu - ale tylko w trakcie iteracji po elementach tej kolekcji - mamy dodatkowe możliwości działania, a mianowicie: uzyskanie klucza dla danej pary (metoda getKey()), uzyskanie wartości dla danej pary (metoda getValue()), zmiana wartości dla danej pary (metoda setValue(Object).
Przykładowy fragment kodu, który - w trakcie iteracji - zmienia wielkość liter w pisowni stolic, pokazuje sposób zastosowania Map.Entry.
    // Zmiana wielkości liter w pisowni stolic
    Iterator pit = countryCapital.entrySet().iterator();
    while (pit.hasNext()) {
      // To jedyny sposób uzyskania dostępu do obiektu Map.Entry !!!
      Map.Entry entry = (Map.Entry) pit.next();
      String cap = (String) entry.getValue();
      entry.setValue(cap.toLowerCase());
    }
I na koniec omawiania map - dwa słowa o klasie WeekHashMap.
Jej zadaniem jest współpraca z odśmiecaczen (garbage collcctor), która może nam pomóc w następującej sytuacji. Wyobraźmy sobie, że referencja do klucza, który związany jest z jakąś wartością w mapie zniknęła z naszego programu. Nie mamy więc żadnego sposobu, by dostać się do tej wartości. Ta para w mapie jest już praktycznie bezużyteczna i powinna być usunięta. Ale ponieważ nie mamy klucza nie możemy tego zrobić, a odśmiecacz nie może usunąć tego elementu mapy, bowiem struktura, ktora go opisuje nadal w mapie "żyje".
Właśnie w takiej sytuacji pomocna jest klasa WeekHashMap: pary w takiej mapie są automatycznie usuwane przez odśmiecacz wtedy, gdy w innych częściach programu nie ma już żadnej referencji wskazującej na klucze tych par.
Klasy WeekHashMap powinniśmy używać przy potencjalnie dużych mapach, gdy struktura fragmentów programu, operujących na mapie jest złożona i nie bardzo potrafimy zagwarantować usuwania odwzorowań z mapy, gdy klucze prowadzące do tych odwzorowań przestają istnieć.

6.8. Algorytmy, widoki, fabrykatory kolekcji

Java Collection Framework zawiera dwie użyteczne klasy, wspomagające dzialania na kolekcjach (a także tablicach) - klasę Collections i klasę Arrays.

Klasa Collections dostarcza statycznych metod, operujących na kolekcjach lub zwracających kolekcje. Do metod tych należą:
Wybrane algorytmy kolekcyjne
static intbinarySearch(List list, Object key)
          Wyszukiwanie binarne na liście. Zwraca indeks elementu, który jest równy podanemu obiektowi key (wedle metody compareTo z klas(y) elementów listy, przy czym zarówno elementy listy, jak i obiekt key muszą być porównywalne). Lista musi być najpierw posortowana według naturalnego porządku np. metodą sort(List).  Przy braku elementu zwraca wartość < 0 ( a nie -1 !)
static intbinarySearch(List list, Object key, Comparator c)
          Wyszukiwanie binarne według podanego komparatora (porównywanie obiektu key z elementami listy następuje za pomocą metody compare komparatora). Lista musi być posortowana zgodnie z porządkiem definiowanym przez komparator np. metodą sort(List, Comparator). Zwraca indeks odnalezionego elementu lub wartość < 0, gyd elementu brak.
static voidsort(List list)
          Sortowanie listy według naturalengo porządku elementów (rosnąco)
static voidsort(List list, Comparator c)
          Sortowanie listy wedle porządku określanego przez komparator.

Uwaga: wszystko o czym mowa była przy okazji przedstawiania pojęć naturalnego porządku oraz  komparatorów - stosuje się do w/w algorytmów.

W klasie Arrays dostarczono statycznych metod, m.in. implementujących algorytmy sortowania i binarnego wyszukiwania dla tablic zarówno typów pierwotnych, jak i obiektów (w tym ostatnim przypadku również z możliwością użycia komparatorów).

Metody klasy Collections zwracające widoki kolekcji nakladają na kolekcje "opakowania" w celu zmiany ich niektórych właściwościi.
W szczególności możemy uzyskać niemodyfikowalne oraz synchronizowane widoki dowolnej kolekcji.

Przypomnijmy, że niemodyfikowalność kolekcji oznacza niemożliwość wszelkich modyfikacji (zarówno strukturalnych - dodawanie usuwanie elementów, jak i zmian wartości elementó).
Czasami jest to potrzebne, gdy chcemy zagwarantować, by po utworzeniu kolekcja w ogóle nie mogła podlegać zmianom, lub gdy chcemy zróżnicować prawa dostępu do kolekcji dla różnych  grup użytkowników naszej aplikacji (ktoś może zmieniać kolekcje, kto inny - tylko przeglądać).
Gotowe implementacje kolekcji w JCF są modyfikowalne.

Niemodyfikowalne widoki kolekcji możemy uzyskać za pomocą metod:
public static Collection unmodifiableCollection(Collection c);
public static Set unmodifiableSet(Set s);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map m);
public static SortedSet unmodifiableSortedSet(SortedSet s);
public static SortedMap unmodifiableSortedMap(SortedMap m);
Szczególnym rodzajem niemodyfikowalności jest brak możliwości zmian rozmiaru kolekcji. Takich kolekcji (których elementy możemy zmieniać, ale nie możemy do nich dodawać nowych elementów ani usuwać istniejących) dostarcza statyczna metoda asList z klasy Arrays, zwracająca listę, elementami której są elementy tablicy przekazanej jako argument.
Metoda ta może służyć nie tylko do łatwego tworzenia list z istniejących tablic, ale również do tworzenia nowych, pustych list o niezmiennych rozmiarach:
// Tworzy listę o ustalonym (i niezmiennym) rozmiarze 1000 elementów
List l = Arrays.asList(new Object[1000]);

Gotowe kolekcje w JCF (za wyjątkiem "starych" Vector i Hashtable) nie są synchronizowane.
Poprawia to efektywność korzystania z kolekcji (jak pamiętamy, synchronizacja jest kosztowna), ale jednocześnie unniemożliwia bezpieczny dostęp do nich przez kilka wątków naraz. Jeśli chcemy udostępnić kolekcje w środowisku wielowatkowym, powinniśmy utworzyć ich synchronizowane widoki. Służą temu metody:
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);
Podkreślmy raz jeszcze, że gdy mowa o widokach (lub "opakowaniach") kolekcji, to tak naprawdę kolekcja jest jedna (nie jest tworzony nowy obiekt, nie są kopiowane wartości elementów). Wszystkie operacje wykonywane są na tej jednej kolekcji,
Jeśli zatem mamy np. listę i jej synchronizowany widok:
List list1 = new ArrayList();
List list2 = Collections.synchronizedList(list1);   
to zmienne list1 i list2 oznaczają tę samą (co do treści) kolekcję.
A przy współbieżności ważne jest, by dostęp z każdego wątku był synchronizowany. Nie powinniśmy zatem pozostawiać możliwości niesynchronizowanego dostępu poprzez  refeerencję do kolekcji z niesynchronizowanym dostępem (referencję list1 w powyższym przykładzie). Powinniśmy raczej napisać:
List list = Collections.synchronizedList(new ArrayList());
Same synchronizowane widoki nie zapewniają jednak bezpieczeństwa przy iterowania po kolekcjach. Iterowanie składa się z wielu operacji, które winny być potraktowane atomistycznie (w przeciwnym razie - przy użyciu iteratora przez inny wątek - wystąpi wyjątek ConcurrentModificationException). Zatem zarówno uzyskanie iteratora jak i jego użycie winno być umieszczone w bloku synchronizowanym:

Collection c = Collections.synchronizedCollection(jakasKol);
synchronized(c) {
    Iterator i = c.iterator(); 
    while (i.hasNext()) {
     // ... i.next() itp.;
    }
 }
Źródło: Java Tutorial, Sun Microsystem 2002

Nieco inaczej wygląda sprawa z synchronizowanymi mapami. Tutaj synchronizacja powinna dotyczyć samej mapy - a nie jej widoków: kluczy,  wartości, czy par (mimo, że własnie na tych kolekcjach wykonywane są iteracje).

Map map = Collections.synchronizedMap(new HashMap());
// ...
Set keys = map.keySet();  // Nie musi być w bloku synchronizowanym
//...
synchronized(map) {  // Synchronizacja na map, a nie na keys
    Iterator i = keys.iterator(); // Musi być w bloku synchronizowanym!
    while (i.hasNext()) {
      // ... i.next() itp.
    }
}
Źródło: Java Tutorial, Sun Microsystem 2002

I jeszcze dwie ważne uwagi, dotyczące widoków kolekcji:


W klasie Collections  znajdziemy także wygodne metody fabrykujące specjalne kolekcje:

static List
nCopies(int n, Object o)
          Tworzy (i zwraca) listę n egzemplarzy obiektu o.
static Setsingleton(Object o)
          Tworzy i zwraca neimodyfikowalny zbiór zawierający jeden obiekt
static ListsingletonList(Object o)
          j.w. - listę
static MapsingletonMap(Object key, Object value)
          j.w. - dla mapy.


Niektóre sposoby ich wykorzystania przedstawiono w poniższych fragmentach kodów:

// Tworzy listę 1000 napisów "Tak"
List l = new ArrayList(Collections.nCopies(1000, "Tak"));

// Zwiększa listę o 1000 napisów "Nie"
l.addAll(Collections.nCopies(1000, "Nie"));

// Usuwa z listy wszystkie wystąpienia napisu "Tak"
l.removeAll(Collections.singleton("Tak"));
Źródło: Java Tutorial, Sun Microsystem 2002

6.9. Własne implementacje kolekcji

Architektura kolekcji jest pomyślana również pod kątem tworzenia nowych własnych rodzajów i implementacji kolekcji.
Ułatwieniem jest przy tym możliwość skorzystania z gotowych klas abstrakcyjnych, implementujących wszystkie interfejsy kolekcyjne, co upraszcza tworzenie implementacji, bowiem nie trzeba definiować wszystkich metod interfejsów (częsć z tych metod została w klasach abstrakcyjnych zdefiniowana, pozostaje nam tylko zdefiniowanie metod abstrakcyjnych).
Wszystkie te klasy znajdują się w pakiecie java.util, a ich nazwy zaczynają się słowem Abstract...
Oczywiście, gotowe implementacje różnych rodzajow kolekcji dziedziczą te abstrakcyjne klasy, co przedstawia poniższy rysunek.

r1
Źródło: C. Horstmann, op. cit.


6.10. Podsumowanie


Poznaliśmy bardzo ważną składową środowiska Javy - architekturę kolekcji Java Collections Framework. Przedstawione zasady i sposoby korzystania z interfejsów i klas kolekcyjnych pozwalają  w sposób prosty, uniwersalny i elastyczny poslugiwać się w programach zaawansowanymi strukturami danych.


6.11. Zadania i ćwiczenia

Zadanie 1. Tworzenie i przetwarzanie prostych kolekcji 

Napisać program, który tworzy różne kolekcje listowe (typu List) i zbiorowe (typu Set) napisów i liczb, podanych w dwóch tablicach o równych rozmiarach. Napisy i liczby (ściślej: referencje do nich) mają być dodawane do każdej z kolekcji na przemian (najpierw napis, później liczba).

Na kolekcjach przeprowadzić następujące operacje: skonkatenować wszystkie łańcuchy znakowe, zsumować wszystkie liczby.

Wyprowadzić wyniki tych operacji dla każdej z kolekcji, poprzedzone informacją o tym jaka to kolekcja i jakie elementy zawiera.

Zapewnić minimum kodowania (operacje dodawania do konkretnej kolekcji oraz jej przetwarzania wyodrębnić w oddzielnych metodach).

Przykład:

dwie tablice napisów i liczb:

String[] s = { "ala", "kot", "pies", "zebra", "ala" };
int[] num = { 1, 2, 7, 9, 2 };

przedstawiono w programie w postaci dwóch konkretnych kolekcji: ArrayList i HashSet. Wynik działania programu:

Kolekcja java.util.ArrayList
[ala, 1, kot, 2, pies, 7, zebra, 9, ala, 2]
Konkatenacja: ala kot pies zebra ala
Suma: 21
Kolekcja java.util.HashSet
[9, pies, zebra, 7, ala, kot, 2, 1]
Konkatenacja: pies zebra ala kot
Suma: 19

Pomoc: -(material spoza wykladu) -
nazwę klasy obiektu obj można uzyskać poprzez odwołanie obj.getClass().getName() [ zwraca napis = nazwa klasy]

Pytania i dodatkowe zadania:

A propos ostatniego pytania musimy uzyskać wydruk podobny do następującego:

Kolekcja java.util.ArrayList
[ala, 1, kot, 2, pies, 7, zebra, 9, ala, 2]
Konkatenacja: ala kot pies zebra ala
Suma: 21
Kolekcja java.util.HashSet
[9, pies, zebra, 7, ala, kot, 2, 1]
Konkatenacja: pies zebra ala kot
Suma: 19
Kolekcja java.util.TreeSet
[1, 2, 7, 9, ala, kot, pies, zebra]
Konkatenacja: ala kot pies zebra
Suma: 19


Zadanie 2. Algorytmy i mapy

Napisac program, ktory z pliku tekstowego (podanego jako argument) wczytuje dane o pracownikach (imie, nazwisko, rok urodzenia, zarobki), a nastepnie wyprowadza informacje o nich:

Uwagi: Pomoc: Przykład:

Wydruk z programu po wczytaniu danych z przykładowego pliku


i podaniu w dialogu wejściowym :

Sonia Ala
Zwierz Staefen (błąd!)
Zwierz Stefan (poprawienie błędu)

Wydruk;

W porzadku alfabetycznym:
Albanski Albin 1978 2300
Jankowski Jan 1975 1500
Jemioluszka Anna 1945 4500
Kowalski Jan 1980 2000
Sonia Ala 1957 3000
Zwierz Stefan 1968 2500
---------------------------------------
Wedlug zarobkow:
Jankowski Jan 1975 1500
Kowalski Jan 1980 2000
Albanski Albin 1978 2300
Zwierz Stefan 1968 2500
Sonia Ala 1957 3000
Jemioluszka Anna 1945 4500
---------------------------------------
Informacje w trybie interaktywnym (po podaniu nazwiska i imienia):
Sonia Ala 3000
Not such worker: Zwierz Staefan
Zwierz Stefan 2500