Remove from Array : Java Quickie

lets say you have a problem . You have an array of N numbers . You want to remove the i th number . Then you need a new array not containing the j th number . You are using java . How can you do it ??

Here 's a quickie:

int[] result = null;

result = new int[n-1];
if(i > 0 ) System.arraycopy(array,0,result,0,i);
if(i+1 < n ) System.arraycopy(array,i+1,result,i,n-1-i);

}

This is quick way of removing the element you need and getting a new array devoid of the removed number .

Thnking in Heaps : Algorithms

An interative version of max-Heap :

void iter_maxHeapify(int * a,int rootIndex,int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = left(rootIndex);

for(int largest = rootIndex;
(leftIndex < heapLength) || (rightIndex < heapLength);
leftIndex = left(rootIndex),rightIndex = right(rootIndex)){

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(rootIndex != largest){
swap(a[largest],a[rootIndex]);
rootIndex = largest;
}
}

}

Building the Heap:

void buildMaxHeap(int * a,int heapLength){
for(int i = heapLength/2;i >=0;i--){
maxHeapify(a,i,heapLength);
}
}


Sorting a heap:

void heapSort(int * a ,int heapLength){
buildMaxHeap(a,heapLength);
for(int i = 0;i < heapLength;i++){
swap(a[i],a[heapLength-1]);
maxHeapify(a,1,heapLength-i-1);
}
}

Tweaking JDT : eclipse

To create a new Java Class/Interface using JDT you can use the following code :

IJavaproject prj;
IPackage package;

prj.createType(package, "your class body");

To find subclasses of a given type using JDT use :

IType type = prj.findType("class name");
ITypeHierarchy typeHierarchy = type.newTypeHierarchy(prj,new NullProgressMonitor());
IType[] subclasses = typeHierarchy.getAllSubtypes(prj);



To check if the given class aka IType is part of this project

IType type;

IResource resource = type.getUnderlyingResource();

boolean isPartOfClass = resource.getProject().equals(project.getProject());

Marker Resolutions for markers : Eclipse

In Eclipse it is possible to associate marker resolutions with markers . This is more commonly known as Quick Fixes also evoked by using the key combination Ctrl + 1.

You need to implement the extension point with id :

"org.eclipse.ui.markerResolution"

for the markerType attribute under that extension point specify the marker id
you want to associate this resolution with .

Then in the "class" attribute specify the class that implements the MarkerResolutionGenerator

The world of wide characters aka Unicode

Wide characters aka unicode characters are characters that occupy 16 bits per character .
In C we have a header file specifically for that .



that contains special data type for that

wchar_t

wchar_t * text = L"Hello";

is used to tell the compiler that it should use 16 bit aka wide variants of characters.

strlen for wide characters becomes wcslen .

To take care of these problems windows provides TCHAR.H

it contains many functions starting with _t , like. ..

_tprintf


by defining _UNICODE

like

#define _UNICODE

its possible to use 16 bit / 8 bit versions of functions without much verbosity .

the same _t functions then correctly map on to their 8 bit and 16 bit counter parts.

Fnding markers in a workspace : eclipse

If you have a marker or you know a marker id :

let the id be : org.my.marker

then all markers of that type can be easily found . The way to found those markers is :

IWorkspaceRoot root = ResourcePlugin.getWorkspace().getRoot();
root.findMarkers("org.my.marker",false,IResource.DEPTH_INFINITE);

To create a marker :

getProject().createMarker("org.my.marker",false,IResource.DEPTH_INFINITE);

generally since workspace changes are expensive , an IWorkspaceRunnable should be used
to batch many workspace operations together .

IWorkspaceRunnable runnable = new IWorkspaceRunnable(){
public void run(IProgressMonitor monitor) {
IMarker marker = resource.createMarker(markerId);
setAttributes(marker);

}

};


the setAttributes method sets the marker . This generally boild down to populating a hashtable
and setting it .

resource.getWorkspace().run(runnable , null);

An imageProvider can be specified in the marker definition to define an image for the marker .

Overloading the && , || , " , " operators : C++

&& , || and comma operator in C++ are very useful . && and || are useful in short circuiting code .
Now when you overload these operator at the global level or at the member level . Then at that case

an expression like

(exp1 && exp2)

gets transformed into something like

(exp1.operator&&(exp2))

that being the case , both the arguments exp1 and exp2 are evaluated . Hence since we are not
sure in which order the arguments are evaluated , short circuiting is thrown out of the window.

So commonsense says it makes sense not to overload the && , || and the comma operator .

Little Sugar (Trees : relations)

A complete binary tree has odd number of nodes .

Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree

The number of internal nodes + 1 = number of leaves

number of internal nodes = number of leaves - 1

n = number of nodes

