Heap Sort Algorithm In C++

Heap sort algorithm is a comparison based ( divide and conquer ) sorting algorithm with worst and base case complexity of O (n log n) invented by J. W. J. Williams in 1964. [1] Implementing heap sort algorithm in C++ can be divided into two phases. The first phase is to turn the original array into a binary heap structure. Each array elements ( indices ) represents the nodes of the binary heap tree. Root of tree is always the first index (0 th index) of the array. The relationship with the nodes and the indices is as following; If j is the index of current node; then

parent = floor( (j – 1) / 2)

 leftChild = (2 * j ) + 1

righChild = (2 * j ) + 2

The second phase is recursively removing the largest or smallest dependent on order by ( ascending or descending ) element from the heap ( root of the heap ) and inserting it into the array. At the end of this recursive phase original array is sorted.

Implementing Heap Sort Algorithm In C++

In this post, I will write down a heap class which takes an unsorted array pointer as a parameter or a file that has random numbers per each line.

heap.h

#ifndef HEAP_H_
#define HEAP_H_

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

class Heap
{

public:
    	
	enum order
	{
		ASCENDING, DESCENDING
	};

	Heap(std::string fileName, Heap::order type);

	Heap(int* array, int size, Heap::order type);

	void sort();

	void writeToFile(std::string fileName);
	
	void print() const;

	void setSortType(Heap::order type);

	~Heap();

protected:

	int *array;
	
	int arraySize, heapSize;
	
	Heap::order sortType;

	bool isFromFile;

	void _minHeapify(int);

	void _maxHeapify(int);

	void _buildMaxHeap();

	void _buildMinHeap();

	void _swap(int, int);
};

#endif /* HEAP_H_ */

heap.cxx

#include "heap.h"

Heap::Heap(int *array, int size, Heap::order type)
{
    this->array = array;
	this->arraySize = size - 1;
	this->heapSize = this->arraySize;
	this->sortType = type;
	this->isFromFile = false;
}

Heap::Heap(std::string fileName, Heap::order type)
{
	std::ifstream file;

	file.open(fileName.c_str());

	if(!file)
	{
		std::cerr << "File could not be opened" << std::endl;
		exit(1);
	}

	std::string temp;
	int numberOfLines = 0;

	while(getline(file, temp))
	{
		++numberOfLines;
	}

	file.clear();
	file.seekg(0, std::ios::beg);

	this->arraySize = numberOfLines;
	this->heapSize = this->arraySize;

	array = new int[this->arraySize];
	this->sortType = type;
	this->isFromFile = true;
	int c = 0;
	int number;
	while( file>>number )
	{
		this->array[c++] = number;
	}

	file.close();
}

void Heap::writeToFile(std::string fileName)
{
	std::ofstream file;
	file.open(fileName.c_str(), std::ios::out);
	
	if(file.is_open())
	{
		for(int i = 0; i < this->arraySize; i++)
		{
			file << this->array[i] << std::endl;
		}
	}
	else
	{
		std::cerr << "Unable to create file" << std::endl;
		exit(1);
	}

	file.close();
}

void Heap::print() const
{
	for (int i = 0; i < this->arraySize; i++)
	{
		if (i == 0)
		{
			std::cout << "[ " << this->array[i] << ", ";
		}
		else if (i > 0 && i < this->arraySize - 1)
		{
			std::cout << this->array[i] << ", ";
		}
		else
		{
			std::cout << this->array[i] << "]" << std::endl;
		}
	}
}

void Heap::setSortType(Heap::order type)
{
	this->sortType = type;
}

void Heap::sort()
{
	std::cout <<"Heap sort begins..." << std::endl;

	if(this->sortType == Heap::ASCENDING)
	{
		this->_buildMaxHeap();

		for(int i = this->arraySize; i>= 1; i--)
		{
			this->_swap(0, i);
			this->heapSize--;
			this->_maxHeapify(0);
		}

	}
	else if ( this->sortType == Heap::DESCENDING )
	{
		this->_buildMinHeap();

		for(int i = this->arraySize; i>= 1; i--)
		{
			this->_swap(0, i);
			this->heapSize--;
			this->_minHeapify(0);
		}
	}
}

void Heap::_buildMaxHeap()
{
	this->heapSize = this->arraySize;

	for(int i = floor(this->arraySize/2); i >= 1; i--)
	{
		this->_maxHeapify(i);
	}
}

void Heap::_buildMinHeap()
{
	this->heapSize = this->arraySize;

	for(int i = floor(this->arraySize/2); i >= 1; i--)
	{
		this->_minHeapify(i);
	}
}

void Heap::_minHeapify(int i)
{
	int left, right, smallest;

	left = 2 * i + 1;
	right = 2 * i + 2;

	if((left <= this->heapSize) && (this->array[left] < this->array[i]))
	{
		smallest = left;
	}
	else
	{
		smallest = i;
	}

	if((right <= this->heapSize) && (this->array[right] < this->array[smallest]))
	{
		smallest = right;
	}

	if(smallest != i)
	{
		this->_swap(i, smallest);
		this->_minHeapify(smallest);
	}
}

