SHA_Search Namespace Reference

Functions

template<typename IT , typename IsEqual >
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 MaxKthElement (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 >
int SHA_Search::BinarySearch ( const IT &  begin,
const IT &  end,
const typename std::iterator_traits< IT >::value_type &  key 
)

Binary Search Iteratively proceed a dichotomic search within a sorted collection on the first occurence of the key passed as parameter.

Complexity
O(log(N)).
Template Parameters
ITtype using to go through the collection.
Parameters
begin,enditerators 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.
keythe key value to be searched.
Returns
The vector index of the first found key, -1 otherwise.

Definition at line 43 of file binary.hxx.

44  {
45  int index = -1;
46  auto lowIt = begin;
47  auto highIt = end;
48  auto middleIt = lowIt + std::distance(lowIt, highIt) / 2;
49 
50  // While there is still objects between the two ITs and no object has been foud yet
51  while(lowIt < highIt && index < 0)
52  {
53  // Found object - Set index computed from initial begin IT
54  if (IsEqual()(key, *middleIt))
55  {
56  index = static_cast<int>(std::distance(begin, middleIt));
57  break;
58  }
59  // Search key within upper collection
60  else if (key > *middleIt)
61  lowIt = middleIt + 1;
62  // Search key within lower collection
63  else
64  highIt = middleIt;
65 
66  middleIt = lowIt + std::distance(lowIt, highIt) / 2;
67  }
68 
69  return index;
70  }
template<typename IT , typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>>
std::pair<int, int> SHA_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.

Complexity
O(N * O(f(a, b))), with f(a,b) the functor used; is O(1) for the default std::minus.
Template Parameters
Iteratortype using to go through the collection.
Distancefunctor type computing the distance between two elements.
Parameters
begin,enditerators 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.
Todo:
return iterators instead.

Definition at line 48 of file max_distance.hxx.

49  {
50  if (std::distance(begin, end) < 2)
51  return std::pair<int, int>(-1, -1);
52 
53  int minValIdx = 0;
54  std::pair<int, int> indexes(minValIdx, 1);
55  auto maxDist = Distance()(*begin, *(begin + 1));
56 
57  for (auto it = begin + 1; it != end; ++it)
58  {
59  const auto currentIdx = static_cast<const int>(std::distance(begin, it));
60 
61  // Keeps track of the minimum value index
62  if (*it < *(begin + minValIdx))
63  minValIdx = currentIdx;
64 
65  // Keeps track of the largest distance and the indexes
66  const auto distance = Distance()(*it, *(begin + minValIdx));
67  if (distance > maxDist)
68  {
69  maxDist = distance;
70  indexes.first = minValIdx;
71  indexes.second = currentIdx;
72  }
73  }
74 
75  return indexes;
76  }
template<typename IT , typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
IT SHA_Search::MaxKthElement ( const IT &  begin,
const IT &  end,
unsigned int  k 
)

Kth Smallest / Biggest element - Order Statitstics 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.
Complexity
recursively look on the choosen partition: N + N/2 + N/4 + N/8 + ... = O(N).
Template Parameters
ITRandom-access iterator type.
Comparefunctor 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.
kthe 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 50 of file kth_max_element.hxx.

51  {
52  const auto kSize = static_cast<const int>(std::distance(begin, end));
53  if (k >= static_cast<unsigned int>(kSize))
54  return end;
55 
56  auto pivot = begin + (rand() % kSize); // Take random pivot
57  auto newPivot = SHA_Sort::Partition<IT, Compare>(begin, pivot, end); // Partition
58 
59  // Get the index of the pivot (i'th smallest/biggest value)
60  const auto kPivotIndex = std::distance(begin, newPivot);
61 
62  // Return if at the kth position
63  if (kPivotIndex == k)
64  return newPivot;
65 
66  // Recurse search on left part if there is more than k elements within the left sequence
67  // Recurse search on right otherwise
68  return (kPivotIndex > k) ? MaxKthElement<IT, Compare>(begin, newPivot, k)
69  : MaxKthElement<IT, Compare>(newPivot, end, k - kPivotIndex);
70 
71  }
template<typename Container , typename IT , typename Compare = std::greater_equal<typename std::iterator_traits<IT>::value_type>>
Container SHA_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 in O(Nē).

Complexity
O(N * m * O(f(a, b))) with:
  • m number of elements to be looking for
  • f(a, b) the compare functor used: O(1) for the default std::greater_equal
Template Parameters
Containertype used to return the elements.
ITtype using to go through the collection.
Comparefunctor type.
Parameters
begin,enditerators 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.
mthe 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 53 of file max_m_elements.hxx.

54  {
55  if (m < 1 || m > std::distance(begin, end))
56  return Container();
57 
58  // Initiale values depends on the comparator functor
59  const auto limitValue = Compare()(0, std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
60  lowest()) ?
61  std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
62  lowest() :
63  std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
64  max();
65 
66  // Allocate the container final size
67  Container maxMElements;
68  maxMElements.resize(m, limitValue);
69  for (auto it = begin; it != end; ++it)
70  {
71  // Insert the value at the right place and bubble down replacement value
72  int index = 0;
73  auto tmpVal = *it;
74  for (auto subIt = maxMElements.begin(); index < m; ++subIt, ++index)
75  if (Compare()(tmpVal, *subIt))
76  std::swap(*subIt, tmpVal);
77  }
78 
79  return maxMElements;
80  }
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> SHA_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.

Complexity
O(N * (O(f(a, b)) + O(g(a, b))) with:
  • f(a, b) the distance functor used; is O(1) for the default std::minus.
  • g(a, b) the compare functor used; is O(1) for the default std::greater.
Template Parameters
ITtype using to go through the collection.
Distancefunctor type computing the distance between two elements.
Comparefunctor type.
Parameters
begin,enditerators 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.
Todo:
return iterators instead.

Definition at line 55 of file max_sub_sequence.hxx.

56  {
57  if (std::distance(begin, end) < 2)
58  return std::pair<int, int>(-1, -1);
59 
60  int minValIdx = 0;
61  std::pair<int, int> indexes(minValIdx, minValIdx);
62  auto minSum = static_cast<typename std::iterator_traits<IT>::value_type>(0);
63  auto currSum = *begin;
64  auto maxSum = *begin;
65 
66  for (auto it = begin + 1; it != end; ++it)
67  {
68  currSum += *it;
69  auto currentIdx = static_cast<int>(std::distance(begin, it));
70 
71  // keep track of the minimum sum and its first value index
72  if (Compare()(minSum, currSum))
73  {
74  minValIdx = currentIdx;
75  minSum = currSum;
76  }
77 
78  // Keeps track of the maximal sub array and its end value index
79  auto curMax = Distance()(currSum, minSum);
80  if (Compare()(curMax, maxSum))
81  {
82  indexes.first = minValIdx + ((*(begin + minValIdx) < 0) ? 1 : 0);
83  indexes.second = currentIdx;
84  maxSum = Distance()(currSum, minSum);
85  }
86  }
87 
88  return indexes;
89  }