Тема 7 — Алгоритми на Collections Framework

Collections Framework не е просто набор от контейнери — той включва и статична колекция от алгоритми, изпълнявани върху тях чрез класа java.util.Collections. Тези алгоритми покриват сортиране, търсене, разместване, манипулации и намиране на екстремуми. Ключовото архитектурно решение е, че алгоритмите работят с интерфейса (List, Collection), а не с конкретна имплементация — замяна на ArrayList с LinkedList не изисква промяна на алгоритъма.

1. Сортиране

1.1 Принципи — `Comparable` и `Collections.sort`

Всеки клас, имплементиращ Comparable<T>, дефинира естествена подредба чрез метода compareTo. Collections.sort(list) ползва тази подредба:

String[] arr = {"i", "walk", "the", "line"};
List<String> list = Arrays.asList(arr);
Collections.sort(list);
System.out.println(list); // [i, line, the, walk]

Вградените типове имат предефинирана естествена подредба:

Тип	Принцип
`Byte`, `Short`, `Integer`, `Long`, `Double`, `Float`, `BigInteger`, `BigDecimal`	Числа със знак
`Character`	Числа без знак
`Boolean`	`FALSE < TRUE`
`File`	Лексикографски по файлово имен
`String`	Лексикографски (по Unicode)
`Date`	Хронологично
`CollationKey`	Лексикографски с локали (Regional Settings)

1.2 Имплементиране на `compareTo`

public class Student extends Person implements Comparable<Student> {
    // Нарастващ ред по факултетен номер:
    public int compareTo(Student o) {
        return strFacNumer.compareTo(o.strFacNumer);
    }
}

1.3 Локализирано сортиране — `CollationKey`

Стандартният String.compareTo не отчита национални азбучни наредби (напр. А < Б < В в Bulgarian locale). CollationKey решава проблема:

import java.text.Collator;
import java.text.CollationKey;

class Person implements Comparable {
    private static final Collator collator = Collator.getInstance(Locale.getDefault());
    private final CollationKey sortKey;

    public Person(String firstName, String lastName) {
        sortKey = collator.getCollationKey(lastName.toUpperCase() + firstName.toUpperCase());
    }
    public CollationKey getSortKey() { return sortKey; }

    public int compareTo(Object o) {
        return sortKey.compareTo(((Person)o).getSortKey());
    }
}

1.4 Непроменяеми (immutable) класове за колекции

Обектите, записани в Set или използвани като ключове в Map, не трябва да се променят след вмъкване — промяна би нарушила инвариантите на структурата. Изисквания:

Конструкторът хвърля NullPointerException при null аргументи;
hashCode() е предефиниран (равни обекти ↔ равни хеш кодове);
equals() връща false при null и при различен клас;
Полетата са final — без set методи.

public class Name implements Comparable<Name> {
    private final String firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName  = lastName;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Name)) return false;
        Name n = (Name) obj;
        return firstName.equals(n.firstName) && lastName.equals(n.lastName);
    }

    public int hashCode() {
        return 31 * firstName.hashCode() + lastName.hashCode();
    }

    public String toString() { return firstName + " " + lastName; }

    public int compareTo(Name nm) {    // каскадно сравнение
        int cmp = lastName.compareTo(nm.lastName);
        return cmp != 0 ? cmp : firstName.compareTo(nm.firstName);
    }
}

// Употреба:
Name[] arr = {new Name("John","Lennon"), new Name("Karl","Marx"),
              new Name("Groucho","Marx"), new Name("Oscar","Grouch")};
List<Name> names = Arrays.asList(arr);
Collections.sort(names);
// [Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]

2. Интерфейсът `Comparator`

Когато естествената подредба е недостатъчна или обектът не имплементира Comparable, се ползва Comparator — обект, капсулиращ специфична подредба:

public interface Comparator<T> {
    int compare(T o1, T o2); // отрицателно / 0 / положително
}

2.1 Клас-сравнители

class LastNameComparator implements Comparator<Person> {
    public int compare(Person a, Person b) {
        return a.getLastNameKey().compareTo(b.getLastNameKey());
    }
}

// Употреба:
Collections.sort(list, new LastNameComparator());

2.2 Анонимен `Comparator`

static final Comparator<EMailImpl> MESSAGE_ORDER = new Comparator<EMailImpl>() {
    public int compare(EMailImpl left, EMailImpl right) {
        return left.getMessage().compareTo(right.getMessage());
    }
};
Collections.sort(results, MESSAGE_ORDER);

2.3 Каскадно сравняване

Когато основният критерий е равен, добавят се допълнителни — предотвратява грешно изключване на дублирани по основен критерий обекти от SortedSet:

static final Comparator<EMailImpl> CASCADE_ORDER = new Comparator<EMailImpl>() {
    public int compare(EMailImpl left, EMailImpl right) {
        int messCmp = left.getMessage().compareTo(right.getMessage());
        if (messCmp != 0) return messCmp;
        // За цели числа: left.getNum() - right.getNum()
        return Integer.compare(left.getNum(), right.getNum());
    }
};

3. Алгоритъм за случайно разместване (`shuffle`)

Обратен на сортирането — размества елементите на List посредством случайни пермутации. Приложение: карти, хазарт, тестване.

Collections.shuffle(list);                    // с вградена случайност
Collections.shuffle(list, new Random(seed));  // с предаден Random

Имплементация (Fischer-Yates):

public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

4. Алгоритми за манипулиране на данни

Статични методи в Collections:

Метод	Описание
`reverse(List l)`	Обратен ред на елементите
`fill(List list, Object o)`	Презаписва всички елементи с дадена стойност
`copy(List dest, List src)`	Копира `src` в `dest`; `dest` ≥ размера на `src`
`swap(List<?> list, int i, int j)`	Разменя елементите на позиции `i` и `j`
`addAll(Collection<? super T> c, T... elements)`	Добавя множество елементи едновременно
`reverseOrder()`	Връща `Comparator` за обратен естествен ред

// Пример swap:
List<String> list = new ArrayList<>(Arrays.asList("Java","Android","Python","Node.js"));
Collections.swap(list, 0, 2);
// [Python, Android, Java, Node.js]

// Пример addAll:
Set<Integer> set = new HashSet<>();
Collections.addAll(set, 5, 4, 3, 2, 1);
// set = {1, 2, 3, 4, 5}

5. Двоично търсене (`binarySearch`)

Търси елемент във вече сортиран List. Две форми:

// Форма 1 — естествена подредба (compareTo):
static int binarySearch(List<? extends Comparable<? super T>> list, T key)

// Форма 2 — с Comparator:
static int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

Резултат:

Намерен: индекс [0, n-1];
Не е намерен: -(insertion point) - 1 — отрицателна стойност, от която може да се извади insertion point:

Integer[] arr = {10, 20, 50, 70, 90};
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
int index = Collections.binarySearch(list, 60);
if (index < 0)
    list.add(-index - 1, 60); // вмъква на правилната позиция за запазване на ред

6. Алгоритми за композиция

// Брои срещанията на елемент в колекция:
static int frequency(Collection<?> c, Object obj)

// Проверява дали две колекции нямат общи елементи:
static boolean disjoint(Collection<?> c1, Collection<?> c2)

// frequency:
Integer arr[] = {20, 10, 20, 30, 20, 40, 20};
int freq = Collections.frequency(Arrays.asList(arr), 20); // 4

// disjoint:
List<Integer> a = Arrays.asList(10, 20, 30, 40);
List<Integer> b = Arrays.asList(10, 20, 30, 4, 5);
Collections.disjoint(a, b); // false — имат общи елементи

7. Намиране на екстремуми (`min` / `max`)

// Естествена подредба:
T min(Collection<? extends T> coll)
T max(Collection<? extends T> coll)

// С Comparator:
T min(Collection<? extends T> coll, Comparator<? super T> comp)
T max(Collection<? extends T> coll, Comparator<? super T> comp)

List<Integer> list = Arrays.asList(-80, 40, -50, 20);
Collections.min(list);                              // -80
Collections.min(list, Collections.reverseOrder());  // 40 (max в обратен ред)
Collections.max(list);                              // 40

Комбиниран пример:

List<Integer> data = new ArrayList<>(Arrays.asList(-8, 20, -20, 8));
Collections.sort(data, Collections.reverseOrder()); // [20, 8, -8, -20]
Collections.shuffle(data);
System.out.println("Min: " + Collections.min(data));
System.out.println("Max: " + Collections.max(data));

Резюме

Collections.sort() ползва compareTo() от Comparable; за нестандартна подредба се подава Comparator.
Каскадното сравняване предотвратява загубата на обекти в SortedSet при равенство по основен критерий.
CollationKey осигурява локализирано лексикографско сортиране с правилна регионална наредба.
shuffle реализира случайно разместване (Fischer-Yates); swap, reverse, fill, copy, addAll покриват основните манипулации.
binarySearch изисква предварително сортирана колекция; отрицателният резултат кодира точката на вмъкване.
frequency и disjoint са композиционни алгоритми; min/max намират екстремуми по естествена или зададена подредба.

Тема 7 — Алгоритми на Collections Framework

1. Сортиране

1.1 Принципи — Comparable и Collections.sort

1.2 Имплементиране на compareTo

1.3 Локализирано сортиране — CollationKey