Wednesday, October 15, 2008

use find magic to create etags

To create a TAGS file so that you can work with emacs / vim use the following command

find . -ipath '*.p*' -print | etags -

the above command for example will create etags for all the pl , pm files in the current directory

Saturday, September 27, 2008

Little Sugar:Decreasing capacity in C++

When you use vector,string class in C++, the problem that happens is that the capacity just increases and does not decrease, causing the data structure to hog lot of memory.
For example, say in the vector 10 elements were added , then to the same vector 1000000 elements were added. Then 900000 were deleted. This will not cause the capacity to decrease. This might result in the vector still holding on to a lot of memory.

One way to fix this is the sap trick.

vector < int > elements; // the original vector

vector < int > (elements.begin(), elements.end() ).swap(elements)

Wednesday, August 13, 2008

vector::assign

"assign" is a method in STL for the vector class. When ever you need to erase the contents of the vector and replace it with totally new contents use the assign member function .You should use the operator= then all elements of the right hand side container would be copied to the container on the left hand side.

e.g

v1.assign(v2.begin() + v2.size()/2 , v2.end())

Thursday, June 05, 2008

C++ : std::swap and template specialization

say you want to use the swap method provided in std namespace for your own class . Then instead of using the std::swap option blindly , that would involve making use that your class has at least a copy constructor and that the assignment operator is overridden.

It makes more sense to use template specialization for std::swap

class MyClass {
public:
void Swap(MyClass &) ;
};

namespace std {
template<> swap(MyClass& a, MyClass& b){
a.Swap(b);
}
}

so that way we just tune the default swap to use our class specific Swap and things become fast and simple for us .

Wednesday, June 04, 2008

C++ : std::mem_fun

Say you have a class

class MyClass {
public:
int DoSomething(){
}
};

now say you have

std::vector classes;

you can use something like this

for_each(classes.begin(), classes.end(), &DoSomething);

where DoSomething is

int DoSomething(MyClass& e){
d.DoSomething();
}


to call the member function DoSomething rather than the wrapper function use function calls like these

for_each(classes.begin(), classes.end(), mem_fun_ref(&MyClass::DoSomething));

if the classes vector was defined something like this

vector classes

then you would use something like this

for_each(classes.begin(), classes.end(), mem_fun(&MyClass::DoSomething));

C++ : Template specializations

Assuming you have a piece of code that is templatized and looks like this

template
void prettyPrint(T value, char* buf);

now assume that you are using sprintf for formatting the input .

that being the case you can use template specializations like this :

template<> void prettyPrint(int value, char* buf){
sprintf(buf, "%d", value);
}

template<> void prettyPrint(char value, char* buf){
sprintf(buf, "%c", value);
}

Tuesday, June 03, 2008

C++: copy magic

Say if you have a vector and you want to print it . Then instead of the normal for loop and cout call inside the loop you can do the following :

if you have a vector "v"

copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

this will print the entire vector .

To generalize this you could use something like this :

template
OutputIterator copy(const Container& c, OutputIterator result){
return std::copy(c.begin(), c.end(), result);
}

C++ : pragma warning

if there is a header file after including which you start getting warnings , and especially if that header file is a third party header file , its better to wrap the header file with your own custom wrapper .

#pragma warning(push)
#pragma warning(disable:line_number_causing_warning)
#include
#pragma warning(pop)

Thursday, May 22, 2008

C++ : Little Sugar

In C++ when ever you see a function that accepts a const reference than its a valid candidate for temporaries . Temporaries are objects that are created and destroyed whenever there is mismatch in function arguments and a constructor exists that takes the passed argument and converts it to a destination entity via the constructor .

C++ : Little Sugar

mutable keyword is useful in C++ , when you are changing a member variable in side a constant function . A simple way to remove constantness of the "this" pointer is to use code like this

const_cast(this)

C++ : new operator and operator new

The new operator in C++ is something that cannot be changed . For example
when you use code something like this ,

string *ps = new string("Memory Management");

the new operator is used . Its sole purpose is to allocate memory and initialize it.

The new operator in turn uses the operator new to allocate memory which can be overloaded.

