Separate from the choice of data structure, consider that you can make updates to the chosen structure 'in the background' vs. after every key press. This allows the editor to remain responsive and opens the possibility of combining multiple updates.

For example with the basic array data structure, the first key press to insert a character could launch a shift by 1 in the background. Then if there have been, say 3 more key presses to insert characters by the time the first shift completes, the next shift will be by 3. The shift by 3 takes no more time to perform than the shift by 1, so with a modestly sized buffer to track pending updates, the editor should be able to keep up with rapid typing, even for large files using a simple data structure.

The more complex data structures can benefit from background operations, e.g. for consolidation or re-balancing. Of course this all comes with extra complexity to manage the foreground and background tasks, and communication between them.

"Insert new line" won't work either as that only inserts a RETURN char of 1-byte. And inserting multiple RETURN characters just pushes any text off the screen.

Another good idea is to use the end-of-document as your buffer. Appending to the end of the document is as fast as using a separate buffer or inserting spaces or anything else. You then hi-light and cut the text using some sort of clipboard, or save the selected text to a file, then paste/insert/load your text at the point at which you want the text to be inserted.

The snag there is that most people have grown used to full screen text editors - courtesy of huge amounts of memory and fast processors.

On a system with a relatively small amount of memory - say 64k - that has also to include some screen ram and the executing program itself, you might be restricted to only half that as a usable buffer. For anything that allows bulk writing you're going to need a fairly speedy way of editing a chunk of text apparently within the body of existing text, and that might have to include a way to get data on and off storage temporarily.

It is certainly possible to edit text on a small system: Electric Pencil by Michael Shrayer was released on 8080 in 1976 and was spoken of glowingly by a number of authors though I think he got bored of it later and it was superseded by programs like Wordstar.

Apropos of file sizes: the average word length in English is about five characters, plus a space. Dicken's 'Pickwick Papers' (I blame the season!) is almost 140k words, so perhaps close to a million characters... with a document that size, responsiveness to the user is going to be critical and something like background pagination or spell-checking is probably not going to be practical.

I find it amusing that MS Word has accrued so many bells and whistles these days that in these days of multi-gigahertz clocks it is still easy for a competent typist to type ahead of the display:

