Лекция 12. Коллекции
#######################################################################################



Обобщенное программирование
===========================================================


Введение
-----------------------------------------------------------


Обобщенное программирование
``````````````````````````````````````````````````````````

**Обобщенное программирование** - разновидность подхода к написанию программ, которая позволяет описать работу с различными типами данных некоторым единственным способом.


В С++ такой подход основан на использовании **шаблонов (templates)**.


В Java его называют **Generics**.
Можно создавать обобщения для классов и для методов.


Обобщения позволяют конструировать **контейнеры** для хранения данных различных типов. На них основан механизм **коллекций**.


Generics
-----------------------------------------------------------



.. code-block:: java

 class SimpleGeneric<T>
 {
     private T element;
 
     public T getElement() {
         return element;
     }
     public void setElement(T element) {
         this.element = element;
     }
 }




.. code-block:: java

 public class SimpleDemo
 {
     public static void main(String[] args) {
         SimpleGeneric<String> sg1 = new SimpleGeneric<>();
         sg1.setElement("12345");
  
         SimpleGeneric<Integer> sg2 = new SimpleGeneric<>();
         sg2.setElement(99);
     }
 }


В качестве параметров **T** могут выступать **ссылочные типы** (пользовательские классы и классы оболочек). Использовать примитивные типы нельзя.
Можно создавать обобщения для методов:



.. code-block:: java

 class GenMethod
 {
     public static <T> boolean eq(T one, T two) {
         return one.equals(two);
     }
 }
 public class GenMethodTest {
     public static void main(String[] args) {
         System.out.println(GenMethod.eq(new Integer(77),
                                             new Integer(77)));
     }
 }


Метод для обработки массива:



.. code-block:: java

 class GenMethod
 {
     public static <T> boolean present(T[] arr, T item) {
         for(int i=0;i<arr.length;i++)
             if(arr[i].equals(item))
                 return true;
         return false;
     }
 }
 public class GenMethodTest2 {
     public static void main(String[] args) {
         Integer[] arr=new Integer[] {1,2,3,4};
         System.out.println(GenMethod.present(arr,2));
     }
 }


При создании обобщения можно использовать несколько параметров:



.. code-block:: java

 class Pair<T1, T2> { 
     T1 object1; 
     T2 object2; 
  
     Pair(T1 one, T2 two) { 
         object1 = one; 
         object2 = two; 
     } 
  
     public T1 getFirst() { 
         return object1; 
     } 
     public T2 getSecond() { 
         return object2; 
     } 
 } 
 ...
 Pair<Integer, String> pair = 
           new Pair<Integer, String>(12,"Иванов А.А."); 
 ..


В современных версиях языка можно опускать указания типов в правой части выражения, например:



.. code-block:: java

 Pair<Integer, String> pair = 
           new Pair<>(12,"Иванов А.А.");


При несоответствии типов фактических параметров (в круглых скобках) будет ошибка компиляции.
Вопрос: какие строки вызовут ошибку?



.. code-block:: java

 1. List<Integer> list = new List<Integer>(); 
 2. List<Integer> list = new ArrayList<Integer>(); 
 3. List<Number> list = new ArrayList<Integer>(); 
 4. List<Integer> list = new ArrayList<Number>(); 


Пояснение: **List** - интерфейс, **Number** - базовый класс для **Integer**.


Wildcards
-----------------------------------------------------------

В качестве параметров для шаблонов могут выступать **подстановочные символы (wildcards)**. Еще их называют **масками**.



.. code-block:: java

 public interface Box<T> {
     public T get();
     public void put(T element);
 }
 
 public void unbox(Box<?> box) {
     System.out.println(box.get());
 }


Подстановочные символы играют важную роль в системе типов; с их помощью можно описать тип, ограниченный некоторым семейством типов, описываемых обобщенным классом. 


Для обобщенного класса **ArrayList**, тип **ArrayList<?>** обозначает супертип **ArrayList<T>** для любого типа **T**.



.. code-block:: java

 interface Box<T> {
     public T get();
     public void put(T element);
 }
 class MyBox<T> implements Box<T> {
    T item;
    public void put(T element) {
       item=element;
    }    
    public T get() {
       return item;
    }
 }




