Порой приходится слышать от товарищей, что на собеседовании их просили написать код, который бы обращал строку. И даже в 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"} };
Как видно, для решения требуется что-то, что знает о том, что у Юникода «под капотом». И ответственность за это, как правило, возлагают на библиотеку ICU. Поэтому можно считать эту заметку обзором ICU для тех, кто, как и я, собирается начать ее использовать.
Алгоритм решения проблемы
Для решения задачи нужно проделать следующие шаги:
- декодировать 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();
Перенос подпоследовательностей
После того, как фраза разделена на символы, нужно поменять подпоследовательности местами. Сделать это не совсем просто, так как они могут иметь разную длину. Вариант поместить все в стек, а затем считывать и записывать показался мне неспортивным, и я пришел к решению с двумя очередями: очередь тех, кто хочет записаться в начало (заполняется по мере откусывания символов с конца) и тех, кто хочет записаться в конец (заполняется по мере откусывания символов с начала). Когда количество «откусанных», например, с начала символов не меньше длины ожидающей своего часа подпоследовательности, она освобождает свое место в очереди.
Заключение
На этом мой краткий обзор ICU завершен. Надеюсь, что он был полезен и интересен. Полный исходный код с примерами и тестами можно найти на github.
ссылка на оригинал статьи http://habrahabr.ru/post/222331/
Добавить комментарий