summaryrefslogtreecommitdiff
path: root/boost/sort/common/util/search.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common/util/search.hpp')
-rw-r--r--boost/sort/common/util/search.hpp529
1 files changed, 529 insertions, 0 deletions
diff --git a/boost/sort/common/util/search.hpp b/boost/sort/common/util/search.hpp
new file mode 100644
index 0000000000..fbe056e2f8
--- /dev/null
+++ b/boost/sort/common/util/search.hpp
@@ -0,0 +1,529 @@
+//----------------------------------------------------------------------------
+/// @file search.hpp
+/// @brief
+/// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See copy at http://www.boost.org/LICENSE_1_0.txt )
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_SEARCH_HPP
+#define __BOOST_SORT_COMMON_SEARCH_HPP
+
+#include <boost/sort/common/util/traits.hpp>
+#include <cassert>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+
+template<class T>
+struct filter_pass
+{
+ typedef T key;
+ const key & operator()(const T & val) const
+ {
+ return val;
+ };
+};
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # I N T E R N A L F U N C T I O N S # ##
+// # # ##
+// ################################################################ ##
+// ##
+// I M P O R T A N T ##
+// ##
+// These functions are not directly callable by the user, are for internal ##
+// use only. ##
+// These functions don't check the parameters ##
+// ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+// function : internal_find_first
+/// @brief find if a value exist in the range [first, last).
+/// Always return as valid iterator in the range [first, last-1]
+/// If exist return the iterator to the first occurrence. If don't exist
+/// return the first greater than val.
+/// If val is greater than the *(last-1), return (last-1)
+/// If val is lower than (*first), return first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found,
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ Iter_t LI = first, LS = last - 1, it_out = first;
+ while (LI != LS)
+ {
+ it_out = LI + ((LS - LI) >> 1);
+ if (comp(flt(*it_out), val))
+ LI = it_out + 1;
+ else LS = it_out;
+ };
+ return LS;
+};
+//
+//-----------------------------------------------------------------------------
+// function : internal_find_last
+/// @brief find if a value exist in the range [first, last).
+/// Always return as valid iterator in the range [first, last-1]
+/// If exist return the iterator to the last occurrence.
+/// If don't exist return the first lower than val.
+/// If val is greater than *(last-1) return (last-1).
+/// If is lower than the first, return first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ Iter_t LI = first, LS = last - 1, it_out = first;
+ while (LI != LS)
+ {
+ it_out = LI + ((LS - LI + 1) >> 1);
+ if (comp(val, flt(*it_out))) LS = it_out - 1;
+ else LI = it_out;
+ };
+ return LS;
+};
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # P U B L I C F U N C T I O N S # ##
+// # # ##
+// ################################################################ ##
+// ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+// function : find_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t find_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (first == last) return last;
+ Iter_t LS = internal_find_first(first, last, val, comp, flt);
+ return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+//
+//-----------------------------------------------------------------------------
+// function : find_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t find_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t LS = internal_find_last(first, last, val, comp, flt);
+ return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+
+//----------------------------------------------------------------------------
+// function : lower_bound
+/// @brief Returns an iterator pointing to the first element in the range
+/// [first, last) that is not less than (i.e. greater or equal to) val.
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t lower_bound(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t itaux = internal_find_first(first, last, val, comp, flt);
+ return (itaux == (last - 1) and comp(flt(*itaux), val)) ? last : itaux;
+};
+//----------------------------------------------------------------------------
+// function :upper_bound
+/// @brief return the first element greather than val.If don't exist
+/// return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+/// @remarks
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t upper_bound(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t itaux = internal_find_last(first, last, val, comp, flt);
+ return (itaux == first and comp(val, flt(*itaux))) ? itaux : itaux + 1;
+}
+;
+//----------------------------------------------------------------------------
+// function :equal_range
+/// @brief return a pair of lower_bound and upper_bound with the value val.If
+/// don't exist return last in the two elements of the pair
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return pair of iterators
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline std::pair<Iter_t, Iter_t> equal_range(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ return std::make_pair(lower_bound(first, last, val, comp, flt),
+ upper_bound(first, last, val, comp, flt));
+};
+//
+//-----------------------------------------------------------------------------
+// function : insert_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ return lower_bound(first, last, val, comp, flt);
+};
+//
+//-----------------------------------------------------------------------------
+// function : insert_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ return upper_bound(first, last, val, comp, flt);
+};
+
+/*
+
+ //
+ //###########################################################################
+ // ##
+ // ################################################################ ##
+ // # # ##
+ // # I N T E R N A L F U N C T I O N S # ##
+ // # # ##
+ // ################################################################ ##
+ // ##
+ // I M P O R T A N T ##
+ // ##
+ // These functions are not directly callable by the user, are for internal ##
+ // use only. ##
+ // These functions don't check the parameters ##
+ // ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ // function : internal_find_first
+ /// @brief find if a value exist in the range [first, last).
+ /// Always return as valid iterator in the range [first, last-1]
+ /// If exist return the iterator to the first occurrence. If don't exist
+ /// return the first greater than val.
+ /// If val is greater than the *(last-1), return (last-1)
+ /// If val is lower than (*first), return first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found,
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t internal_find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ const Compare & comp= Compare() )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first;
+ while ( LI != LS)
+ { it_out = LI + ( (LS - LI) >> 1);
+ if ( comp ( *it_out, val)) LI = it_out + 1 ; else LS = it_out ;
+ };
+ return LS ;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : internal_find_last
+ /// @brief find if a value exist in the range [first, last).
+ /// Always return as valid iterator in the range [first, last-1]
+ /// If exist return the iterator to the last occurrence.
+ /// If don't exist return the first lower than val.
+ /// If val is greater than *(last-1) return (last-1).
+ /// If is lower than the first, return first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t internal_find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ const Compare &comp= Compare() )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first ;
+ while ( LI != LS)
+ { it_out = LI + ( (LS - LI + 1) >> 1);
+ if ( comp (val, *it_out)) LS = it_out - 1 ; else LI = it_out ;
+ };
+ return LS ;
+ };
+
+ //
+ //###########################################################################
+ // ##
+ // ################################################################ ##
+ // # # ##
+ // # P U B L I C F U N C T I O N S # ##
+ // # # ##
+ // ################################################################ ##
+ // ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ // function : find_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ assert ( (last - first) >= 0 );
+ if ( first == last) return last ;
+ Iter_t LS = internal_find_first ( first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : find_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t LS = internal_find_last (first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS ;
+ };
+
+ //----------------------------------------------------------------------------
+ // function : lower_bound
+ /// @brief Returns an iterator pointing to the first element in the range
+ /// [first, last) that is not less than (i.e. greater or equal to) val.
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t lower_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t itaux = internal_find_first( first, last, val,comp);
+ return (itaux == (last - 1) and comp (*itaux, val))?last: itaux;
+ };
+ //----------------------------------------------------------------------------
+ // function :upper_bound
+ /// @brief return the first element greather than val.If don't exist
+ /// return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ /// @remarks
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t upper_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t itaux = internal_find_last( first, last, val,comp);
+ return ( itaux == first and comp (val,*itaux))? itaux: itaux + 1;
+ };
+ //----------------------------------------------------------------------------
+ // function :equal_range
+ /// @brief return a pair of lower_bound and upper_bound with the value val.If
+ /// don't exist return last in the two elements of the pair
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return pair of iterators
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline std::pair<Iter_t, Iter_t> equal_range ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ return std::make_pair(lower_bound(first, last, val,comp),
+ upper_bound(first, last, val,comp));
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : insert_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ return lower_bound (first, last, val, comp);
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : insert_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ return upper_bound (first, last, val, comp);
+ };
+
+ */
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif