#ifndef RANGE_H_EMS
#define RANGE_H_EMS
#include <vector>
namespace MergeSort_EMS
{
template <typename T>
class Range
{
public:
Range( T* begin, unsigned elements ) : _array(begin), _nElements(elements)
{
}
unsigned size() const { return _nElements ; }
operator T*() { return _array; }
private:
T* _array ;
unsigned _nElements ;
};
// ranges fed to merge are expected to be contiguous memory where
// a would house the earlier of the indexes in an array that composed
// the two.
template <typename T>
Range<T> merge( Range<T> a, Range<T> b, std::vector<T>& scratch )
{
scratch.clear() ;
Range<T> merged( a, a.size()+b.size() ) ;
unsigned aIdx = 0 ;
unsigned bIdx = 0 ;
unsigned processed = 0 ;
// members of a that are not greater than b[0] will not need to be moved.
while ( aIdx < a.size() && a[aIdx] <= b[bIdx] )
++aIdx, ++processed ;
// once we reach an element in a that is greater than b[0], the rest
// of the elements in a must be moved to scratch.
if ( aIdx < a.size() )
{
scratch.insert(scratch.begin(), a+aIdx, a+a.size() ) ;
unsigned sIdx = 0 ;
while ( processed < merged.size() && sIdx < scratch.size() && bIdx < b.size() )
{
if ( scratch[sIdx] <= b[bIdx] )
merged[processed] = scratch[sIdx++] ;
else
merged[processed] = b[bIdx++] ;
++processed ;
}
if ( processed == merged.size() )
return merged ;
if ( bIdx == b.size() )
{ // only stuff in scratch left
while ( processed < merged.size() )
merged[processed++] = scratch[sIdx++] ;
}
}
// at this point, anything left in b should already be in the correct position.
return merged ;
}
}
#endif
#ifndef MERGESORT_H_EMS
#define MERGESORT_H_EMS
#include <algorithm>
#include <vector>
namespace MergeSort_EMS
{
template <typename T>
void twosies(T* array, unsigned size)
{
unsigned max_iterations = size / 2 ;
for ( unsigned i=0; i < max_iterations; ++i )
{
if ( *array > *(array+1) )
std::swap( *array, *(array+1) ) ;
array += 2 ;
}
}
template <typename T>
void merge_sort(std::vector<T> & sortee)
{
// prepare our two-element sorted subarrays
// reduces the maximum number of ranges we need to store
// at one time by half.
twosies(sortee.data(), sortee.size()) ;
// memory buffer to feed to merge
std::vector<T> scratch ;
scratch.reserve((sortee.size()+1)/2) ;
std::vector<Range<T>> ranges ;
ranges.reserve((sortee.size()+1)/2) ;
// generate initial twosie Ranges
{
const unsigned num_twosies = sortee.size() / 2 ;
T* ptr = sortee.data() ;
for ( unsigned i=0; i<num_twosies; ++i )
{
ranges.push_back(Range<T>(ptr, 2));
ptr += 2;
}
if ( sortee.size() % 2 )
ranges.push_back(Range<T>(ptr, 1)) ;
}
// work the merge
while ( ranges.size() > 1 )
{
unsigned max_to_merge = ranges.size() - ranges.size()%2 ;
unsigned i ;
for ( i=0; i<max_to_merge; i+=2 )
{
Range<T> r1 = ranges[i] ;
Range<T> r2 = ranges[i+1] ;
// CAUTION: See merge definition/comments before changing what is fed to it.
ranges[i/2] = merge(r1, r2, scratch) ;
}
if ( ranges.size()%2 ) // odd man out
ranges[i/2] = ranges.back() ;
// Use of resize requires a default constructor if used with only one argument,
// Range doesn't have a default constructor and we don't need one. Feed resize
// a bullshit argument so we don't have to implement a default constructor. Since
// we're only reducing the size of the vector, it won't be used anyway.
ranges.resize(max_to_merge/2 + ranges.size()%2, Range<T>(0,0)) ;
}
}
};
#endif
#ifndef TOSORT_H_EMS
#define TOSORT_H_EMS
#include <vector>
#include <limits>
#include <functional>
const unsigned nullindex = std::numeric_limits<unsigned>::max() ;
class ToSort
{
public:
static std::function<void(unsigned,unsigned, unsigned)> update_func ;
ToSort(const std::vector<ToSort>& v, unsigned id) ;
ToSort(const ToSort & c);
ToSort(ToSort && c) ;
ToSort& operator=(ToSort&&c) ;
ToSort& operator=(const ToSort& c) ;
operator unsigned() const { return _id ; }
private:
const std::vector<ToSort>* _container ;
unsigned _id ;
unsigned _prev_pos ;
void _update_notify() const ;
bool _in_container() const ;
unsigned _container_pos() const ;
};
#endif
#include <vector>
#include <limits>
std::function<void(unsigned,unsigned, unsigned)> ToSort::update_func = nullptr ;
ToSort::ToSort(const std::vector<ToSort>& v, unsigned id)
: _container(&v), _id(id), _prev_pos(nullindex)
{
}
ToSort::ToSort(const ToSort& c)
: _container(c._container), _id(c._id), _prev_pos(c._container_pos())
{
_update_notify() ;
}
ToSort::ToSort(ToSort&& c)
: _container(c._container), _id(c._id), _prev_pos(c._container_pos())
{
_update_notify() ;
}
ToSort& ToSort::operator=(ToSort&&c)
{
*this = c ;
c._container = nullptr ;
return *this ;
}
ToSort& ToSort::operator=(const ToSort& c)
{
_container = c._container ;
_id = c._id ;
_prev_pos = c._container_pos() ;
_update_notify() ;
return *this ;
}
void ToSort::_update_notify() const
{
if ( update_func != nullptr && _container != nullptr )
update_func(_container_pos(), _id, _prev_pos) ;
}
// if we append or push a ToSort to the end of a container,
// _in_container() may be called before the container has updated
// its size to reflect the addition, so of this is one past the end
// of the container we will consider it to be in the container.
bool ToSort::_in_container() const
{
if ( _container == nullptr )
return false ;
ToSort const * array = _container->data() ;
if ( this >= array && array + _container->size() >= this )
return true ;
return false ;
}
unsigned ToSort::_container_pos() const
{
if ( _in_container() )
return this - _container->data() ;
else
return nullindex ;
}
#include <numeric>
#include <iostream>
#include <vector>
#include <random>
namespace ms = MergeSort_EMS ;
void populate_vector(std::vector<ToSort>& v)
{
v.clear() ;
std::random_device rd ;
const unsigned v_size = rd() % 15 + 6 ;
for ( unsigned i=0; i<v_size; ++i )
v.push_back(ToSort(v, i)) ;
std::shuffle(v.begin(), v.end(), rd ) ;
}
class OnUpdate
{
std::vector<ToSort>& _v ;
public:
OnUpdate(std::vector<ToSort>& v) : _v(v) {}
void operator()(unsigned index, unsigned id, unsigned prev_index)
{
if ( prev_index == nullindex )
std::cout << id << " was inserted at " << index << '\n' ;
else
{
if ( index == nullindex )
std::cout << id << " was removed from " << prev_index << '\n' ;
else
std::cout << id << " was moved from " << prev_index << " to " << index << '\n' ;
}
}
};
void show(const std::vector<ToSort>& v)
{
std::cout << "{ " ;
for ( unsigned i=0; i< v.size(); ++i )
{
std::cout << v[i] << ' ' ;
}
std::cout << "}\n" ;
}
int main()
{
std::vector<ToSort> v ;
v.reserve(100) ;
OnUpdate update(v) ;
ToSort::update_func = update ;
do
{
ToSort::update_func = nullptr ; // disable updating while populating the vector
populate_vector(v) ;
ToSort::update_func = update ;
show(v) ;
ms::merge_sort(v) ;
show(v) ;
std::cout << '\n' ;
} while ( std::cin.get() == '\n' ) ;
}