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

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

class SimpleGeneric<T>
{
    private T element;

    public T getElement() {
        return element;
    }
    public void setElement(T element) {
        this.element = element;
    }
}

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

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

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

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,"Иванов А.А.");
..

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

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

public interface Box<T> {
    public T get();
    public void put(T element);
}

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

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

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

Коллекции¶

Интерфейсы¶

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

public interface Collection<E>...

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

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

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

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

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

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

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

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

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

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

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

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

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

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 из пакета 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 из пакета 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) меняет значение в данной паре.

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

Интерфейс 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 включительно.

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

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

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

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 в порядке, заданном объектом с.

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) — определяет пересекаются ли две коллекции

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