Kolekcje

1. Architektura kolekcji (JCF). Interfejsy i implementacje

• listami,
• kolejkami,
• zbiorami (w tym: zbiorami uporządkowanymi),
• mapami (odwzorowania: klucz -> wartość ).

1. w tablicy pokazano relacje dziedziczenia interfejsów (np. wszystkie interfejsy dziedzicżą, rozszerzają interfejs  Collection),
2. wszystkie interfejsy kolekcyjne sa sparametryzowane, dla wygody pominięto parametry typu.

1. Wszystkie klasy są sparametryzowane.
2. Pominięto klasy kolekcyjne z pakietu java.util.concurrent, służące programowaniu współbieznemu.
3. Użyte w tablicy pojęcia, dotyczące sposobu implementacji, zostaną wyjasnione w trakcie omawiania konkretnych struktur danych.

class ListUtils {
  
  static <T> void append(List<T> list, T[] items) {
    for (T item : items) 
      list.add(item);
  }
// ...
}

  static void show(List<?> list) {
    for (Object o : list)
      System.out.println(o);
  }

    String[] items = { "Kot", "Pies", "Zebra", "Tygrys" };
    List<String> list1 = new ArrayList<String>();
    ListUtils.append(list1, items);
    ListUtils.show(list1);

    Integer[] arr = {1, 2, 3};
    List<Integer> list1 = new LinkedList<Integer>();
    ListUtils.append(list1, arr);
    ListUtils.show(list1);
    

ArrayList list2 = ListUtils.create(
                            new String[] { "Truskawki", "Banany"}
                            );

    List<String> list2 = ListUtils.create(
                           new String[] { "Truskawki", "Banany"}
                           );

  static <T>  List<T> create(T[] items) {
    ArrayList<T> list = new ArrayList<T>();
    append(list, items);
    return list;
  }

import java.util.*;

class NumberedList extends ArrayList<String> {
  // ...
  public NumberedList addAuto(Object o) {
    super.add("Nr." + (size()+1) + " " +o);
    return this;
  }
  // ...
}

    NumberedList nls = new NumberedList();
    nls.addAuto("Pies").addAuto("Kot").addAuto("Wilk");
    ListUtils.show(nls);

2. Ogólne operacje na kolekcjach. Operacje opcjonalne i grupowe.

• 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(obiekt).

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

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

        public boolean add(T o) {
	    throw new UnsupportedOperationException();
        }
	public boolean remove(T o) {
	    throw new UnsupportedOperationException();
        }

• dodawanie do dowolnej kolekcji wszystkich elementów innej dowolnej kolekcji - metoda addAll(Collection),
• usuwanie z kolekcji wszystkich elementó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),
• stwierdzanbia czy obie kolekcje zawierają identyczne elementy,
  
• usunięcie wszystkich elementów kolekcji - metoda clear().
  

  List lista;
  //... utworzenie listy w konkretnej implementacji np.ArrayList lub LinkedList
  Set tset = new  TreeSet(lista);

    List<String> list = new ArrayList<String>()
    // ... 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);
    }
  } 

List<String> lista = Arrays.asList("Ala", "ma", "kota");

import java.util.*;

public class GroupOp {

  List<String> list1 = new ArrayList<String>();
  Set<String> set1 = new HashSet<String>();

  void add(String ...strings ) {
    for (String s : strings) {
      list1.add(s);
      set1.add(s);
    }
  }
  