• sliding animated cursor (disconcerting to me and many other users)
• spell check as you type (I can spell; if I can't tell me later. p.s. UK spelling please!)
• grammar check as you type (your idea of grammar is not necessarily the same as mine)
• style check as you type (neither is your manual of style)
• 'woke' check as you type (let's just not go there, ok?)
• character style changes (wysisyg has a lot to answer for)

and no doubt many others, are things you probably really shouldn't be considering with a 6502 processor

Neil

Um, but I digressed: a text editor is a different tool: in particular it has to be able to cope with lines of text which are longer than the screen width...

Neil

I spent hundreds of hours in the 1980s using Apple Writer II for high school, college, and correspondence. It worked well on my 40-column upper-case only Apple ][+, and it instantly detected and adapted to my Apple //e-compatible Franklin Ace when I started using that instead. It was quite nimble, and even included a macro facility called WPL. I don't know the nuts and bolts of how Paul Lutus did it, but he did it very well.

_________________
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)

I feel it's always been good advice, when writing a very long document like a book, to use a new file for each chapter. That keeps down the maximum size, which is good for performance and also disaster recovery - only one chapter can be lost or damaged in an editing accident.

_________________
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?

Excellent advice, and perhaps also an argument for using segmented source files. One file per function is perhaps overly complex, but one file per function class makes a lot of sense.

As do frequent backups (as opposed to saves)...

Neil

Going more OT, but the internal mechanics of a text editor and word processor do have similarities, or maybe did have in the days of WordStar, AppleWorks and so on - I suspect the internal format of a modern Microsoft Word, Apple Pages or even Libreoffice Writer are far more complex today though.

I don't use a word processor myself - rather I use a text editor and then a typesetting tool to manipulate that text based on commands I put into the text. This idea is not new.

TeX (or more precisely LaTeX) which I use goes back to 1978 although my first encounter with it was round about the late 80s. Before that I'd used Unix troff

(And as a job I once had to write a troff from scratch in the days before GPL and the Internet - or at least before they reached the UK)

and there were various layout programs for the systems I used (including a trivial one I wrote at university in the early 80s) which would take commands from the text. (As a left-handed dyslexic autistic person I positively hate hand-writing. It's not neat, my spelling is bad and I frequently swap not just letters but whole words)

LaTeX lets me split things up into chapters, create tables of contents, indexes, cross references and so on. I see people struggle and 'write' pages of macros to do this in MS Word. LaTeX is not without it's issues though - you do have to type more to get those commands in - and sometimes you do need to define macros to help things along but I've yet to find something as flexible as LaTeX for what I need.

Today the most well know markup is probably the HTML we use in web pages although that too has been changed with the use of CSS, Javascript (back to 'macros' again..) and many other means, but a simple text editor is all you really need to get something going.

Back to text editors - notepad or nano (or nano-like) editor are generally type to insert, move the cursor with arrow keys and type or delete with some "control" codes to do extra stuff like quickly move the cursor to the start of end of a line or do searches and sometimes replace. Sometimes mouse input can be used, sometimes there are special codes to insert a new/blank line or sometimes you use a combination command like "move cursor to end of line, then press enter" and so on.

Emacs is probably the most feature-full of this style of editor with it's own 'macro' language but it's relatively huge - I had a job to port it to a system with 8MB of RAM and a 32-bit CPU once (late 80s) - gave-up and ported VI (Stevie - the forerunner to VIM) then used that to port micro Emacs (essentially nano) and that was good enough... And FWIW, I've used vi or vim ever since. I've written many editors (often 'domain specific' rather than general text editing) but my nano-like editor in my BCPL system was derived from the nano-like editor I wrote in C which was derived from the nano-like editor I included in my RTB Basic system which was derived from another project way back....


A nano-like editor can be written in about 1000 lines of C. My C version for the 6502 is some 1500 lines (including blank lines, multi-line comments, etc.) it compiles to about 15KB. The BCPL version is just under 1800 lines (with blank lines, comments, etc.) and compiles to 5.5KB of code...

As for block-moving memory, I think the only time I've done that is in my TinyBasic. I think almost all 8-bit BASICs do it that way. It's "cheap" and saves the creation of a separate array or linked-list of line numbers, but even then, editing a line is done outside the main buffer - insrt/delete characters happen in the line input buffer and it's only when you push return that the system works out to delete, overwrite or insert the line (and in my TB, overwrite is delete then insert) BASIC has the additional challenge of mapping a BASIC line number to the line number if the line being edited, but that's a problem for another place...

Oh, one other thing:

Lets be realistic. If you're editing a 1MB file on a single digit Mhz system then you're doing it wrong. Really. Give up. It's not the system for this task no matter what you might think the CPU is capable of, This is not the system. Even on Unix systems I used in the late 80s (I had a Sun3/50 as my 'desktop') I'd not do that - a 16Mhz 68030 with 4MB of RAM trying to edit a 1MB file? I might just about get away with it, but I'd need to be very patient. I've enjoyed making my '816 system self-hosting, (ie. run it's own editor & compiler) but even then there is a limit to what I think it can do.

Enough ramblings for now..

Cheers,

-Gordon

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

LaTeX can be a bit of a handful, but for us Linux types (and perhaps Windows as well?) there is the LyX front end.

I've published a couple of books using LyX and do a lot of documentation with it. You'll have seen me bang on elsewhere about semantic white space - LyX enforces it (though you can still hit it with an Ugly Red Text stick if you insist!).

Neil

I was going to wait another day or two to reply, but I figured now is about right to respond to Gordon.

Thank you all for the excellent info! Lots of great ideas here.

Yesterday I tried the "insert 256 characters" approach. It was ok-ish, but even after a full page of text to shift it was bogging down. If I kept that going for much larger documents then it would certainly not be feasible.

This morning I have been working on Gordon's "nano like" idea. At least that's what I think it is. Each time I hit Return (or Arrow Up/Down) it saves the line buffer at the bottom of a virtual stack. Each line being 80 columns, simplify it down to 128 bytes, then I essentially only have the amount of edits that I have RAM available. BUT it doesn't slow down much. The slowest it goes is when it's re-drawing the characters on the screen after a Return (or Backspace when deleting a line). The compromise is that eventually I will run out of available memory and it will have to "defrag" or "compress" or something, removing older edited lines.

So far so good, still working on it, but seems promising.



I don't understand, maybe because I am so young that all I've ever known is 1.44 MB 'floppies' (they weren't so floppy) and onwards. The main constraint for handling 1 MB text files is just to show how "shift all the data on each character" is unfeasible. The single digit MHz constraint was to show I'm not running on a modern PC or something. I don't necessarily think I will ever reach 1 MB files of me just typing away at my SBC, but you never know.

And since LaTeX was brought up, I have done a lot in LaTeX over the years. I've used it to make documents in Koine Greek, math formula books for the college, and the latest is using MathJax with HTML/Javascript for automated math assessment creation. I really don't like how picky it is, and maybe I just don't understand the inner workings, but it is a great tool and I use it when I need to use it. I certainly don't avoid it!

Thank you!

Chad

Nano is a common editor used in Unix/Linux systems. It was based on an editor called Pico which was part of the Pine/Alpine email package. It's a simple editor: What you type goes into the text, Cursor keys move as you might expect, page up/down/home/end keys (where present) again do what you might expect along with a bunch of control-keys to do extra stuff - e.g. Ctrl-K for Kill a line (delete it), Ctrl-U to un-kill a line (so you have copy/paste lines there) and so on. Press Ctrl-K 10 times, then move and Ctrl-U and you've moved 10 lines. Or Ctrl-K 10 times, then immediately Ctrl-U to pu them back, then move and another Ctrl-U to copy them into a new location...

It has grown over the years to support things like syntax highlighting and so on and while I don't use it for coding, it is a good base when you need a "quick and dirty" editor. (And I've been using Pine, now Alpine email programs for some 30 years now)

https://en.wikipedia.org/wiki/GNU_nano


Anyway...

A speed-up you can use is to only copy the line the cursor is on into a "working" buffer if you type a command that changes the line (insert char, delete, etc) that way you can scroll up/down/left/right very quickly.

I also forced a maximum line length in my editor of 160 characters. This is based on my personal editing where I'd normally never had a window more than 160 characters wide (often 120 characters as that's a comfortable left-right scan for me. (BCPL also uses a byte for string lengths so the absolute maximum is 255 characters anyway unless I do my own management)

So I read a file in, line at a time, allocating space for each line and keeping an array of pointers to each line.

So what I think of is essentially a line editor with many lines.

Editing and compiling a 2000 line program is right at the limits of this system and even if it had double the RAM things like read/writing to/from disc and the actual compile time start to become limitations on usability. (The BCPL compiler is just under 6700 lines in total and I have compiled it on the system, but it's an all-nighter)


Heap management is via free/malloc or freevec/getvec in BCPL - my management code (written in in BCPL) is a fairly standard first-fit allocator which 'remembers' the pointer to the last block allocated (so starts looking for free space where it last allocated something until it hits the end of free space before wrapping round looking for holes).

And when I was looking at options to write a new little OS, and when looking at how to boot BCPL I initially wrote this in sweet-16 which also worked very well on the 6502. (And I blew the dust off it recently for my next little 6502 project which may or may not see the light of day...)

I think a good little memory management/allocator like this is a handy thing to have. How you might implement it on an '816 to handle bank crossing is left as an exercise to the user though... (The underlying VM/Bytecode in my BCPL system gives me linear RAM and does the bank shenanigans for you to accessing RAM in BCPL is very easy - the cost is speed of the underlying VM)

I do edit and compile short programs regularly on my system and have never run out of memory due to heap fragmentation. The heap management code does insert guard words at the start and end of each allocation to check for overwriting - that works well and the editors never tripped the guards...





Well, indeed, you never know but we'll always push the boundaries. Today, we're doing (or thinking about doing) stuff on a CPU that we'd never have dreamed about doing on that CPU when it was released in 1986 - The Acorn Communicator had 512KB or 1MB of RAM, and while the Apple IIgs has space for expansion (Up to 8MB I think) did anyone/thing use it all? The communicator did have an "Office" suite but I never used it - how might it have handled a 1MB file? Hm. I presume there was also an upgrade AppleWorks for the IIgs - could that manage very large files?

From my own/personal point of view, I've hit the limit of my '816 system - Like many others (companies, individuals) before me I'm looking at moving on - the '816 now appears to be a stop-gap, almost - and allowed me to do my own "what if" and implement a multi-tasking OS with development tools but now I want it a little faster...

Here's another thought: Unix has some interesting tools to manage text files most of them are redundant these days (I suspect) - one is split - split a file into smaller files each with a certain number of lines in it.. Merging them back is trivial with the cat command... Did these arise because files were starting to get big, but couldn't be managed as a whole? (for editing, sorting, searching?) Then there's the sed command - a stream editor reads a file, a set of editing commands and writes a new file... (something I have used 'for real' with a very old computer with tape reader and punch!) And maybe think Unix - do one thing well - and if that one thing is editing files < 64K long, then write something nice to split files and merge them again...

... and we're almost back to writing a chapter per file and my old mantra; save early save often...

Cheers,

-Gordon

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

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

Hi Chad! I have a couple of thoughts for you:

The first one is, don't feel bad! This is a surprisingly *hard* problem, and has been since the beginning of computers.

The second one is, "storing text data (i.e., file format)," "altering text data," and "displaying text data" are three separate problems that don't necessarily need to be intermingled, although they can be. It might not be a bad idea to do a top-down "block diagram" design of your text editor architecture.

_________________
"The key is not to let the hardware sense any fear." - Radical Brad

So true!

Storing text data: This was the purpose of me asking here. I'm getting really close to a nano-like line editor with many lines, as Gordon has talked about. I think that's the best way for me right now.

Altering text data: This goes hand-in-hand with this particular method. You are not really 'editing' so much as 'replacing'. The newest version on the stack is the one you should use, older versions of the line should be ignored.

Displaying text data: Completely separate indeed. My particular setup is, well, particular, and it's a math problem just to get it display correctly! Right now that is the slowest part, refreshing the screen after a Return, but it seems manageable so far.

I only have two main things left to program as of now: Defrag and Scrolling Display. Will post more when I have something interesting to show. Thank you!

Chad