[recovery mode] Алгоритм Ляна-Кнута в реальном проекте, или как я делал читалку для iOS

Всем привет! В этот раз я хочу рассказать, как я реализовывал альтернативу iBooks. В своем предыдущем посте я писал об алгоритме расстановки мягких переносов в тексте. Он как раз и пригодился при создании своей читалки, оценить его работу можно наглядно в приложении. Но помимо этого, при реализации проекта мне пришлось столкнуться с многими другими интересными вещами, такими как парсинг и рендеринг HTML с CSS, реализация элементов управления с кастомным дизайном и т.п. Наш дизайнер rashapasta очень любит подкинуть мне задачек с эдаким нестандартным интерфейсом, который нужно реализовывать ручками, но обо всем по порядку.

UI (или танцы с бубном)

В плане UI в проекте не самой простой задачей было сделать grid таблицу с горизонтальным пейджингом. Как обычно в поисках готовых решений я полез на stackoverflow.com, но увы, все что перебрал было в той или иной степени непригодным.
Были большие надежды на AQGridView, но как оказалось, от горизонтального заполнения и пейджинга там только пустые заглушки. Было решено дать ей второй шанс и применить многим знакомый трюк с поворотом таблицы на 90 градусов. Этот вариант поначалу даже показался работающим и более менее приемлемым, но и тут нашлись свои камни.

Баги в самом AQGridView и в стандартном UIScrollView отбили мне желание использовать этот компонент. В некоторых ситуациях grid постоянно ломался: некоторые ячейки выпадали и постоянно слетал порядок. Чтобы развеять сомнения в своей криворукости, я попробовал воспроизвести проблему на демке из комплекта – баг подтвердился.
Что касается UIScrollView и его производных — тут я тоже сначала грешил на AQGridView, но когда стал использовать UITableView, проблема повторилась. Суть бага в том, что при повернутом через трансформацию UIScrollView отваливался bounce эффект, что было очень некрасиво и неестественно для iOS.

Опытным путем выяснилось, что виноват ресайз и перемещение UIScrollView при поворотах девайса, который делался руками через обработчик layoutSubviews. Взяв свой шаманский бубен, я выяснил, что все ломает позиционирование повернутого UIScrollView через свойство center.

Вся эта долгая история закончилась тем, что пришлось извращаться со старым добрым UITableView. Bounce я починил, и проблема с поворотом решилась. Ячейку таблицы сделал размером в страницу и состоит она из нескольких под-ячеек, каждая из которых реализована в виде экземпляра отдельного класса. Получилось вот так:

Работа с HTML и алгоритм Ляна-Кнута.

С парсингом популярных форматов электронных книг и рендерингом отдельная история. С HTML в принципе не сложно, libxml отлично справился. Файл HTML обрабатывается рекурсивно, разбивается на блоки текста, каждому блоку выставляются соответствующие аттрибуты. Остается загнать все это во framesetter из CoreText и готово. Но не тут то было! Надо сделать переносы и выравнивание по ширине. Пришлось спускаться уровнем ниже и использовать не framesetter, а typesetter. С помощью него можно удобно резать текст на строки, например функцией

CFIndex CTTypesetterSuggestClusterBreak( CTTypesetterRef typesetter, CFIndex startIndex, double width);

В процессе разбиения на строки нужно определять место разрыва. Если разрыв возникает в середине какого-либо слова, то нужно правильно поставить перенос. Вот тут и приходит на помощь реализация указанного выше алгоритма Ляна-Кнута.

Рендер (или не заставляйте пользователя ждать!)

Осталось всего ничего — порезать полученную гору строчек текста на страницы и можно рендерить. Опытным путем выяснилось, что вся эта связка операций по обработке текста перед рендером занимает целую кучу времени. Из профайлера я понял, что виной всему расстановка переносов. Загнал расчет книги в фоновый режим и в отдельный потоке – стало работать шустрее.

Единственный минус — пока идет рендер, нельзя использовать слайдер перемотки. При необходимости перехода на главу, которая еще не обработана, ставим ее первой в очереди обработки, чтобы максимально быстро ее отобразить на экране.

В итоге получилось вроде неплохо, и на iPad книги обрабатываются довольно быстро (учитывая, что это рендер на лету).

Вот как выглядят отрисованные страницы в разных ориентациях экрана:

Для работы по HTTP был как обычно заюзан AFNetworking, очень рекомендую. Правда было одно «но», при анализе приложения на утечки памяти обнаружилась проблема с отображением прогресса загрузки файлов, связанная с циклическими ссылками. В методе setDownloadProgressBlock был блок вроде этого:

if ([self.progressDelegate respondsToSelector:@selector(fileDownloadRequest:progressBytes:withTotalBytes:)])
{
            [self.progressDelegate fileDownloadRequest:self progressBytes:alreadyDownloadedBytes+totalBytesRead withTotalBytes:alreadyDownloadedBytes+totalBytesExpectedToRead];
}

Наличие self в коде блока и вызывало циклическую зависимость. Решается это путем создания отдельной локальной переменной, в которую копируется указатель на делегат, и уже эта переменная используется в блоке. Стало вот так:

id<FileDownloadProgressDelegate> progress = self.progressDelegate;
    [self.request setDownloadProgressBlock:^(NSInteger bytesRead, NSInteger totalBytesRead, NSInteger totalBytesExpectedToRead) {
        if ([progress respondsToSelector:@selector(fileDownloadRequest:progressBytes:withTotalBytes:)])
        {
                [progress fileDownloadRequest:self progressBytes:alreadyDownloadedBytes+totalBytesRead withTotalBytes:alreadyDownloadedBytes+totalBytesExpectedToRead];
        }
}];

В дальнейшем, по мере наличия свободного времени, я продолжу описывать свой опыт разработки под iOS, а пока приглашаю обсудить результат моих трудов в комментах.

Автор: s0L