n = number of leaves + number of internal nodes

n +1 = 2 * number of leaves

number of leaves = (n+1)/2

The number of total nodes upto height h :

= pow(2,h+1) - 1

The number of nodes for any binary tree at height (h) :

= ceil(n / pow(2,h+1))

Little Sugar (Trees : relations)

A complete binary tree has odd number of nodes .

Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree

The number of internal nodes + 1 = number of leaves

number of internal nodes = number of leaves - 1

n = number of nodes

n = number of leaves + number of internal nodes

n +1 = 2 * number of leaves

number of leaves = (n+1)/2

type conversions : C++

Implicit type conversions in C++ can be quite problematic . To take care of type conversion issues , C++ provides us with a simple mechanism .

use the explicit keyword .

so for a class like Array

class Array{

public:
explicit Array(int size){
...
}

};

so by using the explicit keyword in this manner , you tell the compiler to use the constructor only
when explicit object construction is taking place.

another way around the explicit keyword is :

class Array{
public:
class ArraySize{
public:
ArraySize(int size)
this->size = size;
}

private:
int size;
};

Array(ArraySize size){
...
}
};

So by using the nested public ArraySize class in this manner , you 'll see that even if the compiler makes implicit type conversions for cases like

Array a(10);

the integer 10 is correctly transformed to ArraySize and the constructor having ArraySize as a parameter is called .

The beauty of this last technique is that it works in many cases , cause the compiler is allowed to make 1 implicit type conversion but now two.

Default Constructors : C++

Just imagine if your class does not have a default constructor and infact has one that accepts a parameter . In that case few things might not be possible . To illustrate

class Piece{
public:
Piece(int n);

};


Things like these will not work

Piece pieces[10];

Why?? -> cause u don t have a default constructor and trying to create an array of 10 piece instances just tries to call exactly that for every one of them .

Piece * pieces = new Piece[10];

wont work.

How to get it working :

Piece pieces[] = {
Piece(1),
Piece(2),
Piece(3)
};


Another way to get it working would be :

Piece * pieces[10];

: here you are just declaring an array of 10 Piece pointers;

Or Piece* *pieces = new Piece*[10];

But you still need to initialize all the pointers like this :

for(int i = 0;i < 10;i++){ pieces[i] = new Piece(i); }

Another way of initializing accomplishing this would be :

void * memory = operator new[](10 * sizeof(Piece));

this will create memory for 10 piece objects . Now we can go an and make the memory more specific to Piece :

Piece * pieces = static_cast<piece*>(memory);

Now that pieces points to memory for Piece , lets initialize the pieces with code like

for(int i = 0;i < 10;i++){ new(&pieces[i]) Pieces(i); }

Though this arcane technique will get the job done . It seriously is arcane . Not only that it also has the disadvantage of boilerplate code like this :

for(int i = 9;i >= 0;i--){
pieces[i].~Piece();
}

operator delete[] memory;

If we do not follow the 1st approach , we see that what problems we can face . A small hack to get around this problem would be :

class Piece{
public:
Piece(int n = Piece::UNDEFINED);
private:
static const int UNDEFINED;
};


const int Piece::UNDEFINED = -1;

Hello Windows Facts

windows.h is the mother of all other header files in windows . It includes other header files .

Windef.h => basic type defintions

winnt.h => type definitions for unicode support.

winbase.h => kernel functions.

winusr.h => user interface functions

wingdi.h => graphics device interface functions.

WINAPI => is a naming convention like __stdcall .

Moving Patterns

If you have a layer of objects and each object in that layer shares a certain set of methods . Those methods can be moved in a common super type . This super type that is common for a whole layer is called a layer super type .

Remote Facade is a facade for objects that are not part of a given process address space , in other words whenever you need to access objects that line in other processes you should use a remote facade to encapsulate and operate on remote objects via the facade . The facade make a number of operation invisible and may also cache the most commonly use objects.

When ever data has to marshaled across processes boundaries and lot of data needs to sent . A Data Transfer Object can be used . The parameters are packed into a simple POJO called a DTO and marshaled . On the server side , the server used some sort of assembler to break the DTO and set the corresponding properties on domain objects.

Floating in a Tree

If you have a priority queue setup of many nodes. Lets say we want to bring the node with the highest value to the top . IN orther words if i have given a heap than how do i modify the heap so that the biggest element is always present at the root.

One simple logic can be . Given a root node of a subtree .

• Assume the root node is the largest node .
  
• Now compare the value of root node with left child and mark the one with the bigger value as biggest
• Then compare biggest with the right child now and make the bigger of the two as the new biggest.
• now repeat the above mentioned steps with the new largest node

In terms of code this looks like :

