May 9 2012

Sorting with Function Pointers

Karthik Nadig

This is a simple application of function pointers. Here I am trying to sort an array points based on X values, Y values or the distance from the origin. I have a simple sorting algorithm and the sorting criteria can be changed by using function pointers. 

Lets start with the types we need. First, I need a structure to hold the X and Y values of the point. Point2D structure takes care of that. Second, a type that will define the sorting criteria, see in line 9. It define a pointer to a function that accepts two arguments both of which are Point2D structures and returns a bool. Typically comparison operations have this format.

   1:  #include <iostream>
   2:  #include <math.h>
   3:  using namespace std;
   4:   
   5:  // 2D co-ordinate system
   6:  typedef struct _Point2D
   7:  {    double X, Y;}Point2D;
   8:  // function pointer type definiton
   9:  typedef bool (*Compare)(Point2D&,Point2D&);

Lets define a function to create and initialize a Point2D structure. This will make it easier to control or set default values to the Point2D structure.

  10:  // function that returns a 2D point
  11:  Point2D fnCreatePoint(const double x=0.0,const double y=0.0)
  12:  {
  13:      Point2D point;
  14:      point.X = x;
  15:      point.Y = y;
  16:      return point;
  17:  }

Lets further define swap function usually used in sorting algorithms and a simple sorting function. There are fairly direct, if you need more help with this see: Swap, Bubble Sort. Note that the sorting algorithm takes a additional argument of type Compare. That is the type of the function pointer that will define the comparison criteria while sorting.

  18:  // swaps the two values
  19:  void swap(Point2D& a,Point2D& b)
  20:  {
  21:      Point2D t;
  22:      t.X = a.X;t.Y = a.Y;
  23:      a.X = b.X;a.Y = b.Y;
  24:      b.X = t.X;b.Y = t.Y;
  25:  }
  26:  // sorts an array of values
  27:  Point2D* sort(Point2D* points,const int len,Compare fnCompare)
  28:  {
  29:      for(int i = 0;i<len;i++)
  30:          for(int j = i+1;j<len;j++)
  31:              if(!fnCompare(points[i],points[j]))
  32:                  swap(points[i],points[j]);
  33:      return points;
  34:  }

Now, that we have the framework we need, let us define a few comparing functions. These are simple functions that perform a particular type com comparison. The compare_x function compares only the X value of the Point2D structure. Similarly, compare_y function compares the Y value. The compare_distance function calculates the distance from the origin for the two points and then compares the distance. Note that each of these functions follow the argument types and return value type defined previously in line 9. 

  35:  // comparing functions
  36:  bool compare_x(Point2D& a,Point2D& b)
  37:  {     return a.X < b.X;}
  38:  bool compare_y(Point2D& a,Point2D& b)
  39:  {     return a.Y < b.Y;}
  40:  bool compare_distance(Point2D& a,Point2D& b)
  41:  {     return
  42:          sqrt(pow(a.X,2.0) + pow(a.Y,2.0)) <
  43:          sqrt(pow(b.X,2.0) + pow(b.Y,2.0));
  44:  }

We have all the components that are needed to make this work. Here, I create an array with five points in it and call the sorting algorithm with the appropriate comparison criteria. Finally, display the sorted array of points.

int main()
{
    Point2D points[]={
        fnCreatePoint(-1,1),
        fnCreatePoint(-2,2),
        fnCreatePoint(1,-1),
        fnCreatePoint(2,-2),
        fnCreatePoint(0,0)};
    int length = 5;
 
    cout << "Sorted by X value:" << endl;
    // Sorts the points based on X
    sort(points,length,compare_x);
    Display(points,length);
 
    cout << endl << "Sorted by Y value:" << endl;
    // Sorts the points based on Y
    sort(points,length,compare_y);
    Display(points,length);
 
    cout << endl << "Sorted by distance from the origin:" << endl;
    // Sorts the points based on distance from the origin
    sort(points,length,compare_distance);
    Display(points,length);
 
    return 0;
}

