Если вы знаете, что такое ICU, то, вероятно, вы не узнаете из этого поста ничего нового.
Порой приходится слышать от товарищей, что на собеседовании их просили написать код, который бы обращал строку. И даже в Cracking the Coding Interview это второй вопрос в тестах. Однако, правильное, с моей точки зрения, решение выходит далеко за рамки библиотечного вызова или одного цикла while.
В случае, когда переданная строка является ASCII-строкой, сработает и самый простой подход. Но все становится интереснее, если на вход может быть передана UTF-8 строка. Проблем тут сразу две: переменная ширина и модифицирующие символы.
Чтобы было понятнее, начну с тестов, которые программа должна проходить (слева — вход, справа — ожидаемый выход):
Порой приходится слышать от товарищей, что на собеседовании их просили написать код, который бы обращал строку. И даже в Cracking the Coding Interview это второй вопрос в тестах. Однако, правильное, с моей точки зрения, решение выходит далеко за рамки библиотечного вызова или одного цикла while.
В случае, когда переданная строка является ASCII-строкой, сработает и самый простой подход. Но все становится интереснее, если на вход может быть передана UTF-8 строка. Проблем тут сразу две: переменная ширина и модифицирующие символы.
Чтобы было понятнее, начну с тестов, которые программа должна проходить (слева — вход, справа — ожидаемый выход):
const char* cases[][2] = {
// тривиальные ascii-случаи
{"", ""},
{"a", "a"},
{"ab", "ba"},
{"a b", "b a"},
// одна русская буква, записанная в UTF-8
{"\xd1\x84", "\xd1\x84"},
// смесь русских и латинских букв
{"x\xd1\x84", "\xd1\x84x"},
{"y\xd1\x84z", "z\xd1\x84y"},
{"\xd1\x84\xd1\x85", "\xd1\x85\xd1\x84"},
// одна русская буква, записанная в декомпозированной форме
{"\xd0\x98\xcc\x86", "\xd0\x98\xcc\x86"},
// смесь русских декомпозированных и латинских букв
{"i\xd0\x98\xcc\x86", "\xd0\x98\xcc\x86i"},
{"\xd0\x98\xcc\x86i", "i\xd0\x98\xcc\x86"},
{"\xd0\x98\xcc\x86\xd1\x84", "\xd1\x84\xd0\x98\xcc\x86"},
// забавы ради: zЙ̈y
{"z\xd0\x98\xcc\x86\xcc\x88y", "y\xd0\x98\xcc\x86\xcc\x88z"}
};
Алгоритм решения проблемы
Для решения задачи нужно проделать следующие шаги:- декодировать UTF-8 строку в структуру, не зависящую от кодировки,
- разделить эту структуру на подпоследовательности так, чтобы все непротяженные символы и только они оказались в одной подпоследовательности со своим базовым,
- переставить подпоследовательности местами,
- сконвертировать обратно в UTF-8.
Считывание данных
Класс icu::UnicodeString представляет собой абстракцию над представлением данных в памяти, позволяя просто работать с данными, как с последовательностью Unicode-символов. Имеет множество методов для декодирования и кодирования, в частности, мне понадобятся такие:// Decoding
icu::UnicodeString s = icu::UnicodeString::fromUTF8(cases[test_case][0]);
// Encoding
std::string result;
s.toUTF8String(result);
Разделение на символы
Класс icu::BreakIterator позволяет получить координаты начала следующего/предыдушего протяженного_символа/слова/предложения в UnicodeString (именно так текст разбивается на слова при поиске по странице в браузере Chromium и его производных). Надо отметить, что для правильной работы итератор должен знать язык текста.// Initialize iterator
UErrorCode ec = U_ZERO_ERROR;
icu::Locale ru_locale = icu::Locale("ru");
std::unique_ptr<icu::BreakIterator> iter;
iter.reset(icu::BreakIterator::createCharacterInstance(ru_locale, ec));
iter->setText(my_unicode_string);
// Set it to the beginning of my_unicode_string and get next character's position
iter->first();
int32_t next_char = iter->next();
// Or set it to the after-last-character position and get previous character position
iter->last();
int32_t this_char = iter->previous();