cpptplabs

Интерпретаторы для работы с различными стуктурами данных. Геометрия, стандартная библиотека, заданный стиль кодирования, модульные архитектурыне шаблоны.

Геометрия

Как получить ограничивающий прямоугольник многоугольника? вот так

Cтандартная библиотека

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

Заданный стиль кодирования

Как оформить код там где это можно сделать не однозначно? Прочитай coding guidelines (см ниже) и помни о нем всегда.

Модульные архитектурыне шаблоны

Как сделать метод класса, у которого в начале делается одно действие для всех подклассов а потом делается то что специфично для конкретного подкласса? вот так

задания

Геометрические фигуры (T1)

Все числовые данные в этой работе должны быть представлены значениями с плавающей запятой. Использование контейнеров стандартной библиотеки в настоящей работе недопустимо (за исключением std::string для обработки ввода)

1. Создать файл base-types.hpp, содержащий определения следующих структур: • point_t, представляющую собой точку на плоскости, координаты должны храниться в полях x и y. • rectangle_t, описывающую прямоугольник шириной width и высотой height с центром в точке pos.
2. Создать файл shape.hpp, содержащий определение абстрактного класса Shape. Этот класс должен предоставлять следующие методы: getArea вычисление площади getFrameRect получение ограничивающего прямоугольника для фигуры (см. типы из предыдуще- го пункта), стороны ограничивающего прямоугольника всегда параллельны осям move перемещение центра фигуры, 2 варианта: в конкретную точку и в виде смещений по осям абсцисс и ординат scale изотропное масштабирование фигуры относительно её центра с указанным коэффициентом
3. Реализовать класс Rectangle в файлах rectangle.hpp и rectangle.cpp, соответственно.
4. Дополнительно реализовать ещё 2 (две) геометрические фигуры, указанные преподавателем.
5. Продемонстрировать правильную работу классов программой, демонстрирующей полиморфное при- менение классов. Использование контейнеров стандартной библиотеки в настоящей работе недопу- стимо. Управление памятью должно осуществляться с помощью умных указателей, предоставляе- мых стандартной библиотекой (см. std::unique_ptr, std::shared_ptr и std::weak_ptr). • Программа должна быть реализована в виде 1-го исполняемого файла, не обрабатывающего параметры командной строки. • Программа должна обрабатывать поток стандартного ввода, содержащий описание геометри- ческих фигур. Каждая строка гарантировано содержит описание не более одной фигуры. Эле- менты в описании разделены ровно одним пробелом и гарантировано являются вещественными числами (за исключением названия фигур) Описание завершается командой масштабирования фигур. Пример описания: CIRCLE 1.15 2.5 10.1 RECTANGLE -5.9 -3.4 3.0 4.0 SQUARE -1.55 -1.55 10.5 TRIANGLE 1.3 2.2 3.2 5.0 10.0 -5.5 POLYGON 1.3 2.2 3.2 5.0 10.0 -5.5 SCALE -15.0 -7.5 1.5 • Каждая фигура описывается своим набором параметров. Отсутствие самопересечений, выпук- лость фигур и корректное количество, и только количество, параметров гарантируется, если не сказано иного: – Прямоугольник описывается парой координат своих углов: левым нижним и правым верх- ним. Считайте, что стороны прямоугольника параллельны осям координат. Центром фигу- ры считайте точку пересечения диагоналей RECTANGLE 1.0 1.0 3.0 4.0 RECTANGLE 0.0 0.0 -2.0 -10.0 – Круг описывается координатами центра и радиусом. Радиус должен быть положительным. Центром фигуры считайте центр окружности CIRCLE 2.0 3.0 15.0 – Кольцо описывается координатами цетра и парой радиусов: внешней и внутренней окруж- ности соответственно. Центром фигуры считайте центры окружностей RING 2.0 3.0 20.0 15.0 – Эллипс описывается координатами центра и двумя значениями радиусов: по вертикальной оси и по горизонатльной оси. Считайте, что оси эллипса параллельны осям координатам. Центром эллипса считайте точку пересечения осей эллипса ELLIPSE 0.0 0.0 10.0 20.0 – Квадрат описывается координатами своего левого нижнего угла и длиной стороны. Считай- те, что стороны квадрата параллельны осям координат. Центром фигуры считайте точку пересечения диагоналей SQUARE 6.0 7.0 1.0 – Треугольник описывается координатами трёх своих вершин. Условия треугольника должны быть соблюдены. Центром фигуры считать центр тяжести фигуры TRIANGLE 0.0 0.0 1.0 1.0 0.0 1.0 – Параллелограмм описывается тремя вершинами, составляющими треугольник, одна из сто- рон которого является диагональю параллелограмма, а две дургие — сторонами параллело- грамма. Стороны параллелограмма формируются первой и последней парой вершин. При этом одна из сторон должна быть параллельна оси абсцисс. Центром фигуры считать точку пересечения диагоналей PARALLELOGRAM 0.0 1.0 10.0 1.0 5.0 0.0 PARALLELOGRAM 0.0 1.0 10.0 1.0 5.0 5.0 – Ромб описывается тремя вершинами, составляющими треугольник, две стороны которого являются частью диагоналей ромба. Считайте, что диагонали ромба должны быть парал- лельны осям координат. Центром фигуры считайте точку пересечения диагоналей DIAMOND 0.0 5.0 10.0 0.0 0.0 0.0 – Правильный многоугольник задаётся тремя вершинами. Вершины должны соответствовать условиям треугольника и формировать прямоугольный треугольник, гипотенуза которого равна радиусу описанной у многоугольника окружности, а один из катетов - радиусу впи- санной в многоугольник окружности. Считайте центром фигуры первую из трёх вершин. REGULAR 0.0 0.0 0.0 1.0 1.0 1.0 – Полигон описывается координатам своих вершин. Центром фигуры считайте центр тяжести фигуры. При этом количество точек в описании должно быть достаточным для формиро- вания полигона. Кроме того, никакие точки не должны совпадать POLYGON 0.0 0.0 1.0 0.0 1.0 1.0 0.0 1.0 – Невыпуклый четырёхугольник описывается четыремя вершинами. Первые три должны удо- влетворять свойствам треугольника. Четвёртая вершина должна лежать внутри треуголь- ника, формируемого первыми тремя вершинами. Вогнутость четырёхугольника формиру- ется последними тремя вершинами в описании. Центром фигуры считайте точку, форми- рующую вогнутость CONCAVE 0.0 5.0 0.0 0.0 10.0 -1.0 1.0 1.0 – Четырёхугольник с самопересечениями задаётся координатами двух своих пересекающихся сторон. Центром фигуры считайте точку пересечения этих сторон. Кроме того, считайте, что первая и последняя вершины в описании формируют сторону фигуры COMPLEXQUAD 0.0 0.0 10.0 10.0 2.0 0.0 3.0 0.0 • Команда масштабирования содержит параметры изотропного масштабирования: по порядку координаты центра, относительно которого необходимо произвести масштабирование, и коэф- фициент масштабирования. Коэффициент должен быть положительным • После выполнения масштабирования в соответствии с указанными параметрами, программа должна вывести в стандартный вывод на отдельных строках: – суммарную площадь и координаты ограничивающих прямоугольников обрабатываемых фигур в порядке их описания до масштабирования. – суммарную площадь и координаты ограничивающих прямоугольников обрабатываемых фигур в порядке их описания после масштабирования Элементы должны быть разделены ровно одним пробелом, содержать один и только один знак после запятой (округление проводить в соотвествии с правилами математики) и описаны в следующем порядке. • Пустые строки в описании фигур игнорируются • Описания фигур не реализованных в программе должны игнорироваться, как если бы строка была пустой • Если описание фигуры содержит ошибку, но её описание неверно, программа игнорирует её, но после масштабирования в стандартной поток ошибок должно выводиться сообщение о наличии ошибок в описании поддерживаемых фигур (конкретные фигуры указывать не требуется) • Программа должна завершаться с сообщением об ошибке и ненулевым кодом возврата, если ввод завершился EOF (на Linux: Ctrl + D | на Windows: Ctrl + Z затем Enter), но команда масштабирования не описана или имеет некорректный коэффициент масштабирования • Описание каждого ограничивающего прямоугольника в выводе должно содержать по порядку координаты левого нижнего угла и координаты правого верхнего угла. Например для входных данных: RECTANGLE -1.0 -1.0 1.0 1.0 SQUARE -2.0 -2.0 4.0 SQUARE -10.0 -5.0 -5.0 SCALE 0.0 0.0 2.0 – Если фигура SQUARE не поддерживается программой, то в стандартный поток вывода должно быть выведено: 4.0 -1.0 -1.0 1.0 1.0 16.0 -2.0 -2.0 2.0 2.0 – Если фигура SQUARE поддерживается программой, то в стандартный поток вывода долж- но быть выведено: 20.0 -1.0 -1.0 1.0 1.0 -2.0 -2.0 2.0 2.0 80.0 -2.0 -2.0 2.0 2.0 -4.0 -4.0 4.0 4.0 А в стандартный поток ошибок необходимо вывести сообщение о наличии некорректной фигуры. При этом код возврата должен быть нулевым.