.. code-block:: java

 class WCDemo 
 {
    public static void unbox(Box<?> box) {
       System.out.println(box.get());
    }
    public static void main(String[] args) {
       MyBox<Integer> mb=new MyBox<>();
       mb.put(12);
       unbox(mb);          
    }
 }



Коллекции
===========================================================


Введение
-----------------------------------------------------------


Коллекции
``````````````````````````````````````````````````````````

**Коллекция** – это объект-контейнер, включающий группу, как 

правило, однотипных объектов. Структура коллекций 

(collections framework) Java стандартизирует способ, с

помощью которого ваши программы хранят и обрабатывают 

группы объектов.


Структура коллекций:


#. Интерфейсы
#. Реализации
#. Алгоритмы

Преимущества использования структуры коллекций:


#. Избавление от рутинных операций по кодированию стандартных структур данных и алгоритмов
#. Высокая эффективность реализации
#. Универсальность и простота изучения(различные типы коллекций работают похожим друг на друга образом и с высокой степенью способности к взаимодействию)
#. Расширяемость 

Структура коллекций находится в пакете **java.util.***


Интерфейсы
-----------------------------------------------------------

Все коллекции в Java являются параметризованными



.. code-block:: java

 public interface Collection<E>...




.. image:: _static/12/collections.png

Корень иерархии. Задает самые общие методы для работы с коллекциями.




.. code-block:: java

 public interface Collection<E> extends Iterable<E> 
 {   int size();
     boolean isEmpty();
     boolean contains(Object element);
     boolean add(E element);         
     boolean remove(Object element); 
     Iterator<E> iterator();
     ...




.. code-block:: java

 ...
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c); 
    boolean removeAll(Collection<?> c);        
    boolean retainAll(Collection<?> c);        
    void clear(); 
    Object[ ] toArray();
 }



Перемещение
-----------------------------------------------------------

Первый способ:



.. code-block:: java

 for (Object o : collection)
    System.out.println(o);


Второй способ:



.. code-block:: java

 public interface Iterator<E> 
 {
    boolean hasNext();
    E next();
    void remove(); 
 }




.. code-block:: java

 Collection <String> cs = new ArrayList<String>();
 cs.add("1");
 cs.add("2");
 cs.add("3"); 
 String str = new String();
 for (str : cs)
   System.out.println(str);




.. code-block:: java

 Collection <String> cs = new ArrayList<String>();
 cs.add("1");
 cs.add("2");
 cs.add("3"); 
 Iterator it = cs.iterator();
 while(it.hasNext())
    System.out.println(it.next());


Метод **remove()** может быть вызван только один раз 

после вызова метода **next()**, иначе бросается исключение.

Метод **remove()** единственный безопасный способ 

модификации коллекции.   



.. code-block:: java

 while(!col1.isEmpty()) {
   Iterator it = col1.iterator();
   Object o = it.next();
   System.out.println("Удаляем:" + o);
   it.remove();
 }



Обзор коллекций
===========================================================


Set
``````````````````````````````````````````````````````````

**Set** – коллекция без повторяющихся элементов 

(математическое множество). Методы

совпадают с **Collection** но **add()** вернет **false**,

если элемент уже есть в коллекции. 



.. code-block:: java

 import java.util.*;
 public class FindDups {
     public static void main(String[ ] args) {
         Set<String> s = new HashSet<String>();
         for (String a : args)
             if (!s.add(a))
                 System.out.println("Duplicate detected: " + a);
         System.out.println(s.size() + " distinct words: " + s);
     }
 }


Интерфейс **SortedSet** из пакета **java.util**, 

расширяющий интерфейс **Set**, описывает 

упорядоченное множество, отсортированное

по естественному порядку возрастания его

элементов или по порядку, заданному

реализацией интерфейса **Comparator**.

Элементы не нумеруются, но есть понятие

первого, последнего, большего и меньшего

элемента.


* **Comparator Comparator()** — возвращает способ упорядочения коллекции;
* **Object first ()** — возвращает первый, меньший элемент коллекции;
* **SortedSet headSet (Object toElement)** — возвращает начальные, меньшие элементы до элемента toElement исключительно;
* **Object last()** — возвращает последний, больший элемент коллекции;
* **SortedSet subSet(Object fromElement, Object toElement)** — возвращает подмножество коллекции от элемента fromElement включительно до элемента toElement исключительно;
* **SortedSet tailSet (Object fromElement)** — возвращает последние, большие элементы коллекции от элемента fromElement включительно.