  public GroupOp() {
    add("Pies", "Kot", "Tygrys", "Zebra", 'Z' + "ebra");
    System.out.println(list1);
    list1.removeAll(set1);
    System.out.println("Usunięte będą wszystkie elementy, bo działa equals:\n"+ list1);
    list1.addAll(set1);
    System.out.println(list1);
    //List<Integer> list2 = new ArrayList<Integer>(list1);  // błąd w kompilacji
    // Zastosowanie Arrays.asList();
    List<Integer> list2 = Arrays.asList(1,2,3,4,5);
    System.out.println(list2);
    // ale teraz list2 jest fixed-size
    try {
      list2.add(35);
    } catch(Exception exc) {
       System.out.println("Wystąpił wyjątek: " + exc);
       System.out.println("bo lista niemodyfikowalna:\n" + list2);
    }
    System.out.println("Możemy zrobić, aby była modyfikowalna:");
    list2 = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5));
    System.out.println("Teraz możemy dodać coś");
    list2.addAll(Arrays.asList(35, 1, 2, 3));
    System.out.println(list2);
    System.out.println("Gdy chcemy usunąć duplikaty:");
    Set<Integer> set2 = new HashSet<Integer>(list2);
    System.out.println(set2);
    System.out.println("A czy możemy połączyć kolekcje z różnymi typami elementów?\nTak.");
    // Nalezy uzyć typu Object
    List<Object> list3 = new ArrayList<Object>(list1);
    list3.addAll(set2);
    System.out.println(list3);
    // Tyle, że przy iteracjach już musimy posługiwać się typem Object
    // i ew. robić konwersje zawężające
    int sum = 0;
    String txt = "";
    for(Object o : list3) {
      if (o instanceof Integer) sum += (Integer) o;
      else txt += (String) o;
    }
    System.out.println("Suma liczb: " + sum);
    System.out.println("Napis: " + txt);
    // A na koniec sprawdzimy jak z listy zrobić tablicę
    // Najlepiej tak, bo będzie uwzględniony typ elementów
    System.out.println("Tablica z listy");
    String[] tab = (String[]) list1.toArray(new String[0]);
    for (String string : tab) {
      System.out.println(string + " " + string.length());
    }
    
  }

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

3. Iteratory

Iterator<T> iter = c.iterator(); // c - dowolna kolekcja, typ Collection, T - typ elementów kolekcji
while (iter.hasNext()) {
  Object o = iter.next();
  if (warunek_usunięcia(o)) iter.remove();
}

    List<String> l = new ArrayList<String>();
    // .. dodanie do listy jakichś elementów
    Iterator<String> it1 = l.iterator();
    while (it1.hasNext()) {
      it1.next();
      l.add("Coś"); // Błąd fazy wykonania
    }
 

    List<String> l = new ArrayList<String>();
    // dodanie do listy jakichś elementów
    Iterator<String> it1 = l.iterator();
    Iterator<String> it2 = l.iterator();
    while (it1.hasNext()) {
      it1.next();
      it2.next();
      it2.remove();  // Błąd fazy wykonania
    }

4. Przykład: uniwersalne działania na kolekcjach

public interface CHelper<T>  {
  
  // Tworzy obiekt z podanego napisu s i zwraca go
  T makeObject(String s);
  
  // Tworzy String z obiektu - możliwe, że w altrnatywny sposób niż toString
  String makeString(); 

  // Zwraca true, jeśli dane obiektu są uznane za nieaktualne
  boolean isNotUpToDate();

}

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

public class MKolekt {

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

  public static <T extends CHelper<T>> 
         void makeCollectionFromFile(Collection<T> col, String fname,
                                     Class<T> klasaOb) {
    try {
      CHelper<T> mgr =  klasaOb.newInstance();

      Scanner in = new Scanner(new File(fname));
      while(in.hasNextLine()) {
        T obj = mgr.makeObject(in.nextLine());
        col.add(obj);
      }
      in.close();
    } catch (Exception exc) {
        exc.printStackTrace();
        System.exit(1); 
    }
  }

  // Usuwa z kolekcji c obiekty przeznaczone do usunięcia
  // na podstawie wyniku metodu isNotUpToDate

  public static <T extends CHelper<T>> void iterRemove(Collection<T> c) {
    Iterator<T> iter = c.iterator();
    while (iter.hasNext()) {
      CHelper<T> elt = iter.next();
      if (elt.isNotUpToDate()) iter.remove();
    }
  }

  // Zapisuje do pliku fname, w kolejnych wierszach,
  // kolejne elementy kolekcji col
  public static <T extends CHelper<T>>
    void writeToFile(Collection<T> col, String fname) throws Exception {
      Formatter out = null;
      try {
        out = new Formatter(new File(fname));
        for (T obj : col) {
          String line = obj.makeString();
          out.format("%s%n", line);
        }
      } finally {
          if (out != null) out.close();
      }
    
  }
  
  public static void show(Collection<?> col) {
    for (Object o : col) System.out.println(o);
  }

}

• sposób zastosowania sparametryzowanych metod i użycie ograniczeń parametrów typu (T extends CHelper) - dzieki temu zapewniona jest zgodność typów w fazie kompilacji i bez konwersji zawęzających możemy stosować metody deklarowane w interfejsie CHelper,
• metoda makeCollectionFromFile jako ostatni argument uzyskuje obiekt klasy Class<T>, gdzie T jest konkretnym typem (nazwą klasy). Obiekt ten reprezentuje klasę obiektó dodawanych do kolekcji. Jest on nam potrzebny, bo używając metody newInstance() klasy Class tworzymy (za pomoca konstruktora bezparametrowego) obiekt klasy elementów , a ten z kolei jest niezbędny by polimorficznie na jego rzezc wywołać metodę makeObject(...).
• metoda show(...) pozwala wypisac elementy dowolnej kolekcji, bowiem użyto parametru uniwersalnego <?>.

