update firefox, partially working.

1 files changed, 0 insertions, 3385 deletions

diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
deleted file mode 100644
index 95cfd56ba..000000000
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
+++ /dev/null
@@ -1,3385 +0,0 @@
---- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2014-02-05 09:52:11.000000000 +0100
-@@ -1,1688 +1,1694 @@
--//Templated spread_sort library

--

--//          Copyright Steven J. Ross 2001 - 2009.

--// Distributed under the Boost Software License, Version 1.0.

--//    (See accompanying file LICENSE_1_0.txt or copy at

--//          http://www.boost.org/LICENSE_1_0.txt)

--

--//  See http://www.boost.org/ for updates, documentation, and revision history.

--		  

--/*

--Some improvements suggested by:

--Phil Endecott and Frank Gennari

--Cygwin fix provided by:

--Scott McMurray

--*/

--

--#ifndef BOOST_SPREAD_SORT_H

--#define BOOST_SPREAD_SORT_H

--#include <algorithm>

--#include <cstring>

--#include <vector>

--#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"

--

--namespace boost {

--  namespace detail {

--  	//This only works on unsigned data types

--  	template <typename T>

--  	inline unsigned 

--  	rough_log_2_size(const T& input) 

--  	{

--  		unsigned result = 0;

--  		//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance

--  		while((input >> result) && (result < (8*sizeof(T)))) ++result;

--  		return result;

--  	}

--

--  	//Gets the maximum size which we'll call spread_sort on to control worst-case performance

--  	//Maintains both a minimum size to recurse and a check of distribution size versus count

--  	//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead

--  	inline size_t

--  	get_max_count(unsigned log_range, size_t count)

--  	{

--  		unsigned divisor = rough_log_2_size(count);

--  		//Making sure the divisor is positive

--  		if(divisor > LOG_MEAN_BIN_SIZE)

--  			divisor -= LOG_MEAN_BIN_SIZE;

--  		else

--  			divisor = 1;

--  		unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);

--  		//Don't try to bitshift more than the size of an element

--  		if((8*sizeof(size_t)) <= relative_width)

--  			relative_width = (8*sizeof(size_t)) - 1;

--  		return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 

--  			(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  relative_width);

--  	}

--

--  	//Find the minimum and maximum using <

--  	template <class RandomAccessIter>

--  	inline void 

--  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)

--  	{

--  		min = max = current;

--  		//Start from the second item, as max and min are initialized to the first

--  		while(++current < last) {

--  			if(*max < *current)

--  				max = current;

--  			else if(*current < *min)

--  				min = current;

--  		}

--  	}

--

--  	//Uses a user-defined comparison operator to find minimum and maximum

--  	template <class RandomAccessIter, class compare>

--  	inline void 

--  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)

--  	{

--  		min = max = current;

--  		while(++current < last) {

--  			if(comp(*max, *current))

--  				max = current;

--  			else if(comp(*current, *min))

--  				min = current;

--  		}

--  	}

--

--  	//Gets a non-negative right bit shift to operate as a logarithmic divisor

--  	inline int

--  	get_log_divisor(size_t count, unsigned log_range)

--  	{

--  		int log_divisor;

--  		//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so

--  		if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)

--  			log_divisor = 0;

--  		else {

--  			//otherwise divide the data into an optimized number of pieces

--  			log_divisor += LOG_MEAN_BIN_SIZE;

--  			if(log_divisor < 0)

--  				log_divisor = 0;

--  			//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically

--  			if((log_range - log_divisor) > MAX_SPLITS)

--  				log_divisor = log_range - MAX_SPLITS;

--  		}

--  		return log_divisor;

--  	}

--

--  	template <class RandomAccessIter>

--  	inline RandomAccessIter * 

--  	size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)

--  	{

--  		//Assure space for the size of each bin, followed by initializing sizes

--  		if(bin_count > bin_sizes.size())

--  			bin_sizes.resize(bin_count);

--  		for(size_t u = 0; u < bin_count; u++)

--  			bin_sizes[u] = 0;

--  		//Make sure there is space for the bins

--  		cache_end = cache_offset + bin_count;

--  		if(cache_end > bin_cache.size())

--  			bin_cache.resize(cache_end);

--  		return &(bin_cache[cache_offset]);

--  	}