void Heap::_maxHeapify(int i)
{
	int left, right, biggest;

	left = 2 * i + 1;
	right = 2 * i + 2;

	if((left <= this->heapSize) && (this->array[left] > this->array[i]))
	{
		biggest = left;
	}
	else
	{
		biggest = i;
	}

	if((right <= this->heapSize) && (this->array[right] > this->array[biggest]))
	{
		biggest = right;
	}

	if(biggest != i)
	{
		this->_swap(i, biggest);
		this->_maxHeapify(biggest);
	}
}

void Heap::_swap(int a, int b)
{
	int temp;
	temp = this->array[a];
	this->array[a] = this->array[b];
	this->array[b] = temp;
}

Heap::~Heap()
{
	if (this->array && this->isFromFile )
	{
		delete this->array;
		this->array = NULL;
	}

	std::cout << "Heap is destructed" << std::endl;
}

main.cxx

#include "heap.h"

#include <fstream>
#include <iostream>
#include <ctime>
#include <stdlib.h>

#include "boost/random.hpp"
#include "boost/generator_iterator.hpp"

void constructRandomFile(int numberOfLines, int min, int max)
{
    typedef boost::mt19937 RNGType;
	RNGType rng(time(NULL));

	boost::uniform_int<> range( min, max);
	boost::variate_generator< RNGType, boost::uniform_int<> > random(rng, range);

	std::ofstream file;
	file.open("sample-data.txt", std::ios::out);
	
	if(file.is_open())
	{
		for(int i = 0; i < numberOfLines; i++)
		{
			file << random() << std::endl;
		}
	}
	else
	{
		std::cerr << "Unable to create file" << std::endl;
		exit(1);
	}

	file.close();
}

int main(int argc, char **argv)
{
	if ( argc != 5 )
	{
		std::cerr << "Sample Usage : " << argv[0] << " numberOfLines min max order(ascending or descending)" << std::endl;
		return -1;
	}

	int numberOfLines = atoi(argv[1]);
	int min = atoi(argv[2]);
	int max = atoi(argv[3]);
	std::string sortType = argv[4];

	constructRandomFile(numberOfLines, min, max);

	double sort_start_clk, sort_end_clk;

	Heap *heap = NULL;

	if(strcmp(sortType.c_str(), "ascending") == 0 || strcmp(sortType.c_str(), "ASCENDING") == 0)
	{
		heap = new Heap("./sample-data.txt", Heap::ASCENDING);
	}
	else if(strcmp(sortType.c_str(), "descending") == 0 || strcmp(sortType.c_str(), "DESCENDING") == 0)
	{
		heap = new Heap("./sample-data.txt", Heap::DESCENDING);
	}
	else
	{
		std::cerr << "Invalid Sort Type. Accepted values are (ascending, descending, ASCENDING, DESCENDING)" << std::endl;
		return -1;
	}

	sort_start_clk = clock();
	heap->sort();
	sort_end_clk = clock();

	double sort_time = (double) (sort_end_clk - sort_start_clk) * 1000 / CLOCKS_PER_SEC;
	
	std::cout <<"Heap Sort Time: " << sort_time << " miliseconds" << std::endl;

	std::cout << "Writing to file..." << std::endl;
	heap->writeToFile("./sorted.txt");
	std::cout << "Writing done." << std::endl;
	
	delete heap;

	return 0;
}



makefile

CC=g++
CFLAGS=-O3 -Wall -c -fmessage-length=0

all: heap

heap: main.o heap.o
    $(CC) main.o heap.o -o heap

main.o: main.cxx
	$(CC) $(CFLAGS) main.cxx

heap.o: heap.cxx
	$(CC) $(CFLAGS) heap.cxx

clean:
	rm -r heap *.o

To access the source code click the following link : http://www.chasank.com/uploads/heapsort-in-cpp-blog-chasank-com.tar.gz

To be able to compile the source code boost library should be present on the current system. To install boost library install the following libraries on console.

yum -y install boost boost-devel

For those who does not want to install boost library I have uploaded a sample data which contains unsorted ten millions lines between 1 and 10000000 ( ten millions) To download sample data click the following link; http://www.chasank.com/uploads/sample-data.tar.gz

Just remove the constructRandomFile function and boost headers from the main.cxx. Make the necessary changes to feed the heap class with sample data.

References

1. “Heapsort”, Wikipedia, Retrieved On 24.05.2015 from http://en.wikipedia.org/wiki/Heapsort

Stopping Maximo Workflow using PL/SQL

IBM Maximo Asset Management is an enterprise and comprehensive solution for managing ITIL oriented services. IBM Maximo asset management includes the asset, work, service, contract, inventory and procurment management modules as a service oriented architecture. [1] For more official information about IBM Maximo Asset Management please visit the following link; IBM Maximo Asset Management