its prototype looks like this :

void * operator new(size_t size);

there is another version of new operator called the placement new , that is used to create objects in pre initialized memory. example usage for it looks like this :

string *ps = new(memory) string("Memory Management");

same is the case for delete operator and operator delete

operator new[] is another type of operator that can be used to allocate new arrays

Tuesday, May 20, 2008

C++ : Little Sugar

While creating objects in C++ , in order to initialize objects use the member initialization list. When initialization of a class starts , initialization of its members happens . If the member initialization list is not used the default constructor of all the class members is called even before entering the constructor . Once inside the constructor the copy constructor or operator = is called to initialize the member objects .

On the other hand if member initialization list is used only the copy constructor is called once and hence you prevent the over head of an extra call.

Monday, May 19, 2008

C++ : Creating Objects

Here are 2 simple rules to allocating and deleting objects.

MyObject * myPointer;

while updating object memory always use code like this:

MyObject::update(){
delete myPointer;
myPointer = NULL;
myPointer = MyObject::CreateNew();
}

while deallocating always use code like this:

MyObject::~MyObject(){
delete myPointer;
myPointer = NULL;
}

Tuesday, April 29, 2008

Refactoring Large Methods: Refactoring

Refactoring Large Methods:

"The object programs that live best and longest

are those with short methods. Programmers new to

objects often feel that no computation ever takes

place, that object programs are endless sequences

of delegation. When you have lived with such a

program for a few years, however, you learn just

how valuable all those little methods are. All of

the payoffs of indirection—explanation, sharing,

and choosing—are supported by little methods" -

Refactoring Book - Martin Fowler

Large Methods are code smells.To refactor large

methods follow the following methods :

-> Use extract method refactoring to extract a

lot of small methods

-> In case of a method having a number of

temporary variables , temporary variables can be

replaced by query methods

-> A query method is a small method that is

intended to replace variables .

e.g int myVariable = oldValue1 * oldValue2

create a new method like

int getValue(){
return oldValue1 * oldValue2;
}

now replace all usages to myVariable by the
method getValue()

-> Then try introduce Parameter Object

refactoring to take care of huge number

parameters in the extracted method

-> Use Preserve Whole Object Refactoring in case

lot of parameters are passed to methods , and

each of these parameters are local values.

-> If still extract method refactoring becomes

difficult use "Replace method with Method Object"

refactoring

Sunday, April 27, 2008

QuickSort : C++

i was having a re look at quick sort.

Here is the code in c++ :


template< class T >
int partition(T a[], int p, int r){
T x = a[r];
int i = p - 1;
for(int j = p;j < r;j++){
if(a[j] <= x){
i++;
swap(a[i],a[j]);
}
}
swap(a[i+1] , a[r]);
return i + 1;
}


template< class T >
void quickSort(T a[], int p, int r){
if(p < r){
int q = partition(a, p , r);
quickSort(a, p , q-1);
quickSort(a, q+1 , r);
}
}


The idea of quicksort is to take an array and divide it into partitions .
First a key is chosen . That is called the pivot . Here 'x' is the pivot .
Based on the value of 'x' other values in an array are put in 2 partitions .
One partition that contains values less than 'x' and other partition contains values greater than x .

Here i and j are used to mark the extent of these 2 partitions .

The beauty of the algorithm lies in the fact , how integers are used to manipulate partitions . 'i' is initially set to value that precedes a real boundary . 'j' is set to the first location in the array . Now as values are compared with 'x' ( the key)
if value is less than 'x' the partition extent marked by 'i' are increased , else the partition extent marked by 'j' is increased . In the first case where values of 'i' is less than 'x' and since 'i' now occupies what 'j' occupied the values at those indices are swapped .

the partition method does in place sorting of the array and the quickSort method is responsible for choosing partitons .

Sunday, April 13, 2008

C++ : template specialization

template <>
char* Add<char*>(char* a , char* b){
return strcat(a,b);
}

char * res = Add<char*>("foo","bar");

This code refers to a new type of syntax for templates called template specialization syntax.
Generally when you write code for templates .

you end up using stuff like

template<class>