Алгоритмы I (T2)

Написать программу, которая выполняет следующие действия:

1. Заполняет std::vector< DataStruct > структурами DataStruct, прочитанными со стандартного ввода. Чтение необходимо осуществлять с помощью итераторов и алгоритмов STL (std::copy, ите- раторы потока и перегрузки оператора побитового сдвига для чтения из потока)
2. Сортирует считанные данные следующим образом: (a) По возрастанию key1 (b) По возрастанию key2, если key1 одинаковые (c) По возрастанию длины строки key3, если прочие поля равны
3. Выводит результаты сортировки на стандартный вывод. Каждая строка должна содержать ровно один объект. Формат каждого выводимого объекта аналогичен формату ввода. Вывод необходимо осуществлять с помощью итераторов и алгоритмов STL (std::copy, итераторов потока и перегрузки оператора побитового сдвига для вывода в поток) Входные данные могут содержать строки с неподдерживаемым форматом данных. Такие строки должны игнорироваться. Формат данных, который необходимо обрабатывать зависит в том числе от определения DataStruct
4. Тип DataStruct определён следующим образом: struct DataStruct { /* TYPE1 / key1; / TYPE2 */ key2; std::string key3; }; Конкретные типы полей key1 и key2, а также соответствующий полям формат должны быть указаны преподавателем
5. Каждая запись ограничена парой скобок. Внутри этих скобок в качестве разделителей используются пробельные символы и символы :. Например: (:key1 10ull:key2 ’c’:key3 "Data":) Порядок описания полей в структуре не определён. Например следующие структуры данных счи- таются идентичными: (:key1 10ull:key2 ’c’:key3 "Data":) (:key2 ’c’:key1 10ull:key3 "Data":) (:key3 "Data":key2 ’c’:key1 10ull:) Имя поля и соответствующее значение гарантировано разделены ровно одним пробелом. Символы двоеточия гарантировано примыкают к прочим элементам записи. При выводе в поток поля выво- дятся в том порядке, в котором они заданы в структуре (запоминать исходный порядок не требуется)
6. Поля могут иметь следующий тип и соответствующий формат: • [DBL LIT] Вещественное поле с двойной точностью (double) в формате литерала: :keyX 50.0d: :keyX 50.0D: • [DBL SCI] Вещественное поле с двойной точностью (double) в научном формате: :keyX 5.45e-2: :keyX 5.45E-2: Число должно выводиться в стандартном виде, т.е мантисса должна быть меньше 10 и не меньше 1 • [SLL LIT] Знаковое максимально доступной ёмкости (long long) в формате литерала: :keyX 89ll: :keyX -89LL: • [ULL LIT] Беззнаковое максимально доступной ёмкости (unsigned long long) в формате ли- терала: :keyX 89ull: :keyX 89ULL: • [ULL OCT] Беззнаковое максимально доступной ёмкости (unsigned long long) в формате воь- смиричного литерала: :keyX 076: :keyX 01001: • [ULL BIN] Беззнаковое максимально доступной ёмкости (unsigned long long) в формате дво- ичного литерала: :keyX 0b1000101: :keyX 0B001001: • [ULL HEX] Беззнаковое максимально доступной ёмкости (unsigned long long) в формате шест- надцатиричного литерала: :keyX 0xFFFA: :keyX 0X0100f: Цифры шестандцатиричного числа выводятся в верхнем регистре • [CHR LIT] Символ (char) в формате символьного литерала: :keyX ’c’: :keyX ’A’: • [CMP LSP] Комплексное число (std::complex< double >) в следующем виде: :keyX #c(1.0 -1.0): :keyX #c(-1.0 1.0): Гарантируется, что вещественная и мнимая часть разделены ровно одним пробелом. При срав- нении с другими полями должен быть использован модуль комплексного числа • [RAT LSP] Рациональное число (std::pair< long long, unsigned long long >) в следующем виде: :keyX (:N -2:D 3:): :keyX (:N 3:D 2:): • Если в качестве варианта задания выданы [CMP LSP] и [RAT LSP], то DataStruct должна быть определена следующем образом: struct DataStruct { std::complex< double > key1; std::pair< long long, unsigned long long > key2; std::string key3; }; При этом обрабатываемые записи имеют следующий вид: (:key1 #c(1.0 -1.0):key2 (:N -1:D 5:):key3 "data":) (:key2 (:N -1:D 5:):key3 "with : inside":key1 #c(2.0 -3.0):) Все вещественные выводятся с точностью до десятичных долей. Символы, характерные для лите- ралов выводятся в нижнем регистре (1.1e+1, 1ull, 0b01, 0x0F).