It’s not best practice to insert or modify any data from directly database. However, sometimes maximo admins may need to insert or modify bulk data directly from database. For example;  with a new untested IBM Netcool integration thousands of IT alarms could be generated. In this case, closing or cancelling these work orders from application would become a painful situation for responsible staff.

Stopping maximo workflow using PL/SQL is possible with the following script. Maximo database keeps the work flow any application on the following tables; wfinstance, wfassignment, wfcallstack and wftransaction. By modifying these tables we can simulate the close or cancel process of a workorder process.

Stopping maximo workflow using PL/SQL;

First of all, primary keys of workorders (wonum) should be imported to a temporary table such as BULK_TABLE. We will iterate these table row by row using a PL/SQL loop.

First control is whether the current wonum exists or not. If the current wonum exists; with the second loop we will find any active workflow(s) ( somehow current record may have multiple workflows ). Inside of the second loop; we will modify tables related with work flow by unique identifier of workflow WFID. After that, we are inserting a row to wostatus table to keep the last status change of record. Lastly we are inserting a row to wftransaction table that keeps the transaction records of work flow. Please note that; nodeid, processname and processrev may change depending on current implementation of application process.

 

DECLARE
    
	V_WORKORDERID MAXIMO.WORKORDER.WORKORDERID%TYPE;
	
	V_RECORD_EXISTS NUMBER := 0;
	
	V_PARENT MAXIMO.WORKORDER.PARENT%TYPE;

BEGIN

	-- LET'S ITERATE OVER A BULK TABLE THAT HAVE WONUMS
	FOR C IN ( SELECT WONUM FROM MAXIMO.BULK_TABLE ) LOOP
	
		V_RECORD_EXISTS := 0;
		
		SELECT COUNT(*) INTO V_RECORD_EXISTS FROM WORKORDER WHERE WONUM = C.WONUM;
		
		-- WE ARE SURE CURRENT WONUM EXISTS
		IF ( V_RECORD_EXISTS <> 0 ) THEN
			
			SELECT WORKORDERID INTO V_WORKORDERID FROM WORKORDER WHERE WONUM = C.WONUM;
		
			-- CURRENT WORKORDER MAY HAVE MULTIPLE ACTIVE WORK FLOWS; WE SHOULD STOP THEM ALL
			FOR C1 IN ( SELECT WFID FROM WFINSTANCE WHERE OWNERTABLE = 'WORKORDER' AND OWNERID = V_WORKORDERID AND ACTIVE = 1 ) LOOP
			
				BEGIN
				
					UPDATE WFINSTANCE SET ACTIVE = 0 WHERE WFID = C1.WFID;
				
					UPDATE WFCALLSTACK SET ACTIVE = 0 WHERE WFID = C1.WFID;
													
					UPDATE WFASSIGNMENT SET ASSIGNSTATUS = 'INACTIVE' WHERE WFID = C1.WFID AND ASSIGNSTATUS = 'ACTIVE';
								
					UPDATE WORKORDER SET STATUS = 'CANCEL', HISTORYFLAG = 1 WHERE WORKORDERID = V_WORKORDERID;
					
					SELECT PARENT INTO V_PARENT FROM WORKORDER WHERE WORKORDERID = V_WORKORDERID;
						   
					INSERT INTO WOSTATUS
					(WONUM, STATUS, CHANGEDATE, CHANGEBY, ORGID, SITEID, WOSTATUSID, PARENT)
					VALUES
					(C.WONUM, 'CANCEL', SYSDATE, 'MAXADMIN', 'COMPANY', 'SITE', WOSTATUSSEQ.NEXTVAL, V_PARENT);
					
					-- NODEID, PROCESSNAME AND PROCESS REVISION MAY CHANGE DEPENDING BY IMPLEMENTATION
					INSERT INTO WFTRANSACTION
					(TRANSID, NODEID, WFID, TRANSTYPE, TRANSDATE, MEMO, NODETYPE, PROCESSREV, PROCESSNAME, PERSONID, OWNERTABLE, OWNERID)
					VALUES
					(WFTRANSACTIONSEQ.NEXTVAL, 100, C1.WFID, 'WFSTOP', SYSDATE, 'MANUAL STOP', 'STOP', 1, 'WOPROCESS', 'MAXADMIN', 'WORKORDER', V_WORKORDERID);
						
					COMMIT;
					
				END;
			
			END LOOP;
				
		ELSE
		
			DBMS_OUTPUT.PUT_LINE('CURRENT WONUM : '|| C.WONUM ||' DOES NOT EXISTS AT WORKORDER TABLE');
			
		END IF;
		
	END LOOP;
	
END;
/
		
			

Reference(s)

1. “IBM Maximo Asset Management“, IBM USA, Retrieved on 17-05-2015 from http://www-03.ibm.com/software/products/en/maximoassetmanagement

 

 

