Sep 21, 2011

How to compile googletest with gcc and CMake on Mac OS X SnowLeopard

I often found the way with Visual Studio C++ or XCode on web but I don't use them on my laptop. So I researched the way without IDE.

My settings
  • Mac OS X 10.6.8(Snow Leopard)
  •  gcc 4.5.4
  • cmake 2.8.5
According to googletest's README, you need more than 2.6.4 of cmake but the version of gcc is not clear.

Process
  1. Get source code of google test from svn repository
  2. Build googletest with cmake
  3. Create source file that has main function
  4. Create test code
  5. Build test code with g++
  6. Run the test
(1) Get source code of google test from svn repository

Place the source where you want.
svn checkout http://googletest.googlecode.com/svn/trunk/ gtest-svn

(2) Build googletest with cmake
Make a directory that cmake runs, which is good for anywhere.  {GTEST_DIR} is where theres is googletest. It is success when you get libgtest.a and libgtest_main.a after build.

mkdir mybuild
cd mybuild
cmake ${GTEST_DIR}
make

(3) Create source file that has main function

Create source file that has main function. You can find sample as below link.

You have to call below functions in main function.
  • testing::InitGoogleTest(&argc, argv); 
  • RUN_ALL_TESTS();

#include <iostream>
#include "gtest/gtest.h"

GTEST_API_ int main(int argc, char **argv) {
  std::cout << "Running main() from testmain.cc\n";

  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}
(4) Craeate test code
#include "gtest/gtest.h"

TEST(firstTest, abs)
{
  EXPECT_EQ(1, abs( -1 ));
  EXPECT_EQ(1, abs( 1 ));
}

(5) Build test code with g++
You have to add the directory where there is googletest's header file into include path. You also have to build test code with static library of google test that you made at (2).

As below, testmain.cc is a file that has main function and mytest.cc is a file that has test code.


g++ -I{GTEST_DIR}/include testmain.cc mytest.cc libgtest.a libgtest_main.a -o mytes

(6) Run the test
Run the test. It is success if you see the test result as below.




Sep 20, 2011

auto_ptr and shared_ptr for resource management


Resource management is common troublesome issue for C/C++ programmer. If you don't free a resource that you acquire, you will run out of resource some day.

Scott Meyers, the author of Effective C++, recommended RAII(Resource Acquisition Is Initialization) for resource management. There are several ways to do it but simple way is to use auto_ptr and shared_ptr if your concern is about memory.

Give you a couple of example.

In this example, an error occurs before you delete an object that you acquirer, so resource leak happens. So you have to care about somebody except you because he can write a code that resource leak happens.

Investment* createInvestment() {
  return new Investment;
}

// an example of memory leak                                                                              
void f1(){
  std::cout << "f1" << std::endl;
  try {
    Investment *pInv = createInvestment();

    //If some one write code that can throws error,                                                       
    //destructor of Investment may not be called.                                                         
    throw 1;

    delete pInv;
  } catch(...) {
    std::cout << "catch" << std::endl;
  }
}

In this example, I used auto_ptr for resource management. Now you don't need to care about resource. When the control flow leaves the scope, auto_ptr frees a pointer.

//an example of auto_ptr                                                                                  
void f2(){
  std::cout << "f2" << std::endl;

  try {
    //If you pass a pointer to auto_ptr,                                                                  
    //auto_ptr frees it when the control flow leaves the scope.                                           
    std::auto_ptr pInv(createInvestment());
    throw 1;
  } catch (...) {
    std::cout << "catch" << std::endl;
  }
}

auto_ptr has several limitation. For example several auto_ptr cannot contain the same pointer. So you cannot put auto_ptr into STL container because STL container assume that every object can copy.

void f3(){
  std::cout << "f3" << std::endl;
  //several auto_ptr cannot contain the same pointer.                                                     
  //If you copy auto_ptr, then the source becomes null pointer and                                        
  //the destination can contain the pointer.                                                              
  Investment* pInv1 = createInvestment();
  std::auto_ptr pInv2(pInv1);
  std::auto_ptr pInv3(pInv2);
}

If you need to contain the same pointer with several auto_ptr, you should use shared_ptr in Boost Libraries. But shared_ptr has limitation. You cannot use it for an array.

