Category: C++

Binary Search For Duplicate Data

GOAL

The goal of this article it to describe an algorithm to find first target item or last target item from sorted list with duplication using binary search and how to implement them in C++.

What is binary search?

Binary search is one of the search algorithms, that finds position or judges existence of an target value on sorted array.

Binary search compares the current value defined as a half of target range of the array to the target value. Binary search compares the middle element of current target range in the array to the target value. The current target range is narrowed according to the result of comparison as below.

What if there are same values in the array?

If there are same values, the found element can be first one, last one or other. How can we change this algorithm to search for the smallest or largest element?

Find first index

If the value currently focused is equal to the target value, the current value is contained to the next range as a max value. End the process when min index equal to max index, then check if the min value is equal to the target value.

(more…)

[Tips]How to detect “Enter Key” pressed in C/C++?

GOAL

To detect enter key pressed in C/C++ program.

Environment

Windows 10
Visual Studio 2017

Method

Method 1. get char

If you just detect enter key pressed at any time, use getchar() or cin.get() function.

C language

#include <stdio.h>
#include <windows.h> // for Sleep function

int main(void)
{
	while(true){
		if (getchar() == '\n') {
			printf("Enter key is pressed");
			Sleep(1000); //wait for check printed message.
			break;
		}
	}
	return 0;
}

C++

#include <iostream>
using namespace std;

int main() {
	while (1) {
		if (cin.get() == '\n') {
			cout << "Enter key is pressed" << endl;
			break;
		}
	}
	return 0;
}

Method 2. get line

If you’d like to detect that only enter key is pressed without input another key before enter, use scanf() , fgets() or gets() in C language or getline() in C++

C language

#include <stdio.h>
#include <string.h>
#include <windows.h> // for Sleep function

int main(void)
{
	while (1) {
		//if (getchar() == '\n') {
		char str[32];
		gets(str);
		if(strcmp(str,"")==0){
			printf("Enter key is pressed");
			Sleep(1000); //wait for check printed message.
			break;
		}
	}
	return 0;
}

C++

#include <iostream>
using namespace std;

int main() {
	string str;
	while (1) {
		getline(cin, str);
		if (str == "") {
			cout << "Enter key is pressed" << endl;
			break;
		}
	}
	return 0;
}

Method 3. GetKeyState

GetKeyState() is only provided on Windows. You can get the current “state” of the key. It returns 0 when the key is not pressed.

The key code is here.

#include <iostream>
#include <windows.h> // for GetKeyState function
using namespace std;

int main() {
	cout << "some process here" << endl;
	while (1) {
		if (GetKeyState(VK_RETURN) < 0) {
			cout << "Enter Key is Pressing" << endl;
		}
		else if (GetKeyState(VK_ESCAPE) < 0) {
			break;
		}
	}
	return 0;
}

What is pch.h

When I create a new C/C++ project in VisualStudio, an header file named “pch.h” is generated.

GOAL

To understand what is pch.h and how to use it.

Environment

Windows 10
VisualStudio 2017

What is pch.h

pch.h is a precompiled header that is an header file where any stable header files such as Standard Library headers are included. You can add header files you’d like to pre compile. The precompiled header is compiled only when it, or any files it includes, are modified.

Reference: Precompiled Header Files in Microsoft documentation

The following is initial pch.h

#ifndef PCH_H
#define PCH_H

// TODO: add headers that you want to pre-compile here
#endif //PCH_H

The advantage of pch.h

Using pch.h reduce compilation time, especially when applied to large header files, header files that include many other header files.

How to use pch.h

Add header files you’d like to use in the pch.h as below.

#ifndef PCH_H
#define PCH_H

#include <stdio.h>
#include <math.h>
#include "myheader.h"

#endif //PCH_H

How to adapt your AE plugin for 8, 16, 32bit color

Hello. In previous article “First After Effects Effects-Plug-In Development“, I implemented a simple After Effects plugin. This article is supplement to it.

