777egor777 / emailbase

User's email base. Compression available(detail description in README)

База e-mail адресов пользователей

• Описание
• Инструкция по установке
• Интерфейс
• Алгоритм сжатия
• Многопоточность
• CodeStyle
• Тесты
• Автор
• Критика и предложения
• Документация JavaDoc
• Лицензия

Описание

Программа реализует возможность проводить различные операции с базой email-ов пользователей. У одного пользователя может быть несколько email-ов, но среди них нет повторяющихся. Среди разных пользователей могут быть повторяющиеся e-mail'ы, всех таких пользоваталей в рамках процедуры "сжатия" мы можем объединить в одного. Например, база:

• user1 ->[email protected],[email protected],[email protected]
• user2 ->[email protected],[email protected]
• user3 ->[email protected],[email protected]
• user4 ->[email protected],[email protected]
• user5 ->[email protected]

Будет преобразована в базу:

• user1 ->[email protected],[email protected],[email protected],[email protected],[email protected]
• user3 ->[email protected],[email protected]

Доступны операции:

1. Вывести базу на экран
2. Перезаписать полностью базу (удалить старую и ввести новую)
3. Очистить базу (удалить всех текущих юзеров и их email-ы)
4. Добавить юзера
5. Добавить email существующему юзеру
6. Удалить юзера
7. Удалить e-mail
8. Сжать базу
9. Выйти из программы

Подробное описание каждой из операций здесь

В данной версии программы отсутствует возможность хранения базы - после выхода из программы все внесённые данные будут стёрты. Так же в данной версии программы программы взаимодействие с пользователем осуществляется через консольный интерфейс.

В версии 0.1 программы количество пользователей <= 100 и количество email-адресов у любого пользователя <= 100.

Инструкция_по_установке

Скачать JAR TODO Инструкция по запуску JAR

Интерфейс

1. Вывести базу на экран
   • База выводится в формате
     • "user#id1 ->email1, ..., emailn"
     • ...
     • "user#idm ->email1, ..., emailn"
2. Переписать базу
   1. Старые данные стираются
   2. Пользователь вводит n - число юзеров в базе (n <= 100 в нынешней версии)
   3. Далее пользователь вводит подряд каждого из n новых пользователей в следующем формате:
      1. Сначала вводится m - число email-ов у юзера (m <= 100 в нынешней версии)
      2. Далее вводятся подряд каждый из m email-ов
      3. Каждый email должен иметь формат "[email protected]", где:
         1. name - лат. буквы и цифры, длина более 3 символов
         2. service - лат. буквы, длина более 3 символов
         3. domain - строка из набора {"ru", "com", "net", "org", "edu"}
3. Очистить базу
   • Все юзеры из базы удаляются
4. Добавить юзера
   • Пользователь вводит нового юзера
   • См по аналогии с п. 2
5. Добавить email
   • Пользователь вводит id юзера, которому нужно добавить e-mail
   • Пользователь вводит e-mail по аналогии с п.2
6. Удалить юзера
   • Пользователь вводит id юзера, которого нужно удалить
7. Удалить email
   • Пользователь вводит id юзера, у которого нужно удалить e-mail
   • Программа выводит нумерованный список email-ов этого юзера
   • Пользователь вводит номер email-а, который надо удалить
8. Сжать базу
9. Выйти из программы

Алгоритм_сжатия

Способ1

Построим граф. Вершины - юзеры. Граф неориентированный. Между каждой парой юзеров, у которых есть хотя бы один совпадающий e-mail ставим ребро. Далее задача состоит в том, чтобы выделить в этом графе компоненты связности, и в каждой компоненте связности объединить юзеров. Компоненты связности будем выделять алгоритмом поиска в глубину, который работает за линейное время относительно количества вершин и рёбер графа. То есть за O(N + M), где N - количество вершин в графе, M - количество рёбер в графе. В данной программе за N будем считать количество юзеров, а за M - сумма размеров списков email-ов по всем юзерам.

• Реализация
  • В худшем случае количество рёбер может быть O(N^2), что само собой по себе несёт плохую асимптотику.
  • Мы стремимся к сложности алгоритма O(M)
  • На самом деле при данной реализации количество рёбер графа будет O(M), так как достаточно установить связь между двумя ближайшими по расположению в базе данных юзерами, имеющими данный e-mail, чтобы все юзеры с этим email-ом гарантированно были в одной компоненте связности. А значит, достаточно пройтись по всей базе e-mail'ов один раз, чтобы добавить все необходимые рёбра -> их количество будет не более чем M