Алгоритмы II (T3)

С помощью стандартных алгоритмов (см. ) и функторов (см. ) реализуйте следующую программу:

1. Считайте в стандартный контейнер геометрические фигуры из файла, имя которого будет переданно в программу через параметры командной строки. Этот пункт должен быть выполнен отдельным действием, нельзя совмещать дальнейшие действия с чтением данных • Геометрические фигуры должны быть заданы следующей структурой: struct Point { int x, y; }; struct Polygon { std::vector< Point > points; }; • В файле с описаниями фигур на каждой строке содержится не более одного описания фигу- ры, содержащего по порядку: количество вершин в фигуре, последовательность из указанного количества вершин. Каждая вершина задаётся парой координат. Например, файл с описанием может иметь вид: 3 (1;1) (1;3) (3;3) 4 (0;0) (0;1) (1;1) (1;0) 5 (0;0) (0;1) (1;2) (2;1) (2;0) 3 (0;0) (-2;0) (0;-2) Элементы описания разделены друг от друга ровно одним пробелом. • Не соответствующие формату описания фигур должны игнорироваться • Если описание фигуры соответствует формату, то гарантируется: отсуствие самопересечений и что любая тройка вершин фигуры формирует невырожденный треугольник
2. Программа должна обрабатывать пользовательский ввод и поддерживать ряд команд. Веществен- ные числа в результатах выводятся с точностью до одного знака после запятой. Далее приведено описание команд с примерами, в которых подразумевается, что были считаны фигуры, описанные выше: • [AREA <EVEN|ODD>] Расчёт суммы площади фигур с нечётным количеством вершин и с чётным (в зависимости от переданного параметра) AREA ODD 1.0 AREA EVEN 7.0 • [AREA ] Расчёт среднего площадей фигур AREA MEAN 2.0 • [AREA ] Расчёт суммы площади фигур с заданным количеством вершин AREA 3 4.0 • [MAX <AREA|VERTEXES>] Расчёт максимального значения площади или количества вершин (в зависимости от переданного параметра) MAX AREA 3.0 MAX VERTEXES 5 • [MIN <AREA|VERTEXES>] Расчёт минимального значения площади или количества вершин (в зависимости от переданного параметра) MIN AREA 1.0 MIN VERTEXES 3 • [COUNT <EVEN|ODD|num-of-Vertexes>] Подсчёт количества фигур с нечётным, чётным и кон- кретным количеством вершин (в зависимости от переданного параметра) COUNT EVEN 3 COUNT ODD 1 COUNT 3 2
3. Кроме того, поддержите реализацию ещё нескольких команд, указанных преподавателем (не менее 2-х из перечисленных): • PERMS Подсчёт количества фигур, которые являются перестановкой координат ука- занной в качестве параметра. Например, для фигур 3 (3;3) (1;1) (1;3) 3 (0;1) (1;1) (0;0) 3 (3;1) (1;1) (3;3) Ожидается следующий результат: PERMS 3 (1;1) (1;3) (3;3) 2 • MAXSEQ Подсчёт максимального количества идущих подряд фигур идентичной ука- занной в параметрах. Например, для фигур 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) Ожидается следующий результат: PERMS 3 (3;3) (1;1) (1;3) 3 PERMS 4 (0;0) (1;0) (1;1) (0;1) 2 PERMS 4 (1;0) (1;1) (0;1) (0;0) 0 • RMECHO Удаление идущих подряд дубликатов фигур идентичных указанной в пара- метре и вывод количества удалённых фигур. Например, для фигур 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) Ожидается следующий результат: RMECHO 3 (3;3) (1;1) (1;3) 2 При этом, оставшиеся фигуры идентичны следующему набору 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) • ECHO Дублирует всякое вхождение указанной в параметре фигуры. Дубликаты до- бавляются сразу после идентичного элемента. Команда должна выводить количество добавлен- ных фигур. Например, для фигур 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) Ожидается следующий результат: ECHO 3 (3;3) (1;1) (1;3) 2 При этом, фигуры в коллекции идентичны следующему набору: 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) 3 (3;3) (1;1) (1;3) • LESSAREA Команда подсчитывает количество фигур с площадью меньшей, чем пло- щадь фигуры, переданной в параметре. Например, для фигур 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) 3 (3;3) (1;1) (1;3) 4 (0;0) (1;0) (1;1) (0;1) Ожидается следующий результат: LESSAREA 3 (0;0) (2;2) (2;0) 2 • INFRAME Команда проверяет лежит ли указанная фигура целиком внутри прямо- угольника, ограничивающего сохранённый в коллекции набор фигур: если да - выводится со- общение , иначе - . Например, для фигур 4 (0;0) (1;0) (1;1) (0;1) 4 (5;5) (6;5) (6;6) (5;6) Ожидается следующий результат: INFRAME 3 (0;0) (2;2) (2;0)

