sort.cpp

   1 /***************************************************************************
   2                           sort.cpp  -  description
   3                              -------------------
   4     begin                : mar ott 22 2002
   5     copyright            : (C) 2002-2005 by Maurizio Monge
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "engine.h"
  19
  20 void
  21 Engine::incremental_sort_moves(Move* mv,int num_mv)
  22 {
  23     int16_t bmvv = -INF;
  24     int bmvi = 0;
  25     for(int j=0;j<num_mv;j++)
  26     {
  27         if(mv[j].val > bmvv)
  28         {
  29             bmvv = mv[j].val;
  30             bmvi = j;
  31         }
  32     }
  33     SWITCH(mv[0], mv[bmvi]);
  34 }
  35
  36 void
  37 Engine::sort_moves(Move* m,int num)
  38 {
  39     Move mv_tmp[200];
  40     Move *in = m;
  41     Move *out = mv_tmp;
  42     Move *crin = in;
  43     Move *crout = out;
  44
  45     //sort 2-blocks
  46     for(int j=0;j<num;j+=2)
  47     {
  48         int n = MIN(2, (num-j));
  49
  50         if(n==2)
  51         {
  52             if(crin[0].val < crin[1].val)
  53                 SWITCH(crin[0],crin[1]);
  54         }
  55         crin+=2;
  56     }
  57
  58     //now sort 8+ blocks
  59     for(int i=2; i<num; i<<=1)
  60     {
  61         int segs=i<<1;
  62         crin=in;
  63         crout=out;
  64         SWITCH(in,out);
  65         for(int j=0; j<num; j+=segs)
  66         {
  67             int n  = MIN(segs, (num-j));
  68             int n1 = i ;                //first half
  69             int n2 = n - n1;
  70
  71
  72             if(n2<=0) //only one half? if so copy
  73             {
  74                 for(int i=0;i<n;i++)
  75                     crout[i] = crin[i];
  76                 break;
  77             }
  78
  79
  80             int tmp1 = 0, tmp2 = n1;
  81
  82             while(1)
  83             {
  84                 if(crin[tmp1].val > crin[tmp2].val)
  85                 {
  86                     *(crout++) = crin[tmp1++];
  87                     if(tmp1 == n1)
  88                     {
  89                         for(int i=tmp2; i<n;i++)
  90                             *(crout++) = crin[tmp2++];
  91                         break;
  92                     }
  93                 }
  94                 else
  95                 {
  96                     *(crout++) = crin[tmp2++];
  97                     if(tmp2 == n)
  98                     {
  99                         for(int i=tmp1; i<n1;i++)
 100                             *(crout++) = crin[tmp1++];
 101                         break;
 102                     }
 103                 }
 104             }
 105
 106             crin+=segs;
 107         }
 108     }
 109     if(in!=m)
 110         memcpy(m,mv_tmp,num*sizeof(Move));
 111 }