In C++

Your task is to design, implement, test, and document the following methods for the Rope class. The notation S[i, j] is used to represent the substring that begins at index i and ends at index j. Assume as well that the maximum size of a leaf substring is 10.

Rope( ) : Create an empty rope (1 mark).

Rope(string S) : Create a balanced rope from a given string S (8 marks).

Rope Concatenate(Rope R1, Rope R2) : Return the concatenation of ropes R1 and R2 (4 marks).

void Split(int i, Rope R1, Rope R2) : Return the two ropes split at index i (10 marks).

void Insert(string S, int i) : Insert string S at index i (6 marks).

void Delete(int i, int j) : Delete the substring S[i, j] (6 marks).

string Substring(int i, int j) : Return the substring S[i, j] (8 marks).

char CharAt(int i) : Return the character at index i (4 marks).

int IndexOf(char c) : Return the index of the first occurrence of character c (4 marks).

void Reverse() : Reverse the string represented by the current rope (6 marks).

int Length() : Return the length of the string (1 mark)

. string ToString() : Return the string represented by the current rope (4 marks).

void PrintRope() : Print the augmented binary tree of the current rope (4 marks).

Optimizations The ideal rope maintains a height of O(log n), but that can be quite a challenge. To help limit the height of the tree, try to implement the following optimizations. 1. After a Split, compress if possible the path back to the root (4 marks). 2. Combine left and right siblings whose total string length is 5 or less (4 marks). 3. Rebalance the rope periodically (4 marks).