src/kernel/sorting.c

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
   5  * Copyright (c) 2001-2004, The GROMACS development team,
   6  * check out http://www.gromacs.org for more information.
   7  * Copyright (c) 2012, by the GROMACS development team, led by
   8  * David van der Spoel, Berk Hess, Erik Lindahl, and including many
   9  * others, as listed in the AUTHORS file in the top-level source
  10  * directory and at http://www.gromacs.org.
  11  *
  12  * GROMACS is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public License
  14  * as published by the Free Software Foundation; either version 2.1
  15  * of the License, or (at your option) any later version.
  16  *
  17  * GROMACS is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with GROMACS; if not, see
  24  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  25  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  26  *
  27  * If you want to redistribute modifications to GROMACS, please
  28  * consider that scientific software is very special. Version
  29  * control is crucial - bugs must be traceable. We will be happy to
  30  * consider code for inclusion in the official distribution, but
  31  * derived work must not be called official GROMACS. Details are found
  32  * in the README & COPYING files - if they are missing, get the
  33  * official version at http://www.gromacs.org.
  34  *
  35  * To help us fund GROMACS development, we humbly ask that you cite
  36  * the research papers on the package. Check out http://www.gromacs.org.
  37  */
  38 #ifdef HAVE_CONFIG_H
  39 #include <config.h>
  40 #endif
  41
  42 #include <limits.h>
  43 #include "sysstuff.h"
  44 #include "smalloc.h"
  45 #include "sorting.h"
  46
  47 /*****************************************************************************
  48  *                                                                           *
  49  *                   Block sorting on coordinates                            *
  50  *                                                                           *
  51  *****************************************************************************/
  52
  53 static rvec *make_xblock(t_block *block,rvec x[])
  54 {
  55   int i,j,k,nr,n;
  56   rvec *xblock;
  57
  58   nr=block->nr;
  59   snew(xblock,nr);
  60   for (i=0; i<nr; i++)
  61     {
  62       for (j=0; j<DIM; j++) xblock[i][j]=0.0;
  63       for (j=block->index[i]; j<(int)(block->index[i+1]); j++)
  64         for (k=0; k<DIM; k++) xblock[i][k]+=x[j][k];
  65       n=block->index[i+1]-block->index[i];
  66       for (k=0; k<DIM; k++) xblock[i][k]/=n;
  67     }
  68   return xblock;
  69 }
  70
  71 static rvec *xblock; /* just global to bcomp1, used in qsort */
  72
  73 static int bomp1(const void *p1,const void *p2)
  74 {
  75   int i,i1,i2;
  76
  77   i1=*(int *)p1;
  78   i2=*(int *)p2;
  79   for (i=0; i<DIM; i++)
  80     if (xblock[i1][i]<xblock[i2][i]) return -1;
  81     else if (xblock[i1][i]>xblock[i2][i]) return 1;
  82   return 0;
  83 }
  84
  85 void sort_xblock(t_block *block,rvec x[],int renum[])
  86 {
  87   int i,nr,*invnum;
  88
  89   nr=block->nr;
  90   snew(invnum,nr);
  91   xblock=make_xblock(block,x);
  92   for (i=0; i<nr; i++) invnum[i]=i;
  93   qsort((void *)invnum,nr,(size_t)sizeof(invnum[0]),bomp1);
  94   for (i=0; i<nr; i++) renum[invnum[i]]=i;
  95   sfree(xblock);
  96   sfree(invnum);
  97 }
  98
  99 /*****************************************************************************
 100  *                                                                           *
 101  *                        Bond list sorting                                  *
 102  *                                                                           *
 103  *****************************************************************************/
 104
 105 static int bcomp2(const void *p1,const void *p2)
 106 {
 107   int done;
 108
 109   if ((((atom_id *)p1)[0])!=(((atom_id *)p2)[0]))
 110     done=((((atom_id *)p1)[0])-(((atom_id *)p2)[0]));
 111   else
 112     done=((((atom_id *)p1)[1])-(((atom_id *)p2)[1]));
 113 #ifdef DEBUG
 114   printf("bcomp2: [%d,%d] with [%d,%d] result %d\n",
 115           ((atom_id *)p1)[0],((atom_id *)p1)[1],
 116           ((atom_id *)p2)[0],((atom_id *)p2)[1],done);
 117 #endif
 118   return done;
 119 }
 120
 121 void sort_bond_list(t_bond bonds[],int nr)
 122 {
 123   qsort((void *)bonds,nr,(size_t)sizeof(bonds[0]),bcomp2);
 124 }