• Реализация данного алгоритма представлена в главной ветке репозитория

Способ2

* Сформируем для каждого e-mail'а список id, которым он принадлежит
* Для каждого такого списка объединяем все id в одну группу - компоненту связности
* В этом случае граф строить не надо, хотя формально всё ещё можно
описывать задачу в терминах теории графов. 
* Будем использовать структуру данных
  ["Система непересекающихся множеств"](https://ru.wikipedia.org/wiki/Система_непересекающихся_множеств)
  (Disjoint-Set-Union, DSU)
* При эффективной реализации(с использлванием эвристики сжатия путей
  в комбинации с ранговой эвристикой) операции объединения множеств
  двух вершин (join(id1, id2)) и операция взятия т.н. "лидера" множества - 
  вершины, в которую мы и будем его объединять (getLeader(id1)) работают
  за O(1)
* Доказательство времени работы и подробное описание работы
  данной структуры данных можно посмотреть по 
  [ссылке](https://e-maxx.ru/algo/dsu)  

• Реализация данного алгоритма предствалена в этой ветке (TODO)

Многопоточность

В этой ветке реализована версия программы, в которой все создаваемые объекты - Immutable, что очень здорово при работе в многопоточной среде. (TODO)

Правда, в этом случае серьёзно пострадало время работы программы, ведь при каждом изменении теперь создаётся новый объект базы email-ов, на что уходит время пропорциональное её размерам.

Соответственно, если алгоритм с изменяемыми объектами работал за линейное относительно размеров базы время, алгоритм с Immutable- объектами будет работать за квадратичное относительно размеров базы время.

CodeStyle

В проекте используется Code-Style, принятый в компании Job4j:

1. Именование:
   • Осмысленные названия переменных, методов, классов, пакетов
   • Имя класса начинается с заглавной буквы
   • Имя переменной/метода/пакета - со строчной
   • При именовании используем только латинские буквы и цифры
2. Подключённый CheckStyle-плагин для контроля базовых ошибок по синтаксису
3. Кодировка файла: UTF-8
4. В каждом пакете "package-info.java" файл
5. Документация JavaDoc на весь код
   • Информация о том, что делает метод/класс/функция
   • Когда пишешь документацию, лучше понимаешь что делает метод
   • Через какое-то время самому себе и коллегам будет проще разобраться в коде
   • Ещё один повод разбивать классы на простые и однозначные методы. Так проще писать документацию
6. Избегать т.н. "magic numbers" - непонятных чисел/других констант/ литералов в коде.
   • Создавать константу с понятным именем и JavaDoc-описанием
7. Писать тесты на весь код. Стремиться к максимальному покрытию кода, не менее 80% по JaCoCo
   • Ещё один повод писать более качественный код, который можно протестировать
8. Использовать неизменяемые объекты - Immutable
   • Все поля класса - final
   • Необходимо для того чтобы код корректно работал в многопоточной среде
9. Всегда возвращать ссылку на объект. Никогда не возвращать null reference
10. Не использовать наследование! Вместо него использовать композицию
    • Задаём интерфейс
    • Реализуем "класс - предок" через него
    • "Класс - потомок" так же реализует интерфейс
    • "Класс - потомок" принимает в конструктор объект по ссылке типа интерфейса. Передавать в конструктор будем "класс-предок"
    • Таким образом мы можем добавить новое поведение к уже существующему, и осуществить "множественное наследование" благодаря интерфейсам и композиции
11. Количество строк в методе - не более 10
12. Один return на весь метод

Тесты

Весь код покрыт модульными junit-тестами. Я старался рассмотреть все возможные случаи входных данных. Если вы видите какие-то упущения и недостатки, просьба мне написать

Критика_и_предложения

Все замечания и пожелания по этому проекту просьба направлять мне на электронный адрес: [email protected]

Автор

Гераськин Егор Владимирович

Java-разработчик, стажёр в компании Job4j

[email protected]

[phone]

JavaDoc

Скачать

Лицензия

Данный проект реализуется под лицензией MIT