I hope this helps you understand function pointers. Source code: fptr_example.cpp


Mar 14 2012

What is ‘void’?

Karthik Nadig

I have often seen that there is a confusion around the ‘void’ concept in C++ among the new comers to C++. Especially when it is used as a pointer. A commonly seen definition is that void means lack of something. Hence you cannot have a variable of type void. But you can have a pointer which is of void type. This is a bit confusing, so I am going to try and give examples and explain about each one.

Before I start, a pointer stores the address to some content. So, the size of all pointers are the same regardless of the content they point to. However, the pointer arithmetic depends on the type of content it is pointing to. Here I am going to talk about a type that means nothing and can be used to point to any type.

1. void vX;

This is NOT allowed in C++. You cannot have a variable of type void. This makes some sense, void means nothing, hence you cannot declare a variable of type nothing. A variable is a name for a location in memory, and since void does not define the amount of memory needed you cannot allocate it.

2. void fnDoSomething(void);

This is allowed in C++. This says that the function fnDoSomething accepts nothing and returns nothing. There is no memory  needed to store the variables here. However, void fnDoSomething(int iX, void); is invalid. This is trying to say fnDoSomething accepts an integer and the next argument is nothing. The compiler will show an error indicating that the type of the second argument is not known or invalid use of void. Since we are passing values the compiler has to put code in there to copy the value that will go into ‘iX’, so before copying memory has to be allocated for that argument. The first argument is fine because the compiler knows the cost of int and it can allocate the amount of memory needed for it. When the compiler looks at the second argument, it cannot allocate memory because of the problem we saw in section 1. Finally, void fnDoSomething(); has the same meaning as void fnDoSomething(void); . Here is a simple example:

   1:  void fnSomething(void)
   2:  {
   3:      cout << "Something was done.";
   4:  }

3. void *vpX;

This is allowed in C++. First, a pointer is being declared. This is allowed but NOTvoid vX;’ because here a pointer was created and we are telling the compiler not to care about the type of the item it is pointing to. Usually, the amount of memory for any type of pointer is 4 bytes (8 bytes for x64). Second, since it is a pointer the compiler knows the amount of memory it needs to allocate, and ‘vpX’ is the name for that allocated memory.  A void pointer can point to any variable (except for those which are const or volatile) or can point to a function (except for member functions of a class).  Here is an example, the program  prints the byte sequence from memory for int and double data types using the same function.

   1:  void fnPrintHex(void *vpData,int iSize)
   2:  {
   3:      unsigned char* cpData = (unsigned char*)vpData;
   4:      for(int i=iSize-1;i>=0;i--)
   5:          cout << hex << (int)*(cpData+i);
   6:  }
   7:   
   8:  int main()
   9:  {
  10:      int iX =1234;
  11:      fnPrintHex(&iX,sizeof(iX));
  12:      cout << endl;
  13:   
  14:      double dX = 1234.5678;
  15:      fnPrintHex(&dX,sizeof(dX));
  16:      cout << endl;
  17:   
  18:      return 0;
  19:  }

4. const void *vpX;

This is allowed in C++. This means that the void pointer points to a constant value. The following will cause a type-cast error during compilation:

   1:  const int iX = 10;
   2:  void *vpX = &iX; // Type cast error

Only a const void type pointer is allowed to point to a constant. This means that the pointer itself is NOT constant and its value can be changed. But, the value it is pointing to is supposed to be constant. Note, const T *pX = &X is valid, T here is the same type as X. In the following code, in line 3 the ‘vpZ’ pointer is assigned the address of ‘iX’ and in line 4 it is reassigned with address of ‘iY’. The following code should print 1234 and 10, on separate lines.

   1:  const int iX = 1234;
   2:  const int iY = 10;
   3:  const void *vpZ = &iX;
   4:  vpZ = &iY;
   5:  cout << iX << endl << *(const int*)vpZ;

figure_1a

