Algorithms.h++

Go to the documentation of this file.

#ifndef __libquark_util_Algorithms_hxx
#define __libquark_util_Algorithms_hxx

namespace quark {
namespace util {

class Algorithms
{
  public:

  template<typename ITER, typename T, typename LESSTHAN>
  static int orderedInsertPosition(ITER begin, ITER end, const T &item,
                                   LESSTHAN lessThan = defaultLessThan)
  {
    if(begin == end) return 0;

    ITER left = begin;
    ITER right = end - 1;
    ITER offset = begin;

    while(left < right)
    {
      int half = (right - left) >> 1;
      ITER mid = left + half;

      if(lessThan(*mid, item))
      {
        offset = left = mid;
        ++offset;
        ++left;
      }
      else if(lessThan(item, *mid))
        right = mid;
      else
      {
        offset = mid;
        break;
      }
    }

    if(lessThan(*offset, item))
      ++offset;

    return(offset - begin);
  }

  private:

  template<typename T> static bool defaultLessThan(const T &a, const T &b)
  { return(a < b); }

  Algorithms();

  Q_DISABLE_COPY(Algorithms);
};

} // namespace util
} // namespace quark

#endif // __libquark_util_Algorithms_hxx