Hello everyone!

I'm working on a text editor that runs on my next '816 SBC, and I'm running into math problems. Yes, and I'm the math professor!

Let's start with Notepad, or equivalent. You press a key, and it inserts a character between whatever other characters you had the cursor on. Already we have math problems! So in memory, am I supposed to shift the entire document down by one character, just to slip this new one in? If the document is small enough and processor speed high enough (say like on a modern PC), no problem. But let's say I have 1MB of text to shift on a machine that is in the single digit MHz, and that gets cumbersome and slow. For each key.

You press backspace, now you have to shift everything back one. You press return, and you shift everything forward one and insert \n where the cursor was. This is all a lot of shifting...

Is there something I am missing here? Is there a technique that is just alluding me?

I'm on my second attempt at making this text editor right now. The first one just spit whatever character was in memory onto the screen, dropping lines by counting memory slots and not \n characters. This allowed me to not need to shift the entire document for each character, only for each return. But it's also incredibly wasteful, as most of my memory was simply $20 (for ASCII space) characters. Even when I went this way, the inevitable slow shifting was still there whenever I pressed return.

Any ideas? Know how older text editors worked behind the scenes?

Thank you for any advice.

Chad

Some text editors keep the text as a list of pointers to lines. But you may run into problems with memory fragmentation unless you have a good memory management system.

I tend to like one or more buffers with the text before the insertion point at the low end of the buffer and the text after at the end of the buffer with free space in the middle. New text is just entered into the buffer at the beginning of the gap as it is typed. When the insertion point is moved, the gap is moved.

Most of what you ever wanted to know about text editing but was afraid to ask in this read:

https://www.finseth.com/craft/craft.pdf