There is a minor issue here. Note that in the above code both ‘iX’ and ‘iY’ are constants and their value cannot be changed. But, you’ll see that you can do something as shown in the code below. If you read the code it may seem like it’ll print 1000 and 1000 on separate lines. Well it actually prints 1234 and 1000 on separate lines. Constants are optimized, hence the value of ‘iX’ gets placed wherever it is used. But, the original memory location is still alterable since it was type-cast to a editable type. Note, some debuggers will show the value of ‘iX’ on line 4 as 1000, you may have to test this on your compiler and debugger.

   1:  const int iX = 1234;
   2:  const void * vpZ = &iX;
   3:  *(int*)vpZ = 1000;
   4:  cout << iX << endl << *(int*)vpZ;

figure_1b

In the figure above, the number is highlighted in red because the compiler would have already picked up the value and applied everywhere ‘iX’ is used. So even if the value is changed it no longer matters wherever ‘iX’ used.

5. void *const vpX;

This is allowed in C++. This means that the void pointer itself is a constant but it points to a variable. So, once an address is assigned to the pointer, you cannot reassign another address to it. In line 3 an address is assigned to ‘vpZ’ and after that line ‘vpZ’ cannot be assigned another address.

   1:  int iX = 1234;
   2:  int iY = 10;
   3:  void *const vpZ = &iX;
   4:  vpZ = &iY; // This is NOT allowed

But, the content at the address where the void pointer points to can be changed. You need to type-cast before you can make any changes. See the following code, it prints out 1000 and 1000, on separate lines.

   1:  int iX = 1234;
   2:  void *const vpZ = &iX;
   3:  *(int*)vpZ = 1000;
   4:  cout << iX << endl << *(int*)vpZ;

figure_1c

6. const void* const vpX;

This is allowed in C++. This is a void pointer which is a constant pointing to an address whose contents are also constant. This is a combination of section 4 and 5 and the same rules apply. The following code will fail to compile, see section 5 for the reason:

   1:  const int iX = 1234;
   2:  const int iY = 5432;
   3:  const void *const vpZ = &iX;
   4:  vpZ = &iY; // This is NOT allowed

But the following code is allowed, see section 4 for the reason:

   1:  const int iX = 1234;
   2:  const void *const vpZ = &iX;
   3:  *(int*)vpZ = 1000;
   4:  cout << iX << endl << *(int*)vpZ;

I tested all of my code in visual C++ and GNU GCC. Please let me know if there are any mistakes. This is an introduction, I’ll try and write more advanced usage of void pointers in the future. Thanks for your patience.


Dec 27 2010

Hint of personality

Karthik Nadig

In “Errors as we speak”, we saw how error prone communicating with words can be. Let’s explore a deeper level of translation between idiolects, and how our mind achieves this translation.

Psychology has taught us that we communicate people with a mental “looking glass”, which filters content based on the idiosyncrasies of the individuals it has picked up. We have a general looking glass that we use to communicate with strangers. This general looking glass is conditioned by every experience accumulated till date. It allows us to make choices such as mode of speech, body language, subtleties in the intonation of words, etc. This general looking glass works until the conversation remains general (definition of ‘general’ is relative to each individual).

As we learn more about a person, we seize to use the general looking glass and we switch to a specialized one, dedicated to the person. This can be observed in our daily life and we understand some people who are close to us, even if they were not able create a complete sentence about whatever they were trying to say. This is because, the looking glass, with time, has now tuned to pickup and translate, a person’s idiolect to one’s own idiolect. In essence, our mind captures the personality of the individuals. One might ask, why do we need this mechanism? What purpose does capturing one’s personality have?

Our mind is a sucker for running simulations. Call it imagination, prediction or contemplating outcome, it is an important feature which allows us to form social groups. Capturing personalities allows our mind to estimate the consequences of our actions by predicting reactions of people. By using the feedback from the predicted reactions our mind to improve its strategy, prepare itself for consequences.

