Практика по Java

x02-2015 (практика по Java) группа

Юрий Литвинов

Студент TODO №1 №2 №3 №4 Тест 1 №5 №6 №8 №9 №10 №11 Тест 2 Тест 3 №13 Тест 4
87 Хеш-таблица Хеш-таблица-2 Матрицы Trie Maybe Дерево FP MyTreeSet Zip Streams Сериализация БД Rule Пул потоков Injector SmartList Дополнительная задача LinkedHashMap
Белова Татьяна 4
Веселов Иван 4
Винерский Глеб 9
Винниченко Максим 6
Кощенко Екатерина 5
Привалихин Алексей 16
Свидченко Олег 6
Севастюк Дмитрий 15
Тонких Андрей 6
Черепанов Валерий 6
Шавкунов Михаил 4
Щербин Егор 6

Задачи

Тест 4. 28.12.16
  1. LinkedHashMap

    Необходимо реализовать интерфейс Map так, чтобы во время итерации объекты выдавались в порядке добавления.
    Пользоваться LinkedHashMap и другими библиотечными контейнерами нельзя, Abstract* можно.
    Удаление по итератору можно не реализовывать, в возвращаемом Set<Entry<E>> должны работать только iterator и size.
    Инвалидацию итераторов можно не реализовывать.
    Асимптотика всех операций должна соответствовать ожидаемой от HashMap-а.

Домашняя работа 13. 27.12.16
  1. Дополнительная задача

    Существуют поставщики и потребители сообщений, а также их преобразователи и фильтры.
    Поставщики передают сообщения координатору с опреденной "пометкой", тот их пропускает через фильтры, передает преобразователю, а потом посылает потребителям, ожидающим сообщения с соответствующей "пометкой".

    Поставщики наследуют интерфейс BroadcastSender, в котором определены следующие методы:

    • String getTopic() -- возвращает тему сообщений, публикуемых поставщиком. Должен возвращать всегда одно и то же значение.
    • void setCoordinator(...) -- указывает поставщику, куда передавать сообщения.
    • void run() -- запускает поставщик.

    Потребители наследуют интерфейс BroadcastReceiver, в котором определено следующее:

    • Set<String> getTopics() -- возвращает темы сообщений, ожидаемых поставщиком. Должен возвращать всегда одно и то же.
    • receive(...) -- вызывается координатором, когда тот передает сообщение получателю.

    Фильтры наследуют интерфейс Filter, в котором определено следующее:

    • Set<String> getTopics() -- см. выше.
    • boolean filter(...) -- возвращает true, если фильтр пропустил сообщение.

    На одну тему может быть [0; +inf) фильтров.

    Преобразователи наследуют интерфейс Function, в котором определено следующее:

    • Set<String> getTopics() -- см. выше.
    • ... apply(...) -- преобразование сообщения.

    На одну тему может быть [0; 1] преобразователей. Преобразователь обязан не менять тип данных в сообщении, поскольку данные будут передаваться получателям с той же темой.

    Как должно работать:

    • Координатор загружает из указанной папки классы с поставщиками, потребителями и т.п., создает их экземпляры, вызывая конструкторы без параметров.
    • Запускает каждого поставщика в отдельном потоке
    • Разбирает поступившие сообщения в отдельном потоке.
    • Проверяет ограничения, наложенные на преобразователи.
    • Может оптимизировать свою работу исходя из вышеописанных ограничений

    Задача: реализовать такой механизм передачи сообщений
    Стоимость: 20 баллов

