Bing's Programming Experiences and Tips on C++

An Updated Reading List

2016-05-05T11:23:00.004+02:00

Mathematics, Data Structures & Algorithms

Discrete Mathematics and Its Applications (Fifth Edition), Kenneth H.Rosen

Concrete Mathematics : A Foundation for Computer Science (Second Edition), Ronald L. Graham / Donald E. Knuth / Oren Patashnik

* Introduction to Algorithms (Second Edition), Thomas H. Cormen / Charles E. Leiserson / Ronald L. Rivest / Clifford Stein

Data Structures, Algorithms, and Applications in C++， Sartaj Sahni
Data Structures & Program Design In C (Second Edition), Robert Kruse / C.L. Tondo / Bruce Leung

The Art of Computer Programming
Donald E.Knuth

Compiler

Compilers: Principles, Techniques, and Tools (2nd Edition)
[Alfred V. Aho / Ravi Sethi / Jeffrey D. Ullman]

Advanced Compiler Design and Implementation
[Steven S. Muchnick]

Operating System

Operating System Concepts (Now we have the 7th Edition)
[Abraham Silberschatz / Peter Baer Galvin / Greg Gagne]

Operating Systems : Design and Implementation (Now we have the 3rd Edition)
[Andrew S. Tanenbaum / Albert S. Woodhull]

C++

C++ Primer
Lippman / Josee Lajoie]

*The C++ Programming Language (Special Edition)
[Bjarne Stroustrup]

*Effective C++ (Now we have the 3rd Edition)
*More Effective C++
*Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14 (New)
Scott Meyers

Modern C++ Design: Generic Programming and Design Patterns Applied
Andrei Alexandrescu

Go
The Go Programming Language
Alan A. A. Donovan

ASM

The Art of Assembly Language
Randall Hyde (x86)

Introduction to 80x86 Assembly Language and Computer Architecture
Richard C. Detmer

UNIX Programming

Advanced Programming in the UNIX Environment
[W. Richard Stevens]

The UNIX Programming Environment
[Brianw. Kernighan]

UNIX Network Programming, Volume 1 : The Sockets Networking API (Third Edition)
[W. Richard Stevens / Bill Fenner / Andrew M. Rudoff]

UNIX Network Programming Volume 2 : Interprocess Communications (Second Edition)
[W. Richard Stevens]

Computer Networks

Computer Networks (Fourth Edition)
[Andrew S. Tanenbaum]

TCP/IP Illustrated, Volume 1 : The Protocols
TCP/IP Illustrated, Volume 2 : The Implementation
TCP/IP Illstrated, Volume 3 : TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols
[W. Richard Stevens]

Internetworking with TCP/IP Vol I : Principles, Protocols, and Architecture (Third Edition)
Internetworking with TCP/IP Vol II : Design, Implementation, and Internals (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, BSD Socket Version (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, Windows Sockets Version
[Douglas E. Comer / David L. Stevens]

Database

An Introduction to Database Systems (Seventh Edition)
[C. J.Date]

Database System Concepts (Fourth Edition)
[Abraham Silberschat / Henry F.Korth / S.Sudarshan]

Software Engineering / Craftsmanship

Code Complete: A Practical Handbook of Software Construction, Second Edition， Steven C. McConnell

**Pragmatic programmer: from journeyman to master， Andrew Hunt and David Thomas
Peopleware：Productive Projects and Teams, Tom DeMarco, Timothy Lister

**The Software Craftsman: Professionalism, Pragmatism, Pride (Robert C. Martin Series)

Clean Code: A Handbook of Agile Software Craftsmanship

**Soft Skills: The software developer's life manual

**The Lean Startup: How Today's Entrepreneurs Use Continuous Innovation to Create Radically Successful Businesses

Data Science
***Data Science from Scratch: First Principles with Python, Joel Grus

Fedora 21 Installed!

2015-04-11T14:36:00.001+02:00

Haven't written anything since three years and now I come back, with my beloved Fedora.

Just installed the latest Fedora 21 and now I'm enjoying typing with it.

Fedora 21 provides a Scientific spin, very cool, C/C++, Python, LaTex and a lot of other new and old friends!

A Real-life Story about exception specification

2012-09-05T23:04:00.000+02:00

Today, just before I thought I'd finish my day and go home, I got a urgent problem. One of our component kept coring, making services unavailable to clients.

Investigation started right away and we found the cause after a while. The cause is quite simple but unexpected.

The reason is we have a function specified with a exception specification. For those who are not familiar with the exception specification, it's the famous throw(A) that you can put after a function declaration or definition. It's used to tell compiler what exceptions should be allow to be thrown in the function, particularly, if nothing is in the (), that means the function is not allowed to throw anything.

Well we have one such function that with a throw() however, it DO throw an exception. So what happens? The exception is caught and treated as unexpected, then terminate() is called, then terminate() calls abort(), program aborts with a core (SIGABRT 6).

It's NOT hard to understand all of this, but we had a painful time to find out that it's actually this exception specification had caused the problem, it's in the same line as the function definition, far away from when the line where actually throws something.

It's a shame that after years of debate on this topic, we still fail on that. Here are some links:
http://www.gotw.ca/publications/mill22.htm
http://www.gotw.ca/gotw/082.htm
http://www.boost.org/development/requirements.html#Exception-specification
All those gurus suggest NOT USING EXCEPTION SPECIFICATION !

After beaten senselessly, now I remember, never write a exception specification.

Also I have to put another point on that, a function with exception specification is just a trap for other programmers who is working on it, it may not notice the very existence of the throw() and throw something in the function body, or even harder to prevent, he may just call a function that throws inside. I'm such a victim, modified a function with throw() but throw something.

Fedora 17 Installed!

2012-06-30T22:08:00.002+02:00

Another step towards a better OS, Fedora 17 has been released quite some time ago but only I have a chance to upgrade to it for my PC. So now I'm posting on my new Fedora 17!

It has a new kernel version and most recent development tools. The only little thing is the reboot panic but solutions are out there.

A Real-life Story about Floating Point Value Comparison

2012-04-27T23:16:00.001+02:00

I got a problem today in our software. In general, when we have two input double values like v1= 800 and v2= 750, it's working correctly while if v1=1000 and v2 = 900, it's not working as expected.

The logic is based on the comparison result of the two values. While for both two cases above we have v1 > v2, the results are not the same, why?

After tracking down to where the comparison is made, I found out that it's essentially written like this:
if (FormatToString(v1) > FormatToString(v2)) DoSomething();

I'm pretty sure, at the first look to this line, it's not doing what whoever wrote it wanted to do. The above line is actually doing a lexical comparison of the two strings converted from two double values.

Take a look at how the operator > is overloaded for string type in the basic_string.h :

/**
   * @brief Test if string follows string.
   * @param lhs First string.
   * @param rhs Second string.
   * @return True if @a lhs follows @a rhs. False otherwise.
   */
template
    inline bool
    operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) > 0; }

Notice that in the comments, it's stated as "Test if string follows string" and the implementation is using the basic_string::compare() method which by default will do a lexical comparison like this : it returns 0 if all the characters in the compared contents compare equal, a negative value if the first character that does not match compares to less (the character's ASCII value) in the object than in the comparing string, and a positive value in the opposite case.

So come to our example:
"800" > "750" : Ture, but
"1000" > "900" : False because '1' < '9'.

Fix it is simple, but the question is why the guy wrote this ? A simple mistake (and has been there since several years without being detected and corrected) ? I don't know exactly but tracking up in the code I found some clue that might explain.

Some lines before this buggy line, I found a similar comparison but it's only testing the equality of two double values and there, the double values are formatted into strings then compared for equality:

if (FormatToString(v1) != FormatToString(v2)) DoSomething();

This works fine and hides all the double value maths complexity behind the FormatToString method who knows exactly how many digits should be considered.

I guess later on, there comes another need to test not only for equality but also to know which value is larger then the guy took a simple copy-paste-modifiy way which results in this bug.

The the question comes back to how to compare two double values ? This is a hard question to answer, read this paper and you will know why. However, in our case, a really simple solution does exist. Guess what?

Just patch the shorter one of the two strings with leading '0's, then the lexical comparison will be an equivalent to the value comparison!

"1000" > "900" : False, but
"1000" > "0900": True !

Introduction to Algorithms - The Reading Notes: Part 7, The Quick Sort

2011-11-25T22:27:00.001+01:00

Now comes our famous QuickSort. It's famous because it's quick, so how quick it is? The answer from the theoretical analysis is Θ(n ln n) in average. OK, you may argue that the MergeSort and HeapSort we talked before also run in O(n ln n) , why this one is quicker? The answer is hidden in the big O notation, we usually don't write the constant factor in the function. In fact, QuickSort has a smaller hidden factor than others which distinguishes in practice QuickSort from the others. However, QuickSort can run, in the worst case, in O(n²) time. Now let's see how to write some code to do QuickSort.

As a starting point, we write our unit tests. As usual, we only need to add test cases in SortingTest.h and implement them in SortingTest.cpp.

    CPPUNIT_TEST( testQuickSort_0 );
    CPPUNIT_TEST( testQuickSort_1 );
    CPPUNIT_TEST( testQuickSort_Dec_0 );
    CPPUNIT_TEST( testQuickSort_Dec_1 );
...
    void testQuickSort_0();
    void testQuickSort_1();
    void testQuickSort_Dec_0();
    void testQuickSort_Dec_1();

The implementation of the tests which is quite straightforward, actually, same as tests for other sorting algorithms except the method used to sort, here we use QuickSort::Sort(v):

    // Setup Array.
...
    QuickSort::Sort(v);
...
    // Test Assertions.

Now if we try to compile, we will get some compiling errors, of course. We do not have our QuickSort class created. So now it's the time to create it.

    class QuickSort 
    {
        public:
            static void Sort(std::vector &v, bool bNonDecreasing = true);
        protected:
            static int  Partition(std::vector &v, int p, int r, bool bNonDecreasing);
            static void DoSort(std::vector &v, int p, int r, bool bNonDecreasing);
    };

The QuickSort provides exactly the same interface as other sorting algorithms which is the Sort method. As usual, we allow to sort in both non-decreasing and decreasing orders.

The DoSort method will recursively call itself to sort two sub-arrays partitioned by the method Partition.

Write the QuickSort class, compile it with scons, then run the unit tests. Failed!! Double check the code, then fix all the bugs until all unit tests pass. Below is the resulting code.

void QuickSort::Sort(std::vector &v, bool bNonDecreasing) 
{
    if (v.size() <= 1 )
    {
        return;
    }

    DoSort(v, 0, v.size()-1, bNonDecreasing);
}

int QuickSort::Partition(std::vector &v, int p, int r, bool bNonDecreasing)
{
    int pivot = v[r];
    int i = p-1; // i marks the end of the left partition.

    // j markes the end of the right partition
    for (int j = p; j <= r-1;  j++)
    {
        if ((v[j] < pivot &&  bNonDecreasing) ||
            (v[j] > pivot && !bNonDecreasing))
        {
            i++;
            int t = v[i];
            v[i]  = v[j];
            v[j]  = t;
        }
    }
    v[r] = v[i+1];
    v[i+1] = pivot;

    return i+1;
}

void QuickSort::DoSort(std::vector &v, int p, int r, bool bNonDecreasing)
{
    std::cout << "Sorting sub array: " << p << ":" << r << std::endl;
    if (p < r)
    {
        int q = Partition(v, p, r, bNonDecreasing);
        DoSort(v, p, q-1, bNonDecreasing);
        DoSort(v, q+1, r, bNonDecreasing);
    }
}

About this document ...

ITA Reading Notes This document was generated using the LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -html_version 4.0,math -no_navigation -scalable_fonts -split 0 -no_auto_link ITAReadingNotes-Main
The translation was initiated by Bing Han on 2011-11-25

Introduction to Algorithms - The Reading Notes: Part 6, The Heap Sort

2011-11-20T22:50:00.001+01:00

Heap Sort

The basic idea of Heap Sort is to sort with help of a special data structure called heap. A heap is a binary tree where each note in the tree contains a value. If the value of each node is no less than it's children, we call it a Max-Heap. If the value of each node is no more than it's children, we call it a Min-Heap.

Don't be confused by name heap, which is also used commonly as a notion of a region of memory space where program can dynamically allocate.

Heap is very interesting, on one hand, it's a binary tree, so it benefits binary tree properties such as it's height grows logarithmically with the number of nodes it has; on the other hand, it has one important order relationship between parent and child nodes.

As usual, we won't discuss in detail the theoretical aspect of the algorithm, instead, we focus on the implementation of the algorithm.

Before implementing the algorithm, let's first setup the unit test. As we already has our test infrastructure for previous sorting algorithms we discussed, we simply need to add some test cases inside.

For Heap Sort, I'm going to create a class with name HeapSort which provides a Sort method as other sort algorithms. So in the CppUnitTest/SortingTest.h, I add some test cases and their declarations:

CPPUNIT_TEST( testHeapSort_0 );
    CPPUNIT_TEST( testHeapSort_1 );
...
    void testHeapSort_0();
    void testHeapSort_1();

Then I define those tests (methods) in the CppUnitTest/SortingTest.cpp:

void SortingTest::testHeapSort_0()
{
    int iArray[] = {10, 5, 7, -2, 19, 50, 300, 320, 160, 1000};
    std::vector v(iArray, iArray + sizeof(iArray) / sizeof(int));
    HeapSort::Sort(v);
    CPPUNIT_ASSERT_EQUAL(v[0], -2);
    CPPUNIT_ASSERT_EQUAL(v[1], 5);
    CPPUNIT_ASSERT_EQUAL(v[2], 7);
    CPPUNIT_ASSERT_EQUAL(v[3], 10);
    CPPUNIT_ASSERT_EQUAL(v[4], 19);
    CPPUNIT_ASSERT_EQUAL(v[5], 50);
    CPPUNIT_ASSERT_EQUAL(v[6], 160);
    CPPUNIT_ASSERT_EQUAL(v[7], 300);
    CPPUNIT_ASSERT_EQUAL(v[8], 320);
    CPPUNIT_ASSERT_EQUAL(v[9], 1000);
}


void SortingTest::testHeapSort_1()
{
...
}

Now I can start coding the HeapSort class. First, I declare the main interface method, which is Sort for the HeapSort class, then I declare some helper methods Sort will use.

