8.5. Основы Kotlin. Графы

Коллекции

Коллекция является так называемым надтипом как множества, так и списка. Коллекция объединяет их общие свойства и возможности. Список, помимо возможностей коллекции, имеет возможность индексирования. Множество, помимо возможностей коллекции, не добавляет в себя уже имеющиеся элементы.

Коллекция Collection<T> хранит в себе однотипные элементы типа T. Возможностями коллекции являются:

1. Определение количества элементов (размера), пустоты, непустоты.
2. Определение вхождения элемента и перебор элементов (in).
3. Сложение с другой коллекцией или с отдельным элементом.
4. Для мутирующей коллекции MutableCollection<T>, также — добавление и удаление элемента.

Коллекции используются в ситуации, когда программисту безразличен конкретный вид коллекции. В частности, многие операции, уже привычные нам для списков, на самом деле определены для коллекций.

Ассоциативные массивы (карты)

Ассоциативный массив (он же — карта или словарь) Map<K, V> подобен обычному массиву или, вернее, списку. Разница заключается в том, что индексом в списке является целое число от 0 до list.size - 1, а индексом в ассоциативном массиве может быть всё что угодно. Тип используемого индекса (ключа) определяется параметром карты K, а тип хранимых значений — параметром V. Для массива vertices, ключом является строка String (имя вершины), а значением — сама вершина Vertex.

Класс Graph использует только две операции над vertices — создание и индексацию. Для создания карты используются метод mapOf(…​) для обычной карты Map<K, V>, либо mutableMapOf(…​) для мутирующей карты. Пример вызова:

val map = mapOf("John" to 87, "Mike" to 41, "Fred" to 24)

Такой вызов создаст карту типа Map<String, Int>, ключом которой является строка, а значением — целое число. По ключу “John” карта хранит число 87 и так далее. Функция key to value создаёт пару из ключа и значения, а из перечисления пар создаётся сама карта.

Индексация для карты происходит как и для массива, но индекс должен совпадать по типу с ключом карты. В частности, индексом vertices является строка (имя интересующей нас вершины). В обычной карте можно только читать значения по ключу, а в мутирующую карту их можно добавлять. Следует отметить, что ключи в карте не могут повторяться — при попытке добавить в карту новое значение для уже существующего ключа произойдёт удаление старого значения по этому ключу.

Любопытно поведение карты при обращении по несуществующему ключу, например, map["Tom"] для карты из примера. В отличие от списка, никаких исключений при этом не формируется; однако, результат данной операции — null. Это так называемая нулевая ссылка, которая уже встречалась нам в шестом уроке. Тип результата операции обращения по индексу в данном случае Int?, что означает Int либо null.

Безопасные операции

Рассмотрим теперь подробнее функцию neighbors() из класса Graph:

    fun neighbors(name: String) = vertices[name]?.neighbors?.map { it.name } ?: listOf()

Разберём определение этой функции. Как уже говорилось выше, результат vertices[name] может оказаться нулевой ссылкой, тип этого выражения Vertex?. У типа Vertex (без ?) имеется свойство neighbors; однако, обратиться к нему просто как vertices[name].neighbors нельзя, так как null не имеет ни свойств, ни методов. Поэтому приходиться использовать так называемое безопасное обращение: vertices[name]?.neighbors. Результатом такого обращения будет значение свойства neighbors у полученной из карты вершины; если же ключа name в карте нет, то вместо вершины мы будем иметь null и результатом безопасного обращения также будет null. Тип выражения vertices[name]?.neighbors — MutableSet<Vertex>?.

В дальнейшем мы тем же способом вызываем функцию высшего порядка map, замещая каждую вершину из полученного множества её именем и получая список имён. Поскольку обращение к map тоже происходит через ?., то при отсутствии найденной вершины с самого начала вместо списка имён мы получим null. Тип выражения vertices[name]?.neighbors?.map { it.name } — List<String>?.

Наконец, в конце выражения используется так называемый Элвис-оператор. Элвис-оператор имеет два аргумента, например, a ?: b и действует так:

1. Если a не null, результат Элвис-оператора равен a.
2. Если a null, результат Элвис-оператора равен b.

В примере с neighbors и в том и в другом случае мы имеем результат типа List<String>, поэтому и данная функция имеет тип результата List<String>.