Java Program to Implement Rope

This is a Java Program to implement Rope. A rope is a data structure for storing and manipulating a very long string.

Here is the source code of the Java program to implement Rope. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 * Java Program to Implement Rope
 **/
 
import java.util.Scanner;
 
/** Class RopeNode **/
class RopeNode
{
    RopeNode left, right;
    String data;
    int weight;    
    /** Constructor **/
    public RopeNode(String data)
    {
        this.data = data;
        left = null;
        right = null;
        weight = data.length();
    }
    /** Constructor **/
    public RopeNode()
    {
        data = null;
        left = null;
        right = null;
        weight = 0;
    }
}
 
/** Class Rope **/
class Rope
{
    RopeNode root;
 
    /** Constructor **/
    public Rope()
    {
        root = new RopeNode("");
    }
    /** Function to clear rope **/
    public void makeEmpty()
    {
        root = new RopeNode("");
    }
    /** Function to concat an element **/
    public void concat(String str)
    {
        RopeNode nptr = new RopeNode(str);
        RopeNode newRoot = new RopeNode();
        newRoot.left = root;
        newRoot.right = nptr;
        newRoot.weight = newRoot.left.weight ;
        if (newRoot.left.right != null)
            newRoot.weight += newRoot.left.right.weight;
        root = newRoot;
    }
    /** Function get character at a paricular index **/
    public char indexAt(int ind)
    {
        RopeNode tmp = root;
        if (ind > tmp.weight)
        {
            ind -= tmp.weight;
            return tmp.right.data.charAt(ind);
        }
        while (ind < tmp.weight)
            tmp = tmp.left;
        ind -= tmp.weight;
        return tmp.right.data.charAt(ind);            
    }
    /** Function get substring between two indices **/
    public String substring(int start, int end)
    {
        String str = "";
        boolean found = false;
        RopeNode tmp = root;
        if (end > tmp.weight)
        {
            found = true;
            end -= tmp.weight;
            if (start > tmp.weight)
            {
                start -= tmp.weight;
                str = tmp.right.data.substring(start, end);
                return str;
            }
            else
                str = tmp.right.data.substring(0, end);            
        }        
        if (!found)
        {
            while (end <= tmp.weight)
                tmp = tmp.left;
            end -= tmp.weight;
            if (start >= tmp.weight)
            {
                start -= tmp.weight;
                str = tmp.right.data.substring(start, end) + str;
                return str;
            }
            str = tmp.right.data.substring(0, end);            
        }    
        tmp = tmp.left;
        while (start < tmp.weight)
        {
            str = tmp.right.data + str;
            tmp = tmp.left;
        }
        start -= tmp.weight;
        str = tmp.right.data.substring(start) + str;    
 
        return str;        
    }
    /** Function to print Rope **/
    public void print()
    {
        print(root);
        System.out.println();
    }
    private void print(RopeNode r)
    {
        if (r != null)
        {
            print(r.left);
            if (r.data != null)
                System.out.print(r.data);
            print(r.right);
        }
    }    
}
 
/** Class RopeTest **/
public class RopeTest
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        /** Creating object of Rope **/
        Rope r = new Rope(); 
        System.out.println("Rope Test\n");          
        char ch;
        /**  Perform rope operations  **/
        do    
        {    
            System.out.println("\nRope Operations\n");
            System.out.println("1. concat ");
            System.out.println("2. get character at index");
            System.out.println("3. substring");
            System.out.println("4. clear");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter string to concat");
                r.concat( scan.next() );                     
                break;                          
            case 2 : 
                System.out.println("Enter index");
                System.out.println("Character at index = "+ r.indexAt(scan.nextInt()));
                break;                         
            case 3 : 
                System.out.println("Enter integer start and end limit");
                System.out.println("Substring : "+ r.substring( scan.nextInt(), scan.nextInt() ));
                break;                                          
            case 4 :  
                System.out.println("\nRope Cleared\n");
                r.makeEmpty();
                break;            
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /**  Display rope  **/ 
            System.out.print("\nRope : ");
            r.print();
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y'); 
    }
}

Rope Test
 
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
1
Enter string to concat
rope
 
Rope : rope
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
1
Enter string to concat
is
 
Rope : ropeis
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
1
Enter string to concat
a
 
Rope : ropeisa
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
1
Enter string to concat
datastructure
 
Rope : ropeisadatastructure
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
2
Enter index
5
Character at index = s
 
Rope : ropeisadatastructure
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
2
Enter index
13
Character at index = r
 
Rope : ropeisadatastructure
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
3
Enter integer start and end limit
5 15
Substring : sadatastru
 
Rope : ropeisadatastructure
 
Do you want to continue (Type y or n)
 
y
 
Rope Operations
 
1. concat
2. get character at index
3. substring
4. clear
4
 
Rope Cleared
 
 
Rope :
 
Do you want to continue (Type y or n)
 
n