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
Sanfoundry Global Education & Learning Series – 1000 Java Programs.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Related Posts:
- Check Computer Science Books
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs
- Check Data Structure Books
- Practice Computer Science MCQs