1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385 |
- --- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp 2013-12-05 17:07:50.000000000 +0100
- +++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp 2014-02-05 09:52:11.000000000 +0100
- @@ -1,1688 +1,1694 @@
- -//Templated spread_sort library
- -
- -// Copyright Steven J. Ross 2001 - 2009.
- -// Distributed under the Boost Software License, Version 1.0.
- -// (See accompanying file LICENSE_1_0.txt or copy at
- -// http://www.boost.org/LICENSE_1_0.txt)
- -
- -// See http://www.boost.org/ for updates, documentation, and revision history.
- -
- -/*
- -Some improvements suggested by:
- -Phil Endecott and Frank Gennari
- -Cygwin fix provided by:
- -Scott McMurray
- -*/
- -
- -#ifndef BOOST_SPREAD_SORT_H
- -#define BOOST_SPREAD_SORT_H
- -#include <algorithm>
- -#include <cstring>
- -#include <vector>
- -#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
- -
- -namespace boost {
- - namespace detail {
- - //This only works on unsigned data types
- - template <typename T>
- - inline unsigned
- - rough_log_2_size(const T& input)
- - {
- - unsigned result = 0;
- - //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
- - while((input >> result) && (result < (8*sizeof(T)))) ++result;
- - return result;
- - }
- -
- - //Gets the maximum size which we'll call spread_sort on to control worst-case performance
- - //Maintains both a minimum size to recurse and a check of distribution size versus count
- - //This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
- - inline size_t
- - get_max_count(unsigned log_range, size_t count)
- - {
- - unsigned divisor = rough_log_2_size(count);
- - //Making sure the divisor is positive
- - if(divisor > LOG_MEAN_BIN_SIZE)
- - divisor -= LOG_MEAN_BIN_SIZE;
- - else
- - divisor = 1;
- - unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
- - //Don't try to bitshift more than the size of an element
- - if((8*sizeof(size_t)) <= relative_width)
- - relative_width = (8*sizeof(size_t)) - 1;
- - return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
- - (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width);
- - }
- -
- - //Find the minimum and maximum using <
- - template <class RandomAccessIter>
- - inline void
- - find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
- - {
- - min = max = current;
- - //Start from the second item, as max and min are initialized to the first
- - while(++current < last) {
- - if(*max < *current)
- - max = current;
- - else if(*current < *min)
- - min = current;
- - }
- - }
- -
- - //Uses a user-defined comparison operator to find minimum and maximum
- - template <class RandomAccessIter, class compare>
- - inline void
- - find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
- - {
- - min = max = current;
- - while(++current < last) {
- - if(comp(*max, *current))
- - max = current;
- - else if(comp(*current, *min))
- - min = current;
- - }
- - }
- -
- - //Gets a non-negative right bit shift to operate as a logarithmic divisor
- - inline int
- - get_log_divisor(size_t count, unsigned log_range)
- - {
- - int log_divisor;
- - //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
- - if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
- - log_divisor = 0;
- - else {
- - //otherwise divide the data into an optimized number of pieces
- - log_divisor += LOG_MEAN_BIN_SIZE;
- - if(log_divisor < 0)
- - log_divisor = 0;
- - //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
- - if((log_range - log_divisor) > MAX_SPLITS)
- - log_divisor = log_range - MAX_SPLITS;
- - }
- - return log_divisor;
- - }
- -
- - template <class RandomAccessIter>
- - inline RandomAccessIter *
- - size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
- - {
- - //Assure space for the size of each bin, followed by initializing sizes
- - if(bin_count > bin_sizes.size())
- - bin_sizes.resize(bin_count);
- - for(size_t u = 0; u < bin_count; u++)
- - bin_sizes[u] = 0;
- - //Make sure there is space for the bins
- - cache_end = cache_offset + bin_count;
- - if(cache_end > bin_cache.size())
- - bin_cache.resize(cache_end);
- - return &(bin_cache[cache_offset]);
- - }
- -
- - //Implementation for recursive integer sorting
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void
- - spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes)
- - {
- - //This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
- - //If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
- - RandomAccessIter max, min;
- - find_extremes(first, last, max, min);
- - //max and min will be the same (the first item) iff all values are equivalent
- - if(max == min)
- - return;
- - RandomAccessIter * target_bin;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
- - div_type div_min = *min >> log_divisor;
- - div_type div_max = *max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin; this takes roughly 10% of runtime
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[(*(current++) >> log_divisor) - div_min]++;
- - //Assign the bin positions
- - bins[0] = first;
- - for(unsigned u = 0; u < bin_count - 1; u++)
- - bins[u + 1] = bins[u] + bin_sizes[u];
- -
- - //Swap into place
- - //This dominates runtime, mostly in the swap and bin lookups
- - RandomAccessIter nextbinstart = first;
- - for(unsigned u = 0; u < bin_count - 1; ++u) {
- - RandomAccessIter * local_bin = bins + u;
- - nextbinstart += bin_sizes[u];
- - //Iterating over each element in this bin
- - for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
- - //Swapping elements in current into place until the correct element has been swapped in
- - for(target_bin = (bins + ((*current >> log_divisor) - div_min)); target_bin != local_bin;
- - target_bin = bins + ((*current >> log_divisor) - div_min)) {
- - //3-way swap; this is about 1% faster than a 2-way swap with integers
- - //The main advantage is less copies are involved per item put in the correct place
- - data_type tmp;
- - RandomAccessIter b = (*target_bin)++;
- - RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
- - if (b_bin != local_bin) {
- - RandomAccessIter c = (*b_bin)++;
- - tmp = *c;
- - *c = *b;
- - }
- - else
- - tmp = *b;
- - *b = *current;
- - *current = tmp;
- - }
- - }
- - *local_bin = nextbinstart;
- - }
- - bins[bin_count - 1] = last;
- -
- - //If we've bucketsorted, the array is sorted and we should skip recursion
- - if(!log_divisor)
- - return;
- -
- - //Recursing; log_divisor is the remaining range
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
- - size_t count = bin_cache[u] - lastPos;
- - //don't sort unless there are at least two items to compare
- - if(count < 2)
- - continue;
- - //using std::sort if its worst-case is better
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[u]);
- - else
- - spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
- - }
- - }
- -
- - //Generic bitshift-based 3-way swapping code
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
- - , const unsigned log_divisor, const div_type div_min)
- - {
- - RandomAccessIter * local_bin = bins + ii;
- - for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
- - for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin;
- - target_bin = bins + (shift(*current, log_divisor) - div_min)) {
- - data_type tmp;
- - RandomAccessIter b = (*target_bin)++;
- - RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
- - //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
- - if (b_bin != local_bin) {
- - RandomAccessIter c = (*b_bin)++;
- - tmp = *c;
- - *c = *b;
- - }
- - //Note: we could increment current once the swap is done in this case, but that seems to impair performance
- - else
- - tmp = *b;
- - *b = *current;
- - *current = tmp;
- - }
- - }
- - *local_bin = nextbinstart;
- - }
- -
- - //Standard swapping wrapper for ascending values
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
- - , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
- - {
- - nextbinstart += bin_sizes[ii];
- - inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
- - }
- -
- - //Functor implementation for recursive sorting
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
- - inline void
- - spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
- - {
- - RandomAccessIter max, min;
- - find_extremes(first, last, max, min, comp);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
- - div_type div_min = shift(*min, log_divisor);
- - div_type div_max = shift(*max, log_divisor);
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[shift(*(current++), log_divisor) - div_min]++;
- - bins[0] = first;
- - for(unsigned u = 0; u < bin_count - 1; u++)
- - bins[u + 1] = bins[u] + bin_sizes[u];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - for(unsigned u = 0; u < bin_count - 1; ++u)
- - swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
- - bins[bin_count - 1] = last;
- -
- - //If we've bucketsorted, the array is sorted and we should skip recursion
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
- - size_t count = bin_cache[u] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[u], comp);
- - else
- - spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
- - }
- - }
- -
- - //Functor implementation for recursive sorting with only Shift overridden
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void
- - spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes, right_shift shift)
- - {
- - RandomAccessIter max, min;
- - find_extremes(first, last, max, min);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
- - div_type div_min = shift(*min, log_divisor);
- - div_type div_max = shift(*max, log_divisor);
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[shift(*(current++), log_divisor) - div_min]++;
- - bins[0] = first;
- - for(unsigned u = 0; u < bin_count - 1; u++)
- - bins[u + 1] = bins[u] + bin_sizes[u];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - for(unsigned ii = 0; ii < bin_count - 1; ++ii)
- - swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
- - bins[bin_count - 1] = last;
- -
- - //If we've bucketsorted, the array is sorted and we should skip recursion
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
- - size_t count = bin_cache[u] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[u]);
- - else
- - spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
- - }
- - }
- -
- - //Holds the bin vector and makes the initial recursive call
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void
- - spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
- - {
- - std::vector<size_t> bin_sizes;
- - std::vector<RandomAccessIter> bin_cache;
- - spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
- - }
- -
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
- - inline void
- - spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
- - {
- - std::vector<size_t> bin_sizes;
- - std::vector<RandomAccessIter> bin_cache;
- - spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
- - }
- -
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void
- - spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
- - {
- - std::vector<size_t> bin_sizes;
- - std::vector<RandomAccessIter> bin_cache;
- - spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
- - }
- - }
- -
- - //Top-level sorting call for integers
- - template <class RandomAccessIter>
- - inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
- - {
- - //Don't sort if it's too small to optimize
- - if(last - first < detail::MIN_SORT_SIZE)
- - std::sort(first, last);
- - else
- - detail::spread_sort(first, last, *first >> 0, *first);
- - }
- -
- - //integer_sort with functors
- - template <class RandomAccessIter, class right_shift, class compare>
- - inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
- - right_shift shift, compare comp) {
- - if(last - first < detail::MIN_SORT_SIZE)
- - std::sort(first, last, comp);
- - else
- - detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
- - }
- -
- - //integer_sort with right_shift functor
- - template <class RandomAccessIter, class right_shift>
- - inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
- - right_shift shift) {
- - if(last - first < detail::MIN_SORT_SIZE)
- - std::sort(first, last);
- - else
- - detail::spread_sort(first, last, shift(*first, 0), *first, shift);
- - }
- -
- - //------------------------------------------------------ float_sort source --------------------------------------
- - //Casts a RandomAccessIter to the specified data type
- - template<class cast_type, class RandomAccessIter>
- - inline cast_type
- - cast_float_iter(const RandomAccessIter & floatiter)
- - {
- - cast_type result;
- - std::memcpy(&result, &(*floatiter), sizeof(cast_type));
- - return result;
- - }
- -
- - //Casts a data element to the specified datinner_float_a type
- - template<class data_type, class cast_type>
- - inline cast_type
- - mem_cast(const data_type & data)
- - {
- - cast_type result;
- - std::memcpy(&result, &data, sizeof(cast_type));
- - return result;
- - }
- -
- - namespace detail {
- - template <class RandomAccessIter, class div_type, class right_shift>
- - inline void
- - find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
- - {
- - min = max = shift(*current, 0);
- - while(++current < last) {
- - div_type value = shift(*current, 0);
- - if(max < value)
- - max = value;
- - else if(value < min)
- - min = value;
- - }
- - }
- -
- - //Specialized swap loops for floating-point casting
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
- - , const unsigned log_divisor, const div_type div_min)
- - {
- - RandomAccessIter * local_bin = bins + ii;
- - for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
- - for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin;
- - target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
- - data_type tmp;
- - RandomAccessIter b = (*target_bin)++;
- - RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
- - //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
- - if (b_bin != local_bin) {
- - RandomAccessIter c = (*b_bin)++;
- - tmp = *c;
- - *c = *b;
- - }
- - else
- - tmp = *b;
- - *b = *current;
- - *current = tmp;
- - }
- - }
- - *local_bin = nextbinstart;
- - }
- -
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
- - , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
- - {
- - nextbinstart += bin_sizes[ii];
- - inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
- - }
- -
- - template <class RandomAccessIter, class cast_type>
- - inline void
- - find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
- - {
- - min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
- - while(++current < last) {
- - cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
- - if(max < value)
- - max = value;
- - else if(value < min)
- - min = value;
- - }
- - }
- -
- - //Special-case sorting of positive floats with casting instead of a right_shift
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void
- - positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
- - bins[0] = first;
- - for(unsigned u = 0; u < bin_count - 1; u++)
- - bins[u + 1] = bins[u] + bin_sizes[u];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - for(unsigned u = 0; u < bin_count - 1; ++u)
- - float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
- - bins[bin_count - 1] = last;
- -
- - //Return if we've completed bucketsorting
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
- - size_t count = bin_cache[u] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[u]);
- - else
- - positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
- - }
- - }
- -
- - //Sorting negative_ float_s
- - //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void
- - negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
- - bins[bin_count - 1] = first;
- - for(int ii = bin_count - 2; ii >= 0; --ii)
- - bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - //The last bin will always have the correct elements in it
- - for(int ii = bin_count - 1; ii > 0; --ii)
- - float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
- - //Since we don't process the last bin, we need to update its end position
- - bin_cache[cache_offset] = last;
- -
- - //Return if we've completed bucketsorting
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
- - size_t count = bin_cache[ii] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[ii]);
- - else
- - negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
- - }
- - }
- -
- - //Sorting negative_ float_s
- - //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void
- - negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes, right_shift shift)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min, shift);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[shift(*(current++), log_divisor) - div_min]++;
- - bins[bin_count - 1] = first;
- - for(int ii = bin_count - 2; ii >= 0; --ii)
- - bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - //The last bin will always have the correct elements in it
- - for(int ii = bin_count - 1; ii > 0; --ii)
- - swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
- - //Since we don't process the last bin, we need to update its end position
- - bin_cache[cache_offset] = last;
- -
- - //Return if we've completed bucketsorting
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
- - size_t count = bin_cache[ii] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[ii]);
- - else
- - negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
- - }
- - }
- -
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
- - inline void
- - negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min, shift);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[shift(*(current++), log_divisor) - div_min]++;
- - bins[bin_count - 1] = first;
- - for(int ii = bin_count - 2; ii >= 0; --ii)
- - bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - //The last bin will always have the correct elements in it
- - for(int ii = bin_count - 1; ii > 0; --ii)
- - swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
- - //Since we don't process the last bin, we need to update its end position
- - bin_cache[cache_offset] = last;
- -
- - //Return if we've completed bucketsorting
- - if(!log_divisor)
- - return;
- -
- - //Recursing
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
- - size_t count = bin_cache[ii] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[ii], comp);
- - else
- - negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
- - }
- - }
- -
- - //Casting special-case for floating-point sorting
- - template <class RandomAccessIter, class div_type, class data_type>
- - inline void
- - float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
- - //The index of the first positive bin
- - div_type first_positive = (div_min < 0) ? -div_min : 0;
- - //Resetting if all bins are negative
- - if(cache_offset + first_positive > cache_end)
- - first_positive = cache_end - cache_offset;
- - //Reversing the order of the negative bins
- - //Note that because of the negative/positive ordering direction flip
- - //We can not depend upon bin order and positions matching up
- - //so bin_sizes must be reused to contain the end of the bin
- - if(first_positive > 0) {
- - bins[first_positive - 1] = first;
- - for(int ii = first_positive - 2; ii >= 0; --ii) {
- - bins[ii] = first + bin_sizes[ii + 1];
- - bin_sizes[ii] += bin_sizes[ii + 1];
- - }
- - //Handling positives following negatives
- - if((unsigned)first_positive < bin_count) {
- - bins[first_positive] = first + bin_sizes[0];
- - bin_sizes[first_positive] += bin_sizes[0];
- - }
- - }
- - else
- - bins[0] = first;
- - for(unsigned u = first_positive; u < bin_count - 1; u++) {
- - bins[u + 1] = first + bin_sizes[u];
- - bin_sizes[u + 1] += bin_sizes[u];
- - }
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - for(unsigned u = 0; u < bin_count; ++u) {
- - nextbinstart = first + bin_sizes[u];
- - inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
- - }
- -
- - if(!log_divisor)
- - return;
- -
- - //Handling negative values first
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
- - size_t count = bin_cache[ii] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[ii]);
- - //sort negative values using reversed-bin spread_sort
- - else
- - negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
- - }
- -
- - for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
- - size_t count = bin_cache[u] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[u]);
- - //sort positive values using normal spread_sort
- - else
- - positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
- - }
- - }
- -
- - //Functor implementation for recursive sorting
- - template <class RandomAccessIter, class div_type, class data_type, class right_shift>
- - inline void
- - float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
- - , std::vector<size_t> &bin_sizes, right_shift shift)
- - {
- - div_type max, min;
- - find_extremes(first, last, max, min, shift);
- - if(max == min)
- - return;
- - unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
- - div_type div_min = min >> log_divisor;
- - div_type div_max = max >> log_divisor;
- - unsigned bin_count = div_max - div_min + 1;
- - unsigned cache_end;
- - RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- -
- - //Calculating the size of each bin
- - for (RandomAccessIter current = first; current != last;)
- - bin_sizes[shift(*(current++), log_divisor) - div_min]++;
- - //The index of the first positive bin
- - div_type first_positive = (div_min < 0) ? -div_min : 0;
- - //Resetting if all bins are negative
- - if(cache_offset + first_positive > cache_end)
- - first_positive = cache_end - cache_offset;
- - //Reversing the order of the negative bins
- - //Note that because of the negative/positive ordering direction flip
- - //We can not depend upon bin order and positions matching up
- - //so bin_sizes must be reused to contain the end of the bin
- - if(first_positive > 0) {
- - bins[first_positive - 1] = first;
- - for(int ii = first_positive - 2; ii >= 0; --ii) {
- - bins[ii] = first + bin_sizes[ii + 1];
- - bin_sizes[ii] += bin_sizes[ii + 1];
- - }
- - //Handling positives following negatives
- - if((unsigned)first_positive < bin_count) {
- - bins[first_positive] = first + bin_sizes[0];
- - bin_sizes[first_positive] += bin_sizes[0];
- - }
- - }
- - else
- - bins[0] = first;
- - for(unsigned u = first_positive; u < bin_count - 1; u++) {
- - bins[u + 1] = first + bin_sizes[u];
- - bin_sizes[u + 1] += bin_sizes[u];
- - }
- -
- - //Swap into place
- - RandomAccessIter nextbinstart = first;
- - for(unsigned u = 0; u < bin_count; ++u) {
- - nextbinstart = first + bin_sizes[u];
- - inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
- - }
- -
- - //Return if we've completed bucketsorting
- - if(!log_divisor)
- - return;
- -
- - //Handling negative values first
- - size_t max_count = get_max_count(log_divisor, last - first);
- - RandomAccessIter lastPos = first;
- - for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
- - size_t count = bin_cache[ii] - lastPos;
- - if(count < 2)
- - continue;
- - if(count < max_count)
- - std::sort(lastPos, bin_cache[ii]);
- - //sort negative values using reversed-bin spread_sort
- - else
- - negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
- - }
- -
- - 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
|