INFRAME 3 (-1;-1) (1;1) (1;0) • INTERSECTIONS Команда подсчитывает количество фигур, с которыми пересекается фигура, указанная в параметрах. Например, для фигур 4 (0;0) (1;0) (1;1) (0;1) 4 (1;1) (2;1) (2;2) (1;2) Ожидается следующий результат: INTERSECTIONS 4 (0;0) (2;0) (2;2) (0;2) 2 INTERSECTIONS 4 (1;1) (3;1) (3;3) (1;3) 2 INTERSECTIONS 4 (2;2) (4;2) (4;4) (2;4) 1 • SAME Команда подсчитывает количество фигур, совместимых наложением (без по- воротов) с указанной в параметрах. Например, для фигур 4 (0;0) (1;0) (1;1) (0;1) 3 (0;0) (1;1) (0;1) 4 (1;1) (2;1) (2;2) (1;2) Ожидается следующий результат: SAME 4 (-1;-1) (-1;0) (0;0) (0;-1) 2 SAME 3 (10;10) (11;11) (10;11) 1 SAME 3 (10;10) (10;11) (11;10) 0 • RECTS Команда подсчитывает количество прямоугольников в коллекции фигур. Например, для фигур 4 (0;0) (1;0) (1;1) (0;1) 3 (0;0) (1;1) (0;1) 4 (1;1) (0;2) (1;3) (2;2) 4 (-2;1) (2;3) (3;1) (-1;-1) Ожидается следующий результат: RECTS 3 • RIGHTSHAPES Команда подсчитывает количество фигур, содержащих прямые углы. Например, для фигур 4 (0;0) (1;0) (1;1) (0;1) 5 (-1;-1) (-2;1) (3;0) (3;-5) (0;-6) 3 (0;0) (1;1) (0;1) 4 (1;1) (0;2) (1;3) (2;2) Ожидается следующий результат: RIGHTSHAPES 3 4. Если команда по каким-то причинам некорректна, то должно быть выведено сообщени 5. Признаком конца ввода команд является EOF (на Linux: Ctrl + D | на Windows Ctrl +Z Enter) затем 6. Работа должа быть выполнена в виде 1-го исполняемого файла, принимающего параметры следую- щим образом $ ./lab filename filename представляет собой обязательный параметр. Если он не задан, программа должна завер- шаться с ненулевым кодом возврата и сообщением об ошибке Совет-1 Не используйте алгоритм std::for_each и циклы. Постарайтесь подобрать более специальный ал- горитм Совет-2 Постарайтесь использовать именно стандартные функторы и композиции из них (см. std::bind) Подумайте, какие типы можно реализовать дополнительно и какие операторы для них можно было бы перегрузить

Алгоритмы для работы с графами (FT)

Общая постановка задачи:

