Wykład 6





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:

Szczegóły konstrukcji użytych w przykładowych programach będą omówione w następnych punktach.
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.
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
AppleJeś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ówAle 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:

w zbiorze elementy nie mają pozycji. Przy przeglądaniu mogliśmy zatem
zastosowac wyłącznie iterator (dostęp "po indeksach" nie jest możliwy).
porządek iterowania (przeglądania) zbioru nie jest określony (jak
widać kolejność wyprowadzonych wyników jest inna niż kolejność firm w pliku).

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: Apple2: IBM3: Sun4: 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:

możemy bardzo latwo posługiwać się tablicami o dynamicznie zmieniających się rozmiarach,
możemy bardzo łatwo zapewnić, by w kolekcji nie powtarzały się elementy danych (realizacja koncepcji zbioru),
możemy bardzo latwo porządkować dane (zbiory uporządkowane i sortowanie list),
możemy bardzo łatwo posługiwac się efektywnymi realizacjami tablic asocjacyjnych.

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 implementacjeKlasy Java Collections Framework dostarczają środków do posługiwania się:

listami (i ich szczególnymi przypadkami - stosami, kolejkami i kolejkami podwójnymi),
zbiorami (w tym: zbiorami uporządkowanymi),
mapami (tablicami asocjacyjnymi, realizowanymi jako słowniki).


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:


Użyte w tablicy pojęcia, dotyczące sposobu implementacji, zostaną wyjasnione w trakcie omawiania konkretnych struktur danych.
Klasa TreeSet implementuje interfejs SortedSet, a klasa TreeMap
- interfejs SortedMap. Oba te interfejsy sa rozszerzeniami wymienionych w
tablicy interfejsow (odpowiednio Set i Map).W tabeli pokazano podstawowe, najwazniejsze interfejsy i klasy. O innych mowa będzie w dalszym ciągu dyskusji.


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.




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).




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:

uzyskanie liczby elementów w kolekcji - metoda int size(),
stwierdzenie czy kolekcja jest pusta - metoda boolean isEmpty(),
stwierdzenie, czy kolekcja zawiera podany obiekt - metoda boolean contains(Object).

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:

kolekcje mogą być modyfikowalne lub niemodyfikowalne,
kolekcje mogą dopuszczać duplikaty bądź nie.

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:

albo nie dostarczać metod add i remove w interfejsie Collection,
albo stworzyć dwa interfejsy dla modyfikowalnych i niemodyfikowalnych kolekcji i odpowiednie hierarchie dziedziczenia,
albo dostarczając metod dodawania i usuwania elementów w interfejsie
Collection, zapewnić jakieś środki decydowania w konkretnych implementacjach
czy metody te są dopuszczalne.


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.






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:



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:

dodawanie do dowolnej kolekcji wszystkich elementów innej dowolnej kolekcji - metoda addAll(Collection),
usuwanie z kolekcji wszystkich elmentów, które są zawarte w innej kolekcji - metoda removeAll(Collection),
pozostawienie w kolekcji tylko tych elementów, które są zawarte w innej kolekcji - metoda retainAll(Collection),
usunięcie wszystkich elementów kolekcji - metoda clear().


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:


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:

wszystkie operacje modyfikującę listę strukturalnie lub pod względem zawartości są opcjonalne,
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:


konkurencyjne modyfikacje wartości elementów listy w trakcie iteracji za pomocą iteratora listowego nie są wykrywane,
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:



Dodanie elementu na liście LinkedList:



Ź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:

wstawienie elementu na początek listy,
pobrania elementu z początku listy,
usunięcia elementu z początku listy.



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:

wstawienie elementu na koniec listy,pobrania elementu z końca listy,usunięcia elementu z końca listy.




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:

wyliczanie kodu mieszania było szybkie,
kody mieszania dla rożnych elementów zależały tylko od ich wartości i były (możliwie) różne dla różnych wartości elementów,
wynikowe indeksy dawały możliwie równomierną dystrybucję elementów danych po elmentach tablicy mieszania.


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.




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:

Z każdym węzłem drzewa związana jest wartość
Wartość ta jest większa od wartości lewego potomka i mniejsza od wartości prawego potomka
Z każdym węzłem związany jest atrybut koloru - czerwony lub czarny
Każdy czerwony węzeł, ktory nie jest liściem ma tylko czarnych potomków
Każda ścieżka od korzenia do liścia zawiera tyle samo czarnych węzłów
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.



