fix cross-compile on Darwin

5 files changed, 3439 insertions, 19 deletions

diff --git a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
index bf6c335de..3a79329a3 100644
--- a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
+++ b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
@@ -1,6 +1,6 @@
 --- mozilla-release.orig/media/mtransport/third_party/nICEr/src/stun/addrs.c	2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c	2014-01-03 13:06:22.000000000 +0100
-@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id:
++++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c	2014-02-05 07:19:01.000000000 +0100
+@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id: 
  #undef __unused
  #include <linux/sysctl.h>
  #endif
@@ -10,7 +10,7 @@
  #ifndef LINUX
  #if !defined(__OpenBSD__) && !defined(__NetBSD__)
  #include <net/if_var.h>
-@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id:
+@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id: 
  #include <net/if_dl.h>
  #include <net/if_types.h>
  #include <sys/sockio.h>
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
new file mode 100644
index 000000000..60d33bb2e
--- /dev/null
+++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
@@ -0,0 +1,23 @@
+--- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py	2013-12-05 17:07:48.000000000 +0100
++++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py	2014-02-05 08:12:49.000000000 +0100
+@@ -364,20 +364,6 @@ def WriteOnDiff(filename):
+ 
+ def GetFlavor(params):
+   """Returns |params.flavor| if it's set, the system's default flavor else."""
+-  flavors = {
+-    'cygwin': 'win',
+-    'win32': 'win',
+-    'darwin': 'mac',
+-  }
+-
+-  if 'flavor' in params:
+-    return params['flavor']
+-  if sys.platform in flavors:
+-    return flavors[sys.platform]
+-  if sys.platform.startswith('sunos'):
+-    return 'solaris'
+-  if sys.platform.startswith('freebsd'):
+-    return 'freebsd'
+ 
+   return 'linux'
+ 
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
new file mode 100644
index 000000000..452d380f0
--- /dev/null
+++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
@@ -0,0 +1,26 @@
+--- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py	2013-12-05 17:07:48.000000000 +0100
++++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py	2014-02-05 08:13:30.000000000 +0100
+@@ -118,23 +118,6 @@ def ensure_directory_exists(path):
+ 
+ def GetFlavor(params):
+   """Returns |params.flavor| if it's set, the system's default flavor else."""
+-  system = platform.system().lower()
+-  flavors = {
+-    'microsoft': 'win',
+-    'windows'  : 'win',
+-    'cygwin'   : 'win',
+-    'darwin'   : 'mac',
+-    'sunos'    : 'solaris',
+-    'dragonfly': 'dragonfly',
+-    'freebsd'  : 'freebsd',
+-    'netbsd'   : 'netbsd',
+-    'openbsd'  : 'openbsd',
+-  }
+-
+-  if 'flavor' in params:
+-    return params['flavor']
+-  if system in flavors:
+-    return flavors[system]
+ 
+   return 'linux'
+ 
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
index 3ee2e0fdc..809dff52a 100644
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
+++ b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
@@ -1,6 +1,6 @@
 --- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2014-01-02 14:58:37.000000000 +0100
-@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
++++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2014-02-05 07:19:01.000000000 +0100
+@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores() 
      WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1,
                   "Available number of cores:%d", number_of_cores_);
  
@@ -12,7 +12,7 @@
  #elif defined(WEBRTC_BSD) || defined(WEBRTC_MAC)
      int name[] = {
        CTL_HW,
-@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
+@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores() 
                     "Failed to get number of cores");
        number_of_cores_ = 1;
      }
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
index ac1d23267..95cfd56ba 100644
--- 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
@@ -1,14 +1,3385 @@
 --- 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-01-02 14:53:44.000000000 +0100
-@@ -21,6 +21,11 @@ Scott McMurray
- #include <vector>

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

- 

-+#include <features.h>

-+#if defined(__UCLIBC__)

-+#undef getchar

-+#endif

-+

- namespace boost {

-   namespace detail {

-   	//This only works on unsigned data types

++++ 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);

+-  		}

+-  		

+-  		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

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

+-  		}

+-  	}

+-

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

+-  	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, 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]++;

+-  		//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, comp);

+-  		}

+-  		

+-  		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

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

+-  		}

+-  	}

+-

+-  	template <class RandomAccessIter, class cast_type, class data_type>

+-  	inline void 

+-  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);

+-  	}

+-

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

+-  	inline void 

+-  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

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

+-  	}

+-

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

+-  	inline void 

+-  	float_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;

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

+-  	}

+-  }

+-

+-  //float_sort with casting

+-  //The cast_type must be equal in size to the data type, and must be a signed integer

+-  template <class RandomAccessIter, class cast_type>

+-  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 

+-  {

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

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

+-  	else

+-  		detail::float_Sort(first, last, cVal, *first);

+-  }

+-

+-  //float_sort with casting to an int

+-  //Only use this with IEEE floating-point numbers

+-  template <class RandomAccessIter>

+-  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 

+-  {

+-  	int cVal = 0;

+-  	float_sort_cast(first, last, cVal);

+-  }

+-

+-  //float_sort with functors

+-  template <class RandomAccessIter, class right_shift>

+-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 

+-  {

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

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

+-  	else

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

+-  }

+-

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

+-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 

+-  {

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

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

+-  	else

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

+-  }

+-

+-  //------------------------------------------------- string_sort source ---------------------------------------------

+-  namespace detail {

+-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.

+-  	template<class RandomAccessIter>

+-  	inline void

+-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)

+-  	{

+-  		unsigned nextOffset = char_offset;

+-  		bool done = false;

+-  		while(!done) {

+-  			RandomAccessIter curr = first;

+-  			do {

+-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character

+-  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {

+-  					done = true;

+-  					break;

+-  				}

+-  			} while(++curr != finish);

+-  			if(!done)

+-  				++nextOffset;

+-  		} 

+-  		char_offset = nextOffset;

+-  	}

+-

+-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.

+-  	template<class RandomAccessIter, class get_char, class get_length>

+-  	inline void

+-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)

+-  	{

+-  		unsigned nextOffset = char_offset;

+-  		bool done = false;

+-  		while(!done) {

+-  			RandomAccessIter curr = first;

+-  			do {

+-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character

+-  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {

+-  					done = true;

+-  					break;

+-  				}

+-  			} while(++curr != finish);

+-  			if(!done)

+-  				++nextOffset;

+-  		} 

+-  		char_offset = nextOffset;

+-  	}

+-

+-  	//A comparison functor for strings that assumes they are identical up to char_offset

+-  	template<class data_type, class unsignedchar_type>

+-  	struct offset_lessthan {

+-  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}

+-  		inline bool operator()(const data_type &x, const data_type &y) const 

+-  		{

+-  			unsigned minSize = std::min(x.size(), y.size());

+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {

+-  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))

+-  					return true;

+-  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))

+-  					return false;

+-  			}

+-  			return x.size() < y.size();

+-  		}

+-  		unsigned fchar_offset;

+-  	};

+-

+-  	//A comparison functor for strings that assumes they are identical up to char_offset

+-  	template<class data_type, class unsignedchar_type>

+-  	struct offset_greaterthan {

+-  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}

+-  		inline bool operator()(const data_type &x, const data_type &y) const 

+-  		{

+-  			unsigned minSize = std::min(x.size(), y.size());

+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {

+-  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))

+-  					return true;

+-  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))

+-  					return false;

+-  			}

+-  			return x.size() > y.size();

+-  		}

+-  		unsigned fchar_offset;

+-  	};

+-

+-  	//A comparison functor for strings that assumes they are identical up to char_offset

+-  	template<class data_type, class get_char, class get_length>

+-  	struct offset_char_lessthan {

+-  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}

+-  		inline bool operator()(const data_type &x, const data_type &y) const 

+-  		{

+-  			unsigned minSize = std::min(length(x), length(y));

+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {

+-  				if(getchar(x, u) < getchar(y, u))

+-  					return true;

+-  				else if(getchar(y, u) < getchar(x, u))

+-  					return false;

+-  			}

+-  			return length(x) < length(y);

+-  		}

+-  		unsigned fchar_offset;

+-  		get_char getchar;

+-  		get_length length;

+-  	};

+-

+-  	//String sorting recursive implementation

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)

