LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-23-2010, 07:25 AM   #16
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195Reputation: 1195

Quote:
Originally Posted by anishakaul View Post
Does the below design make sense ?
Sorry, not to me.
Quote:
The first linked list is the read only file containing the original text of the file in question. Each node contains 80 characters (a line)
What do you mean by a linked list is a file? Why are you implying 80 characters is a line?
I think the designs you might have read for keeping the original separate from the edits are not intended for undo (as you seem to have assumed) but for efficiency in reducing the original processing and storage costs of reading in the initial file. It appears you are defeating that purpose by breaking the original into nodes.

Quote:
The last linked list is the one in which user will append the changes or the new text.
I am unable to even guess what you meant by the rest of the design. Efficiently representing just the changes is not likely to be practical. Storing the text of only the changes is practical, but it should require a unified structure of pointers into changed and unchanged text that represents the current state of the partially edited file.
 
1 members found this post helpful.
Old 11-23-2010, 10:03 PM   #17
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,724

Original Poster
Blog Entries: 29

Rep: Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931
Thanks again for bothering to reply, John.

Quote:
Originally Posted by johnsfine View Post
Sorry, not to me.
I am sorry that I didn't state clearly what I meant.

Quote:
Originally Posted by johnsfine View Post
What do you mean by a linked list is a file?
This meant that the original contents of the file would be read into the first link list.

Quote:
Originally Posted by johnsfine View Post
I think the designs you might have read for keeping the original separate from the edits are not intended for undo (as you seem to have assumed) but for efficiency in reducing the original processing and storage costs of reading in the initial file. It appears you are defeating that purpose by breaking the original into nodes.
Yes, absolutely, I had a wrong understanding of that data structure. Now I do realize there is no need to break the first linklist into nodes!

Quote:
Originally Posted by johnsfine View Post
I am unable to even guess what you meant by the rest of the design. Efficiently representing just the changes is not likely to be practical. Storing the text of only the changes is practical, but it should require a unified structure of pointers into changed and unchanged text that represents the current state of the partially edited file.
The middle link list showing the pointers is not the actual design. In the actual design, of course, sets/groups of pointers would be made to represent different tasks. I am sorry for that confusion now.

Quote:
Originally Posted by johnsfine View Post
Why are you implying 80 characters is a line?
I had started a thread for knowing the maximum number number of characters which can be displayed in a screen: http://www.linuxquestions.org/questi...screen-844325/

and now I am thinking that if I denote new lines by keeping a pointer on the start of each line, then:
  • When the user wants to move one line up, we just have to jump to the next pointer, skipping the characters in between.
  • If according to that thread I take 80 chars maximum for a line, and the user shrinks the window, I'll just have to adjust the pointers to denote new lines rather than moving data.

Thanks again for your reply, I shall post here the final data structure design in a short duration.
 
Old 01-22-2011, 08:34 AM   #18
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,724

Original Poster
Blog Entries: 29

Rep: Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931Reputation: 931
Does the following structure now makes sense?
Code:
struct deletionHandler
{
    /* 'ptrFirst' points to the character on the left of the character(s) to be deleted */
    char *ptrFirst;
    /* 'ptrSecond' points to the character on the right of the character(s) to be deleted */
    char *ptrSecond;
};

struct insertionHandler
{
    /* 'ptrFirst' points to the character on the left of the left of the cursor */
    char *ptrFirst;
    /* 'ptrSecond' points to the character to be inserted */
    char *ptrSecond;
    /* 'ptrThird' points to the character on the right of the left of the cursor */
    char *ptrThird;
};

/* The vectors acts as a stack (stack is used for maintaining undo's and redo's) to store the deletionHandler's/insertionHandler's objects */
vector <deletionHandler> deletionPointerStack;
vector <insertionHandler> insertionPointerStack;
The line pointers kept in another structure will point to the new line characters entered by user. Line numbers will be displayed according to those new line characters.
 
Old 03-08-2016, 12:24 PM   #19
dugan
LQ Guru
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 10,435

Rep: Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914
I think it's worth updating this thread to post this link:

A Brief Glance at How Various Text Editors Manage Their Textual Data
 
3 members found this post helpful.
Old 03-09-2016, 12:38 AM   #20
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.1
Posts: 722
Blog Entries: 2

Rep: Reputation: 123Reputation: 123
Darn! A necro thread.

There's little point in adding my thoughts then.
 
Old 01-03-2022, 09:05 AM   #21
dugan
LQ Guru
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 10,435

Rep: Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914
Just want to point something out.

A linked list is better for insertions and deletions only if you don't need to traverse the list to find the insertion or deletion point. If you do, then insertions and deletions become O(n) and their only advantage over dynamic arrays disappears.

That's why linked lists are typically used to implement data structures where you insert and delete from the beginning or end (stacks, queues, and deques), not where you insert and delete from the middle.

The link I posted above, which shows how actual text editors have actually done it, is still active. The TLDR is that "buffers", which is to say arrays, are more popular than linked lists.

And here's a blog entry on developing VSCode's text buffer:

Text Buffer Reimplementation