Тест 3. 21.12.16
Юнит-тесты, которые должны проходить
  1. SmartList
    • Необходимо создать класс SmartList, реализующий интерфейс java.util.List.
    public class SmartList<E> implements List<E> {
        ...
    }
    
    • Основная идея — реализовать изменяемый список так, чтобы он был оптимизирован для хранения небольшого количества элементов, но при этом в него можно было добавить произвольное их число.

    • В классе должно быть объявлено ровно два поля:

      • типа int для хранения размера
      • ссылочного типа для хранения данных
    • В зависимости от текущего размера списка в поле для данных хранятся значения разных типов:

      • Если список пуст, то значение этого поля должно быть null
      • Если в списке ровно один элемент, то в этом поле должна храниться ссылка на него
      • Если в списке от 2 до 5 элементов, то в этом поле хранится массив размера 5, элементы которого указывают на соответствующие элементы списка
      • Иначе в этом поле хранится ссылка на обычный ArrayList, в котором хранятся все элементы
    • В классе должно быть определено два конструктора:

      • По умолчанию (без параметров), создает пустой список
      • Принимающий один параметр — коллекцию, элементы которой должны быть добавлены в список
    • Maven/Gradle проект

    • При реализации рекомендуется наследовать ваш класс от AbstractList (хотя он добавляет еще одно поле), и нельзя наследоваться от ArrayList.

    • Стандартные операции коллекций (add/contains/remove и т.д.) должны работать за то же время, что и аналогичные методы в стандартной реализации ArrayList.

Домашняя работа 12. 14.12.16
Enum-ы в Java (презентация)
Тест 2. 07.12.16
Презентация с условием
Классы Injector и исключения
  1. Injector

    Необходимо реализовать статический метод Injector.initialize, эмулирующий работу контейнера Dependency Injection. Его основная задача – создать объект класса, полное имя которого передано в параметре rootClassName. Также в метод передается набор доступных классов реализаций. Для каждого такого класса за один initialize должно быть создано не более одного экземпляра. Гарантируется, что каждый класс содержит ровно один конструктор.

    • Параметры конструктора определяют зависимости данного класса:

    public class A {
    public A(Interface1 x) {}
    }

    public class B implements Interface1 {}

    • Класс A зависит от интерфейса Interface1 (так же зависимостью может быть абстрактный или конкретный класс). Таким образом, чтобы создать объект класса A, можно сначала создать объект класса B и передать его в конструктор.
    • Понятно, что зависимости могут быть несколько более замысловатыми.
    • Метод initialize должен завершиться с исключением AmbiguousImplementationException, если найдено несколько разных классов-реализаций одной и той же зависимости (зависимости – это только те классы и интерфейсы, которые встречаются в конструкторах).
    • Метод initialize должен завершиться с исключением ImplementationNotFoundException, если для какой-то зависимости не найдено ни одной реализации.
    • Метод initialize должен завершиться с исключением InjectionCycleException, если зависимости прямо или косвенно образуют цикл.
    • В остальных случаях метод должен вернуть объект класса rootClassName.
Домашняя работа 11. 30.11.16
Продвинутый JUnit (презентация)
  1. Rule

    Реализовать Rule для JUnit, позволяющий регистрировать потоки и проверяющий, что к концу теста они все завершились без исключений.

  2. Пул потоков

    Реализовать простой пул задач с фиксированным числом потоков (число задается в конструкторе)

    • При создании объекта ThreadPoolImpl в нем должно начать работу n потоков
    • У каждого потока есть два состояния: ожидание задачи / выполнение задачи
    • Задача — вычисление некоторого значения, вызов get у объекта типа Supplier<R>
    • При добавлении задачи, если в пуле есть ожидающий поток, то он должен приступить к ее исполнению. Иначе задача будет ожидать исполнения, пока не освободится какой-нибудь поток
    • Задачи, принятые к исполнению, представлены в виде объектов интерфейса LightFuture
    • Метод shutdown должен завершить работу потоков. Для того, чтобы прервать работу потока, рекомендуется пользоваться методом Thread.interrupt()
    • LightFuture
      • Метод isReady возвращает true, если задача выполнена
      • Метод get возвращает результат выполнения задачи
      • В случае, если соответствующий задаче supplier завершился с исключением, этот метод должен завершиться с исключением LightExecutionException
      • Если результат еще не вычислен, метод ожидает его и возвращает полученное значение
      • Метод thenApply — принимает объект типа Function, который может быть применен к результату данной задачи X и возвращает новую задачу Y, принятую к исполнению
      • Новая задача будет исполнена не ранее, чем завершится исходная
      • В качестве аргумента объекту Function будет передан результат исходной задачи, и все Y должны исполняться на общих основаниях (т.е. должны разделяться между потоками пула)
      • Метод thenApply может быть вызван несколько раз
      • Метод thenApply не должен блокировать работу потока, если результат задачи X ещё не вычислен

    При этом:

    • В данной работе запрещено использование содержимого пакета java.util.concurrent
    • Все интерфейсные методы должны быть потокобезопасны
    • Для каждого базового сценария использования должен быть написан несложный тест
    • Также должен быть написан тест, проверяющий, что в пуле действительно не менее n потоков

    Дедлайн: 21.12.2016

