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
Wednesday, October 15, 2008
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)
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())
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 .
It makes more sense to use template specialization for std::swap
class MyClass {
public:
void Swap(MyClass &) ;
};
namespace std {
template<> swap
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));
class MyClass {
public:
int DoSomething(){
}
};
now say you have
std::vector
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
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);
}
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
sprintf(buf, "%d", value);
}
template<> void prettyPrint
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);
}
if you have a vector "v"
copy(v.begin(), v.end(), ostream_iterator
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)
#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)
const_cast
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
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.
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;
}
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
"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++ :
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 .
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.
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 .
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 .
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.
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.
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
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 .
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 )
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.
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 .
{
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
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..
So if you want a head start , ThoughtWorks is the place to be ;)
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
- 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 .
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();
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()
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());
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.
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
}
}
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;
}
}
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
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)
{}
};
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 .
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);
}
}
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());
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
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.
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 .
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 .
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))
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
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.
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;
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 .
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.
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 .
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 .
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
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:
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)
- static_cast
- const_cast
- dynamic_cast
- reinterpret_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"
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)
(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)
Subscribe to:
Posts (Atom)
Labels
. linux
(1)
algorithm
(15)
analytics
(1)
bash
(2)
bigoh
(1)
bruteforce
(1)
c#
(1)
c++
(40)
collections
(1)
commands
(2)
const
(1)
cosine similarity
(1)
creating projects
(1)
daemon
(1)
device_drivers
(1)
eclipse
(6)
eclipse-plugin-development
(9)
equals
(1)
formatting
(1)
freebsd
(1)
game programming
(1)
hashcode
(1)
heap
(1)
heaps
(1)
immutable-objects
(1)
java
(19)
JDT
(1)
kernel
(1)
linux
(4)
little sugar
(23)
logging
(1)
machine learning
(1)
marker-resolution
(1)
markers
(1)
mergesort
(1)
mixins
(1)
numbers
(1)
opengl
(2)
patterns
(2)
priority-queue
(1)
programming
(51)
ps
(1)
ranking
(1)
refactoring
(3)
references
(1)
security
(1)
set
(1)
shell
(1)
similarity
(1)
statistics
(1)
stl
(1)
tetris
(1)
threads
(1)
trees
(2)
unicode
(1)
unix
(2)
views
(2)
windows programming
(2)
XNA
(1)