Friday, April 24, 2009

XML as objects in OOPs

I always wondered how can we represent XML tags using code. And, the answer what I came out with was pretty easy and neat.

Each XML begins with a root node and has some nested tags embedded in them. Those tags has more nested tags embedded in between them. Thus they follow a tree like structure.
Also, every node has some attributes associated with it. They are nothing but key value properties of that node.
Consider an XML data shown above

Thus we can represent, each node say root1 as
XML root1 = new XML("root1")
root1.addAttribue(key1,value1)
root1.addAttribue(key2,value2)

same can be done for sub-root and root2. But, as sub-root are embedded in root2. We can add another line
root2.addChild(sub-root)
root2.addChild(sub-root)

Now, finally root1 and root2 can be added as children to root.
Thus completing the whole tree structure.

Refer to this page for code and detaills.



-----------
Kapil Dalwani

Monday, April 6, 2009

Sorting .....Comparison Sort

Sorting is a technique which is defined such as,

if A[i] and A[j] are two elements of an array, then the array is sorted if for all i and j

A[i] <= A[j] for all i < style="font-weight: bold;">

QuickSort.

You can find the algorithm of QuickSort here on Wikipedia.

I would just touchbase on algo.

QuickSort(int start, int end, int * arr){

if(start < end){
int q = partition(start,end,arr);
QuickSort(start,q-1,arr)
QuickSort(q+1,end,arr)
}
}
This is a recursive defintion of QuickSort. The main function is the partition which returns the index of pivot element. The function runs in a way that if Pivot=arr[end] is the element initially chosen as the pivot. Then at the end of function, the pivot is placed at its correct position q. All the elements with index less than q are smaller than Pivot and all elements greater than q are greater than Pivot. During the entire course of algorithm, Pivot at index q doesn't changes its position.

Iterative version

QuickSort(int start,end, arr){

bounds = {start,end}
pushToStak(bounds);

while(notEmpty(){
bound = popStack()
while(bound.lowerVal < q =" partition(lower,upperval,arr)"> end-1){
Tempbounds = (start,q-1)
bound.lowerVal = q+1
else{
Tempbounds = {q+1,end)
bound.upperVal = q-1
}
pushStack(Tempbounds )
bound
}
}
}

You can find the C implementation of this code on code.goggle.com.
Download QuickSort.

Thursday, April 2, 2009

Binary Tree Traversal

There are 3 basic ways to traverse a Binary TREE:-
a) PreOder
b) InOrder
c) PostOrder

And,its very easy to define them recursively

PreOrder:-

a)Visit the Root
b)Visit the Left Sub tree in PreOrder
c)Visit the Right Sub tree in Preorder.

Same can be done for InOrder and Postorder where Root is visited at stage b) and stage c) respectively.

Here is a sample code
PreOrder ( Tree tree){

if(tree!=null){
printf(tree->info);
PreOrder(tree->left);
PreOrder(tree->right);
}
}

Writing recursive definition is easy,
writing iterative version is bit tricky.

You can find the iterative version of all three here. I have posted them at code.google.com.

Feel free to use it and send me your suggestion/comments/feedback.

Cheers,
Kapil Dalwani

Wednesday, April 1, 2009

Why Let-Them-C ???

Well, to most of the India students who have written some piece of C code, this title would sound similar. Yes, I wanted it to name it "Let Us C" from the famous C language book authored by Yashwant Kanitkar. But, I ddin't wanted to go into legal issues and decided to name it as "Let Them C".. !

I will try to cover problems, suggestion, code etc related to technical problems faced by me during professional experience. So, its a blog meant only for Coders...other can do a void return.

Feel free to contribute, hack, code etc this website.

Cheers,
Kapil Dalwani

P.S. why is the background black?? Well just my way of showing that I care for Mother Earth....