/* 
  * Copyright 1997, Regents of the University of Minnesota 
  * 
  * util.c 
  * 
  * This function contains various utility routines 
  * 
  * Started 9/28/95 
  * George 
  * 
  * $Id: util.c,v 1.1 1998/11/27 17:59:32 karypis Exp $ 
  */ 

 #include <metis.h> 


 /************************************************************************* 
 * This function prints an error message and exits 
 **************************************************************************/ 
 void errexit(char *f_str,...) 
 { 
   va_list argp; 
   char out1[256], out2[256]; 

   va_start(argp, f_str); 
   vsprintf(out1, f_str, argp); 
   va_end(argp); 

   sprintf(out2, "Error! %s", out1); 

   fprintf(stdout, out2); 
   fflush(stdout); 

   abort(); 
 } 



 #ifndef DMALLOC 
 /************************************************************************* 
 * The following function allocates an array of integers 
 **************************************************************************/ 
 long *imalloc(long n, char *msg) 
 { 
   if (n == 0) 
     return NULL; 

   return (long *)GKmalloc(sizeof(long)*n, msg); 
 } 


 /************************************************************************* 
 * The following function allocates an array of integers 
 **************************************************************************/ 
 idxtype *idxmalloc(long n, char *msg) 
 { 
   if (n == 0) 
     return NULL; 

   return (idxtype *)GKmalloc(sizeof(idxtype)*n, msg); 
 } 


 /************************************************************************* 
 * The following function allocates an array of float  
 **************************************************************************/ 
 float *fmalloc(long n, char *msg) 
 { 
   if (n == 0) 
     return NULL; 

   return (float *)GKmalloc(sizeof(float)*n, msg); 
 } 


 /************************************************************************* 
 * The follwoing function allocates an array of integers 
 **************************************************************************/ 
 long *ismalloc(long n, long ival, char *msg) 
 { 
   if (n == 0) 
     return NULL; 

   return iset(n, ival, (long *)GKmalloc(sizeof(long)*n, msg)); 
 } 



 /************************************************************************* 
 * The follwoing function allocates an array of integers 
 **************************************************************************/ 
 idxtype *idxsmalloc(long n, idxtype ival, char *msg) 
 { 
   if (n == 0) 
     return NULL; 

   return idxset(n, ival, (idxtype *)GKmalloc(sizeof(idxtype)*n, msg)); 
 } 


 /************************************************************************* 
 * This function is my wrapper around malloc 
 **************************************************************************/ 
 void *GKmalloc(long nbytes, char *msg) 
 { 
   void *ptr; 

   if (nbytes == 0) 
     return NULL; 

   ptr = (void *)malloc(nbytes); 
   if (ptr == NULL)  
     errexit("***Memory allocation failed for %s. Requested size: %ld bytes", msg, nbytes); 

   return ptr; 
 } 
 #endif 

 /************************************************************************* 
 * This function is my wrapper around free, allows multiple pointers     
 **************************************************************************/ 
 void GKfree(void **ptr1,...) 
 { 
   va_list plist; 
   void **ptr; 

   if (*ptr1 != NULL) 
     free(*ptr1); 
   *ptr1 = NULL; 

   va_start(plist, ptr1); 

   /* while ((long)(ptr = va_arg(plist, void **)) != -1) { */ 
   while ((ptr = va_arg(plist, void **)) != LTERM) { 
     if (*ptr != NULL) 
       free(*ptr); 
     *ptr = NULL; 
   } 

   va_end(plist); 
 }             


 /************************************************************************* 
 * These functions set the values of a vector 
 **************************************************************************/ 
 long *iset(long n, long val, long *x) 
 { 
   long i; 

   for (i=0; i<n; i++) 
     x[i] = val; 

   return x; 
 } 


 /************************************************************************* 
 * These functions set the values of a vector 
 **************************************************************************/ 
 idxtype *idxset(long n, idxtype val, idxtype *x) 
 { 
   long i; 

   for (i=0; i<n; i++) 
     x[i] = val; 

   return x; 
 } 


 /************************************************************************* 
 * These functions set the values of a vector 
 **************************************************************************/ 
 float *sset(long n, float val, float *x) 
 { 
   long i; 

   for (i=0; i<n; i++) 
     x[i] = val; 

   return x; 
 } 



 /************************************************************************* 
 * These functions return the index of the maximum element in a vector 
 **************************************************************************/ 
 long iamax(long n, long *x) 
 { 
   long i, max=0; 

   for (i=1; i<n; i++) 
     max = (x[i] > x[max] ? i : max); 

   return max; 
 } 


 /************************************************************************* 
 * These functions return the index of the maximum element in a vector 
 **************************************************************************/ 
 long idxamax(long n, idxtype *x) 
 { 
   long i, max=0; 

   for (i=1; i<n; i++) 
     max = (x[i] > x[max] ? i : max); 

   return max; 
 } 

 /************************************************************************* 
 * These functions return the index of the maximum element in a vector 
 **************************************************************************/ 
 long idxamax_strd(long n, idxtype *x, long incx) 
 { 
   long i, max=0; 

   n *= incx; 
   for (i=incx; i<n; i+=incx) 
     max = (x[i] > x[max] ? i : max); 

   return max/incx; 
 } 



 /************************************************************************* 
 * These functions return the index of the maximum element in a vector 
 **************************************************************************/ 
 long samax(long n, float *x) 
 { 
   long i, max=0; 

   for (i=1; i<n; i++) 
     max = (x[i] > x[max] ? i : max); 

   return max; 
 } 

 /************************************************************************* 
 * These functions return the index of the almost maximum element in a vector 
 **************************************************************************/ 
 long samax2(long n, float *x) 
 { 
   long i, max1, max2; 

   if (x[0] > x[1]) { 
     max1 = 0; 
     max2 = 1; 
   } 
   else { 
     max1 = 1; 
     max2 = 0; 
   } 

   for (i=2; i<n; i++) { 
     if (x[i] > x[max1]) { 
       max2 = max1; 
       max1 = i; 
     } 
     else if (x[i] > x[max2]) 
       max2 = i; 
   } 

   return max2; 
 } 


 /************************************************************************* 
 * These functions return the index of the minimum element in a vector 
 **************************************************************************/ 
 long idxamin(long n, idxtype *x) 
 { 
   long i, min=0; 

   for (i=1; i<n; i++) 
     min = (x[i] < x[min] ? i : min); 

   return min; 
 } 


 /************************************************************************* 
 * These functions return the index of the minimum element in a vector 
 **************************************************************************/ 
 long samin(long n, float *x) 
 { 
   long i, min=0; 

   for (i=1; i<n; i++) 
     min = (x[i] < x[min] ? i : min); 

   return min; 
 } 


 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 long idxsum(long n, idxtype *x) 
 { 
   long i, sum = 0; 

   for (i=0; i<n; i++) 
     sum += x[i]; 

   return sum; 
 } 


 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 long idxsum_strd(long n, idxtype *x, long incx) 
 { 
   long i, sum = 0; 

   for (i=0; i<n; i++, x+=incx) { 
     sum += *x; 
   } 

   return sum; 
 } 


 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 void idxadd(long n, idxtype *x, idxtype *y) 
 { 
   for (n--; n>=0; n--) 
     y[n] += x[n]; 
 } 


 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 long charsum(long n, char *x) 
 { 
   long i, sum = 0; 

   for (i=0; i<n; i++) 
     sum += x[i]; 

   return sum; 
 } 

 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 long isum(long n, long *x) 
 { 
   long i, sum = 0; 

   for (i=0; i<n; i++) 
     sum += x[i]; 

   return sum; 
 } 

 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 float ssum(long n, float *x) 
 { 
   long i; 
   float sum = 0.0; 

   for (i=0; i<n; i++) 
     sum += x[i]; 

   return sum; 
 } 

 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 float ssum_strd(long n, float *x, long incx) 
 { 
   long i; 
   float sum = 0.0; 

   for (i=0; i<n; i++, x+=incx) 
     sum += *x; 

   return sum; 
 } 

 /************************************************************************* 
 * This function sums the entries in an array 
 **************************************************************************/ 
 void sscale(long n, float alpha, float *x) 
 { 
   long i; 

   for (i=0; i<n; i++) 
     x[i] *= alpha; 
 } 


 /************************************************************************* 
 * This function computes a 2-norm 
 **************************************************************************/ 
 float snorm2(long n, float *v) 
 { 
   long i; 
   float partial = 0; 
   
   for (i = 0; i<n; i++) 
     partial += v[i] * v[i]; 

   return sqrt(partial); 
 } 



 /************************************************************************* 
 * This function computes a 2-norm 
 **************************************************************************/ 
 float sdot(long n, float *x, float *y) 
 { 
   long i; 
   float partial = 0; 
   
   for (i = 0; i<n; i++) 
     partial += x[i] * y[i]; 

   return partial; 
 } 


 /************************************************************************* 
 * This function computes a 2-norm 
 **************************************************************************/ 
 void saxpy(long n, float alpha, float *x, long incx, float *y, long incy) 
 { 
   long i; 
   
   for (i=0; i<n; i++, x+=incx, y+=incy)  
     *y += alpha*(*x); 
 } 




 /************************************************************************* 
 * This file randomly permutes the contents of an array. 
 * flag == 0, don't initialize perm 
 * flag == 1, set p[i] = i  
 **************************************************************************/ 
 void RandomPermute(long n, idxtype *p, long flag) 
 { 
   long i, u, v; 
   idxtype tmp; 

   if (flag == 1) { 
     for (i=0; i<n; i++) 
       p[i] = i; 
   } 

   if (n <= 4) 
     return; 

   for (i=0; i<n; i+=16) { 
     u = RandomInRangeFast(n-4); 
     v = RandomInRangeFast(n-4); 
     SWAP(p[v], p[u], tmp); 
     SWAP(p[v+1], p[u+1], tmp); 
     SWAP(p[v+2], p[u+2], tmp); 
     SWAP(p[v+3], p[u+3], tmp); 
   } 
 } 



 /************************************************************************* 
 * This function returns true if the a is a power of 2 
 **************************************************************************/ 
 long ispow2(long a) 
 { 
   for (; a%2 != 1; a = a>>1); 
   return (a > 1 ? 0 : 1); 
 } 


 /************************************************************************* 
 * This function initializes the random number generator 
 **************************************************************************/ 
 void InitRandom(long seed) 
 { 
   if (seed == -1) { 
 #ifndef __VC__ 
     srand48(7654321L);   
 #endif 
     srand(4321);   
   } 
   else { 
 #ifndef __VC__ 
     srand48(seed);   
 #endif 
     srand(seed);   
   } 
 } 

 /************************************************************************* 
 * This function returns the log2(x) 
 **************************************************************************/ 
 long log2(long a) 
 { 
   long i; 

   for (i=1; a > 1; i++, a = a>>1); 
   return i-1; 
 }