void f4(){
  //several shared_ptr objects can have the same pointer.                                                 
  boost::shared_ptr pInv1(createInvestment());
  boost::shared_ptr pInv2(pInv1);

  //If every shared_ptr objects are freed, then the pointer                                               
  //that they have also freed.                                                                            
}


Here is a sample code for this entry.
https://github.com/yohei1126/effectivecpp/blob/master/chap3/term13/Investment.cpp

There are other ways for resource management. I will write it some day :)

Sep 17, 2011

One liner is a good way to do some smaller jobs in your life


Perl one liner is a good way to do some smaller jobs in daily life like renaming a file name or showing a file list.

You may think that you can do it by writing a script or a program. But one of the advantages of one liner is that you can combine it with other command like UNIX pipe and filter.

Here is an example of Perl one liner. You can pick up source files and header files for C/C++ language. It is not so difficult.

perl -MFile::Find -e 'find(sub {print "$File::Find::name\n" if $File::Find::name =~ /\.(c|cpp|h)$/ }, ".")'

You may say that you want to write other language. It is OK. You can use any LL but you may have some limitation in older OS. For example, I am using Open VMS, which is OS by HP, and I can use only Perl in LL. It is good to learn basic of other language for you.

I hope you will write some one liner in your work :)

Sep 5, 2011

Best Cow Line (POJ 3617)

You actually can solve the problem No. 3617 in POJ, Peking University Judge Online, with the greedy algorithm.

The author of "Programming contest challenge book" says that the greedy algorithm is effective for a problem that deal with dictionally order.

Here is more simple description of POJ 3617.

- - - - -


Description:
You have a string S that length is N and make a string T that length is N. At the beginning, length of S is zero. You can do either operation from below:

 - delete the first character of S and add it into the end of T
 - delete the last character of S and add it into the end of T

Make T as small as in dictionary order.

Constraint:
1 <= N <= 2000
string s can contain small alphabet.

Sample Input:
N = 6
S = "ABCDBCB"

Sample Output:
ABCBCD

My Solution:
https://github.com/yohei1126/pccb/blob/master/beginner/search/GreedyAlgorithm/BestCowLine/BestCowLine.cpp

Interval Scheduling Problem or a.k.a Earliest Deadline First Scheduling

Here is another example of the greedy algorithm, "Interval Scheduling Problem". You can find detailed explanation on Wikipedia

If I explain how this algorithm can work in an instinctive way, I can say like this:
  • The earlier a job ends, the more jobs you can choose.
This is not a proof. If you want to know how to proof, please see  "Earliest deadline first scheduling" on Wikipedia. Earliest deadline first scheduling is is a dynamic scheduling algorithm used in real-time operating systems.

-----

Problem:
You have 'N' jobs. Each job starts at time 'si' and ends at time 'ti'. You have to choose join or not for each job. If you join, you must jon from the beginning to the end of the job. You cannot join more than two jobs at one time. An overlapping of start time and end time is not permitted. You want to join as much as possible. Hou many jobs can you join?

Constraint:
1 <= N <= 100000
1 <= si < ti <= 10^9

Sample input:
N = 5
s = {1, 2, 4, 6, 8}
t = {3, 5, 7, 9, 10}

Sample output:
3

My Solution:

Coins Problem : An example of greedy algorithm

The greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.

Please see details of the greedy algorithm on wikipedia.

Coins problem in "Problem contest challenge book" is an example of a greedy algorithm. The point is that you use the largest amount of coin preferentially.

---

Problem:
You have coins as bellow.
  • A number of 1     yen coin is C1
  • A number of 5     yen coin is C5
  • A number of 10   yen coin is C10
  • A number of 50   yen coin is C50
  • A number of 100 yen coin is C100
  • A number of 500 yen coins is C500
You want to pay A yen with the minimum number of coins. How many coins do you have to pay? There is at least one solution for this. 

Constraint
0 <= C1, C5, C10, C50, C100, C500 <= 10^9
0 <= A <= 10^9 

Sample input:
A = 620
c500 = 2, c100 = 0, c50 = 3, c10 = 1, c5 = 2, c1 = 3 

Sample output:
6

My solution:
You can find my solution for this problem on my github.