import java.util.*;

public class Test {

  public static void main(String[] args) {
    List<Journal> gazety = new ArrayList<Journal>();
    Set<Student>  studenci = new HashSet<Student>();
    MKolekt.makeCollectionFromFile(gazety, "Journal.in", Journal.class);
    MKolekt.makeCollectionFromFile(studenci, "Student.in", Student.class);
    System.out.println("Oryginalna zawartość kolekcji"); 
    MKolekt.show(gazety);
    MKolekt.show(studenci);
    // ustalenie minimalnego roku wydania
    // gazety wydane wczesniej będą usunięte z kolekcji
    Journal.setLimitYear(2004);
    MKolekt.iterRemove(gazety);
    // ustalenie minimalnej oceny
    // studenci z oceną niższą będa usunięci z kolekcji   
    Student.setLimitMark(3);
    MKolekt.iterRemove(studenci);
    // Pokazujemy po usunięciu
    System.out.println("Nowa zawartość kolekcji");
    MKolekt.show(gazety);
    MKolekt.show(studenci);
    // I zapisujemy do pliku

    try {
      MKolekt.writeToFile(gazety, "Journal.out");
      MKolekt.writeToFile(studenci, "Student.out");
    } catch (Exception exc) {
      exc.printStackTrace();
    }
  }

}

import java.util.*;

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

  //konstruktor brzparametrowy (wg kontraktu potrzebny do newInstance w MKolekt)
  public Journal() { }  
  
  public Journal(String t, int y) {
    title = t;
    year = y;
  }

  // Implementacja metody stwierdzającej czy Journal można uznać za aktualny
  @Override
  public boolean isNotUpToDate() {
    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.
  @Override
  public Journal makeObject(String s){
    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);
    return j;
  }
  
  // Tworzy String z obiektu
  // inna forma niż toString (dla zapisu do pliku)
  @Override
  public String makeString() {
    return '"' + title + '"' + " " + year; 
  }

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

  @Override
  public int hashCode() {
    return this.toString().hashCode();
  }

  @Override
  public boolean equals(Object obj) {
    return toString().equals(obj.toString());
  }

  @Override
  public int compareTo(Journal j) {
    return toString().compareTo(j.toString());
  }

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

import java.util.*;

public class Student implements CHelper<Student>, Comparable<Student> {
  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 isNotUpToDate() {
    return mark < minMark;
  }

  // Tworzy obiekt Student i dodaje do kolekcji
  // format napisy: nazwisko tab ocena
  public Student makeObject(String s) {
    Scanner sc = new Scanner(s).useDelimiter("\t");
    String name = sc.next();
    double mark = 0;
    try {
      mark = sc.nextDouble();
    } catch (Exception exc) {
      exc.printStackTrace();
    }
    Student stud = new Student(name, mark);
    return stud;

  }
  
  @Override
  public String makeString() {
    return name + '\t' + mark;
  }

  // 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(Student s) {
    return this.toString().compareTo(s.toString());
  }

  public int hashCode() { return this.toString().hashCode(); }

  public String toString() { return name + " " + mark; }
}

5. Listy i iteratory listowe

public class ArrayList<E> implements List<E> // ,  ...
{
    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;
    }
// ...
}

1. wszystkie operacje modyfikującę listę strukturalnie lub pod względem zawartości są opcjonalne,
2. pozycje na liście numerowane są od 0 (tak jak indeksy w tablicy).

1. konkurencyjne modyfikacje wartości elementów listy w trakcie iteracji za pomocą iteratora listowego nie są wykrywane,
2. w przeciwieństwie  do metody add z interefejsu Collection metoda add iteratora listowego nie zwraca żadnego wyniku: na liście operacja dodawania zawsze jest skuteczna.

import java.util.*;
class ListIter1 {

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


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

    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++;
    }

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

public class Lists {

  long start;

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