There are many ways to do it - I was going to suggest the space-in-the-middle method - but a few days ago I came across Challenging projects every programmer should try which has text editor as the first challenge mentioned. It then talks about some of the possibilities: "Data structures for storing the text: array, rope, gap buffer, piece table." With links! (Edit: also noting that if you want to implement an undo, that's an extra input to your choice of approach.)

There are a few options. One is to use expanded memory if you can have access to a 1 meg card, would be a big help swapping memory in and out.

But if it is all memory swapping on and off of a disk, I would go with another option. Have a Ctrl-char sequence that inserts 255 spaces into the document. Type what you need to type using overstrike mode, then have another Ctrl-char close up the unneeded space. For the most part then, inserting 255 characters is as fast as inserting 1 char at a time, moving the whole document down.

That's a nice idea!

Some of those ideas go way over my head Maybe I'm just a visual learner...

But I especially like the "insert 256 characters" idea! Maybe it could also be "insert new line" or "insert row". Lots of ways to take that.

If anyone else has any ideas I'm all ears.

Thank you!

Chad

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I decided a long time ago that a text editor that tries to shift the whole document in place is doomed to a syrup-like existence...

I'm noodling this idea, and I lean to a (doubly) linked list of blocks, nominally paragraphs - i.e. one can ignore the actual line width, and deal in the space between whatever you expect to get when you hit return. At save, everything gets unwound to get a linear file stored.

To insert, you create a new paragraph by replacing previous characters with a pointer to the new block, itself starting with the previous characters you just had to overwrite; to delete, one only needs to move within a limited size block.

But there are still a lot of things I haven't thought about yet: how to do undo, and particularly, how much and how often to defragment... it's mainly a project I do while I'm trying to get to sleep.

Neil

I'm not much of a software person, so I don't know answer to your question. I think shifting is inevitable, but it make sense to have line buffer and shift at carriage return instead of character-by-character. I would also suggest Miguel Garcia's TE editor. It small and simple screen editor written in 'C'. Because of its small size it has been ported to Z80 CP/M to work with limited program space. It is ported to my standalone Z80 computer, Z80ALL, and I'm thinking of porting it to 65ALL as well.

Bill

Many (30+) years ago, I played with a text editor that I wanted to write to go with an assembler for my Apple ][+. I had settled on a "heap of lines" plan, where each line of 127 chars or less was prepended by a byte containing the number of chars *2 + an "active" flag in bit 0. The editor manipulated pointers into this heap and should have been quite responsive until it was time to collect garbage. I never completed that project (nor the assembler), but I have fond memories of trying, and I probably still have some snippets on paper and floppy stashed around and about in my wicked mess of a house.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

As I recall the Turbo Pascal editor left extra gaps inside each line depending on where the cursor is. That way at most you are only generally shifting one character at a time. The only time you'd need to shift more than that is when you need extra space in the gap.

See here: https://en.wikipedia.org/wiki/Gap_buffer

My current version of a nano-like editor (maybe notepad like too) keeps an array of pointers to each line. Editing is essentially a line at a time. When you move to a line and add characters into it, the line is copied to a new buffer allocated from the heap (think malloc), worked on then the old line is forgotten (think free) and the new one is inserted into the list.

My malloc & free (actually getvec and freevec in the BCPL world) are fairly efficient and fast - arguably not the best algorithm, but academics have/are/will-be arguing over that forever.

Heap fragmentation is a possibility, but on my 512KB '816 system I've not encountered it - saying that, save early, save often is still a long-learned mantra.

Technically there might be a slow-down if I already had a large number of lines in memory then added lines at the top as this causes the entire array of line pointers to be moved (these are 32-bit values), so if I had 2000 lines, then the move is going to be 2000 * 4 = 8000 bytes. This is all done in a BCPL loop. A quick test - editing itself - add a line at the top - hard to tell - it's probably under a second, so not instant but just noticeable - or maybe not as there is buffered type-a-head if you're a good typist.

Obviously in assembler it would be much quicker, also with the ability to use the block move opcodes in the '816 - which I can't be bothered to use here as data spans banks transparently to BCPL so it would need more assembler code to cater for something usable from BCPL. A generic "memmove()" may help, but I've no real incentive to write more 816 code right now.

This is all under my BCPL OS which runs on-top of a Bytecode/VM. Approximate execution speed is from 200 to 500Khz per instruction with the '816 being clocked at 16Mhz. The editor is very responsive and fast but the biggest file I've edited with it is probably itself - currently about 1800 lines or so.



-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Hi!



There are various data structures to solve your problem, with different complexities for different operations. For example:

- Gap Buffer: this data structure divides the text in memory in two parts - all the data before the cursor, then all the free memory and then all the data after the cursor. You need two pointers, one points at the start of the gap and one at the end of the gap, and move the data around when the cursor moves.
- Piece Table: this data structure stores the original text in one big block of memory, and stores a list pieces (a pointer and a length) that describe the document. Originally you have one piece pointing at the start of the data and with the full length. When you insert into a piece, you divide the piece into two and add a third that points to new memory (at the end of the block) with the added data. This structure makes having an undo operation trivial, as the data is never deleted.
- Rope: this is a three representing the data, similar to the piece table, each node has a chunk of text and two childs for the text before and after the node. Insert and delete operations are done in the tree, and you need to keep the tree balanced for good performance.

For a text of length N and an operation on k characters after e editions, the three structures are O(k) for insertions and deletions. The Gap Buffer is also O(k) to move the cursor k characters, the Piece Table is O(e) and the Rope is O(ln(N)) for moving and locating the cursor.

For the small memory amounts of the 8 and 16 bit computers, the Gap Buffer is easy to implement and very fast.

A variation of the Gap Buffer is, instead of storing a big gap in the middle of the text, to store the current line being edited in a separated buffer, this means that the gap is created when a line is started to edit and deleted when the line editing ends. This is the model that the FastBasic editor uses, when the cursor moves up/down the current line is copied to the edit buffer, and all the editions happens in that buffer - this makes editing the line fast, and it only moves memory when you go to another line after the edition.

Have Fun!