but say you want the same generic code for many cases . In the above mentioned code for example if the add function used the "+" operator to add two types it would have not worked for char* pointers , because the "+" operator does not work with them .

by using the syntax as mentioned above its possible to tell the compiler that there are exceptions to your generic code and that for special cases these new methods should be called.

C++ : The need for virtual destructors

With the advent of object oriented languages the use of polymophism became very common .
In C++ when you have a derived Class and a base class .

when you have code like this :

class Base {
};

class Derived : public Base{
};

Base * p = new Derived();

delete p;

what's wrong with it .

Since this piece of code is based on polymorphism , the base pointer will refer to an instance of a derived class object .

when delete on the pointer p is called , due to static typing in c++ , destructor of Base is called , instead of Derived . To correct this

virtual ~Base(){
}

should be added . By making the destructor virtual the destructor of the derived class would be called now .

Saturday, April 12, 2008

Refactoring : Self Encapsulate Field

Some times in a code base , especially inside a class , a field is referenced from many places.
Say you decide to move this field to another class .

A clean way of doing this is to first extract a getter method for that field within the same class .
Now with all occurances replaced by the getter method , move this getter method to the new class .
Similarly replace the code where the field is being set by the appropriate setter code and then move the setter code to another class .

Refactroing : Handling Duplicate Code

In legacy code bases we see lot of duplicate code . so how do we handle it ?

I am assuming you are using a tool that supports refactoring . In that case ,

Case 1:

If in a class you have lot of repeated code , use extract method refactoring to move the repeated code into a common method inside the class . Now replace if not automatically all occurance s of the repeated code with the call to the newly created method.

Case 2:

You have 2 sibling classes that have same piece of code .

Use extract method to create method with the same name in the 2 classes . Then use pull up refactoring to pull up the common method now in a super class . If the super class does not exist create it now .

Case 3:

You have 2 sibling classes that have almost the same piece of code , but some different bits here and there .

Use extract method to create method with the same signature in both the classes . Then identify the parts that are different , extract these different parts into methods of their own . Make sure that the names of these different parts is same in both sibling classes.

Now use template method design pattern , to create a common method in a super class of these 2 siblings . Using polymorph ism and inheritance to implement the different methods in the sibling classes.

Tuesday, April 08, 2008

C++: Object slicing and pass by value

In C++ , when a object is passed by value to a function that accepts a parameter then object slicing might happen. Consider the following class

class Base {
public:
virtual const char * toString() throw();

};

class Derived : public Base {
public:
virtual const char* toString() throw();
};

Derived derived;
Base base;

void doSomething(Base base){
....
}

doSomething(base);
doSomething(derived);


now we have 2 classes Base and Derived with a common virtual function that have been overridden in the derived class . We create 2 objects "derived" and "base".

Both of them are passed to the function doSomething . What happens in this case .

In the first case , it works the way its supposed to . In the second case , object slicing takes place and the members that are just of derived class are chopped off and the virtual function of the base class is called.

Monday, April 07, 2008

C++ : pointer to member function

class Foo{
public:
int iVal;
int Bar(int);
};


int Foo::* pm;

is a pointer to a member variable that is an integer.

pm = &Foo::iVal;

is used to initailize a pointer to a member variable

Foo foo;

int i = foo.*pm

is used to retrieve values of the pointer to member variable

int (Foo::*pmf) (int) = &Foo::Bar;

is a pointer to member function that is initialized by the address of member function Bar

C++ : Preventing implicit type conversion

class Foo{
public:

Foo(int n ){
...
}

};

Foo foo(42);
Foo boo = 42;

In the above mentioned snippet , the first constructor is matched and called. In the second case , for the assignment operator since the right hand side is 42 and since we have a constructor that takes integer as an argument . The corresponding constructor is called . This is syntactic sugar that can lead to lots of problems . To prevent something like this .

the explicit keyword should be used in front of constructors .

Wednesday, April 02, 2008

C++: Rethrowing exceptions

Consider the following piece of code

catch (Base& w)
{
...
throw;
}
catch (Base& w)
{
...
throw w;
}

What do you think is the difference between the 2 approaches above .

