Вопрос, с которым я столкнулся, касается реализации структуры данных Gap Buffer .В частности, я говорю о структуре данных, которая по сути представляет собой LinkedList, где каждый узел представляет собой (довольно маленький) массив символов.Это идеально подходит для редактирования текста, потому что вы можете вставлять больше символов в любой точке, выделяя новые массивы, если нет места, куда вы смотрите.
Внедрение самого Gap Buffer не представляет особой проблемы, так как выглядит в точности какLinkedList и методы реализации, такие как Add и Remove, являются алгоритмически простыми.Просто вставьте новый символ в узел, соответствующий позиции, если есть место, и выделите новый узел, если требуется больше места.
Самым сложным вопросом была эффективная реализация метода Trim с постусловием.что при запуске Trim все непробельные элементы в буфере разрыва будут «сжаты» по направлению к началу, то есть все элементы перемещаются как можно дальше вперед, а пробелы сокращаются.
Наивный метод состоит в том, чтобы просто перебирать каждый элемент массива один за другим, перемещая его в следующее свободное пространство до тех пор, пока все элементы не будут повторены, и затем удаляя все пустые узлы в конце списка.Однако это не идеально:
Если во время итерации мы приближаемся к пустому массиву, мы должны немедленно удалить этот массив из списка, объединив вокруг него 2 массива.С другой стороны, если мы приближаемся к массиву, который полностью заполнен, мы должны пропустить массив, так как он уже уплотнен.
Являются ли эти два случая единственными случаями, которые нам нужно рассмотреть, когда речь идет об эффективности?Есть ли другие потенциальные улучшения?И как будет выглядеть полностью эффективный Trim алгоритмически?