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.

  1. /**
  2.  * Java Program to Implement Rope
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class RopeNode **/
  8. class RopeNode
  9. {
  10.     RopeNode left, right;
  11.     String data;
  12.     int weight;    
  13.     /** Constructor **/
  14.     public RopeNode(String data)
  15.     {
  16.         this.data = data;
  17.         left = null;
  18.         right = null;
  19.         weight = data.length();
  20.     }
  21.     /** Constructor **/
  22.     public RopeNode()
  23.     {
  24.         data = null;
  25.         left = null;
  26.         right = null;
  27.         weight = 0;
  28.     }
  29. }
  30.  
  31. /** Class Rope **/
  32. class Rope
  33. {
  34.     RopeNode root;
  35.  
  36.     /** Constructor **/
  37.     public Rope()
  38.     {
  39.         root = new RopeNode("");
  40.     }
  41.     /** Function to clear rope **/
  42.     public void makeEmpty()
  43.     {
  44.         root = new RopeNode("");
  45.     }
  46.     /** Function to concat an element **/
  47.     public void concat(String str)
  48.     {
  49.         RopeNode nptr = new RopeNode(str);
  50.         RopeNode newRoot = new RopeNode();
  51.         newRoot.left = root;
  52.         newRoot.right = nptr;
  53.         newRoot.weight = newRoot.left.weight ;
  54.         if (newRoot.left.right != null)
  55.             newRoot.weight += newRoot.left.right.weight;
  56.         root = newRoot;
  57.     }
  58.     /** Function get character at a paricular index **/
  59.     public char indexAt(int ind)
  60.     {
  61.         RopeNode tmp = root;
  62.         if (ind > tmp.weight)
  63.         {
  64.             ind -= tmp.weight;
  65.             return tmp.right.data.charAt(ind);
  66.         }
  67.         while (ind < tmp.weight)
  68.             tmp = tmp.left;
  69.         ind -= tmp.weight;
  70.         return tmp.right.data.charAt(ind);            
  71.     }
  72.     /** Function get substring between two indices **/
  73.     public String substring(int start, int end)
  74.     {
  75.         String str = "";
  76.         boolean found = false;
  77.         RopeNode tmp = root;
  78.         if (end > tmp.weight)
  79.         {
  80.             found = true;
  81.             end -= tmp.weight;
  82.             if (start > tmp.weight)
  83.             {
  84.                 start -= tmp.weight;
  85.                 str = tmp.right.data.substring(start, end);
  86.                 return str;
  87.             }
  88.             else
  89.                 str = tmp.right.data.substring(0, end);            
  90.         }        
  91.         if (!found)
  92.         {
  93.             while (end <= tmp.weight)
  94.                 tmp = tmp.left;
  95.             end -= tmp.weight;
  96.             if (start >= tmp.weight)
  97.             {
  98.                 start -= tmp.weight;
  99.                 str = tmp.right.data.substring(start, end) + str;
  100.                 return str;
  101.             }
  102.             str = tmp.right.data.substring(0, end);            
  103.         }    
  104.         tmp = tmp.left;
  105.         while (start < tmp.weight)
  106.         {
  107.             str = tmp.right.data + str;
  108.             tmp = tmp.left;
  109.         }
  110.         start -= tmp.weight;
  111.         str = tmp.right.data.substring(start) + str;    
  112.  
  113.         return str;        
  114.     }
  115.     /** Function to print Rope **/
  116.     public void print()
  117.     {
  118.         print(root);
  119.         System.out.println();
  120.     }
  121.     private void print(RopeNode r)
  122.     {
  123.         if (r != null)
  124.         {
  125.             print(r.left);
  126.             if (r.data != null)
  127.                 System.out.print(r.data);
  128.             print(r.right);
  129.         }
  130.     }    
  131. }
  132.  
  133. /** Class RopeTest **/
  134. public class RopeTest
  135. {
  136.     public static void main(String[] args) 
  137.     {
  138.         Scanner scan = new Scanner(System.in);
  139.         /** Creating object of Rope **/
  140.         Rope r = new Rope(); 
  141.         System.out.println("Rope Test\n");          
  142.         char ch;
  143.         /**  Perform rope operations  **/
  144.         do    
  145.         {    
  146.             System.out.println("\nRope Operations\n");
  147.             System.out.println("1. concat ");
  148.             System.out.println("2. get character at index");
  149.             System.out.println("3. substring");
  150.             System.out.println("4. clear");
  151.  
  152.             int choice = scan.nextInt();            
  153.             switch (choice)
  154.             {
  155.             case 1 : 
  156.                 System.out.println("Enter string to concat");
  157.                 r.concat( scan.next() );                     
  158.                 break;                          
  159.             case 2 : 
  160.                 System.out.println("Enter index");
  161.                 System.out.println("Character at index = "+ r.indexAt(scan.nextInt()));
  162.                 break;                         
  163.             case 3 : 
  164.                 System.out.println("Enter integer start and end limit");
  165.                 System.out.println("Substring : "+ r.substring( scan.nextInt(), scan.nextInt() ));
  166.                 break;                                          
  167.             case 4 :  
  168.                 System.out.println("\nRope Cleared\n");
  169.                 r.makeEmpty();
  170.                 break;            
  171.             default : 
  172.                 System.out.println("Wrong Entry \n ");
  173.                 break;   
  174.             }
  175.             /**  Display rope  **/ 
  176.             System.out.print("\nRope : ");
  177.             r.print();
  178.  
  179.             System.out.println("\nDo you want to continue (Type y or n) \n");
  180.             ch = scan.next().charAt(0);                        
  181.         } while (ch == 'Y'|| ch == 'y'); 
  182.     }
  183. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.