BitonicSort.h File Reference

#include <cstdint>
#include <vector>

Go to the source code of this file.

Enumerations
enum	sort_direction { up, down }

Functions
template<typename T >
void	BitonicMerge (sort_direction aDir, typename std::vector< T >::iterator &aDataStart, typename std::vector< T >::iterator &aDataEnd)
template<typename T >
void	BitonicSort (sort_direction aDir, typename std::vector< T >::iterator &aDataStart, typename std::vector< T >::iterator &aDataEnd)

Enumeration Type Documentation

sort_direction

enum sort_direction

Enumerator
up
down

Definition at line 7 of file BitonicSort.h.

{ up, down };

Function Documentation

BitonicMerge()

template<typename T >

void BitonicMerge	(	sort_direction	aDir,
		typename std::vector< T >::iterator &	aDataStart,
		typename std::vector< T >::iterator &	aDataEnd
	)

Definition at line 41 of file BitonicSort.h.

References edm::swap(), and up.

                                                           {
  uint32_t lSize(aDataEnd - aDataStart);
  if (lSize > 1) {
    uint32_t lPower2(1);
    while (lPower2 < lSize)
      lPower2 <<= 1;

    typename std::vector<T>::iterator lMidpoint(aDataStart + (lPower2 >> 1));
    typename std::vector<T>::iterator lFirst(aDataStart);
    typename std::vector<T>::iterator lSecond(lMidpoint);

    for (; lSecond != aDataEnd; ++lFirst, ++lSecond) {
      if (((*lFirst) > (*lSecond)) == (aDir == up)) {
        std::swap(*lFirst, *lSecond);
      }
    }

    BitonicMerge<T>(aDir, aDataStart, lMidpoint);
    BitonicMerge<T>(aDir, lMidpoint, aDataEnd);
  }
}

BitonicSort()

template<typename T >

void BitonicSort	(	sort_direction	aDir,
		typename std::vector< T >::iterator &	aDataStart,
		typename std::vector< T >::iterator &	aDataEnd
	)

Definition at line 22 of file BitonicSort.h.

References down, and up.

                                                          {
  uint32_t lSize(aDataEnd - aDataStart);
  if (lSize > 1) {
    typename std::vector<T>::iterator lMidpoint(aDataStart + (lSize >> 1));
    if (aDir == down) {
      BitonicSort<T>(up, aDataStart, lMidpoint);
      BitonicSort<T>(down, lMidpoint, aDataEnd);
    } else {
      BitonicSort<T>(down, aDataStart, lMidpoint);
      BitonicSort<T>(up, lMidpoint, aDataEnd);
    }
    BitonicMerge<T>(aDir, aDataStart, aDataEnd);
  }
}