List
``````````````````````````````````````````````````````````

Интерфейс **List** из пакета **java.util**, 

расширяющий интерфейс **Collection**, 

описывает методы работы с упорядоченными 

коллекциями. Иногда их называют 

последовательностями (sequence). Элементы 

такой коллекции пронумерованы, начиная от 

нуля, к ним можно обратиться по индексу. В 

отличие от коллекции **Set** элементы коллекции 

**List** могут повторяться.


* **void add(int index, Object obj)** — вставляет элемент obj в позицию index; старые элементы, начиная с позиции index, сдвигаются, их индексы увеличиваются на единицу;
* **boolean addAll(int index, Collection coll)** — вставляет все элементы коллекции coll;
* **Object get(int index)** -— возвращает элемент, находящийся в позиции index;
* **int indexOf (Object obj)** — возвращает индекс первого появления элемента obj в коллекции;

* **int lastIndexOf (Object obj)** — возвращает индекс последнего появления элемента obj в коллекции;
* **ListIterator listIterator()** — возвращает итератор коллекции;
* **ListIterator listIterator (int index)** — возвращает итератор конца коллекции от позиции index;
* **Object set (int index, Object obj)** — заменяет элемент, находящийся в позиции index, элементом obj;
* **List subList(int from, int to)** — возвращает часть коллекции от позиции from включительно до позиции to исключительно.

Map
``````````````````````````````````````````````````````````

Интерфейс **Map** из пакета **java.util** описывает

коллекцию, состоящую из пар "ключ — значение". 

У каждого ключа только одно значение, что

соответствует математическому понятию

однозначной функции или отображения. Такую

коллекцию часто называют еще словарем

(dictionary) или ассоциативным массивом

(associative array).


* **boolean containsKey (Object key)** — Проверяет наличие ключа key;
* **boolean containsValue (Object value)** — Проверяет наличие значения value;
* **Set entrySet()** — представляет коллекцию в виде множества, каждый элемент которого — пара из данного отображения, с которой можно работать методами вложенного интерфейса Map.Entry;
* **Object get(Object key)** -— возвращает значение, отвечающее ключу key;

* **Set keySet()** — представляет ключи коллекции в виде множества;
* **Object put (Object key, Object value)** — добавляет пару "key— value", если такой пары не было, и заменяет значение ключа key, если такой ключ уже есть в коллекции;
* **void putAll (Map m)** — добавляет к коллекции все пары из отображения m;
* **Collection values()** — представляет все значения в виде коллекции.
* методы **getKey()** и **getValue()** позволяют получить ключ и значение пары;
* метод **setValue (Object value)** меняет значение в данной паре.


.. code-block:: java

 for (Iterator it=map.entrySet().iterator(); it.hasNext(); ) 
 {
     Map.Entry entry = (Map.Entry)it.next();
     Object key = entry.getKey();
     Object value = entry.getValue();
 }



SortedMap
``````````````````````````````````````````````````````````

Интерфейс **SortedMap**, расширяющий интерфейс 

**Map**, описывает упорядоченную по ключам 

коллекцию Map. Сортировка производится либо в 

естественном порядке возрастания ключей, либо 

в порядке, описываемом в интерфейсе 

**Comparator**.


* **Comparator comparator()** — возвращает способ упорядочения коллекции;
* **Object firstKey()** — возвращает первый, меньший элемент коллекции;
* **SortedMap headMap (Object toKey)** — Возвращает начало коллекции до элемента с ключом toKеу исключительно;
* **Object lastKey()** — возвращает последний, больший ключ коллекции;
* **SortedMap subMap (Object fromKey, Object toKey)** — возвращает часть коллекции от элемента с ключом fromKey включительно до элемента с ключом toKey исключительно;
* **SortedMap tailMap(Object fromKey)** — возвращает остаток коллекции от элемента fromKey включительно.

ListIterator
``````````````````````````````````````````````````````````