In the first case , the exception is re thrown . In the second case a copy is made and a new exception is thrown . Also the copy is based on the static type i.e
Base (copy constructor is called )

C++ : Object Copies in C++ are based on Object's Static Type Not Dynamic Type

Consider the following piece of code

class Base { ... };
class Derived: public Base { ... };

void passAndThrowDerived()
{
Derived local;
...
Base& rw = local;

throw rw;

}


In the above mentioned case . When a copy of rw is made while throwing it .
The copy constructor for the type is called . In this case the since rw is a reference to Base there fore the copy constructor of Base is called rather than the
Copy Constructor of Derived class.

C++ : Why are objects thrown as exception always copied

When an exception is thrown , the objects are generally copied. To explain this consider the following :

{
MyObject myObject;
cin >> myObject;
throw myObject;
}

if the object myObject was passed by reference then the same myObject would be thrown out . If the same object is thrown out then as soon as it goes out of scope , its destructor would get called and as a result of which some garbage would finally reach the exceptional handling code .

It is for this reason that copies of myObject are thrown rather than the original one .

Monday, March 24, 2008

Little Sugar : C++

In C++ have you imagined what would happen if the destructor of your class throws an exception . For starters , the object would not get destroyed properly . Actually in reality the control would go back to the callee from the current point directly.

Alright , now think what would happen if the destructor got called as a part of some exception handling code and this destructor threw an exception .

Since the active callee is calling the destructor due to some raised exception .
it would result in the terminate() function getting called and though would terminate the program immediately

Sunday, March 23, 2008

ThoughtWorks: Why it should be your first Software Company ??

ThoughtWorks , should be your first software company because:

You will learn..

  • What good software design is all about. You will hone the skills that will enable you to write good solid beautiful code .
  • Good coding practices e.g ( Test Driven Development .. )
  • To re factor code properly and effectively .
  • How to test your code like crazy
Other reasons why you will love Thoughtworks..

  • People adore Ruby and Python ;) and use them for their project work
  • Fellow developers try out cool and technologies like Erlang and haskell and incite you to try something or do something different.
  • Free Food
  • XBox , PlayStation
  • Table Tennis and other games .
  • Cool outings and free booze ;)
  • Amazing people from whom you 'll learn like crazy almost everyday , till the next 1.5 yrs
  • You can play pranks on the CEO and he wont fire you .
And finally an average ThoughtWorker with 1.5 yrs of work experience = most of the Software Engineers with 3.5 yrs of experience .

So if you want a head start , ThoughtWorks is the place to be ;)


Thursday, March 20, 2008

Java Thread Programming : Using Semaphores

The java concurrent framework provides Semaphore . Semaphores are useful when the end user wants to implement some kind of resource pool.

In a semaphore permits can be acquired and released . A semaphore when created can be initialized with the number of entries it can contain at any point of time .

Semaphore s = new Semaphore(N);

// acquire a permit

s.acquire();

// release a permit

s.release();

Java Concurrent Programming : CountDownLatch

CountDownLatch in the concurrent programming framework provided by java is pretty cool.
In principle it works like a binary latch . (Once set it remain in that state for ever )

So when would something like a countdownlatch be useful for thread programming .

Consider a scenario , you have a big task T to be done by N threads .

1) Now you want all the threads to be started at the same time so that they get equal opportunity
to participate in the completion of the task .

2) You want your main thread to do something when all the threads finish .

You can create two CountDownLatch objects.

CountDownLatch startLatch = new CountDownLatch(1);
CountDownLatch endLatch = new CountDownLatch(N);

Then you can construct all the threads like this

Thread thread = new Thread(){
public void run(){
try{
startLatch.await();
// do the task
endLatch.countDown();
}catch(InterruptedException e){
Thread.currentThread.interrupt();
}

}
}


thread.start();

so when the thread starts it will block cause of the CountDownLatch (await method call)

when startLatch.countDown() is called the latch opens and all the threads can flow now and start working .

similarly the main thread that is waiting for all threads to finish .

will continue when all the threads have called endLatch.countDown()

Monday, March 17, 2008

Eclipse Plugin Development : Small nuggets