What is color (bit) depth

Colors are represented as numbers in computers. In RGB color system, color is represented (R, G, B) such as (100, 120, 144) or (0.5, 0.2, 0.7). In gray scale mode, color is represented as one value such as a integer form 0 to 255 or float from 0 to 1.0.

Color bit depth is resolution of each values. When the color is 8 bpc(bit per channel) each channel, R, G, B and A is expressed using 8bit. When the color is 8bpp(bit per pixel), each pixel color is expressed using 8bit, 3bit for R and G and 2 bit for B.

The following is the image of the difference between 4bit color (4bpc) and 8bit color (8bpc).

Difference 4bpc and 8bpc

Color bit depth in After Effects

In After Effects, you can use 8-bpc, 16-bpc, or 32-bpc color. (check “Color depth and high dynamic range color” for details)

8bit: 0-255 for each channel (256 gradation)
16bit: 0-32767 for each channel (32,768 gradation)
32bit: The range represented by a 32-bit float for each channel (4,294,967,296 gradation)

The color is represented by integer in 8bpc and 16bpc color. Float value is clamped into [0.0 – 1.0] and convert to [0-255] or [0-32767] in 8bpc and 16bpc.

Color bit depth in AE plug-in development

When you develop After Effects plug-in, you should consider all color 8/16/32bit.

8bit

8ARGB color is stored using PF_Pixel8

//this is from AE_Effect.h

// Basic pixel defn's
typedef struct {
	A_u_char	alpha, red, green, blue;
} PF_Pixel;

typedef PF_Pixel		PF_Pixel8;
typedef PF_Pixel		PF_UnionablePixel;

16bit

//this is from AE_Effect.h

typedef struct {
	#ifdef PF_PIXEL16_RENAME_COMPONENTS
		// this style is useful for debugging code converted from 8 bit
		A_u_short		alphaSu, redSu, greenSu, blueSu;
	#else
		A_u_short		alpha, red, green, blue;
	#endif
} PF_Pixel16;

32bit

32bit color is supported in CS6 (11.0) and more.

//this is from AE_Effect.h

typedef A_FpShort			PF_FpShort;
typedef A_FpLong			PF_FpLong;
typedef struct {
	PF_FpShort				alpha, red, green, blue;
} PF_PixelFloat, PF_Pixel32;

And as you can see below, each channel is char type (8bit) in PF_Pixel or PF_Pixel8, unsigned short type (16bit) in PF_Pixel16 and float type (32bit) in PF_PixelFloat or PF_Pixel32.

//picked up from A.h

typedef char			A_char;
typedef float			A_FpShort;
typedef unsigned short	A_u_short;

Tips of color depth handling in AE plug-in development

Global setup

To make your effect handle 16-bpc color, set out_data->out_flags PF_OutFlag_DEEP_COLOR_AWARE.

And to make your effect supports 32-bpc colors, set out_data->out_flags2 PF_OutFlag2_FLOAT_COLOR_AWARE and PF_OutFlag2_SUPPORTS_SMART_RENDER.

Set pixel format

Before CS6, PF_CHECKOUT_PARAM() only returned 8-bit ARGB buffers, regardless of the pixel format currently being used for rendering. Starting in CS6, an effect can opt in to get frames in the same format as the render request, whether it is 32-bit float, YUV, etc.

from  After Effects SDK Guide

Render

In Render function, the iterate function scan input flame and calculate output frame as pixel to pixel operation, pixel function. The iterate functions is selected separately depending on the PrPixelFormat of destination pixels. Check After Effects SDK Guide “Progress During Iteration” for details.

Smart Render

In Smart Render function, pixel functions is selected separately depending on the PrPixelFormat like Render function.

If you want to know about the difference between Render function and SmartRender function, check the article “The difference of Render and Smart Render in After Effects”. (sorry, it will come soon)

The conditional branch by switch sentence is following.

 switch (format) {
    case PF_PixelFormat_ARGB128:
        iterateFloatSuite ->iterate(
            in_data, 0, output_worldP->height, input_worldP, 
            NULL, (void*)infoP, FilterImage32, output_worldP);
        break;
    case PF_PixelFormat_ARGB64:
        iterate16Suite ->iterate(
            in_data, 0, output_worldP->height, input_worldP,
            NULL, (void*)infoP, FilterImage16, output_worldP);
        break;
    case PF_PixelFormat_ARGB32:
        iterate8Suite ->iterate(
            in_data, 0, output_worldP->height, input_worldP,
            NULL, (void*)infoP, FilterImage8, output_worldP);
        break;
     default:
         err = PF_Err_BAD_CALLBACK_PARAM;
         break;
}

Pixel functions

Prepare each functions for 8/16/32 bit separately. The follow example is in SDK_Noise.cpp.

The differences are following.

*inP and *outP

// 8bit
static PF_Err FilterImage8 (
    void *refcon, A_long xL, A_long yL, 
    PF_Pixel8 *inP, PF_Pixel8 *outP)

// 16bit
static PF_Err FilterImage16 (
    void *refcon, A_long xL, A_long yL, 
    PF_Pixel16 *inP, PF_Pixel16 *outP)

// 32bit
static PF_Err FilterImage32 (
    void *refcon, A_long xL, A_long yL, 
    PF_PixelFloat *inP, PF_PixelFloat *outP)

tempF

// 8bit   clamp in range [0, PF_MAX_CHAN8]
tempF = rand() % PF_MAX_CHAN8;
tempF *= (niP->valF / SLIDER_MAX);

// 16bit   clamp in range [0, PF_MAX_CHAN16]
tempF = rand() % PF_MAX_CHAN16;
tempF *= (niP->valF / SLIDER_MAX);

// 32bit    clamp in range [0, 1 = PF_MAX_CHAN16/PF_MAX_CHAN16]
tempF = (PF_FpShort)(rand() % PF_MAX_CHAN16);
tempF *= (PF_FpShort)(niP->valF / (SLIDER_MAX * PF_MAX_CHAN16));

channels of outP

// 8bit  clamp in the range [0, PF_MAX_CHAN8] 
outP->red = MIN(PF_MAX_CHAN8, inP->red + (A_u_char) tempF);

// 16bit  clamp in the range[0, PF_MAX_CHAN16] 
outP->red = MIN(PF_MAX_CHAN16, inP->red + (A_u_short) tempF);

// 32bit
outP->red = (inP->red + tempF);

Understanding typedef in C/C++

GOAL

To understand “typedef” in C++

What is typedef?

typedef is a reserved keyword that gives a new name to existing data type used in C/C++ programming. That new name like this is called alias or synonym.

The following is an example of typedef. typedef is used just for user convenience.

typedef int USER_Id;
USER_Id john_id; //this is same as int john_id
john_id = 24;

When to use typedef

These are some of many use cases of type def.

To clarify the meaning of variable

For example, when you handle data of date many times, you may want to identify month and day.

typedef  int Month;  //define alias "Month"
typedef int Day;  // define alias "Day"

This is an example of use.

#include <iostream>
using namespace std;

typedef  int Month;
typedef int Day;

void print_birthday(Month m,  Day d){
    printf("your birthday is %d/%d\n",m, d);
}
Day last_day(Month m){
    if(m == 4 && m==6 && m==9 && m==11)
        return 30;
    if(m == 2)
        return 28; //ignore leap year 
    else
        return 31;
}
int main(void){
    print_birthday(12,24);  /* output is "your birthday is 12/24" */
    cout << last_day(10);  /* output is "31"*/
}

To omit long type

typedef long long unsigned int LLUInt;

int main(void){
    LLUInt test1 = 10;
    LLUInt test2 = 20;
    cout << test1+test2 << endl;  /* output is "30"*/
}

To omit the “struct” keyword in C language

When you declare a defined structure, you should use the “struct” keyword in C language.

struct person{
    char *nickname;
    int age;
};
//declare
struct person john;

If you use typedef and rename the structure, you don’t need the “struct” keyword.

typedef struct person{
    char *nickname;
    int age;
} person_type;

//declare
person_type john;

The definition of the structure in above source code is the same as this.

struct person{
    char *nickname;
    int age;
};
typedef person person_type;

self-referencing structure

The following is the Node structure used in linked list.

struct Node {
    int data;
    struct Node *next;
}

This self-referencing structure is also defined by using typedef.

typedef struct _node{
int data;
struct _node * next;
} Node;
Node* top;

To create a pointer type

Usually you should use * to declare a pointer.

int *p1, *p2, *p3, *p4;

You can define pointer type by using typedef.

typedef int* IntP
IntP p1, p2, p3, p4;

string

#include <iostream>
using namespace std;

typedef char* my_str;

int main(void){
    my_str name = "Nako";
    printf("My name is %s\n", name); /* output is "My name is Nako"*/
}

Variations

Structure and its pointer

typedef struct _node{
    int data;
    struct _node * next;
} Node, *pNode;

Function

In this example, variable f can store a pointer to function int FUNC(int n).

#include <iostream>
using namespace std;

int next_int(int x) { return x + 1; } //example of int FUNC(int n)
int half_int(int x) { return x/2;}  //example of int FUNC(int n)

int main(void){
    int (*f1)(int n);
    int (*f2)(int n);
    f1 = next_int;
    f2 = half_int;
    cout << f1(4) << " " << f2(4) << endl;  /*output is "5 2"*/
}

Typedef can add the name to the pointer of function.

typedef int (*FUNCT)(int n);

The above example of function pointer can be changed as below.

#include <iostream>
using namespace std;

int next_int(int x) { return x + 1; }
int half_int(int x) { return x/2;}

typedef int (*FUNCT)(int n);

int main(void){
    FUNCT f1;
    FUNCT f2;
    f1 = next_int;
    f2 = half_int;
    cout << f1(4) << " " << f2(4) << endl;    /*output is "5 2"*/
}

list

typedef can define list as type.

#include <iostream>
using namespace std;

typedef int Members[5];

int main(void){
    Members team_a = {13, 25, 66, 89, 100};
    Members team_b = {21, 22, 50, 78, 81};
    for(int i=0; i<5; i++){
        cout << team_a[i] << " ";  /*output is "13 25 66 89 100 "*/
    }
    cout << endl;
    for(int i=0; i<5; i++){
        cout << team_b[i] << " ";  /*output is "21 22 50 78 81 "*/
    }
}

using in C++

The “using” declaration introduces a name into the declarative region in C++. The “using” declaration is usually used for making a declaration of namespace such as “using namespace std;”, but it can be also used for alias.

using Month = int;
using Day = int;
using FUNCT = int (*)(int);

I’ll write about the difference between typedef and using and its features someday. Thank you!

[C++]How to separate header file and source file.

GOAL

To understand the rules and general method to separate header files and source files in C++.

What is header files?

Header files are files where class definitions and function declarations are summarized. You can use the class written in the header file by writig #include or #include “myheader.h” in source file as follows.

#include <iostream>
#include "myClass.h"
using namespace std;
int main(){
   myClass instance1;
   cout << instance1.getName() << endl;
}

Why are header files necessary?

In C++, variables, classes, functions and so on should be declared before used, like sayHello() or myClass in the sample code below.

//mysource.cpp

#include <string>
#include <iostream>
using namespace std;
void sayHello(){
    cout << "Hello!" << endl;
}
class myClass {
    private:
        string name;
    public:
        myClass();
        myClass(string name_str);
        string getName();
};
myClass::myClass(){
    name = "nothing";
}
myClass::myClass(string name_str){
    name = name_str;
}
string myClass::getName(){
    return name;
}

int main() {
    sayHello();
    myClass cat1("Joe");
    cout << cat1.getName() << endl;
}
//console result
Hello!
Joe

If this declaration is missed or called by wrong name, an error will occur. And when you use the same function or class in multiple files, you have to declare it many times in each file. It is difficult to understand the structured of code if the names of functions that have same function are different. And it is also difficult to make corrections collectively. For this reasons, the declaration part are split into the header files separately from the main source files.

//myClass.h
#include <string>
#include <iostream>

class myClass {
    private:
        std::string name;
    public:
        myClass();
        myClass(std::string name_str);
        std::string getName();
};
myClass::myClass(){
    name = "nothing";
}
myClass::myClass(std::string name_str){
    name = name_str;
}
std::string myClass::getName(){
    return name;
}
//mysource.cpp
#include <iostream>
#include "myClass.h"
using namespace std;
int main() {
    myClass cat1("Joe");
    cout << cat1.getName() << endl;
}
//console result
Joe

About #include

Header files can be loaded with #include or #include “filename”. The difference between the two styles is that when #include is used, the system searches the directory of the library specified by the compiler preferentially, but on the other hand, when #include “filename” is used, the system searches the current directory.

See below for C and C++ standard libraries.

What to put in a header file

Reference: What to put in a header file from Microsoft C++ language reference

In header files, write classes, methods and variable declarations. You can also make class-related definitions.

  • Definitions
    • Class definition
    • Inline function definition
    • Macro definition
  • Declarations
    • extern variable declaration
    • typedef declaration
    • Global function declaration

The declared functions in the header file are defined in the source file. Be aware of items not to be included in the header file. For example, the next chapter explains why variables are only declarated and are’nt defined in the header file.

Items that should not be written in the header file

Reference : What to put in a header file from Microsoft C++ language reference

Items such as duplicate definitions, that may cause confusion.

  • Definition of built-in types (int, float, string, etc.)
  • Anonymous namespace
    • That is definition a class in a namespace that is not named.
  • Using directive
    • If “using” is used, the namespace is also applied indirectly to the source file that read the header file, and it is easy to get confused.

Items that allocate memory area. (When multiple source files are read, each item reserves another area with the same name, which results in duplicate definition.)

  • Non-inline function definition
    • Inline function will be expanded to the call destination, so they have no problem.
  • Defining non-const variables (variables that are not constants)
    • Even if it is static, the variables are not shared and the entity is created for each source file.
    • Use const variables to define constants.

How to define a function?

Write only the declaration in the header file myClass.h.

//myClass.h
void myFunction();

Define the function in one of the .cpp files that are compiled together (either the main source file or myClass.cpp created for each header file).

//myClass.cpp
#include "myClass.h"
void myFunction(){
    printf("This is my function!");
}

In other .cpp files, you can use and use myFuction() defined in myClass.cpp by including only myClass.h.

How to define a variable?

Only “extern” is used in the header file myClass.h.

//myClass.h
extern int myVar;

Define the global variables in one of the .cpp files that are compiled together (either the main source file or myClass.cpp created for each header file).

//myClass.cpp
#include "myClass.h"
int myVar;

In other .cpp files, you can use variables by including only myClass.h. However, it is not recommended because it rarely uses variables in header file and it’s good to use class variables in C++.

Use include guards

Reference: Include guards from Microsoft C++ language reference

Include guard is a mechanism to prevent duplicate inclusion of header files. Duplicate inclusion can occur, for example, if you include one header file A in another header file B, then include A and B from a C++ source file.

//myClass.h
#ifndef MYCLASS_H
#define MYCLASS_H
/*myClass.h本体*/
#endif

[error]No such file or directory (header file)

Error Detail

When I compile c++ file using g++ command as below, the fatal error: numpy/arrayobject.h: No such file or directory occurred.

>g++ filename.cpp -std=c++11 -IC:\Python27\include -lpython2.7
In file included from filename.cpp:1:
../libs/matplotlibcpp.h:17:12: fatal error: numpy/arrayobject.h: No such file or directory
   17 | #  include <numpy/arrayobject.h>

matplotlibcpp.h in the source code is c++ header file to plot a graph.

numpy/arrayobject.h is in the directory C:\Python27\Lib\site-packages\numpy\core\include\numpy.

Cause

The compiler could not find arrayobject.h because that file is not included in the include search path.

Solution

Add the path to arrayobject.h using -I command line option as follows.

>g++ filename.cpp -std=c++11 -IC:\Python27\include -lpython2.7 -IC:\Python27\Lib\site-packages\numpy\core\include

How to create C++ Plugin for Maya

GOAL

To set up the environment for C++ Maya plugin. To build sample plug-in and execute it.

Environment

Maya 2018
Maya 2018 Update 6 win64 DevKit
Windows10 with environment for C++ compile
Microsoft Visual C++ 2017 ver15.8.4

Method

Get Maya DevKit

Access Maya Developer Center. And scroll down to click “Maya <version> Update 6 win64 DevKit”. Then unzip the file.

Setting up the build environment

Refer to Autodesk Maya Document “Setting up your build environment“.

Add the 3 directories, \devkit , \mkspecs in devkitBase into Maya installation directory (e.g. C:\Program Files\Autodesk\Maya2018).

* To compile custom plug-ins, you can also find the C++ API header files(\include\maya ) and libraries(\lib).

Build enclosed plug-ins in Visual Studio

Open devkit/plug-ins folder( either maya installation folder or newly created folder where plug-in folder is copied and put would be fine). I create a folder named “maya_cpp_plugin” and copy plug-in files to the new folder.

Find “Hello World Cmd” and open it.

Add folder “include” into the list of include directories for Visual Studio. Right Click the name of project name and open Properties.

Then, add ” C:\Program Files \ Autodesk\Maya2018\include” into the Additional Include Directories.

Add ” C:\Program Files\Autodesk\Maya2018\lib” into Additional Library Directories.

Open solution file *.sln, then Visual Studio will start up. Click Build > Build Solution.

The output files are in the directory maya_cpp_plugin\helloWorldCmd\x64\Release(or Debug). “helloWorldCmd.mll” is the main plugin file.

Plug-in installation

Refer to Autodesk Maya Document “Installing a Maya plug-in“.

Add plugin helloWorldCmd.mll to the plug-in directory defined as MAYA_PLUG_IN_PATH in <username>\Documents\maya\<version>\Maya.env file. If Maya.env doesn’t exist, create it according to “Setting environment variables using Maya.env“.

Start Maya and open Plug-in Manager.

Click a check mark next to helloWorldCmd.mll

Execute the Plug-in with command

Open Script Editor and execute the Command “helloWorld”.

The message “helloWorld” is displayed on the console, upper side of the Script Editor.

Installing g++ in Windows 10

GOAL

To install g++ in Windows10 and compile a c++ file. g++ is included in

What is g++?

g++ is the command to compile c++ and the name of C++ compiler included in GCC, the GNU Compiler Collection. You can use g++ on GNU such as Cygwin and MinGW.

Method

I’ll use MinGW

Get mingw-get-setup.exe

Access the MinGW web site and go to the Downloads page. Click and downloads mingw-get-setup.exe.

from MinGW web site

Run the downloaded file.

Click “Install” an “Continue” with your preference.

Install Basic MinGW and GCC(g++).

Mark “mingw32-base-bin” and “mingw32-gcc-g++-bin” on MinGW Installation Manager.

from MinGW Installation Manager

Click Installtion > Apply Changes

from MinGW Installation Manager

Export path

Add C:\MinGW\bin into environment variables Path.

Operation check

Open Command Prompt and input the command “g++ -v”.

Command to compile C++ file

g++ helloWorld.cpp

You can see command line options at the die.net g++(1) – Linux man page.

Appendix

Additionally install msys if you’d like to use shell with MinGW.