Обращение не ASCII-строки

Если вы знаете, что такое ICU, то, вероятно, вы не узнаете из этого поста ничего нового.

    Порой приходится слышать от товарищей, что на собеседовании их просили написать код, который бы обращал строку. И даже в Cracking the Coding Interview это второй вопрос в тестах. Однако, правильное, с моей точки зрения, решение выходит далеко за рамки библиотечного вызова или одного цикла while.

    В случае, когда переданная строка является ASCII-строкой сработает и самый простой подход. Но все становится интереснее, если на вход может быть передана UTF-8 строка. Проблем тут сразу две: переменная ширина и модифицирующие символы.
    Чтобы было понятнее, начну с тестов, которые программа должна проходить (слева — вход, справа — ожидаемый выход):

const char* cases[][2] = {
  // тривиальные ascii-случаи
  {"", ""},
  {"a", "a"},
  {"ab", "ba"},
  {"a b", "b a"},

  // одна русская буква, записанная в UTF-8
  {"xd1x84", "xd1x84"},

  // смесь русских и латинских букв
  {"xxd1x84", "xd1x84x"},
  {"yxd1x84z", "zxd1x84y"},
  {"xd1x84xd1x85", "xd1x85xd1x84"},

  // одна русская буква, записанная в декомпозированной форме
  {"xd0x98xccx86", "xd0x98xccx86"},

  // смесь русских декомпозированных и латинских букв
  {"ixd0x98xccx86", "xd0x98xccx86i"},
  {"xd0x98xccx86i", "ixd0x98xccx86"},
  {"xd0x98xccx86xd1x84", "xd1x84xd0x98xccx86"},

  // забавы ради: zЙ̈y
  {"zxd0x98xccx86xccx88y", "yxd0x98xccx86xccx88z"}
};

    Как видно, для решения требуется что-то, что знает о том, что у Юникода «под капотом». И ответственность за это, как правило, возлагают на библиотеку ICU. Поэтому можно считать эту заметку обзором ICU для тех, кто, как и я, собирается начать ее использовать.

Алгоритм решения проблемы

    Для решения задачи нужно проделать следующие шаги:

1. декодировать UTF-8 строку в структуру, не зависящую от кодировки,
2. разделить эту структуру на подпоследовательности так, чтобы все непротяженные символы и только они оказались в одной подпоследовательности со своим базовым,
3. переставить подпоследовательности местами,
4. сконвертировать обратно в 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.

Автор: xni

Источник