# How Ze works on the inside

## Terminal viewing

Viewing is done by remembering a file offset for the window.
For example a window viewing 60 lines on file offset 2 would show lines from 2 to 61.
Then we have a cursor, which just represents a row-position and a column-position.
With those two, we can interact with lines, where we have cursor, jump to certain lines and generally move the cursor.

## Overview

Ze represents the file as a *treap*.
A treap is a randomized search tree, which is a binary search tree for its keys and a max-heap for their *priorities*.
Internally, the treap operation do not based on node keys, but the sizes of their subtrees - this applies for the b.s.t. attributes.
Nodes of this treap contain lines from the file.
The treap is *semi-persistent*, which means it remembers all of its versions and can modify the last one.
On a higher level, the editor repeatedly takes user input and does corresponding actions.
Those actions are divided into three modes: *normal*, *insert* and *select*.
It uses `ncurses` c library for handling terminal input/output.

## Treap Semi-persistence

Ze uses a semi-persistence technique of remembering paths from root to a leaf.

The main idea is that whenever an editation step changes the treap, only nodes on such a path are changed.
This means that it is sufficient only to remember those paths.

With this method, the version of the treap is represented by the latest root node.
The root then remembers its son, which is on the change-path and so on.
Roll-back is done simply by following the latest path and erasing nodes it contains.

## Treap meta-operations

The core of all editation steps are three operations: *insert*, *remove* and *update*.
Every other operation can wrap something around these three.

Sometimes that includes using more of them - for that scenario the treap also remembers how many of these meta-operations were used.
Undo is then just erasing as many versions as the editation step used.
As an added bonus, it also remembers the line changed, which makes it possible to jump on the line, where the change occured.

### Insert

For insert, we need two modes - with and without version-change.
That is because of treap build - because of it we can just do as many inserts as there are lines of the loaded file and take it as an initial version.

The new-version-remembering mode works recursivelly - starting with root, it decides whether the left sons subtree has higher or the same size as is the desired index where a new line should be inserted.
If yes, then it calls itself on the left son, otherwise on the right son but with an index, that has the size of the left subtree + 1 subtracted from it.
When it is called on a non-existent node, it creates a new node and returns it.

With each return, a new node is created with the appropriate son pointer and it's remembered as the next node on its version path.
But that alone wouldn't suffice, because the treap also acts as a heap.
Here come node rotations in play.
If a returned node has higher priority than the original node, they are rotated to suit the heap rules.

At last, the treap remembers a new root, representing a new version.

The version-not-remembering mode works almost the same, but not creating new nodes, but instead modifying the treap.

### Remove

Remove doesn't need the option not to remember a new version, but it's a little more complicated.
If we're still chasing the node to remove, we simply follow the path to it, same as with insert.

But when we find the node, then comes the fun.
If any one of the removed nodes sons are non-existent, the removed node is replaced by one that exists, if there is one.
But if both sons are real, we pick the one with higher priority to replace the removed node.
We do this with a handy rotation, which keeps b.s.t. rules, but gets the higher-priority son higher.
Then, when we have the desired son where we want him, we call the remove recursively on the node, we put lower.
Internally, this is done by making a permanent copy of the son and a temporary copy of the removed node, so we can rotate them and not affect the previous versions.

Each return then creates a new node, just as with an insert.

### Update

With the knowledge of insert and delete, update is pretty simple.

We find the desired point to update by following sizes of subtrees just as with the previous two operations.
Then, when we find it, we create a new, identical node with the new text and return that.
Then with each return, we create our trail of breadcrumbs.

## Other editation actions

Everything else, which changes the treap in any way, can be done by using these three meta-operations.

### Select mode and selection

Operations on selected text are generalized by a function called `apply_on_selection()`.
It just takes a function to apply to the lines selected in the file and applies it on them.

It can remove the selected text from the file - that is done with treap removes and updates on the edges.
It can copy the selected text into the selectoin.

The selection is just a vector of lines.
We can paste them into the file afterwards.

### Insert mode

One write on one line should create only one version.
That is accomplished by buffering changes to one line and applying them afterwards.
Other than that, we are just updating specific lines.

### Find and replace

We iterate through the file, finding incremental indexes.
We go through each of these lines and search the desired substring.

Then a find just moves the cursor there.
A replace does an update on this line, changing the substring to something else.