+-  	{

+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

+-  		//Iterate to the end of the empties.  If all empty, return

+-  		while((*first).size() <= char_offset) {

+-  			if(++first == last)

+-  				return;

+-  		}

+-  		RandomAccessIter finish = last - 1;

+-  		//Getting the last non-empty

+-  		for(;(*finish).size() <= char_offset; --finish) { }

+-  		++finish;

+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.

+-  		update_offset(first, finish, char_offset);

+-  		

+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).

+-  		const unsigned max_size = bin_count;

+-  		const unsigned membin_count = bin_count + 1;

+-  		unsigned cache_end;

+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;

+-  			

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

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

+-  			if((*current).size() <= char_offset) {

+-  				bin_sizes[0]++;

+-  			}

+-  			else

+-  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;

+-  		}

+-  		//Assign the bin positions

+-  		bin_cache[cache_offset] = first;

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

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

+-  		

+-  		//Swap into place

+-  		RandomAccessIter nextbinstart = first;

+-  		//handling empty bins

+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

+-  		nextbinstart +=	bin_sizes[0];

+-  		RandomAccessIter * target_bin;

+-  		//Iterating over each element in the bin of empties

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

+-  			//empties belong in this bin

+-  			while((*current).size() > char_offset) {

+-  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);

+-  				iter_swap(current, (*target_bin)++);

+-  			}

+-  		}

+-  		*local_bin = nextbinstart;

+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops

+-  		unsigned last_bin = bin_count - 1;

+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

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

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

+-  			local_bin = bins + u;

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

+-  			//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 + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 

+-  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))

+-  					iter_swap(current, (*target_bin)++);

+-  			}

+-  			*local_bin = nextbinstart;

+-  		}

+-  		bins[last_bin] = last;

+-  		//Recursing

+-  		RandomAccessIter lastPos = bin_cache[cache_offset];

+-  		//Skip this loop for empties

+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)

+-  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));

+-  			else

+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);

+-  		}

+-  	}

+-

+-  	//Sorts strings in reverse order, with empties at the end

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)

+-  	{

+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

+-  		RandomAccessIter curr = first;

+-  		//Iterate to the end of the empties.  If all empty, return

+-  		while((*curr).size() <= char_offset) {

+-  			if(++curr == last)

+-  				return;

+-  		}

+-  		//Getting the last non-empty

+-  		while((*(--last)).size() <= char_offset) { }

+-  		++last;

+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.

+-  		update_offset(curr, last, char_offset);

+-  		RandomAccessIter * target_bin;

+-  		

+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).

+-  		const unsigned max_size = bin_count;

+-  		const unsigned membin_count = bin_count + 1;

+-  		const unsigned max_bin = bin_count - 1;

+-  		unsigned cache_end;

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

+-  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);

+-  			

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

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

+-  			if((*current).size() <= char_offset) {

+-  				bin_sizes[bin_count]++;

+-  			}

+-  			else

+-  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;

+-  		}

+-  		//Assign the bin positions

+-  		bin_cache[cache_offset] = first;

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

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

+-  		

+-  		//Swap into place

+-  		RandomAccessIter nextbinstart = last;

+-  		//handling empty bins

+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);

+-  		RandomAccessIter lastFull = *local_bin;

+-  		//Iterating over each element in the bin of empties

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

+-  			//empties belong in this bin

+-  			while((*current).size() > char_offset) {

+-  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);

+-  				iter_swap(current, (*target_bin)++);

+-  			}

+-  		}

+-  		*local_bin = nextbinstart;

+-  		nextbinstart = first;

+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops

+-  		unsigned last_bin = max_bin;

+-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }

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

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

+-  			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 = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 

+-  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))

+-  					iter_swap(current, (*target_bin)++);

+-  			}

+-  			*local_bin = nextbinstart;

+-  		}

+-  		bins[last_bin] = lastFull;

+-  		//Recursing

+-  		RandomAccessIter lastPos = first;

+-  		//Skip this loop for empties

+-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; 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_size)

+-  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));

+-  			else

+-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);

+-  		}

+-  	}

+-

+-  	//String sorting recursive implementation

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>

+-  	inline void 

+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)

+-  	{

+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

+-  		//Iterate to the end of the empties.  If all empty, return

+-  		while(length(*first) <= char_offset) {

+-  			if(++first == last)

+-  				return;

+-  		}

+-  		RandomAccessIter finish = last - 1;

+-  		//Getting the last non-empty

+-  		for(;length(*finish) <= char_offset; --finish) { }

+-  		++finish;

+-  		update_offset(first, finish, char_offset, getchar, length);

+-  		

+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).

+-  		const unsigned max_size = bin_count;

+-  		const unsigned membin_count = bin_count + 1;

+-  		unsigned cache_end;

+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;

+-  			

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

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

+-  			if(length(*current) <= char_offset) {

+-  				bin_sizes[0]++;

+-  			}

+-  			else

+-  				bin_sizes[getchar((*current), char_offset) + 1]++;

+-  		}

+-  		//Assign the bin positions

+-  		bin_cache[cache_offset] = first;

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

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

+-  		

+-  		//Swap into place

+-  		RandomAccessIter nextbinstart = first;

+-  		//handling empty bins

+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

+-  		nextbinstart +=	bin_sizes[0];

+-  		RandomAccessIter * target_bin;

+-  		//Iterating over each element in the bin of empties

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

+-  			//empties belong in this bin

+-  			while(length(*current) > char_offset) {

+-  				target_bin = bins + getchar((*current), char_offset);

+-  				iter_swap(current, (*target_bin)++);

+-  			}

+-  		}

+-  		*local_bin = nextbinstart;

+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops

+-  		unsigned last_bin = bin_count - 1;

+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

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

+-  		for(unsigned ii = 0; ii < last_bin; ++ii) {

+-  			local_bin = bins + ii;

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

+-  			//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 + getchar((*current), char_offset);  target_bin != local_bin; 

+-  					target_bin = bins + getchar((*current), char_offset))

+-  					iter_swap(current, (*target_bin)++);

+-  			}

+-  			*local_bin = nextbinstart;

+-  		}

+-  		bins[last_bin] = last;

+-  		

+-  		//Recursing

+-  		RandomAccessIter lastPos = bin_cache[cache_offset];

+-  		//Skip this loop for empties

+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)

+-  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));

+-  			else

+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);

+-  		}

+-  	}

+-

+-  	//String sorting recursive implementation

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>

+-  	inline void 

+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)

+-  	{

+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

+-  		//Iterate to the end of the empties.  If all empty, return

+-  		while(length(*first) <= char_offset) {

+-  			if(++first == last)

+-  				return;

+-  		}

+-  		RandomAccessIter finish = last - 1;

+-  		//Getting the last non-empty

+-  		for(;length(*finish) <= char_offset; --finish) { }

+-  		++finish;

+-  		update_offset(first, finish, char_offset, getchar, length);

+-  		

+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).

+-  		const unsigned max_size = bin_count;

+-  		const unsigned membin_count = bin_count + 1;

+-  		unsigned cache_end;

+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;

+-  			

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

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

+-  			if(length(*current) <= char_offset) {

+-  				bin_sizes[0]++;

+-  			}

+-  			else

+-  				bin_sizes[getchar((*current), char_offset) + 1]++;

+-  		}

+-  		//Assign the bin positions

+-  		bin_cache[cache_offset] = first;

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

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

+-  		

+-  		//Swap into place

+-  		RandomAccessIter nextbinstart = first;

+-  		//handling empty bins

+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

+-  		nextbinstart +=	bin_sizes[0];

+-  		RandomAccessIter * target_bin;

+-  		//Iterating over each element in the bin of empties

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

+-  			//empties belong in this bin

+-  			while(length(*current) > char_offset) {

+-  				target_bin = bins + getchar((*current), char_offset);

+-  				iter_swap(current, (*target_bin)++);

+-  			}

+-  		}

+-  		*local_bin = nextbinstart;

+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops

+-  		unsigned last_bin = bin_count - 1;

+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

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

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

+-  			local_bin = bins + u;

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

+-  			//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 + getchar((*current), char_offset);  target_bin != local_bin; 

+-  					target_bin = bins + getchar((*current), char_offset))

+-  					iter_swap(current, (*target_bin)++);

+-  			}

+-  			*local_bin = nextbinstart;

+-  		}

+-  		bins[last_bin] = last;

+-  		

+-  		//Recursing

+-  		RandomAccessIter lastPos = bin_cache[cache_offset];

+-  		//Skip this loop for empties

+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)

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

+-  			else

+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos

+-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);

+-  		}

+-  	}

+-

+-  	//Sorts strings in reverse order, with empties at the end

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>

+-  	inline void 

+-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)

+-  	{

+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

+-  		RandomAccessIter curr = first;

+-  		//Iterate to the end of the empties.  If all empty, return

+-  		while(length(*curr) <= char_offset) {

+-  			if(++curr == last)

+-  				return;

+-  		}

+-  		//Getting the last non-empty

+-  		while(length(*(--last)) <= char_offset) { }

+-  		++last;

+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.

+-  		update_offset(first, last, char_offset, getchar, length);

+-  		

+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).

+-  		const unsigned max_size = bin_count;

+-  		const unsigned membin_count = bin_count + 1;

+-  		const unsigned max_bin = bin_count - 1;

+-  		unsigned cache_end;

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

+-  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);

+-  			

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

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

+-  			if(length(*current) <= char_offset) {

+-  				bin_sizes[bin_count]++;

+-  			}

+-  			else

+-  				bin_sizes[max_bin - getchar((*current), char_offset)]++;

+-  		}

+-  		//Assign the bin positions

+-  		bin_cache[cache_offset] = first;

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

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

+-  		

+-  		//Swap into place

+-  		RandomAccessIter nextbinstart = last;

+-  		//handling empty bins

+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);

+-  		RandomAccessIter lastFull = *local_bin;

+-  		RandomAccessIter * target_bin;

+-  		//Iterating over each element in the bin of empties

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

+-  			//empties belong in this bin

+-  			while(length(*current) > char_offset) {

+-  				target_bin = end_bin - getchar((*current), char_offset);

+-  				iter_swap(current, (*target_bin)++);

+-  			}

+-  		}

+-  		*local_bin = nextbinstart;

+-  		nextbinstart = first;

+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops

+-  		unsigned last_bin = max_bin;

+-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }

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

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

+-  			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 = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 

+-  					target_bin = end_bin - getchar((*current), char_offset))

+-  					iter_swap(current, (*target_bin)++);

+-  			}

+-  			*local_bin = nextbinstart;

+-  		}

+-  		bins[last_bin] = lastFull;

+-  		//Recursing

+-  		RandomAccessIter lastPos = first;

+-  		//Skip this loop for empties

+-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; 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_size)

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

+-  			else

+-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos

+-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);

+-  		}

+-  	}

+-

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

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);

+-  	}

+-

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

+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);

+-  	}

+-

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

+-  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);

+-  	}

+-

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

+-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);

+-  	}

+-

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

+-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>

+-  	inline void 

+-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)

+-  	{

+-  		std::vector<size_t> bin_sizes;

+-  		std::vector<RandomAccessIter> bin_cache;

+-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);

+-  	}

+-  }

+-

+-  //Allows character-type overloads

+-  template <class RandomAccessIter, class unsignedchar_type>

+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 

+-  {

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

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

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

+-  	else

+-  		detail::string_sort(first, last, *first, unused);

+-  }

+-

+-  //Top-level sorting call; wraps using default of unsigned char

+-  template <class RandomAccessIter>

+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 

+-  {

+-  	unsigned char unused = '\0';

+-  	string_sort(first, last, unused);

+-  }

+-

+-  //Allows character-type overloads

+-  template <class RandomAccessIter, class compare, class unsignedchar_type>

+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 

+-  {

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

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

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

+-  	else

+-  		detail::reverse_string_sort(first, last, *first, unused);

+-  }

+-

+-  //Top-level sorting call; wraps using default of unsigned char

+-  template <class RandomAccessIter, class compare>

+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 

+-  {

+-  	unsigned char unused = '\0';

+-  	reverse_string_sort(first, last, comp, unused);

+-  }

+-

+-  template <class RandomAccessIter, class get_char, class get_length>

+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 

+-  {

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

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

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

+-  	else {

+-  		//skipping past empties at the beginning, which allows us to get the character type 

+-  		//.empty() is not used so as not to require a user declaration of it

+-  		while(!length(*first)) {

+-  			if(++first == last)

+-  				return;

+-  		}

+-  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));

