//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// bits/algorithms.h -- Builtins for exception handling.
//
// Author           : Thierry Delisle
// Created On       : Mon Oct 30 13:37:34 2017
// Last Modified By : --
// Last Modified On : --
// Update Count     : 0
//

#pragma once

#ifdef SAFE_SORT
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim );

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort( T * arr, size_t dim ) {
	switch( dim ) {
		case 1 : return;
		case 2 : __libcfa_small_sort2( arr ); return;
		case 3 : __libcfa_small_sort3( arr ); return;
		case 4 : __libcfa_small_sort4( arr ); return;
		case 5 : __libcfa_small_sort5( arr ); return;
		case 6 : __libcfa_small_sort6( arr ); return;
		default: __libcfa_small_sortN( arr, dim ); return;
	}
}

#define min(x, y) (y > x ? x : y)
#define max(x, y) (y > x ? y : x)
#define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort2( T * arr ) {
	SWAP(0, 1);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort3( T * arr ) {
	SWAP(1, 2);
	SWAP(0, 2);
	SWAP(0, 1);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort4( T * arr ) {
	SWAP(0, 1);
	SWAP(2, 3);
	SWAP(0, 2);
	SWAP(1, 3);
	SWAP(1, 2);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort5( T * arr ) {
	SWAP(0, 1);
	SWAP(3, 4);
	SWAP(2, 4);
	SWAP(2, 3);
	SWAP(0, 3);
	SWAP(0, 2);
	SWAP(1, 4);
	SWAP(1, 3);
	SWAP(1, 2);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort6( T * arr ) {
	SWAP(1, 2);
	SWAP(4, 5);
	SWAP(0, 2);
	SWAP(3, 5);
	SWAP(0, 1);
	SWAP(3, 4);
	SWAP(1, 4);
	SWAP(0, 3);
	SWAP(2, 5);
	SWAP(1, 3);
	SWAP(2, 4);
	SWAP(2, 3);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sortN( T * arr, size_t dim ) {
	int i, j;
	for (i = 1; i < dim; i++) {
		T tmp = arr[i];
		for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
			arr[j] = arr[j-1];
		}
		arr[j] = tmp;
	}
}

#else

static inline void __libcfa_small_sort2( void* * arr );
static inline void __libcfa_small_sort3( void* * arr );
static inline void __libcfa_small_sort4( void* * arr );
static inline void __libcfa_small_sort5( void* * arr );
static inline void __libcfa_small_sort6( void* * arr );
static inline void __libcfa_small_sortN( void* * arr, size_t dim );

forall( dtype T )
static inline void __libcfa_small_sort( T* * arr, size_t dim ) {
	switch( dim ) {
		case 1 : return;
		case 2 : __libcfa_small_sort2( (void **) arr ); return;
		case 3 : __libcfa_small_sort3( (void **) arr ); return;
		case 4 : __libcfa_small_sort4( (void **) arr ); return;
		case 5 : __libcfa_small_sort5( (void **) arr ); return;
		case 6 : __libcfa_small_sort6( (void **) arr ); return;
		default: __libcfa_small_sortN( (void **) arr, dim ); return;
	}
}

#define min(x, y) (y > x ? x : y)
#define max(x, y) (y > x ? y : x)
#define SWAP(x,y) { void* a = min(arr[x], arr[y]); void* b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}

static inline void __libcfa_small_sort2( void* * arr ) {
	SWAP(0, 1);
}

static inline void __libcfa_small_sort3( void* * arr ) {
	SWAP(1, 2);
	SWAP(0, 2);
	SWAP(0, 1);
}

static inline void __libcfa_small_sort4( void* * arr ) {
	SWAP(0, 1);
	SWAP(2, 3);
	SWAP(0, 2);
	SWAP(1, 3);
	SWAP(1, 2);
}

static inline void __libcfa_small_sort5( void* * arr ) {
	SWAP(0, 1);
	SWAP(3, 4);
	SWAP(2, 4);
	SWAP(2, 3);
	SWAP(0, 3);
	SWAP(0, 2);
	SWAP(1, 4);
	SWAP(1, 3);
	SWAP(1, 2);
}

static inline void __libcfa_small_sort6( void* * arr ) {
	SWAP(1, 2);
	SWAP(4, 5);
	SWAP(0, 2);
	SWAP(3, 5);
	SWAP(0, 1);
	SWAP(3, 4);
	SWAP(1, 4);
	SWAP(0, 3);
	SWAP(2, 5);
	SWAP(1, 3);
	SWAP(2, 4);
	SWAP(2, 3);
}

static inline void __libcfa_small_sortN( void* * arr, size_t dim ) {
	int i, j;
	for (i = 1; i < dim; i++) {
		void* tmp = arr[i];
		for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
			arr[j] = arr[j-1];
		}
		arr[j] = tmp;
	}
}

#endif

#undef SWAP
#undef min
#undef max