// 
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
// 
// searchsort.c -- 
// 
// Author           : Peter A. Buhr
// Created On       : Thu Feb  4 18:17:50 2016
// Last Modified By : Peter A. Buhr
// Last Modified On : Tue Jan  2 08:01:17 2018
// Update Count     : 100
// 

#include <fstream>
#include <stdlib>										// bsearch, qsort
#include <stdlib.h>										// C version of bsearch

int comp( const void * t1, const void * t2 ) { return *(int *)t1 < *(int *)t2 ? -1 : *(int *)t2 < *(int *)t1 ? 1 : 0; }

int main( void ) {
	const unsigned int size = 10;
	int iarr[size];

	for ( unsigned int i = 0; i < size; i += 1 ) {
		iarr[i] = size - i;
		sout | iarr[i] | ", ";
	} // for
	sout | endl | endl;

	// ascending sort/search by changing < to >
	qsort( iarr, size );
	for ( unsigned int i = 0; i < size; i += 1 ) {
		sout | iarr[i] | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {		// C version
		int key = size - i;
		int * v = bsearch( &key, iarr, size, sizeof( iarr[0] ), comp );
		sout | key | ':' | *v | ", ";
	} // for
	sout | endl;

	for ( unsigned int i = 0; i < size; i += 1 ) {
		int * v = bsearch( size - i, iarr, size );
		sout | size - i | ':' | *v | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {
		unsigned int posn = bsearch( size - i, iarr, size );
		sout | size - i | ':' | iarr[posn] | ", ";
	} // for
	sout | endl | endl;

	// descending sort/search by changing < to >
	for ( unsigned int i = 0; i < size; i += 1 ) {
		iarr[i] = i + 1;
		sout | iarr[i] | ", ";
	} // for
	sout | endl;
	{
		int ?<?( int x, int y ) { return x > y; }
		qsort( iarr, size );
		for ( unsigned int i = 0; i < size; i += 1 ) {
			sout | iarr[i] | ", ";
		} // for
		sout | endl;
		for ( unsigned int i = 0; i < size; i += 1 ) {
			int * v = bsearch( size - i, iarr, size );
			sout | size - i | ':' | *v | ", ";
		} // for
		sout | endl;
		for ( unsigned int i = 0; i < size; i += 1 ) {
			unsigned int posn = bsearch( size - i, iarr, size );
			sout | size - i | ':' | iarr[posn] | ", ";
		} // for
	}
	sout | endl | endl;

	double darr[size];
	for ( unsigned int i = 0; i < size; i += 1 ) {
		darr[i] = size - i + 0.5;
		sout | darr[i] | ", ";
	} // for
	sout | endl;
	qsort( darr, size );
	for ( unsigned int i = 0; i < size; i += 1 ) {
		sout | darr[i] | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {
		double * v = bsearch( size - i + 0.5, darr, size );
		sout | size - i + 0.5 | ':' | *v | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {
		unsigned int posn = bsearch( size - i + 0.5, darr, size );
		sout | size - i + 0.5 | ':' | darr[posn] | ", ";
	} // for
	sout | endl | endl;

	struct S { int i, j; } sarr[size];
	int ?<?( S t1, S t2 ) { return t1.i < t2.i && t1.j < t2.j; }
	ofstream & ?|?( ofstream & os, S v ) { return os | v.i | ' ' | v.j; }
	for ( unsigned int i = 0; i < size; i += 1 ) {
		sarr[i].i = size - i;
		sarr[i].j = size - i + 1;
		sout | sarr[i] | ", ";
	} // for
	sout | endl;
	qsort( sarr, size );
	for ( unsigned int i = 0; i < size; i += 1 ) {
		sout | sarr[i] | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {
		S temp = { size - i, size - i + 1 };
		S * v = bsearch( temp, sarr, size );
		sout | temp | ':' | *v | ", ";
	} // for
	sout | endl;
	for ( unsigned int i = 0; i < size; i += 1 ) {
		S temp = { size - i, size - i + 1 };
		unsigned int posn = bsearch( temp, sarr, size );
		sout | temp | ':' | sarr[posn] | ", ";
	} // for
	sout | endl | endl;
	{
		unsigned int getKey( const S & s ) { return s.j; }
		for ( unsigned int i = 0; i < size; i += 1 ) {
			sout | sarr[i] | ", ";
		} // for
		sout | endl;
		for ( unsigned int i = 0; i < size; i += 1 ) {
			S * v = bsearch( size - i + 1, sarr, size );
			sout | size - i + 1 | ':' | *v | ", ";
		} // for
		sout | endl;
		for ( unsigned int i = 0; i < size; i += 1 ) {
			unsigned int posn = bsearch( size - i + 1, sarr, size );
			sout | size - i + 1 | ':' | sarr[posn] | ", ";
		} // for
		sout | endl | endl;
	}
} // main

// Local Variables: //
// tab-width: 4 //
// compile-command: "cfa searchsort.c" //
// End: //