Методы программирования 2: Множества на основе битовых полей

Используемые инструменты

• Система контроля версий Git. Рекомендуется использовать один из следующих клиентов на выбор студента: git-scm, GitHub Desktop.
• Библиотека автоматического тестирования Google Test Framework. Не требует установки, идет вместе с шаблонным проектом.
• Среда разработки Microsoft Visual Studio (> 2008).
• Утилита CMake для сборки исходных кодов. Наличие данной утилиты опционально. Она может быть использована для генерации решения для среды разработки, отличной от Microsoft Visual Studio.

Общая структура проекта

Структура проекта:

• gtest - библиотека Google Test.
• include - директория для размещения заголовочных файлов.
• samples - директория для размещения демо-приложений.
• sln - директория с файлами решений и проектов для VS 2008 и VS2010, вложенные директории vc9 и vc10 соответственно.
• src - директория с исходными кодами.
• test - директория с тестами и основным приложением, инициализирующим запуск тестов.
• .gitignore - перечень расширений файлов, игнорируемых Git при добавлении файлов в репозиторий.
• README.md - информация о проекте, которую вы сейчас читаете.
• CMakeLists.txt - корневой файл для сборки проекта с помощью CMake. Может быть использован для генерации проекта в среде разработки, отличной от Microsoft Visual Studio.
• .travis.yml - конфигурационный файл для системы автоматического тестирования Travis-CI. Тесты, входящие в состав шаблонного проекта, регулярно проверяются на удаленной инфраструктуре.

В решении содержатся следующие модули:

• Модуль tbitfield (./include/tbitfield.h, ./src/tbitfield.cpp), содержащий реализацию класса битового поля. Предполагается, что в ходе выполнения работы реализуются методы класса (в файле ./src/tbitfield.cpp), при этом заголовочный файл (./include/tbitfield.h) с объявлениями должен оставаться неизменным.
• Модуль tset (./include/tset.h, ./src/tset.cpp), содержащий реализацию класса множества. При выполнении работы так же, как и в случае класса битового поля, разрабатывается только реализация методов класса.
• Тесты для классов битовое поле и множество (./test/test_tbitfield.cpp, ./test/test_tset.cpp).
• Пример использования класса битового поля и множества для поиска простых чисел с использованием алгоритма, называемого "Решетом Эратосфена" (./samples/sample_prime_numbers.cpp).

Цели и задачи

Цель данной работы -- разработка структуры данных для хранения множеств с использованием битовых полей, а также освоение таких инструментов разработки программного обеспечения, как система контроля версий Git и фрэймворк для разработки тестов Google Test Framework.

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

Выполнение работы предполагает решение следующих задач:

1. Реализация заданного интерфейса класса битового поля TBitField.
2. Реализация заданного интерфейса класса множества TSet.
3. Обеспечение работоспособности тестов и примера использования.

Инструкция по выполнению работы