--

--  	//Implementation for recursive integer sorting

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void 

--  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  				  , std::vector<size_t> &bin_sizes)

--  	{

--  		//This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data

--  		//If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration

--  		RandomAccessIter max, min;

--  		find_extremes(first, last, max, min);

--  		//max and min will be the same (the first item) iff all values are equivalent

--  		if(max == min)

--  			return;

--  		RandomAccessIter * target_bin;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));

--  		div_type div_min = *min >> log_divisor;

--  		div_type div_max = *max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  	

--  		//Calculating the size of each bin; this takes roughly 10% of runtime

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[(*(current++) >> log_divisor) - div_min]++;

--  		//Assign the bin positions

--  		bins[0] = first;

--  		for(unsigned u = 0; u < bin_count - 1; u++)

--  			bins[u + 1] = bins[u] + bin_sizes[u];

--  

--  		//Swap into place

--  		//This dominates runtime, mostly in the swap and bin lookups

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned u = 0; u < bin_count - 1; ++u) {

--  			RandomAccessIter * local_bin = bins + u;

--  			nextbinstart += bin_sizes[u];

--  			//Iterating over each element in this bin

--  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {

--  				//Swapping elements in current into place until the correct element has been swapped in

--  				for(target_bin = (bins + ((*current >> log_divisor) - div_min));  target_bin != local_bin; 

--  					target_bin = bins + ((*current >> log_divisor) - div_min)) {

--  					//3-way swap; this is about 1% faster than a 2-way swap with integers

--  					//The main advantage is less copies are involved per item put in the correct place

--  					data_type tmp;

--  					RandomAccessIter b = (*target_bin)++;

--  					RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);

--  					if (b_bin != local_bin) {

--  						RandomAccessIter c = (*b_bin)++;

--  						tmp = *c;

--  						*c = *b;

--  					} 

--  					else

--  						tmp = *b;

--  					*b = *current;

--  					*current = tmp;

--  				}

--  			}

--  			*local_bin = nextbinstart;

--  		}

--  		bins[bin_count - 1] = last;

--  

--  		//If we've bucketsorted, the array is sorted and we should skip recursion

--  		if(!log_divisor)

--  			return;

--  

--  		//Recursing; log_divisor is the remaining range

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {

--  			size_t count = bin_cache[u] - lastPos;

--  			//don't sort unless there are at least two items to compare

--  			if(count < 2)

--  				continue;

--  			//using std::sort if its worst-case is better

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[u]);

--  			else

--  				spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

--  		}

--  	}

--

--  	//Generic bitshift-based 3-way swapping code

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift

--  		, const unsigned log_divisor, const div_type div_min) 

--  	{

--  		RandomAccessIter * local_bin = bins + ii;

--  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {

--  			for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min));  target_bin != local_bin; 

--  				target_bin = bins + (shift(*current, log_divisor) - div_min)) {

--  				data_type tmp;

--  				RandomAccessIter b = (*target_bin)++;

--  				RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);

--  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs

--  				if (b_bin != local_bin) {

--  					RandomAccessIter c = (*b_bin)++;

--  					tmp = *c;

--  					*c = *b;

--  				} 

--  				//Note: we could increment current once the swap is done in this case, but that seems to impair performance

--  				else

--  					tmp = *b;

--  				*b = *current;

--  				*current = tmp;

--  			}

--  		}

--  		*local_bin = nextbinstart;

--  	}

--

--  	//Standard swapping wrapper for ascending values

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift

--  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 

--  	{

--  		nextbinstart += bin_sizes[ii];

--  		inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);

--  	}

--

--  	//Functor implementation for recursive sorting

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

--  	inline void 

--  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)

--  	{

--  		RandomAccessIter max, min;

--  		find_extremes(first, last, max, min, comp);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));

--  		div_type div_min = shift(*min, log_divisor);

--  		div_type div_max = shift(*max, log_divisor);

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;

--  		bins[0] = first;

--  		for(unsigned u = 0; u < bin_count - 1; u++)

--  			bins[u + 1] = bins[u] + bin_sizes[u];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned u = 0; u < bin_count - 1; ++u)

--  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);

--  		bins[bin_count - 1] = last;

--  		

--  		//If we've bucketsorted, the array is sorted and we should skip recursion

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {

--  			size_t count = bin_cache[u] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[u], comp);

--  			else

--  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);

--  		}

--  	}

--

--  	//Functor implementation for recursive sorting with only Shift overridden

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void 

--  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes, right_shift shift)

--  	{

--  		RandomAccessIter max, min;

--  		find_extremes(first, last, max, min);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));

--  		div_type div_min = shift(*min, log_divisor);

--  		div_type div_max = shift(*max, log_divisor);

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;

--  		bins[0] = first;

--  		for(unsigned u = 0; u < bin_count - 1; u++)

--  			bins[u + 1] = bins[u] + bin_sizes[u];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned ii = 0; ii < bin_count - 1; ++ii)

--  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

--  		bins[bin_count - 1] = last;

--  		

--  		//If we've bucketsorted, the array is sorted and we should skip recursion

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {

--  			size_t count = bin_cache[u] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[u]);

--  			else

--  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);

--  		}

--  	}

--

--  	//Holds the bin vector and makes the initial recursive call

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void 

--  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)

--  	{

--  		std::vector<size_t> bin_sizes;

--  		std::vector<RandomAccessIter> bin_cache;

--  		spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);

--  	}

--

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

--  	inline void 

--  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)

--  	{

--  		std::vector<size_t> bin_sizes;

--  		std::vector<RandomAccessIter> bin_cache;

--  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);

--  	}

--

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void 

--  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)

--  	{

--  		std::vector<size_t> bin_sizes;

--  		std::vector<RandomAccessIter> bin_cache;

--  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);

--  	}

--  }

--

--  //Top-level sorting call for integers

--  template <class RandomAccessIter>

--  inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 

--  {

--  	//Don't sort if it's too small to optimize

--  	if(last - first < detail::MIN_SORT_SIZE)

--  		std::sort(first, last);

--  	else

--  		detail::spread_sort(first, last, *first >> 0, *first);

--  }

--

--  //integer_sort with functors

--  template <class RandomAccessIter, class right_shift, class compare>

--  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,

--  						right_shift shift, compare comp) {

--  	if(last - first < detail::MIN_SORT_SIZE)

--  		std::sort(first, last, comp);

--  	else

--  		detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);

--  }

--

--  //integer_sort with right_shift functor

--  template <class RandomAccessIter, class right_shift>

--  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,

--  						right_shift shift) {

--  	if(last - first < detail::MIN_SORT_SIZE)

--  		std::sort(first, last);

--  	else

--  		detail::spread_sort(first, last, shift(*first, 0), *first, shift);

--  }

--

--  //------------------------------------------------------ float_sort source --------------------------------------

--  //Casts a RandomAccessIter to the specified data type

--  template<class cast_type, class RandomAccessIter>

--  inline cast_type

--  cast_float_iter(const RandomAccessIter & floatiter)

--  {

--  	cast_type result;

--  	std::memcpy(&result, &(*floatiter), sizeof(cast_type));

--  	return result;

--  }

--

--  //Casts a data element to the specified datinner_float_a type

--  template<class data_type, class cast_type>

--  inline cast_type

--  mem_cast(const data_type & data)

--  {

--  	cast_type result;

--  	std::memcpy(&result, &data, sizeof(cast_type));

--  	return result;

--  }

--

--  namespace detail {

--  	template <class RandomAccessIter, class div_type, class right_shift>

--  	inline void 

--  	find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)

--  	{

--  		min = max = shift(*current, 0);

--  		while(++current < last) {

--  			div_type value = shift(*current, 0);

--  			if(max < value)

--  				max = value;

--  			else if(value < min)

--  				min = value;

--  		}

--  	}

--

--  	//Specialized swap loops for floating-point casting

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii

--  		, const unsigned log_divisor, const div_type div_min) 

