kome::core::SearchTool Class Reference

This class has some searching algorithm method. More...

#include <SearchTool.h>

Static Public Member Functions
template<typename S , typename T >
static int	binarySearch (S value, boost::function< T(int) > getElementFun, boost::function< int(T, S) > compareFun, int size)
	binary search More...

Detailed Description

This class has some searching algorithm method.

Definition at line 26 of file SearchTool.h.

Member Function Documentation

template<typename S , typename T >

static int kome::core::SearchTool::binarySearch ( S  value, boost::function< T(int) >  getElementFun, boost::function< int(T, S) >  compareFun, int  size  )

inlinestatic

binary search

Parameters

[in]	value	specified value
[in]	getElementFun	function which get element from array.
[in]	compareFun	comparison function. return value more than zero : element's value is greater than specified value. zero: element's value is equal to specified value. less than zero: element's value is less than specified value.
[in]	size	size of array

Returns

If it contains a element which has specified value, this function returns the index. [0 or positive] Otherwise it returns (- insertion point - 1). [negative]

Definition at line 48 of file SearchTool.h.

              {
                // range of search
                int top = 0;
                int bottom = size - 1;
                int idx = -1;

                // search
                while( top <= bottom && idx < 0 ) {
                    // get element located middle of searching range
                    int mid = ( top + bottom ) / 2;
                    T elm0 = getElementFun( mid );

                    // compare
                    int cmp = compareFun( elm0, value );
                    if( cmp == 0 ) {    // particular element is found.
                        idx = mid;

                        // return the first of particular elements.
                        mid--;
                        while( mid >= top ) {
                            T elm1 = getElementFun( mid );
                            if( compareFun( elm1, value ) == 0 ) {  // particular element
                                idx = mid;
                                mid--;
                            }
                            else {
                                mid = top - 1;
                            }
                        }
                    }
                    else if( cmp > 0 ) {    // Element's value is greater than searching value.
                        bottom = mid - 1;
                    }
                    else {  // Element's value is less than searching value.
                        top = mid + 1;
                    }
                }

                if( idx < 0 ) {     // not found
                    idx = - top - 1;
                }

                return idx;
            }

---

The documentation for this class was generated from the following file:

• CoreToolkits/SearchTool.h