Building QT, VTK and ITK on Windows 7 (X64)

In this post, I will write down step by step how to build qt, vtk ( Visualization Toolkit) and itk ( Insight Toolkit ) 64 bit on a windows 7 OS. Versions may be little outdated but all they are tested and working together like a charm.

  • TOOLS AND SDKs

  • INSTALLATION ORDER

    • Firstly, we have to install Microsoft Visual Studio 2012 Express Edition with online installer. After installing MSVC 2012 we are ready for building QT with 64 bit support. For building SDK’s (especially for VTK and ITK ) you can use the following pattern;
    • C:\sdk_name\machine_type\version_name\install \source \sdk_name-bin
  • BUILDING QT

    • For QT, we should use the following directory structure; C:\Qt\x64\4.8.4\ Extract the qt-everywhere-opensource-src-4.8.4.tar.gz to C:\Qt\x64\ and rename the folder name as 4.8.4
    • Open the command prompt with administrator privileges;
    • Start -> All Programs -> Microsoft Visual Studio 2012 -> Visual Studio Tools -> VS2012 x64 Cross Tools Command Prompt
    • Change Directory with the command C:\Windows\system32>cd C:\Qt\x64\4.8.4
    • Type the following configure command .If you are planning to use phonon, web-kit, script and multimedia modules you can remove some of the parameters For more information please visit – http://qt-project.org/doc/qt-4.8/modules.html
    • C:\Qt\x64\4.8.4\configure -opensource -shared -no-webkit -no-phonon -no-phonon-backend -no-multimedia -no-audio-backend -no-script -no-qt3support -platform win32-msvc2012
    • Type ( It can take about 1 hour – 2 hour depending on your cpu power. You should take a coffee break) C:\Qt\x64\4.8.4\nmake
    • Type ( It can take about 5 minutes ) C:\Qt\x64\4.8.4\nmake install
    • Install Qt Creator and launch the program;
    • From tools -> options -> Build & run -> Qt Versions : click the add button and browse the qmake.exe which is located on C:\Qt\x64\4.8.4\bin\qmake.exe
    • From tools -> options -> Build & run -> Kits : click the add button and choose the compiler “Microsoft Visual C++ Compiler 11.0 (amd64)” and the Qt version name you have just defined press apply and ok. Now you are ready for using Qt 4.8.4 with 64 bit support.
  • BUILDING VTK

    • Extract vtk-6.0.0.zip to C:\vtk\x64\6.0.0\ and rename the folder name as just “source” Create the directories install and vtk-bin on C:\vtk\x64\6.0.0\
    • CMAKE PHASE

      • Install Cmake and launch it
      • Browse the source as : C:\vtk\x64\6.0.0\source
      • Browse the build for binaries : C:\vtk\x64\6.0.0\vtk-bin
      • Click the configure button and choose the : “Visual Studio 11 Win64”
      • After finishing the configure phase check “Grouped” And “Advanced” boxes.
      • Uncheck BUILD -> BUILD_TESTING
      • Change CMAKE -> CMAKE_CONFIGURATION_TYPES as “Release”
      • Change CMAKE -> CMAKE_INSTALL_PREFIX as “C:\vtk\x64\6.0.0\install”
      • Check Module -> Module_vtkGUISupportQt
      • Check Module -> Module_vtkGUISupportQtOpenGL
      • Check VTK -> VTK_ALL_NEW_OBJECT_FACTORY
      • Check VTK -> VTK_Group_Imaging
      • Check VTK -> VTK_MAKE_INSTANTIATORS
      • Press again configure button, it will probably show an error press ok and continue
      • Change Ungrouped Entries -> QT_QMAKE_EXECUTABLE as “C:\Qt\x64\4.8.4\bin\qmake.exe”
      • Press again configure button it will populate QT configurations as red lines again. Check them
      • Press for last time configure button If there are no red lines
      • Press Generate button.
    • VISUAL STUDIO PHASE

      • Open the VTK.sln file from c:\vtk\x64\6.0.0\vtk-bin\VTK.sln
      • MSVC 2012 will open the project solution file, from solution explorer you should be able to see 123 projects.
      • Click ALL_BUILD project with right mouse button, from the menu click Build ( at this phase vtk library will be compiled this phase will take about 1-3 hours depending on your cpu power. Coffee break again)
      • If all of the projects are built successfully; Right click the INSTALL project and press build ( at this phase, compiled dlls, libs and include headers will be installed into C:\vtk\x64\6.0.0\install – That’s all you are ready to use VTK!
  • BUILDING ITK

    • Extract the InsightToolkit-4.4.0.zip file into C:\itk\x64\4.4.0\ and rename the extracted folder as source Create the directories install and itk-bin on C:\itk\x64\4.4.0\
    • CMAKE PHASE

      • Launch CMake, delete & reload cache – Browse the source as : C:\itk\x64\4.4.0\source – Browse the build for binaries : C:\itk\x64\4.4.0\itk-bin
      • Click the configure button and choose the : “Visual Studio 11 Win64”
      • After finishing the configure phase check “Grouped” And “Advanced” boxes.
      • Uncheck BUILD -> BUILD_EXAMPLES
      • Check BUILD -> BUILD_SHARED_LIBS
      • Uncheck BUILD -> BUILD_TESTING
      • Change CMAKE -> CMAKE_CONFIGURATION_TYPES as “Release”
      • Change CMAKE -> CMAKE_INSTALL_PREFIX as “C:\itk\x64\4.4.0\install”
      • Change ITK -> ITK_COMPUTER_MEMORY_SIZE as the amount of memory you are using in GB
      • Check ITK -> ITK_USE_64BITS_IDS
      • Check Module -> Module_ITKVtkGlue
      • Press again configure button; – Take a look at Ungrouped Entries -> VTK_DIR entry it should be “C:\vtk\x64\6.0.0\vtk-bin” If not set it.
      • Press again configure button and if there are no red lines anymore
      • Press Generate button.
    • VISUAL STUDIO PHASE

      • Open the ITK.sln file from c:\itk\x64\4.4.0\itk-bin\ITK.sln
      • MSVC 2012 will open the project solution file, from solution explorer you should be able to see 214 projects.
      • Click ALL_BUILD project with right mouse button, from the menu click Build ( at this phase itk library will be compiled this phase will take about 1-3 hours depending on your cpu power. Last coffee break)
      • If all of the projects are built successfully; Right click the INSTALL project and press build ( at this phase, compiled dlls, libs and include headers will be installed into C:\itk\x64\4.4.0\install – That’s all you are ready to use ITK!
  • USING QT-VTK-ITK ALL TOGETHER IN SAME PROJECT

    • Launch Qt Creator and create a Qt Project, to be able to use VTK and ITK libraries on that project you should add the following lines to your .pro file.
    • NOTE: Copy the binary dll files located on c:\vtk\x64\6.0.0\install\bin\ and c:\itk\x64\4.4.0\install\bin\ into the build folder of your project or you may add these folders to system wide PATH

     

DEFINES += "vtkRenderingCore_AUTOINIT=4(vtkInteractionStyle,vtkRenderingFreeType,vtkRenderingFreeTypeOpenGL,vtkRenderingOpenGL)"
DEFINES += "vtkRenderingVolume_AUTOINIT=1(vtkRenderingVolumeOpenGL)"
DEFINES += _CRT_SECURE_NO_WARNINGS

win32: LIBS += "advapi32.lib" "ws2_32.lib" "Rpcrt4.lib"

win32: LIBS += -LC:/vtk/x64/6.0.0/install/lib \
-lvtkChartsCore-6.0 \
-lvtkCommonColor-6.0 \
-lvtkCommonComputationalGeometry-6.0 \
-lvtkCommonCore-6.0 \
-lvtkCommonDataModel-6.0 \
-lvtkCommonExecutionModel-6.0 \
-lvtkCommonMath-6.0 \
-lvtkCommonMisc-6.0 \
-lvtkCommonSystem-6.0 \
-lvtkCommonTransforms-6.0 \
-lvtkDICOMParser-6.0 \
-lvtkDomainsChemistry-6.0 \
-lvtkFiltersAMR-6.0 \
-lvtkFiltersCore-6.0 \
-lvtkFiltersExtraction-6.0 \
-lvtkFiltersFlowPaths-6.0 \
-lvtkFiltersGeneral-6.0 \
-lvtkFiltersGeneric-6.0 \
-lvtkFiltersGeometry-6.0 \
-lvtkFiltersHybrid-6.0 \
-lvtkFiltersHyperTree-6.0 \
-lvtkFiltersImaging-6.0 \
-lvtkFiltersModeling-6.0 \
-lvtkFiltersParallel-6.0 \
-lvtkFiltersParallelImaging-6.0 \
-lvtkFiltersProgrammable-6.0 \
-lvtkFiltersSelection-6.0 \
-lvtkFiltersSources-6.0 \
-lvtkFiltersStatistics-6.0 \
-lvtkFiltersTexture-6.0 \
-lvtkFiltersVerdict-6.0 \
-lvtkGUISupportQt-6.0 \
-lvtkGUISupportQtOpenGL-6.0 \
-lvtkGeovisCore-6.0 \
-lvtkIOAMR-6.0 \
-lvtkIOCore-6.0 \
-lvtkIOEnSight-6.0 \
-lvtkIOExodus-6.0 \
-lvtkIOExport-6.0 \
-lvtkIOGeometry-6.0 \
-lvtkIOImage-6.0 \
-lvtkIOImport-6.0 \
-lvtkIOInfovis-6.0 \
-lvtkIOLSDyna-6.0 \
-lvtkIOLegacy-6.0 \
-lvtkIOMINC-6.0 \
-lvtkIOMovie-6.0 \
-lvtkIONetCDF-6.0 \
-lvtkIOPLY-6.0 \
-lvtkIOParallel-6.0 \
-lvtkIOSQL-6.0 \
-lvtkIOVideo-6.0 \
-lvtkIOXML-6.0 \
-lvtkIOXMLParser-6.0 \
-lvtkImagingColor-6.0 \
-lvtkImagingCore-6.0 \
-lvtkImagingFourier-6.0 \
-lvtkImagingGeneral-6.0 \
-lvtkImagingHybrid-6.0 \
-lvtkImagingMath-6.0 \
-lvtkImagingMorphological-6.0 \
-lvtkImagingSources-6.0 \
-lvtkImagingStatistics-6.0 \
-lvtkImagingStencil-6.0 \
-lvtkInfovisCore-6.0 \
-lvtkInfovisLayout-6.0 \
-lvtkInteractionImage-6.0 \
-lvtkInteractionStyle-6.0 \
-lvtkInteractionWidgets-6.0 \
-lvtkNetCDF-6.0 \
-lvtkNetCDF_cxx-6.0 \
-lvtkParallelCore-6.0 \
-lvtkRenderingAnnotation-6.0 \
-lvtkRenderingContext2D-6.0 \
-lvtkRenderingCore-6.0 \
-lvtkRenderingFreeType-6.0 \
-lvtkRenderingFreeTypeOpenGL-6.0 \
-lvtkRenderingGL2PS-6.0 \
-lvtkRenderingHybridOpenGL-6.0 \
-lvtkRenderingImage-6.0 \
-lvtkRenderingLOD-6.0 \
-lvtkRenderingLabel-6.0 \
-lvtkRenderingOpenGL-6.0 \
-lvtkRenderingVolume-6.0 \
-lvtkRenderingVolumeAMR-6.0 \
-lvtkRenderingVolumeOpenGL-6.0 \
-lvtkViewsContext2D-6.0 \
-lvtkViewsCore-6.0 \
-lvtkViewsGeovis-6.0 \
-lvtkViewsInfovis-6.0 \
-lvtkalglib-6.0 \
-lvtkexoIIc-6.0 \
-lvtkexpat-6.0 \
-lvtkfreetype-6.0 \
-lvtkftgl-6.0 \
-lvtkgl2ps-6.0 \
-lvtkhdf5-6.0 \
-lvtkhdf5_hl-6.0 \
-lvtkjpeg-6.0 \
-lvtkjsoncpp-6.0 \
-lvtklibxml2-6.0 \
-lvtkmetaio-6.0 \
-lvtkoggtheora-6.0 \
-lvtkpng-6.0 \
-lvtkproj4-6.0 \
-lvtksqlite-6.0 \
-lvtksys-6.0 \
-lvtktiff-6.0 \
-lvtkverdict-6.0 \
-lvtkzlib-6.0

INCLUDEPATH += C:/vtk/x64/6.0.0/install/include/vtk-6.0
DEPENDPATH += C:/vtk/x64/6.0.0/install/include/vtk-6.0

win32: LIBS += -LC:/itk/x64/4.5.0/install/lib \
-lITKBiasCorrection-4.5 \
-lITKBioCell-4.5 \
-lITKCommon-4.5 \
-lITKDICOMParser-4.5 \
-lITKEXPAT-4.5 \
-lITKFEM-4.5 \
-lITKIOBMP-4.5 \
-lITKIOBioRad-4.5 \
-lITKIOCSV-4.5 \
-lITKIOGDCM-4.5 \
-lITKIOGE-4.5 \
-lITKIOGIPL-4.5 \
-lITKIOHDF5-4.5 \
-lITKIOIPL-4.5 \
-lITKIOImageBase-4.5 \
-lITKIOJPEG-4.5 \
-lITKIOLSM-4.5 \
-lITKIOMRC-4.5 \
-lITKIOMesh-4.5 \
-lITKIOMeta-4.5 \
-lITKIONIFTI-4.5 \
-lITKIONRRD-4.5 \
-lITKIOPNG-4.5 \
-lITKIOSiemens-4.5 \
-lITKIOSpatialObjects-4.5 \
-lITKIOStimulate-4.5 \
-lITKIOTIFF-4.5 \
-lITKIOTransformBase-4.5 \
-lITKIOTransformHDF5-4.5 \
-lITKIOTransformInsightLegacy-4.5 \
-lITKIOTransformMatlab-4.5 \
-lITKIOVTK-4.5 \
-lITKIOXML-4.5 \
-lITKKLMRegionGrowing-4.5 \
-lITKLabelMap-4.5 \
-lITKMesh-4.5 \
-lITKMetaIO-4.5 \
-lITKNrrdIO-4.5 \
-lITKOptimizers-4.5 \
-lITKPath-4.5 \
-lITKPolynomials-4.5 \
-lITKQuadEdgeMesh-4.5 \
-lITKSpatialObjects-4.5 \
-lITKStatistics-4.5 \
-lITKVNLInstantiation-4.5 \
-lITKVTK-4.5 \
-lITKVideoCore-4.5 \
-lITKVideoIO-4.5 \
-lITKVtkGlue-4.5 \
-lITKWatersheds-4.5 \
-lITKgiftiio-4.5 \
-lITKniftiio-4.5 \
-lITKznz-4.5 \
-litkNetlibSlatec-4.5 \
-litkdouble-conversion-4.5 \
-litkgdcmCommon-4.5 \
-litkgdcmDICT-4.5 \
-litkgdcmDSED-4.5 \
-litkgdcmIOD-4.5 \
-litkgdcmMSFF-4.5 \
-litkgdcmjpeg12-4.5 \
-litkgdcmjpeg16-4.5 \
-litkgdcmjpeg8-4.5 \
-litkhdf5-4.5 \
-litkhdf5_cpp-4.5 \
-litkjpeg-4.5 \
-litkopenjpeg-4.5 \
-litkpng-4.5 \
-litksys-4.5 \
-litktiff-4.5 \
-litkv3p_lsqr-4.5 \
-litkv3p_netlib-4.5 \
-litkvcl-4.5 \
-litkvnl-4.5 \
-litkvnl_algo-4.5 \
-litkzlib-4.5

INCLUDEPATH += C:/itk/x64/4.5.0/install/include/ITK-4.5
DEPENDPATH += C:/itk/x64/4.5.0/install/include/ITK-4.5

LDAP Authentication using Php

LDAP (Lightweight Directory Access Protocol) is an open and vendor-neutral application protocol for accessing and maintaining directory information services using IP network based on server – client model.[1] LDAP server can contain a huge organization’s hierarchical directory tree. For example; you may want to send an email to IT support department that you have never emailed before on a big company. An email client program such as Microsoft Outlook can find the IT support staff by using company’s LDAP server. Authentication using LDAP protocol instead of database authentication could be done. In this post, I will show the ldap authentication using php script.

LDAP Authentication Using Php Script

Let’s assume application we are using, has an Oracle database to store user and application data but authentication is done with LDAP server. We have to use the following code to authenticate user


Note that for oracle and ldap connection, you should turn on apache modules on configuration file.

<?php

    ob_start();
	session_start();
	
	$login_id = '';
	$password = '';
	
	if (isset($_POST['loginid']) && !empty($_POST['loginid'])) 
	{
		$login_id = trim($_POST['loginid']);
	}
	else
	{
		$_SESSION['ERROR_MESSAGE'] = 'Login Name Field Is Required';
		
		$url = '../../index.php';
 		header('Location: '.$url);
 		exit();
	}
	
	if (isset($_POST['password']) && !empty($_POST['password'])) 
	{
		$password = trim($_POST['password']);
	}
	else
	{
		$_SESSION['ERROR_MESSAGE'] = 'Password Field Is Required';
		
		$url = '../../index.php';
 		header('Location: '.$url);
 		exit();
	}
	
	$db_user = getenv("DB_USER");
	$db_pass = getenv("DB_PASS");
	$db_name = getenv("DB_NAME");
	$db_charset = getenv("DB_CHARSET");
	
	$db = oci_connect($db_user, $db_pass, $db_name, $db_charset, OCI_DEFAULT);
	if (!$db) 
	{
		$_SESSION['ERROR_MESSAGE'] = oci_error()['message'];
		
		$url = '../../index.php';
 		header('Location: '.$url);
 		exit();
	}
	
	$query = "SELECT LOGINID, DISTINGUISHEDNAME FROM USER WHERE LOGINID = :loginid AND STATUS = 'ACTIVE'";
	
	$stid = oci_parse($db, $query);

	oci_bind_by_name($stid, ':loginid', $login_id);
	oci_execute($stid);
	
	$row = oci_fetch_array($stid, OCI_ASSOC+OCI_RETURN_NULLS);
	
	if ( oci_num_rows($stid) == 1 )
	{
		$host = getenv("LDAP_HOST");
		$ldaptree = getenv("LDAP_TREE"); // ex: DC=company,DC=domain
		$ldapdn = '';
		
		$ldapdn = $row['DISTINGUISHEDNAME'];
		
		$ldapconn = ldap_connect($host);
		$ds = $ldapconn;
 
		ldap_set_option($ds, LDAP_OPT_PROTOCOL_VERSION, 3);
		ldap_set_option($ds, LDAP_OPT_REFERRALS, 0);
		ldap_set_option($ds, LDAP_OPT_NETWORK_TIMEOUT, 100);

		if ($ldapconn) 
		{	
			// If user can bind with his password, LDAP authentication is succeed.
			$ldapbind = ldap_bind($ldapconn, $ldapdn, $password);
	
			if($ldapbind)
			{
				$_SESSION['USERID'] = $row['LOGINID'];
		
				oci_free_statement($stid);
				oci_close($db);
				
				ldap_close($ldapconn);
	
				$url = '../start_center.php';
				header('Location: '.$url);
				exit();
			}
			// LDAP Authentication failed
			else
			{
				$_SESSION['ERROR_MESSAGE'] = 'Access Denied!';
		
				oci_free_statement($stid);
				oci_close($db);
		
				$url = '../../index.php';
				header('Location: '.$url);
				exit();
			}
		} 
		else
		{
			$_SESSION['ERROR_MESSAGE'] = 'Access Denied!';
		
			oci_free_statement($stid);
			oci_close($db);
		
			$url = '../../index.php';
			header('Location: '.$url);
			exit();
		}	
	}
	else
	{
		$_SESSION['ERROR_MESSAGE'] = 'Access Denied!';
		
		oci_free_statement($stid);
		oci_close($db);
		
		$url = '../../index.php';
 		header('Location: '.$url);
 		exit();
	}
?>

 References:

1. “Lightweight Directory Access Protocol”, wikipedia.com, Retrived on 21.05.2015 from http://en.wikipedia.org/wiki/Lightweight_Directory_Access_Protocol

How to implement stack using linked list in c++

Stack is one of the basic data structure of the computer science. In modern computer technology random access memory (RAM) is used as stack to store the register’s (accumulator) of CPU on each interrupt or context change. Context change can be explained as; Let’s imagine while cpu is executing a process, operating system decides to run another process which has a higher priority, then current register data is pushed to memory (RAM) to take a snapshot of first process. After while when operating system decides to execute the first process again. Snapshot is popped from RAM to resume initial execution.

Stack can be also implemented on higher level computing languages such as c, c++ or Java. In this post I will show how to implement stack using linked list in c++.

How to implement stack using linked list in c++

Class Node represents the data which stack will store.  Class Node has two attributes; the data itself and the reference to next node which may be NULL on different circumstances.

Class Stack represents the stack itself. Class has two attributes; A reference to the top node and the current size of stack. Most important functions of Stack class are push and pop.

Push function takes the data itself or Node reference. When the push function is called with parameter data, the function allocates new Node reference with the parameter data and calls the other Push function to store node to the stack.

Pop function returns the last pushed Node’s data and decrease the stack size by one.


Note: this Stack implementation uses LIFO (Last In First Out).

To compile the source code with gcc, copy and name the following code block as stack.cpp and run the following command on console.

g++ stack.cpp -o stack

To run the compiled code.

./stack

#include <iostream>

template< class T >
class Node
{
public:
    Node(T data)
	{
		this->data = data;
		this->next = NULL;
	}
	
	~Node()
	{
	}
	
	T getData() const
	{
		return this->data;
	}
	
	Node< T >* getNext()
	{
		return this->next;
	}
	
	void setNext(Node< T >* node)
	{
		this->next = node;
	}
	
	void setData(T data)
	{
		this->data = data;
	}
	
protected:

	T data;
	Node* next;
};

template < class T >
class Stack
{
public:

	Stack()
	{
		this->top = NULL;
		this->size = 0;
	}
	
	~Stack()
	{
		Node < T > *temp = this->top;
		
		while ( temp != NULL )
		{
			Node< T >* current = temp->getNext();
			std::cout << "Deallocation : " << temp->getData() << std::endl;
			delete temp;
			temp = current;
		}
	}
	
	bool isEmpty()
	{
		return this->top == NULL;
	}
	
	void push(T t)
	{
		Node< T >* node = new Node< T >(t);
		this->push(node);
	}
	
	void push(Node< T >* node)
	{
		std::cout << "Push : " << node->getData() << std::endl;	
		if( this->top == NULL )
		{
			this->top = node;
			this->top->setNext(NULL);
		}
		else
		{
			node->setNext(this->top);
			this->top = node;
		}
		this->size += 1;
	}
	
	T pop()
	{	
		Node< T > *temp = this->top;
		this->top = top->getNext();
		
		std::cout << "Pop : " << temp->getData() << std::endl;
		this->size -= 1;
		return temp->getData();
	}
	
	void printStack()
	{
		Node< T > *current = this->top;
		
		std::cout << "Size of the stack : " << this->size << std::endl;
		
		while( current != NULL )
		{
			std::cout << current->getData() << std::endl;
			current = current->getNext();
		}
	}
	
	int getSize() const
	{
		return this->size;
	}

protected:

	Node< T >* top;
	
	int size;
};

int main(int argc, char **argv)
{
	Stack< int >* stack = new Stack< int >();
	
	stack->push(4);
	stack->push(2);
	stack->push(6);
	int popped_int = stack->pop();
	
	std::cout << "Popped node : " << popped_int << std::endl;
	
	stack->push(12);
	stack->push(67);
	stack->push(6);
	stack->printStack();
	
	int poppedNode = stack->pop();
	std::cout << "Popped node : " << poppedNode << std::endl;
	
	stack->printStack();
	
	delete stack;
	
	return 0;
}