123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651
//================================================================ /** * @packageDocumentation * @module std   *///================================================================import { IForwardIterator } from "../iterator/IForwardIterator";import { IPointer } from "../functional/IPointer";import { Pair } from "../utility/Pair";
import { BinaryPredicator } from "../internal/functional/BinaryPredicator";import { UnaryPredicator } from "../internal/functional/UnaryPredicator";import { equal_to, less } from "../functional/comparators";import { advance, distance } from "../iterator/global";


/* =========================================================    ITERATIONS (NON-MODIFYING SEQUENCE)        - FOR_EACH        - AGGREGATE CONDITIONS        - FINDERS        - COUNTERS============================================================    FOR_EACH--------------------------------------------------------- *//** * Apply a function to elements in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param fn The function to apply. *  * @return The function *fn* itself. */export function for_each<        InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>,        Func extends (val: IPointer.ValueType<InputIterator>) => any>    (first: InputIterator, last: InputIterator, fn: Func): Func{    for (let it = first; !it.equals(last); it = it.next())        fn(it.value);
    return fn;}
/** * Apply a function to elements in steps. *  * @param first Input iteartor of the starting position. * @param n Steps to maximum advance. * @param fn The function to apply. *  * @return Iterator advanced from *first* for *n* steps. */export function for_each_n<        InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>,        Func extends (val: IPointer.ValueType<InputIterator>) => any>    (first: InputIterator, n: number, fn: Func): InputIterator{    for (let i: number = 0; i < n; ++i)    {        fn(first.value);        first = first.next();    }    return first;}
/* ---------------------------------------------------------    AGGREGATE CONDITIONS--------------------------------------------------------- *//** * Test whether all elements meet a specific condition. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return Whether the *pred* returns always `true` for all elements. */export function all_of<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator,         last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): boolean{    for (let it = first; !it.equals(last); it = it.next())        if (pred(it.value) === false)            return false;
    return true;}
/** * Test whether any element meets a specific condition. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return Whether the *pred* returns at least a `true` for all elements. */export function any_of<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator,         last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): boolean{    for (let it = first; !it.equals(last); it = it.next())        if (pred(it.value) === true)            return true;
    return false;}
/** * Test whether any element doesn't meet a specific condition. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return Whether the *pred* doesn't return `true` for all elements. */export function none_of<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator,         last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): boolean{    return !any_of(first, last, pred);}
/** * Test whether two ranges are equal. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return Whether two ranges are equal. */export function equal<        InputIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator1>, InputIterator1>>,        InputIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator1>, InputIterator2>>>    (        first1: InputIterator1, last1: InputIterator1,         first2: InputIterator2    ): boolean;
/** * Test whether two ranges are equal. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return Whether two ranges are equal. */export function equal<        InputIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator1>, InputIterator1>>,        InputIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator2>, InputIterator2>>>    (        first1: InputIterator1, last1: InputIterator1,         first2: InputIterator2,        pred: BinaryPredicator<IPointer.ValueType<InputIterator1>, IPointer.ValueType<InputIterator2>>    ): boolean;
export function equal<        InputIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator1>, InputIterator1>>,        InputIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator2>, InputIterator2>>>    (        first1: InputIterator1, last1: InputIterator1,         first2: InputIterator2,        pred: BinaryPredicator<IPointer.ValueType<InputIterator1>, IPointer.ValueType<InputIterator2>> = equal_to as any    ): boolean{    while (!first1.equals(last1))        if (!pred(first1.value, first2.value))            return false;        else        {            first1 = first1.next();            first2 = first2.next();        }    return true;}
/** * Compare lexicographically. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param last2 Input iterator of the last position of the 2nd range. * @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Default is {@link less}. *  * @return Whether the 1st range precedes the 2nd. */export function lexicographical_compare<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2,        comp: BinaryPredicator<IPointer.ValueType<Iterator1>> = less    ): boolean{    while (!first1.equals(last1))        if (first2.equals(last2) || comp(first2.value, first1.value))            return false;        else if (comp(first1.value, first2.value))            return true;        else        {            first1 = first1.next();            first2 = first2.next();        }            return !first2.equals(last2);}
/* ---------------------------------------------------------    FINDERS--------------------------------------------------------- *//** * Find a value in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param val The value to find. *  * @return Iterator to the first element {@link equal to equal_to} the value. */export function find<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         val: IPointer.ValueType<InputIterator>    ): InputIterator{    return find_if(first, last, elem => equal_to(elem, val));}
/** * Find a matched condition in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return Iterator to the first element *pred* returns `true`. */export function find_if<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): InputIterator{    for (let it = first; !it.equals(last); it = it.next())        if (pred(it.value))            return it;
    return last;}
/** * Find a mismatched condition in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return Iterator to the first element *pred* returns `false`. */export function find_if_not<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): InputIterator{    return find_if(first, last, elem => !pred(elem));}
/** * Find the last sub range. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param last2 Input iterator of the last position of the 2nd range. *  * @return Iterator to the first element of the last sub range. */export function find_end<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2    ): Iterator1;
/** * Find the last sub range. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param last2 Input iterator of the last position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return Iterator to the first element of the last sub range. */export function find_end<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2,         pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>>    ): Iterator1;
export function find_end<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2,         pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>> = <any>equal_to    ): Iterator1{    if (first2.equals(last2))        return last1;
    let ret: Iterator1 = last1;
    for (; !first1.equals(last1); first1 = first1.next())    {        let it1: Iterator1 = first1;        let it2: Iterator2 = first2;
        while (pred(it1.value, it2.value))        {            it1 = it1.next();            it2 = it2.next();
            if (it2.equals(last2))            {                ret = first1;                break;            }            else if (it1.equals(last1))                return ret;        }    }    return ret;}
/** * Find the first sub range. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param last2 Input iterator of the last position of the 2nd range. *  * @return Iterator to the first element of the first sub range. */export function find_first_of<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2    ): Iterator1;
/** * Find the first sub range. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param last2 Input iterator of the last position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return Iterator to the first element of the first sub range. */export function find_first_of<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2,        pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>>    ): Iterator1;
export function find_first_of<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2, last2: Iterator2,        pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>> = <any>equal_to    ): Iterator1{    for (; !first1.equals(last1); first1 = first1.next())        for (let it = first2; !it.equals(last2); it = it.next())            if (pred(first1.value, it.value))                return first1;
    return last1;}
/** * Find the first adjacent element. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A binary function predicates two arguments are equal. Default is {@link equal_to}. *  * @return Iterator to the first element of adjacent find. */export function adjacent_find<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         pred: BinaryPredicator<IPointer.ValueType<InputIterator>> = equal_to    ): InputIterator{    if (!first.equals(last))    {        let next: InputIterator = first.next();
        while (!next.equals(last))        {            if (pred(first.value, last.value))                return first;
            first = first.next();            next = next.next();        }    }    return last;}

/** * Search sub range. *  * @param first1 Forward iteartor of the first position of the 1st range. * @param last1 Forward iterator of the last position of the 1st range. * @param first2 Forward iterator of the first position of the 2nd range. * @param last2 Forward iterator of the last position of the 2nd range. *  * @return Iterator to the first element of the sub range. */export function search<        ForwardIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator1>, ForwardIterator1>>,         ForwardIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator1>, ForwardIterator2>>>    (        first1: ForwardIterator1, last1: ForwardIterator1,         first2: ForwardIterator2, last2: ForwardIterator2    ): ForwardIterator1;
/** * Search sub range. *  * @param first1 Forward iteartor of the first position of the 1st range. * @param last1 Forward iterator of the last position of the 1st range. * @param first2 Forward iterator of the first position of the 2nd range. * @param last2 Forward iterator of the last position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return Iterator to the first element of the sub range. */export function search<        ForwardIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator1>, ForwardIterator1>>,         ForwardIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator2>, ForwardIterator2>>>    (        first1: ForwardIterator1, last1: ForwardIterator1,         first2: ForwardIterator2, last2: ForwardIterator2,        pred: BinaryPredicator<IPointer.ValueType<ForwardIterator1>, IPointer.ValueType<ForwardIterator2>>    ): ForwardIterator1;
export function search<        ForwardIterator1 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator1>, ForwardIterator1>>,         ForwardIterator2 extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator2>, ForwardIterator2>>>    (        first1: ForwardIterator1, last1: ForwardIterator1,         first2: ForwardIterator2, last2: ForwardIterator2,        pred: BinaryPredicator<IPointer.ValueType<ForwardIterator1>, IPointer.ValueType<ForwardIterator2>> = <any>equal_to    ): ForwardIterator1{    if (first2.equals(last2))        return first1;
    for (; !first1.equals(last1); first1 = first1.next())    {        let it1: ForwardIterator1 = first1;        let it2: ForwardIterator2 = first2;
        while (pred(it1.value, it2.value))        {            it1 = it1.next();            it2 = it2.next();
            if (it2.equals(last2))                return first1;            else if (it1.equals(last1))                return last1;        }    }    return last1;}
/** * Search specific and repeated elements. *  * @param first Forward iteartor of the first position. * @param last Forward iterator of the last position. * @param count Count to be repeated. * @param val Value to search. * @param pred A binary function predicates two arguments are equal. Default is {@link equal_to}. *  * @return Iterator to the first element of the repetition. */export function search_n<ForwardIterator extends Readonly<IForwardIterator<IPointer.ValueType<ForwardIterator>, ForwardIterator>>>    (        first: ForwardIterator, last: ForwardIterator,         count: number, val: IPointer.ValueType<ForwardIterator>,         pred: BinaryPredicator<IPointer.ValueType<ForwardIterator>> = equal_to    ): ForwardIterator{    let limit: ForwardIterator = advance(first, distance(first, last) - count);
    for (; !first.equals(limit); first = first.next())    {        let it: ForwardIterator = first;        let i: number = 0;
        while (pred(it.value, val))        {            it = it.next();
            if (++i === count)                return first;        }    }    return last;}
/** * Find the first mistmached position between two ranges. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. *  * @return A {@link Pair} of mismatched positions. */export function mismatch<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2    ): Pair<Iterator1, Iterator2>;
/** * Find the first mistmached position between two ranges. *  * @param first1 Input iteartor of the first position of the 1st range. * @param last1 Input iterator of the last position of the 1st range. * @param first2 Input iterator of the first position of the 2nd range. * @param pred A binary function predicates two arguments are equal. *  * @return A {@link Pair} of mismatched positions. */export function mismatch<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2,        pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>>    ): Pair<Iterator1, Iterator2>;
export function mismatch<        Iterator1 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator1>, Iterator1>>,         Iterator2 extends Readonly<IForwardIterator<IPointer.ValueType<Iterator2>, Iterator2>>>    (        first1: Iterator1, last1: Iterator1,         first2: Iterator2,        pred: BinaryPredicator<IPointer.ValueType<Iterator1>, IPointer.ValueType<Iterator2>> = <any>equal_to    ): Pair<Iterator1, Iterator2>{    while (!first1.equals(last1) && pred(first1.value, first2.value))    {        first1 = first1.next();        first2 = first2.next();    }    return new Pair(first1, first2);}
/* ---------------------------------------------------------    COUNTERS--------------------------------------------------------- *//** * Count matched value in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param val The value to count. *  * @return The matched count. */export function count<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         val: IPointer.ValueType<InputIterator>    ): number{    return count_if(first, last, elem => equal_to(elem, val));}
/** * Count matched condition in range. *  * @param first Input iteartor of the first position. * @param last Input iterator of the last position. * @param pred A function predicates the specific condition. *  * @return The matched count. */export function count_if<InputIterator extends Readonly<IForwardIterator<IPointer.ValueType<InputIterator>, InputIterator>>>    (        first: InputIterator, last: InputIterator,         pred: UnaryPredicator<IPointer.ValueType<InputIterator>>    ): number{    let ret: number = 0;
    for (let it = first; !it.equals(last); it = it.next())        if (pred(it.value))            ++ret;
    return ret;}