123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211
//================================================================ /** * @packageDocumentation * @module std   *///================================================================import { IRandomAccessIterator } from "../iterator/IRandomAccessIterator";import { IPointer } from "../functional/IPointer";
import { Comparator } from "../internal/functional/Comparator";import { General } from "../internal/functional/General";import { less } from "../functional/comparators";import { advance, distance } from "../iterator/global";
/* =========================================================    EA-STL (https://github.com/electronicarts/EASTL/blob/master/include/EASTL/heap.h)        - PUSH & POP        - SORT        - INTERNAL============================================================    PUSH & POP--------------------------------------------------------- *//** * Make a heap. *  * @param first Random access iteartor of the first position. * @param last Random access iterator of the last position. * @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Default is {@link less}. */export function make_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): void{    let heapSize: number = distance(first, last);    if (heapSize < 2)        return;
    let parentPosition: number = ((heapSize - 2) >> 1) + 1;    do    {        let temp: IPointer.ValueType<RandomAccessIterator> = first.advance(--parentPosition).value;        _Adjust_heap(first, parentPosition, heapSize, parentPosition, temp, comp);    }    while (parentPosition !== 0);}
/** * Push an element into heap. *  * @param first Random access iteartor of the first position. * @param last Random access iterator of the last position. * @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Default is {@link less}. */export function push_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): void{    let tempBottom: IPointer.ValueType<RandomAccessIterator> = last.prev().value;    _Promote_heap(first, 0, distance(first, last) - 1, tempBottom, comp);}
/** * Pop an element from heap. *  * @param first Random access iteartor of the first position. * @param last Random access iterator of the last position. * @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Default is {@link less}. */export function pop_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): void{    let tempBottom: IPointer.ValueType<RandomAccessIterator> = last.prev().value;    last.prev().value = first.value;
    _Adjust_heap(first, 0, distance(first, last) - 1, 0, tempBottom, comp);}
/* ---------------------------------------------------------    SORT--------------------------------------------------------- *//** * Test whether a range is heap. *  * @param first Bi-directional iteartor of the first position. * @param last Bi-directional iterator of the last position. * @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 range is heap. */export function is_heap<RandomAccessIterator extends Readonly<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): boolean{    let it = is_heap_until(first, last, comp);    return it.equals(last);}
/** * Find the first element not in heap order. *  * @param first Bi-directional iteartor of the first position. * @param last Bi-directional iterator of the last position. * @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 Iterator to the first element not in heap order. */export function is_heap_until<RandomAccessIterator extends Readonly<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): RandomAccessIterator{    let counter: number = 0;    for (let child = first.next(); _Comp_it(child, last.index()); child = child.next(), counter ^= 1)    {        if (comp(first.value, child.value))            return child;        first = advance(first, counter);    }    return last;}
/** * Sort elements of a heap. *  * @param first Random access iteartor of the first position. * @param last Random access iterator of the last position. * @param comp A binary function predicates *x* element would be placed before *y*. When returns `true`, then *x* precedes *y*. Default is {@link less}. */export function sort_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         last: RandomAccessIterator,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>> = less    ): void{    for (; distance(first, last) > 1; last = last.prev())        pop_heap(first, last, comp);}
/* ---------------------------------------------------------    INTERNAL--------------------------------------------------------- */function _Promote_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         topPosition: number,         position: number,         value: IPointer.ValueType<RandomAccessIterator>,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>>    ): void{    for (let parentPosition: number = (position - 1) >> 1;        (position > topPosition) && comp(first.advance(parentPosition).value, value);         parentPosition = (position - 1) >> 1)    {        first.advance(position).value = first.advance(parentPosition).value;        position = parentPosition;    }    first.advance(position).value = value;}
function _Adjust_heap<RandomAccessIterator extends General<IRandomAccessIterator<IPointer.ValueType<RandomAccessIterator>, RandomAccessIterator>>>    (        first: RandomAccessIterator,         topPosition: number,         heapSize: number,         position: number,         value: IPointer.ValueType<RandomAccessIterator>,         comp: Comparator<IPointer.ValueType<RandomAccessIterator>>    ): void{    let childPosition: number = (2 * position) + 2;    for (; childPosition < heapSize; childPosition = (2 * childPosition) + 2)    {        if (comp(first.advance(childPosition).value, first.advance(childPosition - 1).value))            --childPosition;                first.advance(position).value = first.advance(childPosition).value;        position = childPosition;    }
    if (childPosition === heapSize)    {        first.advance(position).value = first.advance(childPosition - 1).value;        position = childPosition - 1;    }    _Promote_heap(first, topPosition, position, value, comp);}
function _Comp_it(x: any, y: any): boolean{    if (x.base instanceof Function)        return y < x;    else        return x < y;}