C++

Forum

 
Notepad using a Two-Dimensional Doubly Linkedlist

haider885 (8)
Can Any body do it????
These are Some Info.....
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
Create a notepad that allows the user to write text on the console. For this purpose, the user should be
able to control and track the movement of the cursor. The user can access, add and delete any part of
the text. To add or delete a text, the user can take the cursor to that location (using the arrow keys) and
perform the required operation. The working of the program (i.e. the movement of the cursor, add and
delete operation) must be consistent with the working of the real notepad. However, you do not have
to handle word wrapping.

In addition, the user should be able to save and load the data in a text file using S and L respectively.
The program will automatically save the data in file save.txt, and load the data from the same file.
There is no need to ask the user for the file name. Use Q to quit the notepad. Don’t forget to
implement the destructor.

Internally, the notepad is composed of two-dimensional doubly linkedlist. Its implementation is just
like a doubly linked list with an additional property that it can grow in two dimensions. Since text can
be written on multi lines, each row of the 2D-linkedlist represents one line. Each node contains four
links which it uses to connect to node before, after, below and above it. In addition each node can store
a character.
closed account (Dy7SLyTq)
well yeah it shouldnt be that hard. sounds like homework though which means no one is going to write code for you. what part are you stuck on?
haider885 (8)
Track Movement of cursor???????
closed account (Dy7SLyTq)
whatever graphics api you use should do it for you
cire (8284)
Nobody is likely to do it for you. You're going to need to use a OS specific features or a library that wraps those features for you to do what is described.

http://www.cplusplus.com/forum/beginner/1/#msg6680

cross-posted to:
http://www.daniweb.com/software-development/cpp/threads/469871/notepad-using-a-two-dimensional-doubly-linkedlist
where you also needed to do some research before you posted.
Duthomhas (13107)
...still, it is an absurd assignment.

It sounds like the instructor want's OP to maintain a linked list that looks like this:

  c--c--c--c
  |  |  |  |
  c--c--c--c--c
  |  |
  c--c

where c represents a character node, and dashes and pipes represent links.

Such a system is not used in the wild -- it introduces an incredible amount of overhead for basic operations.


@haider
Sorry you have to do this. When dealing with linked lists, keep a lot of paper handy that you can draw on. Use a pencil. Whenever you do something like add and remove (shudder) nodes, you can draw what you want to happen on your paper, in the order it has to happen, and then implement it.

Personally, to remove a node, I'd cheat by simply shifting the values of each following node to the left by one, then delete just the last node. This reduces the node updates to just unlinking in one spot, instead of having to relink across three whole rows of nodes.

Good luck.
JLBorges (13770)
> Internally, the notepad is composed of two-dimensional doubly linkedlist.

Logically, this is is a two-dimensional doubly linked list of characters (a data structure that allows us to move left and right, as well as up and down):
std::vector<std::string> list_2d ;

The messy part is: "the user should be able to control and track the movement of the cursor." You would need to use a library like curses for this.

The rest of the program is quite straightforward.
For instance, the low-level operations look something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

using text = std::vector<std::string> ;

std::ostream& operator<< ( std::ostream& stm, const text& txt )
{
    int n = 0 ;
    for( const auto& line : txt )
        stm << std::setw(3) << n++ << ". " << line << '\n' ;
    return stm ;
}

text& insert( text& txt, std::size_t row, std::size_t col, char c )
{
    if( row >= txt.size() ) txt.resize(row+1) ;
    auto& line = txt[row] ;

    if( col > line.size() ) line.resize( col+1, ' ' ) ;

    if( c == '\n' )
    {
        auto tail = line.substr(col) ;
        line.resize(col) ;
        txt.insert( txt.begin() + row+1, tail ) ;
    }
    else line.insert( col, 1, c ) ;

    return txt ;
}

text& erase( text& txt, std::size_t row, std::size_t col )
{
    if( row < txt.size() )
    {
        auto& line = txt[row] ;
        if( col < line.size() ) line.erase(col) ;
    }

    return txt ;
}

text& erase( text& txt, std::size_t row )
{
    if( row < txt.size() ) txt.erase( txt.begin() + row ) ;
    return txt ;
}