(People who saw previous versions of this post might have seen swipes at a guy upthread who presented himself with authority and strongly advocated using a linked list. You know who it was, and I'm sure you know what I said).

Last edited by dugan; 01-03-2022 at 09:27 AM.
 
Old 01-03-2022, 09:48 AM   #22
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,759
Blog Entries: 4

Rep: Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520
Today, we have languages like C++ which implement various container classes. Sometimes-magical and hard-to-implement exotic data structures have already been correctly implemented in them. Just take them off the shelf and use them, knowing that they will work: you don't have to look inside. In similar fashion we have a robust string type. We have "dictionaries." We have "garbage collector" dynamic memory management just like interpreters use. You simply use the class for what it's built for and look at the source code of the thing only if you are morbidly curious. You know that it has been thoroughly debugged already. And this is how many interpreters and other tools which you reliably use every day were built.

(You can even find: "a complete, working, text editor.")

Actum Ne Agas: "Do Not Do A Thing Already Done."

Last edited by sundialsvcs; 01-03-2022 at 09:53 AM.
 
Old 01-03-2022, 01:59 PM   #23
EdGr
Member
 
Registered: Dec 2010
Location: California, USA
Distribution: I run my own OS
Posts: 788

Rep: Reputation: 389Reputation: 389Reputation: 389Reputation: 389
This is an interesting topic.

In the 1980s, I wrote a text editor that uses a form of doubly-linked list. The doubly-linked list works well because most editing operations are performed on local areas of text. The user inserts and deletes from the same local areas much more often than he accesses randomly from the entire text.

My experience has been that the doubly-linked list's ability to insert and delete without moving anything in memory is a net win.
Ed
 
Old 01-03-2022, 07:50 PM   #24
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,759
Blog Entries: 4

Rep: Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520
To me, perhaps the greatest benefit of "object-oriented programming" was that we could finally stop re-implementing the same wheels. Instead, we could abstract them.

We could finally build a piece of logic which could once-and-for-all correctly implement a particular algorithm, and then "safely apply them to [anything]." Why? Because every [anything] was: 'an object.' (Most "language-internally-defined types" in this context are effectively equivalent to objects.)

So far, there is (AFAIK ...) no Nobel Prize for software. However, if there were, I think that this concept would surely qualify.
 
Old 01-04-2022, 03:04 AM   #25
Michael Uplawski
Senior Member
 
Registered: Dec 2015
Location: Non. Je suis propriétaire – No. I am an owner.
Distribution: Apple-selling shops, markets and direct marketing
Posts: 1,315
Blog Entries: 35

Rep: Reputation: 707Reputation: 707Reputation: 707Reputation: 707Reputation: 707Reputation: 707Reputation: 707
Quote:
Originally Posted by sundialsvcs View Post
To me, perhaps the greatest benefit of "object-oriented programming" was that we could finally stop re-implementing the same wheels. Instead, we could abstract them.
If “abstract” means restricting our exchanges with an object to the necessary and fill in the gaps selectively, I may consent. But the mere “re-use” with the ever-returning argument to not “invent the wheel twice” made us drive square-wheeled tricycles for the simple reason that everybody did. Anybody who utters “invent the wheel again” nowadays should be obliged to prove his comprehension of the current concept (the original “wheel”) instead of pointing at a long line of programs and people who integrate tons of libraries which, each one, only provide a fraction of their functionality to the program and some double the functionality of other libraries, present in the same project.

– I admit that I had been taught to call this Java, but the principle appears to be general.

The main and original achievement of Object Orientation is the possibility to think about program code in the way we think about other objects that we encounter as human beings in our daily life. Programming object-oriented should be more natural than the mere production of algorithms. It still needs insight and discipline. Everything can be perverted and blown up, I do not doubt that.

And I appreciate any project which picks up old ideas to produce better results. From scratch or otherwise. Who cares.

Last edited by Michael Uplawski; 01-04-2022 at 03:10 AM.
 
Old 01-04-2022, 10:43 AM   #26
EdGr
Member
 
Registered: Dec 2010
Location: California, USA
Distribution: I run my own OS
Posts: 788

Rep: Reputation: 389Reputation: 389Reputation: 389Reputation: 389
Much of the design of a text editor is in its data structure. One shouldn't expect to write a world-class editor without also designing a custom data structure.

The reason is that the data structure matters. It is tightly-coupled to the algorithms, and these affect the editor's ability to handle enormous files.

I have tested various editors on gigabyte files. You might be surprised how many fall apart. Mine works.
Ed
 
Old 01-04-2022, 04:55 PM   #27
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,759
Blog Entries: 4

Rep: Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520Reputation: 3520
My point is simply this – "while you might know how to correctly implement a red/black tree, you don't need to do it anymore." Someone else already did it for you, and they thoroughly debugged it. Then, they created it as a public "container class" that is capable of storing and retrieving anything "as long as it is an Object." This is of course a gigantic step forward. Creative and inventive though we might all be, we should not have to "first, re-invent bricks and mortar" in order to build a wall with them.

Last edited by sundialsvcs; 01-04-2022 at 04:56 PM.
 
Old 01-04-2022, 05:58 PM   #28
dugan
LQ Guru
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 10,435

Rep: Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914Reputation: 4914
Sundial, stop making “points” that have nothing to do with what anyone said.

No-one has indicated that they wouldn’t use library data structures, or that they weren’t aware that libraries of data structures exist.

Last edited by dugan; 01-04-2022 at 06:47 PM.
 
Old 01-04-2022, 06:00 PM   #29
EdGr
Member
 
Registered: Dec 2010
Location: California, USA
Distribution: I run my own OS
Posts: 788

Rep: Reputation: 389Reputation: 389Reputation: 389Reputation: 389
My point is that text editors are like race cars, custom-built for the job. You have to make the important parts yourself because no-one sells such things.
Ed
 
1 members found this post helpful.
  


Reply

Tags
text editor


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ - Store a text file in a Data Structure nilly16 Programming 3 05-26-2009 06:42 AM
text selection question in text editor olin Linux - Software 1 09-25-2007 01:25 PM
Text Editor on Fedora Core 4 in Text Mode blong4life Linux - Software 5 07-31-2006 09:07 PM
Which light text editor can copy text from file and paste in browser? davidas Linux - Software 9 03-06-2006 11:28 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:25 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration