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.

  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 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}

(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); 

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

GTEST_API_ int main(int argc, char **argv) {
  std::cout << "Running main() from\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, is a file that has main function and is a file that has test code.

g++ -I{GTEST_DIR}/include 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.

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.

- - - - -

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.

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

Sample Input:
N = 6

Sample Output:

My Solution:

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.


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?

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:

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.


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. 

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:

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

Aug 19, 2011

An example of the breadth-first search

You can use the breadth-first search to process every state like the depth-first search.

When you want to search the shortest path for search space like a maze, the breadth-first search is a good solution for you because you have to search the same state so many times with the depth first-search.

The breadth-first search has a weak point. It needs memory that is proportional to a number of state.

This is an example of the breadth-first search:

- Description
You have a maze which size is M * N. The maze consists of path and wall.
You can move 4 direction (up, down, right and left) in one turn.
Solve the shortest path from the start to the goal.
- Constraint
N, M >= 100
- Sample Input
10 10
- Sample Output
My solution is like this. You can find it on my github repository.
using namespace std;

const int INF = 1000000;
const int MAX_N = 100;
const int MAX_M = 100;

typedef pair P;
char maze[MAX_N][MAX_M+1];  // maze
int n, m;   // size of maze
int sx, sy; // start position
int gx, gy; // goal position

//shortest path for each point
int d[MAX_N][MAX_M];

//vector for for moving direction
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

//solve the shortest path from (sx, sy) to (gx, gy)
int bfs() {

q; //initialize every point with INF before search for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { d[i][j] = INF; } } q.push(P(sx,sy)); d[sx][sy] = 0; while(q.size()) { P tmp = q.front(); q.pop(); //if you find goal then you finish search if ((tmp.first == gx)&&(tmp.second == gy)){ break; } for(int i = 0; i < 4; i++) { int nx = tmp.first + dx[i]; int ny = tmp.second + dy[i]; if ((0 <= nx) && (nx < n) && (0 <= ny) && (ny < m) && (maze[nx][ny] != '#') && (d[nx][ny] == INF)) { // if d[nx][ny] == INF then it is a position that // you have already visited. q.push(P(nx,ny)); d[nx][ny] = d[tmp.first][tmp.second] + 1; } } } return d[gx][gy]; } void solve() { int res = bfs(); cout << res << endl; } int main(int argc, char* argv[]) { if (argc != 2) { cout << "./a.out "; return 1; } ifstream ifs(argv[1]); if (!ifs) { cout << "can't open file:" << argv[1] << endl; return 1; } string buf; getline(ifs, buf); sscanf(buf.c_str(), "%d %d", &n, &m); for(int i = 0; i < n; i++) { getline(ifs, buf); for (int j = 0; j < m; j++) { maze[i][j] = buf[j]; if (maze[i][j] == 'S') { sx = i; sy = j; } if (maze[i][j] == 'G') { gx = i; gy = j; } } } solve(); return 0; }

Aug 18, 2011

Lake Counting(POJ No.2386)

This is a good example of Depth-First Search.


Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

* Line 1: The number of ponds in Farmer John's field.
Sample Input

10 12
Sample Output


You can find my solution on github:

Aug 5, 2011

g++ compile error: declaration of "XXX" shadows a parameter

I found below error when I compiling C++ program with g++:
declaration of "XXX" shadows a parameter
Acording to the forum in, which titile is "declaration of "blah" shadows a parameter??", you see this when you make derived class and don't initialize it with a constructor initialization list.

Jul 13, 2011

Android: “Path for project must have only one segment”

If you find this message when you are launching the Android application, the Eclipse cannot find the path to the project.
Path for project must have only one segment.
You have to specify the Project name for the Launch configuration.

Refference:, Android: “Path for project must have only one segment”

Jul 4, 2011

repo init throws import readline error

While I was attempting to use the repo init command for downloading Android source code, it threw an error about importing the readline module like this:
Traceback (most recent call last):
File "/Users/xxx/bin/repo", line 91, in <module> import readline
ImportError: No module named readline
I found the same problem on Issue 1032 of Android open source project.

This happend because the python readline module was not included as part of OSX. To fix this problem, you have to install the python readline module.
sudo port install py25-readline
If you are using Python that is contained in OSX, you have to change it to MacPort's Python.
sudo port select python python25
I am using Mac OS X as a UNIX with better UI. I like Mac OS BUT Mac OS X has a lot of problem for programming environment as I mentioned before ><

Jul 3, 2011

compile problem because of an expired debug certificate

When I was compiling my Android app, I couldn't do it. I found this message in Problem view.
Error generating final archive: Debug certificate expired on XXX
I found same problem in android web site. According to the site, the Android build tools local debug key but it is already expired. To fix this problem, I had to regenerate my debug key.

Here is the step.
  1. delete the debug keystore/key already generated by the Android build tools. Specifically, delete the debug.keystore file. On Linux/Mac OSX, the file is stored in~/.android. On Windows XP, the file is stored in C:\Documents and Settings\<user>\.android. On Windows Vista, the file is stored in C:\Users\<user>\.android
  2. generate new debug keysore file with this command: keytool -genkey -v -keystore <PATH_TO_FILE>/debug.keystore -alias androiddebugkey -keyalg RSA -validity 10000 -dname "CN=Android Debug,O=Android,C=US"
Note: <PATH_TO_FILE> is a path to the debug keystore file. Please set appropriate path for your environment.