text& erase_newline( text& txt, std::size_t row )
{
    if( row < txt.size()-1 )
    {
        txt[row] += txt[row+1] ;
        txt.erase( txt.begin() + row+1 ) ;
    }

    return txt ;
}

int main()
{
    text txt =
    {
        "Create a notepad that allows the user to",
        "write text on the console.",
        "For this purpose, the user should be able to",
        "control and track the movement of the cursor.",
        "The user can access, add and delete",
        "any part of the text.",

    };

    std::cout << txt << "--------------------------------\n" ;

    insert( txt, 2, 27, '\n' ) ;
    std::cout << txt << "--------------------------------\n" ;

    insert( txt, 3, 27, '#' ) ;
    insert( txt, 3, 28, '!' ) ;
    std::cout << txt << "--------------------------------\n" ;
    insert( txt, 9, 27, '#' ) ;
    insert( txt, 9, 28, '!' ) ;
    std::cout << txt << "--------------------------------\n" ;

    erase( txt, 8 ) ;
    std::cout << txt << "--------------------------------\n" ;

    erase( txt, 7 ) ;
    erase( txt, 7 ) ;
    erase( txt, 3, 27 ) ;
    erase( txt, 3, 27 ) ;
    erase_newline( txt, 2 ) ;
    std::cout << txt << "--------------------------------\n" ;
}

http://coliru.stacked-crooked.com/a/afc7adf21ed4c199
Duthomhas (13107)
std::vector<std::string> list_2d ;

Should have been a std::deque, but that's a nit-pick.

In any case, that doesn't help OP.

OPs assignment wrote:
Each node contains four links which it uses to connect to node before, after, below and above it. In addition each node can store a character.

JLBorges (13770)
> In any case, that doesn't help OP.
> OPs assignment wrote:
> Each node contains four links which it uses to connect to node before, after,
> below and above it. In addition each node can store a character.

The problem that the haider885 is having is with: "Track Movement of cursor???????"
http://www.cplusplus.com/forum/general/120257/#msg654378

I realize that this was no great help:
The messy part is: "the user should be able to control and track the movement of the cursor." You would need to use a library like curses for this.


The intent of the post was to point out that:

a. A two-dimensional doubly linked list of characters is logically just a data structure that allows us to move left and right, as well as up and down.

b. Working with a vector of strings makes the code a lot easier to write, understand, debug and test; particularly if editor operations like search, replace, delete word etc. are to be provided.


Apparently, the two issues that I omitted to mention do not seem to be obvious to every one; so let me state those too.

c. the program being driven by the speed at which the user can type in stuff, the design is not primarily driven by performance considerations.

d. writing a facade, which maintains the required "Each node contains four links ... etc. ... " requirement is trivial. We can still implement the program logic with std::vector<>, std::string, standard algorithms etc.

The earlier code, with the facade tacked on (assuming that the text is reasonably small: the entire text would easily fit into available memory, not more than a few thousand lines etc.):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

using text = std::vector<std::string> ;

std::ostream& operator<< ( std::ostream& stm, const text& txt )
{
    int n = 0 ;
    for( const auto& line : txt )
        stm << std::setw(3) << n++ << ". " << line << '\n' ;
    return stm ;
}

text insert( text txt, std::size_t row, std::size_t col, char c )
{
    if( row >= txt.size() ) txt.resize(row+1) ;
    auto& line = txt[row] ;

    if( col > line.size() ) line.resize( col+1, ' ' ) ;

    if( c == '\n' )
    {
        auto tail = line.substr(col) ;
        line.resize(col) ;
        txt.insert( txt.begin() + row+1, tail ) ;
    }
    else line.insert( col, 1, c ) ;

    return txt ;
}

text erase( text txt, std::size_t row, std::size_t col )
{
    if( row < txt.size() )
    {
        auto& line = txt[row] ;
        if( col < line.size() ) line.erase(col) ;
    }

    return txt ;
}

text erase( text txt, std::size_t row )
{
    if( row < txt.size() ) txt.erase( txt.begin() + row ) ;
    return txt ;
}