+-  	}

+-  }

+-

+-  template <class RandomAccessIter, class get_char, class get_length, class compare>

+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 

+-  {

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

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

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

+-  	else {

+-  		//skipping past empties at the beginning, which allows us to get the character type 

+-  		//.empty() is not used so as not to require a user declaration of it

+-  		while(!length(*first)) {

+-  			if(++first == last)

+-  				return;

+-  		}

+-  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));

+-  	}

+-  }

+-

+-  template <class RandomAccessIter, class get_char, class get_length, class compare>

+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 

+-  {

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

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

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

+-  	else {

+-  		//skipping past empties at the beginning, which allows us to get the character type 

+-  		//.empty() is not used so as not to require a user declaration of it

+-  		while(!length(*(--last))) {

+-  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order

+-  			if(first == last)

+-  				return;

+-  		}

+-  		//making last just after the end of the non-empty part of the array

+-  		++last;

+-  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));

+-  	}

+-  }

+-}

+-

+-#endif

++//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"
++
++#include <features.h>
++#if defined(__UCLIBC__)
++#undef getchar
++#endif
++
++
++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);
++  		}
++  		
++  		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
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
++  		}
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	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, 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]++;
++  		//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, comp);
++  		}
++  		
++  		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
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
++  		}
++  	}
++
++  	template <class RandomAccessIter, class cast_type, class data_type>
++  	inline void 
++  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	float_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;
++  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
++  	}
++  }
++
++  //float_sort with casting
++  //The cast_type must be equal in size to the data type, and must be a signed integer
++  template <class RandomAccessIter, class cast_type>
++  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::float_Sort(first, last, cVal, *first);
++  }
++
++  //float_sort with casting to an int
++  //Only use this with IEEE floating-point numbers
++  template <class RandomAccessIter>
++  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 
++  {
++  	int cVal = 0;
++  	float_sort_cast(first, last, cVal);
++  }
++
++  //float_sort with functors
++  template <class RandomAccessIter, class right_shift>
++  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::float_Sort(first, last, shift(*first, 0), *first, shift);
++  }
++
++  template <class RandomAccessIter, class right_shift, class compare>
++  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else
++  		detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
++  }
++
++  //------------------------------------------------- string_sort source ---------------------------------------------
++  namespace detail {
++  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
++  	template<class RandomAccessIter>
++  	inline void
++  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
++  	{
++  		unsigned nextOffset = char_offset;
++  		bool done = false;
++  		while(!done) {
++  			RandomAccessIter curr = first;
++  			do {
++  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
++  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
++  					done = true;
++  					break;
++  				}
++  			} while(++curr != finish);
++  			if(!done)
++  				++nextOffset;
++  		} 
++  		char_offset = nextOffset;
++  	}
++
++  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
++  	template<class RandomAccessIter, class get_char, class get_length>
++  	inline void
++  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
++  	{
++  		unsigned nextOffset = char_offset;
++  		bool done = false;
++  		while(!done) {
++  			RandomAccessIter curr = first;
++  			do {
++  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
++  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
++  					done = true;
++  					break;
++  				}
++  			} while(++curr != finish);
++  			if(!done)
++  				++nextOffset;
++  		} 
++  		char_offset = nextOffset;
++  	}
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class unsignedchar_type>
++  	struct offset_lessthan {
++  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(x.size(), y.size());
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
++  					return true;
++  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
++  					return false;
++  			}
++  			return x.size() < y.size();
++  		}
++  		unsigned fchar_offset;
++  	};
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class unsignedchar_type>
++  	struct offset_greaterthan {
++  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(x.size(), y.size());
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
++  					return true;
++  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
++  					return false;
++  			}
++  			return x.size() > y.size();
++  		}
++  		unsigned fchar_offset;
++  	};
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class get_char, class get_length>
++  	struct offset_char_lessthan {
++  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(length(x), length(y));
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(getchar(x, u) < getchar(y, u))
++  					return true;
++  				else if(getchar(y, u) < getchar(x, u))
++  					return false;
++  			}
++  			return length(x) < length(y);
++  		}
++  		unsigned fchar_offset;
++  		get_char getchar;
++  		get_length length;
++  	};
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while((*first).size() <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;(*finish).size() <= char_offset; --finish) { }
++  		++finish;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(first, finish, char_offset);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if((*current).size() <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while((*current).size() > char_offset) {
++  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u + 1];
++  			//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 + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
++  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)
++  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Sorts strings in reverse order, with empties at the end
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		RandomAccessIter curr = first;
++  		//Iterate to the end of the empties.  If all empty, return
++  		while((*curr).size() <= char_offset) {
++  			if(++curr == last)
++  				return;
++  		}
++  		//Getting the last non-empty
++  		while((*(--last)).size() <= char_offset) { }
++  		++last;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(curr, last, char_offset);
++  		RandomAccessIter * target_bin;
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		const unsigned max_bin = bin_count - 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
++  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if((*current).size() <= char_offset) {
++  				bin_sizes[bin_count]++;
++  			}
++  			else
++  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = last;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
++  		RandomAccessIter lastFull = *local_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while((*current).size() > char_offset) {
++  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		nextbinstart = first;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = max_bin;
++  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			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 = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
++  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = lastFull;
++  		//Recursing
++  		RandomAccessIter lastPos = first;
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; 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_size)
++  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
++  			else
++  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*first) <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;length(*finish) <= char_offset; --finish) { }
++  		++finish;
++  		update_offset(first, finish, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[getchar((*current), char_offset) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = bins + getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned ii = 0; ii < last_bin; ++ii) {
++  			local_bin = bins + ii;
++  			nextbinstart += bin_sizes[ii + 1];
++  			//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 + getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = bins + getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)
++  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
++  		}
++  	}
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*first) <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;length(*finish) <= char_offset; --finish) { }
++  		++finish;
++  		update_offset(first, finish, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[getchar((*current), char_offset) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = bins + getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u + 1];
++  			//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 + getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = bins + getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; 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_size)
++  				std::sort(lastPos, bin_cache[u], comp);
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
++  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
++  		}
++  	}
++
++  	//Sorts strings in reverse order, with empties at the end
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
++  	inline void 
++  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		RandomAccessIter curr = first;
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*curr) <= char_offset) {
++  			if(++curr == last)
++  				return;
++  		}
++  		//Getting the last non-empty
++  		while(length(*(--last)) <= char_offset) { }
++  		++last;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(first, last, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		const unsigned max_bin = bin_count - 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
++  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[bin_count]++;
++  			}
++  			else
++  				bin_sizes[max_bin - getchar((*current), char_offset)]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = last;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
++  		RandomAccessIter lastFull = *local_bin;
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = end_bin - getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		nextbinstart = first;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = max_bin;
++  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			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 = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = end_bin - getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = lastFull;
++  		//Recursing
++  		RandomAccessIter lastPos = first;
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; 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_size)
++  				std::sort(lastPos, bin_cache[u], comp);
++  			else
++  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
++  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
++  		}
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
++  	}
++  }
++
++  //Allows character-type overloads
++  template <class RandomAccessIter, class unsignedchar_type>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::string_sort(first, last, *first, unused);
++  }
++
++  //Top-level sorting call; wraps using default of unsigned char
++  template <class RandomAccessIter>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 
++  {
++  	unsigned char unused = '\0';
++  	string_sort(first, last, unused);
++  }
++
++  //Allows character-type overloads
++  template <class RandomAccessIter, class compare, class unsignedchar_type>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else
++  		detail::reverse_string_sort(first, last, *first, unused);
++  }
++
++  //Top-level sorting call; wraps using default of unsigned char
++  template <class RandomAccessIter, class compare>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 
++  {
++  	unsigned char unused = '\0';
++  	reverse_string_sort(first, last, comp, unused);
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*first)) {
++  			if(++first == last)
++  				return;
++  		}
++  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
++  	}
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length, class compare>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*first)) {
++  			if(++first == last)
++  				return;
++  		}
++  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
++  	}
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length, class compare>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*(--last))) {
++  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
++  			if(first == last)
++  				return;
++  		}
++  		//making last just after the end of the non-empty part of the array
++  		++last;
++  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
++  	}
++  }
++}
++
++#endif