Я никогда не разрабатывал редактор, но как насчет этого:
Я считаю, что можно было бы расширить схему, которая используется для хранения тем текстовых символов, в зависимости, конечно, от деталей вашей реализации(язык, наборы инструментов и т. д.) и ваши требования к производительности и использованию ресурсов.
Вместо того, чтобы использовать отдельную структуру данных для стилей, я бы предпочел иметь ссылку, которая сопровождала бы каждый символ и указывала на массив или списокс соответствующими символами.Символы с одинаковым набором стилей могут указывать на один и тот же массив или список, чтобы их можно было использовать совместно.
Вставка и удаление символов не влияют на сами темы стилей, кроме изменения количества ссылок на них,который может быть обработан с небольшим подсчетом ссылок.
В зависимости от вашего языка программирования вы можете даже сжать вещи немного больше, указав на полпути в список, хотя дополнительная бухгалтерия для этого может фактически сделать его более неэффективным.
Основная проблема сэто предложение использования памяти.В редакторе ASCII, написанном на C, связывание указателя с каждым символом увеличило бы его эффективное использование памяти с 1 байта до 12 байтов в 64-битной системе из-за заполнения выравнивания структуры.
Я бы посмотрел о нарушениитекст в небольшие блоки переменного размера, которые позволят вам эффективно сжимать указатели.Например, 32-символьный блок может выглядеть следующим образом в C:
struct _BLK_ {
unsigned char size;
unsigned int styles;
char content[];
}
Интересная часть - обработка метаданных в переменной части структуры, которая содержит как сохраненный текст, так и любые указатели стиля.Элемент размера будет указывать количество символов.Целое число стилей (следовательно, ограничение в 32 символа) будет рассматриваться как набор из 32 1-битных полей, каждое из которых указывает, имеет ли символ свой собственный указатель стиля или должен ли он использовать тот же стиль, что и предыдущий символ.Таким образом, 32-символьный блок с одним стилем будет иметь только дополнительные издержки на размер символа, маску стилей и один указатель вместе с любыми байтами заполнения.Вставка и удаление символов в небольшой массив, подобный этому, должны быть достаточно быстрыми.
Что касается самого хранилища текста, дерево звучит как хорошая идея.Возможно, двоичное дерево, где каждое значение узла будет суммой дочерних значений, причем конечные узлы в конечном итоге будут указывать на текстовые блоки с размером в качестве значения узла?Значением корневого узла будет общий размер текста, причем каждое поддерево идеально удерживает половину вашего текста.Тем не менее, вам все равно придется его автоматически балансировать, иногда приходится объединять полупустые текстовые блоки.
И если вы пропустили это, я не специалист по деревьям: -)
РЕДАКТИРОВАТЬ:
Очевидно, что я предложил модифицированную версию этой структуры данных:
http://en.wikipedia.org/wiki/Rope_%28computer_science%29
, как указано в этом посте:
Структура данных для текстового редактора
EDIT 2:
Удаление в предложенной структуре данных должно быть относительно быстрым, так как это может привести к сдвигу байтов в массиве инесколько побитовых операций над маской стилей.Вставка почти такая же, если блок не заполнен.Возможно, имеет смысл зарезервировать некоторое пространство (то есть несколько битов в маске стилей) в каждом блоке, чтобы обеспечить возможность будущих вставок непосредственно в блоки без необходимости изменять само дерево для относительно небольших объемов нового текста.
Еще одним преимуществом объединения символов и стилей в блоки, подобные этому, является то, что присущая им локальность данных должна обеспечивать более эффективное использование кэша ЦП, чем другие альтернативы, что в некоторой степени повышает скорость обработки.
Как и любой другойОднако сложная структура данных может потребовать либо профилирования с использованием репрезентативных тестовых примеров, либо адаптивного алгоритма для определения оптимальных параметров его работы (размер блока, любое зарезервированное пространство и т. д.).