huc::search Namespace Reference

Functions
template<typename IT , typename IsEqual = std::equal_to<typename std::iterator_traits<IT>::value_type>>
int	BinarySearch (const IT &begin, const IT &end, const typename std::iterator_traits< IT >::value_type &key)
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
IT	KthOrderStatistic (const IT &begin, const IT &end, unsigned int k)
template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>>
std::pair< int, int >	MaxDistance (const IT &begin, const IT &end)
template<typename Container , typename IT , typename Compare = std::greater_equal<typename std::iterator_traits<IT>::value_type>>
Container	MaxMElements (const IT &begin, const IT &end, const int m)
template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>, typename Compare = std::greater<typename std::iterator_traits<IT>::value_type>>
std::pair< int, int >	MaxSubSequence (const IT &begin, const IT &end)

Function Documentation

template<typename IT , typename IsEqual = std::equal_to<typename std::iterator_traits<IT>::value_type>>

int huc::search::BinarySearch	(	const IT &	begin,
		const IT &	end,
		const typename std::iterator_traits< IT >::value_type &	key
	)

Binary Search - Given a sorted sequence, find the exact position of a specific value.

Template Parameters

IT	type using to go through the collection.
Compare	functor type (std::less_equal to find kth smallest element, std::greater_equal to find the kth biggest one).

Parameters

begin,end	iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
key	the key value to be searched.

Returns

The index of the first key occurence found, -1 if not found.

Definition at line 44 of file binary.hxx.

    {
      int index = -1;
      auto lowIt = begin;
      auto highIt = end;
      auto middleIt = lowIt + std::distance(lowIt, highIt) / 2;

      // While there is still objects between the two ITs and no object has been foud yet
      while(lowIt < highIt && index < 0)
      {
        // Found object - Set index computed from initial begin IT
        if (IsEqual()(key, *middleIt))
        {
          index = static_cast<int>(std::distance(begin, middleIt));
          break;
        }
        // Search key within upper collection
        else if (key > *middleIt)
          lowIt = middleIt + 1;
        // Search key within lower collection
        else
          highIt = middleIt;

        middleIt = lowIt + std::distance(lowIt, highIt) / 2;
      }

      return index;
    }

template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>

IT huc::search::KthOrderStatistic	(	const IT &	begin,
		const IT &	end,
		unsigned int	k
	)

Kt'h Order Statitstic - Find the kth smallest/biggest element contained within [begin, end[.

Warning

this method is not stable (does not keep order with element of the same value).

this method changes the elements order between your iterators.

Template Parameters

IT	Random-access iterator type.
Compare	functor type (std::less_equal to find kth smallest element, std::greater_equal to find the kth biggest one).

Parameters

begin,end	- ITs to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
k	the zero-based kth element - 0 for the biggest/smallest.

Returns

the kth smallest IT element of the array, the end IT in case of failure.

Definition at line 48 of file kth_order_statistic.hxx.

    {
      // Sequence does not contain enough elements: Could not find the k'th one.
      const auto kSize = static_cast<const int>(std::distance(begin, end));
      if (k >= static_cast<unsigned int>(kSize))
        return end;

      auto pivot = begin + (rand() % kSize);                           // Take random pivot
      auto newPivot = sort::Partition<IT, Compare>(begin, pivot, end); // Partition

      // Get the index of the pivot (i'th value)
      const auto kPivotIndex = std::distance(begin, newPivot);

      // If at the k'th position: found!
      if (kPivotIndex == k)
        return newPivot;

      // Recurse search on left part if there is more than k elements within the left sequence
      // Recurse search on right otherwise
      return (kPivotIndex > k) ? KthOrderStatistic<IT, Compare>(begin, newPivot, k)
                               : KthOrderStatistic<IT, Compare>(newPivot, end, k - kPivotIndex);

    }

template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>>

std::pair<int, int> huc::search::MaxDistance	(	const IT &	begin,
		const IT &	end
	)

MaxDistance Identifies the two indexes of the array with the maximal distance.

Known as the simple stock market problem with the default functor (std::minus): It finds i and j that maximizes Aj - Ai, where i < j. In other words, maximizes the benefice of a resell given an array of prices varying over time.

Template Parameters

Iterator	type using to go through the collection.
Distance	functor type computing the distance between two elements.

Parameters

begin,end

iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns

indexes of the array with the maximal distance, <-1,-1> in case of error.