Same as described in the ITA, we will construct a binary tree directly on the input array, by using the index of an item in the array. So item 0 is always the root of the heap tree. Then, item 1 and 2 are two children of item 0, item 3 and 4 are two children of item 1, item 5 and 6 are children of item 2, and so on. In short, given a node i , we know that it's left child is 2*i + 1 and it's right child is (i + 1)*2 , if they exist, where i starts from 0. As for it's parent, it depends. If i = 0 , then it's the root node, so it does not really have a parent, otherwise, the parent node's index can be computed as (i - 1)/2 .

We declare Parent, Left and Right methods to do the computation described above.
Also, the Heap Sort is based on first building a MaxHeap ( in case we need to sort non-decreasingly, otherwise, we build a MinHeap), then each time takes the root (which is the largest item in the heap), then reconstruct the heap. So we will also declare two auxiliary methods BuildMaxHeap and MaxHeapify to do the job. Methods for building and reconstructing MinHeap are also provided. The whole HeapSort class declaration looks like follows:

class HeapSort 
{
    public:
    static void Sort(std::vector &v, bool bNonDecreasing = true);

    protected:
    static int  Parent(const int i) { return ((i > 0) ? (i - 1) >> 1: 0); }
    static int  Left(const int i)   { return (i << 1) + 1; }
    static int  Right(const int i)  { return (i + 1) << 1; }

    static void BuildMaxHeap(std::vector &v);
    static void BuildMinHeap(std::vector &v);
    static void MaxHeapify(std::vector &v, const int i, const int iHeapSize);
    static void MinHeapify(std::vector &v, const int i, const int iHeapSize);
};

Now comes the time to implement those methods. We will implement them in a bottom-up way. So, first look at the MaxHeapify method, it takes three parameters, a vector representing the heap (or a binary tree to be built to a heap) and a integer i which is an index in the vector, representing a sub-tree rooted at i . Also the heap size is provided as the third parameter. MaxHeapify assumes that two sub-trees rooted at both of i 's children are already MaxHeaps, only i is possibly violating the MaxHeap property. So the goal is just to make a MaxHeap rooted at i . To this end, it simply recursively floats down the content of node i until a proper place is found. "Float down" is just an exchange of i with the maximum of i , Left(i ) and Right(i ). Of cause, in case that the maximum is i itself, nothing needs to be done. The code reads as follows:

void HeapSort::MaxHeapify(std::vector &v, const int i, const int iHeapSize)
{
    int l = Left(i);
    int r = Right(i);

    int largest = i;

    if ( l < iHeapSize && v[l] > v[i])
    {
        largest = l;
    }

    if ( r < iHeapSize && v[r] > v[largest])
    {
        largest = r;
    }

    if (largest != i)
    {
        int temp = v[largest];
        v[largest] = v[i];
        v[i] = temp;

        MaxHeapify(v, largest, iHeapSize);
    }
}

Next, we will implement BuildMaxHeap. With the help of MaxHeapify, this is fairly straightforward. We simply need to first MaxHeapify the sub-trees at the lowest level (actually the next to lowest, as the lowest are leaf nodes that does not have any child so trivially they are MaxHeap). As a result, we can start MaxHeapify the sub-trees from the middle of the vector. The trick is, given a vector of size n , if we count from the end of the vector, the first item that may have a child always appears no early than the n/2 th item (think why?). As a result, we have the following simply implementation of BuildMaxHeap:

void HeapSort::BuildMaxHeap(std::vector &v)
{
    for (int i = (v.size() >> 1); i >= 0; i--)
    {
        MaxHeapify(v, i, v.size());
    }
}

We can implement similar methods for MinHeap too.

Now that we have everything in hand, let's implement the final method Sort. We start by building a MaxHeap (or MinHeap), then each time, we exchange the root of the heap (item 0) with the last item in the heap. This exchange does two things: put the current largest at the end of the vector and put a smaller one at the heap root, breaking heap property. Then we use MaxHeapify to reconstruct the heap.
Once the heap is reconstructed, we have again the largest item at root, then we simply repeat the exchange-reconstruct. The code looks like the following, sorting by non-decreasing or non-increasing order are supported with parameter bNonDecreasing, as other sort algorithms:

void HeapSort::Sort(std::vector &v, bool bNonDecreasing) 
{
    if (v.size() <= 1 )
    {
        return;
    }
    
    if (bNonDecreasing)
    {
        BuildMaxHeap(v);
    }
    else
    {
        BuildMinHeap(v);
    }

    int iHeapSize = v.size();
    
    for (int i = v.size() - 1; i >=1; i--)
    {
        int temp = v[0];
        v[0] = v[i];
        v[i] = temp;

        iHeapSize--;
        if (bNonDecreasing)
        {
            MaxHeapify(v, 0, iHeapSize);
        }
        else
        {
            MinHeapify(v, 0, iHeapSize);
        }
    }
}

About this document ...

Introduction to Algorithms - The Reading Notes: Part 5, Maximun Sum Sub-Array (DAC)

2011-11-20T22:50:00.000+01:00

To be completed.

Fedora 16 Release

2011-11-12T22:05:00.000+01:00

Fedora 16 released on November 8, 2011!

I tried to download the 3.5GB DVD image with firefox under windows. I started the download quite late last night, as it takes about 2 hours to finish, I paused it and shut down my PC then went to bed. I resumed it this morning and it finished later, but surprisingly, the resulted .iso file has 6GB!!

I don't know how the firefox downloader worked on it but I do know, I don't have a DVD on which I can write a 6GB image. However, instead delete the bad file directly, I'm curious to see how bad it is. Interestingly, I can mount it with a WinISO virtual driver and then I can open it. Selecting all items in the image, the total size seems correct, i.e. about 3.5GB.

Of cause, the SHA256 checksum failed. (See here on how to verify the image)

Finally, I switched to Fedora and let wget get the things done and it did it correctly.

So, now I have the DVD image to write and install ! :D

Fedora 16 Soon!

2011-10-31T16:18:00.001+01:00

Fedora 15!

2011-06-11T21:49:00.002+02:00

Released at 24 May, the Lovelock is another great step to a better user experience. I installed it today and was shocked by the revolutionary changes to the GNOME desktop, now it's the GNOME shell that I'm interacting with.

It may seem unfamiliar and even irritating when I found no minimize button and everything in my Desktop folder does not show up on the desktop and I have to find applications in another place. But, but, but after I read the release note which is well prepared for the situation that a user like me can have, it answered me all my questions, and in one hour, I started to love it! Fedora name this 15th release Lovelock, does that mean something?

The Super key is really handy, it calls up immediately all windows opened for you to select one. Also it brings the launch bar to front so launching an application can be done instantly with the advantage that it does not take any space when you are working in the application.

Also the Firefox 4, just great! I love it, especially the Sync.

As a programmer, I have the gcc 4.6 in this new release, I have vim 7.3, I have sons 2.0.1 ...

All in all, I love the Lovelock, better than ever.

Introduction to Algorithms - The Reading Notes: Part 4, Maximun Sum Sub-Array (BF)

2011-06-11T14:24:00.000+02:00

Maximum Sub Sub-Array is an interesting problem. It goes like this, I'm given a series of values and I'm asked to find a continuous sub-series that has the maximum sum.

For example, if I'm given a series of value -3, 2, 5, 6, -1, 2, -5, 5, then I find that the sub-series 2,5,6 gives 13 which quite large, but 2, 5, 6, -1, 2 sums up even more, it gives 14. If I look further, I find that the sub-series 2, 5, 6, -1, 2, -5, 5 gives the same maximum of 14. So we may have more than one maximum and our goal is to find any one of them.

ITA mentions the brutal force algorithm that has Ω(n^2) running time, it says the algorithm is to calculate sums of all sub-series possible (there is O(n^2) number of sub-series) and if we can evaluate each sub-series in constant time then we can have Ω(n^2) algorithm, but it does not say how. ITA introduces also a very fast (O(nlgn) algorithm based on DaC (Divide and Conquer).

I understand that this ITA chapter is for DaC so no need to talk more details on this brutal force algorithm and it's put in the exercise. So, let's finish the Ω(n^2) brutal force algorithm first then we will see how to implement the DaC one.

So you already know the number of sub-series is O(n^2), suppose we have a n-length series, but why? The answer is this number equals to the number of ways you have when you try to select any two numbers in the series (those two numbers defines the start and end of the sub-series), that is n(n-1)/2.

Now comes to the question how we calculate the sum of each sub-series. If we just simply calculate sums for all sub-series, then we have to sum n sub-series of length 1, n-1 sub-series of length 2, n-2 sub-series of length 3, ..., 1 sub-series of length n. In total, we need to do add n+2(n-1)+3(n-2)...+ n times, which is equivalent to sum(for i = 1 to n) (i*(n-i+1)), which renders our algorithm O(n^3) in terms of time consumption.

Now we need to do more to get a faster algorithm. Just one more glance at our previous O(n^3) algorithm we find that the sub-series have many common parts and we add those parts repeatedly many times once for each sub-series. That's the key to reduce running time.

I will now use a n*n matrix to save sums of each sub-series, say, [0-1], [0-2]... [1,2], [1,3]... Also each single element represents also a sub-series of length 1, they are also stored in the matrix [0,0], [1,1] ... So only the upper triangle of the matrix is used. The advantage to save the sums in the matrix is that it's very easy to find a sub-series that can be used to build the next sum, because we know that:
sum(sub[i, j]) = sum(sub[i, j-1]) + v[j] = sum(sub[i, j-1]) + sub[j, j]

OK, that's enough for the theory, let's see the code. But wait a moment, before implementing the algorithm, let's put in place the unit test!

I'll use another class for the MaxSubArray unit test, separated from that of the sort algorithms. With CppUnit, I just simply create a .h and .cpp for the new tests, no other configuration is needed.

MiscTest.h

   1:  #ifndef MISCTEST_H

   2:  #define MISCTEST_H

   3:  #include <cppunit/extensions/HelperMacros.h>

4:

5:

   6:  class MiscTest : public CppUnit::TestFixture {

7:

   8:      CPPUNIT_TEST_SUITE( MiscTest);

   9:      CPPUNIT_TEST( testMaxSubArray_0);

  10:      CPPUNIT_TEST_SUITE_END();

11:

  12:      private:

  13:      public:

14:

  15:      void setUp();

  16:      void tearDown();

17:

  18:      // Test cases.

  19:      void testMaxSubArray_0();

20:

  21:  };

  22:  #endif

MiscTest.cpp

   1:  #include "MiscTest.h"

   2:  #include "MaxSubArray.h"

3:

   4:  using namespace Common::Algorithm::MaxSubArray;

5:

   6:  // Registers the fixture into the 'registry'

   7:  CPPUNIT_TEST_SUITE_REGISTRATION( MiscTest );

8:

   9:  void MiscTest::setUp()

  10:  {

  11:  }

  12:  void MiscTest::tearDown()

  13:  {

  14:  }

15:

  16:  // Test normal case.

  17:  void MiscTest::testMaxSubArray_0()

  18:  {

  19:      int iArray[] = {-10, 5, 7, -2, 19, 50, -30, 32, -24, 18};

  20:      std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int));

21:

  22:      int rStart = 0;

  23:      int rEnd = 0;

  24:      int rSum = 0;

  25:      MaxSubArray::CalcBF(v, rStart, rEnd, rSum);

26:

  27:      CPPUNIT_ASSERT_EQUAL( 1, rStart);

  28:      CPPUNIT_ASSERT_EQUAL( 7, rEnd);

  29:      CPPUNIT_ASSERT_EQUAL(81, rSum);

30:

  31:  }

Finally, I can start implementing the algorithm. Then I run the unit test each time I think my algorithm will work, then fix bugs and retry. Here is the final version that passes the test above:

   1:  void MaxSubArray::CalcBF(std::vector<int> &v, int &oStart, int &oEnd, int &oSum)

   2:  {

   3:      // Trivial cases, size = 0 or 1.

   4:      if (v.size() == 0)

   5:      {

   6:      oStart = 0;

   7:      oEnd = 0;

   8:      oSum = 0;

   9:      return;

  10:      }

11:

  12:      if (v.size() == 1)

  13:      {

  14:      oStart = 0;

  15:      oEnd = 0;

  16:      oSum = v[0];

  17:      return;

  18:      }

19:

  20:      oSum= 0;

  21:      oStart = 0;

  22:      oEnd = 0;

  23:      std::vector<int> vResult;

24:

  25:      // Initialize vResult.

  26:      for (size_t i = 0; i < v.size(); i++)

  27:      {

  28:      for (size_t j = 0; j < v.size(); j++)

  29:      {

  30:          if (i == j)

  31:          {

  32:          vResult.push_back(v[i]);

  33:          }

  34:          else

  35:          {

  36:          vResult.push_back(0);

  37:          }

  38:      }

  39:      }

40:

41:

  42:      // Calculate the results.

  43:      // We use a matrix to store sum of all intervals

  44:      // 00   01   02   03   04

  45:      // 10   11   12   13   14

  46:      // 20   21   22   23   24

  47:      // 30   31   32   33   34

  48:      // 40   41   42   43   44

  49:      // M[i,i] = v[i]

  50:      // M[i,j] = sum(i,j) for 0 <= i < j <= v.size().

  51:      // It takes O(n^2) time.

  52:      for (size_t i = 0; i < v.size(); i++)

  53:      {

  54:      for (size_t j = 0; j < v.size(); j++)

  55:      {

  56:          if (i < j)

  57:          {

  58:          vResult[ i * v.size() + j] = vResult[ i * v.size() + j - 1 ] +

  59:                                       vResult[ j * v.size() + j];

  60:          if (oSum < vResult[i * v.size() +j])

  61:          {

  62:              oSum = vResult[i * v.size() + j];

  63:              oStart = i;

  64:              oEnd = j;

  65:          }

  66:          }

  67:      }

  68:      }

  69:  }

Let discuss the faster version that takes only O(nlgn) time, in the next post. Thank you and like to know your feedback.

Introduction to Algorithms - The Reading Notes: Part 3, Merge Sort

2011-06-02T15:17:00.001+02:00

Merge sort is a better sorting algorithm than insertion sort in terms of worst case running time. It's also the algorithm that I ran into when I have my interview for my current job.

The ITA book uses it as an example of the Divide and Conquer philosophy which basically divides a big problem into several smaller ones then solve each of them first, when the smaller problems are solved, the big problem becomes easier to solve. This usually results in a recursive algorithm as the case of the merge sort. I'm not sure it's a good place to introduce this concept in the beginning part of the book, the learning curve is quite steep.

The merge sort contains two parts, the divide or recursive part and the merge part. The idea is to divide the whole list to sort into two lists each of half the original size and sort the two lists separately, then merge the two sorted smaller lists into one sorted list to get the problem solved. The magic is to repeat this procedure for the two smaller lists too, so they became four even smaller lists, and so on.

