Проблемы с алгоритмами часто сопровождаются проблемами с структурами данных.
Сначала сделаем несколько замечаний:
- абзацы можно обрабатывать независимо
- редактированиепри заданном индексе делает недействительным только текущее слово и те, которые следуют за
- , нет необходимости копировать целые слова, когда их индекса будет достаточно для их извлечения, и только их длина имеет значение для вычисления
Абзац
Я бы начал с введения понятия абзаца, которое определяется введенными пользователем переносами строк.Когда происходит издание, вам нужно найти соответствующий абзац, для которого требуется структура поиска.
«Идеальной» структурой здесь будет дерево Фенвика для небольшого текстового поля, однако это кажетсяизлишество.Мы просто сохраним в каждом абзаце количество отображаемых строк, которые составляют его представление, и вы будете считать с начала.Обратите внимание, что доступ к последней отображаемой строке - это доступ к последнему абзацу.
Таким образом, абзацы сохраняются в виде непрерывной последовательности, в терминах C ++, вполне вероятно, принимают удар косвенного действия (т.е. хранят указатели)чтобы сохранить их перемещение при удалении абзаца в середине.
Каждый абзац будет хранить:
- его содержимое, простейшим из которых будет
std::string для его представления. - его отображение в редактируемой форме (которую нам нужно определить еще)
Каждый абзац будет кэшировать свое отображение, этот кэш абзаца будет аннулирован всякий раз, когда редактирование
Фактический рендеринг будет выполняться только для пары абзацев за раз (и, что лучше, для пары отображаемых строк): видимых.
ОтображаетсяСтрока
Абзац может отображаться как минимум с одной строкой, но максимума нет.Нам нужно хранить «дисплей» в редактируемой форме, то есть форме, подходящей для издания.
Один кусок символов с добавленным \n не подходит.Изменения подразумевают перемещение большого количества символов, и пользователи должны изменять текст, поэтому нам нужно лучше.
Используя длины вместо символов, мы можем на самом деле хранить только 4байт (если строка занимает более 3 ГБ ... Я не гарантирую многого об этом алгоритме).
Моей первой идеей было использование индекса символов, однако в случае редактирования все последующие индексы изменяются,и распространение подвержено ошибкам.Длина смещена, поэтому у нас есть индекс относительно позиции предыдущего слова.Это ставит вопрос о том, что такое слово (или токен).В частности, вы сверните несколько пробелов?Как вы справляетесь с ними?Здесь я предполагаю, что слова отделяются друг от друга одним пробелом.
Для «быстрого» поиска я также сохраню длину всей отображаемой строки.Это позволяет быстро пропустить первые отображаемые строки, когда редактирование выполняется с помощью символа 503. Абзац
Таким образом, отображаемая строка будет состоять из:
- общей длины (уступаетмаксимальная отображаемая длина поля после завершения вычисления)
- последовательность слов (токенов) длина
Эта последовательность должна эффективно редактироваться на обоих концах (поскольку для переноса мыБуду вставлять / вставлять слова на обоих концах в зависимости от того, добавлены или удалены слова редактированияЭто не так важно, если посередине мы не настолько эффективны, потому что в середине редактируется только одна строка за раз.
В C ++, vector или deque должно быть хорошо.Хотя теоретически list будет «идеальным», на практике его плохая локальность памяти и большие накладные расходы памяти сведут на нет его асимптотические гарантии.Строка состоит из нескольких слов, поэтому асимптотическое поведение не имеет значения, а высокие константы имеют значение.
Рендеринг
Для рендеринга выберите буфер уже достаточной длины (подойдет std::string с вызовом reserve).Обычно вы clear и каждый раз переписываете буфер, поэтому выделение памяти не происходит.
Вам не нужно отображать то, что не видно, но нужно знать, сколько строк, чтобы подобратьправильный абзац.
Как только вы получите абзац:
- установите
offset на 0 - для каждой скрытой строки, увеличивайте
offset на еедлина (+ 1 для пробела после него) - слово доступно как подстрока
_content, вы можете использовать метод insert для buffer: buffer.insert(buffer.end(), _content[offset], _content[offset+length])
Сложность заключается в поддержании offset, но именно это делает алгоритм эффективным.
Структуры
struct LineDisplay: private boost::noncopyable
{
Paragraph& _paragraph;
uint32_t _length;
std::vector<uint16_t> _words; // copying around can be done with memmove
};
struct Paragraph:
{
std::string _content;
boost::ptr_vector<LineDisplay> _lines;
};
При такой структуре реализация должна быть простой.и не должен сильно замедляться при увеличении контента.