1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487 |
|
/**
* The array module provides array manipulation routines in a manner that
* balances performance and flexibility. Operations are provided for sorting,
* and for processing both sorted and unsorted arrays.
*
* Copyright: Copyright (C) 2005-2006 Sean Kelly. All rights reserved.
* License: BSD style: $(LICENSE)
* Authors: Sean Kelly
*/
module tango.core.Array;
private import tango.core.Traits;
private import tango.stdc.stdlib : alloca, rand;
version( TangoDoc )
{
typedef int Num;
typedef int Elem;
typedef bool function( Elem ) Pred1E;
typedef bool function( Elem, Elem ) Pred2E;
typedef size_t function( size_t ) Oper1A;
}
private
{
struct IsEqual( T )
{
static bool opCall( T p1, T p2 )
{
// TODO: Fix this if/when opEquals is changed to return a bool.
static if( is( T == class ) || is( T == struct ) )
return (p1 == p2) != 0;
else
return p1 == p2;
}
}
struct IsLess( T )
{
static bool opCall( T p1, T p2 )
{
return p1 < p2;
}
}
struct RandOper()
{
static size_t opCall( size_t lim )
{
// NOTE: The use of 'max' here is intended to eliminate modulo bias
// in this routine.
size_t max = size_t.max - (size_t.max % lim);
size_t val;
do
{
static if( size_t.sizeof == 4 )
{
val = (((cast(size_t)rand()) << 16) & 0xffff0000u) |
(((cast(size_t)rand())) & 0x0000ffffu);
}
else // assume size_t.sizeof == 8
{
val = (((cast(size_t)rand()) << 48) & 0xffff000000000000uL) |
(((cast(size_t)rand()) << 32) & 0x0000ffff00000000uL) |
(((cast(size_t)rand()) << 16) & 0x00000000ffff0000uL) |
(((cast(size_t)rand())) & 0x000000000000ffffuL);
}
} while( val > max );
return val % lim;
}
}
template ElemTypeOf( T )
{
alias typeof(T[0]) ElemTypeOf;
}
}
////////////////////////////////////////////////////////////////////////////////
// Find
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t find( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t find( Elem[] buf, Elem[] pat, Pred2E pred = Pred2E.init );
}
else
{
template find_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
foreach( size_t pos, Elem cur; buf )
{
if( pred( cur, pat ) )
return pos;
}
return buf.length;
}
size_t fn( Elem[] buf, Elem[] pat, Pred pred = Pred.init )
{
if( buf.length == 0 ||
pat.length == 0 ||
buf.length < pat.length )
{
return buf.length;
}
size_t end = buf.length - pat.length + 1;
for( size_t pos = 0; pos < end; ++pos )
{
if( pred( buf[pos], pat[0] ) )
{
size_t mat = 0;
do
{
if( ++mat >= pat.length )
return pos - pat.length + 1;
if( ++pos >= buf.length )
return buf.length;
} while( pred( buf[pos], pat[mat] ) );
pos -= mat;
}
}
return buf.length;
}
}
template find( Buf, Pat )
{
size_t find( Buf buf, Pat pat )
{
return find_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template find( Buf, Pat, Pred )
{
size_t find( Buf buf, Pat pat, Pred pred )
{
return find_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
// find element
assert( find( "", 'a' ) == 0 );
assert( find( "abc", 'a' ) == 0 );
assert( find( "abc", 'b' ) == 1 );
assert( find( "abc", 'c' ) == 2 );
assert( find( "abc", 'd' ) == 3 );
// null parameters
assert( find( "", "" ) == 0 );
assert( find( "a", "" ) == 1 );
assert( find( "", "a" ) == 0 );
// exact match
assert( find( "abc", "abc" ) == 0 );
// simple substring match
assert( find( "abc", "a" ) == 0 );
assert( find( "abca", "a" ) == 0 );
assert( find( "abc", "b" ) == 1 );
assert( find( "abc", "c" ) == 2 );
assert( find( "abc", "d" ) == 3 );
// multi-char substring match
assert( find( "abc", "ab" ) == 0 );
assert( find( "abcab", "ab" ) == 0 );
assert( find( "abc", "bc" ) == 1 );
assert( find( "abc", "ac" ) == 3 );
assert( find( "abrabracadabra", "abracadabra" ) == 3 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Reverse Find
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LP)buf.length .. 0$(RB), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t rfind( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LP)buf.length .. 0$(RB), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t rfind( Elem[] buf, Elem[] pat, Pred2E pred = Pred2E.init );
}
else
{
template rfind_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
if( buf.length == 0 )
return buf.length;
size_t pos = buf.length;
do
{
if( pred( buf[--pos], pat ) )
return pos;
} while( pos > 0 );
return buf.length;
}
size_t fn( Elem[] buf, Elem[] pat, Pred pred = Pred.init )
{
if( buf.length == 0 ||
pat.length == 0 ||
buf.length < pat.length )
{
return buf.length;
}
size_t pos = buf.length - pat.length + 1;
do
{
if( pred( buf[--pos], pat[0] ) )
{
size_t mat = 0;
do
{
if( ++mat >= pat.length )
return pos - pat.length + 1;
if( ++pos >= buf.length )
return buf.length;
} while( pred( buf[pos], pat[mat] ) );
pos -= mat;
}
} while( pos > 0 );
return buf.length;
}
}
template rfind( Buf, Pat )
{
size_t rfind( Buf buf, Pat pat )
{
return rfind_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template rfind( Buf, Pat, Pred )
{
size_t rfind( Buf buf, Pat pat, Pred pred )
{
return rfind_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
// rfind element
assert( rfind( "", 'a' ) == 0 );
assert( rfind( "abc", 'a' ) == 0 );
assert( rfind( "abc", 'b' ) == 1 );
assert( rfind( "abc", 'c' ) == 2 );
assert( rfind( "abc", 'd' ) == 3 );
// null parameters
assert( rfind( "", "" ) == 0 );
assert( rfind( "a", "" ) == 1 );
assert( rfind( "", "a" ) == 0 );
// exact match
assert( rfind( "abc", "abc" ) == 0 );
// simple substring match
assert( rfind( "abc", "a" ) == 0 );
assert( rfind( "abca", "a" ) == 3 );
assert( rfind( "abc", "b" ) == 1 );
assert( rfind( "abc", "c" ) == 2 );
assert( rfind( "abc", "d" ) == 3 );
// multi-char substring match
assert( rfind( "abc", "ab" ) == 0 );
assert( rfind( "abcab", "ab" ) == 3 );
assert( rfind( "abc", "bc" ) == 1 );
assert( rfind( "abc", "ac" ) == 3 );
assert( rfind( "abracadabrabra", "abracadabra" ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// KMP Find
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* This function uses the KMP algorithm and offers O(M+N) performance but
* must allocate a temporary buffer of size pat.sizeof to do so. If it is
* available on the target system, alloca will be used for the allocation,
* otherwise a standard dynamic memory allocation will occur.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t kfind( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* This function uses the KMP algorithm and offers O(M+N) performance but
* must allocate a temporary buffer of size pat.sizeof to do so. If it is
* available on the target system, alloca will be used for the allocation,
* otherwise a standard dynamic memory allocation will occur.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t kfind( Elem[] buf, Elem[] pat, Pred2E pred = Pred2E.init );
}
else
{
template kfind_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
foreach( size_t pos, Elem cur; buf )
{
if( pred( cur, pat ) )
return pos;
}
return buf.length;
}
size_t fn( Elem[] buf, Elem[] pat, Pred pred = Pred.init )
{
if( buf.length == 0 ||
pat.length == 0 ||
buf.length < pat.length )
{
return buf.length;
}
static if( is( alloca ) ) // always false, alloca usage should be rethought
{
size_t[] func = (cast(size_t*) alloca( (pat.length + 1) * size_t.sizeof ))[0 .. pat.length + 1];
}
else
{
size_t[] func = new size_t[pat.length + 1];
scope( exit ) delete func; // force cleanup
}
func[0] = 0;
//
// building prefix-function
//
for( size_t m = 0, i = 1 ; i < pat.length ; ++i )
{
while( ( m > 0 ) && !pred( pat[m], pat[i] ) )
m = func[m - 1];
if( pred( pat[m], pat[i] ) )
++m;
func[i] = m;
}
//
// searching
//
for( size_t m = 0, i = 0; i < buf.length; ++i )
{
while( ( m > 0 ) && !pred( pat[m], buf[i] ) )
m = func[m - 1];
if( pred( pat[m], buf[i] ) )
{
++m;
if( m == pat.length )
{
return i - pat.length + 1;
}
}
}
return buf.length;
}
}
template kfind( Buf, Pat )
{
size_t kfind( Buf buf, Pat pat )
{
return kfind_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template kfind( Buf, Pat, Pred )
{
size_t kfind( Buf buf, Pat pat, Pred pred )
{
return kfind_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
// find element
assert( kfind( "", 'a' ) == 0 );
assert( kfind( "abc", 'a' ) == 0 );
assert( kfind( "abc", 'b' ) == 1 );
assert( kfind( "abc", 'c' ) == 2 );
assert( kfind( "abc", 'd' ) == 3 );
// null parameters
assert( kfind( "", "" ) == 0 );
assert( kfind( "a", "" ) == 1 );
assert( kfind( "", "a" ) == 0 );
// exact match
assert( kfind( "abc", "abc" ) == 0 );
// simple substring match
assert( kfind( "abc", "a" ) == 0 );
assert( kfind( "abca", "a" ) == 0 );
assert( kfind( "abc", "b" ) == 1 );
assert( kfind( "abc", "c" ) == 2 );
assert( kfind( "abc", "d" ) == 3 );
// multi-char substring match
assert( kfind( "abc", "ab" ) == 0 );
assert( kfind( "abcab", "ab" ) == 0 );
assert( kfind( "abc", "bc" ) == 1 );
assert( kfind( "abc", "ac" ) == 3 );
assert( kfind( "abrabracadabra", "abracadabra" ) == 3 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// KMP Reverse Find
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LP)buf.length .. 0$(RB), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* This function uses the KMP algorithm and offers O(M+N) performance but
* must allocate a temporary buffer of size pat.sizeof to do so. If it is
* available on the target system, alloca will be used for the allocation,
* otherwise a standard dynamic memory allocation will occur.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t krfind( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LP)buf.length .. 0$(RB), returning
* the index of the first element matching pat, or buf.length if no match
* was found. Comparisons will be performed using the supplied predicate
* or '==' if none is supplied.
*
* This function uses the KMP algorithm and offers O(M+N) performance but
* must allocate a temporary buffer of size pat.sizeof to do so. If it is
* available on the target system, alloca will be used for the allocation,
* otherwise a standard dynamic memory allocation will occur.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t krfind( Elem[] buf, Elem[] pat, Pred2E pred = Pred2E.init );
}
else
{
template krfind_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
if( buf.length == 0 )
return buf.length;
size_t pos = buf.length;
do
{
if( pred( buf[--pos], pat ) )
return pos;
} while( pos > 0 );
return buf.length;
}
size_t fn( Elem[] buf, Elem[] pat, Pred pred = Pred.init )
{
if( buf.length == 0 ||
pat.length == 0 ||
buf.length < pat.length )
{
return buf.length;
}
static if( is( alloca ) ) // always false, alloca usage should be rethought
{
size_t[] func = (cast(size_t*) alloca( (pat.length + 1) * size_t.sizeof ))[0 .. pat.length + 1];
}
else
{
size_t[] func = new size_t[pat.length + 1];
scope( exit ) delete func; // force cleanup
}
func[$ - 1] = 0;
//
// building prefix-function
//
for( size_t m = 0, i = pat.length - 1; i > 0; --i )
{
while( ( m > 0 ) && !pred( pat[length - m - 1], pat[i - 1] ) )
m = func[length - m];
if( pred( pat[length - m - 1], pat[i - 1] ) )
++m;
func[i - 1] = m;
}
//
// searching
//
size_t m = 0;
size_t i = buf.length;
do
{
--i;
while( ( m > 0 ) && !pred( pat[length - m - 1], buf[i] ) )
m = func[length - m - 1];
if( pred( pat[length - m - 1], buf[i] ) )
{
++m;
if ( m == pat.length )
{
return i;
}
}
} while( i > 0 );
return buf.length;
}
}
template krfind( Buf, Pat )
{
size_t krfind( Buf buf, Pat pat )
{
return krfind_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template krfind( Buf, Pat, Pred )
{
size_t krfind( Buf buf, Pat pat, Pred pred )
{
return krfind_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
// rfind element
assert( krfind( "", 'a' ) == 0 );
assert( krfind( "abc", 'a' ) == 0 );
assert( krfind( "abc", 'b' ) == 1 );
assert( krfind( "abc", 'c' ) == 2 );
assert( krfind( "abc", 'd' ) == 3 );
// null parameters
assert( krfind( "", "" ) == 0 );
assert( krfind( "a", "" ) == 1 );
assert( krfind( "", "a" ) == 0 );
// exact match
assert( krfind( "abc", "abc" ) == 0 );
// simple substring match
assert( krfind( "abc", "a" ) == 0 );
assert( krfind( "abca", "a" ) == 3 );
assert( krfind( "abc", "b" ) == 1 );
assert( krfind( "abc", "c" ) == 2 );
assert( krfind( "abc", "d" ) == 3 );
// multi-char substring match
assert( krfind( "abc", "ab" ) == 0 );
assert( krfind( "abcab", "ab" ) == 3 );
assert( krfind( "abc", "bc" ) == 1 );
assert( krfind( "abc", "ac" ) == 3 );
assert( krfind( "abracadabrabra", "abracadabra" ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Find-If
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element where pred returns true.
*
* Params:
* buf = The array to search.
* pred = The evaluation predicate, which should return true if the
* element is a valid match and false if not. This predicate
* may be any callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t findIf( Elem[] buf, Pred1E pred );
}
else
{
template findIf_( Elem, Pred )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred )
{
foreach( size_t pos, Elem cur; buf )
{
if( pred( cur ) )
return pos;
}
return buf.length;
}
}
template findIf( Buf, Pred )
{
size_t findIf( Buf buf, Pred pred )
{
return findIf_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( findIf( "bcecg", ( char c ) { return c == 'a'; } ) == 5 );
assert( findIf( "bcecg", ( char c ) { return c == 'b'; } ) == 0 );
assert( findIf( "bcecg", ( char c ) { return c == 'c'; } ) == 1 );
assert( findIf( "bcecg", ( char c ) { return c == 'd'; } ) == 5 );
assert( findIf( "bcecg", ( char c ) { return c == 'g'; } ) == 4 );
assert( findIf( "bcecg", ( char c ) { return c == 'h'; } ) == 5 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Reverse Find-If
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LP)buf.length .. 0$(RB), returning
* the index of the first element where pred returns true.
*
* Params:
* buf = The array to search.
* pred = The evaluation predicate, which should return true if the
* element is a valid match and false if not. This predicate
* may be any callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t rfindIf( Elem[] buf, Pred1E pred );
}
else
{
template rfindIf_( Elem, Pred )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred )
{
if( buf.length == 0 )
return buf.length;
size_t pos = buf.length;
do
{
if( pred( buf[--pos] ) )
return pos;
} while( pos > 0 );
return buf.length;
}
}
template rfindIf( Buf, Pred )
{
size_t rfindIf( Buf buf, Pred pred )
{
return rfindIf_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( rfindIf( "bcecg", ( char c ) { return c == 'a'; } ) == 5 );
assert( rfindIf( "bcecg", ( char c ) { return c == 'b'; } ) == 0 );
assert( rfindIf( "bcecg", ( char c ) { return c == 'c'; } ) == 3 );
assert( rfindIf( "bcecg", ( char c ) { return c == 'd'; } ) == 5 );
assert( rfindIf( "bcecg", ( char c ) { return c == 'g'; } ) == 4 );
assert( rfindIf( "bcecg", ( char c ) { return c == 'h'; } ) == 5 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Find Adjacent
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* the index of the first element that compares equal to the next element
* in the sequence. Comparisons will be performed using the supplied
* predicate or '==' if none is supplied.
*
* Params:
* buf = The array to scan.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t findAdj( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
}
else
{
template findAdj_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred = Pred.init )
{
if( buf.length < 2 )
return buf.length;
Elem sav = buf[0];
foreach( size_t pos, Elem cur; buf[1 .. $] )
{
if( pred( cur, sav ) )
return pos;
sav = cur;
}
return buf.length;
}
}
template findAdj( Buf )
{
size_t findAdj( Buf buf )
{
return findAdj_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template findAdj( Buf, Pred )
{
size_t findAdj( Buf buf, Pred pred )
{
return findAdj_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( findAdj( "aabcdef" ) == 0 );
assert( findAdj( "abcddef" ) == 3 );
assert( findAdj( "abcdeff" ) == 5 );
assert( findAdj( "abcdefg" ) == 7 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Contains
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* true if an element matching pat is found. Comparisons will be performed
* using the supplied predicate or '<' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* True if an element equivalent to pat is found, false if not.
*/
equals_t contains( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* true if a sequence matching pat is found. Comparisons will be performed
* using the supplied predicate or '<' if none is supplied.
*
* Params:
* buf = The array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* True if an element equivalent to pat is found, false if not.
*/
equals_t contains( Elem[] buf, Elem[] pat, Pred2E pred = Pred2E.init );
}
else
{
template contains( Buf, Pat )
{
equals_t contains( Buf buf, Pat pat )
{
return cast(equals_t)(find( buf, pat ) != buf.length);
}
}
template contains( Buf, Pat, Pred )
{
equals_t contains( Buf buf, Pat pat, Pred pred )
{
return cast(equals_t)(find( buf, pat, pred ) != buf.length);
}
}
debug( UnitTest )
{
unittest
{
// find element
assert( !contains( "", 'a' ) );
assert( contains( "abc", 'a' ) );
assert( contains( "abc", 'b' ) );
assert( contains( "abc", 'c' ) );
assert( !contains( "abc", 'd' ) );
// null parameters
assert( !contains( "", "" ) );
assert( !contains( "a", "" ) );
assert( !contains( "", "a" ) );
// exact match
assert( contains( "abc", "abc" ) );
// simple substring match
assert( contains( "abc", "a" ) );
assert( contains( "abca", "a" ) );
assert( contains( "abc", "b" ) );
assert( contains( "abc", "c" ) );
assert( !contains( "abc", "d" ) );
// multi-char substring match
assert( contains( "abc", "ab" ) );
assert( contains( "abcab", "ab" ) );
assert( contains( "abc", "bc" ) );
assert( !contains( "abc", "ac" ) );
assert( contains( "abrabracadabra", "abracadabra" ) );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Mismatch
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a parallel linear scan of bufA and bufB from $(LB)0 .. N$(RP)
* where N = min$(LP)bufA.length, bufB.length$(RP), returning the index of
* the first element in bufA which does not match the corresponding element
* in bufB or N if no mismatch occurs. Comparisons will be performed using
* the supplied predicate or '==' if none is supplied.
*
* Params:
* bufA = The array to evaluate.
* bufB = The array to match against.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first mismatch or N if the first N elements of bufA
* and bufB match, where N = min$(LP)bufA.length, bufB.length$(RP).
*/
size_t mismatch( Elem[] bufA, Elem[] bufB, Pred2E pred = Pred2E.init );
}
else
{
template mismatch_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] bufA, Elem[] bufB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
while( posA < bufA.length && posB < bufB.length )
{
if( !pred( bufB[posB], bufA[posA] ) )
break;
++posA, ++posB;
}
return posA;
}
}
template mismatch( BufA, BufB )
{
size_t mismatch( BufA bufA, BufB bufB )
{
return mismatch_!(ElemTypeOf!(BufA)).fn( bufA, bufB );
}
}
template mismatch( BufA, BufB, Pred )
{
size_t mismatch( BufA bufA, BufB bufB, Pred pred )
{
return mismatch_!(ElemTypeOf!(BufA), Pred).fn( bufA, bufB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( mismatch( "a", "abcdefg" ) == 1 );
assert( mismatch( "abcdefg", "a" ) == 1 );
assert( mismatch( "x", "abcdefg" ) == 0 );
assert( mismatch( "abcdefg", "x" ) == 0 );
assert( mismatch( "xbcdefg", "abcdefg" ) == 0 );
assert( mismatch( "abcdefg", "xbcdefg" ) == 0 );
assert( mismatch( "abcxefg", "abcdefg" ) == 3 );
assert( mismatch( "abcdefg", "abcxefg" ) == 3 );
assert( mismatch( "abcdefx", "abcdefg" ) == 6 );
assert( mismatch( "abcdefg", "abcdefx" ) == 6 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Count
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* a count of the number of elements matching pat. Comparisons will be
* performed using the supplied predicate or '==' if none is supplied.
*
* Params:
* buf = The array to scan.
* pat = The pattern to match.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The number of elements matching pat.
*/
size_t count( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
}
else
{
template count_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
size_t cnt = 0;
foreach( size_t pos, Elem cur; buf )
{
if( pred( cur, pat ) )
++cnt;
}
return cnt;
}
}
template count( Buf, Pat )
{
size_t count( Buf buf, Pat pat )
{
return count_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template count( Buf, Pat, Pred )
{
size_t count( Buf buf, Pat pat, Pred pred )
{
return count_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( count( "gbbbi", 'a' ) == 0 );
assert( count( "gbbbi", 'g' ) == 1 );
assert( count( "gbbbi", 'b' ) == 3 );
assert( count( "gbbbi", 'i' ) == 1 );
assert( count( "gbbbi", 'd' ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Count-If
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), returning
* a count of the number of elements where pred returns true.
*
* Params:
* buf = The array to scan.
* pred = The evaluation predicate, which should return true if the
* element is a valid match and false if not. This predicate
* may be any callable type.
*
* Returns:
* The number of elements where pred returns true.
*/
size_t countIf( Elem[] buf, Pred1E pred = Pred1E.init );
}
else
{
template countIf_( Elem, Pred )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred )
{
size_t cnt = 0;
foreach( size_t pos, Elem cur; buf )
{
if( pred( cur ) )
++cnt;
}
return cnt;
}
}
template countIf( Buf, Pred )
{
size_t countIf( Buf buf, Pred pred )
{
return countIf_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( countIf( "gbbbi", ( char c ) { return c == 'a'; } ) == 0 );
assert( countIf( "gbbbi", ( char c ) { return c == 'g'; } ) == 1 );
assert( countIf( "gbbbi", ( char c ) { return c == 'b'; } ) == 3 );
assert( countIf( "gbbbi", ( char c ) { return c == 'i'; } ) == 1 );
assert( countIf( "gbbbi", ( char c ) { return c == 'd'; } ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Replace
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), replacing
* occurrences of pat with val. Comparisons will be performed using the
* supplied predicate or '==' if none is supplied.
*
* Params:
* buf = The array to scan.
* pat = The pattern to match.
* val = The value to substitute.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The number of elements replaced.
*/
size_t replace( Elem[] buf, Elem pat, Elem val, Pred2E pred = Pred2E.init );
}
else
{
template replace_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Elem val, Pred pred = Pred.init )
{
size_t cnt = 0;
foreach( size_t pos, ref Elem cur; buf )
{
if( pred( cur, pat ) )
{
cur = val;
++cnt;
}
}
return cnt;
}
}
template replace( Buf, Elem )
{
size_t replace( Buf buf, Elem pat, Elem val )
{
return replace_!(ElemTypeOf!(Buf)).fn( buf, pat, val );
}
}
template replace( Buf, Elem, Pred )
{
size_t replace( Buf buf, Elem pat, Elem val, Pred pred )
{
return replace_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, val, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( replace( "gbbbi".dup, 'a', 'b' ) == 0 );
assert( replace( "gbbbi".dup, 'g', 'h' ) == 1 );
assert( replace( "gbbbi".dup, 'b', 'c' ) == 3 );
assert( replace( "gbbbi".dup, 'i', 'j' ) == 1 );
assert( replace( "gbbbi".dup, 'd', 'e' ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Replace-If
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), replacing
* elements where pred returns true with val.
*
* Params:
* buf = The array to scan.
* val = The value to substitute.
* pred = The evaluation predicate, which should return true if the
* element is a valid match and false if not. This predicate
* may be any callable type.
*
* Returns:
* The number of elements replaced.
*/
size_t replaceIf( Elem[] buf, Elem val, Pred2E pred = Pred2E.init );
}
else
{
template replaceIf_( Elem, Pred )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem val, Pred pred )
{
size_t cnt = 0;
foreach( size_t pos, ref Elem cur; buf )
{
if( pred( cur ) )
{
cur = val;
++cnt;
}
}
return cnt;
}
}
template replaceIf( Buf, Elem, Pred )
{
size_t replaceIf( Buf buf, Elem val, Pred pred )
{
return replaceIf_!(ElemTypeOf!(Buf), Pred).fn( buf, val, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( replaceIf( "gbbbi".dup, 'b', ( char c ) { return c == 'a'; } ) == 0 );
assert( replaceIf( "gbbbi".dup, 'h', ( char c ) { return c == 'g'; } ) == 1 );
assert( replaceIf( "gbbbi".dup, 'c', ( char c ) { return c == 'b'; } ) == 3 );
assert( replaceIf( "gbbbi".dup, 'j', ( char c ) { return c == 'i'; } ) == 1 );
assert( replaceIf( "gbbbi".dup, 'e', ( char c ) { return c == 'd'; } ) == 0 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Remove
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), moving all
* elements matching pat to the end of the sequence. The relative order of
* elements not matching pat will be preserved. Comparisons will be
* performed using the supplied predicate or '==' if none is supplied.
*
* Params:
* buf = The array to scan. This parameter is not marked 'ref'
* to allow temporary slices to be modified. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on the
* result of this operation, even though it may be viewed as a
* side-effect.
* pat = The pattern to match against.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The number of elements that do not match pat.
*/
size_t remove( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), moving all
* elements matching pat to the end of the sequence. The relative order of
* elements not matching pat will be preserved. Comparisons will be
* performed '=='.
*
* Params:
* buf = The array to scan. This parameter is not marked 'ref'
* to allow temporary slices to be modified. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on the
* result of this operation, even though it may be viewed as a
* side-effect.
* pat = The pattern to match against.
*
* Returns:
* The number of elements that do not match pat.
*/
size_t remove( Elem[] buf, Elem pat );
}
else
{
template remove_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
size_t cnt = 0;
for( size_t pos = 0, len = buf.length; pos < len; ++pos )
{
if( pred( buf[pos], pat ) )
++cnt;
else
exch( pos, pos - cnt );
}
return buf.length - cnt;
}
}
template remove( Buf, Pat )
{
size_t remove( Buf buf, Pat pat )
{
return remove_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template remove( Buf, Pat, Pred )
{
size_t remove( Buf buf, Pat pat, Pred pred )
{
return remove_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf, char pat, size_t num )
{
assert( remove( buf, pat ) == num );
foreach( pos, cur; buf )
{
assert( pos < num ? cur != pat : cur == pat );
}
}
test( "abcdefghij".dup, 'x', 10 );
test( "xabcdefghi".dup, 'x', 9 );
test( "abcdefghix".dup, 'x', 9 );
test( "abxxcdefgh".dup, 'x', 8 );
test( "xaxbcdxxex".dup, 'x', 5 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Remove-If
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), moving all
* elements that satisfy pred to the end of the sequence. The relative
* order of elements that do not satisfy pred will be preserved.
*
* Params:
* buf = The array to scan. This parameter is not marked 'ref'
* to allow temporary slices to be modified. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on the
* result of this operation, even though it may be viewed as a
* side-effect.
* pred = The evaluation predicate, which should return true if the
* element satisfies the condition and false if not. This
* predicate may be any callable type.
*
* Returns:
* The number of elements that do not satisfy pred.
*/
size_t removeIf( Elem[] buf, Pred1E pred );
}
else
{
template removeIf_( Elem, Pred )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
size_t cnt = 0;
for( size_t pos = 0, len = buf.length; pos < len; ++pos )
{
if( pred( buf[pos] ) )
++cnt;
else
exch( pos, pos - cnt );
}
return buf.length - cnt;
}
}
template removeIf( Buf, Pred )
{
size_t removeIf( Buf buf, Pred pred )
{
return removeIf_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf, bool delegate( char ) dg, size_t num )
{
assert( removeIf( buf, dg ) == num );
foreach( pos, cur; buf )
{
assert( pos < num ? !dg( cur ) : dg( cur ) );
}
}
test( "abcdefghij".dup, ( char c ) { return c == 'x'; }, 10 );
test( "xabcdefghi".dup, ( char c ) { return c == 'x'; }, 9 );
test( "abcdefghix".dup, ( char c ) { return c == 'x'; }, 9 );
test( "abxxcdefgh".dup, ( char c ) { return c == 'x'; }, 8 );
test( "xaxbcdxxex".dup, ( char c ) { return c == 'x'; }, 5 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Unique
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)0 .. buf.length$(RP), moving all
* but the first element of each consecutive group of duplicate elements to
* the end of the sequence. The relative order of all remaining elements
* will be preserved. Comparisons will be performed using the supplied
* predicate or '==' if none is supplied.
*
* Params:
* buf = The array to scan. This parameter is not marked 'ref'
* to allow temporary slices to be modified. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on the
* result of this operation, even though it may be viewed as a
* side-effect.
* pred = The evaluation predicate, which should return true if e1 is
* equal to e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The number of distinct sub-sequences in buf.
*/
size_t distinct( Elem[] buf, Pred2E pred = Pred2E.init );
}
else
{
template distinct_( Elem, Pred = IsEqual!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
if( buf.length < 2 )
return buf.length;
size_t cnt = 0;
Elem pat = buf[0];
for( size_t pos = 1, len = buf.length; pos < len; ++pos )
{
if( pred( buf[pos], pat ) )
++cnt;
else
{
pat = buf[pos];
exch( pos, pos - cnt );
}
}
return buf.length - cnt;
}
}
template distinct( Buf )
{
size_t distinct( Buf buf )
{
return distinct_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template distinct( Buf, Pred )
{
size_t distinct( Buf buf, Pred pred )
{
return distinct_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf, char[] pat )
{
assert( distinct( buf ) == pat.length );
foreach( pos, cur; pat )
{
assert( buf[pos] == cur );
}
}
test( "abcdefghij".dup, "abcdefghij" );
test( "aabcdefghi".dup, "abcdefghi" );
test( "bcdefghijj".dup, "bcdefghij" );
test( "abccdefghi".dup, "abcdefghi" );
test( "abccdddefg".dup, "abcdefg" );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Shuffle
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from $(LB)2 .. buf.length$(RP), exchanging
* each element with an element in the range $(LB)0 .. pos$(RP), where pos
* represents the current array position.
*
* Params:
* buf = The array to shuffle.
* oper = The randomize operation, which should return a number in the
* range $(LB)0 .. N$(RP) for any supplied value N. This routine
* may be any callable type.
*/
void shuffle( Elem[] buf, Oper1A oper = Oper1A.init );
}
else
{
template shuffle_( Elem, Oper )
{
static assert( isCallableType!(Oper) );
void fn( Elem[] buf, Oper oper )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
for( size_t pos = buf.length - 1; pos > 0; --pos )
{
exch( pos, oper( pos + 1 ) );
}
}
}
template shuffle( Buf, Oper = RandOper!() )
{
void shuffle( Buf buf, Oper oper = Oper.init )
{
return shuffle_!(ElemTypeOf!(Buf), Oper).fn( buf, oper );
}
}
debug( UnitTest )
{
unittest
{
char[] buf = "abcdefghijklmnopqrstuvwxyz";
char[] tmp = buf.dup;
assert( tmp == buf );
shuffle( tmp );
assert( tmp != buf );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Partition
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Partitions buf such that all elements that satisfy pred will be placed
* before the elements that do not satisfy pred. The algorithm is not
* required to be stable.
*
* Params:
* buf = The array to partition. This parameter is not marked 'ref'
* to allow temporary slices to be sorted. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on
* the result of this operation, even though it may be viewed
* as a side-effect.
* pred = The evaluation predicate, which should return true if the
* element satisfies the condition and false if not. This
* predicate may be any callable type.
*
* Returns:
* The number of elements that satisfy pred.
*/
size_t partition( Elem[] buf, Pred1E pred );
}
else
{
template partition_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
size_t fn( Elem[] buf, Pred pred )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
if( buf.length < 2 )
return 0;
size_t l = 0,
r = buf.length,
i = l,
j = r - 1;
while( true )
{
while( i < r && pred( buf[i] ) )
++i;
while( j > l && !pred( buf[j] ) )
--j;
if( i >= j )
break;
exch( i++, j-- );
}
return i;
}
}
template partition( Buf, Pred )
{
size_t partition( Buf buf, Pred pred )
{
return partition_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf, bool delegate( char ) dg, size_t num )
{
assert( partition( buf, dg ) == num );
for( size_t pos = 0; pos < buf.length; ++pos )
{
assert( pos < num ? dg( buf[pos] ) : !dg( buf[pos] ) );
}
}
test( "abcdefg".dup, ( char c ) { return c < 'a'; }, 0 );
test( "gfedcba".dup, ( char c ) { return c < 'a'; }, 0 );
test( "abcdefg".dup, ( char c ) { return c < 'h'; }, 7 );
test( "gfedcba".dup, ( char c ) { return c < 'h'; }, 7 );
test( "abcdefg".dup, ( char c ) { return c < 'd'; }, 3 );
test( "gfedcba".dup, ( char c ) { return c < 'd'; }, 3 );
test( "bbdaabc".dup, ( char c ) { return c < 'c'; }, 5 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Select
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Partitions buf with num - 1 as a pivot such that the first num elements
* will be less than or equal to the remaining elements in the array.
* Comparisons will be performed using the supplied predicate or '<' if
* none is supplied. The algorithm is not required to be stable.
*
* Params:
* buf = The array to partition. This parameter is not marked 'ref'
* to allow temporary slices to be sorted. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on
* the result of this operation, even though it may be viewed
* as a side-effect.
* num = The number of elements which are considered significant in
* this array, where num - 1 is the pivot around which partial
* sorting will occur. For example, if num is buf.length / 2
* then select will effectively partition the array around its
* median value, with the elements in the first half of the array
* evaluating as less than or equal to the elements in the second
* half.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the pivot point, which will be the lesser of num - 1 and
* buf.length.
*/
size_t select( Elem[] buf, Num num, Pred2E pred = Pred2E.init );
}
else
{
template select_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
size_t fn( Elem[] buf, size_t num, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
if( buf.length < 2 )
return buf.length;
size_t l = 0,
r = buf.length - 1,
k = num;
while( r > l )
{
size_t i = l,
j = r - 1;
Elem v = buf[r];
while( true )
{
while( i < r && pred( buf[i], v ) )
++i;
while( j > l && pred( v, buf[j] ) )
--j;
if( i >= j )
break;
exch( i++, j-- );
}
exch( i, r );
if( i >= k )
r = i - 1;
if( i <= k )
l = i + 1;
}
return num - 1;
}
}
template select( Buf, Num )
{
size_t select( Buf buf, Num num )
{
return select_!(ElemTypeOf!(Buf)).fn( buf, num );
}
}
template select( Buf, Num, Pred )
{
size_t select( Buf buf, Num num, Pred pred )
{
return select_!(ElemTypeOf!(Buf), Pred).fn( buf, num, pred );
}
}
debug( UnitTest )
{
unittest
{
char[] buf = "efedcaabca".dup;
size_t num = buf.length / 2;
size_t pos = select( buf, num );
assert( pos == num - 1 );
foreach( cur; buf[0 .. pos] )
assert( cur <= buf[pos] );
foreach( cur; buf[pos .. $] )
assert( cur >= buf[pos] );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Sort
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Sorts buf using the supplied predicate or '<' if none is supplied. The
* algorithm is not required to be stable. The current implementation is
* based on quicksort, but uses a three-way partitioning scheme to improve
* performance for ranges containing duplicate values (Bentley and McIlroy,
* 1993).
*
* Params:
* buf = The array to sort. This parameter is not marked 'ref' to
* allow temporary slices to be sorted. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on
* the result of this operation, even though it may be viewed
* as a side-effect.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*/
void sort( Elem, Pred2E = IsLess!(Elem) )( Elem[] buf, Pred2E pred = Pred2E.init );
}
else
{
template sort_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
void fn( Elem[] buf, Pred pred = Pred.init )
{
bool equiv( Elem p1, Elem p2 )
{
return !pred( p1, p2 ) && !pred( p2, p1 );
}
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
// NOTE: This algorithm operates on the inclusive range [l .. r].
void insertionSort( size_t l, size_t r )
{
for( size_t i = r; i > l; --i )
{
// swap the min element to buf[0] to act as a sentinel
if( pred( buf[i], buf[i - 1] ) )
exch( i, i - 1 );
}
for( size_t i = l + 2; i <= r; ++i )
{
size_t j = i;
Elem v = buf[i];
// don't need to test (j != l) because of the sentinel
while( pred( v, buf[j - 1] ) )
{
buf[j] = buf[j - 1];
j--;
}
buf[j] = v;
}
}
size_t medianOf( size_t l, size_t m, size_t r )
{
if( pred( buf[m], buf[l] ) )
{
if( pred( buf[r], buf[m] ) )
return m;
else
{
if( pred( buf[r], buf[l] ) )
return r;
else
return l;
}
}
else
{
if( pred( buf[r], buf[m] ) )
{
if( pred( buf[r], buf[l] ) )
return l;
else
return r;
}
else
return m;
}
}
// NOTE: This algorithm operates on the inclusive range [l .. r].
void quicksort( size_t l, size_t r, size_t d )
{
if( r <= l )
return;
// HEURISTIC: Use insertion sort for sufficiently small arrays.
enum { MIN_LENGTH = 80 }
if( r - l < MIN_LENGTH )
return insertionSort( l, r );
// HEURISTIC: If the recursion depth is too great, assume this
// is a worst-case array and fail to heap sort.
if( d-- == 0 )
{
makeHeap( buf[l .. r+1], pred );
sortHeap( buf[l .. r+1], pred );
return;
}
// HEURISTIC: Use the median-of-3 value as a pivot. Swap this
// into r so quicksort remains untouched.
exch( r, medianOf( l, l + (r - l) / 2, r ) );
// This implementation of quicksort improves upon the classic
// algorithm by partitioning the array into three parts, one
// each for keys smaller than, equal to, and larger than the
// partitioning element, v:
//
// |--less than v--|--equal to v--|--greater than v--[v]
// l j i r
//
// This approach sorts ranges containing duplicate elements
// more quickly. During processing, the following situation
// is maintained:
//
// |--equal--|--less--|--[###]--|--greater--|--equal--[v]
// l p i j q r
//
// Please note that this implementation varies from the typical
// algorithm by replacing the use of signed index values with
// unsigned values.
Elem v = buf[r];
size_t i = l,
j = r,
p = l,
q = r;
while( true )
{
while( pred( buf[i], v ) )
++i;
while( pred( v, buf[--j] ) )
if( j == l ) break;
if( i >= j )
break;
exch( i, j );
if( equiv( buf[i], v ) )
exch( p++, i );
if( equiv( v, buf[j] ) )
exch( --q, j );
++i;
}
exch( i, r );
if( p < i )
{
j = i - 1;
for( size_t k = l; k < p; k++, j-- )
exch( k, j );
quicksort( l, j, d );
}
if( ++i < q )
{
for( size_t k = r - 1; k >= q; k--, i++ )
exch( k, i );
quicksort( i, r, d );
}
}
size_t maxDepth( size_t x )
{
size_t d = 0;
do
{
++d;
x /= 2;
} while( x > 1 );
return d * 2; // same as "floor( log( x ) / log( 2 ) ) * 2"
}
if( buf.length > 1 )
{
quicksort( 0, buf.length - 1, maxDepth( buf.length ) );
}
}
}
template sort( Buf )
{
void sort( Buf buf )
{
return sort_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template sort( Buf, Pred )
{
void sort( Buf buf, Pred pred )
{
return sort_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf )
{
sort( buf );
char sav = buf[0];
foreach( cur; buf )
{
assert( cur >= sav );
sav = cur;
}
}
test( "mkcvalsidivjoaisjdvmzlksvdjioawmdsvmsdfefewv".dup );
test( "asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdf".dup );
test( "the quick brown fox jumped over the lazy dog".dup );
test( "abcdefghijklmnopqrstuvwxyz".dup );
test( "zyxwvutsrqponmlkjihgfedcba".dup );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Lower Bound
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a binary search of buf, returning the index of the first
* location where pat may be inserted without disrupting sort order. If
* the sort order of pat precedes all elements in buf then 0 will be
* returned. If the sort order of pat succeeds the largest element in buf
* then buf.length will be returned. Comparisons will be performed using
* the supplied predicate or '<' if none is supplied.
*
* Params:
* buf = The sorted array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t lbound( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
}
else
{
template lbound_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
size_t beg = 0,
end = buf.length,
mid = end / 2;
while( beg < end )
{
if( pred( buf[mid], pat ) )
beg = mid + 1;
else
end = mid;
mid = beg + ( end - beg ) / 2;
}
return mid;
}
}
template lbound( Buf, Pat )
{
size_t lbound( Buf buf, Pat pat )
{
return lbound_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template lbound( Buf, Pat, Pred )
{
size_t lbound( Buf buf, Pat pat, Pred pred )
{
return lbound_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( lbound( "bcefg", 'a' ) == 0 );
assert( lbound( "bcefg", 'h' ) == 5 );
assert( lbound( "bcefg", 'd' ) == 2 );
assert( lbound( "bcefg", 'e' ) == 2 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Upper Bound
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a binary search of buf, returning the index of the first
* location beyond where pat may be inserted without disrupting sort order.
* If the sort order of pat precedes all elements in buf then 0 will be
* returned. If the sort order of pat succeeds the largest element in buf
* then buf.length will be returned. Comparisons will be performed using
* the supplied predicate or '<' if none is supplied.
*
* Params:
* buf = The sorted array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* The index of the first match or buf.length if no match was found.
*/
size_t ubound( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
}
else
{
template ubound_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred) );
size_t fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
size_t beg = 0,
end = buf.length,
mid = end / 2;
while( beg < end )
{
if( !pred( pat, buf[mid] ) )
beg = mid + 1;
else
end = mid;
mid = beg + ( end - beg ) / 2;
}
return mid;
}
}
template ubound( Buf, Pat )
{
size_t ubound( Buf buf, Pat pat )
{
return ubound_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template ubound( Buf, Pat, Pred )
{
size_t ubound( Buf buf, Pat pat, Pred pred )
{
return ubound_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( ubound( "bcefg", 'a' ) == 0 );
assert( ubound( "bcefg", 'h' ) == 5 );
assert( ubound( "bcefg", 'd' ) == 2 );
assert( ubound( "bcefg", 'e' ) == 3 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Binary Search
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a binary search of buf, returning true if an element equivalent
* to pat is found. Comparisons will be performed using the supplied
* predicate or '<' if none is supplied.
*
* Params:
* buf = The sorted array to search.
* pat = The pattern to search for.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* True if an element equivalent to pat is found, false if not.
*/
bool bsearch( Elem[] buf, Elem pat, Pred2E pred = Pred2E.init );
}
else
{
template bsearch_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred) );
bool fn( Elem[] buf, Elem pat, Pred pred = Pred.init )
{
size_t pos = lbound( buf, pat, pred );
return pos < buf.length && !( pat < buf[pos] );
}
}
template bsearch( Buf, Pat )
{
bool bsearch( Buf buf, Pat pat )
{
return bsearch_!(ElemTypeOf!(Buf)).fn( buf, pat );
}
}
template bsearch( Buf, Pat, Pred )
{
bool bsearch( Buf buf, Pat pat, Pred pred )
{
return bsearch_!(ElemTypeOf!(Buf), Pred).fn( buf, pat, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( !bsearch( "bcefg", 'a' ) );
assert( bsearch( "bcefg", 'b' ) );
assert( bsearch( "bcefg", 'c' ) );
assert( !bsearch( "bcefg", 'd' ) );
assert( bsearch( "bcefg", 'e' ) );
assert( bsearch( "bcefg", 'f' ) );
assert( bsearch( "bcefg", 'g' ) );
assert( !bsearch( "bcefg", 'h' ) );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a parallel linear scan of setA and setB from $(LB)0 .. N$(RP)
* where N = min$(LP)setA.length, setB.length$(RP), returning true if setA
* includes all elements in setB and false if not. Both setA and setB are
* required to be sorted, and duplicates in setB require an equal number of
* duplicates in setA. Comparisons will be performed using the supplied
* predicate or '<' if none is supplied.
*
* Params:
* setA = The sorted array to evaluate.
* setB = The sorted array to match against.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* true if setA includes all elements in setB, false if not.
*/
bool includes( Elem[] setA, Elem[] setB, Pred2E pred = Pred2E.init );
}
else
{
template includes_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
bool fn( Elem[] setA, Elem[] setB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
while( posA < setA.length && posB < setB.length )
{
if( pred( setB[posB], setA[posA] ) )
return false;
else if( pred( setA[posA], setB[posB] ) )
++posA;
else
++posA, ++posB;
}
return posB == setB.length;
}
}
template includes( BufA, BufB )
{
bool includes( BufA setA, BufB setB )
{
return includes_!(ElemTypeOf!(BufA)).fn( setA, setB );
}
}
template includes( BufA, BufB, Pred )
{
bool includes( BufA setA, BufB setB, Pred pred )
{
return includes_!(ElemTypeOf!(BufA), Pred).fn( setA, setB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( includes( "abcdefg", "a" ) );
assert( includes( "abcdefg", "g" ) );
assert( includes( "abcdefg", "d" ) );
assert( includes( "abcdefg", "abcdefg" ) );
assert( includes( "aaaabbbcdddefgg", "abbbcdefg" ) );
assert( !includes( "abcdefg", "aaabcdefg" ) );
assert( !includes( "abcdefg", "abcdefggg" ) );
assert( !includes( "abbbcdefg", "abbbbcdefg" ) );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Union Of
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Computes the union of setA and setB as a set operation and returns the
* retult in a new sorted array. Both setA and setB are required to be
* sorted. If either setA or setB contain duplicates, the result will
* contain the larger number of duplicates from setA and setB. When an
* overlap occurs, entries will be copied from setA. Comparisons will be
* performed using the supplied predicate or '<' if none is supplied.
*
* Params:
* setA = The first sorted array to evaluate.
* setB = The second sorted array to evaluate.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* A new array containing the union of setA and setB.
*/
Elem[] unionOf( Elem[] setA, Elem[] setB, Pred2E pred = Pred2E.init );
}
else
{
template unionOf_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
Elem[] fn( Elem[] setA, Elem[] setB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
Elem[] setU;
while( posA < setA.length && posB < setB.length )
{
if( pred( setA[posA], setB[posB] ) )
setU ~= setA[posA++];
else if( pred( setB[posB], setA[posA] ) )
setU ~= setB[posB++];
else
setU ~= setA[posA++], posB++;
}
setU ~= setA[posA .. $];
setU ~= setB[posB .. $];
return setU;
}
}
template unionOf( BufA, BufB )
{
ElemTypeOf!(BufA)[] unionOf( BufA setA, BufB setB )
{
return unionOf_!(ElemTypeOf!(BufA)).fn( setA, setB );
}
}
template unionOf( BufA, BufB, Pred )
{
ElemTypeOf!(BufA)[] unionOf( BufA setA, BufB setB, Pred pred )
{
return unionOf_!(ElemTypeOf!(BufA), Pred).fn( setA, setB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( unionOf( "", "" ) == "" );
assert( unionOf( "abc", "def" ) == "abcdef" );
assert( unionOf( "abbbcd", "aadeefg" ) == "aabbbcdeefg" );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Intersection Of
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Computes the intersection of setA and setB as a set operation and
* returns the retult in a new sorted array. Both setA and setB are
* required to be sorted. If either setA or setB contain duplicates, the
* result will contain the smaller number of duplicates from setA and setB.
* All entries will be copied from setA. Comparisons will be performed
* using the supplied predicate or '<' if none is supplied.
*
* Params:
* setA = The first sorted array to evaluate.
* setB = The second sorted array to evaluate.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* A new array containing the intersection of setA and setB.
*/
Elem[] intersectionOf( Elem[] setA, Elem[] setB, Pred2E pred = Pred2E.init );
}
else
{
template intersectionOf_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
Elem[] fn( Elem[] setA, Elem[] setB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
Elem[] setI;
while( posA < setA.length && posB < setB.length )
{
if( pred( setA[posA], setB[posB] ) )
++posA;
else if( pred( setB[posB], setA[posA] ) )
++posB;
else
setI ~= setA[posA++], posB++;
}
return setI;
}
}
template intersectionOf( BufA, BufB )
{
ElemTypeOf!(BufA)[] intersectionOf( BufA setA, BufB setB )
{
return intersectionOf_!(ElemTypeOf!(BufA)).fn( setA, setB );
}
}
template intersectionOf( BufA, BufB, Pred )
{
ElemTypeOf!(BufA)[] intersectionOf( BufA setA, BufB setB, Pred pred )
{
return intersectionOf_!(ElemTypeOf!(BufA), Pred).fn( setA, setB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( intersectionOf( "", "" ) == "" );
assert( intersectionOf( "abc", "def" ) == "" );
assert( intersectionOf( "abbbcd", "aabdddeefg" ) == "abd" );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Missing From
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Returns a new array containing all elements in setA which are not
* present in setB. Both setA and setB are required to be sorted.
* Comparisons will be performed using the supplied predicate or '<'
* if none is supplied.
*
* Params:
* setA = The first sorted array to evaluate.
* setB = The second sorted array to evaluate.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* A new array containing the elements in setA that are not in setB.
*/
Elem[] missingFrom( Elem[] setA, Elem[] setB, Pred2E pred = Pred2E.init );
}
else
{
template missingFrom_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
Elem[] fn( Elem[] setA, Elem[] setB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
Elem[] setM;
while( posA < setA.length && posB < setB.length )
{
if( pred( setA[posA], setB[posB] ) )
setM ~= setA[posA++];
else if( pred( setB[posB], setA[posA] ) )
++posB;
else
++posA, ++posB;
}
setM ~= setA[posA .. $];
return setM;
}
}
template missingFrom( BufA, BufB )
{
ElemTypeOf!(BufA)[] missingFrom( BufA setA, BufB setB )
{
return missingFrom_!(ElemTypeOf!(BufA)).fn( setA, setB );
}
}
template missingFrom( BufA, BufB, Pred )
{
ElemTypeOf!(BufA)[] missingFrom( BufA setA, BufB setB, Pred pred )
{
return missingFrom_!(ElemTypeOf!(BufA), Pred).fn( setA, setB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( missingFrom( "", "" ) == "" );
assert( missingFrom( "", "abc" ) == "" );
assert( missingFrom( "abc", "" ) == "abc" );
assert( missingFrom( "abc", "abc" ) == "" );
assert( missingFrom( "abc", "def" ) == "abc" );
assert( missingFrom( "abbbcd", "abd" ) == "bbc" );
assert( missingFrom( "abcdef", "bc" ) == "adef" );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Difference Of
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Returns a new array containing all elements in setA which are not
* present in setB and the elements in setB which are not present in
* setA. Both setA and setB are required to be sorted. Comparisons
* will be performed using the supplied predicate or '<' if none is
* supplied.
*
* Params:
* setA = The first sorted array to evaluate.
* setB = The second sorted array to evaluate.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*
* Returns:
* A new array containing the elements in setA that are not in setB
* and the elements in setB that are not in setA.
*/
Elem[] differenceOf( Elem[] setA, Elem[] setB, Pred2E pred = Pred2E.init );
}
else
{
template differenceOf_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
Elem[] fn( Elem[] setA, Elem[] setB, Pred pred = Pred.init )
{
size_t posA = 0,
posB = 0;
Elem[] setD;
while( posA < setA.length && posB < setB.length )
{
if( pred( setA[posA], setB[posB] ) )
setD ~= setA[posA++];
else if( pred( setB[posB], setA[posA] ) )
setD ~= setB[posB++];
else
++posA, ++posB;
}
setD ~= setA[posA .. $];
setD ~= setB[posB .. $];
return setD;
}
}
template differenceOf( BufA, BufB )
{
ElemTypeOf!(BufA)[] differenceOf( BufA setA, BufB setB )
{
return differenceOf_!(ElemTypeOf!(BufA)).fn( setA, setB );
}
}
template differenceOf( BufA, BufB, Pred )
{
ElemTypeOf!(BufA)[] differenceOf( BufA setA, BufB setB, Pred pred )
{
return differenceOf_!(ElemTypeOf!(BufA), Pred).fn( setA, setB, pred );
}
}
debug( UnitTest )
{
unittest
{
assert( differenceOf( "", "" ) == "" );
assert( differenceOf( "", "abc" ) == "abc" );
assert( differenceOf( "abc", "" ) == "abc" );
assert( differenceOf( "abc", "abc" ) == "" );
assert( differenceOf( "abc", "def" ) == "abcdef" );
assert( differenceOf( "abbbcd", "abd" ) == "bbc" );
assert( differenceOf( "abd", "abbbcd" ) == "bbc" );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Make Heap
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Converts buf to a heap using the supplied predicate or '<' if none is
* supplied.
*
* Params:
* buf = The array to convert. This parameter is not marked 'ref' to
* allow temporary slices to be sorted. As buf is not resized in
* any way, omitting the 'ref' qualifier has no effect on the
* result of this operation, even though it may be viewed as a
* side-effect.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*/
void makeHeap( Elem[] buf, Pred2E pred = Pred2E.init );
}
else
{
template makeHeap_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
void fn( Elem[] buf, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
void fixDown( size_t pos, size_t end )
{
if( end <= pos )
return;
while( pos <= ( end - 1 ) / 2 )
{
size_t nxt = 2 * pos + 1;
if( nxt < end && pred( buf[nxt], buf[nxt + 1] ) )
++nxt;
if( !pred( buf[pos], buf[nxt] ) )
break;
exch( pos, nxt );
pos = nxt;
}
}
if( buf.length < 2 )
return;
size_t end = buf.length - 1,
pos = end / 2 + 2;
do
{
fixDown( --pos, end );
} while( pos > 0 );
}
}
template makeHeap( Buf )
{
void makeHeap( Buf buf )
{
return makeHeap_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template makeHeap( Buf, Pred )
{
void makeHeap( Buf buf, Pred pred )
{
return makeHeap_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void basic( char[] buf )
{
if( buf.length < 2 )
return;
size_t pos = 0,
end = buf.length - 1;
while( pos <= ( end - 1 ) / 2 )
{
assert( buf[pos] >= buf[2 * pos + 1] );
if( 2 * pos + 1 < end )
{
assert( buf[pos] >= buf[2 * pos + 2] );
}
++pos;
}
}
void test( char[] buf )
{
makeHeap( buf );
basic( buf );
}
test( "mkcvalsidivjoaisjdvmzlksvdjioawmdsvmsdfefewv".dup );
test( "asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdf".dup );
test( "the quick brown fox jumped over the lazy dog".dup );
test( "abcdefghijklmnopqrstuvwxyz".dup );
test( "zyxwvutsrqponmlkjihgfedcba".dup );
test( "ba".dup );
test( "a".dup );
test( "".dup );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Push Heap
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Adds val to buf by appending it and adjusting it up the heap.
*
* Params:
* buf = The heap to modify. This parameter is marked 'ref' because
* buf.length will be altered.
* val = The element to push onto buf.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*/
void pushHeap( ref Elem[] buf, Elem val, Pred2E pred = Pred2E.init );
}
else
{
template pushHeap_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
void fn( ref Elem[] buf, Elem val, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
void fixUp( size_t pos )
{
if( pos < 1 )
return;
size_t par = ( pos - 1 ) / 2;
while( pos > 0 && pred( buf[par], buf[pos] ) )
{
exch( par, pos );
pos = par;
par = ( pos - 1 ) / 2;
}
}
buf ~= val;
if( buf.length > 1 )
{
fixUp( buf.length - 1 );
}
}
}
template pushHeap( Buf, Val )
{
void pushHeap( ref Buf buf, Val val )
{
return pushHeap_!(ElemTypeOf!(Buf)).fn( buf, val );
}
}
template pushHeap( Buf, Val, Pred )
{
void pushHeap( ref Buf buf, Val val, Pred pred )
{
return pushHeap_!(ElemTypeOf!(Buf), Pred).fn( buf, val, pred );
}
}
debug( UnitTest )
{
unittest
{
void basic( char[] buf )
{
if( buf.length < 2 )
return;
size_t pos = 0,
end = buf.length - 1;
while( pos <= ( end - 1 ) / 2 )
{
assert( buf[pos] >= buf[2 * pos + 1] );
if( 2 * pos + 1 < end )
{
assert( buf[pos] >= buf[2 * pos + 2] );
}
++pos;
}
}
char[] buf;
foreach( cur; "abcdefghijklmnopqrstuvwxyz" )
{
pushHeap( buf, cur );
basic( buf );
}
buf.length = 0;
foreach( cur; "zyxwvutsrqponmlkjihgfedcba" )
{
pushHeap( buf, cur );
basic( buf );
}
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Pop Heap
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Removes the top element from buf by swapping it with the bottom element,
* adjusting it down the heap, and reducing the length of buf by one.
*
* Params:
* buf = The heap to modify. This parameter is marked 'ref' because
* buf.length will be altered.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*/
void popHeap( ref Elem[] buf, Pred2E pred = Pred2E.init );
}
else
{
template popHeap_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
void fn( ref Elem[] buf, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
void fixDown( size_t pos, size_t end )
{
if( end <= pos )
return;
while( pos <= ( end - 1 ) / 2 )
{
size_t nxt = 2 * pos + 1;
if( nxt < end && pred( buf[nxt], buf[nxt + 1] ) )
++nxt;
if( !pred( buf[pos], buf[nxt] ) )
break;
exch( pos, nxt );
pos = nxt;
}
}
if( buf.length > 1 )
{
exch( 0, buf.length - 1 );
fixDown( 0, buf.length - 2 );
}
if( buf.length > 0 )
{
buf.length = buf.length - 1;
}
}
}
template popHeap( Buf )
{
void popHeap( ref Buf buf )
{
return popHeap_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template popHeap( Buf, Pred )
{
void popHeap( ref Buf buf, Pred pred )
{
return popHeap_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf )
{
if( buf.length < 2 )
return;
size_t pos = 0,
end = buf.length - 1;
while( pos <= ( end - 1 ) / 2 )
{
assert( buf[pos] >= buf[2 * pos + 1] );
if( 2 * pos + 1 < end )
{
assert( buf[pos] >= buf[2 * pos + 2] );
}
++pos;
}
}
char[] buf = "zyxwvutsrqponmlkjihgfedcba".dup;
while( buf.length > 0 )
{
popHeap( buf );
test( buf );
}
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Sort Heap
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Sorts buf as a heap using the supplied predicate or '<' if none is
* supplied. Calling makeHeap and sortHeap on an array in succession
* has the effect of sorting the array using the heapsort algorithm.
*
* Params:
* buf = The heap to sort. This parameter is not marked 'ref' to
* allow temporary slices to be sorted. As buf is not resized
* in any way, omitting the 'ref' qualifier has no effect on
* the result of this operation, even though it may be viewed
* as a side-effect.
* pred = The evaluation predicate, which should return true if e1 is
* less than e2 and false if not. This predicate may be any
* callable type.
*/
void sortHeap( Elem[] buf, Pred2E pred = Pred2E.init );
}
else
{
template sortHeap_( Elem, Pred = IsLess!(Elem) )
{
static assert( isCallableType!(Pred ) );
void fn( Elem[] buf, Pred pred = Pred.init )
{
// NOTE: Indexes are passed instead of references because DMD does
// not inline the reference-based version.
void exch( size_t p1, size_t p2 )
{
Elem t = buf[p1];
buf[p1] = buf[p2];
buf[p2] = t;
}
void fixDown( size_t pos, size_t end )
{
if( end <= pos )
return;
while( pos <= ( end - 1 ) / 2 )
{
size_t nxt = 2 * pos + 1;
if( nxt < end && pred( buf[nxt], buf[nxt + 1] ) )
++nxt;
if( !pred( buf[pos], buf[nxt] ) )
break;
exch( pos, nxt );
pos = nxt;
}
}
if( buf.length < 2 )
return;
size_t pos = buf.length - 1;
while( pos > 0 )
{
exch( 0, pos );
fixDown( 0, --pos );
}
}
}
template sortHeap( Buf )
{
void sortHeap( Buf buf )
{
return sortHeap_!(ElemTypeOf!(Buf)).fn( buf );
}
}
template sortHeap( Buf, Pred )
{
void sortHeap( Buf buf, Pred pred )
{
return sortHeap_!(ElemTypeOf!(Buf), Pred).fn( buf, pred );
}
}
debug( UnitTest )
{
unittest
{
char[] buf = "zyxwvutsrqponmlkjihgfedcba".dup;
sortHeap( buf );
char sav = buf[0];
foreach( cur; buf )
{
assert( cur >= sav );
sav = cur;
}
}
}
}
|