The merge part is quite straightforward, compare the elements at the head position of two sorted list, and put the larger (or smaller) into the result list until one of the list contains no element, then we can safely put the rest of the other list into the result list. Only one thing to remark, the vector constructor who takes to iterators s and e means to construct a vector that contains elements from s to e-1 of the original vector.

   1:  void MergeSort::Merge(std::vector<int> &v, int p, int q, int r, bool bNonDecreasing)

   2:  {

   3:      std::cout << "Merging sub array: " << p << ":"<< q-1 << " and " << q << ":" << r-1 << std::endl;

   4:      std::vector<int> vSub1(v.begin()+p, v.begin()+q);

   5:      std::vector<int> vSub2(v.begin()+q, v.begin()+r);

   6:      std::cout << "vSub1.size: " << vSub1.size() << ", vSub2.size: "<< vSub2.size() << std::endl;

   7:      int iLastValue = (bNonDecreasing ? INT_MAX : INT_MIN);

8:

   9:      vSub1.push_back(iLastValue);

  10:      vSub2.push_back(iLastValue);

11:

  12:      int i = 0;

  13:      int j = 0;

  14:      for (int k = p; k < r; k++)

  15:      {

  16:      if ( bNonDecreasing && (vSub1[i] < vSub2[j]) ||

  17:          !bNonDecreasing && (vSub1[i] > vSub2[j]))

  18:      {

  19:         v[k] = vSub1[i];

  20:         i++;

  21:      }

  22:      else

  23:      {

  24:          v[k] = vSub2[j];

  25:          j++;

  26:      }

27:

  28:      }

  29:  }

The recursive part is a bit tricky. Personally, I prefer to give a unique interface to the users of my sorting library, so I'd like to call my interface MergeSort::Sort(input_vector_to_sort, order). Then I found that I need a helper method that can be called recursively and I named it as DoSort(). DoSort() takes two additional parameters, the start and the end position in the list that defines the sub-list to be sorted. It starts by dividing the input vector into two smaller ones then it calls itself recursively for each smaller vector, finally it merges the two smaller vector (sorted now).

   1:  void MergeSort::DoSort(std::vector<int> &v, int p, int r, bool bNonDecreasing)

   2:  {

   3:      std::cout << "Sorting sub array: " << p << ":" << r << std::endl;

   4:      if (p < r)

   5:      {

   6:      int q = (p+r)/2;

   7:      std::cout << "Dividing sub array: " << p << ":" << q  << ", " << q+1 << ":" << r << std::endl;

   8:      DoSort(v, p, q, bNonDecreasing);

   9:      DoSort(v, q+1, r, bNonDecreasing);

  10:      Merge(v, p, q+1, r+1, bNonDecreasing);

  11:      }

  12:  }

Finally, the interface method is fairly simple:

   1:  void MergeSort::Sort(std::vector<int> &v, bool bNonDecreasing)

   2:  {

   3:      if (v.size() < 1 )

   4:      {

   5:      return;

   6:      }

7:

   8:      DoSort(v, 0, v.size()-1, bNonDecreasing);

   9:  }

Introduction to Algorithms - The Reading Notes: Part 2, Insertion Sort

2011-05-11T21:38:00.003+02:00

Insertion Sort is probably the simplest algorithm so it is used in many books as the first example. ItA discusses this minion algorithm right in the Part I Foundations, Chapter 2 Getting Started.

The aim of the algorithm is to sort a set of keys in a certain order: You have some keys as input then the algorithm will give you a ordered list of your keys. Here is how the insertion sort works: suppose all the keys are in an input list, then the algorithm starts working on the the keys one by one in a certain order, for example from left to right. Each time it works on a key, it save it's value, then it looks all keys already processed (they are to the left of the current key), from right to left, by comparing the current key with them and moving the processed keys one place to the right if it should be placed after the current key, according to the ordering rule. This process ends until when an already processed key that should be placed to the left of the current key or there is no more already processed keys. Then we put the current key in the place of the last already processed key we found. Now that we find a good place for the current key, we can start processing the next unprocessed key.

The algorithm is simple, code the pseudo code in C++ is straightforward. What I'd to say here is how I set up the whole project with CppUnit and SCons.

CppUnit is very handy for unit test, especially when I'm writing libraries. Just as in this ITA project, I'd like to put all the algorithms in some libraries, I don't need to write a separate main cpp file just to test these algorithms, instead, I setup a CppUnit testing framework for this. It's easier to maintain. For how to install/use CppUnit, here is the CppUnit Documentation.

First, I implement the Insertion Sort algorithm in InsertSort.cpp and .h files and I put them in a folder named Sorting. With TDD in mind, I write only the class declaration but leaving the method empty.

Then I setup the CppUnit framework: I need three files: SortingTest.h and .cpp, where I'll implement test code for all the sorting algorithms I'll write; TestMain.cpp. where is the "main" function of the test code. The beauty of using CppUnit is this "main" function has only infrastructure interest, it's not related to the particular test cases. So once setup, I don't need to change it. I'll only work on the SortingTest class.

Now I will write a test case:

   1:  // Test normal case.

   2:  void SortingTest::testInsertSort_0()

   3:  {

   4:      int iArray[] = {10, 5, 7, -2, 19, 50, 300, 320, 160, 1000};

   5:      std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int));

   6:      Common::Algorithm::Sort::InsertSort(v);

   7:      CPPUNIT_ASSERT_EQUAL(v[0], -2);

   8:      CPPUNIT_ASSERT_EQUAL(v[1], 5);

   9:      CPPUNIT_ASSERT_EQUAL(v[2], 7);

  10:      CPPUNIT_ASSERT_EQUAL(v[3], 10);

  11:      CPPUNIT_ASSERT_EQUAL(v[4], 19);

  12:      CPPUNIT_ASSERT_EQUAL(v[5], 50);

  13:      CPPUNIT_ASSERT_EQUAL(v[6], 160);

  14:      CPPUNIT_ASSERT_EQUAL(v[7], 300);

  15:      CPPUNIT_ASSERT_EQUAL(v[8], 320);

  16:      CPPUNIT_ASSERT_EQUAL(v[9], 1000);

  17:  }

The aim of the test case is to test the basic function of the algorithm, I initialize a vector with 10 integers, then I call the InsertSort(), finally, I test that the vector is sorted by examining that each element has the expected value. CppUnit provides a macro CPPUNIT_ASSERT_EQUAL for this kind of test.

Now that I have the algorithm code (although not yet complete), I have the testing code, I can compile both and run my test. I use SCons for this. SCons is very convenient yet powerful. Basically, you write a configuration file usually named as SConstruct, inside you tell scons how to build your project.

   1:  Library(target='Sorting/Sorting', \

   2:          source=Glob('Sorting/*.cpp'))

   3:  Program(target='CppUnitTest/TestMain', \

   4:          source=Glob('CppUnitTest/*.cpp'), \

   5:          LIBS=['cppunit','Sorting'], \

   6:          LIBPATH='Sorting', \

   7:          CPPPATH=['Sorting', 'CppUnitTest'])

The Library keyword at line 1 specifies a library to build, the source code are all the .cpp files in the Sorting folder.