Домашняя работа 10. 23.11.16
Базы данных и Java (презентация)
Базы данных и Java (туториал)
  1. БД

    Реализовать на одной из рассмотренных технологий консольный телефонный справочник. Он должен уметь хранить имена и номера телефонов, при этом у одного человека может быть несколько телефонов и у одного телефона может быть несколько хозяев. Должно быть можно в интерактивном режиме (в бесконечном цикле) осуществлять следующие операции:

    • 0 - выйти
    • 1 - добавить запись (имя и телефон)
    • 2 - найти телефоны по имени
    • 3 - найти имена по телефону
    • 4 - удалить заданную пару имя-телефон
    • 5 - у указанной пары "имя-телефон" поменять имя
    • 6 - у указанной пары "имя-телефон" поменять телефон
    • 7 - распечатать все пары имя-телефон в справочнике

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

    Дедлайн: 07.12.2016

Домашняя работа 9. 16.11.16
Презентация с пары
  1. Сериализация
    • Реализовать класс Serialization с двумя статическими функциями:
      • void serialize(Object, OutputStream)
      • Записывает состояние полей переданного объекта в поток
      • T deserialize(InputStream, Class<T>)
      • Создаёт экземпляр класса и инициализирует его поля данными из потока
    • Считается, что в сериализации/десериализации используются объекты:
      • классы которых имеют публичный конструктор без параметров
      • типы полей ограничены примитивными типами и строками

    Дедлайн: 30.11.2016.

Домашняя работа 8. 09.11.16
Особенности Java 7 (презентация)
  1. Zip

    Программе на вход подается путь и регулярное выражение. По указанному пути надо найти все zip-архивы и извлечь все файлы, имена которых удовлетворяют регулярному выражению.

  2. Streams

    Дедлайн: 23.11.2016

Домашняя работа 7. 26.10.16
Экосистема open source-проектов (презентация)
Домашняя работа 6. 19.10.16
Презентация с пары
Интерфейс, который надо реализовать
  1. MyTreeSet

    Необходимо реализовать интерфейс MyTreeSet с использованием бинарного дерева:

    • в реализации должны быть конструктор без параметров и конструктор с параметром типа Comparator<...>
    • методы descendingIterator и descendingSet не должны копировать данные
    • удаление по итератору можно не реализовывать
    • стандартную библиотеку использовать нельзя, разрешается пользоваться Abstract* классами
    • дополнительная задача (+2 балла)
      • инвалидация итератора при модификации дерева

    Дедлайн – 09 ноября

