Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
images
README.markdown
sample_test.go
solution.go
solution_test.go

README.markdown

Piece table

В тази задача ще трябва да имплементирате основната функционалност на един потенциален текстови редактор. Той трябва да може да работи с подадено съдържание на въображаем файл, да предоставя неговото съдържание, да позволява редактиране, undo и redo.

Една от популярните структури за имплементиране на тази функционалност е piece table (на места можете да я срещтнете и като piece chain).

За имплементацията на таблицата, са ни нужни два буфера:

  • Първият (file buffer) съдържа целият зареден файл, преди всякакви редакции. Той никога не търпи промени в процеса на работа (read-only). В рамките на тази задача ще го наричаме "origin".

  • Вторият буфер съдържа само добавеното съдържание във файла. Съдържанието на този буфер може само да расте, веднъж добавени данни там, те не търпят изтриване в процеса на работа (append-only). В рамките на тази задача ще го наричаме "add".

Таблицата съдържа "парчета", които описват част от съдържание във файла, въз основа на това, в кой буфер се намират. Едно парче можем да представим със следната структура:

struct {
	origin bool
	offset int
	length int
}
  • origin указва дали съдържанието, към което сочи се намира в origin буфера.

  • offset указва от кой байт в горепосочения буфер започва съдържанието на това парче.

  • length указва дължината на въпросното съдържание.

При първоначалното отваряне на даден файл целият файл се описва от едно парче, което е единственият запис в таблицата.

Пример:

Отваряме файл със съдържание A large span of text. Origin буферът изглежда така:

origin

Add буферът е празен, а таблицата с парчета изглежда така:

table0

Потребителят решава да добави думата "English" преди последната дума, за да получи файл със съдържание: A large span of English text. Добавяме в add буфера English :

add

Обърнете внимание, че размерът на add буфера е по-голям от необходимото. Това е допустимо, но не задължително. Таблицата ни вече изглежда така:

table1

Въображаемият ни потребител решава да изтрие думата large. Това не води до никакви промени в нашите буфери, тъй като нищо никога не се трие от тях. Таблицата се променя до:

table2

Задача

Задачата ви е да създадете тип, който имплементира следния интерфейс:

type Editor interface {
	// Insert text starting from given position.
	Insert(position uint, text string) Editor

	// Delete length items from offset.
	Delete(offset, length uint) Editor

	// Undo reverts latest change.
	Undo() Editor

	// Redo re-applies latest undone change.
	Redo() Editor

	// String returns complete representation of what a file looks
	// like after all manipulations.
	String() string
}

Също така се очаква и да добавите функция, която създава стойност на вашия тип, от подаден origin буфер.

func NewEditor(string) Editor

Пример

Горният пример би трябвало да може да бъде пресъздаден с помощта на вашата имплементация по този начин:

var f = NewEditor("A large span of text")
f.String() // "A large span of text"

f = f.Insert(16, "English ")
f.String() // "A large span of English text"

f = f.Delete(2, 6)
f.String() // "A span of English text"

Забележки/Препоръки:

  • Внимание: когато предавате решение, трябва да включите в него дефиницията на Editor интерфейса, за да успеете да предадете решението си.
  • Обърнете внимание, че никой от методите не връща грешка. Това ще рече, че очакваме да се справяте с твърде големи стойности на position, offset и length:
    • Твърде голяма стойност на position при Insert трябва да се държи като обикновено добавяне на края на файла. NewEditor("foo").Insert(453, ".") трябва да се държи като NewEditor("foo").Insert(3, ".").
    • Твърде голяма стойност на offset при Delete не трябва променя файла. Тази операция не прави нищо: NewEditor("foo").Delete(300, 1)
    • Твърде голяма стойност на length при Delete трябва да стига до края на файла. NewEditor("foo").Delete(1, 300) трябва да се държи като NewEditor("foo").Delete(1, 2).
  • Обърнете внимание на факта, че всеки един от методите връща редактор. Това все пак не означава, че е задължително да създавате нов редактор, който да връщате. Решението дали да го правите, или да мутирате текущия е ваше.
  • add буферът може да расте до безкрайност.
  • Не се фокусирайте да оптимизирате тези алокации особено много. Напълно ок е да решите, че по подразбиране add буферът е X символа и ако се налага просто удвоява размера си.
  • При отваряне на файл add буферът е празен и е напълно в реда на нещата дори да не е алокиран (т.е. да е nil).
  • Вашият тип не трябва да се казва Editor, тъй като вече имате такъв дефиниран интерфейс в sample тестовете. Напълно допустимо е този тип да не бъде exported.
  • Undo преди извършена операция не трябва да прави нищо.
  • Redo преди изпълнено Undo (или след всички възможни Redo-та) не трябва да прави нищо.
  • След Undo всяка редакция се предполага да инвалидира следваща Redo операция.
  • Операциите Insert и Delete очакват position, offset и length в байтове, а не в символи. Обърнете внимание на това при работа с unicode символи.
You can’t perform that action at this time.