1. Реализовать представление графа в виде матрицы смежности или в виде списков смежных вершин (зависит от реализуемых алгоритмов).
2. Минимальный набор операций для структуры — графа должен включать следующие операции: • формирование пустого графа; • проверка наличия узлов в графе; • проверка наличия заданного узла в графе; • проверка наличия дуги между заданными узлами графа; • включение нового узла в граф; • исключение узла из графа. Дополнительно включаются все операции, необходимые для работы с графом при решении задачи., например, включение дуги с заданным весом между двумя заданными узлами (если дуга существует, то устанавливается нужный вес), исключение дуги между заданными узлами с выдачей веса дуги и т.п.
3. Предусмотреть обработку и инициализацию исключительных ситуаций, связанных, например, с проверкой значения полей перед инициализацией и присваиванием.
4. Программа должна быть написана в соответствии со стилем программирования: C++ Programming Style Guidelines (http://geosoft.no/development/cppstyle.html).
5. Тесты должны учитывать как допустимые, так и не допустимые последовательности входных данных. Вариант 2.2. Обход в ширину неориентированного графа.
6. Реализовать алгоритм обхода в ширину
7. Реализовать алгоритм поиска кратчайших путей для заданной вершины
8. Реализовать алгоритм вычисления диаметра дерева поиска в ширину.

2.1 Описание алгоритма решения и используемых структур данных Граф - массив односвязных списков индексов этого массива, массив логических значений существования вершин. Формирование пустого графа - заполнение массива пустыми списками, инициализация существования вершин ложью. Проверка наличия узлов в графе - обход массива существования. Проверка наличия заданного узла в графе - индексация массива существования. Проверка наличия дуги между заданными узлами графа - обход списка смежных вершин. Включение нового узла в граф - обход массива существования, обход списка смежных вершин и добавление подходящих элементов в пару списков, возведение существования. Исключение узла из графа - обход списков смежных вершин смежных вершин с удалением всех ребер к данной вершине и удаление списка смежных вершин данной вершины, сброс существования. Обход в ширину - обход смежных непройденных вершин текущей вершины с применением функции обратного вызова к паре текущая вершина - смежная вершина, возведением пройденности смежной вершины, помещением смежной вершины в очередь при обходе графа по этой очереди. Поиск кратчайших путей для заданной вершины - обход в ширину с применением функции обратного вызова, устанавливающей расстояние от начальной вершины до смежной вершины на единицу большим расстояния до текущей вершины, вывод расстояний до всех вершин. Вычисление диаметра дерева поиска в ширину - нахождение вершины, находящейся на наибольшем расстоянии поиска кратчайших путей от начальной вершины и нахождение наибольшего расстояния поиска кратчайших путей от полученной вершины до остальных вершин.

Списки смежности сделаны через std::forward_list< std::size_t >. Очередь это std::queue< std::size_t >. Расстояния поиска кратчайших путей для заданной вершины хранятся в массиве целых неотрицательных чисел, заполненном нулями перед поиском. 2.2 Анализ алгоритма Обход в ширину состоит из цикла, выполняющегося для каждой вершины, находящейся в одной компоненте связности с начальной вершиной. В теле этого цикла происходит фиксированное количество операций k на вершину и обход списка смежных вершин с проверкой обойденности каждой смежной вершины, что тратит по 2 операции проверки на ребро. Пусть n - количество вершин в компоненте связности, m - количество ребер компоненты. Суммарно операций выполняется kn + 2m. Можно оценить kn + 2m < kn + km = k(n + m). Операций выполняется меньше чем k(n + m), где k не зависит от n и m. Значит обход в ширину выполняется за O(n + m). При поиске кратчайших путей вызывается обход в ширину, которому передается функция обратного вызова, выполняющаяся за фиксированное число операций. Значит поиск кратчайших путей выполняется за O(n + m). Вычисление диаметра дерева поиска в ширину использует два вызова поиска кратчайших путей, что не влияет на асимптотику. Вычисление диаметра дерева поиска в ширину выполняется за O(n + m). 2.3 Описание спецификации программы (детальные требования) На вход подаются команды:

1. create - создать граф один параметр - размер массива узлов создаваемого графа пересоздает граф с новым размером
2. has-vertices - проверка наличия узлов в графе без параметров выводит логическое значение
3. has-vertex - проверка наличия узла с заданным номером в графе один параметр - номер узла выводит логическое значение
4. has-edge - проверка наличия дуги между заданными узлами графа два параметра - номера узлов выводит логическое значение
5. add-vertex - включение нового узла в граф параметры - номера узлов, связанных с новым узлом выводит номер нового узла или сообщение об ошибке если в графе закончилось место
6. remove-vertex - исключение узла из графа один параметр - номер узла выводит сообщение об ошибке если в графе нет заданного узла
7. breadth-first-search - обход в ширину один параметр - номер стартового узла выводит последовательность пройденных ребер (пар вершин)
8. get-path - поиск кратчайших путей для заданной вершины один параметр - номер заданной вершины выводит все номера вершин с длиной пути к ним из заданной если она есть
9. get-diameter - вычисление диаметра дерева поиска в ширину один параметр - номер стартовой вершины выводит диаметр если в графе есть заданный узел 2.4 Описание программы (структура программы, форматы входных и выходных данных) Программа выполняется в цикле считывания команд из потока стандартного ввода. При передаче параметром файла, команды считываются из него. При наступлении ситуации конца файла программа завершается. В начале создается граф размером 1. Номера узлов подаются как десятичные числа. Команды либо выводят понятные сообщения о результатах работы в поток стандартного вывода, либо ничего не выводят.

стиль кода и требования (coding guidelines)

1 Оформление исходных текстов

1. Исходные тексты программы должны содержать не более одного выражения на одной строке.
2. Недопустимо писать функции в одну строку; сигнатура функции всегда должна идти на отдельной строке или нескольких, если сигнатура имеет большую длину.
3. Строки должны помещаться на экране в веб-интерфейсе GitLab. Как правило: длина одной строки не должна превышать 120 символов в большинстве случаев и 140 символов всегда.
4. Строки не должны заканчиваться пробелами и/или символами табуляции.
5. Файл должен заканчиваться символом конца строки.
6. Все имена должны быть составлены из правильных английских слов или очевидных для читающего сокращений или аббревиатур.
7. Переменные определяются максимально близко к месту использования. Они должны иметь мини- мально возможную область видимости.
8. Все переменные должны быть инициализированы в точке определения.
9. Все неизменяющиеся переменные должны быть отмечены квалификатором const.
10. Аргументы функции, переданные по ссылке или по указателю и не изменяющиеся внутри функ- ции, должны быть отмечены квалификатором const. Параметры, передаваемые по значению мо- гут иметь квалификатор const в определениях функций, но он должен отсутствовать в объявлении функции.
11. Единицей отступа являются 2 пробела.
12. Отступы должны отражать логическую структуру программы: (a) операторы, выполняемые внутри циклов, должны иметь отступ на 1 больший, чем заголовок цикла; (b) операторы, выполняемые внутри if и else, должны иметь отступ больший, чем строки с if и else; (c) Метки операторов case внутри switch должны быть выравнены на тот же отступ, что switch. (d) Операторы внутри switch должны иметь на 1 больший отступ, чем оператор switch.
13. Все операторы, входящие в тела циклов и условий, заключаются в фигурные скобки, даже если это один оператор.
14. Фигурные скобки должны быть расставлены единообразно. Допускаются 2 варианта: (a) Открывающая фигурная скобка переносится на следующую строку и имеет тот же отступ, что и предыдущая строка, закрывающая скобка находится на отдельной строке, и ее отступ совпадает с открывающей. Операторы внутри скобок имеют дополнительный отступ. Например: if (condition) { c = a + b; } else { c = a - b; } Ключевое слово else должно находится на отдельной строке. (b) Открывающая фигурная скобка завершает строку с оператором и отделяется слева пробелом, закрывающая скобка находится на отдельной строке, и ее отступ совпадает с отступом строки, содержащей открывающую скобку (так называемые «египетские скобки»). Операторы внутри скобок имеют дополнительный отступ. Например: 2if (condition) { c = a + b; } else { c = a - b; } Ключевое слово else должно находиться на строке вместе с закрывающей скобкой. Открывающая фигурная скобка в реализации функции всегда переносится на другую строку: void foo() { ... } Способ расстановки фигурных скобок должен быть единообразен во всех работах.
15. Ключевые слова if и else могут быть объединены на одной строке для уменьшения отступов: if (condition1) { c = a + b; } else if (condition2) { c = a - b; }
16. Ключевые слова if, for, while, switch, catch всегда отделяются пробелом от последующей откры- вающей скобки. В то же время список параметров при объявлении, определении и вызове функций никогда не отделяется пробелами.
17. Определяя пространство имен, расстановка фигурных скобок должна соответствовать аналогично- му правилу для условных операторов и циклов: открывающая скобка - либо на строке с имененем пространства имен, либо на отдельной строке сразу после, закрывающая скобка - всегда на отдель- ной строке. Определения и объявления внутри пространства имен имеют дополнительный отступ. Например: namespace component { void foo() { ... if (condition) { c = a - b; } ... } }
18. Отдельные символы операторов в выражениях выделяются пробелами с 2-х сторон, кроме операто- ров: (a) индексации — квадратные скобки не отделяются пробелами от предшествующей переменной, а содержимое скобок не отделяется от них. a[1][index] (b) оператор последовательного выполнения следует грамматическим правилам английского язы- ка — перед запятой пробел не ставится, а после — ставится, перенос строки выполняется строго после запятой; (c) запятая в списке параметров также следуют грамматическим правилам английского языка; (d) операторы доступа к полям составных объектов (. и ->), а также к пространству имен ::, не выделяются пробелами.
19. Двоеточие в метках case и переходах является частью синтаксической конструкции и не отделяется пробелом слева. Сразу за ним идет новая строка.
20. Двоеточие и точка с запятой в цикле for не должна отделяться пробелом слева, но после них обяза- тельно идет пробел или перенос строки. В случае большого условия лучше определить λ-функцию или статическую функцию, чем переносить элементы заголовка цикла, так как перенос сильно ухуд- шает читаемость.
21. Имена переменных и параметров функций должны начинаться со строчной буквы и следовать од- ному из правил: (a) все слова пишутся строчными буквами и разделяются символами подчеркивания; (b) все слова, кроме первого, начинаются с заглавных букв и ничем не разделяются (аббревиатуры более 3 букв имеет смысл писать с заглавной строчными). Оформление должно быть однообразным во всех работах.
22. Расстановка пробельных символов в деклараторах должна быть единообразна и следовать одному из правил (a) Символы обозначение ссылок и указателей отделяется пробелами слева void foo(int &&rvalue) { const int &lvalue = rvalue; const int ptrvalue = &lvalue; const int ptrptrvalue = &ptrvalue; ... } (b) Символы обозначение ссылок и указателей отделяется пробелами справа void foo(int&& rvalue) { const int& lvalue = rvalue; const int ptrvalue = &lvalue; const int ptrptrvalue = &ptrvalue; ... } (c) Символы обозначение ссылок и указателей отделяется пробелами и слева, и справа Идущие подряд «звездочки» пробелами не разделяются
23. Имена классов должны начинаться с большой буквы. Если имя состоит из нескольких слов, они идут подряд без символов подчеркивания, каждое слово начинается с большой буквы (CapsCase). Например, Queue или RoundedRectangle. Исключением из правил могут являться функторы, име- на которых могут быть в нижнем регистре. В этом случае отдельные слова в имени разделяются подчеркиваниями.
24. Имена классов должны представлять собой имена существительные с определениями и дополнени- ями. Исключения: имена функторов должны иметь в основе глагол, так как представляют собой действие.
25. Псевдонимы типов и шаблонов должны быть определены с использованием ключевого слова using вместо ключевого слова typedef
26. Структуры в терминах C (без конструкторов и деструкторов, а также без методов) допустимо на- зывать в нижнем регистре и разделять слова подчеркиваниями. В этом случае имя должно иметь суффикс «_t».
27. Секции внутри класса должны быть упорядочены в порядке убывания интереса к ним со стороны читающего код: первой должна идти секция public, так как это интерфейс класса для клиентов; затем секция protected, поскольку она представляет собой интерфейс для наследников; завершает класс секция private, так как эта информация интересна только разработчику класса.
28. Внутри каждой секции информация должна быть упорядочена следующим образом: (a) типы; (b) поля; (c) конструктор по умолчанию; (d) конструкторы копирования и перемещения; (e) все остальные конструкторы; (f) деструктор; (g) перегруженные операторы; (h) методы.
29. Имена функций и методов должны начинаться со строчной буквы, дополнительные слова должны начинаться с заглавной буквы и идти вместе с предыдущим (camelCase), например, draw() или getArea().
30. Имена функций должны начинаться с глаголов, так как они представляют собой действие.
31. Имена параметров шаблонов должны начинаться с заглавной буквы, так как являются либо типами, либо специфическими константами.
32. При инстанцировании и определении шаблонов необходимо отделять пробельным символом имена параметров от угловых скобок
33. Все методы, не меняющие объект логически, должны быть отмечены квалификатором const.
34. Имена полей класса должны следовать правилам для переменных и иметь отличительный признак поля, в качестве которого следует использовать либо префикс «m_», либо завершающий символ подчеркивания (предпочтительнее). Стратегия именования должна быть единообразной во всех ра- ботах
35. Недопустимо создавать имена, начинающиеся с подчеркиваний, в том числе имена макроопределе- ний. При этом имена макроопределений не должны завершаться символом подчеркивания
36. Имена макроопределений должны быть в верхнем регистре. Если макроопределение состоит из нескольких слов, они должны быть разделены символом нижнего подчеркивания.
37. Написание длинных операторов крайне нежелательно. Перенос длинных операторов на другую стро- ку, если таковы имеются, должен выполняться следующим образом: (a) в начале следующей строки должен находиться перенесенный оператор (за исключением запя- той); (b) отступ должен быть больше на 2 единицы отступа; (c) в случае переноса внутри сложного выражения с круглыми скобками, отступ должен отражать вложенность скобок, каждый уровень вложения добавляет 1 отступ на следующей строке. Пример переноса (ширина строки не соблюдена): if (condition) { a = a + b

• (c

• d / e); } Исключение: в выражениях ввода и вывода с потоками допускается выравнивать операторы на перенесенных строках друг под другом, если это не создает слишком большого отступа: std::cout << a << b << c << d;

538. Список инициализации в конструкторе должен инициализировать не более одной переменной или базового класса на строке. Двоеточие перед списком инициализации должно оставаться на строке со списком параметров, недопустимо переносить его на следующую строку. Оно не отделяется слева пробелом. Аналогично оформляются запятые, разделяющие элементы списка инициализации: запя- тая остается на строке с предыдущим элементом. Отступ в списке инициализации увеличивается на 1 по сравнению со строкой, где начинается определение конструктора (строки перенесены для демонстрации): SampleClass::SampleClass(int a, int b): a_(a), b_(b) {}
539. В конструкции наследования двоеточие не отделяется пробелом слева от имени определяемого клас- са
540. В списках инициализации массивов допускается применение «висящей» запятой после последнего элемента, так как это уменьшает «визуальный шум» в изменениях при увеличении списка инициа- лизации.
541. Внутри выражений круглые скобки должны применяться для исключения неоднозначностей. За исключением очевидных из школьной арифметики приоритетов, все выражения оформляются так, чтобы при чтении не требовалось знать таблицу приоритетов операторов.
542. Не допускается применение «магических значений», вместо этого должны использоваться констан- ты. Есть исключения: 0 и одноразово использованные строковые литералы.
543. Не допускается использование глобального пространства имен, если нет сущесвтенных причин для этого
544. Не следует опускать пространство имён std::. Это помогает читающему понять, что используемая сущность относится к стандартной библиотеке
545. Не допускается использование конструкций using namespace на верхнем уровне в заголовочных файлах. Если конструкция используется в файлах с реализациями, предпочтительно использовать конструкцию внутри определений функций, методов и шаблонов функций (в т.ч. методов шаблон- ного класса)
546. Заголовочные файлы должны содержать header guards независимо от наличия поддержки какого- либо другого механизма предотвращения повторного включения, так как все эти механизмы нестан- дартны и непереносимы.
547. Порядок включения заголовочных файлов важен: (a) внутри файла реализации первым включается соответствующий ему заголовок; (b) стандартные заголовки; (c) заголовки использованных библиотек; (d) свои заголовки.
548. Зависимости от заголовков должны быть минимизированы. Не допускается включение заголовков с реализациями, если достаточно объявлений
549. В файлах реализации все функции должны иметь полные имена, в которых пространства имен и имена классов отделены от имени функции при помощи ::. Использование псевдонимов простран- ства имен в этом случае недопустимо. Например, для функции в пространстве имен lab::detail с именем foo() реализация должна выглядеть так: void lab::detail::foo() { ... } 6Реализация функции в точке объявления допустима только для статических функций внутри еди- ницы трансляции, шаблонных функций, методов шаблонных классов.
550. Псевдонимы пространств имен должны иметь не менее 3-х символов.
551. Форматирование λ-функций должно соответствовать оформлению обычных функций, с учетом того, что список захвата замещает название функции. Недопустимо писать их в одну строку. [](const Object & obj) -> std::string { if (obj.getName().empty()) { return ""; } else { return obj.getName(); } }
552. В механизме исключений должны использоваться только объекты-исключения. Кроме того, созда- ние собственных типов исключений должно быть обоснованным
553. Пустые строки должны использоваться разумно. Допускается использовать не более 1 пустой строки для: • разделения логических групп заголовков; • отделения header guards; • разделения секций с различным доступом в классах (может быть вставлена перед ключевым словом, если оно не первое в определении класса; • разделения различных частей определения класса; • отделения определений переменных от остального кода; • разделения определений классов, функций и т.п.; • отделения логически связанных фрагментов кода от прочих фрагментов. Не следует отделять каждую переменную (или объявление функции и т.д.) пустой строкой, так как это излишне растягивает код. Для разделения классов и функций не допускается использование линеек из символов «минус» и «равно» (и прочих) для разделения блоков кода.
554. В программе не должно быть закомментированного кода. Весь неиспользуемый код должен быть удален. В случае необходимости, такой код может быть восстановлен из системы контроля версий. Общий признак хорошего кода: его можно прочитать по телефону и он будет понятен на той стороне. Наиболее простым способом следовать этим правилам будет настроить редактор так, чтобы он выполнял такое форматирование автоматически.

2 Требования к дизайну Общий дизайн выполненной работы должен удовлетворять следующим требованиям, в порядке убы- вания приоритета:

1. Использовать средства автоматического управления ресурсами. Исключение: работы по алгоритмам и структурам данных, так как соответствующий материал еще не прочитан.
2. Удовлетворять как минимум базовой гарантии безопасности исключений, предпочтительно удовле- творять строгой гарантии.
3. Каждый написанный класс должен перегружать все операторы, имеющие смысл для него. Напри- мер, класс матрицы должен перегружать операторы сравнения на равенство и неравенство, сложе- ния, вычитания и умножения. Отношение матриц (больше или меньше) для матриц не могут быть однозначно определены и, соответственно, не могут определяться в виде перегруженных операторов.
4. Корректно обрабатывать ошибки при взаимодействии с внешним миром, если не сказано иного: ошибки ввода-вывода, некорректный пользовательский ввод и так далее.
5. Программы не должны содержать лишних сущностей. Например, создавать классы только для одно- го метода недопустимо. Дизайн должен быть минималистичным настолько, насколько это возможно. Также недопустимо создавать методы, идентичные создаваемым компилятором. Например, написа- ние тривиального (пустого) открытого невиртуального деструктора недопустимо.
6. Все детали реализации должны быть скрыты от клиентского кода. Если это шаблон, который невоз- можно скрыть, он должен быть помещен во вложенное пространство имен detail.
7. За исключением самых простых, работы не должны выполняться в рамках одной единицы трансля- ции (обычное исполнение типа «слабоотформатированный поток сознания»). Должно присутство- вать разумное деление по файлам и правильно сформированные заголовочные файлы с минималь- ными зависимостями. 3 Общие требования к работам Работы выполняются в рамках стандарта C++ 14. Это означает, что код должен компилироваться и работать на любой платформе: Microsoft Windows® , Linux, macOS. Это автоматически означает, что все платформенно-зависимые вещи, обычно добавляемые в проект Microsoft Visual C++® , должны быть исключены. При компиляции программы должны отсутствовать предупреждения. Для GNU Compiler Collection (GCC)/Clang уровень предупреждений задается ключами -Wall -Wextra -Wold-style-cast. Часть предупре- ждений выключена, так как представляет собой несколько параноидальный подход (-Wno-missing-field- initializers). Программы должны представлять собой консольные приложения, обрабатывающие параметры ко- мандной строки и использующие стандартные каналы ввода-вывода. Тестирование заданий не преду- сматривает интерактивного взаимодействия, поэтому все входные данные должны читаться либо до заданного разделителя, либо до конца файла (End Of File (EOF, конец файла)). Ошибки ввода долж- ны немедленно обрабатываться и программа должна завершиться с ненулевым кодом возврата, так как исправлять ввод при неинтерактивном взаимодействии невозможно. Стандартный набор кодов возврата: 0 Успешное завершение программы. 1 Некорректные параметры. Обычно, в стандартный поток ошибок должно быть выведено описание при- чины ошибки. 2 Внутренняя ошибка программы. В стандартный поток ошибок также следует вывести описание ошибки. Работы выполняются с использованием системы контроля версий [GIT]. Для работы с системой требу- ется зарегистрироваться на сайте https://gitlab.com/. После регистрации на сервере необходимо прислать преподавателю свой логин для добавления в проект (конкретное название проекта зависит от преподава- теля). Каждый студент размещает свои работы в директории со своим именем на английском языке, строч- ными буквами и разделив фамилию и имя точкой, например, lastname.firstname. Каждая работа должна находиться в директории, имя которого представляет собой объединение заглавной латинской буквы, обо- значающей тематику курса («S» или «T») и номера работы, например, lastname.firstname/S1 для первой работы по курсу АиСД или lastname.firstname/T3 для третьей работы по курсу ТП. Каждый коммит должен: • содержать логически единое изменение; • обладать комментарием, из которого понятно что (в первой строке) и зачем (описание после пустой строки) было сделано (с обоснованием и деталями рекомендации можно ознакомится в статье https: //chris.beams.io/posts/git-commit); • успешно компилироваться и компоноваться; • проходить unit-тесты, если они есть; • крайне желательно проходить приемочные тесты. Категорически не допускается «брать штурмом» систему, создавая множество коммитов путем под- бора символов в исходных программах, которые смогут, наконец, скомпилироваться. Бесплатное исполь- зование инфраструктуры для тестирования в месяц ограничено, поэтому лишние попытки завершатся 8исчерпанием лимита. Так или иначе следует настроить собственный раннер, для прохождения Continuous Integration (CI) На проекте используется CI, соответственно, сборка и тестирование выполняются автоматически. Ком- миты, не прошедшие CI (с ошибкой или пропустившие CI) не принимаются. Результаты тестирования доступны в виде архива артефактов сборки и могут быть получены по ссылке «Download acceptance artifacts» Web UI, указанной либо в коммите, либо в CI pipeline. Категорически не допускается добавление в проект не относящихся к нему файлов, а также построен- ных программ, промежуточных файлов и файлов, создаваемых средами разработки. Построение программ выполняется при помощи стандартного Makefile, находящегося в корне репози- тория. Не допускается его изменение, а также любых файлов в корне проекта. Все исходные тексты в каждой работе идентифицируются по расширению «cpp». Обнаруженные ис- ходные тексты делятся на группы: Исходные тексты работы все файлы, имена которых не начинаются с test-. Исходные тексты тестов все файлы, исключая файл main.cpp. Как видно, файл main.cpp стоит особняком: его назначение — функция main() выполненной работы. Общие файлы для нескольких работ должны размещаться в поддиректории common. Они будут ав- томатически добавлены при сборке работы. Внутри common допустимо создавать поддиректории для организации файлов. Библиотека [BOOST] может находиться в нестандартном месте. Для того, чтобы указать его, в корне проекта необходимо разместить файл .boost_location, состоящий из одной строки с путем к корню биб- лиотеки. Путь не должен содержать пробельные символы. Сдача работы осуществляется путем отправки Pull или Merge Request. Сроком представления счита- ется дата отправки запроса. Все содержимое запроса принимается или отклоняется целиком. В случае успешного приема работы запрос объединяется с веткой «master». Все работы выполняются строго последовательно от первой до последней. Представлять, например, 6 работу можно только после успешной сдачи первых пяти. Так как каждая работа должна быть выполнена в отдельном Merge Request, не допускаются следующие ситуации: • более одной работы внутри Merge Request, но, если работа требует исправления уже сданных ра- бот, такие изменения должны быть выполнены в том же Merge Request, так как поддерживают корректность проекта; • несколько Merge Request для одной и той же работы, за исключением предыдущего пункта, так как каждый Merge Request обеспечивает отслеживание истории изменений и приема работы. Изменения в Merge Request должны быть выполнены относительно самого свежего коммита в ветке «master» основного проекта. Достигается это операциями «merge» и «rebase» (см. документацию по Git). Условия, гарантирующие отклонение работы: • неправильное именование директории с работой; • наличие конфликтов при слиянии; • наличие лишних файлов, создаваемых средой разработки и/или компилятором, не нужных для сборки и тестирования работы; • невыполнение настоящих требований к оформлению работ; • получение сообщений от [VALGRIND].