C++ - Finding all arrangement (a.k.a permutation) of object.

When you have a set of object, you may have to build all arrangement of those object.

Example, a vector num = {0,1,2}, you want the 3! permutations ( {0,1,2}, {0,2,1}, {1,0,2},{1,2,0},{2,0,1},{2,1,0} )

Hopefully the Standard Template Library (STL) come with some useful function for that, but their behavior really depend of the operator you provide with your objects.

If you take a look at next_permutation, it stands to "Rearranges the elements in the range [first,last) into the next lexicographically greater permutation." but that point rely to the "bool operator( const T& elt)" of the object (class/type) you use.

A quick example of the pitfall in which I fall today. Imagine a type point define like below:

struct pos_t {
int x; int y;
pos_t(){x = 0 ; y = 0;}
pos_t(int X, int Y){x=X; y=Y;}
pos_t(pos_t const & r) {x = r.x; y=r.y;}
pos_t& operator=(pos_t const & r) {x = r.x; y=r.y; return *this;}
bool operator < ( pos_t const & p) const
{
return (x + y) < ( p.x+p.y);
}
friend ostream& operator << (ostream &o, const pos_t& p)
{
return o << "(" << p.x << "," << p.y << ")";
}
};


Now using the following list of point,  (1,3) ,(2,2) , (3,0) ,(3,1), you expect to get 24 permutations. But you will not !!!! The reason is the operator < we define in our class/struct. Using that operator (1,3) is similar to (3,1) and that the reason why when using next_permutation we implicitly use the less-than operator and we fail.

To really get all permutation out-of next_permutation we need to define clear compare operator.


bool operator < ( pos_t const & p) const
{
  return (x < p.x) || ((x == p.x) && (y < p.y));
}


Now using our list of 4 points, we can call a simple loop to store and display all permutations. See below a piece of code extract of Coding Challenge call "Treasure Hunter" (a kind of A* algorithm can be use to solve it .... )


deque<vector<pos_t>> treasure_order;
std::sort(begin(treasurePos), end(treasurePos));
do {
  vector<pos_t> c;

  c.push_back(pos_t(0,0));
  copy(begin(treasurePos), end(treasurePos), back_inserter(c));
  c.push_back(pos_t(maze.size()-1, maze.size()-1));

  copy(begin(c), end(c), ostream_iterator<pos_t>(cout, " -> "));
  cout << endl;
  treasure_order.push_back(c);

} while ( std::next_permutation(begin(treasurePos),end(treasurePos)) );//*/
cout << "we stored " << treasure_order.size() << " path to get all the treasure (=nbTreasure! = " << fact((int)treasurePos.size()) << ")" << endl;


Using that simple 2D maze where * mark treasure position:

. . . .
. # . *
. # * .
* * # .

We now that based on the 4 treasure we have, we can visit those 4 position using 24 different order....
Remark, here all list start and end with the same point (top-left and bottom-right corner) because they are the starting and ending point of th "Treasure Hunt" !

(0,0) -> (1,3) -> (2,2) -> (3,0) -> (3,1) -> (3,3) ->
(0,0) -> (1,3) -> (2,2) -> (3,1) -> (3,0) -> (3,3) ->
(0,0) -> (1,3) -> (3,0) -> (2,2) -> (3,1) -> (3,3) ->
(0,0) -> (1,3) -> (3,0) -> (3,1) -> (2,2) -> (3,3) ->
(0,0) -> (1,3) -> (3,1) -> (2,2) -> (3,0) -> (3,3) ->
(0,0) -> (1,3) -> (3,1) -> (3,0) -> (2,2) -> (3,3) ->
(0,0) -> (2,2) -> (1,3) -> (3,0) -> (3,1) -> (3,3) ->
(0,0) -> (2,2) -> (1,3) -> (3,1) -> (3,0) -> (3,3) ->
(0,0) -> (2,2) -> (3,0) -> (1,3) -> (3,1) -> (3,3) ->
(0,0) -> (2,2) -> (3,0) -> (3,1) -> (1,3) -> (3,3) ->
(0,0) -> (2,2) -> (3,1) -> (1,3) -> (3,0) -> (3,3) ->
(0,0) -> (2,2) -> (3,1) -> (3,0) -> (1,3) -> (3,3) ->
(0,0) -> (3,0) -> (1,3) -> (2,2) -> (3,1) -> (3,3) ->
(0,0) -> (3,0) -> (1,3) -> (3,1) -> (2,2) -> (3,3) ->
(0,0) -> (3,0) -> (2,2) -> (1,3) -> (3,1) -> (3,3) ->
(0,0) -> (3,0) -> (2,2) -> (3,1) -> (1,3) -> (3,3) ->
(0,0) -> (3,0) -> (3,1) -> (1,3) -> (2,2) -> (3,3) ->
(0,0) -> (3,0) -> (3,1) -> (2,2) -> (1,3) -> (3,3) ->
(0,0) -> (3,1) -> (1,3) -> (2,2) -> (3,0) -> (3,3) ->
(0,0) -> (3,1) -> (1,3) -> (3,0) -> (2,2) -> (3,3) ->
(0,0) -> (3,1) -> (2,2) -> (1,3) -> (3,0) -> (3,3) ->
(0,0) -> (3,1) -> (2,2) -> (3,0) -> (1,3) -> (3,3) ->
(0,0) -> (3,1) -> (3,0) -> (1,3) -> (2,2) -> (3,3) ->
(0,0) -> (3,1) -> (3,0) -> (2,2) -> (1,3) -> (3,3) ->

C++ Command Line using standard input/output.

As programmer you may be familiar with a lot a program design to use input file and/or input stream using the standard input. It’s one of the powerful aspect of tools like grep, sed, etc… And if you want to implement such command-line tool by yourself you may meet one big issue.

Windows vs. Linux.

As often, we would write our code in a portable way and just create a simple while loop like

while(!feof(stdin)) 
  {
    size_t bytes = fread(bufferInput, 1, m_blocksize, stdin);

    // ....
  }

but here you are face to a piece of code dependent of the platform you target, let me explain.

• On Linux stdin and stdout are by default open using the binary mode.


• On the other side on Windows they will be open using the text mode.

because of that, the feof and all the fread, fgets function can have different output on the 2 systems. For example, on Windows, reading using the normal mode will convert \r\n (Windows newline) to the single character ASCII 10, instead of returning 2 bytes under Linux !

To avoid that pitfall, you can use 2 approach:

• freopen, portable and easy to put before using stdin


• or _setmode/setmode available under Windows and also Linux/GCC under certain condition.

freopen:

Basically, the best thing you should do is this:

freopen(NULL, "rb", stdin);

This will reopen stdin using the binary mode, so under Linux it will change nothing, and on Windows, 

it will avoid abnormal character interpretation (premature end-of-stream, etc…). But take care of the 

compiler you use because depending of the freopen spec you read the behavior when passing path 

equal to NULL may be different... see the 2 following description:

• The Open Group Base Specifications

• MSDN 

setmode:

That method is less portable and may require some addition to your GCC environment.

With VS for example, you can call _setmode (require fcntl.h and io.h)

  _setmode(_fileno(stdin), _O_BINARY);
  _setmode(_fileno(stdout), _O_BINARY);

But under linux, the setmode isn’t a standard lib function, it’s a libbsd function. So you have to include <bsd/unistd.h> and link with –lbsd.

Conclusion

If you have to write a multi-platform command line tool using stdin/stdout the most portable way to do it is the freopen solution!

Screen capture with ffmpeg.

ffmpeg is the perfect tool to transcode video, but you may don’t know that it can also be use to capture your PC’s screen and as I didn’t found a clear page explaining how to do that, I will try to do my own (and hope it will help someone ….)

Performing a screen capture is an usual task to report bug, recording a presentation you make (adding your voice and your webcam recoding over-the-top of your slide), etc…

There is several tools you can found under the web (GOOGLE IT), But you have to setup a new application, you don’t even control the Audio/Video filter used to capture and encode the video. If you want to keep control, you would like my command line based solution.

Note that the solution I describe here is for Windows, but it could also work under Linux  with some adaptation, look at –x11grab)

First, check if you have Audio & Video Capture filter:

ffmpeg -list_devices true -f dshow -i dummy

it should return something like:

dshow @ 00000000002fb2e0] DirectShow video devices

dshow @ 00000000002fb2e0]  "…."

dshow @ 00000000002fb2e0] DirectShow audio devices

dshow @ 00000000002fb2e0]  "…."

If you don’t find a filter name between the quotes, you have to setup filters and /or enable the audio output recoding capabilities.

• Setup Video Capture filter for x86 and x64 (it depend of your ffmpeg version).

I recommend the Unreal Screen Capture DirectShow source filter , download the version you need and perform the installation.

• Setup the Audio Capture. That part depends of your device, but for example on my PC, I have a “Realtek High Definition Audio” Device. I clicked on the speakers icon in the system bar and select “recording device”, I had to enable the “stereoMix” device and boost its capture level.

After check again if ffmpeg detect your device/filter, it should be something like:

dshow @ 00000000002fb2e0] DirectShow video devices

dshow @ 00000000002fb2e0]  "UScreenCapture"

dshow @ 00000000002fb2e0] DirectShow audio devices

dshow @ 00000000002fb2e0]  "Stereo Mix (Realtek High Defini"

Run your 1st capture