The test code should be built with the Program keyword, as in line 3. It needs all source code in the CppUnitTest folder and two libraries: the CppUnit library and the Sorting library that I'm testing. The Sorting library is in my local folder so I need to tell SCons where to find it with LIBPATH keyword as in line 6 above. Finally, the test code need the Sorting library header to compile, I'll tell SCons to find the Sorting headers in the Sorting folder with CPPPATH keyword as in line 7.

OK, now I save the Sconstruct file then I type scons. It compiles my Sorting library and the testing code.

I can run the test immediately and it fails evidently. Now you can start to write the InsertSort() method, but personally, I will write some more test cases before writing the InsertSort() method. For example, I will write one case when the input is empty, another when all inputs have the same value, etc.

Finally, I write my InsertSort() method and correct all failing cases, once all test cases pass, I'm quite confident that my InsertSort() works correctly.

Here is the how the InsertSort() is implemented:

   1:  void Sort::InsertSort(std::vector<int> &v)

   2:  {

   3:      int key = 0;

4:

   5:      // Trivial case, nothing to do.

   6:      if (v.size() <= 1)

   7:      {

   8:          return;

   9:      }

10:

  11:      for (int j = 1; j < v.size(); j++)

  12:      {

  13:          key = v[j];

  14:          int i = j-1;

  15:          while (i >= 0 && v[i] > key)

  16:          {

  17:              v[i+1] = v[i];

  18:              i--;

  19:          }

  20:          v[i+1] = key;

  21:      }

  22:  }

23:

Modification: When I started to write the merge sort, I found it could be better to rename the class and the methods, and finally, I ended up with a solution that gives each sorting algorithm a class and they all have the same Sort() method declaration.

   1:  void InsertSort::Sort(std::vector<int> &v, bool bNonDecreasing)

Introduction to Algorithms - The Reading Notes: Part 1, Introduction

2011-05-09T11:43:00.001+02:00

I started reading this book recently and I will share my understandings and thoughts with you.

I will discuss the problems in the book and I'd like to inject in particular more on the software engineering aspects of those algorithms: how to implement them so they can be used in a real-life software project to solve practical problems.

Finally, I will code those algorithms in C++ and build the code under Fedora Linux with Scons. I will also adopt the TDD methodology (TDD stands for Test Driven Development) and use CppUnit for unit testing.

Here are some useful links for this project:
The code formatter, it formats the source code into HTML so they look better when put in the blog. Currently it formats C#, VB and some other languages but not C/C++. I'll continue looking for one but before I find something, I'll use this one for the moment.

The SCons user's guide.

The CppUnit Documentation.

A Real-life Story about Return by Reference - Part II

2011-05-07T16:37:00.000+02:00

Now we know that we should follow some "best practices" when dealing with return by reference:

1. Use toto aToto = getToto() or toto aToto(getToto()), don't write toto aToto; aToto = getToto();

2. Don't return a reference to a local variable, except when you know what you are doing

3. Let member function return a reference to a member variable when the performance is really an issue, and call it with toto &aTotoRef = aToto.getTotoRef() to really take advantage of return by reference. Otherwise, return by value. Always take care of the variable holding the reference result, use it only during the life time of the object itself.

There is one last thing you may want to know, that is the RVO does not work all the time, as a result it cost you one more construction/destruction of your object when you return it by value. I won't say it's a penalty you have to pay, it's just the fair cost you have to pay as the compiler can not help you more because your code asks for more. So when RVO does not work? Well, when the compiler can not decide which is the object it needs to return at compile time. Here is an example:

toto getTotoWithParam(bool first)
{
    if (first)
    {
        toto aToto;
        return aToto;
    }
    else
    {
        toto bToto;
        return bToto;
    }
}

Then, when calling this function, it will show you that the RVO is not apllied.

toto a = getTotoWithParam(false);
toto constructor.
toto copy constructor.
toto destructor.
toto destructor.

The object is constructed inside the function then used to copy construct the object holding the result. Compared with the getToto() function, one more object (temporary object) is created.

toto aToto = getToto():
toto constructor.
toto destructor.

So that all about the return by value/reference that I want to tell you, I hope you now know what to do given a certain situation.

Good luck and I'd like to know what you are thinking about this.

Books to read (once more)

2011-04-24T23:39:00.001+02:00

Mathematics, Data Structures & Algorithms

Discrete Mathematics and Its Applications (Fifth Edition), Kenneth H.Rosen

Concrete Mathematics : A Foundation for Computer Science (Second Edition), Ronald L. Graham / Donald E. Knuth / Oren Patashnik

Introduction to Algorithms (Second Edition), Thomas H. Cormen / Charles E. Leiserson / Ronald L. Rivest / Clifford Stein

Data Structures, Algorithms, and Applications in C++， Sartaj Sahni
Data Structures & Program Design In C (Second Edition), Robert Kruse / C.L. Tondo / Bruce Leung

The Art of Computer Programming
Donald E.Knuth

Compiler

Compilers: Principles, Techniques, and Tools (2nd Edition)
[Alfred V. Aho / Ravi Sethi / Jeffrey D. Ullman]

Advanced Compiler Design and Implementation
[Steven S. Muchnick]

Operating System

Operating System Concepts (Now we have the 7th Edition)
[Abraham Silberschatz / Peter Baer Galvin / Greg Gagne]

Operating Systems : Design and Implementation (Now we have the 3rd Edition)
[Andrew S. Tanenbaum / Albert S. Woodhull]

C++

C++ Primer
Lippman / Josee Lajoie]

The C++ Programming Language (Special Edition)
[Bjarne Stroustrup]

Effective C++ (Now we have the 3rd Edition)
More Effective C++
Scott Meyers

C++ Gotchas: Avoiding Common Problems in Coding and Design
Stephen C.Dewhurst

Modern C++ Design: Generic Programming and Design Patterns Applied
Andrei Alexandrescu

ASM

The Art of Assembly Language
Randall Hyde (x86)

Introduction to 80x86 Assembly Language and Computer Architecture
Richard C. Detmer

UNIX Programming

Advanced Programming in the UNIX Environment
[W. Richard Stevens]

The UNIX Programming Environment
[Brianw. Kernighan]

UNIX Network Programming, Volume 1 : The Sockets Networking API (Third Edition)
[W. Richard Stevens / Bill Fenner / Andrew M. Rudoff]

UNIX Network Programming Volume 2 : Interprocess Communications (Second Edition)
[W. Richard Stevens]

Computer Networks

Computer Networks (Fourth Edition)
[Andrew S. Tanenbaum]

TCP/IP Illustrated, Volume 1 : The Protocols
TCP/IP Illustrated, Volume 2 : The Implementation
TCP/IP Illstrated, Volume 3 : TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols
[W. Richard Stevens]

