/Users/dbr/ma/src/bas/lml/sort.c

Go to the documentation of this file.

#include "base.h"

static void Push( void * set, UINT c, SINT (*Cmp)(void *, UINT, UINT), void (*Swap)(void *, UINT, UINT) ){
    UINT p;

    while( bTRUE ){
        if( c == 0 ){
            break;
        }
        p = (c - 1) / 2;
        if( Cmp( set, c, p ) > 0 ){
            Swap( set, p, c );
            c = p;
        }
        else{
            break;
        }
    }
}

static void Sink( void * set, UINT length, SINT (*Cmp)(void *, UINT, UINT), void (*Swap)(void *, UINT, UINT) ){
    UINT c, l, r;

    c = 0;
    while( bTRUE ){
        l = 2*c + 1;
        if( l < length ){
            r = l + 1;
            if( r < length ){
                if( Cmp( set, l, r ) > 0 ){
                    if( Cmp( set, l, c ) > 0 ){
                        Swap( set, l, c );
                        c = l;
                    }
                    else{
                        break;
                    }
                }
                else if( Cmp( set, c, r ) < 0 ){
                    Swap( set, r, c );
                    c = r;
                }
                else{
                    break;
                }
            }
            else if( Cmp( set, l, c ) > 0 ){
                Swap( set, l, c );
                c = l;
            }
            else{
                break;
            }
        }
        else{
            break;
        }
    }
}

void Sort( void * set, UINT numberOfElements, SINT (*Cmp)(void *, UINT, UINT), void (*Swap)(void *, UINT, UINT) ){
    UINT i;

    for( i = 0; i < numberOfElements; i++ ){
        Push( set, i, Cmp, Swap );
    }
    for( i = 1; i < numberOfElements; i++ ){
        Swap( set, 0, numberOfElements-i );
        Sink( set, numberOfElements-i, Cmp, Swap );
    }
}

UINT BinarySearch( const void * set, UINT startPos, UINT length, const void * object, SINT (*Cmp)(const void *, UINT, const void *) ){
    UINT left, right, mid;
    SINT r;

    if( length == 0 ){
        return NO;
    }
    left = startPos;
    right = left + length - 1;
    while( bTRUE ){
        if( left == right ){
            if( Cmp( set, left, object ) == 0 ){
                return left;
            }
            return NO;
        }
        if( left + 1 == right ){
            if( Cmp( set, left, object ) == 0 ){
                return left;
            }
            if( Cmp( set, right, object ) == 0 ){
                return right;
            }
            return NO;
        }
        mid = (left + right)/2;
        r = Cmp( set, mid, object );
        if( r < 0 ){
            left = mid;
        }
        else if( r > 0 ){
            right = mid;
        }
        else{
            return mid;
        }
    }
}