1. Создайте локальную копию репозитория. Последовательность действий, которую необходимо выполнить описана перед началом работы с проектом, описана в разделе Общие инструкции по работе с Git.
2. Откройте решение bitfield.sln из директории sln:
   • Если установлена Visual Studio 2008, то решение находится во вложенной директории vc9.
   • Если установлена Visual Studio 2010, то решение находится во вложенной директории vc10.
   • Если установлена более высокая версия Visual Studio, то выберите любую из указанных директорий. При открытии решения будет выполнена автоматическая конвертация решения и проектов. В открытом решении имеются следующие проекты: - gtest -- статическая библиотека Google Test Framework. В ходе выполнения работы не требует редактирования. - sample_prime_numbers -- пример реализации алгоритма поиска простых чисел "Решето Эратосфена". Обратите внимание, что файл содержит две реализации алгоритма, первая использует класс битового поля, вторая -- класс множества. Текущая компилируемая версия основной функции зависит, объявлена ли переменная USE_SET или нет (строка кода #define USE_SET). Реализация алгоритма также не требует модификации. - bitfield -- статическая библиотека, содержащая модули tbitfield и tset. - test_bitfield -- тестовое приложение. В ходе выполнения работы не требует редактирования.
3. Разработайте начальную реализацию методов классов TBitField и TSet (файлы ./src/tbitfield.cpp и ./src/tset.cpp). На первом этапе в качестве реализации предлагается поместить "заглушки", чтобы обеспечить успешную компиляцию решения. При этом тесты могут не проходить, а пример использования не работать.
4. Скомпилируйте решение и запустите тестовое приложение.
   1. Для сборки решения воспользуйтесь командой Rebuild Solution контекстного меню, которое появляется при нажатии правой кнопки мыши на решении в Solution Explorer.
   2. Запустите командную строку cmd.exe из директории, в которую попали бинарные файлы.
   3. Вызовите в командной строке тестовое приложение test_bitfield.exe.
5. Последовательно реализуйте конструкторы, операции вставки/удаления, перегруженные операции класса TBitField.
   • После реализации каждого метода пересобирайте решение и запускайте тесты, чтобы отслежить корректность исполнения тестов для реализуемого метода.
   • Когда вы убедились, что метод работает корректно необходимо зафиксировать изменения в локальном репозитории (команды git add и git commit, подробнее в разделе Общие инструкции по работе с Git).
6. После того, как вы убедились, что ВСЕ тесты для класса битового поля отрабатывают корректно, запустите приложение sample_prime_numbers.exe и проверьте его работоспособность для битовых полей (директива #define USE_SET должна быть закомментирована).
7. Последовательно реализуйте конструкторы, операции вставки/удаления, перегруженные операции класса TSet.
   • После реализации каждого метода пересобирайте решение и запускайте тесты, чтобы отслежить корректность исполнения тестов для реализуемого метода.
   • Когда вы убедились, что метод работает корректно необходимо зафиксировать изменения в локальном репозитории (команды git add и git commit, подробнее в разделе Общие инструкции по работе с Git).
8. После того, как вы убедились, что ВСЕ тесты для класса битового поля отрабатывают корректно, запустите приложение sample_prime_numbers.exe и проверьте его работоспособность для битовых полей (директива #define USE_SET должна быть раскомментирована).
9. Чтобы обеспечить возможность удаленной проверки работы (включая автоматический запуск и проверку корректности тестов), необходимо создать Pull Request в upstream-репозиторий. Подробнее, как создать Pull Request, в разделе Общие инструкции по работе с Git.

Общие инструкции по работе с Git

В данном разделе описана типичная последовательность действий, которую необходимо выполнить перед тем, как начать работать с проектом. Далее для определенности используется репозиторий mp2-lab1-bitfield.

1. Создать аккаунт на github.com, если такой отсутствует. Для определенности обозначим аккаунт github-account.

2. Сделать fork репозитория https://github.com/UNN-VMK-Software/mp2-lab1-bitfield (в терминологии Git upstream-репозиторий) к себе в личный профиль с названием github-account. В результате будет создана копия репозитория с названием https://github.com/github-account/mp2-lab1-bitfield (origin-репозиторий).

3. Клонировать origin репозиторий к себе на локальный компьютер, воспользовавшись следующей командой:

$ git clone https://github.com/github-account/mp2-lab1-bitfield

1. Перейти в директорию mp2-lab1-bitfield:

$ cd ./mp2-lab1-bitfield

1. Настроить имя пользователя, из под которого будут выполняться все операции с репозиторием Git:

$ git config --local user.name "github-account"

Чтобы обеспечить возможность удаленной проверки работы (включая автоматический запуск и проверку корректности тестов), необходимо создать Pull Request в upstream-репозиторий:

1. Открыть в браузере https://github.com/github-account/mp2-lab1-bitfield.
2. Нажать кнопку Pull Request в строке над исходными кодами, содержащей информацию о последних коммитах.

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

1. Получить список текущих изменений:

$ git status

1. Пометить файл как добавленный в текущую ветку репозитория (файл будет добавлен после выполнения команды commit):

$ git add [<file_name>]
# <file_name> - название файла для добавления в commit
  если вместо имени указан символ *, то будут добавлены все новые файлы, 
  расширение которых не указано в .gitignore

1. Добавить изменения в текущую ветку локального репозитория:

$ git commit [-m "<message_to_commit>"] [-a]
# [-a] - автоматически добавляет изменения для существующих на сервере файлов
  без выполнения команды git add
# [--amend] - перезаписывает последний коммит (используется, если не забыты
  изменения)

1. Разместить изменения, которые были добавлены в локальный репозиторий с помощью команды push:

$ git push origin/master

1. Удалить файлы или директории (!без опции -f для файлов, состояния которых совпадают с состоянием на сервере):

$ git rm [-f] [--cached]
# [-f] - принудительное удаление (файла с измененным состоянием)
# [--cached] - удаление файлов на сервере, но не в локальной директории

1. Переименовать файлы (или 3 команды: mv, git rm, git add):

$ git mv <file_from> <file_to>