- PVSM.RU - https://www.pvsm.ru -
Задача звучит просто – напечатать таблицу. Напечатать так, чтобы она выглядела красиво и, по возможности, не расползалась.
После некоторых раздумий, решено было воспользоваться FOP [1] для генерации PDF. Загвоздка в том, что Apache FOP [2] не поддерживает table-layout:auto
, то есть при построении таблицы необходимо вручную задать ширину столбцов (хорошо еще, что можно задать относительную ширину в процентах). Если же сделать все столбцы одинаковой ширины, таблица будет выглядеть несколько неэлегантно. Выходит, рассчитывать ширину придется вручную.
Основная идея в том, что ширину столбцов необходимо подобрать таким образом, чтобы как можно сильнее сократить число переносов строк внутри ячеек таблицы.
Я решал задачу на С++ с использованием фреймворка Qt, поэтому некоторые отсылки к языку и Qt определенно будут, но в общем-то, я постараюсь избежать кода и описать основную идею решения.
Во-первых, определимся, какие данные потребуются. Текст в каждой ячейке таблицы разобьем на слова, для каждого слова вычислим, сколько места на бумаге оно занимает. Таким образом, для каждой ячейки будем хранить массив длин слов ее текста.
Кроме того, необходимо знать ширину бумаги, причем выраженную в тех же единицах, что и длина слов.
Я использовал QFontMetrics::width [3] для определения длины слов. Таким образом, длина слов получалась в пикселах. Тогда для того, чтобы определить ширину бумаги в пикселах, достаточно перемножить ее ширину в дюймах на DPI экрана, которое можно получить, воспользовавшись функцией QPaintDevice::logicalDpiX [4].
Может оказаться, что ширина бумаги недостаточна для того, чтобы вместить таблицу, даже если сжать столбцы настолько, что в каждой строке будет умещаться всего по одному слову.
Вероятность такого варианта развития событий мала (если Вы не немец и не тестировщик, конечно), поэтому я не стал разрабатывать сколько-нибудь сложный алгоритм обработки такого рода случаев. Просто проверим, что минимальная ширина таблицы, которая определяется как сумма максимальных длин слов в столбцах, меньше размера бумаги.
минимальная ширина таблицы |
определяется суммой длин самых длинных слов в столбцах |
Если таблица не влезает, придется обрезать длинные слова. Поскольку, раз уж слово решили обрезать, то обрезать его можно в любом месте, будем считать эффективную длину таких обрезанных слов равной нулю.
Итак, будем обрезать самое длинное слово в таблице до тех пор, пока таблица не станет вмещаться на бумагу.
На этом подготовку данных можно считать законченной, и можно перейти к алгоритму расчета ширины столбцов.
В начале статьи я определил основную идею решения. Теперь настало время выразить ее более формально. Фактически, необходимо отобразить таблицу на бумаге таким образом, чтобы как можно сильнее сократить площадь таблицы.
Площадь, занимаемую таблицей, можно определить как сумму площадей ее столбцов:
Здесь и – высота и ширина столбца соответственно.
Конечно, это не совсем верно, но такая модель на практике дает вполне удовлетворительный результат.
Распишем, чему равна высота столбца:
где m – число строк таблицы, lh – высота строки текста, p – некоторый коэффициент, описывающий высоту отступов, wc – число переносов строк.
Поскольку на число строк, высоту строки и отступы влиять невозможно, то их можно вынести в отдельный коэффициент A.
А вот количество переносов строк напрямую зависит от ширины столбца. Таким образом, высоту столбца можно переписать в виде:
А задача сводится к минимизации функции
Да-да, я не ошибся, А и B не будут зависеть от k, поскольку B определяется высотой строки, а A, в добавок, размерами отступов и числом строк.
S можно переписать в виде:
Сейчас я сделаю большую грубость. – это идеальная площадь таблицы, когда переносов вообще нет. Но поскольку нас не интересует оптимизация по ширине таблицы, (в итоге все равно растянем таблицу на всю страницу), то заменим , то есть на постоянную. Теперь все просто: для задачи минимизации коэффициенты G и B никакой роли не играют, поэтому их можно благополучно выкинуть и находить минимум функции
Для нахождения минимума функции возьмем за основу метод градиентного спуска [5], но будем спускаться не в направлении градиента, а по той координате, изменение функции (частная производная, помноженная на изменение координаты) по которой имеет наименьшее (оно же наибольшее по модулю) значение.
На самом деле, функция числа переносов в зависимости от ширины столба не отличается особой гладкостью. Это ступенчатая функция, которая терпит разрывы в точках изменения числа переносов. Выглядит это как-то так:
У такой функции явные проблемы с производными, но мы поступим просто: будем рассматривать не саму функцию, а некоторую монотонно-убывающую функцию, которая в точках изменения числа переносов совпадает с правым пределом изначальной функции.
В качестве начальной точки возьмем точку с наименьшими возможными ширинами столбцов.
Для каждого столбца:
Для того, чтобы сформировать эти массивы, используем подготовленные на первом этапе данные о длине слов в каждой ячейке таблицы.
Дополним массивы (их получилось столько же, сколько и столбцов) начальными точками.
В итоге, для столбца
минимальная ширина таблицы |
получим следующую структуру данных:
m0 | wc0 |
11 | 2 |
13 («ширина» и «таблицы» — на одной строке) | 1 |
24 | 0 |
Аналогичные структуры получим и для остальных столбцов.
Теперь запустим итерационный процесс:
Пока сумма ширин столбцов меньше чем ширина страницы:
В заключение, пересчитаем полученные ширины столбцов из абсолютных единиц в проценты. Тем самым, отвяжемся от той метрики шрифта, которую использовали.
В итоге таблица получается именно такой, какой бы я ее сделал при ручном форматировании.
P.S.
Статья не претендует на математическую строгость, зато показывает, где вам может пригодиться немного математики в прикладном программировании.
Автор: Lol4t0
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/25853
Ссылки в тексте:
[1] FOP: http://ru.wikipedia.org/wiki/Formatting_Objects_Processor
[2] Apache FOP: http://xmlgraphics.apache.org/fop/
[3] QFontMetrics::width: http://doc.qt.digia.com/qt/qfontmetrics.html#width
[4] QPaintDevice::logicalDpiX: http://doc.qt.digia.com/qt/qpaintdevice.html#logicalDpiX
[5] градиентного спуска: http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA
[6] Источник: http://habrahabr.ru/post/167507/
Нажмите здесь для печати.