-
Notifications
You must be signed in to change notification settings - Fork 0
/
rope.c
314 lines (259 loc) · 6.93 KB
/
rope.c
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#include "rope.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "utils.h"
#define EMPTY ""
RopeNode* makeRopeNode(const char* str) {
RopeNode *new_node = malloc(sizeof(*new_node));
DIE(!new_node, "New node malloc failed");
new_node->left = NULL;
new_node->right = NULL;
new_node->str = str;
new_node->weight = strlen(str);
return new_node;
}
RopeTree* makeRopeTree(RopeNode* root) {
if (!root)
return NULL;
RopeTree *new_tree = malloc(sizeof(*new_tree));
DIE(!new_tree, "New tree malloc failed");
new_tree->root = root;
return new_tree;
}
void printRopeNode(RopeNode* rn) {
if (!rn)
return;
if (!(rn->left) && !(rn->right)) {
printf("%s", rn->str);
return;
}
printRopeNode(rn->left);
printRopeNode(rn->right);
}
void printRopeTree(RopeTree* rt) {
if (rt && rt->root) {
printRopeNode(rt->root);
printf("\n");
}
}
void debugRopeNode(RopeNode* rn, int indent) {
if (!rn)
return;
for (int i = 0; i < indent; ++i)
printf("%s", " ");
if (!strcmp(rn->str, EMPTY))
printf("# %d\n", rn->weight);
else
printf("%s %d\n", rn->str, rn->weight);
debugRopeNode(rn->left, indent+2);
debugRopeNode(rn->right, indent+2);
}
int getNodeWeight(RopeNode *rt) {
if (!rt)
return 0;
if (!rt->left && !rt->right)
return rt->weight;
return (getNodeWeight(rt->left) + getNodeWeight(rt->right));
}
RopeTree* concat(RopeTree* rt1, RopeTree* rt2) {
RopeNode *new_root = makeRopeNode(my_strdup(EMPTY));
new_root->left = rt1->root;
new_root->right = rt2->root;
new_root->weight = getNodeWeight(rt1->root);
RopeTree *new_tree = makeRopeTree(new_root);
return new_tree;
}
// Recursive function to find the index
char __indexRope(RopeNode *rn, int idx) {
// If the weight isn't more than the given index
if (rn->weight <= idx && rn->right) {
return __indexRope(rn->right, idx - rn->weight);
}
// Only if the left node exists
if (rn->left) {
return __indexRope(rn->left, idx);
}
return rn->str[idx];
}
char indexRope(RopeTree* rt, int idx) {
if (rt->root) {
return __indexRope(rt->root, idx);
}
return 0;
}
char* search(RopeTree* rt, int start, int end) {
char *c = calloc(end - start + 1, sizeof(char));
for (int i = start; i < end; i++)
// The index has to be i - start
c[i - start] = indexRope(rt, i);
return c;
}
// Concatenantion of nodes
RopeNode* concat_n(RopeNode* rn1, RopeNode* rn2) {
RopeNode *new_root = makeRopeNode(my_strdup(EMPTY));
if (rn1 && rn2) {
// Asigning values and adresses to the new node
new_root->weight = rn1->weight;
new_root->left = rn1;
new_root->right = rn2;
}
return new_root;
}
// Function to copy the given tree
RopeNode *copy_tree(RopeNode *rn) {
if (!rn)
return NULL;
RopeNode* copy_node = makeRopeNode(my_strdup(rn->str));
copy_node->weight = rn->weight;
copy_node->left = copy_tree(rn->left);
copy_node->right = copy_tree(rn->right);
return copy_node;
}
void split_one(RopeNode* rn, int *idx) {
int i;
// Only if the nodes don't exist
if (rn->left == NULL && rn->right == NULL) {
if (*idx != 0) {
// Allocating memory for the strings
char *s1 = malloc(*idx + 1);
char *s2 = malloc(rn->weight - *idx + 1);
// Building the first string
for (i = 0; i < *idx; ++i)
s1[i] = (rn->str)[i];
s1[i] = '\0';
// Building the second string
for (i = *idx; i < rn->weight; ++i)
s2[i - *idx] = (rn->str)[i];
s2[i - *idx] = '\0';
// Emptying the node
free((void *)(rn->str));
rn->str = my_strdup(EMPTY);
// Creating 2 new nodes
// Those nodes have the strings
// created above
RopeNode *rn1 = makeRopeNode(s1),
*rn2 = makeRopeNode(s2);
// Linking them to the given
// node of the rope
rn->left = rn1;
rn->right = rn2;
// The weight is only the left's
rn->weight = getNodeWeight(rn->left);
}
return;
}
int weight = getNodeWeight(rn->left);
if (*idx < weight) {
// Recursivelly calling the function
split_one(rn->left, idx);
} else {
// Substracting the weight
*idx = *idx - weight;
// Recursivelly calling the function
split_one(rn->right, idx);
}
}
RopeNode* split_two(RopeNode* rn, int *idx, char c) {
int weight;
// Only if the nodes exist
if (rn->right && rn->left) {
// If the first character of the right node's string
// is equal to the given character and the
// first character of the left node's string
// is not equal to the given character
if ((rn->right->str)[0] == c && (rn->left->str)[0] != c) {
RopeNode* right_copy = rn->right;
// The right node has to be empty
rn->right = NULL;
// Returning the copy
return right_copy;
} else if ((rn->left->str)[0] == c) {
// If the first character of the left node's string
// is equal to the given character
// Creating copies
RopeNode* right_copy = rn->right;
RopeNode* left_copy = rn->left;
// The nodes has to be empty
rn->right = NULL;
rn->left = NULL;
// Recursivelly calling the function
// with the copies created above
return concat_n(left_copy, right_copy);
}
// The weight is only the left node's weight
weight = getNodeWeight(rn->left);
if (*idx >= weight) {
*idx = *idx - weight;
return split_two(rn->right, idx, c);
} else if (*idx < weight) {
RopeNode *right_two = rn->right;
rn->right = NULL;
// If the index is lower than thw weight
// the concat function is called
// with the split function between
// the left node, the index and the given character c
// and the right copy
return concat_n(split_two(rn->left, idx, c), right_two);
}
}
return NULL;
}
SplitPair split(RopeTree* rt, int idx) {
SplitPair pair;
int idx_copy;
char index;
idx_copy = idx;
// Creating a new root
RopeNode* new_root = copy_tree(rt->root);
// If the index is higher than the weight of the new root
if (idx >= getNodeWeight(new_root)) {
pair.left = new_root;
pair.right = makeRopeNode(my_strdup(EMPTY));
return pair;
}
index = indexRope(rt, idx_copy);
// First split
idx_copy = idx;
split_one(new_root, &idx_copy);
// Second split
idx_copy = idx;
pair.right = split_two(new_root, &idx_copy, index);
pair.left = new_root;
return pair;
}
// Creating a strdup function
char* my_strdup(const char* str)
{
int len;
char* dup;
len = strlen(str) + 1;
dup = malloc(len);
if(!dup)
return NULL;
dup = strcpy(dup, str);
dup[len - 1] = '\0';
return (dup);
}
RopeTree* insert(RopeTree* rt, int idx, const char* str) {
// One split and a concatenation
if(!rt)
return NULL;
SplitPair pair = split(rt, idx);
RopeNode *new_node = makeRopeNode(str),
*new_root = concat_n(pair.left, new_node),
*final_node = concat_n(new_root, pair.right);
RopeTree *new_tree = makeRopeTree(final_node);
return new_tree;
}
RopeTree* delete(RopeTree* rt, int start, int len) {
// Two splits and a concatenation
if(!rt)
return NULL;
SplitPair pair_one = split(rt, start),
pair_two = split(rt, start + len);
RopeNode *new_root = concat_n(pair_one.left, pair_two.right);
RopeTree *new_tree = makeRopeTree(new_root);
return new_tree;
}