Домашняя работа 5. 12.10.16
Разбор контрольной (презентация)
Решение, показанное на паре
  1. FP

    Реализовать аналоги стандартных интерфейсов для работы с лямбда-функциями:

    • Абстрактные классы (или интерфейсы)
      • Function1 — функция одного аргумента (“f(x)”)
      • Function2 — функция от двух аргументов (“f(x, y)”)
      • Predicate — предикат для одного аргумента
      • Нужна какая-нибудь иерархия, связывающая эти классы (интерфейсы)
      • Сигнатуры всех классов и методов должны быть максимально общими
    • Должны быть реализованы методы:
      • Function1.compose — композиция
      • принимает “Function1 g”, возвращает “g(f(x))”, например, int x = f.compose(g).apply(239);
      • Function2.compose — композиция
      • принимает “Function1 g”, возвращает “g(f(x, y))”
      • Function2.bind1 — bind первого аргумента
      • принимает первый аргумент, возвращает “f(_, y)”
      • Function2.bind2 — bind второго аргумента
      • принимает второй аргумент, возвращает “f(x, _)”
      • Function2.curry — каррирование, конвертация в “Function1”
      • например, f = (x, y) -> x + y, f(5) = x -> x + 5
    • Предикаты:
      • Predicate.or и Predicate.and
      • принимают один предикат в качестве аргумента, возвращают предикат, который ведет себя, как дизъюнкция/конъюнкция текущего предиката и предиката-аргумента
      • семантика ленивая, как у || и &&
      • Predicate.not принимает 0 аргументов, возвращает предикат-отрицание текущего предиката
      • Константные предикаты:
      • Predicate.ALWAYS_TRUE
      • Predicate.ALWAYS_FALSE
      • Можно не поля, а методы
    • Отдельный класс Collections с методами:
      • map — принимает f и a, применяет f к каждому элементу ai и возвращает список [f(a1), ..., f(an)]
      • filter — принимает p и a, возвращает список, содержащий элементы ai, на которых p(ai) == true
      • takeWhile — принимает p и a, возвращает список с началом a до первого элемента ai, для которого p(ai) == false
      • takeUnless — то же, что и takeWhile, только для p(ai) == true
      • foldr / foldl — принимает функцию двух аргументов, начальное значение и коллекцию, работает так: https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%91%D1%80%D1%82%D0%BA%D0%B0_%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0
      • a – Iterable

    Дедлайн – 26 октября

Тест 1. 05.10.16
Интерфейс, который необходимо реализовать
Юнит-тесты, которые должны проходить
  1. Multiset

    Реализовать generic-мультимножество, т.е. множество, допускающее включение одного и того же элемента по нескольку раз. Класс должен реализовывать следующий интерфейс:

    public interface Multiset<E> extends Collection<E> {
    
        /** Returns the number of occurrences of an element in this multiset.
         * Expected complexity: Same as `contains`  */
        int count(Object element);
    
        /** Returns the set of distinct elements contained in this multiset.
         * Expected complexity: O(1) */
        Set<E> elementSet();
    
        /** Returns the set of entries representing the data of this multiset.
         * Expected complexity: O(1) */
        Set<Entry<E>> entrySet();
    
        /** Elements that occur multiple times in the multiset will appear multiple times in this iterator.
         * Expected complexity: O(1) */
        @Override
        Iterator<E> iterator();
    
        interface Entry<E> {
            E getElement();
            int getCount();
        }
    }
    

    При этом:
    - стандартные операции коллекций (add/contains/remove и т.д.) должны работать за то же время, что и аналогичные методы в java.util.HashSet;
    - Java Stream API использовать нельзя;
    - remove удаляет только одно вхождение объекта;
    - size возвращает общее количество вхождений;
    - в возвращаемом Set<Entry<E>> должны быть реализованы только iterator и size;
    - итератор должен поддерживать методы hasNext/next/remove
    - итератор должен обходить элементы в порядке их добавления
    Примечания:
    - см. LinkedHash*
    - см. Abstract*
    - реализации методов в Abstract* не всегда удовлетворяют требуемой асимптотике
    - некоторые реализации методов бросают UnsupportedOperationException

    Зависимости для тестов:
    - testCompile 'junit:junit:4.12'
    - testCompile 'org.hamcrest:hamcrest-library:1.3'

Домашняя работа 4. 28.09.16
IDEA static analyzers, задачи
  1. Maybe

    Реализовать generic-класс Maybe (контейнер из одного элемента, в котором может быть, а может и не быть значение) со следующими методами:

    • public static <T> Maybe<T> just(T t) --- создаёт новый объект типа Maybe, хранящий в себе значение t
    • public static <T> Maybe<T> nothing() --- создаёт новый объект типа Maybe без хранимого значения
    • public T get() --- возвращает хранимое значение, если оно есть, бросает исключение (своё), если значения нет
    • public boolean isPresent() --- возвращает true, если значение есть, и false, если нет
    • public <U> Maybe<U> map(Function<?, ?> mapper) --- принимает функцию и возвращает новый объект Maybe со значением, полученным применением функции к хранимому значению, или пустой Maybe, если текущий Maybe пустой. Например, Maybe.just(2).map(x -> x * 2) == Maybe.just(4), Maybe.nothing().map(x -> x * 2) == Maybe.nothing(). Подумать, что надо подставить на место вопросиков в Function<?, ?>, чтобы было хорошо.

    Прочитать числа из файла:

    • если на строке действительно число, возвращается “Maybe” с числом
    • если на строке записано не число, возвращается “Maybe” с null

    Возвести в квадрат прочитанные числа и сохранить их в новый файл

    • Записать в новый файл "null", если в исходном файле на этой строке было не число
  2. Дерево

    Реализовать generic-множество с использованием двоичного дерева поиска (не обязательно сбалансированного) с операциями

    • add
    • contains
    • size

    Дедлайн --- 13 октября

Домашняя работа 3. 21.09.16
Потоки в Java, Git (презентация)
  1. Trie

    Реализовать бор (http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D0%BE%D1%80)
    Должны быть поддержаны следующие методы:

    • boolean add(String element); (возвращает true, если такой строки ещё не было, работает за O(|element|))
    • boolean contains(String element); (работает за O(|element|))
    • boolean remove(String element); (возвращает true, если элемент реально был в дереве, работает за O(|element|))
    • int size(); (работает за O(1))
    • int howManyStartsWithPrefix(String prefix); (работает за O(|prefix|))

    Также бор должен реализовывать интерфейс с методами:

    • void serialize(OutputStream out) throws IOException;
    • void deserialize(InputStream in) throws IOException; (заменяет старое дерево данными из стрима)

    Дедлайн: 07.10.2016

Домашняя работа 2. 13.09.16
Юнит-тестирование и системы сборки (презентация)
Юнит-тестирование и системы сборки (конспект)
Годная документация по Maven
Стайлгайд Google (рекомендую использовать, только отступы пусть будут 4 пробела, а не 2)
  1. Хеш-таблица-2

    Написать юнит-тесты и комментарии к задаче про хеш-таблицу.

  2. Матрицы
    • Вывести элементы двумерного массива NxN (N - нечетное) в порядке обхода по спирали с началом в центре.
    • Отсортировать столбцы матрицы по первым элементам.

    Написать скрипт сборки для этой задачи на Maven или Gradle, научиться собирать и запускать из консоли.
    Юнит-тесты и комментарии обязательны.

Домашняя работа 1. 10.09.16
Презентация с пары (которую не удалось показать в силу отсутствия проектора)
Конспект с пары
  1. Хеш-таблица

    Реализовать хеш-таблицу с ключами и значениями типа String, у которой есть следующие функции:
    - int size() --- количество ключей в хеш-таблице
    - boolean contains(String key) --- true, если данный ключ содержится в хеш-таблице
    - String get(String key) --- возвращает значение по ключу, или null, если такого значения нет
    - String put(String key, String value) --- положить в хеш-таблицу значение value по ключу key и вернуть то, что было по этому ключу раньше, либо null, ели ничего не было
    - String remove(String key) --- удалить значение по заданному ключу из хеш-таблицы и вернуть удалённое значение, либо null, если такого значения не было
    - void clear() --- очистить хеш-таблицу

    Классы стандартной библиотеки типа HashMap или List использовать нельзя.

    Задание надо сдать в виде пуллреквеста из отдельной ветки в собственный репозиторий, в который меня надо добавить как коллаборатора. Мой профиль на гитхабе: https://github.com/yurii-litvinov. Ожидаются комментарии в формате JavaDoc и юнит-тесты, которые мы ещё не проходили, так что можно их пока не делать. Ссылку на пуллреквест надо скинуть сюда, как решение. Жесткий дедлайн: 23:59:59 20 сентября, но начинать пытаться сдавать надо гораздо раньше.

© 2014-2018 HwProj