Definition at line 47 of file max_distance.hxx.

    {
      if (std::distance(begin, end) < 2)
        return std::pair<int, int>(-1, -1);

      int minValIdx = 0;
      std::pair<int, int> indexes(minValIdx, 1);
      auto maxDist = Distance()(*begin, *(begin + 1));

      for (auto it = begin + 1; it != end; ++it)
      {
        const auto currentIdx = static_cast<const int>(std::distance(begin, it));

        // Keeps track of the minimum value index
        if (*it < *(begin + minValIdx))
          minValIdx = currentIdx;

        // Keeps track of the largest distance and the indexes
        const auto distance = Distance()(*it, *(begin + minValIdx));
        if (distance > maxDist)
        {
          maxDist = distance;
          indexes.first = minValIdx;
          indexes.second = currentIdx;
        }
      }

      return indexes;
    }

template<typename Container , typename IT , typename Compare = std::greater_equal<typename std::iterator_traits<IT>::value_type>>

Container huc::search::MaxMElements	(	const IT &	begin,
		const IT &	end,
		const int	m
	)

Max M Elements Identify the m maximal/minimal values sorted in decreasing/increasing order.

using this algorithm with the size of the vector as the number of elements to be found will give you a bubble sort algorithm.

Template Parameters

Container	type used to return the elements.
IT	type using to go through the collection.
Compare	functor type.

Parameters

begin,end	iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
m	the numbers of max elements value to be found.

Returns

a vector of sorted in decreasing/increasing order of the m maximum/minimum elements, an empty array in case of failure.

Definition at line 51 of file max_m_elements.hxx.

    {
      if (m < 1 || m > std::distance(begin, end))
        return Container();

      // Initiale values depends on the comparator functor
      const auto limitValue = Compare()(0,
        std::numeric_limits<typename std::iterator_traits<IT>::value_type>::lowest()) ?
          std::numeric_limits<typename std::iterator_traits<IT>::value_type>::lowest() :
          std::numeric_limits<typename std::iterator_traits<IT>::value_type>::max();

      // Allocate the container final size
      Container maxMElements;
      maxMElements.resize(m, limitValue);
      for (auto it = begin; it != end; ++it)
      {
        // Insert the value at the right place and bubble down replacement value
        int index = 0;
        auto tmpVal = *it;
        for (auto subIt = maxMElements.begin(); index < m; ++subIt, ++index)
          if (Compare()(tmpVal, *subIt))
            std::swap(*subIt, tmpVal);
      }

      return maxMElements;
    }

template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>, typename Compare = std::greater<typename std::iterator_traits<IT>::value_type>>

std::pair<int, int> huc::search::MaxSubSequence	(	const IT &	begin,
		const IT &	end
	)

Max Sub Sequence Identify the subarray with the maximum/minimum sum.

The algorithm can be seen as an elicitation of the MaxDistance one. One of the problem resolved by this algorithm is: "Given an array of gains/losses over time, find the period that represents the best/worst cummulative gain." The algorithm uses the fact that the sum operator is a transitive function.

Template Parameters

IT	type using to go through the collection.
Distance	functor type computing the distance between two elements.
Compare	functor type.

Parameters

begin,end

iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Returns

indexes of the array with the maximum/minimum sum, <-1,-1> in case of error.

Definition at line 52 of file max_sub_sequence.hxx.

    {
      if (std::distance(begin, end) < 2)
        return std::pair<int, int>(-1, -1);

      int minValIdx = 0;
      std::pair<int, int> indexes(minValIdx, minValIdx);
      auto minSum = static_cast<typename std::iterator_traits<IT>::value_type>(0);
      auto currSum = *begin;
      auto maxSum = *begin;

      int currentIdx = 1;
      for (auto it = begin + 1; it != end; ++it, ++currentIdx)
      {
        currSum += *it;

        // keep track of the minimum sum and its first value index
        if (Compare()(minSum, currSum))
        {
          minValIdx = currentIdx;
          minSum = currSum;
        }

        // Keeps track of the maximal sub array and its end value index
        auto curMax = Distance()(currSum, minSum);
        if (Compare()(curMax, maxSum))
        {
          indexes.first = minValIdx + ((*(begin + minValIdx) < 0) ? 1 : 0);
          indexes.second = currentIdx;
          maxSum = Distance()(currSum, minSum);
        }
      }

      return indexes;
    }