CSCI-1200 Data Structures

Homework 8 — Ropes

In this assignment we will be implementing a partial and modified version of a Rope. Due to our modifications, other sources may not use the same terminology or may describe implementation details that are not

relevant to our HW8 implementation – in fact even Wikipedia will differ on some specifics. For this reason

you should avoid looking at code or online resources about ropes, and cannot use someone else’s code in this

assignment. Lecture/lab code is okay to use though. You should read the entire assignment before beginning

your work. You should also make sure you understand the basic concepts discussed at the end of Lecture 18.

The idea behind a rope is that normally, inserting into and erasing from the middle of a string (character

array) is very inefficient, for the same reasons that these operations are slow on an STL vector. Instead, we

can represent a string inside a binary tree where each node has a weight (a non-negative integer) and a value

(zero or more characters). Any node that is not a leaf will have an empty string as its value – only the leaves

hold pieces of the string. The weight of a leaf is the length of its value. The weight of any non-leaf is the

number of characters in the leaves of its left subtree.

Our assignment notably does not implement operator– for rope iterators, nor does it implement erase() or

insert(). Much like an STL map or set, ropes are best implemented with a balanced tree. However, since

we have not discussed balanced trees and this assignment will be large enough without such details, we will

ignore the balanced tree requirement. The README has a section where you will discuss performance and

the impact of not having a balanced tree on performance.

Provided Files

We have provided several files which contain further instructions. main.cpp contains some simple tests in

BasicTests() for various functions you will need to write, and the expected output is shown in output basic.txt.

Your own additional testing should be added to StudentTests(). We have also given you Rope.h which you

can modify as you see fit, Rope student.cpp which has the functions you need to write, and Rope provided.cpp

which you should not change at all. We will use our own copy of Rope provided.cpp when testing on Submitty.

You can add additional functions to the .h file and Rope student.cpp – we will always use your version of

these two files. Pay particular attention to the comments in Rope student.cpp!

Hints

You may find it beneficial to borrow code from our partial implementation of the ds set class and associated

helper classes. Focus on writing the destructor first and then you can start working through BasicTests()

step by step. Carefully consider whether it makes more sense to do a function iteratively or recursively.

Keep in mind for index() you must write an iterative version. You may want to add some private helper

functions to the Rope class. The most challenging function will be split(), and breaking the work up can

make debugging easier. You might also want to call the provided print functions a lot when debugging to

quickly visualize your rope.

Submission

Submit your main.cpp, Rope.h, Rope student.cpp, and README.txt. Dr. Memory will be used on this

assignment and you will be penalized for leaks and memory errors in your solution. If you get at least 3

points on test case 13 by the end of Wednesday, you can submit on Friday without being charged a late day.

Please remember that all submissions are still due by the end of Saturday.

concat()

concat() adds the right-hand (rhs) rope to the left-hand (lhs) rope by creating a new root. In our case, this

is written as lhs.concat(rhs).

2 4

na me_i

2

6

6

3

Hello_ my_

9

left root right root

new root

Starting with two Ropes, left and right we do the

following: (Keep in mind we may need to copy the

right subtree, look in the provided code for clues to

the correct behavior for our case!)

1. Create a new node which will be the new root

2. Connect it to the root of the left rope and update

weight

3. Connect it to the root of the right rope

4. Set the new node to be the root

index()

index(i) for Ropes works like operator[i] would for a string or vector, it returns the i

th character, with

the first character being at i = 0.

The blue arrows/text show the search and how i

changes for i = 9.

22

9

6

6

3

2 6 4 1

2 1

6

my_

na me_i s

Hello_

9

0

0

0

[0]

_Simon

To find the character at index i = 9 (assuming we start

at index 0):

1. Start at the root and decide to go left since the

root’s weight is 22 meaning the left subtree has

indices 0-21

2. Next, decide to go right since the current node’s

weight is 9, meaning the left subtree has indices

0-8. Subtract the root’s weight (9) from i, so now

i = 0. (Anytime we go right we must subtract

the weight of the current node. Think about

why.)

3. Since i = 0 we will always go left. A search will

continue making choices to go left or right until it

hits a leaf. (You can consider why this is always

correct.)

4. At the leaf, return the character at index i, in

our case that’s “na”[0] which is ‘n’.

See next page for split() details

We have adopted a couple examples from the Wikipedia article on ropes. We provide these links only to comply with the

Creative Commons Attribution-Share Alike 3.0 Unported license. Remember that the Wikipedia article describes some functions

differently and you should not view it for homework assistance: [1] [2] [3]

2

split()

4

X

X

1

2

9

6

6

3

2

2

my_

na

Hello_

2

22

9

6

6

3

2 6 1

2 1

6

my_

na s

Hello_

1

m e_i

3

1

11

9

6

6

3

2 6 4 1

2 1

my_

na me_i s

Hello_

11

2

_Simon

22

9

6

6

3

2 6 4 1

2 1

6

my_

na me_i s

Hello_

_Simon

_Simon

me_i

4 1 6

1

s _Simon

To split, we first find the index we want to split

at. Remember that for a split at index i, indices 0

through (i-1) stay in the left rope, and everything

else goes to the right.

If i is in the middle of a node’s value, then we have

to cut the node into two pieces. For example, if

we chose i = 12, then we would want the “e” in

“me i” to be the first part of the new righthand

rope. But this is in the middle of a leaf. To fix

this, give the leaf two new children, a left child

with “m”, and a right child with “e i”, and then

update weights accordingly. We can then use the

new “e i” leaf to start our actual split.

In the lower example, we consider

i = 11 so that we do not have to deal with this.

1. First we find i = 11 which is the first letter

in “me i”. Following the rules of index(), i

will have been adjusted to be 0. So the leaf

will not need to be split.

2. Next, we disconnect the leaf from the

original (lefthand) rope.

3. Going up the rope, for any node where the

right subtree will completely be in the new

(righthand) rope, we also disconnect the

right child from the original rope.

4. Going from left to right we concatenate the

root of each subtree that we disconnected,

since they will all be small ropes. In this

example we split the X1 and then X2

, so

we just concat(X1

, X2

).

5. Finally, update the weights of all nodes

(unless you did this when you were disconnecting/concatenating).

3

CSCI-1200 Data Structures

# Homework 8 — Ropes

Original price was: $35.00.$30.00Current price is: $30.00.