--  	{

--  		RandomAccessIter * local_bin = bins + ii;

--  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {

--  			for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min));  target_bin != local_bin; 

--  				target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {

--  				data_type tmp;

--  				RandomAccessIter b = (*target_bin)++;

--  				RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);

--  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs

--  				if (b_bin != local_bin) {

--  					RandomAccessIter c = (*b_bin)++;

--  					tmp = *c;

--  					*c = *b;

--  				} 

--  				else

--  					tmp = *b;

--  				*b = *current;

--  				*current = tmp;

--  			}

--  		}

--  		*local_bin = nextbinstart;

--  	}

--

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii

--  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 

--  	{

--  		nextbinstart += bin_sizes[ii];

--  		inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);

--  	}

--

--  	template <class RandomAccessIter, class cast_type>

--  	inline void 

--  	find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)

--  	{

--  		min = max = cast_float_iter<cast_type, RandomAccessIter>(current);

--  		while(++current < last) {

--  			cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);

--  			if(max < value)

--  				max = value;

--  			else if(value < min)

--  				min = value;

--  		}

--  	}

--

--  	//Special-case sorting of positive floats with casting instead of a right_shift

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void 

--  	positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;

--  		bins[0] = first;

--  		for(unsigned u = 0; u < bin_count - 1; u++)

--  			bins[u + 1] = bins[u] + bin_sizes[u];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned u = 0; u < bin_count - 1; ++u)

--  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);

--  		bins[bin_count - 1] = last;

--  		

--  		//Return if we've completed bucketsorting

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {

--  			size_t count = bin_cache[u] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[u]);

--  			else

--  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

--  		}

--  	}

--

--  	//Sorting negative_ float_s

--  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void 

--  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;

--  		bins[bin_count - 1] = first;

--  		for(int ii = bin_count - 2; ii >= 0; --ii)

--  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		//The last bin will always have the correct elements in it

--  		for(int ii = bin_count - 1; ii > 0; --ii)

--  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);

--  		//Since we don't process the last bin, we need to update its end position

--  		bin_cache[cache_offset] = last;

--  		

--  		//Return if we've completed bucketsorting

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {

--  			size_t count = bin_cache[ii] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[ii]);

--  			else

--  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);

--  		}

--  	}

--

--  	//Sorting negative_ float_s

--  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void 

--  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes, right_shift shift)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min, shift);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;

--  		bins[bin_count - 1] = first;

--  		for(int ii = bin_count - 2; ii >= 0; --ii)

--  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		//The last bin will always have the correct elements in it

--  		for(int ii = bin_count - 1; ii > 0; --ii)

--  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

--  		//Since we don't process the last bin, we need to update its end position

--  		bin_cache[cache_offset] = last;

--  		

--  		//Return if we've completed bucketsorting

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {

--  			size_t count = bin_cache[ii] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[ii]);

--  			else

--  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);

--  		}

--  	}

--

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

--  	inline void 

--  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min, shift);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;

--  		bins[bin_count - 1] = first;

--  		for(int ii = bin_count - 2; ii >= 0; --ii)

--  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		//The last bin will always have the correct elements in it

--  		for(int ii = bin_count - 1; ii > 0; --ii)

--  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

--  		//Since we don't process the last bin, we need to update its end position

--  		bin_cache[cache_offset] = last;

--  		

--  		//Return if we've completed bucketsorting

--  		if(!log_divisor)

--  			return;

--  		

--  		//Recursing

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {

--  			size_t count = bin_cache[ii] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[ii], comp);

--  			else

--  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);

--  		}

--  	}

--

--  	//Casting special-case for floating-point sorting

--  	template <class RandomAccessIter, class div_type, class data_type>

--  	inline void 

--  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;

--  		//The index of the first positive bin

--  		div_type first_positive = (div_min < 0) ? -div_min : 0;

--  		//Resetting if all bins are negative

--  		if(cache_offset + first_positive > cache_end)

--  			first_positive = cache_end - cache_offset;

--  		//Reversing the order of the negative bins

--  		//Note that because of the negative/positive ordering direction flip

--  		//We can not depend upon bin order and positions matching up