ffmpeg -f dshow -i video="UScreenCapture":audio=Stereo Mix (Realtek High Defini" cap.mp4

Just hit [q] to stop the recoding and play cap.mp4 (ffplay cap.mp4).

By default, it capture the whole screen, and the whole means ALL your screen i.e. for my dual-screen system I recorded a 3840x1200 video.

Select your ROI(Region Of Interest)

We will use the -vf crop=width:height:xtopleft:ytopleft syntax of ffmpeg to select the part of the big picture we really want to record.

For the example, we will capture the output of a video player, but how to get the windows or video area coordinates ? In fact it’s really simple, I use the small application called “Point Position”.

 

Using that tool you can get the top-left and bottom-right coordinate of any window you want to capture, and by the way compute the width and height of the area!

Now capture:

fmpeg -f dshow -r 14.985 -i video="UScreenCapture":audio="Stereo Mix (Realtek High Defini" -vf crop=1278:541:98:198,scale=480:270 -c:v libx264 -profile:v baseline -level:v 3.0 -b:v 350k -r 14.985 -pix_fmt yuv420p cap.mp4

here I added several option to set a capture frame-rate, rescale the cropped area and encode the video using explicit parameters (encoder, bit-rate, etc….)

Conclusion:

No need of additional tool to perform a task that our video’s Swiss knife can do !

Windows PATH Environment Variable too long!

 

Yesterday, I unzipped several useful command line tools each in their respective folder and tried to add all those path in my PATH to easily access all tools from any command prompt, BUT ….

When I tried to copy/paste all the new path through the Environment Variables Editor, you can open from :

“Control Panel\System and Security\System”, click on “Advanced system settings”, select “Advanced” Tab and now click on the “Environment Variables” button…..

  a shortcut will be welcome !

The Editor here has a 2048 characters limit. And I already have a too long path !!!!

An easy workaround from here was to use the “User” PATH as I’m the only user of my workstation it was fine.

But If you really need to update the PATH for all users you can use the registry editor (regedit.exe):

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Environment\Path

The Editor (rigth click on the key and select “Modiffy”) will allow you to use more characters.

But if one day your change are finally truncate, It could mean you hit the maximum of 32767 characters (CONSIDERING ALL YOUR VARIABLES ….)

Coding Style: Detect tabulation and use a given number of space instead.

 

If you need to respect a Coding Style, and that your coding style require tab to be replaced by a given number of space (2 in my case), you may have to check before each commit that the files you have in your working copy doesn’t contain any tab.

To realize that preliminary step, you can use grep.

Run: grep -n -P "\t" *.h && grep -n -P "\t" *.cpp

It will get you the file name and the line number where grep found tabulation.

Now if we want to automatically apply the Coding Styles rules and replace tabs by 2 spaces we can also use a command line.

find ./ -type f -name "*.h" -exec sed -i 's/\t/  /g' {} \;

and

find ./ -type f -name "*.cpp" -exec sed -i 's/\t/  /g' {} \;

The number of space between \t/ and /g has to be the number of space for tab !

Note that grep, find and sed are Linux command, but Windows developer can also use those command if they setup Cygwin.

C++: Find max top 5 number from 3 array.

Yesterday, I read that blog post where C# developer demonstrate how powerful is LINQ to solve a simple problem.
We have 3 array of Integer  and we want to find the 5 maximum number from those 3 Array.  With LINQ, 7 cascaded operation are enough to do that in 3 line of code.
And I’m wondering how many line I would use in C++ to do the same !
Here is my 1st Draft made in 5min. I use only 5 line of code.

//Headers we need
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int Array1 [] = { 9, 65, 87, 89, 888 };
int Array2 [] = { 1, 13, 33, 49, 921 };
int Array3 [] = { 22, 44, 66, 88, 110 };

vector<int> A1(begin(Array1), end(Array1)); 
A1.insert(end(A1), begin(Array2), end(Array2)); 
A1.insert(end(A1), begin(Array3), end(Array3));
sort(begin(A1), end(A1));
vector<int> max(end(A1)-5, end(A1));

//to output the result
copy(begin(max), end(max), ostream_iterator<int>(cout, " "));

But I would see on Stack Overflow if someone has a better solution.

[UPDATE] : you can found interesting to read answer to my StackOverFlow question.
 C++ and C++11 solution are proposed, taking into account the complexity introduce by the sorting. 

Let your hand on the keyboard.

 

I don’t know all the “magic” keyboard shortcut but I always try to learn new shortcut, just because typing and switching between keyboard and mouse is just losing time.

Today I was try to get a shortcut for word/outlook word spell suggestion and find that it’s easy. If the spell checker is enable and that something you just typed appears with the red-underline (saying something is wrong), get back on that word and use MAJ+F10 to open the suggestion list.

Now I can correct a lot of typo mistake on-the-fly without living my keyboard !