SearchTool.h

Go to the documentation of this file.

#ifndef __KOME_CORE_SEARCH_TOOL_H__
#define __KOME_CORE_SEARCH_TOOL_H__


#include <boost/function.hpp>


namespace kome {
    namespace core {

        class CORE_TOOLKITS_CLASS SearchTool {
        public:
            template< typename S, typename T >
            static int binarySearch(
                    S value,
                    boost::function< T ( int ) > getElementFun,
                    boost::function< int ( T, S ) > compareFun,
                    int size
            ) {
                // 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;
            }
        };
    }
}

#endif  // __KOME_CORE_SEARCH_TOOL_H__