Все примеры, представленные в данном наборе доступны в виде отдельных .cpp-файлов в папке cpp2.
// vector_clamp.cpp
// Демонстрация работы с std::vector.
#include <vector>
#include <sstream>
#include <cassert>
#include <cmath> // nan, isnan в test_clamp
using namespace std;
/// "Загоняет" value в отрезок [min_bound, max_bound].
template <class Val>
inline Val clamp(Val value, Val min_bound, Val max_bound)
{
return value < min_bound ? min_bound
: max_bound < value ? max_bound
: value;
}
/// Проверим clamp.
int test_clamp()
{
if (clamp(1, 0, 10) != 1) return 1;
if (clamp(-1, 2, 5) != 2) return 2;
if (clamp(10, 2, 5) != 5) return 3;
if (!isnan(clamp(nan(""), 0., 1.))) return 4;
return 0;
}
/// Применяет clamp к вектору, создаёт новый вектор того же типа с результатами.
template <class Val>
vector<Val> clamped(const vector<Val> &values, Val min_bound, Val max_bound)
{
vector<Val> clv(values.size());
for (size_t i = 0, sz = values.size(); i < sz; ++i)
clv[i] = clamp(values[i], min_bound, max_bound);
return clv;
}
/// Читает вектор значений типа Val из потока ввода in.
/// Столько, сколько сможет.
template <class Val>
vector<Val> read_vector(istream &in)
{
vector<Val> values;
for (Val val; in >> val;)
values.push_back(val);
in.clear(ios::failbit);
values.shrink_to_fit();
return values;
}
/// Тест одновременно read_vector и clamped.
int test_clamped()
{
stringstream test;
test << "10 4 -5. 2 51 2222.022 4 1.2 25 7 8.5 -";
auto values = read_vector<float>(test);
if (clamped(values, 0.f, 100.f) != vector<float>
{ 10.f, 4.f, 0.f, 2.f, 51.f, 100.f, 4.f, 1.2f, 25.f, 7.f, 8.5f })
return 1;
if (clamped(values, 3.f, 8.f) != vector<float>
{ 8.f, 4.f, 3.f, 3.f, 8.f, 8.f, 4.f, 3.f, 8.f, 7.f, 8.f })
return 2;
return 0;
}
int main()
{
assert(test_clamp() == 0);
assert(test_clamped() == 0);
return EXIT_SUCCESS;
}
// amatrix2.hpp
// Матрицы на основе std::vector.
// Упрощённая реализация в виде набора внешних функций для плотных матриц
// на основе структуры данных "массив массивов" ("способ 1").
// Операции текстового ввода-вывода прилагаются.
#ifndef AMATRIX2_HPP_INCLUDED_XAM100
#define AMATRIX2_HPP_INCLUDED_XAM100
#include <vector>
#include <iterator>
#include <type_traits>
#include <istream>
#include <ostream>
///////////////////////////////////////////////////////////////////////////////
// Структура "массив массивов"
// на основе std::vector и шаблонов синонимов типа.
/// Шаблон синонима типа, представляющий строку матрицы как вектор элементов.
template <class T>
using Matrix_row = std::vector<T>;
/// Шаблон синонима типа, представляющий матрицу как вектор строк.
template <class T>
using Matrix = std::vector<Matrix_row<T>>;
///////////////////////////////////////////////////////////////////////////////
// Ввод-вывод вектора как последовательности значений,
// разделённых пробелами и завершаемых переводом строки.
// Функции readln ведут себя аналогично базовому варианту std::getline.
/// Вывести строку из элементов вектора в поток вывода.
template <class T>
std::ostream& writeln(std::ostream &os, const Matrix_row<T> &row)
{
for (auto &item : row)
os << ' ' << item;
return os << '\n';
}
/// Пропустить "горизонтальные" пробелы (' ' и '\t').
inline std::istream& skiphws(std::istream &is)
{
for (char ch; is.get(ch) && (ch == ' ' || ch == '\t');) {}
return is.unget();
}
/// Прочитать строку из потока ввода как последовательность элементов вектора.
template <class T>
std::istream& readln(std::istream &is, Matrix_row<T> &row)
{
row.clear();
for (T item; skiphws(is);)
{
if (is.peek() == '\n')
return is.ignore();
if (!(is >> item))
return is;
row.push_back(item);
}
return is;
}
///////////////////////////////////////////////////////////////////////////////
// Ввод-вывод матрицы как последовательности строк-векторов.
/// Вывести матрицу в поток вывода.
template <class T>
std::ostream& writeln(std::ostream &os, const Matrix<T> &matrix)
{
for (auto &row : matrix)
writeln(os, row);
return os << '\n'; // закрывающая пустая строка
}
/// Сделать массив массивов прямоугольным по максимальной строке ==
/// дополнить более короткие строки значениями по умолчанию.
template <class T>
void force_rectangularity(Matrix<T> &matrix)
{
// Найти максимальный размер строки.
size_t max_len = 0;
for (auto &row : matrix)
if (max_len < row.size())
max_len = row.size();
// Если max_len = 0, очистить матрицу.
if (max_len == 0)
{
matrix.clear();
}
else
{
// Дополнить все строки до максимального размера.
for (auto &row : matrix)
row.resize(max_len);
}
}
/// Прочитать из потока ввода матрицу как набор строк-векторов.
/// Заканчивает чтение на пустой строке (забирает эту строку из потока ввода).
template <class T>
std::istream& readln(std::istream &is, Matrix<T> &matrix)
{
matrix.clear();
for (Matrix_row<T> row; readln(is, row) && !row.empty();)
matrix.push_back(row);
force_rectangularity(matrix);
return is;
}
///////////////////////////////////////////////////////////////////////////////
// Вспомогательные операции.
/// Узнать количество строк в матрице.
template <class T>
inline size_t rows(const Matrix<T> &matrix)
{
return matrix.size();
}
/// Узнать количество столбцов в матрице.
template <class T>
inline size_t cols(const Matrix<T> &matrix)
{
return matrix.empty() ? 0 : matrix.front().size();
}
/// Задать новые размеры матрицы.
template <class T>
Matrix<T>& reshape(Matrix<T> &matrix, size_t rows, size_t cols)
{
matrix.resize(rows);
for (auto &row : matrix)
row.resize(cols);
return matrix;
}
/// Записать в каждый элемент вектора заданное значение.
template <class T>
Matrix_row<T>& fill(Matrix_row<T> &row, T value)
{
row.assign(row.size(), value);
return row;
}
/// Записать в каждый элемент матрицы заданное значение.
template <class T>
Matrix<T>& fill(Matrix<T> &matrix, T value)
{
for (auto &row : matrix)
fill(row, value);
return matrix;
}
/// Проверить, что все элементы вектора равны заданному значению.
template <class T>
bool consists_of(const std::vector<T> &vec, const T &value)
{
for (auto &item : vec)
if (item != value)
return false;
return true;
}
/// Проверить, что все элементы матрицы равны заданному значению.
template <class T>
bool consists_of(const Matrix<T> &matrix, T value)
{
for (auto &row : matrix)
if (!consists_of(row, value))
return false;
return true;
}
///////////////////////////////////////////////////////////////////////////////
// Создание матриц.
/// Создать объект матрицы (копию) из двумерного статического массива.
template <class T, size_t N, size_t M>
Matrix<T> matrix(const T (&arr)[N][M])
{
Matrix<T> result(N);
for (size_t i = 0; i < N; ++i)
result[i].assign(&arr[i][0], &arr[i][M]);
return result;
}
/// Создать матрицу заданных размеров с заданным значением элементов.
template <class T>
Matrix<T> matrix(size_t rows, size_t cols, T value = {})
{
Matrix<T> result(rows);
for (auto &row : result)
row.assign(cols, value);
return result;
}
/// Создать диагональную матрицу заданного размера.
template <class T>
Matrix<T> diagonal(size_t size, T value)
{
Matrix<T> result(size);
for (size_t i = 0; i < size; ++i)
{
auto &row = result[i];
row.resize(size);
row[i] = value;
}
return result;
}
/// Создать диагональную матрицу из диапазона.
/// Задействует некоторые "продвинутые" элементы современного C++.
/// It -- тип итератора, комбинация enable_if+is_convertible
/// используется, чтобы запретить компилятору использовать данный вариант
/// функции diagonal в том случае, если It не является однонаправленным итератором.
template <class It>
std::enable_if_t<std::is_convertible<
typename std::iterator_traits<It>::iterator_category,
std::forward_iterator_tag>::value,
Matrix<typename std::iterator_traits<It>::value_type>>
diagonal(It from, It to)
{
using std::distance;
const size_t size = distance(from, to);
Matrix<typename std::iterator_traits<It>::value_type> result(size);
for (size_t i = 0; i < size; ++i, ++from)
{
auto &row = result[i];
row.resize(size);
row[i] = *from;
}
return result;
}
/// Создать диагональную матрицу из произвольной коллекции.
/// С++11 вариант для MSVC2013, очень близок, но не идентичен
/// закомментированному варианту ниже.
template <class Col>
inline auto diagonal(const Col &collection)
-> decltype(diagonal(std::begin(collection), std::end(collection)))
{
return diagonal(std::begin(collection), std::end(collection));
}
/* C++14, но не MSVC2013:
template <class Col>
auto diagonal(const Col &collection)
{
using std::begin;
using std::end;
return diagonal(begin(collection), end(collection));
}
//*/
/// Вариант, позволяющий выполнять diagonal({ список значений на диагонали }).
template <class T>
inline Matrix<T> diagonal(std::initializer_list<T> values)
{
return diagonal(std::begin(values), std::end(values));
}
#endif//AMATRIX2_HPP_INCLUDED_XAM100
// amatrix2_test.cpp
// Тесты для функций, определённых в amatrix2.hpp.
#include "amatrix2.hpp"
#include <sstream>
#include <cassert>
using namespace std;
class Amatrix2_test
{
using Num = double;
using Row = Matrix_row<Num>;
using Mtx = Matrix<Num>;
static int test_readln()
{
// Прочитаем вектор.
istringstream is("4 5 6.5 -1.125");
Row row;
readln(is, row);
if (row != Row{ 4., 5., 6.5, -1.125 })
return 1;
// Прочитаем две матрицы подряд.
is.clear();
is.str
(
"0.5 1.5 2.5 3.5\n"
"6.1 -0.1\n"
"8.2\n\n"
"12 42\n"
"16 -12\n\n"
);
Mtx mtx, mtx2;
readln(is, mtx);
readln(is, mtx2);
if (rows(mtx) != 3 || cols(mtx) != 4)
return 2;
if (mtx != Mtx
{
Row{ 0.5, 1.5, 2.5, 3.5 },
Row{ 6.1, -0.1, 0.0, 0.0 },
Row{ 8.2, 0.0, 0.0, 0.0 }
})
return 3;
if (mtx2 != Mtx
{
Row{ 12., 42. },
Row{ 16., -12. }
})
return 4;
return 0;
}
static int test_writeln()
{
// Запишем вектор.
ostringstream os;
writeln(os, Row{ -1.5, 0., 2.7 });
if (os.str() != " -1.5 0 2.7\n")
return 1;
// Запишем матрицу.
os.str("");
writeln(os, Mtx
{
Row{ 10.1, 100, 0 },
Row{ 0, -1, 42.5 }
});
if (os.str() !=
" 10.1 100 0\n"
" 0 -1 42.5\n\n")
return 2;
return 0;
}
static int test_reshape_and_fill()
{
Mtx mtx;
reshape(mtx, 10, 100);
if (rows(mtx) != 10 || rows(mtx) != mtx.size())
return 1;
if (cols(mtx) != 100 || cols(mtx) != mtx[0].size())
return 2;
fill(mtx, 42.);
if (!consists_of(mtx, 42.))
return 3;
return 0;
}
static int test_matrix_creation()
{
// matrix (1)
{
auto mtx = matrix(9, 4, 111.);
if (rows(mtx) != 9 || cols(mtx) != 4)
return 1;
if (!consists_of(mtx, 111.))
return 2;
}
// matrix (2)
{
double arr[2][4] =
{
{ 1., 2., 3., 4. },
{ 4., 1., 3., 2. }
};
auto mtx = matrix(arr);
if (rows(mtx) != 2 || cols(mtx) != 4)
return 3;
if (mtx != Mtx
{
Row{ 1., 2., 3., 4. },
Row{ 4., 1., 3., 2. }
})
return 3;
}
// diagonal
{
const Mtx dref
{
Row { 1., 0., 0., 0. },
Row { 0., 2., 0., 0. },
Row { 0., 0., 42., 0. },
Row { 0., 0., 0., 23. }
};
double darr[4] = { 1., 2., 42., 23. };
if (diagonal(darr) != dref)
return 4;
if (diagonal({ 1., 2., 42., 23. }) != dref)
return 5;
if (diagonal(Row{ 1., 2., 42., 23. }) != dref)
return 6;
if (diagonal({ 1., 1., 1. }) != diagonal(3, 1.))
return 7;
}
return 0;
}
public:
static int test_all()
{
int result = 0;
// Здесь именно =, а не ==.
if (result = test_readln())
return 100 + result;
if (result = test_writeln())
return 200 + result;
if (result = test_reshape_and_fill())
return 300 + result;
if (result = test_matrix_creation())
return 400 + result;
return 0;
}
Amatrix2_test()
{
assert(test_all() == 0);
}
};
const Amatrix2_test test_it;
// matrix_zero_block.cpp
#include "amatrix2.hpp"
/// Определить, являются ли внешние по отношению к квадратной подматрице
/// строки или столбцы нулевыми. Возвращает истину для квадратных матриц.
template <class T>
bool are_outer_lines_zeroes(const Matrix<T> &mtx)
{
const auto r = rows(mtx), c = cols(mtx);
if (r < c)
{
// Строк меньше, чем столбцов -- проверим "хвосты" строк на равенство нулю.
// Длина "хвоста".
const auto diff = c - r;
for (auto &row : mtx)
for (size_t j = diff; j < c; ++j)
if (row[j] != T())
return false;
}
else if (c < r)
{
// Столбцов меньше, чем строк -- проверим "лишние" строки на равенство нулю.
// Вычислим указатель на первую "лишнюю" строку,
// все последующие элементы массива принадлежат "лишним" строкам,
// проверим их на равенство нулю.
const auto diff = r - c;
for (size_t i = diff; i < r; ++i)
if (!consists_of(mtx[i], T()))
return false;
}
// Либо матрица является квадратной, либо проверка в ветках if прошла успешно.
return true;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <cassert>
int test_are_outer_lines_zeroes()
{
Matrix<float> m;
reshape(m, 10, 10);
fill(m, 1.f);
if (!are_outer_lines_zeroes(m))
return 1;
reshape(m, 10, 20);
if (!are_outer_lines_zeroes(m))
return 2;
m[5][15] = 42.f;
if (are_outer_lines_zeroes(m))
return 3;
reshape(m, 20, 10);
if (!are_outer_lines_zeroes(m))
return 4;
m[15][5] = 23.f;
if (are_outer_lines_zeroes(m))
return 5;
return 0;
}
int main()
{
assert(test_are_outer_lines_zeroes() == 0);
return 0;
}
// is_incidence_matrix.cpp
// amatrix2.hpp не используется, только позаимствованы объявления синонимов типов Matrix_row и Matrix
#include <vector>
#include <cassert>
/// Шаблон синонима типа, представляющий строку матрицы как вектор.
template <class T>
using Matrix_row = std::vector<T>;
/// Шаблон синонима типа, представляющий матрицу как вектор строк.
template <class T>
using Matrix = std::vector<Matrix_row<T>>;
/// Проверить, является ли матрица 0,1-матрицей.
template <class T>
bool is_01_matrix(const Matrix<T> &m)
{
for (auto &row : m)
for (auto item : row)
if (item != T(0) && item != T(1))
return false;
return true;
}
/// Вычислить вектор сумм элементов столбцов матрицы.
/// Некий тип S используется для счётчика вместо собственно типа T, поскольку T может быть булевским.
template <class S, class T>
std::vector<S> row_sum(const Matrix<T> &m)
{
std::vector<S> s;
if (m.empty())
return s;
const auto rsz = m.front().size();
s.resize(rsz);
for (auto &row : m)
{
assert(row.size() == rsz);
for (std::size_t i = 0; i < rsz; ++i)
s[i] += row[i];
}
return s;
}
/// Проверить, является ли матрица матрицей инцидентности
/// (0,1-матрицей, в каждом столбце которой ровно две единицы).
template <class T>
bool is_incidence_matrix(const Matrix<T> &m)
{
if (!is_01_matrix(m))
return false;
for (auto item : row_sum<std::size_t>(m))
if (item != 2)
return false;
return true;
}
/// Тесты.
int test_is_incidence_matrix()
{
using M = Matrix<int>;
using R = M::value_type; // то же, что Matrix_row<bool>
M m =
{
R{ 0, 0, 1, 1, 1 },
R{ 0, 1, 1, 0, 0 },
R{ 0, 0, 0, 1, 0 },
R{ 1, 0, 0, 0, 1 }
};
if (!is_01_matrix(m))
return 1;
if (row_sum<int>(m) != R{ 1,1,2,2,2 })
return 2;
if (is_incidence_matrix(m))
return 3;
m[0][0] = 1;
m[0][1] = 2;
if (is_01_matrix(m))
return 4;
if (row_sum<int>(m) != R{ 2,3,2,2,2 })
return 5;
if (is_incidence_matrix(m))
return 6;
m[0][1] = 1;
if (!is_incidence_matrix(m))
return 7;
return 0;
}
int main()
{
assert(test_is_incidence_matrix() == 0);
return 0;
}
// file_unique_lines.cpp
// Дан файл, создать новый файл на его основе, не сохраняя подряд идущие повторяющиеся строки.
// Этот пример очень простой. Допускается добавление символа перевода строки в конце.
#include <istream>
#include <ostream>
#include <string>
// Функция читает поток ввода is построчно и пишет новые строки в os.
void unique_lines(std::istream &is, std::ostream &os)
{
// Первая строка is идёт в os в любом случае.
std::string last_line;
if (!getline(is, last_line))
return; // не удалось считать и одну строку
os << last_line << '\n';
// Следующие строки проверяем на повторение.
for (std::string line; getline(is, line); )
if (line != last_line)
{
os << line << '\n';
last_line.swap(line); // обойдёмся без копирования строк
}
}
// Консольное приложение.
#include <iostream>
#include <fstream>
int main()
{
using namespace std;
string filename; // Переменная для считывания имени файла с консоли.
ifstream input; // Файл ввода.
ofstream output; // Файл вывода.
while (true)
{
cout << "Enter the input file name: ";
// Пытаемся открыть файл ввода.
while (true)
{
if (!getline(cin, filename))
return 0; // выход
input.open(filename);
if (input.is_open())
break; // удалось открыть
cout << "Sorry, the file \"" << filename << "\" can't be read.\n";
}
cout << "Enter the output file name: ";
// Пытаемся открыть файл вывода.
while (true)
{
if (!getline(cin, filename))
return 0;
output.open(filename);
if (output.is_open())
break; // удалось открыть
cout << "Sorry, the file \"" << filename << "\" can't be written.\n";
}
// Выполнить операцию над открытыми файлами.
unique_lines(input, output);
// Закрыть файлы.
input.close();
output.close();
}
}
// line_len_stats_0.cpp
// Для заданного файла определить:
// минимальную, максимальную и среднюю длины строк, считая только непробельные символы.
#include <cctype>
#include <istream>
#include <ostream>
#include <string>
// Подсчёт числа непробельных символов в строке.
std::size_t non_space_length(const std::string &line)
{
std::size_t counter = 0;
for (unsigned char ch: line)
counter += !std::isspace(ch);
return counter;
}
// Функтор, собирающий статистику (минимум, максимум, среднее переданных ему значений).
class Statistics
{
std::size_t minv, maxv, n;
double sum;
public:
// конструктор по умолчанию
Statistics()
: minv(0), maxv(0), sum(0), n(0) {}
// оператор () выполняет обновление статистики
void operator()(std::size_t next)
{
if (n > 0)
{
if (next < minv)
minv = next;
else if (maxv < next)
maxv = next;
}
else
{
minv = maxv = next;
}
++n;
sum += next;
}
// извлечь минимум на данный момент
std::size_t min() const { return minv; }
// извлечь максимум на данный момент
std::size_t max() const { return maxv; }
// извлечь количество
std::size_t count() const { return n; }
// среднее арифметическое
double ar_avg() const { return n? sum / n: 0.0; }
};
// Оператор вывода статистики в поток.
std::ostream& operator<<(std::ostream &os, const Statistics &stats)
{
os << "count = " << stats.count();
os << "; min = " << stats.min();
os << "; max = " << stats.max();
os << "; ar-avg = " << stats.ar_avg();
return os;
}
// Собственно сбор статистики по длине строк в потоке без учёта пробельных символов.
Statistics non_space_line_lengths(std::istream &is)
{
Statistics stats;
for (std::string line; getline(is, line); )
stats(non_space_length(line));
return stats;
}
// Консольное приложение.
#include <fstream>
#include <iostream>
int main()
{
// получаем имя файла, пытаемся открыть, если открылся -- считаем и выведем статистику
using namespace std;
for (string line; getline(cin, line); )
{
ifstream input(line);
if (!input.is_open())
cout << "Failed to open \"" << line << "\" for reading.\n";
else
cout << non_space_line_lengths(input) << endl;
}
return 0;
}
// concat_unique_lines.cpp
#include <cstdlib>
#include <string>
#include <queue>
#include <fstream>
#include <iostream>
/// Класс, инкапсулирующий последовательность (очередь) файлов.
class File_sequence
{
private:
std::queue<std::string> filenames; // очередь имён файлов, ожидающих открытия.
std::ifstream current_file; // текущий файл.
public:
File_sequence() {}
/// Инициализировать очередь имён, передав диапазон имён файлов.
template <class InIt>
File_sequence(InIt from, InIt to)
: filenames(std::deque<std::string>(from, to)) {}
/// Добавить в конец очереди имя ещё одного файла.
void push(const std::string &filename)
{
filenames.push(filename);
}
/// Обратиться к текущему файлу как к потоку ввода.
std::istream& access_once()
{
if (!current_file.is_open() || current_file.eof())
open_next_file();
return current_file;
}
/// Проверить состояние текущего файла.
/// Возвращает false либо из-за ошибки чтения (access_once().fail()), либо из-за того, что очередь закончилась.
operator bool() { return access_once().good(); }
private:
// Открыть следующий файл из очереди.
void open_next_file()
{
current_file.close();
while (!filenames.empty() && !current_file.is_open())
{
current_file.open(filenames.front());
filenames.pop();
}
}
};
/// Считать одну строку, замена std::getline для File_sequence.
inline File_sequence& getline(File_sequence &fs, std::string &line)
{
std::getline(fs.access_once(), line);
return fs;
}
/// Приложение.
int main(int argc, const char *argv[])
{
using namespace std;
File_sequence lines(argv + 1, argv + argc);
if (argc < 2)
{
// Прочитать имена файлов с потока ввода.
for (string filename; getline(cin, filename);)
lines.push(filename);
cin.clear();
}
// Do the job.
string prev;
if (getline(lines, prev))
{
cout << prev << '\n';
for (string line; getline(lines, line); )
if (prev != line)
cout << (prev = line) << '\n';
}
return EXIT_SUCCESS;
}
// concat_unique_lines.cpp
#include <cstdlib>
#include <string>
#include <queue>
#include <fstream>
#include <iostream>
// NEW: Используем глобальную "локаль" для определения какой символ является пробельным.
#include <locale>
// NEW: Используем шаблон std::numeric_limits для инициализации минимума и максимума.
#include <limits>
/// Класс, инкапсулирующий последовательность (очередь) файлов.
class File_sequence
{
private:
std::queue<std::string> filenames; // очередь имён файлов, ожидающих открытия.
std::ifstream current_file; // текущий файл.
public:
File_sequence() {}
/// Инициализировать очередь имён, передав диапазон имён файлов.
template <class InIt>
File_sequence(InIt from, InIt to)
: filenames(std::deque<std::string>(from, to)) {}
/// Добавить в конец очереди имя ещё одного файла.
void push(const std::string &filename)
{
filenames.push(filename);
}
/// Обратиться к текущему файлу как к потоку ввода.
std::istream& access_once()
{
if (!current_file.is_open() || current_file.eof())
open_next_file();
return current_file;
}
/// Проверить состояние текущего файла.
/// Возвращает false либо из-за ошибки чтения (access_once().fail()), либо из-за того, что очередь закончилась.
operator bool() { return access_once().good(); }
private:
// Открыть следующий файл из очереди.
void open_next_file()
{
current_file.close();
while (!filenames.empty() && !current_file.is_open())
{
current_file.open(filenames.front());
if (!current_file.is_open()) // NEW: сообщить о невозможности открытия очередного файла.
std::clog << "File open failed: " << filenames.front() << '\n';
filenames.pop();
}
}
};
/// Считать одну строку, замена std::getline для File_sequence.
inline File_sequence& getline(File_sequence &fs, std::string &line)
{
std::getline(fs.access_once(), line);
return fs;
}
// NEW
/// Количество непробельных символов в строке
std::size_t count_nonspace(const std::string &line, const std::locale &gl)
{
std::size_t result = 0;
for (auto ch : line)
result += !std::isspace(ch, gl);
return result;
}
// NEW
/// Функтор, сохраняющий "статистику" переданных ему значений
/// (минимум, максимум, общее количество).
template <class Num>
class Statistics
{
Num minv, maxv, sumv;
std::size_t n;
using Limits = std::numeric_limits<Num>;
public:
Statistics()
: minv(Limits::max()), maxv(Limits::lowest()), sumv(), n(0) {}
/// Обработать следующий замер.
Statistics& operator()(Num num)
{
++n;
sumv += num;
if (num < minv)
minv = num;
else if (maxv < num)
maxv = num;
return *this;
}
/// Получить минимум из всех замеров.
Num min() const { return minv; }
/// Получить максимум из всех замеров.
Num max() const { return maxv; }
/// Получить накопленную сумму.
Num sum() const { return sumv; }
/// Получить количество всех замеров.
std::size_t count() const { return n; }
};
/// Приложение.
int main(int argc, const char *argv[])
{
using namespace std;
File_sequence lines(argv + 1, argv + argc);
if (argc < 2)
{
// Прочитать имена файлов с потока ввода.
for (string filename; getline(cin, filename);)
lines.push(filename);
cin.clear();
}
// NEW
locale gl; // глобальная локаль по умолчанию.
Statistics<size_t> stats;
for (string line; getline(lines, line); )
stats(count_nonspace(line, gl));
// Вывести результат
cout << "Count: " << stats.count();
cout << "\nMin: " << stats.min();
cout << "\nMax: " << stats.max();
cout << "\nAvg: " << double(stats.sum()) / stats.count();
cout << endl;
return EXIT_SUCCESS;
}
// remove_comments_vs.cpp
#include <vector>
#include <string>
/// Тип "строка".
using Line = std::string;
/// Тип "строки" (массив строк).
using Lines = std::vector<Line>;
/// Тип "символ" (строки Line).
using Char = Line::value_type;
/// Удалить закомментированный "хвост" строки.
void remove_comment(Line &line, Char ch)
{
const auto pos = line.find(ch);
// Функция поиска возвращает позицию знака или
// особое значение npos, если знак не найден.
if (pos != Line::npos)
line.resize(pos);
}
/// Удалить комментарии из текста.
void remove_comments(Lines &text, Char comment_mark)
{
for (auto &line : text)
remove_comment(line, comment_mark);
}
// Никаких вспомогательных определений уже не требуется:
// всё, что нужно есть в Стандартной библиотеке C++.
/// Тест функции remove_comments.
bool test_remove_comments()
{
// Исходный текст.
Lines input =
{
"",
"# comment",
"something; # comment",
"'hello, world!'",
"'# not a comment but it's OK to cut here too'... # a real comment"
};
// Текст результата, который должен получиться.
const Lines reference =
{
"",
"",
"something; ",
"'hello, world!'",
"'"
};
remove_comments(input, '#');
return input == reference;
}
#include <cassert>
int main()
{
assert(test_remove_comments());
return 0;
}
// dfa_1proc.cpp
#include <istream>
// Возвращает истину, если автомат остановился в принимающем состоянии.
bool dfa_example(std::istream &is)
{
int state = 0;
bool running = true;
for (char input; is.get(input) && running; ) switch (state)
{
case 0:
if (input == 'a')
state = 1;
else
running = false;
break;
case 1:
if (input == 'b')
state = 2;
else
running = false;
break;
case 2:
if (input == 'c')
state = 3;
else if (input == 'b')
state = 4;
else
running = false;
break;
case 3:
state = 0;
break;
case 4:
if (input == 'b')
state = 1;
else
running = false;
break;
}
// Состояние 4 -- принимающее.
return state == 4;
}
// Проверочная программа.
// Чтобы закончить ввод очередной строки, можно ввести признак конца файла.
#include <iostream>
int main()
{
using namespace std;
while (true)
{
auto accepts = dfa_example(cin);
cout << "\nAccepted: " << accepts << endl;
cin.clear();
cin.sync();
cin.ignore(cin.rdbuf()->in_avail());
}
}
// dfa_2obj.cpp
#include <cassert>
// Конечный автомат в объектной оболочке, отвязанный от istream -- принимает по одному символу.
class Dfa_example
{
int state;
public:
// Конструктор по умолчанию устанавливает начальное состояние.
Dfa_example()
: state(0) {} // список инициализации: здесь то же, что state = 0
// Проверить, находится ли автомат в принимающем состоянии.
bool accepts() const // const говорит, что вызов данной функции не меняет состояние объекта
{
return state == 4;
}
// Возвращает ложь, если автомат застопорился (можно проигнорировать).
// Возвращает истину, если автомат не застопорился и ожидает следующий символ.
bool operator()(char input)
{
switch (state)
{
case 0:
if (input == 'a')
state = 1;
else
return false;
break;
case 1:
if (input == 'b')
state = 2;
else
return false;
break;
case 2:
if (input == 'c')
state = 3;
else if (input == 'b')
state = 4;
else
return false;
break;
case 3:
state = 0;
break;
case 4:
if (input == 'b')
state = 1;
else
return false;
break;
default:
assert(false); // сюда должно быть невозможно попасть
}
return true; // нет застопоривания
}
};
// Проверочная программа.
// Чтобы закончить ввод очередной строки, можно ввести признак конца файла.
#include <iostream>
int main()
{
using namespace std;
while (true)
{
Dfa_example dfa; // создать очередной объект автомата
// так как автомат теперь не работает с потоком ввода сам,
// цикл по символам перемещается в вызывающую программу
for (char input; cin.get(input) && dfa(input); )
{ /* здесь не должно быть кода */ }
cout << "\nAccepted: " << dfa.accepts() << endl;
cin.clear();
cin.sync();
cin.ignore(cin.rdbuf()->in_avail());
}
}
// charlit_dfa_v0.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Возможные состояния автомата.
enum
{
open_quote, // ожидается открывающая '
close_quote, // ожидается закрывающая '
not_quote, // первый символ литерала, не может быть '
escape, // после \
accepted, // литерал закончился
stuck // застопоривание: не литерал
} state = open_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case open_quote:
state = ch == '\''? not_quote : stuck;
break;
case not_quote:
switch (ch)
{
case '\\': state = escape; break;
case '\'': state = stuck; break;
default: state = close_quote;
}
break;
case close_quote:
switch (ch)
{
case '\\': state = escape; break;
case '\'': state = accepted; return from;
default:; /* ничего не менять */
}
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
case stuck:
return nullptr;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// charlit_dfa_v1.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Вытащим open_quote: данное состояние имеет смысл только на первом символе.
if (from == to || *from++ != '\'')
return nullptr;
// Возможные состояния автомата.
enum
{
close_quote, // ожидается закрывающая '
not_quote, // первый символ литерала, не может быть '
escape // после \
} state = not_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case not_quote:
if (ch == '\'')
return nullptr;
state = ch == '\\' ? escape : close_quote;
break;
case close_quote:
if (ch == '\'')
return from;
if (ch == '\\')
state = escape;
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// charlit_dfa_v2.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Вытащим open_quote: данное состояние имеет смысл только на первом символе.
if (from == to || *from++ != '\'')
return nullptr;
// Вытащим not_quote: данное состояние имеет смысл только на втором символе.
if (from == to || *from == '\'')
return nullptr;
// Возможные состояния автомата.
enum
{
close_quote, // ожидается закрывающая '
escape // после \
} state = *from++ == '\\'? escape: close_quote;
while (from != to)
{
const char ch = *from++;
switch (state)
{
case close_quote:
if (ch == '\'')
return from;
if (ch == '\\')
state = escape;
break;
case escape:
/* просто пропустить символ */
state = close_quote;
break;
default:
assert(!"impossible FSM state occured");
}
}
return nullptr; // слишком рано кончилась строка
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// charlit_dfa_v3.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
bool await_quote = from[1] != '\\';
for (from += 2; from != to;)
{
const char ch = *from++;
if (await_quote)
{
if (ch == '\'')
return from;
if (ch == '\\')
await_quote = false;
}
else
await_quote = true;
}
return nullptr; // слишком рано кончилась строка
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// charlit_dfa_v4.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
for (++from; from != to;)
{
switch (*from++)
{
case '\\':
if (from++ == to)
return nullptr;
break;
case '\'':
return from;
default:; /* do nothing */
}
}
return nullptr;
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'",
"'\\\'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// charlit_dfa_v5.cpp
// ДКА-распознаватель символьных литералов C++ (упрощённый).
#include <cassert>
#include <string>
/// Просматривает диапазон массива символов [from, to).
/// Возвращает указатель на символ, следующий за последним принятым (т.е. за литералом).
/// Возвращает nullptr, если литерал не был успешно распознан.
const char* char_lit(const char *from, const char *to)
{
// Не менее трёх символов.
// Первый символ должен быть кавычкой, второй символ не должен быть кавычкой.
if (to - from < 3 || from[0] != '\'' || from[1] == '\'')
return nullptr;
for (++from;;)
{
if (from == to)
return nullptr;
const char ch = *from++;
if (ch == '\\' && from++ == to)
return nullptr;
if (ch == '\'')
return from;
}
}
inline std::size_t char_lit(const char *from, std::size_t len)
{
const auto ptr = char_lit(from, from + len);
return ptr ? ptr - from : 0;
}
int test_char_lit()
{
using namespace std;
const struct {
string str; size_t len;
} in1[] =
{
{ "'a' ' '", 3 },
{ "'\\a'''", 4 },
{ "'1234'fff'", 6 },
{ "'\\''a'", 4 },
{ "'\"'\"'\"'", 3 }
};
int code = 0;
for (auto &test : in1)
{
++code;
if (char_lit(test.str.data(), test.str.length()) != test.len)
return code;
}
const string in2[] =
{
"'",
"\"abc\"",
"abracadabra",
"''''",
" 'a'",
"'\\\'"
};
for (auto &test : in2)
{
++code;
if (char_lit(test.data(), test.length()) != 0)
return code;
}
return 0;
}
int main()
{
assert(test_char_lit() == 0);
return 0;
}
// dfa_2proc.cpp
#include <cassert>
#include <iterator>
template <class Val>
inline int compare(const Val &a, const Val &b)
{
return a < b ? 1 : b < a ? -1 : 0;
}
enum Sequence_type
{
monotone_decreasing = -1,
empty_or_constant = 0,
monotone_increasing = 1,
not_monotone = 2
};
/// ValIt -- итератор (обобщение указателя),
/// последовательность принадлежит полуинтервалу [from, to).
template <class ValIt>
Sequence_type sequence_type(ValIt from, ValIt to)
{
Sequence_type state = empty_or_constant;
if (from != to)
{
for (ValIt a = from, b = std::next(from); b != to; a = b++)
{
const int relation = compare(*a, *b);
switch (state)
{
case monotone_decreasing:
if (relation == 1)
state = not_monotone;
break;
case empty_or_constant:
if (relation == -1)
state = monotone_decreasing;
else if (relation == 1)
state = monotone_increasing;
break;
case monotone_increasing:
if (relation == -1)
state = not_monotone;
break;
case not_monotone:
break; /* do nothing */
default:
assert(!"sequence_type: impossible Sequence_type");
}
}
}
return state;
}
/// Проверить содержимое контейнера.
template <class Container>
inline Sequence_type sequence_type(const Container &container)
{
using std::begin;
using std::end;
return sequence_type(begin(container), end(container));
}
/////////////////////////////////////////////////////////////////////
// Тесты.
int test_sequence_type()
{
int a[] = { 1 },
b[] = { 2, 2, 2, 2, 2 },
c[] = { 0, 0, 1, 1, 2 },
d[] = { 2, 2, 2, 0, 0 },
e[] = { 0, 0, 1, 0, 0 };
if (sequence_type(a) != empty_or_constant)
return 1;
if (sequence_type(b) != empty_or_constant)
return 2;
if (sequence_type(c) != monotone_increasing)
return 3;
if (sequence_type(d) != monotone_decreasing)
return 4;
if (sequence_type(e) != not_monotone)
return 5;
return 0;
}
int main()
{
assert(test_sequence_type() == 0);
return 0;
}
// fst_crlf_v0.cpp
#include <cassert>
// Возвращает указатель на символ, следующий за последним записанным символом.
char* crlf_normalize(const char *from, const char *end, char *to)
{
enum { Other, LF, CR } state = Other;
while (from != end)
{
const char input = *from++;
switch (state)
{
case Other:
switch (input)
{
case '\n':
*to++ = '\n';
state = LF;
break;
case '\r':
*to++ = '\n';
state = CR;
break;
default:
*to++ = input;
}
break;
case LF:
switch (input)
{
case '\n':
*to++ = '\n';
break;
case '\r':
state = Other;
break;
default:
*to++ = input;
state = Other;
}
break;
case CR:
switch (input)
{
case '\n':
state = Other;
break;
case '\r':
*to++ = '\n';
break;
default:
*to++ = input;
state = Other;
}
break;
default:
assert(!"crlf_normalize: impossible state");
}
}
return to;
}
/////////////////////////////////////////////////////////////////////
#include <cstring>
int test_crlf_normalize()
{
using namespace std;
const char input[]
= "test string\nthen\n\nand then\ror"
"\r\rand now combinations\n\rand\r\n"
"and finally\n\n\r\n\r\n\r\r!",
reference_output[]
= "test string\nthen\n\nand then\nor"
"\n\nand now combinations\nand\n"
"and finally\n\n\n\n\n!";
char output[200] = {};
const auto output_len
= crlf_normalize(input, input + strlen(input), output);
if (output_len - output != strlen(reference_output))
return 2;
return strcmp(output, reference_output);
}
int main()
{
assert(test_crlf_normalize() == 0);
return 0;
}
// fst_crlf_v1.cpp
#include <cassert>
// Возвращает указатель на символ, следующий за последним записанным символом.
char* crlf_normalize(const char *from, const char *end, char *to)
{
char input;
Other:
if (from == end) return to;
input = *from++;
if (input == '\n') goto LF;
if (input == '\r') goto CR;
*to++ = input;
goto Other;
LF:
*to++ = '\n';
if (from == end) return to;
input = *from++;
if (input == '\r') goto Other;
if (input == '\n') goto LF;
*to++ = input;
goto Other;
CR:
*to++ = '\n';
if (from == end) return to;
input = *from++;
if (input == '\n') goto Other;
if (input == '\r') goto CR;
*to++ = input;
goto Other;
}
/////////////////////////////////////////////////////////////////////
#include <cstring>
int test_crlf_normalize()
{
using namespace std;
const char input[]
= "test string\nthen\n\nand then\ror"
"\r\rand now combinations\n\rand\r\n"
"and finally\n\n\r\n\r\n\r\r!",
reference_output[]
= "test string\nthen\n\nand then\nor"
"\n\nand now combinations\nand\n"
"and finally\n\n\n\n\n!";
char output[200] = {};
const auto output_len
= crlf_normalize(input, input + strlen(input), output);
if (output_len - output != strlen(reference_output))
return 2;
return strcmp(output, reference_output);
}
int main()
{
assert(test_crlf_normalize() == 0);
return 0;
}
// fst_crlf_v2.cpp
#include <cassert>
// Автомат, запоминающий состояние между вызовами.
class Crlf_normalizer
{
enum { Other, LF, CR } state;
public:
// Конструктор устанавливает начальное состояние.
Crlf_normalizer() : state(Other) {}
// Оператор "скобки" позволяет вызывать объект данного класса как функцию.
// Возвращает указатель на символ, следующий за последним записанным символом.
char* operator()(const char *from, const char *end, char *to)
{
char input;
switch (state)
{
Other_:
case Other:
if (from == end) // выход
return state = Other, to;
input = *from++;
if (input == '\n') goto LF_;
if (input == '\r') goto CR_;
*to++ = input;
goto Other_;
LF_:
*to++ = '\n';
case LF:
if (from == end) // выход
return state = LF, to;
input = *from++;
if (input == '\r') goto Other_;
if (input == '\n') goto LF_;
*to++ = input;
goto Other_;
CR_:
*to++ = '\n';
case CR:
if (from == end) // выход
return state = CR, to;
input = *from++;
if (input == '\n') goto Other_;
if (input == '\r') goto CR_;
*to++ = input;
goto Other_;
default:
assert(false);
return to;
}
}
};
/////////////////////////////////////////////////////////////////////
#include <cstring>
int test_crlf_normalize()
{
using namespace std;
const char input[]
= "test string\nthen\n\nand then\ror"
"\r\rand now combinations\n\rand\r\n"
"and finally\n\n\r\n\r\n\r\r!",
reference_output[]
= "test string\nthen\n\nand then\nor"
"\n\nand now combinations\nand\n"
"and finally\n\n\n\n\n!";
Crlf_normalizer crlf;
char output[200] = {};
// Применим crlf дважды, чтобы проверить сохранение состояния между вызовами.
const auto output_len
= crlf(input + 17, input + strlen(input),
crlf(input, input + 17, output));
if (output_len - output != strlen(reference_output))
return 2;
return strcmp(output, reference_output);
}
int main()
{
assert(test_crlf_normalize() == 0);
return 0;
}
// fst_cpp_decomment.cpp
// Удалить из файла с исходным кодом C++ комментарии.
//
// Вход: файл в стандартном потоке ввода.
// Выход: файл без комментариев в потоке вывода.
//
// Комментарии могут быть двух видов: // ... конец строки
// и /* ... */ без вложенных.
// Комментарии не могут быть внутри строкого или символьного литерала.
// Автомат читает блок символов из диапазона [from, to)
// и записывает результат обработки в массив по адресу out.
char* cpp_decomment(const char *from, const char *to, char *out)
{
Normal_mode:
while (from != to)
{
switch (const char in = *from++)
{
case '\'':
*out++ = in;
goto Char_literal;
case '\"':
*out++ = in;
goto String_literal;
case '/':
goto Possible_comment;
default:
*out++ = in;
}
}
return out;
Char_literal:
while (from != to)
{
switch (const char in = *from++)
{
case '\\': // Char_escape
*out++ = in;
if (from != to)
*out++ = *from++;
break;
case '\'':
*out++ = in;
goto Normal_mode;
default:
*out++ = in;
}
}
return out;
String_literal:
while (from != to)
{
switch (const char in = *from++)
{
case '\\': // String_escape
*out++ = in;
if (from != to)
*out++ = *from++;
break;
case '\"':
*out++ = in;
goto Normal_mode;
default:
*out++ = in;
}
}
return out;
Possible_comment:
if (from == to)
return *out++ = '/', out;
switch (const char in = *from++)
{
case '/': goto Oneliner;
case '*': goto Multiliner;
default:
out[0] = '/';
out[1] = in;
out += 2;
goto Normal_mode;
}
Oneliner:
while (from != to)
{
switch (const char in = *from++)
{
case '\n':
*out++ = in;
goto Normal_mode;
case '\\': // Comment_concat
if (from != to)
++from; // just skip the next char
break;
default:; // skip
}
}
return out;
Multiliner:
while (from != to)
{
if (*from++ == '*')
goto Possible_end;
}
return out;
Possible_end:
if (from != to && *from++ == '/')
{
*out++ = ' ';
goto Normal_mode;
}
goto Multiliner;
}
// Код консольного приложения.
#include <iostream>
#include <string>
int main()
{
using namespace std;
ios::sync_with_stdio(false); /* Отключив синхронизацию с
библиотекой ввода-вывода C, можно получить улучшение производительности. */
// Считать весь текст с потока ввода как последовательность блоков.
static const size_t BUFFER_SIZE = 1024; // Блок в 1кб.
string input;
input.reserve(3 * BUFFER_SIZE);
char buffer[BUFFER_SIZE];
do
{
cin.read(buffer, BUFFER_SIZE);
input.insert(input.end(), &buffer[0], &buffer[0] + cin.gcount());
}
while (cin);
if (input.empty())
return 1;
// Подготовить место для вывода.
string output;
output.resize(input.size());
char *const out = &output[0];
// Выполнить обработку ввода и вывод результата в поток вывода.
auto result_size =
cpp_decomment(input.data(), input.data() + input.size(), out) - out;
output.resize(result_size);
cout << output;
return 0;
}
// parse_int.cpp
// Распознавание целочисленного литерала по стандарту C++14.
// Описание распознанного значения целочисленного литерала (непосредственно записанной константы).
struct Integer
{
// Значение по модулю.
unsigned long long value;
// Информация о типе значения (по суффиксу).
enum Integer_type
{
Signed = 0, // по умолчанию: signed int
Unsigned = 1, // есть unsigned (суффикс u/U)
Long = 2, // есть long (суффикс l/L), может комбинироваться с unsigned (ul/UL)
LongLong = 4 // есть long long (суффикс ll/LL), может комбинироваться с unsigned (ull/ULL)
} type;
};
inline bool operator==(const Integer &a, const Integer &b)
{
return a.type == b.type && a.value == b.value;
}
inline bool operator!=(const Integer &a, const Integer &b)
{
return !(a == b);
}
// Получить значение двоичной цифры.
// Возвращает -1, если ch -- не двоичная цифра.
// Действие оформлено в виде функтора для удобства использования в шаблоне.
const struct Bin_digit
{
static const auto radix = 2u;
int operator()(char ch) const
{
switch (ch)
{
case '0': return 0;
case '1': return 1;
default: return -1;
}
}
} bin_digit;
// Получить значение восьмеричной цифры.
// Возвращает -1, если ch -- не восьмиричная цифра.
// Действие оформлено в виде функтора для удобства использования в шаблоне.
const struct Oct_digit
{
static const auto radix = 8u;
int operator()(char ch) const
{
const int val = ch - '0';
return (unsigned)val < 8u ? val : -1;
}
} oct_digit;
// Получить значение десятичной цифры.
// Возвращает -1, если ch -- не десятичная цифра.
// Действие оформлено в виде функтора для удобства использования в шаблоне.
const struct Dec_digit
{
static const auto radix = 10u;
int operator()(char ch) const
{
const int val = ch - '0';
return (unsigned)val < 10u ? val : -1;
}
} dec_digit;
// Получить значение шестнадцатеричной цифры.
// Возвращает -1, если ch -- не шестнадцатеричная цифра.
// Действие оформлено в виде функтора для удобства использования в шаблоне.
const struct Hex_digit
{
static const auto radix = 16u;
int operator()(char ch) const
{
const int
vald = ch - '0',
valh = ch - 'a' + 10,
valH = ch - 'A' + 10;
if ((unsigned)vald < 10u)
return vald;
if ((unsigned)valh < 16u)
return valh;
if ((unsigned)valH < 16u)
return valH;
return -1;
}
} hex_digit;
// Прочитать последовательность цифр.
// Система счисления определяется функтором DigitParser.
// Результат распознавания:
// -- в случае неуспеха: возвращает nullptr;
// -- в случае успеха: возвращает указатель на символ,
// следующий за последним распознанным символом,
// в result записывает значение распознанного литерала.
template <class DigitParser>
const char* parse_digits
(
const char *from,
const char *const to,
DigitParser parse_digit,
unsigned long long &result
)
{
unsigned long long value = 0;
bool last_in_was_digit = false;
for (; from != to; ++from)
{
const auto in = *from;
auto digit = parse_digit(in);
if (digit != -1)
{
last_in_was_digit = true;
value = value * DigitParser::radix + digit;
}
else
{
if (in != '\'')
break;
if (!last_in_was_digit)
return nullptr;
last_in_was_digit = false;
}
}
result = value;
return last_in_was_digit ? from : nullptr;
}
// Автомат-распознаватель целочисленного литерала C++.
// Результат распознавания:
// -- в случае неуспеха: возвращает nullptr;
// -- в случае успеха: возвращает указатель на символ,
// следующий за последним распознанным символом,
// в result записывает тип и значение распознанного литерала.
const char* parse_int(const char *from, const char *const to, Integer &result)
{
if (from == to)
return nullptr;
result.type = Integer::Signed;
// Распознавание значения.
if (*from++ == '0')
{
if (from == to)
{
result.value = 0;
return to;
}
switch (*from++)
{
case 'x': case 'X':
from = parse_digits(from, to, hex_digit, result.value);
break;
case 'b': case 'B':
from = parse_digits(from, to, bin_digit, result.value);
break;
case '\'':
from = parse_digits(from, to, oct_digit, result.value);
break;
default:
// Откат на один символ позволяет уменьшить дублирование кода.
from = parse_digits(from - 1, to, oct_digit, result.value);
}
}
else
{
// Откат на один символ позволяет уменьшить дублирование кода.
from = parse_digits(from - 1, to, dec_digit, result.value);
}
// Обработать результат parse_digits.
if (!from)
return nullptr;
if (from == to)
return to;
// Распознавание суффикса.
// Всего 6 вариантов (без учёта регистра букв): "", "u", "ul", "ull", "l", "ll".
int type = Integer::Signed;
if (*from == 'u' || *from == 'U')
{
++from;
type |= Integer::Unsigned;
}
if (from != to && *from == 'l' || *from == 'L')
{
++from;
type |= Integer::Long;
}
if (from != to && *from == 'l' || *from == 'L')
{
++from;
type = type & ~Integer::Long | Integer::LongLong;
}
result.type = Integer::Integer_type(type);
return from;
}
///////////////////////////////////////////////////////////
// Тестирование
#include <cassert>
#include <cstring>
// Распознать содержимое символьного массива размера N.
bool test_parse_int(const char *in, int chars_parsed, const Integer &ref_result)
{
Integer result;
const auto len = std::strlen(in);
const auto parse_end = parse_int(in, in + len, result);
return
(chars_parsed == 0) == (parse_end == nullptr) &&
(!parse_end ||
parse_end - in == chars_parsed &&
ref_result == result);
}
bool test_parse_int_fail(const char *in)
{
Integer result;
const auto len = std::strlen(in);
return parse_int(in, in + len, result) == nullptr;
}
int main()
{
const auto
SI = Integer::Signed,
SL = Integer::Long,
SLL = Integer::LongLong,
UI = Integer::Unsigned,
UL = Integer::Integer_type(UI | Integer::Long),
ULL = Integer::Integer_type(UI | Integer::LongLong);
const struct
{
const char *in;
int chars_parsed;
Integer ref_result;
} tests[] =
{
{ "100", 3, {100, SI}},
{ "9123 ", 4, {9123, SI}},
{ "0", 1, {0, SI}},
{ "012", 3, {012, SI}},
{ "0123456789ull", 8, {01234567, SI}},
{ "10'000'000+1", 10, {10'000'000, SI}},
{ "0b011'101 1", 9, {0b011'101, SI}},
{ "0B01", 4, {0b01, SI}},
{ "0xFF'FF,", 7, {0xFFFF, SI}},
{ "0XDEADman", 6, {0xDEAD, SI}},
{ "120uU", 4, {120, UI}},
{ "444l ", 4, {444, SL}},
{ "05577uL", 7, {05577, UL}},
{ "0xABF0LL", 8, {0xABF0, SLL}},
{ "99'99ull", 8, {9999, ULL}}
};
for (auto &test : tests)
assert(test_parse_int(test.in, test.chars_parsed, test.ref_result));
const char* const fail_tests[] =
{
"",
"abracadabra",
"0x",
"0b",
"0xxx",
"'0",
"0'",
"100'",
"1''1",
"-100",
"+200",
" 1"
};
for (auto test : fail_tests)
assert(test_parse_int_fail(test));
return 0;
}
// darr_v1.cpp
#include <cstdlib> // size_t
#include <utility> // swap
using std::size_t;
template <class T>
class Darr
{
T *dt; // data
size_t sz; // size
public:
// Деструктор.
~Darr() { delete[] dt; }
// Конструкторы.
explicit
Darr(size_t n = 0)
: dt(n ? new T[n] : nullptr), sz(n) {}
Darr(const T arr[], size_t n)
: Darr(n)
{
for (size_t i = 0; i < n; ++i)
dt[i] = arr[i];
}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other)
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Узнать размер массива.
size_t size() const { return sz; }
// Прямой доступ к хранимому массиву.
T* data() { return dt; }
const T* data() const { return dt; }
// Обращение к элементу по индексу
T& operator[](size_t idx)
{
return dt[idx];
}
const T& operator[](size_t idx) const
{
return dt[idx];
}
};
#include <cassert>
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9);
return 0;
}
// darr_v2.cpp
#include <cstdlib> // size_t
#include <utility> // swap
#include <cassert>
using std::size_t;
template <class T>
class Darr
{
T *dt; // data
size_t sz; // size
public:
// Деструктор.
~Darr() { delete[] dt; }
// Конструкторы.
explicit
Darr(size_t n = 0)
: dt(n ? new T[n] : nullptr), sz(n) {}
Darr(const T arr[], size_t n)
: Darr(n)
{
for (size_t i = 0; i < n; ++i)
dt[i] = arr[i];
}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Перемещающий конструктор (из временного объекта).
Darr(Darr<T> &&other)
: Darr()
{
other.swap(*this);
}
// Перемещающий оператор присваивания.
Darr<T>& operator=(Darr<T> &&other)
{
if (this != &other)
{
swap(other);
other.clear();
}
return *this;
}
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Освободить память.
void clear() { Darr<T> a; *this = a; }
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other)
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Проверить на пустоту.
bool empty() const { return sz == 0; }
// Узнать размер массива.
size_t size() const { return sz; }
// Прямой доступ к хранимому массиву.
T* data() { return dt; }
const T* data() const { return dt; }
// Обращение к элементу по индексу
T& operator[](size_t idx)
{
assert(idx < size());
return dt[idx];
}
const T& operator[](size_t idx) const
{
assert(idx < size());
return dt[idx];
}
};
#include <memory> // std::move
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9 && c.data() != b.data());
auto cdt = c.data();
auto d = std::move(c);
assert(c.empty() && d.data() == cdt && d.size() == 10);
b = std::move(d);
assert(b.data() == cdt && b.size() == 10);
return 0;
}
// darr_v3.cpp
#include <cstdlib> // size_t
#include <utility> // swap
#include <memory> // std::move, std::unique_ptr
#include <cassert>
using std::size_t;
template <class T>
class Darr
{
std::unique_ptr<T[]> dt; // data -- изменено
size_t sz; // size
public:
// Конструкторы.
explicit
Darr(size_t n = 0)
: dt(n ? std::make_unique<T[]>(n) : nullptr), sz(n) {}
Darr(const T arr[], size_t n)
: Darr(n)
{
for (size_t i = 0; i < n; ++i)
dt[i] = arr[i];
}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Перемещающий конструктор (из временного объекта) -- изменено: по умолчанию.
Darr(Darr<T> &&other) = default;
// Перемещающий оператор присваивания -- изменено: по умолчанию.
Darr<T>& operator=(Darr<T> &&other) = default;
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Освободить память -- изменено.
void clear() { dt.reset(); sz = 0; }
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other)
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Проверить на пустоту -- изменено.
bool empty() const { return !dt; }
// Узнать размер массива -- изменено.
size_t size() const { return dt ? sz : 0; }
// Прямой доступ к хранимому массиву -- изменено.
T* data() { return dt.get(); }
const T* data() const { return dt.get(); }
// Обращение к элементу по индексу
T& operator[](size_t idx)
{
assert(idx < size());
return dt[idx];
}
const T& operator[](size_t idx) const
{
assert(idx < size());
return dt[idx];
}
};
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9 && c.data() != b.data());
auto cdt = c.data();
auto d = std::move(c);
assert(c.empty() && d.data() == cdt && d.size() == 10);
b = std::move(d);
assert(b.data() == cdt && b.size() == 10);
return 0;
}
// darr_v4.cpp
#include <cassert> // assert
#include <cstdlib> // size_t
#include <utility> // swap
#include <memory> // move, unique_ptr
#include <iterator> // reverse_iterator
template <class T>
class Darr
{
public:
// Совместимость со стандартными контейнерами.
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = value_type*;
using const_pointer = const value_type*;
private:
std::unique_ptr<T[]> dt; // data
size_type sz; // size
public:
// Конструкторы.
explicit
Darr(size_type n = 0)
: dt(n ? std::make_unique<T[]>(n) : nullptr), sz(n) {}
Darr(size_type n, const_reference val)
: Darr(n)
{
fill(val);
}
Darr(const_pointer arr, size_type n): Darr(n)
{
const auto dp = data();
for (size_type i = 0; i < n; ++i)
dp[i] = arr[i];
}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Перемещающий конструктор (из временного объекта).
Darr(Darr<T> &&other) = default;
// Перемещающий оператор присваивания.
Darr<T>& operator=(Darr<T> &&other) = default;
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Заполнить весь массив копиями одного значения.
void fill(const_reference val)
{
const auto dp = data();
for (size_type i = 0; i < sz; ++i)
dp[i] = val;
}
// Освободить память.
void clear() { dt.reset(); sz = 0; }
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other)
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Проверить на пустоту -- изменено.
bool empty() const { return !dt; }
// Узнать размер массива -- изменено.
size_type size() const { return dt? sz: 0; }
// Прямой доступ к хранимому массиву -- изменено.
pointer data() { return dt.get(); }
const_pointer data() const { return dt.get(); }
// Обращение к элементу по индексу.
reference operator[](size_type idx)
{
assert(idx < size());
return dt[idx];
}
const_reference operator[](size_type idx) const
{
assert(idx < size());
return dt[idx];
}
// Доступ к первому и последнему элементам.
reference front()
{
assert(!empty());
return *data();
}
const_reference front() const
{
assert(!empty());
return *data();
}
reference back()
{
assert(!empty());
return dt[sz - 1];
}
const_reference back() const
{
assert(!empty());
return dt[sz - 1];
}
// Итераторы.
using iterator = pointer;
using const_iterator = const_pointer;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
iterator begin() { return data(); }
const_iterator begin() const { return data(); }
const_iterator cbegin() const { return begin(); }
iterator end() { return data() + size(); }
const_iterator end() const { return data() + size(); }
const_iterator cend() const { return end(); }
reverse_iterator rbegin() { return{ end() }; }
const_reverse_iterator rbegin() const { return{ end() }; }
const_reverse_iterator crbegin() const { return rbegin(); }
reverse_iterator rend() { return{ begin() }; }
const_reverse_iterator rend() const { return{ begin() }; }
const_reverse_iterator crend() const { return rend(); }
};
// Сравнение на равенство.
template <class T1, class T2>
bool operator==(const Darr<T1> &a, const Darr<T2> &b)
{
const auto sz = a.size();
if (sz != b.size())
return false;
const auto ap = a.data();
const auto bp = b.data();
for (std::size_t i = 0; i < sz; ++i)
if (ap[i] != bp[i])
return false;
return true;
}
// Сравнение на неравенство.
template <class T1, class T2> inline
bool operator!=(const Darr<T1> &a, const Darr<T2> &b)
{
return !(a == b);
}
template <class Int>
Darr<Int> iota(Int n)
{
Darr<Int> result(n);
for (Int i = 0; i < n; ++i)
result[i] = i;
return result;
}
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9 && c.data() != b.data());
auto cdt = c.data();
auto d = std::move(c);
assert(c.empty() && d.data() == cdt && d.size() == 10);
b = std::move(d);
assert(b.data() == cdt && b.size() == 10);
int s = 0;
a = iota(10);
for (int x : a) s += x;
assert(s == 45);
b.fill(1);
for (int x : b) assert(x == 1);
assert(a != b && a == iota(10));
return 0;
}
// darr_v5.cpp
#include <cassert> // assert
#include <cstdlib> // size_t
#include <utility> // swap
#include <memory> // move, unique_ptr
#include <iterator> // reverse_iterator, distance, iterator_traits и forward_iterator_tag
#include <type_traits> // enable_if_t и is_convertible
#include <initializer_list>
template <class T>
class Darr
{
public:
// Совместимость со стандартными контейнерами.
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = value_type*;
using const_pointer = const value_type*;
private:
std::unique_ptr<value_type[]> dt; // data
size_type sz; // size
public:
// Конструкторы.
explicit
Darr(size_type n = 0)
: dt(n ? std::make_unique<value_type[]>(n) : nullptr), sz(n) {}
Darr(size_type n, const_reference val): Darr(n)
{
fill(val);
}
Darr(const_pointer arr, size_type n) : Darr(n)
{
const auto dp = data();
for (size_type i = 0; i < n; ++i)
dp[i] = arr[i];
}
// Инициализировать значениями из диапазона, заданного итераторами
template <class FwdIt>
Darr(FwdIt from, FwdIt to,
std::enable_if_t< // годится только для случая, когда FwdIt является прямым итератором.
std::is_convertible<
typename std::iterator_traits<FwdIt>::iterator_category,
std::forward_iterator_tag>::value, int> = 0)
: Darr(std::distance(from, to))
{
const auto dp = data();
for (size_type i = 0; i < sz; ++i, ++from)
dp[i] = *from;
}
// Инициализировать {}-списком.
explicit
Darr(std::initializer_list<T> il)
: Darr(std::begin(il), std::end(il)) {}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Перемещающий конструктор (из временного объекта).
Darr(Darr<T> &&other) = default;
// Перемещающий оператор присваивания.
Darr<T>& operator=(Darr<T> &&other) = default;
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Присвоить {}-список.
Darr<T>& operator=(std::initializer_list<T> il)
{
return *this = Darr<T>(il);
}
// Заполнить весь массив копиями одного значения.
void fill(const_reference val)
{
const auto dp = data();
for (size_type i = 0; i < sz; ++i)
dp[i] = val;
}
// Переразметить (новый размер и значения).
void resize(size_type n, const_reference val = value_type())
{
if (n != size())
*this = Darr<T>(n, val);
else
fill(val);
}
// Освободить память.
void clear() { dt.reset(); sz = 0; }
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other)
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Проверить на пустоту -- изменено.
bool empty() const { return !dt; }
// Узнать размер массива -- изменено.
size_type size() const { return dt ? sz : 0; }
// Прямой доступ к хранимому массиву -- изменено.
pointer data() { return dt.get(); }
const_pointer data() const { return dt.get(); }
// Обращение к элементу по индексу.
reference operator[](size_type idx)
{
assert(idx < size());
return dt[idx];
}
const_reference operator[](size_type idx) const
{
assert(idx < size());
return dt[idx];
}
// Доступ к первому и последнему элементам.
reference front()
{
assert(!empty());
return *data();
}
const_reference front() const
{
assert(!empty());
return *data();
}
reference back()
{
assert(!empty());
return dt[sz - 1];
}
const_reference back() const
{
assert(!empty());
return dt[sz - 1];
}
// Итераторы.
using iterator = pointer;
using const_iterator = const_pointer;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
iterator begin() { return data(); }
const_iterator begin() const { return data(); }
const_iterator cbegin() const { return begin(); }
iterator end() { return data() + size(); }
const_iterator end() const { return data() + size(); }
const_iterator cend() const { return end(); }
reverse_iterator rbegin() { return{ end() }; }
const_reverse_iterator rbegin() const { return{ end() }; }
const_reverse_iterator crbegin() const { return rbegin(); }
reverse_iterator rend() { return{ begin() }; }
const_reverse_iterator rend() const { return{ begin() }; }
const_reverse_iterator crend() const { return rend(); }
};
// Сравнение на равенство.
template <class T1, class T2>
bool operator==(const Darr<T1> &a, const Darr<T2> &b)
{
const auto sz = a.size();
if (sz != b.size())
return false;
const auto ap = a.data();
const auto bp = b.data();
for (std::size_t i = 0; i < sz; ++i)
if (ap[i] != bp[i])
return false;
return true;
}
// Сравнение на неравенство.
template <class T1, class T2> inline
bool operator!=(const Darr<T1> &a, const Darr<T2> &b)
{
return !(a == b);
}
template <class Int>
Darr<Int> iota(Int n)
{
Darr<Int> result(n);
for (Int i = 0; i < n; ++i)
result[i] = i;
return result;
}
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9 && c.data() != b.data());
auto cdt = c.data();
auto d = std::move(c);
assert(c.empty() && d.data() == cdt && d.size() == 10);
b = std::move(d);
assert(b.data() == cdt && b.size() == 10);
int s = 0;
a = iota(10);
for (int x : a) s += x;
assert(a.size() == 10 && s == 45);
b.fill(1);
for (int x : b) assert(x == 1);
assert(a != b && a == iota(10));
c = { 1, 2, 3, 4 };
s = 0;
for (int x : c) s += x;
assert(c.size() == 4 && s == 10);
b.resize(4);
for (int x : b) assert(x == 0);
assert(b.size() == 4);
return 0;
}
// darr_v6.cpp
#include <cassert> // assert
#include <cstdlib> // size_t
#include <utility> // swap
#include <memory> // move, unique_ptr
#include <iterator> // reverse_iterator, distance, iterator_traits и forward_iterator_tag
#include <type_traits> // enable_if_t и is_convertible
#include <initializer_list>
#include <stdexcept>
#include <algorithm>
template <class T>
class Darr
{
public:
// Совместимость со стандартными контейнерами.
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = const value_type&;
using pointer = value_type*;
using const_pointer = const value_type*;
private:
std::unique_ptr<value_type[]> dt; // data
size_type sz; // size
void check_index(size_type idx)
{
if (sz <= idx)
throw std::out_of_range("Darr: array index out of range");
}
public:
// Конструкторы.
Darr() noexcept: sz(0) {} // Конструктор по умолчанию не бросает исключений.
explicit
Darr(size_type n)
: dt(n ? std::make_unique<value_type[]>(n) : nullptr), sz(n) {}
Darr(size_type n, const_reference val): Darr(n)
{
fill(val);
}
Darr(const_pointer arr, size_type n): Darr(n)
{
std::copy_n(arr, n, data());
}
// Инициализировать значениями из диапазона, заданного итераторами
template <class FwdIt>
Darr(FwdIt from, FwdIt to,
std::enable_if_t< // годится только для случая, когда FwdIt является прямым итератором.
std::is_convertible<
typename std::iterator_traits<FwdIt>::iterator_category,
std::forward_iterator_tag>::value, int> = 0)
: Darr(std::distance(from, to))
{
std::copy_n(from, size(), data());
}
// Инициализировать {}-списком.
explicit
Darr(std::initializer_list<T> il)
: Darr(std::begin(il), std::end(il)) {}
Darr(const Darr<T> &other)
: Darr(other.data(), other.size()) {}
// Перемещающий конструктор (из временного объекта).
Darr(Darr<T> &&other) = default;
// Перемещающий оператор присваивания.
Darr<T>& operator=(Darr<T> &&other) = default;
// Копирующее присваивание.
Darr<T>& operator=(const Darr<T> &other)
{
Darr<T>(other).swap(*this);
return *this;
}
// Присвоить {}-список.
Darr<T>& operator=(std::initializer_list<T> il)
{
return *this = Darr<T>(il);
}
// Заполнить весь массив копиями одного значения.
void fill(const_reference val)
{
std::fill_n(data(), size(), val);
}
// Переразметить (новый размер и значения).
void resize(size_type n, const_reference val = value_type())
{
if (n != size())
*this = Darr<T>(n, val);
else
fill(val);
}
// Освободить память.
void clear() { dt.reset(); sz = 0; }
// Обменять содержимое двух объектов Darr.
void swap(Darr<T> &other) noexcept
{
using std::swap;
swap(dt, other.dt);
swap(sz, other.sz);
}
// Проверить на пустоту -- изменено.
bool empty() const noexcept { return !dt; }
// Узнать размер массива -- изменено.
size_type size() const noexcept { return dt ? sz : 0; }
// Прямой доступ к хранимому массиву -- изменено.
pointer data() noexcept { return dt.get(); }
const_pointer data() const noexcept { return dt.get(); }
// Обращение к элементу по индексу.
reference operator[](size_type idx) noexcept
{
assert(idx < size());
return dt[idx];
}
const_reference operator[](size_type idx) const noexcept
{
assert(idx < size());
return dt[idx];
}
// Обращение к элементу по индексу с проверкой индекса.
reference at(size_type idx)
{
check_index(idx);
return dt[idx];
}
const_reference at(size_type idx) const
{
check_index(idx);
return dt[idx];
}
// Доступ к первому и последнему элементам.
reference front() noexcept
{
assert(!empty());
return *data();
}
const_reference front() const noexcept
{
assert(!empty());
return *data();
}
reference back() noexcept
{
assert(!empty());
return dt[sz - 1];
}
const_reference back() const noexcept
{
assert(!empty());
return dt[sz - 1];
}
// Итераторы.
using iterator = pointer;
using const_iterator = const_pointer;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
iterator begin() noexcept { return data(); }
const_iterator begin() const noexcept { return data(); }
const_iterator cbegin() const noexcept { return begin(); }
iterator end() noexcept { return data() + size(); }
const_iterator end() const noexcept { return data() + size(); }
const_iterator cend() const noexcept { return end(); }
reverse_iterator rbegin() { return{ end() }; }
const_reverse_iterator rbegin() const { return{ end() }; }
const_reverse_iterator crbegin() const { return rbegin(); }
reverse_iterator rend() { return{ begin() }; }
const_reverse_iterator rend() const { return{ begin() }; }
const_reverse_iterator crend() const { return rend(); }
};
// Сравнение на равенство.
template <class T1, class T2>
bool operator==(const Darr<T1> &a, const Darr<T2> &b)
{
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
// Сравнение на неравенство.
template <class T1, class T2> inline
bool operator!=(const Darr<T1> &a, const Darr<T2> &b)
{
return !(a == b);
}
// Лексикографическое сравнение.
template <class T1, class T2>
bool operator<(const Darr<T1> &a, const Darr<T2> &b)
{
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
template <class T1, class T2> inline
bool operator<=(const Darr<T1> &a, const Darr<T2> &b)
{
return !(b < a);
}
template <class T1, class T2> inline
bool operator>(const Darr<T1> &a, const Darr<T2> &b)
{
return b < a;
}
template <class T1, class T2> inline
bool operator>=(const Darr<T1> &a, const Darr<T2> &b)
{
return !(a < b);
}
template <class Int>
Darr<Int> iota(Int n)
{
Darr<Int> result(n);
for (Int i = 0; i < n; ++i)
result[i] = i;
return result;
}
int main()
{
Darr<int> a(10), b = a, c;
assert(a.size() == 10 && b.size() == 10 && c.size() == 0);
assert(a.data() != b.data());
a[8] = 8;
b[8] = 9;
assert(a[8] == 8 && b[8] == 9);
c = b;
assert(c[8] == 9 && c.data() != b.data());
auto cdt = c.data();
auto d = std::move(c);
assert(c.empty() && d.data() == cdt && d.size() == 10);
b = std::move(d);
assert(b.data() == cdt && b.size() == 10);
a.clear();
assert(a.empty() && a.size() == 0);
int s = 0;
a = iota(10);
for (int x : a) s += x;
assert(a.size() == 10 && s == 45);
b.fill(1);
for (int x : b) assert(x == 1);
assert(a != b && a == iota(10));
c = { 1, 2, 3, 4 };
s = 0;
for (int x : c) s += x;
assert(c.size() == 4 && s == 10 && a < c && a <= c && c > a && c >= a);
b.resize(4);
for (int x : b) assert(x == 0);
assert(b.size() == 4);
return 0;
}
// uptr_stack.cpp
#include <memory>
#include <cassert>
using namespace std;
template <class T>
class Stack
{
struct Link
{
T value;
unique_ptr<Link> next;
Link(const T &value, unique_ptr<Link> &&next)
: value(value), next(move(next)) {}
};
unique_ptr<Link> list;
public:
~Stack()
{
while (!empty())
{
auto deleter = move(list);
list = move(deleter->next);
}
}
Stack() = default;
Stack(Stack&&) = default;
Stack& operator=(Stack&&) = default;
Stack(const Stack &other)
{
auto my_tail = &list; // как бы указатель на указатель
auto other_tail = &other.list; // аналогично, но на const
while (*other_tail)
{
*my_tail = make_unique<Link>((*other_tail)->value, nullptr);
my_tail = &(*my_tail)->next;
other_tail = &(*other_tail)->next;
}
}
Stack& operator=(const Stack &other)
{
return *this = Stack(other);
}
bool empty() const noexcept
{
return !list;
}
T& top()
{
assert(!empty());
return list->value;
}
const T& top() const
{
assert(!empty());
return list->value;
}
void push(const T &value)
{
list = make_unique<Link>(value, move(list));
}
void pop()
{
assert(!empty());
list = move(list->next);
}
};
#include <iostream>
int main()
{
Stack<int> s;
s.push(2);
cout << s.empty() << ' ' << s.top() << endl;
s.pop();
cout << s.empty() << endl;
for (int i = 0; i < 1000'000; ++i)
s.push(i);
auto p = move(s);
cout << s.empty() << endl;
s = p;
for (int i = 0; i < 10; ++i, s.pop())
cout << s.top() << ' ';
cout << endl;
return 0;
}
// sort_blocks.cpp
#include <algorithm>
using namespace std;
template <class RanIt, class Comp, class Bound>
void sort_blocks(RanIt from, RanIt to, Comp comp, Bound bound)
{
while (from != to)
{
const auto next_bound = find_if(from, to, bound);
sort(from, next_bound);
from = find_if_not(next_bound, to, bound);
}
}
// Тестирование
#include <functional>
#include <iterator>
#include <cassert>
int test_sort_blocks()
{
int a[] = { 5, 1, 0, 0, 0, 1, 2, 8, 10, 1, 0, 0, 6, 6, 1, 0 };
int b[] = { 1, 5, 0, 0, 0, 1, 1, 2, 8, 10, 0, 0, 1, 6, 6, 0 };
sort_blocks(begin(a), end(a), less<>{}, [](int x) { return x <= 0; });
return !equal(begin(a), end(a), begin(b), end(b));
}
int main()
{
assert(test_sort_blocks() == 0);
return 0;
}
// contour_simplify.cpp
#include <array>
#include <vector>
#include <algorithm>
/// Вершина -- массив из двух координат.
template <class Coord>
using Vertex = std::array<Coord, 2>;
/// Многоугольник = контур = вектор вершин.
template <class Coord>
using Polygon = std::vector<Vertex<Coord>>;
/// Вспомогательная функция -- возведение в квадрат.
template <class T>
T sqr(T x)
{
return x * x;
}
/// Квадрат расстояния между вершинами.
template <class Coord>
Coord squared_distance(const Vertex<Coord> &a, const Vertex<Coord> &b)
{
return sqr(a[0] - b[0]) + sqr(a[1] - b[1]);
}
/// Функция упрощения контура (удаления подряд идущих близких вершин).
template <class Coord>
void simplify(Polygon<Coord> &polygon, Coord min_len)
{
min_len *= min_len; // сравниваем с квадратом.
// Компаратор вершин:
// возвращает истину, если они ближе друг ко другу, чем на min_len единиц.
const auto near = [=](const Vertex<Coord> &a, const Vertex<Coord> &b)
{
return squared_distance(a, b) <= min_len;
};
// Удалим лишние вершины прямым обходом контура как незамкнутой последовательности.
polygon.erase(
std::unique(polygon.begin(), polygon.end(), near),
polygon.end());
// Удалим вершины с конца, слишком близкие к первой вершине
// (контур всё-таки замкнутая последовательность).
while (3 < polygon.size() && near(polygon.front(), polygon.back()))
polygon.pop_back();
}
// Тестирование
#include <cassert>
int test_polygon_simplify()
{
using V = Vertex<int>;
Polygon<int>
input =
{
V{ -100, -100 },
V{ -105, -100 },
V{ -106, -99 },
V{ +100, -100 },
V{ +100, -100 },
V{ +100, -100 },
V{ +100, +100 },
V{ +101, +101 },
V{ -100, +100 },
V{ -50, 0 },
V{ -100, +100 },
V{ -104, -100 },
V{ -100, -100 }
},
reference =
{
V{ -100, -100 },
V{ -106, -99 },
V{ +100, -100 },
V{ +100, +100 },
V{ -100, +100 },
V{ -50, 0 },
V{ -100, +100 }
};
simplify(input, 5);
return input != reference;
}
int main()
{
assert(test_polygon_simplify() == 0);
return 0;
}
// seq_cluster_avg.cpp
#include <cassert>
#include <iterator>
#include <functional>
#include <algorithm>
#include <numeric>
using namespace std;
template <class FwdIt>
typename iterator_traits<FwdIt>::value_type // в C++14 вместо этого можно написать auto
arithmetic_mean(FwdIt from, FwdIt to)
{
assert(from != to);
return accumulate(next(from), to, *from) / distance(from, to);
}
template <class FwdIt, class OutIt, class NearComp>
OutIt sequence_simplify(FwdIt from, FwdIt to, OutIt out, NearComp near)
{
while (from != to)
{
// Найти начало усредняемой группы.
auto group_begin = adjacent_find(from, to, near);
// Скопировать все элементы от текущего значения from до начала группы в вывод.
out = copy(from, group_begin, out);
// Найти конец усредняемой группы.
auto group_end = group_begin == to? to
: find_if_not(group_begin, to,
bind(near, cref(*group_begin), placeholders::_1));
// Если группа не пуста, записать вместо неё в вывод арифметическое среднее
// составляющих её элементов.
if (group_begin != group_end)
*out++ = arithmetic_mean(group_begin, group_end);
// Переставить текущую позицию from за группу.
from = group_end;
}
return out;
}
// Тестирование
#include <cmath>
int test_sequence_simplify()
{
float a[] = { 12, 21, 22, 25, 25, 31, 33, 35, 37, 45, 45 };
float b[20] = {};
float ref[] = { 12, 23.25f, 33, 37, 45 };
auto b_end = sequence_simplify(begin(a), end(a), begin(b),
[](float a, float b) { return abs(a - b) < 6.f; });
return !equal(begin(ref), end(ref), begin(b), b_end);
}
int main()
{
assert(test_sequence_simplify() == 0);
return 0;
}
// generic_mean.cpp
#include <iterator>
#include <functional>
#include <numeric>
#include <cmath>
namespace implementation
{
// Среднее для любых итераторов.
template <class It, class Init, class Compose, class Finalize, class AnyTag>
auto _mean(It from, It to, Init init, Compose compose, Finalize finalize, AnyTag)
{
uint64_t count = 0;
auto acc = init(from);
for (; from != to; ++count, ++from)
acc = compose(acc, *from);
return finalize(acc, count);
}
// Среднее для итераторов произвольного доступа.
template <class It, class Compose, class Finalize>
auto _mean(It from, It to, Compose compose, Finalize finalize, std::random_access_iterator_tag)
{
const auto start = init(from);
const auto count = to - from;
return count? accumulate(from, to, start, compose) / count: start;
}
// Реализации Init.
template <class It>
using IVT = typename std::iterator_traits<It>::value_type;
const struct Zero_init
{
template <class It>
IVT<It> operator()(It) const { return IVT<It>(0); }
} zero_init;
const struct Unit_init
{
template <class It>
IVT<It> operator()(It) const { return IVT<It>(1); }
} unit_init;
}
// Обобщённое среднее.
template <class It, class Init, class Compose, class Finalize>
auto mean(It from, It to, Init init, Compose compose, Finalize finalize)
{
typename std::iterator_traits<It>::iterator_category tag;
return implementation::_mean(from, to, init, compose, finalize, tag);
}
// Арифметическое среднее.
template <class It>
auto arithmetic_mean(It from, It to)
{
return mean(from, to, implementation::zero_init, std::plus<>{},
[](auto &&val, auto count) { return val / count; });
}
// Геометрическое среднее.
template <class It>
auto geometric_mean(It from, It to)
{
return mean(from, to, implementation::unit_init, std::multiplies<>{},
[](auto &&val, auto count) { using std::pow; return pow(val, 1. / count); });
}
// Гармоническое среднее.
template <class It>
auto harmonic_mean(It from, It to)
{
using IVT = implementation::IVT<It>;
return mean(from, to, implementation::zero_init,
[](auto a, auto b) { return a + IVT(1) / b; },
[](auto &&val, auto count) { return count / val; });
}
// Тестирование
int test_generic_mean()
{
using namespace std;
float a[] = { 1, 2, 3, 4, 5, 9 };
if (arithmetic_mean(begin(a), end(a)) != 4.f)
return 1;
float b[] = { 4, 16, 64, 256 };
if (geometric_mean(begin(b), end(b)) != 32.f)
return 2;
float c[] = { 3, 6, 9, 12 };
if (harmonic_mean(begin(c), end(c)) != 5.76f)
return 3;
return 0;
}
#include <cassert>
int main()
{
assert(test_generic_mean() == 0);
return 0;
}
// stdalg_sorts.cpp
// Примеры реализации классических алгоритмов сортировки
// с помощью стандартных алгоритмов C++.
#include <iterator>
#include <algorithm>
#include <memory>
using namespace std;
// Сортировка выбором минимума.
template <class FwdIt>
void min_select_sort(FwdIt from, FwdIt to)
{
for (; from != to; ++from)
iter_swap(from, min_element(from, to));
}
// Сортировка выбором минимума и максимума.
template <class BidIt>
void minmax_select_sort(BidIt from, BidIt to)
{
while (from != to)
{
const auto last = prev(to);
if (from == last)
return;
const auto ab = minmax_element(from, to);
if (from != ab.second)
{
iter_swap(from, ab.first);
iter_swap(last, ab.second);
}
else
{
iter_swap(last, ab.second);
if (ab.first != last)
iter_swap(from, ab.first);
}
to = last;
++from;
}
}
// Рекурсивная сортировка слияниями с внешним буфером достаточного размера.
// size -- количество элементов в диапазоне [from, to) и размер буфера.
template <class FwdIt, class T, class SizeT>
void merge_sort(FwdIt from, FwdIt to, T *buffer, SizeT size)
{
switch (size)
{
case 0: case 1: return;
case 2: // Случай, когда элементов всего два.
{
const auto other = next(from);
if (*other < *from)
iter_swap(from, other);
}
return;
default:
{
const auto
first_half_size = size / 2,
second_half_size = size - first_half_size;
const auto mid = next(from, first_half_size);
// Сортировка половинок.
merge_sort(from, mid, buffer, first_half_size);
merge_sort(mid, to, buffer, second_half_size);
// Слияние половинок с перемещением в буфер.
const auto buffer_end = merge(
make_move_iterator(from), make_move_iterator(mid),
make_move_iterator(mid), make_move_iterator(to),
buffer);
// Перемещение обратно из буфера объединённой последовательности.
move(buffer, buffer_end, from);
}
}
}
// Сортировка слияниями с автоматическим созданием буфера.
template <class FwdIt>
void merge_sort(FwdIt from, FwdIt to)
{
using value_type = typename
iterator_traits<FwdIt>::value_type;
const auto size = distance(from, to);
auto buffer = make_unique<value_type[]>(size);
merge_sort(from, to, buffer.get(), size);
}
// Рекурсивная сортировка слияниями "на месте".
// size -- количество элементов в диапазоне [from, to).
template <class BidIt, class SizeT>
void inplace_merge_sort(BidIt from, BidIt to, SizeT size)
{
switch (size)
{
case 0: case 1: return;
case 2: // Случай, когда элементов всего два.
{
const auto other = next(from);
if (*other < *from)
iter_swap(from, other);
}
return;
default:
{
const auto
first_half_size = size / 2,
second_half_size = size - first_half_size;
const auto mid = next(from, first_half_size);
// Сортировка половинок.
inplace_merge_sort(from, mid, first_half_size);
inplace_merge_sort(mid, to, second_half_size);
// Слияние половинок на месте.
inplace_merge(from, mid, to);
}
}
}
template <class BidIt>
void inplace_merge_sort(BidIt from, BidIt to)
{
inplace_merge_sort(from, to, distance(from, to));
}
// Рекурсивная быстрая сортировка с выбором первого элемента в качестве опорного.
// (Самый примитивный вариант.)
template <class FwdIt>
void quick_sort(FwdIt from, FwdIt to)
{
if (from == to)
return;
// Запомнить ссылку на начальный элемент.
auto &pivot = *from;
auto from1 = next(from);
if (from1 == to)
return;
// Выполнить разбиение остатка на тех, что меньше, и тех, что не меньше.
auto part = partition(from1, to,
[&](const auto &item) { return item < pivot; });
// Дефектный случай: разделили диапазон на один элемент и все остальные.
if (part == from1)
return quick_sort(from1, to);
// Поставить опорный элемент на соответствующее место.
iter_swap(from, prev(part));
// Отсортировать части разбиения.
quick_sort(from, part);
quick_sort(part, to);
}
// Пирамидальная сортировка.
template <class RanIt>
void heap_sort(RanIt from, RanIt to)
{
make_heap(from, to);
sort_heap(from, to);
}
/////////////////////////////////////////////////////
// Тестирование
#include <random>
#include <vector>
#include <iostream>
int test_sorts()
{
using namespace std;
vector<int> data(200'000);
mt19937_64 rng(4512105);
uniform_int_distribution<int> ud;
for (int &x : data)
x = ud(rng);
data[0] = -1;
data[100] = -1;
data[100'000] = -1;
data[199'000] = -1;
auto ref = data;
sort(begin(ref), end(ref));
using VI = vector<int>::iterator;
using Sort = void(*)(VI, VI);
Sort sorts[] =
{
min_select_sort<VI>,
minmax_select_sort<VI>,
merge_sort<VI>,
inplace_merge_sort<VI>,
quick_sort<VI>,
heap_sort<VI>
};
int index = 1;
for (auto s : sorts)
{
auto check = data;
s(begin(check), end(check));
if (check != ref)
return index;
++index;
}
return 0;
}
int main()
{
std::cout << test_sorts() << std::endl;
return 0;
}
// int_mults.cpp
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
/// Итератор, реализующий представление промежутков ряда целых чисел.
template <class Int = int>
class Int_iterator
{
Int val;
public:
using value_type = Int;
using reference = const value_type&;
using pointer = const value_type*;
using difference_type = Int;
using iterator_category = std::random_access_iterator_tag;
explicit Int_iterator(Int val = 0)
: val(val) {}
reference operator*() const { return val; }
pointer operator->() const { return &val; }
Int_iterator& operator++()
{
++val;
return *this;
}
Int_iterator operator++(int)
{
auto old = *this;
++(*this);
return old;
}
Int_iterator& operator--()
{
--val;
return *this;
}
Int_iterator operator--(int)
{
auto old = *this;
--(*this);
return old;
}
Int_iterator& operator+=(difference_type delta)
{
val += delta;
return *this;
}
Int_iterator& operator-=(difference_type delta)
{
val -= delta;
return *this;
}
Int_iterator operator-(difference_type delta) const
{
return Int_iterator<Int>(val - delta);
}
difference_type operator-(Int_iterator rhs) const
{
return val - rhs.val;
}
};
template <class Int>
bool operator==(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a == *b;
}
template <class Int>
bool operator!=(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a != *b;
}
template <class Int>
bool operator<(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a < *b;
}
template <class Int>
bool operator<=(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a <= *b;
}
template <class Int>
bool operator>(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a > *b;
}
template <class Int>
bool operator>=(Int_iterator<Int> a, Int_iterator<Int> b)
{
return *a >= *b;
}
template <class Int>
Int_iterator<Int> operator+(Int_iterator<Int> a, Int delta)
{
return a += delta;
}
template <class Int>
Int_iterator<Int> operator+(Int delta, Int_iterator<Int> a)
{
return a + delta;
}
template <class Int>
Int_iterator<Int> int_iterator(Int n)
{
return Int_iterator<Int>(n);
}
/// Вывод последовательности n, n+1, n+2, ..., m в последовательность по итератору out.
template <class Int, class OutIt>
OutIt count_up(Int n, Int m, OutIt out)
{
return std::copy(
int_iterator(n), int_iterator(m + 1), out);
}
/// Вывод последовательности квадратов натуральных чисел от 1 до n
/// в последовательность по итератору out.
template <class Int, class OutIt>
OutIt squares(Int n, OutIt out)
{
return std::transform(
int_iterator(1), int_iterator(n + 1),
int_iterator(1),
out, std::multiplies<Int>());
}
/// Вывод 1!, 2!, ..., n! в последовательность по итератору out.
template <class Int, class OutIt>
OutIt factorials(Int n, OutIt out)
{
return std::partial_sum(
int_iterator(1), int_iterator(n + 1),
out, std::multiplies<Int>());
}
/// Сумма квадратов натуральных чисел от 1 до n.
template <class Int>
Int squares_sum(Int n)
{
const Int zero = 0, one = 1, end = n + 1;
return std::inner_product(
int_iterator(one), int_iterator(end),
int_iterator(one), zero);
}
/// Записать произведения a*1, a*2, ..., a*n в последовательность по итератору out.
template <class Int, class OutIt>
OutIt mult_seq(Int a, Int n, OutIt out)
{
return std::transform(
int_iterator(1), int_iterator(n + 1),
out, std::bind(std::multiplies<Int>(), a, std::placeholders::_1));
}
/// Применить mult_seq для a=1, ..., n, записывая результаты
/// в последовательность контейнеров по итератору out.
template <class Int, class OutIt>
OutIt mult_table(Int n, OutIt out)
{
std::for_each(
int_iterator(1), int_iterator(n + 1),
[n, &out](Int a)
{
mult_seq(a, n, std::back_inserter(*out++));
});
return out;
}
///// Проверить, делится ли m на n.
//template <class Int>
//class Is_divisible
//{
// Int m;
//
//public:
// explicit Is_divisible(Int m)
// : m(m) {}
//
// bool operator()(Int n) const
// {
// return m % n == 0;
// }
//};
//
//template <class Int>
//Is_divisible<Int> is_divisible(Int m)
//{
// return Is_divisible<Int>(m);
//}
/// Вместо закомментированного кода, вариант C++14:
template <class Int>
auto is_divisible(Int m)
{
return [m](Int n) { return m % n == 0; };
}
/// Вывести только те числа из 2, ..., n, на которые делится m.
template <class Int, class OutIt>
OutIt divisors(Int n, Int m, OutIt out)
{
return std::copy_if(
int_iterator(2), int_iterator(n + 1),
out, is_divisible(m));
}
/// Проверить (перебором делителей) простоту числа n.
const struct Is_prime
{
template <class Int>
bool operator()(Int n) const
{
return std::none_of(
int_iterator(2), int_iterator(n / 2 + 1),
is_divisible(n));
}
} is_prime;
/// Вывести простые числа из диапазона 2, ..., n.
template <class Int, class OutIt>
OutIt primes(Int n, OutIt out)
{
return std::copy_if(
int_iterator(2), int_iterator(n + 1),
out, is_prime);
}
#include <iostream>
#include <vector>
int main()
{
using namespace std;
ostream_iterator<int> c_out(cout, "\t");
count_up(3, 10, c_out);
cout << '\n';
squares(10, c_out);
cout << '\n';
factorials(10, c_out);
cout << '\n';
mult_seq(2, 10, c_out);
cout << '\n';
cout << squares_sum(2) << ' ' << squares_sum(10) << "\n\n";
vector<vector<int>> table(9);
mult_table(9, begin(table));
for (auto &row : table)
{
copy(begin(row), end(row), c_out);
cout << '\n';
}
cout << '\n';
divisors(100, 100, c_out);
cout << '\n';
cout << '\n';
primes(1000, c_out);
cout << '\n';
return 0;
}
// ageo2d.hpp
// Точки и вектора на плоскости, элементарные определения.
// Версия 2: при использовании C++14 (MSVC2015) во многих местах можно было бы записать возвращаемый тип auto.
#include <type_traits>
#ifndef AGEO2D_HPP_INCLUDED_
#define AGEO2D_HPP_INCLUDED_
///////////////////////////////////////////////////////////////////////////////
// Вектора
/// Двумерный вектор.
template <class X = double>
struct Vector_2
{
using Coordinate = X;
Coordinate x, y;
/// Конструктор по умолчанию -- нулевой вектор.
Vector_2()
: x(Coordinate()), y(Coordinate()) {}
/// Создать вектор с заданными координатами.
Vector_2(Coordinate x, Coordinate y)
: x(x), y(y) {}
/// Добавить другой вектор "на месте".
Vector_2& operator+=(const Vector_2 &other)
{
x += other.x;
y += other.y;
return *this;
}
/// Вычесть другой вектор "на месте".
Vector_2& operator-=(const Vector_2 &other)
{
x -= other.x;
y -= other.y;
return *this;
}
/// Домножить на скаляр "на месте".
Vector_2& operator*=(Coordinate factor)
{
x *= factor;
y *= factor;
return *this;
}
};
/// Определить тип координаты вектора для двух типов чисел, из которых она вычисляется.
template <class X, class Y>
using Coordinate_of = typename std::common_type<X, Y>::type;
/// Определить тип вектора для разнотипных координат.
template <class X, class Y>
using Vector_2_of = Vector_2<Coordinate_of<X, Y>>;
/// Создать вектор из разнотипных координат.
/// Вспомогательная функция для удобства записи.
template <class X, class Y> inline
Vector_2_of<X, Y> make_vector(X x, Y y)
{
return Vector_2_of<X, Y>(x, y);
}
/// Проверка пары векторов на равенство.
template <class Coordinate1, class Coordinate2> inline
bool operator==(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return a.x == b.x && a.y == b.y;
}
/// Проверка пары векторов на неравенство.
template <class Coordinate1, class Coordinate2> inline
bool operator!=(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return !(a == b);
}
/// Сумма векторов: операция "+".
template <class Coordinate1, class Coordinate2> inline
Vector_2_of<Coordinate1, Coordinate2>
operator+(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return make_vector(a.x + b.x, a.y + b.y);
}
/// Разность векторов: операция "-".
template <class Coordinate1, class Coordinate2> inline
Vector_2_of<Coordinate1, Coordinate2>
operator-(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return make_vector(a.x - b.x, a.y - b.y);
}
/// Унарный минус.
template <class Coordinate> inline
Vector_2<Coordinate> operator-(const Vector_2<Coordinate> &a)
{
return make_vector(-a.x, -a.y);
}
/// Умножение вектора на скаляр слева: операция "*".
template <class Coordinate1, class Coordinate2> inline
Vector_2_of<Coordinate1, Coordinate2>
operator*(Coordinate1 factor, const Vector_2<Coordinate2> &vec)
{
return make_vector(factor * vec.x, factor * vec.y);
}
/// Умножение вектора на скаляр справа: операция "*".
template <class Coordinate1, class Coordinate2> inline
Vector_2_of<Coordinate1, Coordinate2>
operator*(const Vector_2<Coordinate1> &vec, Coordinate2 factor)
{
return factor * vec; // то же, что и слева
}
/// Скалярное произведение векторов.
template <class Coordinate1, class Coordinate2> inline
Coordinate_of<Coordinate1, Coordinate2>
dotp(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return a.x * b.x + a.y * b.y;
}
/// Псевдоскалярное произведение векторов.
/// Равно произведению длин векторов на синус угла между ними.
template <class Coordinate1, class Coordinate2> inline
Coordinate_of<Coordinate1, Coordinate2>
crossp(const Vector_2<Coordinate1> &a, const Vector_2<Coordinate2> &b)
{
return a.x * b.y - a.y * b.x;
}
///////////////////////////////////////////////////////////////////////////////
// Точки
/// Точка на плоскости.
template <class X = double>
struct Point_2
{
using Coordinate = X;
Coordinate x, y;
/// Конструктор по умолчанию -- начало координат.
Point_2()
: x(Coordinate()), y(Coordinate()) {}
/// Создать точку с заданными координатами.
Point_2(Coordinate x, Coordinate y)
: x(x), y(y) {}
/// Радиус-вектор точки.
Vector_2<Coordinate> radius() const
{
return make_vector(x, y);
}
/// Сместить эту точку на заданный вектор.
template <class Y>
Point_2& operator+=(const Vector_2<Y> &delta)
{
x += delta.x;
y += delta.y;
return *this;
}
/// Сместить эту точку на -delta.
template <class Y>
Point_2& operator-=(const Vector_2<Y> &delta)
{
x -= delta.x;
y -= delta.y;
return *this;
}
};
/// Определить тип точки для разнотипных координат.
template <class X, class Y>
using Point_2_of = Point_2<Coordinate_of<X, Y>>;
/// Создать точку из разнотипных координат.
/// Вспомогательная функция для удобства записи.
template <class X, class Y> inline
Point_2_of<X, Y> make_point(X x, Y y)
{
return Point_2_of<X, Y>(x, y);
}
/// Проверка пары точек на равенство.
template <class Coordinate1, class Coordinate2> inline
bool operator==(const Point_2<Coordinate1> &a, const Point_2<Coordinate2> &b)
{
return a.x == b.x && a.y == b.y;
}
/// Проверка пары точек на неравенство.
template <class Coordinate1, class Coordinate2> inline
bool operator!=(const Point_2<Coordinate1> &a, const Point_2<Coordinate2> &b)
{
return !(a == b);
}
/// Разность двух точек даёт вектор.
template <class Coordinate1, class Coordinate2> inline
Vector_2_of<Coordinate1, Coordinate2>
operator-(const Point_2<Coordinate1> &a, const Point_2<Coordinate2> &b)
{
return make_vector(a.x - b.x, a.y - b.y);
}
/// К точке можно добавить вектор, чтобы получить смещённую точку.
template <class Coordinate1, class Coordinate2> inline
Point_2_of<Coordinate1, Coordinate2>
operator+(const Point_2<Coordinate1> &a, const Vector_2<Coordinate2> &delta)
{
return make_point(a.x + delta.x, a.y + delta.y);
}
/// К точке можно добавить вектор, чтобы получить смещённую точку.
template <class Coordinate1, class Coordinate2> inline
Point_2_of<Coordinate1, Coordinate2>
operator+(const Vector_2<Coordinate1> &delta, const Point_2<Coordinate2> &a)
{
return a + delta;
}
/// Из точки можно вычесть вектор, чтобы получить смещённую точку.
template <class Coordinate1, class Coordinate2> inline
Point_2_of<Coordinate1, Coordinate2>
operator-(const Point_2<Coordinate1> &a, const Vector_2<Coordinate2> &delta)
{
return make_point(a.x - delta.x, a.y - delta.y);
}
#endif//AGEO2D_HPP_INCLUDED_
// jarvis.cpp
// Алгоритм Джарвиса ("заворачивания подарка")
// построения выпуклой оболочки множества точек на плоскости.
// Версия 2: шаблоны и стандартные алгоритмы.
#include "ageo2d.hpp" // точки и вектора
#include <cassert>
#include <utility> // swap
#include <cmath> // abs
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
/// Сравнение по x, затем по y (лексикографическое сравнение векторов и точек).
const struct Less_xy
{
template <class P1, class P2>
bool operator()(const P1 &a, const P2 &b) const
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
} less_xy;
/// В диапазоне точек найти самую верхнюю из самых правых.
template <class P2_FwdIt> inline
P2_FwdIt find_highest_rightmost(P2_FwdIt begin, P2_FwdIt end)
{
return std::max_element(begin, end, less_xy);
}
/// Сравнение радиусов-векторов точек по углу относительно заданного начала координат (origin),
/// затем по длине, если вектора коллинеарны.
template <class P>
class Less_angle
{
P origin;
public:
Less_angle() = default;
explicit Less_angle(const P &origin)
: origin(origin) {}
bool operator()(const P &a, const P &b) const
{
const auto
oa = a - origin,
ob = b - origin;
const auto
cp = crossp(oa, ob);
return cp < 0 || (cp == 0 && dotp(oa, oa) < dotp(oa, ob));
}
};
template <class P> inline
Less_angle<P> make_less_angle(const P &origin)
{
return Less_angle<P>(origin);
}
/// В диапазоне точек найти самый дальний поворот по часовой стрелке от точки v.
template <class P2_FwdIt, class P2>
P2_FwdIt max_cw_turn(P2_FwdIt begin, P2_FwdIt end, const P2 &v)
{
return std::max_element(begin, end, make_less_angle(v));
}
/// Алгоритм заворачивания подарка.
/// Переставляет элементы исходного диапазона точек так,
/// чтобы вершины выпуклой оболочки в порядке обхода против часовой стрелки
/// встали в начале диапазона, возвращает указатель на следущую за последней
/// вершиной построенной выпуклой оболочки вершину.
template <class P2_BidIt>
P2_BidIt convex_hull_jarvis(P2_BidIt begin, P2_BidIt end)
{
using std::swap;
using std::prev;
if (begin == end)
return end;
// Найти самую верхнюю из самых правых точек.
// Это -- последняя вершина выпуклой оболочки.
const auto last_point = *find_highest_rightmost(begin, end);
// Удалить все точки, равные last_point, и записать last_point в конец последовательности.
// чтобы корректно выйти из цикла, когда следующая вершина совпадёт с ней.
const auto last_pos = std::remove(begin, end, last_point);
end = std::next(last_pos);
*last_pos = last_point;
// Цикл по вершинам выпуклой оболочки.
for (auto cur = last_pos;;)
{
const auto next = max_cw_turn(begin, end, *cur);
// Поставить следующую вершину.
swap(*begin, *next);
cur = begin++;
if (next == last_pos) // Выпуклая оболочка построена.
return begin;
}
}
///////////////////////////////////////////////////////////////////////////////
// Геометрические операции, применяемые при тестировании
/// Вспомогательное значение для корректной инициализации конечного итератора рёбер.
const struct End_iterator_tag {} end_iterator_tag;
/// Итератор, позволяющий перебрать отрезки (как вектора) ломаной,
/// в действительности проходя по вершинам.
template <class P_FwdIt>
class Edge_iterator
{
P_FwdIt a, b;
public:
Edge_iterator() = default;
explicit Edge_iterator(P_FwdIt a)
: a(a), b(std::next(a)) { init_val(); }
Edge_iterator(P_FwdIt a, P_FwdIt b)
: a(a), b(b) { init_val(); }
Edge_iterator(P_FwdIt end, End_iterator_tag)
: a(end) {}
using iterator_category = std::forward_iterator_tag;
using value_type = Vector_2<
typename std::iterator_traits<P_FwdIt>::value_type::Coordinate>;
using reference = const value_type&;
using pointer = const value_type*;
using difference_type = std::ptrdiff_t;
Edge_iterator& operator++()
{
a = b;
++b;
init_val();
return *this;
}
Edge_iterator operator++(int)
{
auto old = *this;
++(*this);
return old;
}
reference operator*() const { return val; }
pointer operator->() const { return &val; }
bool operator==(const Edge_iterator &other) const
{
return a == other.a;
}
bool operator!=(const Edge_iterator &other) const
{
return !(*this == other);
}
private:
value_type val;
void init_val()
{
val = *b - *a;
}
};
template <class P_FwdIt> inline
Edge_iterator<P_FwdIt> make_edge_iterator(P_FwdIt a)
{
return Edge_iterator<P_FwdIt>(a);
}
template <class P_FwdIt> inline
Edge_iterator<P_FwdIt> make_edge_iterator(P_FwdIt a, P_FwdIt b)
{
return Edge_iterator<P_FwdIt>(a, b);
}
template <class P_FwdIt> inline
Edge_iterator<P_FwdIt> make_edge_iterator_end(P_FwdIt end)
{
return Edge_iterator<P_FwdIt>(end, end_iterator_tag);
}
/// Компаратор "поворот направо" (против ЧС == counterclockwise == ccw).
const struct Is_ccw
{
template <class V1, class V2>
bool operator()(const V1 &a, const V2 &b) const
{
return crossp(a, b) > 0;
}
} is_ccw;
/// Логическое отрицание is_ccw.
const struct Is_not_ccw
{
template <class V1, class V2>
bool operator()(const V1 &a, const V2 &b) const
{
return crossp(a, b) <= 0;
}
} is_not_ccw;
/// Проверка многоугольника на строгую выпуклость.
template <class P2_BidIt>
bool is_strictly_convex(P2_BidIt begin, P2_BidIt end)
{
using std::next;
using std::prev;
if (begin == end)
return true; // пустое множество
const auto begin_1 = next(begin);
if (begin_1 == end)
return true; // одна точка
const auto begin_2 = next(begin_1);
if (begin_2 == end)
return *begin != *begin_1; // невырожденный отрезок?
// Проходя по всем углам (парам смежных рёбер) многоугольника,
// проверять, что поворот происходит строго против ЧС.
const auto end_1 = prev(end), end_2 = prev(end_1);
const auto
edge_begin = make_edge_iterator(begin),
edge_end = make_edge_iterator_end(end_1);
return is_ccw(*end_1 - *end_2, *begin - *end_1)
&& std::adjacent_find(edge_begin, edge_end, is_not_ccw)
== edge_end;
}
/// Положение точки относительно множества.
enum Point_location
{
point_location_inside, // внутри
point_location_boundary, // на границе
point_location_outside // снаружи
};
/// Определить положение точки p относительно многоугольника [begin, end),
/// вершины в котором перечислены в порядке обхода против часовой стрелки.
/// Осторожно: на результат может влиять погрешность вычислений.
/// Используется правило витков (== ненулевого индекса).
/// Алгоритм позаимствован с http://geomalgorithms.com/a03-_inclusion.html
template <class P2_BidIt, class P2, class Tol>
Point_location locate_point
(
P2_BidIt begin, P2_BidIt end, // многоугольник
P2 p, // точка
Tol tolerance // условный допуск на границе
)
{
using std::abs;
using std::prev;
if (begin == end)
return point_location_outside;
int wn = 0; // количество витков
// Проходя по всем рёбрам многоугольника, считать количество витков.
auto pred = *prev(end);
do
{
const auto next = *begin++;
const auto
edge = next - pred,
prad = p - pred;
const auto cp = crossp(prad, edge);
// Ребро пересекает луч снизу-вверх справа от точки p.
if (pred.y <= p.y && p.y < next.y && 0 < cp)
++wn;
// Ребро пересекает луч сверху-вниз справа от точки p.
else if (next.y <= p.y && p.y < pred.y && cp < 0)
--wn;
// Дополнительная проверка: точка лежит на ребре
else if (abs(cp) <= tolerance
&& dotp(prad, prad) <= dotp(prad, edge))
return point_location_boundary;
pred = next;
} while (begin != end);
return wn == 0 ? point_location_outside : point_location_inside;
}
///////////////////////////////////////////////////////////////////////////////
// Тестирование
#include <iostream>
#include <random>
/// Тест на основе заранее известной оболочки.
int test_chj_0()
{
Point_2<> points[] =
{
{ 0, 0 },
{ 10, 0 },
{ 0, 10 },
{ 10, 10 },
{ 0, 1 },
{ 0, 0 },
{ 5, 0 },
{ 5, 5 },
{ 2, 7 }
};
const auto points_sz = sizeof(points) / sizeof(Point_2<>);
const Point_2<> ch[] =
{
{ 0, 10 },
{ 0, 0 },
{ 10, 0 },
{ 10, 10 },
};
const auto ch_sz = sizeof(ch) / sizeof(Point_2<>);
if (convex_hull_jarvis(points, points + points_sz)
- points != ch_sz) // в оболочке должно быть ch_sz вершин
return 1;
if (!std::equal(ch, ch + ch_sz, points))
return 2;
return 0;
}
/// Заполнить диапазон случайными точками с нормальным распределением по каждой координате.
/// Центр в нуле, среднеквадратичное отклонение единица.
std::vector<Point_2<>> make_random_normal(unsigned seed = 1415)
{
using namespace std;
mt19937_64 rng(seed); // генератор псевдослучайных последовательностей бит
uniform_int_distribution<> sz_distr(3, 2000); // равномерное распределение на целых из [3, 2000]
normal_distribution<> coord_distr; // нормальное распределение
std::vector<Point_2<>> pts(sz_distr(rng));
generate(begin(pts), end(pts),
[&]() { return make_point(coord_distr(rng), coord_distr(rng)); });
return pts;
}
/// Проверить алгоритм выпуклой оболочки на заданном наборе точек.
template <class P2_BidIt>
int test_cvj_on(P2_BidIt begin, P2_BidIt end)
{
const auto ch_end = convex_hull_jarvis(begin, end);
if (!is_strictly_convex(begin, ch_end))
return 1;
// Все прочие точки находятся внутри оболочки?
for (auto p = ch_end; p != end; ++p)
if (locate_point(begin, ch_end, *p, 0.) == point_location_outside)
return 2;
return 0;
}
/// Сгенерировать случайный набор точек и проверить на нём алгоритм выпуклой оболочки.
int test_cvj_1(unsigned seed)
{
using namespace std;
// Сгенерировать случайный набор точек.
auto points = make_random_normal(seed);
cout << points.size() << '\t';
// Проверить работу алгоритма на этом наборе точек.
auto result = test_cvj_on(begin(points), end(points));
cout << result << '\n';
return result;
}
#ifdef _DEBUG
#define TEST(x) assert(x)
#else
#define TEST(x) (void)(x)
#endif
int main()
{
using namespace std;
auto test_0 = test_chj_0();
cout << test_0 << endl;
assert(test_0 == 0);
random_device seed_gen; // генератор первого случайного зерна
mt19937 seed_seq(seed_gen()); // генератор зёрен
while (true)
TEST(test_cvj_1(seed_seq()) == 0);
return EXIT_SUCCESS;
}
// triangulation.cpp
// Simplified flat triangulation algorithm.
// No three points may lie on a common line.
// Decent level of compiler C++14-support is assumed (e.g. at least MSVC2015).
#include "ageo2d.hpp"
#include <cassert>
#include <cmath>
#include <initializer_list>
#include <array>
#include <vector>
#include <stdexcept>
class Triangulation_2_exception
: public std::runtime_error
{
public:
using std::runtime_error::runtime_error;
};
/// Checks if p is within triangle(a, b, c) or outside.
/// Warning: if p belongs to the boundary the result may be any.
template <class NT1, class NT2>
inline bool in_triangle(
const Point_2<NT1> &a,
const Point_2<NT1> &b,
const Point_2<NT1> &c,
const Point_2<NT2> &p
)
{
using std::signbit;
const auto
da = signbit(crossp(a - c, b - c));
const auto
ap = a - p,
bp = b - p,
cp = c - p;
return da == signbit(crossp(ap, bp))
&& da == signbit(crossp(cp, ap))
&& da == signbit(crossp(bp, cp));
}
/// Triangulation class implements incremental triangulation algorithm
/// and triangle search tree.
template <class NT = double>
class Triangulation_2
{
public:
using Coordinate = NT;
using Point = Point_2<NT>;
using Vector = Vector_2<NT>;
using Index = std::size_t;
using Triangle = std::array<Index, 3>;
private:
using Points = std::vector<Point>;
using Triangles = std::vector<Triangle>;
Points points;
Triangles triangles;
using Children_desc = std::array<Index, 3>;
using Children = std::vector<Children_desc>;
Children children;
bool is_leaf(Index t) const
{
assert(t < children.size());
return children[t][0] == 0;
}
void triangles_reserve()
{
children.reserve(triangles.capacity());
children.resize(triangles.size(), Children_desc{});
}
bool in_tri(const Point &p, Index t) const
{
using std::signbit;
assert(t < triangles.size());
const auto &tr = triangles[t];
if (tr[0] >= 3) // generic case: three normal points.
return in_triangle(points[tr[0]], points[tr[1]], points[tr[2]], p);
if (tr[1] >= 3) // special case: one infinite point (tr[0]): strip.
{
const auto
s = points[tr[0]].radius();
const auto
p1 = points[tr[1]],
p2 = points[tr[2]];
const auto
d = p2 - p1,
a = p - p1,
b = p - p2;
const auto
da = signbit(crossp(s, d));
return da == signbit(crossp(s, a))
&& da == signbit(crossp(a, d))
&& da == signbit(crossp(b, s));
}
if (tr[2] >= 3) // special case: two infinite points (tr[0] and tr[1]): angle.
{
const auto
a = p - points[tr[2]],
s1 = points[tr[0]].radius(),
s2 = points[tr[1]].radius();
const auto
da = signbit(crossp(s1, s2));
return da == signbit(crossp(s1, a))
&& da == signbit(crossp(a, s2));
}
assert(t == 0);
return true; // infinite triangle.
}
public:
Index points_size() const { return points.size(); }
Index triangles_size() const { return triangles.size(); }
const Point& point(Index i) const
{
assert(i < points.size());
return points[i];
}
const Triangle& triangle(Index i) const
{
assert(i < triangles.size());
return triangles[i];
}
/// @return how many children have been written to ch (3 at max)
Index triangle_children(Index i, Index ch[3]) const
{
assert(i < triangles.size());
if (is_leaf(i))
return 0;
const auto &chi = children[i];
ch[0] = chi[0];
ch[1] = chi[1];
if (chi[2] == chi[1])
return 2;
ch[2] = chi[2];
return 3;
}
/// Find the index of a triangle to which the point p belongs.
/// Throws Triangulation_2_exception in the case of a failure.
/// @return index of the triangle found
Index locate(const Point &p) const
{
for (Index node = 0;;)
{
if (is_leaf(node))
return node;
Index next_node = 0;
const auto &ch = children[node];
for (int child = 0; child < 3; ++child)
{
if (in_tri(p, ch[child]))
{
next_node = ch[child];
break;
}
}
if (next_node <= node)
throw Triangulation_2_exception(
"Triangulation_2 error: the third point of a common line detected");
node = next_node;
}
}
/// Insert a new point to the triangulation.
/// Adds three new triangles.
/// @return index of the inserted point
Index insert(const Point &p)
{
const Index ti = locate(p);
assert(is_leaf(ti));
const Index pi = points.size();
points.push_back(p);
const auto &tr = triangles[ti];
assert(tr[0] < tr[1] && tr[1] < tr[2]);
triangles.emplace_back(Triangle{ tr[0], tr[1], pi });
triangles.emplace_back(Triangle{ tr[0], tr[2], pi });
triangles.emplace_back(Triangle{ tr[1], tr[2], pi });
triangles_reserve();
const auto ts = triangles.size();
children[ti] = Children_desc{ ts - 3, ts - 2, ts - 1 };
return pi;
}
/// Inserts a range of points.
template <class PointInIt>
void insert(PointInIt from, PointInIt to)
{
// Possible optimization: reserve storage space in advance (distance(from, to) if available).
for (; from != to; ++from)
insert(*from);
}
/////////////////////////////////////////////////////////////////////////////
// Constructors
Triangulation_2(Index reserve = 80)
{
points.reserve(reserve);
triangles.reserve(3*reserve);
points.emplace_back(Coordinate(-1), Coordinate(-1));
points.emplace_back(Coordinate(+1), Coordinate(-1));
points.emplace_back(Coordinate(0), Coordinate(+1));
triangles.emplace_back(Triangle{0, 1, 2});
triangles_reserve();
}
/// Immediately inserts a range of points.
template <class PointInIt>
Triangulation_2(PointInIt from, PointInIt to)
: Triangulation_2()
{
insert(from, to);
}
/// Immediately inserts a list of points.
Triangulation_2(std::initializer_list<Point> pts)
: Triangulation_2(begin(pts), end(pts)) {}
};
/////////////////////////////////////////////////////////////////////
// Simple testing
#include <iostream>
int main()
{
using namespace std;
Triangulation_2<> tr
{
{ 0, 0 },
{ 1, 1 },
{ -2, -1 },
{ 2, -1 },
{ 1, 0 },
{ -1, 2 }
};
// Print the triangulation structure.
cout << "Points:\n";
for (size_t i = 0; i < tr.points_size(); ++i)
{
const auto &p = tr.point(i);
cout << "\t[" << i << "] = (" << p.x << ", " << p.y << ")\n";
}
cout << "Triangles:\n";
for (size_t i = 0, ch[3]; i < tr.triangles_size(); ++i)
{
const auto &t = tr.triangle(i);
cout << "\t[" << i << "] = {" << t[0] << ", " << t[1] << ", " << t[2] << "}";
const auto c = tr.triangle_children(i, ch);
if (c > 0)
{
cout << " -> " << ch[0];
for (size_t i = 1; i < c; ++i)
cout << ", " << ch[i];
}
cout << '\n';
}
return 0;
}
// utf_word_freqs.cpp
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>
#include <unordered_map>
#include "utf8/utf8.h" // UTF8-CPP: http://utfcpp.sourceforge.net/
////////////////////////////////////////////////////////////////////////////////
// Вспомогательные функции
/// Применить отображение к каждому элементу контейнера на месте.
/// @param container контейнер, к элементам которого применяется отображение
/// @param map применяемое отображение (ассоциативный контейнер)
/// @return ссылка на container
template <class Container, class Map>
Container& apply_map(Container &container, const Map &map)
{
for (auto &item: container)
{
auto it = map.find(item);
if (it != map.end())
item = it->second;
}
return container;
}
/// Получить новую строку как результат замены подстроки.
/// @param where исходная строка
/// @param pos позиция начала заменяемой подстроки
/// @param count длина заменяемой подстроки
/// @param on_what строка, на которую производится замена подстроки
/// @return объект новой строки -- результата замены
std::string replace
(
const std::string &where,
std::size_t pos,
std::size_t count,
const std::string &on_what
)
{
std::string result(where);
result.replace(pos, count, on_what);
return result;
}
/// Прочитать всё содержимое файлового потока file в строку.
std::string file_to_string(std::ifstream &file)
{
std::string result;
if (file.is_open())
{
// Определить размер.
// Данный метод формально не является гарантированно кросс-платформенным.
file.seekg(0, std::ios::end);
result.resize(file.tellg());
file.seekg(0, std::ios::beg);
// Прочитать всё содержимое файла "скопом" в result.
file.read(&result[0], result.size());
}
return result;
}
////////////////////////////////////////////////////////////////////////////////
// Определения, связанные с Юникодом
namespace Unicode
{
using std::string;
/// Код символа (номер в таблице Юникод).
using Code = std::uint32_t;
/// Отображение код -> код.
using Code_map = std::unordered_map<Code, Code>;
/// Размер поддерживаемой части таблицы.
const Code CODEPOINT_BOUNDARY = 0xE01F0;
/// Булевская таблица.
using Bools = std::vector<bool>;
/// Описание символа (кодовой позиции).
struct Codepoint_entry
{
Code code; ///< Собственно код (UCS-4 == UTF-32).
char cc[3]; ///< Код категории (две буквы и завершающий нуль).
string category[4]; ///< Полное описание категории (подкатегории).
string name; ///< Название символа в таблице Юникод.
};
/// Таблица описаний символов.
using Codepoint_info = std::vector<Codepoint_entry>;
/// Прочитать описание таблицы символов из потока.
/// См. http://www.unicode.org/notes/tn36/
/// Таблица: http://www.unicode.org/notes/tn36/Categories.txt
/// @param categories поток ввода, читающий из Categories.txt
Codepoint_info read_unicode_info(std::istream &categories)
{
Codepoint_info result;
result.reserve(CODEPOINT_BOUNDARY);
std::istringstream lp; // "парсер" строк таблицы.
Codepoint_entry entry {};
// Обработать файл построчно.
for (string line; std::getline(categories, line);)
{
lp.str(line);
// Прочитать код символа (номер кодовой позиции).
lp >> std::hex >> entry.code;
assert(lp.good());
// Прочитать код категории.
lp >> entry.cc[0] >> entry.cc[1];
// Колонки таблицы разделены символами табуляции.
assert(lp.peek() == '\t');
lp.ignore();
// Прочитать описание категории.
for (auto &cat: entry.category)
std::getline(lp, cat, '\t');
// Всё, что осталось в строчке -- название символа.
assert(lp.good() && lp.peek() != '\t');
std::getline(lp, entry.name);
lp.clear();
result.push_back(entry);
}
return result;
}
/// Создать булевскую таблицу для проверки принадлежности символа заданной категории.
/// @param info заранее прочитанное описание символов Юникод
/// @param cc определяет выбор по коду категории, может содержать один символ (первый)
Bools select_category(const Codepoint_info &info, const char *cc)
{
Bools result(CODEPOINT_BOUNDARY);
for (auto &entry: info)
{
if (entry.code < CODEPOINT_BOUNDARY
&& entry.cc[0] == cc[0]
&& (cc[1] == '\0' || entry.cc[1] == cc[1]))
result[entry.code] = true;
}
return result;
}
/// Построить отображение кодов заглавных букв в коды соответствующих маленьких букв.
/// @param info заранее прочитанное описание символов Юникод
/// @param letter булевская таблица принадлежности символа буквам (для ускорения поиска)
Code_map upper_to_lower_mapping(const Codepoint_info &info, const Bools &letter)
{
// Отображение названий маленьких букв (из которых убрали слово SMALL и заменили его на CAPITAL) в их коды.
// Засчёт подмены названия small является отображением названия заглавной буквы в
// код соответствующей ей маленькой буквы.
std::unordered_map<string, Code> small;
// Найти все маленькие буквы.
for (auto &entry: info)
{
if (entry.code < CODEPOINT_BOUNDARY && letter[entry.code])
{
const auto p = entry.name.find("SMALL");
if (p != string::npos) // действительно маленькая буква.
small.emplace(replace(entry.name, p, 5, "CAPITAL"), entry.code);
}
}
// Найти все заглавные буквы и заполнить result.
Code_map result;
for (auto &entry: info)
{
if (entry.code < CODEPOINT_BOUNDARY && letter[entry.code])
{
const auto p = small.find(entry.name);
if (p != small.end())
result.emplace(entry.code, p->second);
}
}
return result;
}
/// Текст в кодировке UTF-32.
using Utf32 = std::vector<Code>;
}
namespace std
{
template <>
struct hash<Unicode::Utf32>
{
// Combining algorithm based upon 64-bit FNV-1a.
size_t operator()(const Unicode::Utf32 &val) const
{
uint64_t h = 0xCBF29CE484222325ull;
for (auto item: val)
h = (h ^ item) * 0x100000001B3ull;
return h;
}
};
}
namespace Unicode
{
// Две функции, используеющие библиотеку UTF8-CPP.
/// Транскодирование из UTF-8 (в виде string) в UTF-32 (в виде Utf32).
Utf32 unchecked_utf8_to_utf32(const string &input)
{
assert(utf8::is_valid(begin(input), end(input)));
Utf32 result;
result.reserve(input.size());
utf8::unchecked::utf8to32(begin(input), end(input), back_inserter(result));
result.shrink_to_fit();
return result;
}
/// Транскодирование из UTF-32 (в виде Utf32) в UTF-8 (в виде string).
string unchecked_utf32_to_utf8(const Utf32 &input)
{
string result;
result.reserve(input.size());
utf8::unchecked::utf32to8(begin(input), end(input), back_inserter(result));
result.shrink_to_fit();
return result;
}
}
////////////////////////////////////////////////////////////////////////////////
// Программа составления частотного словаря
/// Частотный словарь.
using Word_frequencies = std::unordered_map< Unicode::Utf32, std::uint64_t >;
/// Построить частотный словарь на основе заданного текста.
/// @param text исходный текст в кодировке UTF-32 уже приведённый к одному регистру (только маленькие или только заглавные)
/// @param letter булевская таблица для определения факта принадлежности кода буквам
Word_frequencies count_words
(
const Unicode::Utf32 &text,
const Unicode::Bools &letter
)
{
using namespace Unicode;
// Вспомогательные функции.
const auto is_letter = [&](Code code)
{ return code < CODEPOINT_BOUNDARY && letter[code]; };
const auto next_letter = [&](Utf32::const_iterator from)
{ return find_if(from, end(text), is_letter); };
const auto next_non_letter = [&](Utf32::const_iterator from)
{ return find_if_not(from, end(text), is_letter); };
// Перебрать и посчитать все слова (последовательности букв разделённые небуквами).
Word_frequencies result;
for (auto from = next_letter(begin(text)); from != end(text);)
{
const auto to = next_non_letter(from);
result[Utf32(from, to)]++;
from = next_letter(to);
}
return result;
}
/// Точка входа.
/// Варианты вызова (командная строка):
/// 1. Без параметров: читает из input.txt, пишет в cout.
/// 2. Один параметр: имя файла вместо input.txt.
/// 3. Два параметра: два имени файла (исходный файл и куда сохранить результат).
int main(int argc, char *argv[])
{
using namespace Unicode;
using namespace std;
// Попробуем открыть файл с исходным текстом.
ifstream input;
if (argc == 1) // файл по умолчанию.
input.open("input.txt");
else
input.open(argv[1]);
if (!input.is_open()) // открыть не удалось.
return -1;
// Читаем информацию о символах Юникод из файла Categories.txt.
ifstream categories_desc("Categories.txt");
const auto unicode_info = read_unicode_info(categories_desc);
const auto letter = select_category(unicode_info, "L");
const auto up2lo = upper_to_lower_mapping(unicode_info, letter);
// Читаем исходный файл в строку и транскодируем в UTF-32.
auto text = unchecked_utf8_to_utf32(file_to_string(input));
// Приводим к нижнему регистру и считаем слова.
const auto sf = count_words(apply_map(text, up2lo), letter);
// Сортировка слов по частотам.
vector<pair<uint64_t, string>> fs;
fs.reserve(sf.size());
for (auto &kv : sf) // транскодируем слова обратно в UTF-8.
fs.emplace_back(kv.second, unchecked_utf32_to_utf8(kv.first));
sort(begin(fs), end(fs), greater<>{}); // собственно сортировка.
// Вывод результата.
ofstream output;
if (argc > 2)
output.open(argv[2]);
ostream &out = output.is_open() ? output : cout;
for (auto &kv : fs)
out << kv.second << '\t' << kv.first << '\n';
return 0;
}
Кувшинов Д.Р. © 2016