* **void add(Object element)** — добавляет элемент element перед текущим элементом;
* **boolean hasPrevious()** — возвращает true, если в коллекции есть элементы, стоящие перед текущим элементом;
* **int nextIndex()** — возвращает индекс текущего элемента; если текущим является последний элемент коллекции, возвращает размер коллекции;	
* **Object previous()** — возвращает предыдущий элемент и делает его текущим;
* **int previousIndex()** — возвращает индекс предыдущего элемента;
* **void set(Object element)** — заменяет текущий элемент элементом element; выполняется сразу после next() или  previous().

Comparator
``````````````````````````````````````````````````````````


* **int compare (Object obj1, object obj2)** — возвращает отрицательное число, если obj1 в каком-то смысле меньше obj2; нуль, если они считаются равными; положительное число, если objl больше obj2. С точки зрения теории множеств можно сказать, что этот метод сравнения обладает свойствами тождества, антисимметричности и транзитивности;
* **boolean equals (Object obj)** — сравнивает данный объект с объектом obj, возвращая true, если объекты совпадают в каком-либо смысле, заданном этим методом.

Реализации
``````````````````````````````````````````````````````````


.. image:: _static/12/structure.png


.. image:: _static/12/table.png



.. code-block:: java

 class ComplexCompare implements Comparator {
    public int compare(Object obj1. Object obj2) { 
    Complex z1 = (Complex)obj1, z2 = (Complex)obj2;
    double re1 = z1.getRe(), im1 = z1.getlm();
    double re2 = z2.getRe(), im2 = z2.getlm();
    if (re1 != re2) 
      return (int)(re1 - re2);
    else if (im1 != im2) 
      return (int)(im1 — im2) ;
    else 
      return 0;
    }
    public boolean equals(Object z){ 
    	   return compare (this, z) ==  0;
    }
 }




.. code-block:: java

 TreeSet ts = new TreeSet(new ComplexCompare());
 ts.add(new Complex(1.2, 3.4));
 ts.add(new Complex(-1.25, 33.4));
 ts.add(new Complex(1.23, -3.45));
 ts.add(new Complex(16.2, 23.4));
 
 Iterator it = ts.iterator();
 while(it.hasNext())
 	((Complex)it.next()).print();



Сортировка
``````````````````````````````````````````````````````````

Сортировка может быть сделана только в 

упорядочиваемой коллекции, реализующей 

интерфейс **List**.

Методы: 


* **static void sort (List coll)** — сортирует в естественном порядке возрастания коллекцию coll, реализующую интерфейс List;
* **static void sort (List coll, Comparator с)** — сортирует коллекцию coll в порядке, заданном объектом с. 


.. code-block:: java

 public class Sort {
     public static void main(String[ ] args) {
         List<String> list = Arrays.asList(args);
         Collections.sort(list);
         System.out.println(list);
     }
 }



Поиск
``````````````````````````````````````````````````````````


* **static int binarySearch(List coll, Object element)** — отыскивает элемент element в отсортированной в естественном порядке возрастания коллекции coll и возвращает индекс элемента или отрицательное число, если элемент не найден; отрицательное число показывает индекс, с которым элемент element был бы вставлен в коллекцию, с обратным знаком;
* **static int binarySearch(List coll, Object element. Comparator с)** — то же, но коллекция отсортирована в порядке, определенном объектом с.

Манипуляции
``````````````````````````````````````````````````````````


* **reverse(List coll)** меняет порядок расположения элементов на обратный.
* **copy(List from, List to)** копирует коллекцию from в коллекцию to.
* **fill(List coll, Object element)** заменяет все элементы существующей коллекции coll элементом element.
* **swap(List coll, int i1, int i2)** меняет местами элементы 

* **static Object max (Collection coll)** – возвращает наибольший в естественном порядке элемент коллекции coll;
* **static Object max (Collection coll, Comparator c)** — то же в порядке, заданном объектом с;
* **static object min (Collection coll)** — возвращает наименьший в естественном порядке элемент коллекции coll;
* **static Object min (Collection coil, Comparator c)** — то же в порядке, заданном объектом с.


* **int frequency(Collection coll, Object element)** — считает кол-во появлений указанного элемента в коллекции 
* **disjoint(Collection coll1, Collections coll2)** — определяет пересекаются ли две коллекции

Вопросы для самоконтроля
=============================================