Ź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 obiektów,
lub reguły porównywania obiektów określane przez komparator - obiekt klasy implementującej interfejs Comparator.

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:

liczbę < 0, jeżeli ten obiekt (this) znajduje (w porządku) przed obiektem otherObject,
liczbę > 0, jeżeli ten obiekt (this) znajduje (w porządku) po obiekcie otherObject,
0, jeśli obiekty są takie same.




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:

Operacje na zbiorze HashSet używają (i wymagają) metod hashCode() i
equals(), a dodawanie i wyszukiwanie elementów odbywa się w oparciu o wyniki
metody equals().
Operacje na zbiorze TreeSet odbywają się w oparciu o wyniki metody compareTo() lub metody compare() komparatora.



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:




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:

nie dopuszcza ani kluczy, ani wartości null,
jest synchronizowana.

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 TreeSetJak 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 kolekcjiJava 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żą:

algorytmy kolekcyjne,
metody zwracające widoki kolekcji,
metody tworzące specjalne kolekcje.




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:

widoki (jak widać z sygnatur metod) są formułowane w terminach
interfejsów, a nie klas; zatem używając synchronizowanych lub niemodyfikowalnych
widoków kolekcji nie mamy dostępu do specyficznych metod klas, takich jak
np. getFirst czy getLast z klasy LinkedList,
dla najogólniejszych widoków kolekcji (uzyskiwanych metodami
unmodifiableCollection i synchronizedCollection) metody equals i hashCode
używane wobec elementów kolekji nie są polimorficzne (ich wywolanie nie powoduje
wywołania odpowiednich metod z odpowiednich klas, zamiast tego używane są
metody z klasy Object); dopiero przy konkretyzacji(np. kiedy prosimy o niemodyfikowalną
listę czy synchronizowany zbiór) zyskują one sens i mogą być dobrze zdefiniowane
- wtedy odwolania są w pełni polimorfczne.



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 obiektstatic 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.



Ź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 alaSuma: 21Kolekcja java.util.HashSet[9, pies, zebra, 7, ala, kot, 2, 1]Konkatenacja: pies zebra ala kotSuma: 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:

dlaczego utworzone kolekcje HashSet i ArrayList
różnią się między sobą?jak najłatwiej zmienić implementację listy z
ArrayList na LinkedList? Pokazać kod.co się stanie jeśli w tym programie za pomocą
takich samych środków jak w przypadku list i HashSet będziemy próbować tworzyć
kolekcję TreeSet? Dlaczego ?co trzeba zrobić, żeby utworzenie kolekcji TreeSet
powiodło się i jakie będzie ona miała własności?

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 alaSuma: 21Kolekcja java.util.HashSet[9, pies, zebra, 7, ala, kot, 2, 1]Konkatenacja: pies zebra ala kotSuma: 19Kolekcja java.util.TreeSet[1, 2, 7, 9, ala, kot, pies, zebra]Konkatenacja: ala kot pies zebraSuma: 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:

posortowane wg nazwisk i imionposortowane wg zarobkowna zyczenie - po podaniu w dialogu wejsciowym
nazwiska i imienia - nazwisko i imie oraz zarobki dla danego pracownika.

Uwagi:

uzyskiwanie informacji o konkretnym pracowniku
(po podaniu jego nazwiska i imienia) zapewnić poprzez odpowiednią implementację
mapy,zabezpieczyć się przed powtarzającymi się nazwisko+imię
(w mapie),w standardowej wersji programu (to wystarczy)
wszystkie informacje wyprowadzamy na konsole,w rozbudowanej wersji programu posortowane
informacje kierować do pliku wyjściowego, a zapytania o konkretnych pracownikach
przedstawiać jako komunikaty typu messageDialogw standardowej wersji programu przy powtórzeniach
nazwisko+imie przerywac program, w rozbudowanej wersji zapewnić mechanizm
sensownej obsługi powtórzeń.

Pomoc:

potrzebna odrębna klasa reprezentująca atrybuty
pracowników (imie, nazwisko, rok urodzenia, zarobek), ich uzyskiwanie i pokazywanie
oraz naturalny porządek sortowania wg : nazwisko+imiętylko listy dają się sortowaćjednoczesne przechowywanie referencji do obiektów
na liście i w mapie nie jest niczym złymnaturalny porządek można łamać za pomocą Comparatora

Przykład:
Wydruk z programu po wczytaniu danych z przykładowego
pliku

i podaniu w dialogu wejściowym :Sonia AlaZwierz 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