Internetworking with TCP/IP Vol I : Principles, Protocols, and Architecture (Third Edition)
Internetworking with TCP/IP Vol II : Design, Implementation, and Internals (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, BSD Socket Version (Second Edition)
Internetworking with TCP/IP Vol III : Client-Server Programming and Applications, Windows Sockets Version
[Douglas E. Comer / David L. Stevens]

Database

An Introduction to Database Systems (Seventh Edition)
[C. J.Date]

Database System Concepts (Fourth Edition)
[Abraham Silberschat / Henry F.Korth / S.Sudarshan]

Software Engineering

Code Complete， Steven C. McConnell

Pragmatic programmer: from journeyman to master， Andrew Hunt and David Thomas
Peopleware：Productive Projects and Teams, Tom DeMarco, Timothy Lister

A Real-life Story about Return by Reference - Part I

2011-03-09T08:26:00.000+01:00

Recently I did some new development on our software. As a standard process, I submitted my work to a code review. One of my colleagues suggested me, for one of my method, using a reference as the return type instead of an object, for example:
class toto ()
...

toto getToto();
toto &getToto();

His concern is the that return by reference is more efficient than return by value. Personally, I do not think much about efficiency but more on the correctness and clearness of the code, so for a long time, I return everything by value except for very rare cases such as overloading the operator << , etc. His suggestion triggered me to investigate more this point.

Let's consider return by value first so we have something to compare with. So how to write a function that returns an object by value? Well it's simple.
toto getToto()
{
   toto myToto;
   // Here I can work with myToto.
   return myToto;
}
Or if I really have very simple work to do with the myToto, I can write also:
toto getToto()
{
   return toto();
}

Basically, we have the following ways to use the functions:
toto aToto = getToto(); // get a toto and hold it with aToto

toto aToto(getToto()); // construct aToto with the result of getToto with its copy constructor.

getToto(); // get a toto and do nothing with it. Not useful by valid call.
toto aToto; aToto = getToto(); // assign the result of getToto to an existing object.

That is not all the story yet, we still have another way to call the getToto:

const toto &aRefToto = getToto();

What we are doing here is to bind a reference to a constant to the result of getToto, which is a temporary object so we are not allowed to call it without the 'const' like: toto &aRefToto = getToto(); (at least we cannot do it now with most modern compilers. ).

So which one is more efficient ? It depends on the compiler. Actually, this is a feature usually named as RVO, Return Value Optimization. C++ standard leaves this to the implementation of the compiler. Modern compilers such as gcc does quite well so all the first three examples and the last one have the same best performance: only one object is created in the function, so the constructor and destructor get called only once. Only the fourth example cost more, which is caused by the assignment.

So here is the output of a test program:
toto aToto = getToto():
toto constructor.
toto destructor.

toto aToto(getToto());

toto constructor.

toto destructor.

getToto():

toto constructor.

toto destructor.

toto aToto; aToto = getToto();

toto constructor.

toto assignment.

toto destructor.

const toto &aRefToto = getToto();

toto constructor.

toto destructor.

It is amazing to know that when you call toto aToto = getToto() or toto aToto(getToto()), you have actually zero overhead, the constructor and destructor are called only once for the object that is created inside the function. Also it's amazing to know the difference (the penalty you are paying) when you write something like: toto aToto; aToto = getToto(); once more constructor and destructor and one more assignment!

CONCLUSION ONE: Use toto aToto = getToto() or toto aToto(getToto()), don't write toto aToto; aToto = getToto();

Now let's consider the cases when we return by reference.
Things are a little different when it comes to return by reference. Obviously, you are not allowed to return the reference of a temporary object, so the following form is invalid:
toto &getTotoRef()
{
   return toto();
}
Now we only have on possibility to return a reference of an object:
toto &getTotoRef()
{
   toto aToto;
   return aToto;
}

As far as you remember that the reference is "just another name of the referred object", you may notice that we are doing a dangerous thing here by returning a reference of a local object. Absolutely, you are right. A decent compiler will warn you that you are returning a reference to a local variable. Personally, I never return reference to a local object. This is just to demonstrate the efficiency aspect.

So here we have three ways to use the getTotoRef().
toto &aRefToto = getTotoRef(); // Don't do like this!
toto aToto = getTotoRef(); // construct with result of getTotoRef()
toto aToto(getTotoRef()); // construct with copy constructor.
getTotoRef(); // useless, but valid.
toto aToto; aToto = getTotoRef(); // assign result of getTotoRef() to an existing variable.

Here is the output of the call sequence when the test program runs:

toto &aRefToto = getTotoRef():

toto constructor.

toto destructor.

toto aToto = getTotoRef();

toto constructor.

toto destructor.

toto copy constructor.

toto destructor.

toto aToto(getTotoRef());

toto constructor.

toto destructor.

toto copy constructor.

toto destructor.

getTotoRef();

toto constructor.

toto destructor.

toto aToto; aToto = getTotoRef();

toto constructor.
toto constructor.
toto destructor.
toto assignment.
toto destructor.

So if you use a reference to hold the result of getTotoRef, you have the maximal gain of return by reference: there is no overhead at all. Otherwise, either the copy constructor or the assignment need to be called to construct a new object based on the result of getTotoRef. However, with the first form which is most efficient here, you are bound to have unexpected behavior later when you want to use your reference so don't do that.

CONCLUSION TWO: Don't return a reference to a local variable, except when you know what you are doing :D

So why we have this feature to return a reference in C++? Well, this allows you to do something like:
toto &forwardToto(toto &comingToto)
{
   return comingToto;
}
So here you don't need to create any object. The interest here is that if a function returns a reference, it can appear at the left side of an operator, so the following is valid:
forwardToto() = aToto;
And opens the possibility to do something like cout << "blabla" << endl; because << is overloaded to return a reference. For more on how to overload the operator <<, you should take a/another look at the great book by Prata: C++ Primer Plus (5th Edition)

We can also profit this feature in a member function of a class, but with a lot of care. So think about the tradeoff first.
Suppose we have a class with a member variable, and we have a getter of this variable, so we can make the getter return a reference, like:
class totoClass
{
public:
   toto &getTotoRef();
   _myToto;
}

Then you have the following ways to use this getter:
toto bToto = aToto.getTotoRef(); // Construct bToto.
toto bToto(aToto.getTotoRef()); // Construct bToto.
toto &bToto = aToto.getTotoRef(); // bToto refers to aToto._myToto.
bToto = aToto.getTotoRef(); // assign aToto._myToto to an existing bToto.

What do we pay for each call? Here is the result:

toto bToto = aToto.getTotoRef();

toto copy constructor.

toto destructor.

toto bToto(aToto.getTotoRef());

toto copy constructor.

toto destructor.

toto &bToto = aToto.getTotoRef();

** Nothing is called.

bToto = aToto.getTotoRef();

toto assignment.

OK, not bad, we call once the copy constructor when we want to save the result in another object, fair enough. If we only get the reference as in the third example, we don't need to call any toto constructor/copy constructor/assignment/destructor. That is a big saving if these operations are costly themselves. However, you can do this ***only if you are able to make sure that your totoClass object lives longer than your variable holding the result.

In comparison, tradition getters that return a value is not too bad. Here is what we have:

class totoClass

{

public:

toto getToto(); // get by value.

_myToto;

}

toto bToto = aToto.getToto()

toto copy constructor.

toto destructor.

toto bToto(aToto.getToto());

toto copy constructor.

toto destructor.

const toto &bToto = aToto.getToto();

toto copy constructor.

toto destructor.

bToto = aToto.getToto();

toto copy constructor.

toto assignment.

toto destructor.

So the penalty is at least one copy constructor need to be called. We no longer have the amazing gain when we have with ordinary functions that return a local object by value.

CONCLUSION THREE: Let member function return a reference to a member variable when the performance is really an issue, and call it with toto &aTotoRef = aToto.getTotoRef() to really take advantage of return by reference. Otherwise, return by value. Always take care of the variable holding the reference result, use it only during the life time of the object itself.

Hope this make things clearer, then we can investigate even more in the next part, yes, the story does not end here.

Like to know what you are thinking about this.

Vim Tabs

2010-11-15T15:53:00.001+01:00

If you are not used with the buffer concept as the buffers do not necessarily visible, and you also want to focus on the current file, you have the tabs in Vim just as you have in Editplus or Notepad++ or most of modern text editors. Here is my vim with two tabs each holding its own windows. Yes, it's important that each tab can hold multiple windows, isn't it cool or what!

Here is how you can work with tabs in Vim.

Create a new tab:

- vim -p file1 file2... : Open multiple files each in one tab.
- :tabnew [filename] : Crate a new tab, empty or possibly open a file at the same time.
- Ctrl-w T : If you have multiple windows opened in one tab, use this command to put the current window into a new tab.

Navigate between tabs:

- :tabs : list all opened tabs
- :tabn, :tabp: go to next or previous tab. Less convenient.
- gt : go to next tab. Better.

Vim Windows

2010-11-15T15:32:00.002+01:00

Vim is able to show your files in separated windows which is very handy in many situation. For example, if you are a programmer, very often you need to look at a .cpp file and its header .h at the same time. Or if you are simply writing some text and need to refer to certain part of the same file that can not fill in one screen because your text is quite long.

Then it's the time to think about multiple windows and it will helps a lot. Here is how vim looks like with multiple windows.

Basically, here I created three windows, left top, left bottom and the right one. Several interesting thing to mention here. First, as you can see, we are able to create vertically or horizontally separated windows. Then, we are able to crate multiple windows containing the same file. Finally, we have some important information for each window, the file name, the index of the buffer (the number before the file name), etc.

Here is how I use multiple windows.
To create new window:

- Ctrl-w s will split the current window into two containing the same file.
- :sp same as above.
- :sp filename will create a new window with the file filename.
- Ctrl-w v Split the current window vertically.
- :vs same as above
- :vs filename Vertical split with file filename.

To move between windows: All commands here start with Ctrl-w.

- h,j,k,l: Navigate: same as move the cursor.
- x: Switch positions of two neighbor windows.
- p: Go to previous windows, particularly useful when browsing between .h and .c files.

Close windows:

- Ctrl-w c or :q

My Favorite Software on Windows

2010-11-14T22:49:00.000+01:00

I reinstalled my PC this weekend as you all know that Windows tend to slow down after some time.

I take this opportunity to make a collection of my favorite software on a Windows PC.

7-Zip
Adobe Reader
Google Chrome
Mozilla Firefox
Skype
PPTV
SPlayer
MKPlayer
Sogou Chinese Input Method
Thunder Download

...
To continue.

Problem with System.Windows.Forms.WebBrowser

2010-10-10T09:02:00.002+02:00

I used a lot System.Windows.Forms.WebBrowser in my LSSaver project to process the pages. Recently I got a feed back that LSSaver stops to load the blog titles and is blocked there. The problem seems to happen on a WinXp + IE6 platform.

After investigation, the problem comes from a null pointer exception, but why there is a null pointer? A step by step debug showed me that when using WebBrowser’s DOM to retrieve certain HTML element, the HtmlElement.NextSibling returns an invalid pointer even when there is no more sibling of the calling HtmlElement object. It seems that this is a known issue in the .NET framework:
http://connect.microsoft.com/VisualStudio/feedback/details/304466/htmlelement-nextsibling-returns-incorrect-value

Anyway, I won’t rely on the NextSibling is null or not, I get the number of children from the parent, then rely on this count when traversing all the children elements. The problem is fixed.

Overloading operator << for containers

2010-09-30T22:55:00.002+02:00

Today, I saw a line of code in one of our cpp files, it looks like this:
marshaller << obj_list;
what interesting is that obj_list is an instance of type std::vector, and one of my colleagues asked me if he can do similar things with an instance of type std::map<>.

The answer is "I don't know", because it depends on if the operator << is overloaded for the marshaller type for std::map<>.

The secret why "marshaller << obj_list;" works is that, the marshaller type has an overloaded operator << for std::vector. Something looks like this, assuming marshaller has type T:
T &operator << (T &t, const vector avector){...}

Here is an example with cout:
ostream &operator << (ostream &out, const vector avector)
{
    vector ::const_iterator itr = avector.begin();
    for (; itr != avector.end(); ++itr)
    {
        out << (*itr);
    }
}

int main(void)
{
    vector str_vector;
    for (int i = 0; i < 10; i++)
    {
        stringstream str_stream;
        str_stream << i;
        str_vector.push_back(str_stream.str());
    }
    cout << str_vector;
}
The output is:
0123456789

So for this works with std::map<>, we need to overload << for std::map<>.

Finally, it turned out that there is no such an overload, unfortunately. So we have to do it for each pare in the map.

Do It in a Programmer's Way

2010-09-19T22:28:00.001+02:00

DiPw, I'd like to pronounce it like "deepyou", is my preferred way of doing things, especially things related with my job as a programmer/developer.

Recently, I was assigned a job to migrate documents from the old system to the new one, and this is to be done for each of our customers. In order to secure the migration, I need to check many configurations on both systems, they need to be similarly configured so the migration is transparent for the customers, ideally. What complicates things is also we have test systems and production systems, and the migration need to be done first on test systems then on production systems. So as a result, I have a lot of things to check and compare. Even worse, the settings are managed by several GUI applications so I have to click many times to find one setting on the old system then, do it on a different GUI on the new system. That is not only boring but also fault prone.

A colleague of mine kindly told me that the content of the GUI applications are finally stored in the database and he also gave me some SQL to retrieve the values. That is a big help, however, I still have to manage two types of databases, Oracle and SqlLite.

Why I have to do it manually? It's time consuming and error prone. Why not write a program doing all of these jobs for me? With always DiPw in head, I decided to write a Python program doing these boring jobs and finally it took me one day. Voila, now with the program, I retrieve all need information on all systems for a given customer in 20 minutes and when needed, I can retrieve most up-to-date information whenever I want in 20 minutes, this is impossible without the program. And when it comes the time to migrate another customer, I just run the program for this customer.

Well, I admit that the job is not all about getting all the settings, but it is the most boring part, so let a program do it!

A Real-life Story about Bad Type Cast

2010-08-30T22:00:00.003+02:00

We have a problem today in our soft. That is, in short, we have 285 lines of text to display but only 231 lines are displayed. The investigation is not so easy because the text to be displayed is converted from structured message and the number of lines are calculated on the fly.

Basically, there is a segment in the message that specifies the maximum allowed number of lines, the sender of the message has set it to 999, assuming it the maximum possible lines in the message.

So if you are really a geek in programming C/C++, you may already know where is going wrong. Yes, an integer 999 when assigned to a unsigned char, the latter will have value 231. In more detail: binary presentation of decimal 999 is 1111100111, when assigned to unsigned char, we have only the lower 8 bits left: 11100111, it equals decimal value 231.

The problem is quite clear, but it has been hard to find it out because it hides itself deep in one of the libraries our soft uses.

Another interesting thing is that the library code uses atoi to convert the maximum allowed size in the message to an integer value, but with a parameter like this: "999blabla", that is the value in string followed by other alphabetic characters. atoi is designed to handle this correctly, take a look at the specification of atoi:

int atoi ( const char * str );
Convert string to integer
Parses the C string str interpreting its content as an integral number, which is returned as an int value.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus orminus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.