void maxHeapify(int * a,int rootIndex, int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = right(rootIndex);

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(largest != rootIndex){
swap(a[largest],a[rootIndex]);
maxHeapify(a,largest,heapLength);
}
}

The worst case time for floating a node to any another node depending on your optimization would be approximately equal to the height of the tree , which would generally result in something like ~ lg(N) . To give a counter example for a max Heap operating in a heap . lets give a value of 0 to the root , and let all the other nodes be 1 . In that case the program would go all the way down the heap till the last leaf .

casts in C++

C++ provides us with 4 types of casting mechanisms . Namely:

1. static_cast
2. const_cast
3. dynamic_cast
4. reinterpret_cast

static_cast

In C casting is done via () operator

int i = 7;
e.g double d = (double) i;

in c++ to do something like this one should use static_cast .
e.g double d = static_cast<double>(i);

const_cast

const_cast is used to remove constness of an object .

jump(Person * person);

Person p;
const Person& constPerson = p;

then some thing like this wont work.
jump(&constPerson) , cause jump expects a non const object . To fix this you would have to use something like this.

jump(const_cast<person*>(&constPerson));

dynamic_cast

This cast is used with inheritance hierarchies . Say to cast a between pointers or references of base classes to references or pointers of derived classes.

e.g

Mammal * mammal;

jump(dynamic_cast<person*>(mammal));

if there was a function like

jump(Person& person); then

we would have something like

jump(dynamic_cast<person&>(*mammal));

if the casting is not possible , the dynamic_cast mechaism throws an excetion or the result is null (This is implementation specific)

Little Sugar: C++ references

C++ references are a variant of const pointers that always point to something .

Now consider

string s1("abc");

string s2("def");

string & refTos1 = s1;

Now refTosi points to s1.

Even after refTos1 = s2. Its still points to s1 . But the value of s1 is now changed from "abc" to "def"

Little Sugar : Big Oh

Consider a scenario where you had a list of N numbers . Now say you have an algorithm that finds the does some sort of comparison . If comparison strategy used compares every element with all the succeeding elements . Then on an average the number of comparisons possible in different cases would be something like this :

(n) + (n-1) + (n-2) .... 1

for the 1 st case we have n comparisons
for the 1 st element we have n-1 comparisons
for the 2 nd element we have n-2 comparison .. and so on.

the sum is = ((n)*(n+1))/2 = O(n^2)

Java + meta programming framework == EMF

Meta programming is a popular buzz word these days . There is a framework for java , called EMF (Eclipse Modeling Framework ) that tries to add that support to java . The framework makes meta programming look like total crap . It overly complicates stuff to such a large extent that you just feel like just removing it from your project code.

So in short meta-programming in EMF + java = night mare :(

But on the other hand if you are building your domain layer . EMF is a pretty decent choice . It has in build support for a notification mechanism that allows you to listen to various model changes . So your GUI can become lightly couple to the domain layer and can become very responsive .

If other people have tried EMF , i would love to hear their experiences.

Little Sugar : Sequences

Given a sequence , the sum of elements from the i th position to the j th position can be easily found by adding the elements from the i th location to the j th location . A better optimization over this is generally to do a cumulative sum of all the elements upto the j th element . Then the
sum of any sub sequence can be found by taking the starting i th location and the ending j th location and subtracting the result of the element at the i th place from the element at the j th place .

All About Heap Sort -- Part 1

HeapSort is a sorting algorithm . It performs in place sorting . Its complexity it O(n lg n).
It makes use of a data structure called heap. The heap data structure is like an array which looks like a complete binary tree.If you imagine the heap array as a tree then each node in the tree will have left and right children . Each of the nodes in the tree map on to elements in the array . Every parent at index (i) will have a left child at index (2 * i ) and a right child at index (2 *i +1 ) in the array . Nodes in the heap follow the heap property . Heaps can be a max heap or a min heap.
In a max heap every Parent will have a higher value than any of its children . Its the opposite in the case of min heap. For the heap sort algorithm a max heap is used , generally a min heap is used for a priority queue.

Since a heap of (n) elements is like a complete binary tree its height is (lg n ) and all basic operations run in a time proportional to the height of the tree . Heap is a complete binary tree filled with elements at all levels except the last one . So the max number of elements in a heap of height (h) is (pow(2,h+1) - 1) . The minimum number of elements is equal to the number of elements in a heap of height (h-1) + 1 element. We add the extra one element because in the actual heap there would be at least one element on the last row containing leaves.
So the minimum number of elements = (pow(2,h) -1 ) + 1

The height of a heap is actually = floor(lg n ) . Since , a heap with height h will have elements (n) = pow(2,h) <= n <= pow(2,h+1)-1 < pow(2,h-1) and hence
h <= lg n < 1 =""> height = floor ( lg n )