123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672 |
|
/**
* 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 )
{
alias int Num;
alias int Elem;
alias int Elem2;
alias bool function( Elem ) Pred1E;
alias bool function( Elem, Elem ) Pred2E;
alias Elem2 function( Elem, Elem ) Map2E;
alias Elem function( Elem, Elem ) Reduce2E;
alias 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 [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 [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], 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], 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 [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 [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], 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], 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[$ - m - 1], pat[i - 1] ) )
m = func[$ - m];
if( pred( pat[$ - 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[$ - m - 1], buf[i] ) )
m = func[$ - m - 1];
if( pred( pat[$ - 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 [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], 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 [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, 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;
auto sav = cast(BaseTypeOf!(Elem))buf[0];
foreach( size_t pos, Elem cur; buf[1 .. $] )
{
if( pred( cur, sav ) )
return pos;
sav = cast(BaseTypeOf!(Elem))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 [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 [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 [0 .. N$(RP)
* where N = min(bufA.length, bufB.length), 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 [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 [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 [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 [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 [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 [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 [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 [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".dup );
test( "aabcdefghi".dup, "abcdefghi".dup );
test( "bcdefghijj".dup, "bcdefghij".dup );
test( "abccdefghi".dup, "abcdefghi".dup );
test( "abccdddefg".dup, "abcdefg".dup );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Shuffle
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from [2 .. buf.length$(RP), exchanging
* each element with an element in the range [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 [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".dup;
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 < 1 )
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 );
test( "f".dup, ( char c ) { return c == 'f'; }, 1 );
}
}
}
////////////////////////////////////////////////////////////////////////////////
// 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 [0 .. N$(RP)
* where N = min(setA.length, setB.length), 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;
}
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Map
////////////////////////////////////////////////////////////////////////////////
version (TangoDoc)
{
/** Apply a function to each element an array. The function's
* return values are stored in another array.
*
* Params:
* array = the array.
* func = the function to apply.
* buf = a buffer in which to store the results. This will be resized if it does not have sufficient space.
*
* Returns:
* an array (the same as the buffer passed in, if possible) where the
* ith element is the result of applying func to the ith element of the
* input array
*/
Elem2[] map(Elem[] array, Map2E func, Elem2[] buf = null);
}
else
{
template map(Func, Array)
{
ReturnTypeOf!(Func)[] map(Array array, Func func, ReturnTypeOf!(Func)[] buf = null)
{
if (buf.length < array.length)
{
buf.length = array.length;
}
foreach (i, a; array) buf[i] = func(a);
return buf;
}
}
debug (UnitTest)
{
unittest
{
auto arr = map([1, 17, 8, 12], (int i) { return i * 2L; });
assert(arr == [2L, 34L, 16L, 24L]);
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Reduce
////////////////////////////////////////////////////////////////////////////////
version (TangoDoc)
{
/** Reduce an array of elements to a single element, using a user-supplied
* reductor function.
*
* If the array is empty, return the default value for the element type.
*
* If the array contains only one element, return that element.
*
* Otherwise, the reductor function will be called on every member of the
* array and on every resulting element until there is only one element,
* which is then returned.
*
* Params:
* array = the array to reduce
* func = the reductor function
*
* Returns: the single element reduction
*/
Elem reduce(Elem[] array, Reduce2E func);
}
else
{
template reduce(Array, Func)
{
static assert(isCallableType!(Func));
ReturnTypeOf!(Func) reduce(Array array, Func func)
{
if (array.length == 0) return ReturnTypeOf!(Func).init;
auto e = array[0];
foreach (i, a; array)
{
if (i == 0) continue;
e = func(e, a);
}
return e;
}
}
debug (UnitTest)
{
unittest
{
auto result = reduce([1, 17, 8, 12], (int i, int j) { return i * j; });
assert(result == 1632);
}
}
}
////////////////////////////////////////////////////////////////////////////////
// Filter
////////////////////////////////////////////////////////////////////////////////
version( TangoDoc )
{
/**
* Performs a linear scan of buf from [0 .. buf.length$(RP), creating a new
* array with just the elements that satisfy pred. The relative order of
* elements will be preserved.
*
* Params:
* array = The array to scan.
* 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.
* buf = an optional buffer into which elements are filtered. This
* is the array that gets returned to you.
*
* Returns:
* A new array with just the elements from buf that satisfy pred.
*
* Notes:
* While most Array functions that take an output buffer size that buffer
* optimally, in this case, there is no way of knowing whether the output
* will be empty or the entire input array. If you have special knowledge
* in this regard, preallocating the output buffer will be advantageous.
*/
Elem[] filter(Elem[] array, Pred1E pred, Elem[] buf = null);
}
else
{
template filter(Array, Pred)
{
static assert(isCallableType!(Pred));
ParameterTupleOf!(Pred)[0][] filter(Array array, Pred pred, ParameterTupleOf!(Pred)[0][] buf = null)
{
// Unfortunately, we don't know our output size -- it could be empty or
// the length of the input array. So we won't try to do anything fancy
// with preallocation.
buf.length = 0;
foreach (i, e; array)
{
if (pred(e))
{
buf ~= e;
}
}
return buf;
}
}
debug( UnitTest )
{
unittest
{
void test( char[] buf, bool delegate( char ) dg, size_t num )
{
char[] r = filter( buf, dg );
assert( r.length == num );
size_t rpos = 0;
foreach( pos, cur; buf )
{
if ( dg( cur ) )
{
assert( r[rpos] == cur );
rpos++;
}
}
assert( rpos == num );
}
test( "abcdefghij".dup, ( char c ) { return c == 'x'; }, 0 );
test( "xabcdefghi".dup, ( char c ) { return c == 'x'; }, 1 );
test( "abcdefghix".dup, ( char c ) { return c == 'x'; }, 1 );
test( "abxxcdefgh".dup, ( char c ) { return c == 'x'; }, 2 );
test( "xaxbcdxxex".dup, ( char c ) { return c == 'x'; }, 5 );
}
}
}
|