This ability of our mind is so good that it can associate personality to everything, be it an animate (pet animals) or inanimate (bike, tools), existing (anything tangible) or imagined (characters in a book) objects. It so well evolved that sometimes we can communicate using the looking glass, within our mind, and yet come up with a response which exactly reflects the response of the person we just simulated, this almost sounds like telepathy. Although our mind has evolved this feature, we don’t have complete control over it.


Dec 19 2010

Errors as we speak

Karthik Nadig

It is all about exchange of ideas. In this world of information exchange, we designed transmission mechanisms that are, in effect, error free. But, we have forgotten the most fundamental of transmission mechanisms that isn’t yet perfect. It took nature millions of years of evolution to perfect some of its technologies, and communication mechanism of humans, i.e., speech, isn’t one of them.

The Source: Information exchange, in any form, has two terminal components a Source and a Destination. Let’s, begin with the source. We are yet to figure out how information content is stored and operated on in the brain. But we sure don’t think with words, although, words do contribute, in part, in guiding the thought process. The problem appears when it is time to transfer the idea from our mind to any form of media tangible or intangible. One form of presenting our idea is with words and this is where conversion from abstract idea to words has to happen.

The Encoder: We convert an idea to words by selecting those which, to us, at that moment, are our best approximation to the abstractness of the idea. My friend, Tom Horton, calls it “bag of words”. We pick words, depending on the vocabulary and our meaning for that (based on visceral feeling we have for the word). Since our choice is an approximation, finally, our presented idea, after conversion, is an accumulation of approximation.

The Medium: Words can be transferred using a myriad of media, but I want to look at the medium we were born with. I believe that it is easily subjected to errors compared to other forms. Firstly, words have to be converted to sound, this happens by picking up a sequence of pulses which control the vocal chords. These sequences of pulses were learnt, which means another layer of approximation is introduced.  Then we expect the vocal chords to reproduce the sound and we have introduced another layer of errors. Secondly, the generated sound travels through the air (assumed to be speaking with someone in person), superimposed by noise, introducing a major layer of error. Lastly, the transfer is incomplete without reception. Ears pick up this sound, slightly obfuscated, and compares and picks up the words that have the highest probability of correctness, based on physical comparison of sounds, context and several hundreds of other fact0rs, etc.

The Decoder: Let’s face it; this is a real tough one. It is difficult to find someone who has at least one neuron that can fire, let alone find someone and get them to completely understand something by explaining it to them. As with the encoder, the words after being captured have to be transformed into the idea, or the abstract form. Since each person has a different visceral feel for words the transformation is never prefect.

The Destination: I believe that the destination for a transferred idea is reached when the intended person begins to understand the concept. However, each person thinks with physics of his own. The rules that govern the through process in each individual person is different, which brings us to a conclusion that each person understands the world differently. I conclude my rant here, that have patience when explaining things to others.

Disclaimer: I have not added any references to the claims I have made here because it is a rant. If you did learn anything from it, I beg your pardon, it was purely accidental.


Feb 11 2010

Morphology in Frequency Domain

Karthik Nadig

To put it simply,

[latex]GrayScale(Image) \rightarrow DFT(Image) \rightarrow f(Image) \rightarrow IDFT(Image)[/latex]

Replace $latex f(Image) = f(x)$ by any of the functions from the following table, it also shows the effect of the function on the “Lenna” image. The images show effect of morphology or filter applied in the frequency domain.

Source Code: C++

f(x)

Processed Image

Dilate(x) :
Morphological Dilate
dilate1
Erode(x) :
Morphological Erode

erode1

Open(x) :
Morphological Open

open1

Close(x) :
Morphological Close

close1

Gradient(x) :
Morphological Gradient

gradient1

Gaussian(x) :
Simple Gaussian Blur

gaussian1

Images processed with FFTW and OpenCV libraries.


Jul 20 2009

Nano-scale Dyson Sphere

Karthik Nadig

I was watching Season 2 of The Big Bang Theory: The Hofstadter Isotope episode; Howard Wolowitz mentioned about the Drake Equation and it’s plausible application to predicting the possibility of getting laid, and then there was something about hitting it and quitting it.  So, I looked up Drake Equation on Wikipedia, and as usual one thing led to the other and finally reached the Dyson Sphere.

