Live editing about yocto HOT 3 CLOSED

check out the ncurses branch to follow the development
EDIT: it is now the default branch

from yocto.

Problem with modifying text:
New chars need to be inserted into the text at any position without overwriting the previous char which was there (all other char move to the right).

To do this with O(1) complexity, a linked list is needed, however in a linked list we cannot say: list[5], the whole line needs to be traversed, O(n). However, this is not a concern in this case since elements are always accessed sequentially.

In the current implementation, which is a 2d array, we can only insert in O(n), which is much, much worse. However, the typical line of a text does not exceed 100 characters, so it not that inefficient to shift ~100 chars after the inserted one forward. In addition, we can access any position of the array in O(1).

Insert function code for both implementations:

Array

char* insertX(int n, char arr[],
              char x, int pos)
{
    int i;
 
    // increase the size by 1
    n++;
 
    // shift elements forward
    for (i = n; i >= pos; i--)
        arr[i] = arr[i - 1];
 
    // insert x at pos
    arr[pos - 1] = x;
 
    return arr;
}

Linked list (not tested)

typedef struct line {
    char ch;
    struct node *next;
} line_t;

line_t *insertX(line_t *graph, char x, int pos)
{
    int i = 0;
    // to be inserted
    line_t *p;
    p = (line_t*)malloc(sizeof(line_t));
    p->ch = x;
    p->next = NULL;

    if (graph == NULL) {
        graph = p;
    } else {
        while (tmp->next != NULL) {
            tmp = tmp->next; //go forward
            i++;
            // ONLY this (below) part does the insertion
            if (i == pos) {
            //insert p to tmp
                p->next = tmp->next;
                tmp->next = p;
                break;
            }
        }
    }
    graph = tmp;

    return graph;
}

some O() complexities for data structures:
theoretical

Edit:
There is a doubly-linked list in STL which is currently used.
In the future, I would like to have my own linked list implementation in C.

Edit2:
I am currently working on using a rope. A linked list, although in theory it seems perfect, in reality it is very different. A linked list and a rope are not serially stored in memory and as a result, they are more difficult to be all in the CPU cache also stores an extra pointer for each node. A rope is like a binary tree, so it has worse big-O complexity (see the updated table) but uses less memory.

By the way, Vi uses a rope and Emacs a gap buffer (dynamic array with gap for O(1) insertion).

Edit3:
Implemented my own gap buffer for each line, and deque for wrapping them:
deque<gapbuffer<char>> text(42)
Advantages: gap buffer uses almost as much memory as a normal array and has better insertion
The deque is used because arrays are contiguous in memory, so when resized they have to copy all the data to a new location.

Read 5 GB in 1 sec using 5.1 GB of memory (gap buffer) with fread(1MB block size) and parallel Open MP appending

from yocto.

New issue found: Try inserting text in a line which has tabs '\t' not spaces.
A tab is a single character, yet it is displayed as 8 characters.
The current way of inserting, is inserting according to x-axis of the cursor.
So there is a 7 character offset.

from yocto.