Small snuggets for eclipse plugin development are small snippets of code useful in eclipse plugin development.

In eclipse windows that you see contains pages . Each of this page hosts a view or an editor .
Generally these editors are not hosted directly but indirectly via references ( aka proxies to the actual editor / views )

So to get reference to the actual editors / views from the pages use code like this :

IWorkbenchPage page = getPage();
IEditorReference[] editors = page.getEditorReferences();

Once you have the references you can get the actual hosted editor / view.

Editors in eclipse implement IEditorPart , so to get an editor some thing like this would work:

IEditorPart editor = editor.getEditor(true);

To reveal IJavaElement in the editor ( basically any java method , entity ) using JDT ( eclipse for java development is based on it )

JavaUI.revealInEditor(part , javaElement);

To add an action (aka tool bar item ) in the toolbar for your view something like this would work :

IActionBars actionBars = view.getViewSite().getActionBars();
IToolBarManager manager = actionBars.getToolBarManager();
manager.add(new MyToolBarItem());

Thursday, March 13, 2008

Eclipse Plugin Development : Programatically saving all open editors

In Eclipse editors are contained in WorkbenchWindow . To save all open editors one can call code like this

IWorkbench workbench = PlatformUI.getWorkbench();
return workbench.saveAllEditors(false);

This will get the current workbench and save all open editors.

Sunday, March 09, 2008

Java : Inner Classes and Parent Reference Escaping

When an inner class is created inside a class in java, it transparently contains a reference to its parent class. If by chance this reference leaks out , it compromises the thread safety of the parent class. To avoid these kind of issues , factory methods should be used to create inner classes .

Another thing that should be best avoided is : starting of a thread inside the constructor of a class.
Since the thread object also shares the reference to its parent class, this reference might be in an inconsistent state when the thread is started .

To prevent these type of scenarios factory methods are best.

e.g

public class Prent {

private childThread;

private Parent(){
childThread = new Thread();
}

public static Parent newInstance(){
Parent parent = new Parent();
childThread.start();
return parent
}

}

Monday, March 03, 2008

Eclipse : Adding nature to a project

In Eclipse plugin development terminology adding a nature to a project is like tagging the project with a specific tag . Generally natures are used to install various builders for the project. I will talk about builders in a later post . Lets look at some code and see how how natures are added to projects:

IProjectDescription projectDescription = project.getDescription();

description is a description of the project . It gives a lot of information including the entire list of
nature ids and build commands.

String[] ids = projectDescription.getNatureIds();
String[] newIds = new String[ids.length + 1];
System.arraycopy(ids,0,newIds,0,ids.length);
newIds[ids.length] = YOUR_NATURE_ID;
projectDescription.setNatureIds(newIds);
project.setDescription(projectDescription,null);

the remove nature id code is kind of similar .

To actually implement your nature , you need to contribute to the extension point
org.eclipse.core.resources.natures

Basically that boils down to adding something like this in your plugin.xml

id="yourNatureID"
name="Your Nature Name">







"id" here represents the id of the nature .
"name" represents the name of the nature .
"class" represents the class implements the IProjectNature .

the requires-nature here represents the nature id that is required for this nature to be successfully installed .

Next , finally the class that implements the IProjectNature interface.

public class YourProjectNature implements IProjectNature {
IProject project;
public YourProjectTestNature() {
}
public IProject getProject() {
return project;
}
public void setProject(IProject project) {
this.project= project;
}
}

Sunday, March 02, 2008

Little Sugar : C++

The only to initialize const pointers in c++ within a class , is via member initialization list.

class MyClass{

Data * const data_ptr;

MyClass(Data * const value) : data_ptr(value)
{}
};

Tuesday, February 05, 2008

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 .

Thursday, January 31, 2008

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.

Monday, January 28, 2008

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 .

Sunday, January 27, 2008

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 .

Friday, January 25, 2008

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

Sunday, January 20, 2008

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.

Tuesday, January 15, 2008

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.

Friday, January 11, 2008

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 .

Thursday, January 10, 2008

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)

Wednesday, January 09, 2008

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"

Tuesday, January 08, 2008

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)