  public Lists(int n) {
    ArrayList<String>  aList = new ArrayList<String>(n);
    for (int i=0; i < n; i++) aList.add("a");
    LinkedList<String> lList = new LinkedList<String>(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<String> l) {
    Random rand = new Random();
    for (int i=0; i<10000; i++) {
      int index = rand.nextInt(l.size());
      String s = l.get(index);
      s = s + "a";
      l.set(index, s);
    }
  }

  void insert(List<String> l) {
    ListIterator<String> 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(new Scanner(JOptionPane.showInputDialog("Ile elementó na liście?")).nextInt());
  }
}

for (int i=0, n = list.size(); i<n; i++) list.get(i);

for (Iterator iter = list.iterator(); iter.hasNext(); ) iter.next();

6. Kolejki

• wstawienie elementu na końcu liniowej sekwencji elementów,
• pobrania elementu z początku liniowej sekwencji elementów,
• usunięcia elementu z początku liniowej sekwencji elementów.

• wstawienie elementu na początku liniowej sekwencji elementów,
• pobrania elementu z początku liniowej sekwencji elementów,
• usunięcia elementu z początku liniowej sekwencji elementów.

• LinkedList - lista, która jest jednocześnie kolejką podwójną (bez ograniczeń na miejsce),
• ArrayDeque - kolejka podwójna, zrealizowana jako rozszerzalna tablica
• PriorityQueue - kolejka z priorytetami.

import java.util.*;

public class Kolejki {

  public static void main(String[] args) {
    ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
    
    // Działa jak kolejka FIFO
    deq.offer(1);
    deq.add(20);
    deq.add(12);
    
    System.out.println("FIFO: " + deq);
    System.out.println("Podglądamy (z początku): " + deq.peek());
    
    // Działa jak kolejka LIFO
    deq.clear();
    deq.addFirst(1);
    deq.addFirst(20);
    deq.addFirst(12);

    System.out.println("LIFO: " + deq);
    System.out.println("Podglądamy (z początku): " + deq.peek());

    // Kolejka z priorytetami
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(20);
    pq.add(12);
    System.out.println("PRIOR QUE: " + pq); 

    System.out.println("Z kolejki z priorytami pobieramy\nkolejne elementy\nzawsze z początku");
    System.out.println("Początek - domyślnie najmniejszy element");
    Integer n;
    while((n = pq.poll()) != null) {
      System.out.println(n);
    }
  }

}

7. Zbiory. Haszowanie i porządkowanie.

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

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();
  }
}

1. Ustal wartość stałej całkowitoliczbowej wynik (liczba całkowita, najlepiej pierwsza np 19) .
2. Dla każdego pola klasy, branego pod uwagę przy porównywaniu obiektów, wylicz całkowitoliczbowy kod c:
1. jeżeli pole f jest typu boolean: c = (f ? 0 : 1).
2. jeżeli pole f jest typu byte, char, short, albo int: c = (int)f.
3. jeżeli pole f jest typu long: c = (int)(f ^ (f >>> 32)).
4. jeżeli pole f jest typu float: c = Float.floatToIntBits(f).
5. jeżeli pole f jest typu double, wylicz long l =  Double.doubleToLongBits(f), a następnie zastosuje przekształcenie c = (int)(l ^ (l >>> 32)).
6. jeżeli pole f jest referencją, zastosuj (jeśli trzeba rekursywnie, albo po odpowiednim przekształceniu referencji) metodę hashcode() z klasy obiektu wskazywanegop przez tę referencję, najprościej c = f.hashcode(),
7. jeżeli pole f oznacza tablicę, zastosuj opisaną wyżej procedutę rekursywnie (dla każdego elementu tablicy) i wylicz kod wynikowy jak poniżej (następny punkt)
3. Składaj wyniki powyższych obliczeń w formule: wynik = 37*wynik + c;
4. Zwróć ten wynik (jako wynik metody hashcode())

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() {
    int wynik = 17;
    wynik = 37*wynik + lname.hshcode();
    wynik = 37*wynik + fname.hashcode();
    return wynik;
  }

  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());
  }
}

    Set set = new LinkedHashSet();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());

1. Z każdym węzłem drzewa związana jest wartość
2. Wartość ta jest większa od wartości lewego potomka i mniejsza od wartości prawego potomka
3. Z każdym węzłem związany jest atrybut koloru - czerwony lub czarny
4. Każdy czerwony węzeł, ktory nie jest liściem ma tylko czarnych potomków
5. Każda ścieżka od korzenia do liścia zawiera tyle samo czarnych węzłów
6. Korzeń jest czarny.

    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());

8. Porównywanie obiektów

