#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <set>
// стратегия для векторов
struct VectorAccessor
{
using value_type = std::vector<int>;
static size_t getSize(const value_type& cont) { return cont.size(); }
static int getItem(const value_type& cont, size_t idx) { return cont.at(idx); }
static void addItem( value_type& cont, int val) { cont.push_back(val); }
};
// стратегия для строк
struct StringAccessor
{
using value_type = std::string;
static size_t getSize(const value_type& cont)
{
return std::count(cont.begin(), cont.end(), '.') + 1; // количество определяется точками
}
static int getItem(const value_type& cont, size_t idx)
{
auto getPosPoint =[&](size_t idx) -> std::string::size_type // ищем точку с номером idx
{ // условно номер 0 - это начало строки
std::string::size_type pos = 0;
for (size_t i = 0; i < idx; ++i)
pos = cont.find('.', pos + 1);
return pos;
};
auto getPos = [&](size_t idx) // ищем границы целого с номером idx
{
std::string::size_type posL = getPosPoint(idx);
std::string::size_type posR = cont.find('.', posL + 1);
return std::make_tuple(posL, posR);
};
auto [pos1, pos2] = getPos(idx); // получаем границы целого
return std::stoul(cont.substr(pos1 == 0 ? 0 : pos1 + 1, pos2 - pos1)); // получаем целое
}
static void addItem(value_type& cont, int val)
{
cont += (cont.empty() ? "" : ".") + std::to_string(val); // точка впереди не нужна
}
};
// селектор политик
template <typename T> struct Selector;
template <> struct Selector<std::vector<int>> { using ValueType = VectorAccessor; };
template <> struct Selector<std::string> { using ValueType = StringAccessor; };
// это не моё
using Vint = std::vector<int>;
using Bolt = std::vector<Vint>;
using Wood = std::vector<std::string>;
Bolt raw = { {4,6}, {5,2}, {4,7,1}, {3,2,1}, {2,2} };
Wood dirty = { "4.6", "5.2", "4.7.1", "3.2.1", "2.2" };
// а это опять моё
// Сравняльщик. Шаблонной лямбдой больно муторно
template <typename T> struct Sorter
{
using selector = typename Selector<typename T::value_type>::ValueType; // политика
// если длины разные, то меньше тот, кто длинее;
// иначе меньше тот, чей int с наименьшим номером меньше, пока предыдущие int равны
bool operator()(const typename selector::value_type& left,
const typename selector::value_type& right) const
{
bool res = selector::getSize(left) != selector::getSize(right); // сравнить длины
if (res) return selector::getSize(left) > selector::getSize(right); // не равны.
for (size_t i = 0; i < selector::getSize(left); ++i) // иначе сравниваем int
if (selector::getItem(left, i) != selector::getItem(right, i)) // по порядку, пока равны.
return selector::getItem(left, i) < selector::getItem(right, i);// меньший int меньше
return false;
}
};
// получить результат из source
template <typename T>
auto doTest(const T& source)
{
std::multiset<typename T::value_type, Sorter<T>> heap(source.begin(), source.end()); // сортируем
std::set <typename T::value_type, Sorter<T>> product;
using selector_type = decltype(heap)::key_compare::selector; // селектор
// просто копируем source в результат поэлементно, попутно добавляем все подэлементы элемента
// с меньшими длинами
for (const auto& i : heap)
{
size_t j = selector_type::getSize(i); // длина текущего элемента
product.insert(i); // добавить элемент
while (--j != 0) // перебрать подэлементы
{ // конечно выгоднее удалять последний,
decltype(product)::value_type newItem; // чем добавлять все, кроме последнего
// но лень переписывать политики
for (size_t k = 0; k < j; ++k) // добавить все, кроме последнего
selector_type::addItem(newItem, selector_type::getItem(i, k));
product.insert(newItem); // добавить в результат
}
}
return product;
}
// протестировать вектор векторов
void testBold()
{
const auto& product = doTest(raw);
// вывод
for (const auto& i : product)
{
std::cout << '{';
for (const auto& j : i)
std::cout << ' ' << j << ' ';
std::cout << "};";
}
std::cout << std::endl;
}
// протестировать вектор строк
void testWood()
{
const auto& product = doTest(dirty);
// вывод
std::cout << '{';
for (const auto& i : product)
std::cout << ' ' << i << ' ';
std::cout << "};";
std::cout << std::endl;
}
int main()
{
testBold();
testWood();
dirty = {"1.12.1", "2.4.15", "1.11.1", "33.4"}; // и это тоже не моё
testWood();
dirty = {"1.12", "2.4.15", "111.1.1", "3.4", "1.1"}; // ну вы поняли
testWood();
}