--  		//so bin_sizes must be reused to contain the end of the bin

--  		if(first_positive > 0) {

--  			bins[first_positive - 1] = first;

--  			for(int ii = first_positive - 2; ii >= 0; --ii) {

--  				bins[ii] = first + bin_sizes[ii + 1];

--  				bin_sizes[ii] += bin_sizes[ii + 1];

--  			}

--  			//Handling positives following negatives

--  			if((unsigned)first_positive < bin_count) {

--  				bins[first_positive] = first + bin_sizes[0];

--  				bin_sizes[first_positive] += bin_sizes[0];

--  			}

--  		}

--  		else

--  			bins[0] = first;

--  		for(unsigned u = first_positive; u < bin_count - 1; u++) {

--  			bins[u + 1] = first + bin_sizes[u];

--  			bin_sizes[u + 1] += bin_sizes[u];

--  		}

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned u = 0; u < bin_count; ++u) {

--  			nextbinstart = first + bin_sizes[u];

--  			inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);

--  		}

--  		

--  		if(!log_divisor)

--  			return;

--  		

--  		//Handling negative values first

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {

--  			size_t count = bin_cache[ii] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[ii]);

--  			//sort negative values using reversed-bin spread_sort

--  			else

--  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);

--  		}

--  		

--  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {

--  			size_t count = bin_cache[u] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[u]);

--  			//sort positive values using normal spread_sort

--  			else

--  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

--  		}

--  	}

--

--  	//Functor implementation for recursive sorting

--  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>

--  	inline void 

--  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

--  					, std::vector<size_t> &bin_sizes, right_shift shift)

--  	{

--  		div_type max, min;

--  		find_extremes(first, last, max, min, shift);

--  		if(max == min)

--  			return;

--  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));

--  		div_type div_min = min >> log_divisor;

--  		div_type div_max = max >> log_divisor;

--  		unsigned bin_count = div_max - div_min + 1;

--  		unsigned cache_end;

--  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);

--  			

--  		//Calculating the size of each bin

--  		for (RandomAccessIter current = first; current != last;)

--  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;

--  		//The index of the first positive bin

--  		div_type first_positive = (div_min < 0) ? -div_min : 0;

--  		//Resetting if all bins are negative

--  		if(cache_offset + first_positive > cache_end)

--  			first_positive = cache_end - cache_offset;

--  		//Reversing the order of the negative bins

--  		//Note that because of the negative/positive ordering direction flip

--  		//We can not depend upon bin order and positions matching up

--  		//so bin_sizes must be reused to contain the end of the bin

--  		if(first_positive > 0) {

--  			bins[first_positive - 1] = first;

--  			for(int ii = first_positive - 2; ii >= 0; --ii) {

--  				bins[ii] = first + bin_sizes[ii + 1];

--  				bin_sizes[ii] += bin_sizes[ii + 1];

--  			}

--  			//Handling positives following negatives

--  			if((unsigned)first_positive < bin_count) {

--  				bins[first_positive] = first + bin_sizes[0];

--  				bin_sizes[first_positive] += bin_sizes[0];

--  			}

--  		}

--  		else

--  			bins[0] = first;

--  		for(unsigned u = first_positive; u < bin_count - 1; u++) {

--  			bins[u + 1] = first + bin_sizes[u];

--  			bin_sizes[u + 1] += bin_sizes[u];

--  		}

--  		

--  		//Swap into place

--  		RandomAccessIter nextbinstart = first;

--  		for(unsigned u = 0; u < bin_count; ++u) {

--  			nextbinstart = first + bin_sizes[u];

--  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);

--  		}

--  		

--  		//Return if we've completed bucketsorting

--  		if(!log_divisor)

--  			return;

--  		

--  		//Handling negative values first

--  		size_t max_count = get_max_count(log_divisor, last - first);

--  		RandomAccessIter lastPos = first;

--  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {

--  			size_t count = bin_cache[ii] - lastPos;

--  			if(count < 2)

--  				continue;

--  			if(count < max_count)

--  				std::sort(lastPos, bin_cache[ii]);

--  			//sort negative values using reversed-bin spread_sort

--  			else

--  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);