class Worker implements Comparable<Worker> {
  private String lname;
  private String fname;
  // ...
  public int compareTo(Worker otherObj) {
    return this.lname.compareTo(otherObj.lname);
  }   
  // ...
}

    Worker[] p = { new Worker("Jan", "Kowalski", 1000),
                   new Worker("Jan", "Malinowski", 1200),
                   new Worker("Jan", "Kowalski", 1400),
                   new Worker("Jab", "Kowalewski", 2000),
                 };

    Set<Worker> set = new TreeSet<Worker>();
    for (int i=0; i < p.length; i++) set.add(p[i]);
    System.out.println(set.toString());

import java.util.*;

class Worker implements Comparable<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 getSalary() { return salary; }

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

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


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

    // Zbiór uporządkowany wg rosnących pensji
    Set<Worker> set2 = new TreeSet<Worker>(new Comparator<Worker>() {
                   public int compare(Worker o1, Worker o2) {
                     // różnica pensji wystarczy do porownania?:
                     return o1.getSalary() - o2.getSalary();
                   }
               });
    for (Worker w : workers) set2.add(w);
    System.out.println(set2);

    // Zbiór uporządkowany w malejącym porządku naturalnym (malejące nazwiska)
    Set<Worker> set3 = new TreeSet<Worker>(Collections.reverseOrder());
    for (Worker w : workers) set3.add(w);
    System.out.println(set3);

  }
}

9. Mapy

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();
  }
}

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;
 }

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

class CapitalsMap {

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

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

  private void readInfo() {
    try {
      Scanner in = new Scanner(new File("stolice.txt"));
      while(in.hasNextLine()) {
        Scanner line = new Scanner(in.nextLine()).useDelimiter("/");
        // Dodawanie do mapy pary: kraj - stolica
        countryCapital.put(line.next(),line.next());
      }
      in.close();
    } catch (Exception exc) {
        exc.printStackTrace();
        System.exit(1);
      }
  }

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

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

class CapitalsMap2 {

  Map<String, String> countryCapital = new HashMap<String, String>();

  public CapitalsMap2() {
    readInfo();
    show("Mapa inicjalna - HashMap", countryCapital);
    show("Mapa w porządku naturalnym - TreeMap",
          new TreeMap<String, String>(countryCapital)
         );
    // Pusta mapa z komparatorem odwracającym naturalny porządek
    Map<String, String> mapRo = new TreeMap<String, String>(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<String> it = countryCapital.keySet().iterator();
    while (it.hasNext()) {
      String key = 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<String, String> map) {
    System.out.println(msg);
    Set<String> keys = map.keySet();
    System.out.println("Klucze: " + keys);
    Collection<String> vals = map.values();
    System.out.println("Wartości: " + vals);
    Set entries = map.entrySet();
    System.out.println("Pary: " + entries);
  }
  
  private void readInfo() {
    try {
      Scanner in = new Scanner(new File("stolice.txt"));
      while(in.hasNextLine()) {
        Scanner line = new Scanner(in.nextLine()).useDelimiter("/");
        // Dodawanie do mapy pary: kraj - stolica
        countryCapital.put(line.next(),line.next());
      }
      in.close();
    } catch (Exception exc) {
        exc.printStackTrace();
        System.exit(1);
      }
  }
  
  public static void main(String[] args) {
    new CapitalsMap2();
  }

}

    // Zmiana wielkości liter w pisowni stolic
    Iterator<Map.Entry<String, String>> pit = countryCapital.entrySet().iterator();
    while (pit.hasNext()) {
      // To jedyny sposób uzyskania dostępu do obiektu Map.Entry !!!
      Map.Entry<String, String> entry =  pit.next();
      String cap =  entry.getValue();
      entry.setValue(cap.toUpperCase());
    }
    show("Po zmianie wielkości liter", countryCapital);
  }

10. Algorytmy, widoki, fabrykatory kolekcji

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

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

// Tworzy listę o ustalonym (i niezmiennym) rozmiarze 1000 elementów
List l = Arrays.asList(new Object[1000]);

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

List list1 = new ArrayList();
List list2 = Collections.synchronizedList(list1);   

List list = Collections.synchronizedList(new ArrayList());

Collection c = Collections.synchronizedCollection(jakasKol);
synchronized(c) {
    Iterator i = c.iterator(); 
    while (i.hasNext()) {
     // ... i.next() itp.;
    }
 }

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

• 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 kolekcji nie są polimorficzne (ich wywolanie nie powoduje wywołania odpowiednich metod  z odpowiednich podklas, zamiast tego używane są metody z klasy Object); dopiero przy konkretyzacji  w konkretnych klasach (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.

11. Własne implementacje kolekcji