String Reversal in Java using StringBuffer, toCharacterArray and Recursion

Using StringBuffer Class

new StringBuffer(name).reverse().toString()

Using CharArray and StringBuilder

        public static String charReverse(String data){
		StringBuilder sb = new StringBuilder();
		char[] ca = data.toCharArray();
		
		for (int i=data.length()-1; i>=0;i--){
			sb.append(ca[i]);
		}
		return sb.toString();
	}

Using Recursion

public static String recursiveReverse(String data){
		
		if (data.length() < 2)
			return data;
		
		return recursiveReverse(data.substring(1)) + data.charAt(0);
	}

StringReversal Class

public class StringReversal {

	public static void main (String[] args){
		String name = "linuxjunkies";
		
		System.out.println("StringBuffer: " + new StringBuffer(name).reverse().toString());
		System.out.println("CharacterArray: " + charReverse(name));
		System.out.println("Recursion: " + recursiveReverse(name));
	}
	
	public static String charReverse(String data){
		StringBuilder sb = new StringBuilder();
		char[] ca = data.toCharArray();
		
		for (int i=data.length()-1; i>=0;i--){
			sb.append(ca[i]);
		}
		return sb.toString();
	}
	
	public static String recursiveReverse(String data){
		
		if (data.length() < 2)
			return data;
		
		return recursiveReverse(data.substring(1)) + data.charAt(0);
	}
}

The Output

StringBuffer: seiknujxunil
CharacterArray: seiknujxunil
Recursion: seiknujxunil

Data Structures using Java Part 8: Heaps and Stack, Binary Search, Recursion, Scope, Parameter passing

The Stack and the Heap
————————–
The heap stores all objects, including arrays and all the class variables.
The stack stores all the local variables including parameters.

When a method is called Java creates a stack frame (or called an activation record). It stores the parameters and the local variables. The JVM maintains an entire stack of “stack frames”. When the method completes, its stack frame is erased. Most OS give enough space for a few thousands of stack frames.

Thread.dumpstack()
———————-
This method when called will print out the contents of the stack frame. Its present in the java.lang package and so doesnt need to be imported.

Parameter passing
——————–
In Java , the parameters are passed by value. That is they are copied.

class IntBox{

	static void donothing(int x){
		x = 2;
	}

	public int i;

	static void set3(Intbox ib){
	ib.i = 3;
	}

	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
}

// called
	static void donothing(int x){
		x = 2;
	}

// calling
	int a = 1;
	donothing(a);

The variable a will be created in present stack frame. When the function donothing() is called, a new stack frame is created on top of the previous frame and the variable x resides in this frame. Note that no change happens to a after the function completes. The frame is erased once the function exits.

When the parameter is a reference, the reference is copied and not the object it is pointing to.

//called

	static void set3(Intbox ib){
	ib.i = 3;
	}

//calling
	IntBox b = new IntBox();
	set3(b);

In the local stack variable b is created. The object is created in heap with the variable i inside it. b points to object. set3() creates a parameter ib, both in new stack frame and then ib points to object pointed by b. The value of the object is changed by ib which is reflected on b, since both point to the same thing.

// called
	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
//calling
	IntBox b = new IntBox();
	badSet4(b);

The difference here is that now a new object is created by the setBad() function and its value of ib is being set. The old heap object still retains its value. This happens to be a common programming error.

Binary Search
—————-
Used to search a sorted array. Suppose we want to search in a sorted int array. In this example , we try to find whether the variable “find” exists in the array, if so then return its array index. If not, return failure. This is going to be a predefined constant like FAILURE = -1. I have used a recursive algorithm.

Binary Search Procedure

// Binary Search
public static final int FAILURE = -1; // set as -1 because no index is less than 0 and final implies constant

public static int binarySearch(int[] i, int left, int right, int find){

	if (left > right)				// this is the base case; exit if the case.
		return FAILURE;

	int mid = (left + right)/2;          // find the middle element ; base case

	if (find = i[mid]){
		return mid;			// found!
	}else if (find < i[mid]){		// less implies the left subarray
		return binarySearch(i, left, mid -1, find);
	}else {					// more implies the right subarray
		return binarySearch(i, mid + 1, right,  find);
	}
	}
}

Recursion base cases:
1. if find = middle element: return index
2. if subarray is of length 0, nothing is there to search, return 0.

How fast is it?
Takes log n (base 2) recursive binarySearch calls.

Scope and Recursion
———————-
Scope of a variable : is portion of the program , actual lines of code, that can access the variable.
1. Class variables: (static fields) are in scope everywhere in the class except where shadowed by local variables. (like when using “this”)
2. Fully qualified class variable:For example “System.out” is not ambiguous. They are in scope everywhere in the class and are not shadowed. If public, they are in scope in ALL classes.
3. Instance variables: These are in scope in methods that are not static, except when shadowed.
4. Fully qualified instance variable: For example: “this.name” Same as 2.
5. Local variables: which includes parameters, only in scope in the block that defines them.