pick.c

Hausdorff Distance for Image Recognition

/*
 *
 * $Header: /usr/u/wjr/src/support/RCS/pick.c,v 2.3 1993/07/26 22:16:16 wjr Exp $
 *
 * Copyright (c) 1990, 1991, 1992, 1993 Cornell University.  All Rights
 * Reserved.
 *
 * Copyright (c) 1991, 1992 Xerox Corporation.  All Rights Reserved.
 *
 * Use, reproduction, preparation of derivative works, and distribution
 * of this software is permitted.  Any copy of this software or of any
 * derivative work must include both the above copyright notices of
 * Cornell University and Xerox Corporation and this paragraph.  Any
 * distribution of this software or derivative works must comply with all
 * applicable United States export control laws.  This software is made
 * available AS IS, and XEROX CORPORATION DISCLAIMS ALL WARRANTIES,
 * EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE,
 * AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED HEREIN, ANY
 * LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
 * EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
 * NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGES.
 */

static char rcsid[] = "@(#)$Header: /usr/u/wjr/src/support/RCS/pick.c,v 2.3 1993/07/26 22:16:16 wjr Exp $";

#include "misc.h"

/*
 * Pick the (whichval)'th smallest element from vals. If whichval = 0,
 * pick the smallest; if whichval = 1, pick the second smallest, etc.
 * If whichval < 0, return something small.
 */
long
pickNth(long *vals, int nvals, int whichval)
{
    int low;
    int high;
    long pivot;
    int bottom;
    int top;
    long tmp;

    /*
     * This is similar to a quicksort, but we zoom in on the
     * value requested, and do not do a complete sort.
     */
    low = 0;
    high = nvals - 1;
    if (low > high) {
	/* Nothing to do - return something arbitrary */
	return(0);
	}

    if (whichval > high) {
	whichval = high;
	}
    if (whichval < low) {
	return(0);
	}

    while (TRUE) {
	assert(low <= high);

	if (whichval == low) {
	    /* We want the minimum of vals[low..high] */
	    pivot = vals[low];
	    for (low++; low <= high; low++) {
		pivot = MIN(pivot, vals[low]);
		}
	    return(pivot);
	    }
	else if (whichval == high) {
	    /* We want the maximum of vals[low..high] */
	    pivot = vals[low];
	    for (low++; low <= high; low++) {
		pivot = MAX(pivot, vals[low]);
		}
	    return(pivot);
	    }

	/* Pick a pivot */
	pivot = vals[low];
	/* Make sure that there is at least one thing smaller than pivot */
	for (bottom = low + 1; bottom <= high; bottom++) {
	    if (vals[bottom] > pivot) {
		pivot = vals[bottom];
		break;
		}
	    else if (vals[bottom] < pivot) {
		break;
		}
	    }
	if (bottom == high + 1) {
	    /* All the same - return the (single) value */
	    return(pivot);
	    }

	bottom = low;
	top = high;
	while (bottom < top) {
	    /*
	     * Skip over elements that are in the right place.
	     * We know that these loops will terminate safely since there
	     * is at least one value in the array smaller than pivot,
	     * and it is below top, so the first loop will terminate,
	     * and there is at least one value equal to pivot,
	     * and it is at or higher than bottom, so the second loop
	     * will terminate.
	     */
	    while (vals[top] >= pivot) {
		top--;
		}
	    while (vals[bottom] < pivot) {
		bottom++;
		}

	    if (top >= bottom) {
		/* Swap the values at top and bottom */
		tmp = vals[top];
		vals[top] = vals[bottom];
		vals[bottom] = tmp;
		}
	    }

	/* At this point, top and bottom have just crossed */
	assert(top == bottom - 1);

	/* vals[low..top] are < pivot; vals[bottom..high] are >= pivot */
	if (top >= whichval) {
	    high = top;
	    }
	else {
	    low = bottom;
	    }
	}
    }

double
frac_lower(long *vals, int nvals, long upper)
{
    int i;
    int lowercount;

    assert(vals != (long *)NULL);

    if (nvals == 0) {
	return(1.);
	}

    lowercount = 0;
    for (i = 0; i < nvals; i++) {
	if (vals[i] <= upper) {
	    lowercount++;
	    }
	}

    return((double)lowercount / (double)nvals);
    }