text erase_newline( text txt, std::size_t row )
{
    if( row < txt.size()-1 )
    {
        txt[row] += txt[row+1] ;
        txt.erase( txt.begin() + row+1 ) ;
    }

    return txt ;
}

///////////////////   facade   ////////////////////////

struct Char
{
    explicit Char( char c ) : this_char(c) {}

    char this_char = 0 ;
    Char* left = nullptr ;
    Char* right = nullptr ;
    Char* up = nullptr ;
    Char* down = nullptr ;
};

using Char2d = std::vector< std::vector<Char> > ;

text make_text( const Char2d& c2d )
{
    text txt ;
    for( const auto& row : c2d )
    {
        std::string str ;
        str.reserve( row.size() ) ;
        for( const auto& node : row ) str += node.this_char ;
        txt.push_back( std::move(str) ) ;
    }
    return txt ;
}

Char2d make_2d( const text& txt )
{
    Char2d c2d ;

    for( const auto& line : txt )
    {
        std::vector<Char> v ;
        for( char c : line ) v.emplace_back(c) ;
        c2d.push_back( std::move(v) ) ;
    }

    for( std::size_t i = 0 ; i < c2d.size() ; ++i )
    {
        auto& row = c2d[i] ;
        const auto sz = row.size() ;
        for( std::size_t j = 0 ; j < sz ; ++j )
        {
            if( j != 0 ) row[j].left = std::addressof( row[j-1] ) ;
            if( j != sz-1 ) row[j].right = std::addressof( row[j+1] ) ;
            if( i > 0 && c2d[i-1].size() > j )
                row[j].up = std::addressof( c2d[i-1][j] ) ;
            if( i != c2d.size() - 1 && c2d[i+1].size() > j )
                row[j].down = std::addressof( c2d[i+1][j] ) ;
        }
    }

    return c2d ;
}

Char2d& insert( Char2d& c2d, std::size_t row, std::size_t col, char c )
{ return c2d = make_2d( insert( make_text(c2d), row, col, c ) ) ; }

Char2d& erase( Char2d& c2d, std::size_t row, std::size_t col )
{
    if( row < c2d.size() && col < c2d[row].size() )
        c2d = make_2d( erase( make_text(c2d), row, col ) ) ;
    return c2d ;
}

Char2d& erase( Char2d& c2d, std::size_t row )
{
    if( row < c2d.size() ) c2d = make_2d( erase( make_text(c2d), row ) ) ;
    return c2d ;
}

Char2d& erase_newline( Char2d& c2d, std::size_t row )
{
    if( row < c2d.size()-1 ) c2d = make_2d( erase_newline( make_text(c2d), row ) ) ;
    return c2d ;
}

std::ostream& operator<< ( std::ostream& stm, const Char2d& c2d )
{ return stm << make_text(c2d) ; }

int main()
{
    Char2d c2d = make_2d(
    {
        "Create a notepad that allows the user to",
        "write text on the console.",
        "For this purpose, the user should be able to",
        "control and track the movement of the cursor.",
        "The user can access, add and delete",
        "any part of the text.",

    } );

    std::cout << c2d << "--------------------------------\n" ;

    insert( c2d, 2, 27, '\n' ) ;
    std::cout << c2d << "--------------------------------\n" ;

    insert( c2d, 3, 27, '#' ) ;
    insert( c2d, 3, 28, '!' ) ;
    std::cout << c2d << "--------------------------------\n" ;
    insert( c2d, 9, 27, '#' ) ;
    insert( c2d, 9, 28, '!' ) ;
    std::cout << c2d << "--------------------------------\n" ;

    erase( c2d, 8 ) ;
    std::cout << c2d << "--------------------------------\n" ;

    erase( c2d, 7 ) ;
    erase( c2d, 7 ) ;
    erase( c2d, 3, 27 ) ;
    erase( c2d, 3, 27 ) ;
    erase_newline( c2d, 2 ) ;
    std::cout << c2d << "--------------------------------\n" ;
}

http://coliru.stacked-crooked.com/a/a1081820edc26f82
Duthomhas (13107)
Your points are valid and true and I agree...

I'm not sure his professor would accept that, though.
Topic archived. No new replies allowed.