I am not going to explain what Dyson Sphere is, you probably would have already clicked the link, and now no longer coherent about where you were on this page. Most depictions of Dyson Sphere are of shell kind. This is the least plausible type, cause to construct a 3m thick sphere with inner radius of 1AU (or 149.60×109m) requires about 8.4×1023m3 of material. Our entire planet has just 1.09×1021m3 of material, so we’ll need 772 more earth sized planets to build such a structure. I have mentioned the parameters in volumes cause it’ll probably be difficult to find any matter in such enormous quantities within our solar system, unless we decide to use all the planets, asteroids or anything that moves around the sun as a source of material.

The original design was to encompass a star swarms of solar power satellites to capture most or all of its energy. Although fictional world says it’s possible to build a solid sphere, it’s highly unlikely. But it is possible to extract portion of the sun energy if we could build nano-scale satellites to absorb and store the sun’s energy in portable form. This is some what analogous to insect colonies amassing food in huge quantities.

Again this would be possible if the technology advances enough to protect any electronic instrument, in space,  from an astounding number of solar phenomenon which can put and end to the project even before it begins. At least the plausibility of this idea is higher than that of building a solid sphere.

If you actually learnt something from this; it was purely accidental. If you were really looking for schematics of such a project and google led you to this page; sorry, I had to write this blog other wise my head would explode.


Jun 7 2009

Home

Karthik Nadig

Home is a documentary on Earth by Yann Arthus-Bertrand, a French photographer, journalist and environmentalist. The film is entirely composed of aerial view of the earth which portrays diversity of life and present state of the earth. The theme of the film is about the delicate balance which nature maintains and how our actions disrupted it.

The documentary shows harsh facts and awful truths about the impact of disruption of natural balance. The movie concludes with a positive tone, showing what is being done and can be done to reverse it.

Here, are some facts (not from the documentary):

  1. About 4000 chemicals are released into the atmosphere by smoking cigarette, 400 of which are toxic. To make 300 cigarettes, on an average, a tree gets wasted. In Britain about 34 million days worth of working hours were lost in 2007 due to leave; because of smoking related sickness. Primly smoking increases the risk of erectile dysfunction by about 50%. Those numbers will make sense when you’ll know that you breathe in about 15,000 liters of air in a day.
  2. Ever heard of Great pacific garbage patch, humanity has to be congratulated for this amazing feat. The estimated size of the affected area is about 700,000 km² to more than 15 million km², may contain over 100 million tons of debris.
  3. 80% of the urban waste in India ends up in the rivers, about 3 billion liters of waste per day. Only 55% of the 15 million Delhi residents are connected to the city’s sewage system, this is supposedly a good figure compared to the other cities.
  4. In some areas of India, the groundwater tables have dropped as much as 70 centimeters (about 25 inches). Up to 25% of India’s agriculture may be threatened by the depletion of groundwater resources. In the Czech Republic 70% of surface and ground waters are polluted, mostly with agricultural and industrial wastes.
  5. About 1/3 of the water each person uses on a daily basis is wasted. Each person in the UK uses 150 liters of water a day. Fixing a leaking tap can save as much as 5000 liters a year. During an average monsoon season in India, about 10000 liters of rain water can be harvested from a roof of 25 sq ft.
  6. Out of the top 10 most polluted cities in the world 4 of them belong to India (Delhi, Kolkata, Kanpur, Lucknow), Delhi being the second most polluted city in the world. 400,000 Chinese die prematurely each year from respiratory illnesses and other diseases related to air pollution.
  7. In US, 1.5 million barrels of crude oil (enough fuel to run 100,000 cars for a year) is used to produce 60 million bottles, all of which will end up in the landfill in a day.

Those numbers are staggering, so is the world population (about 7 billion). A few minor changes and using the resources frugally, or even trying to do that will significantly contribute to reduce the adverse effects of pollution and wastage.