htswanalysis/MACS/lib/gsl/gsl-1.11/combination/combination.c

   1 /* combination/combination.c
   2  * based on permutation/permutation.c by Brian Gough
   3  *
   4  * Copyright (C) 2001 Szymon Jaroszewicz
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 3 of the License, or (at
   9  * your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  */
  20
  21 #include <config.h>
  22 #include <gsl/gsl_errno.h>
  23 #include <gsl/gsl_combination.h>
  24
  25 size_t
  26 gsl_combination_n (const gsl_combination * c)
  27 {
  28   return c->n ;
  29 }
  30
  31 size_t
  32 gsl_combination_k (const gsl_combination * c)
  33 {
  34   return c->k ;
  35 }
  36
  37 size_t *
  38 gsl_combination_data (const gsl_combination * c)
  39 {
  40   return c->data ;
  41 }
  42
  43 #ifndef HIDE_INLINE_STATIC
  44 size_t
  45 gsl_combination_get (const gsl_combination * c, const size_t i)
  46 {
  47   if (gsl_check_range)
  48     {
  49       if (i >= c->k)            /* size_t is unsigned, can't be negative */
  50         {
  51           GSL_ERROR_VAL ("index out of range", GSL_EINVAL, 0);
  52         }
  53     }
  54
  55   return c->data[i];
  56 }
  57 #endif
  58
  59
  60 int
  61 gsl_combination_valid (gsl_combination * c)
  62 {
  63   const size_t n = c->n ;
  64   const size_t k = c->k ;
  65
  66   size_t i, j ;
  67
  68   if( k > n )
  69     {
  70       GSL_ERROR("combination has k greater than n", GSL_FAILURE) ;
  71     }
  72   for (i = 0; i < k; i++)
  73     {
  74       const size_t ci = c->data[i];
  75
  76       if (ci >= n)
  77         {
  78           GSL_ERROR("combination index outside range", GSL_FAILURE) ;
  79         }
  80
  81       for (j = 0; j < i; j++)
  82         {
  83           if (c->data[j] == ci)
  84             {
  85               GSL_ERROR("duplicate combination index", GSL_FAILURE) ;
  86             }
  87           if (c->data[j] > ci)
  88             {
  89               GSL_ERROR("combination indices not in increasing order",
  90                         GSL_FAILURE) ;
  91             }
  92         }
  93     }
  94
  95   return GSL_SUCCESS;
  96 }
  97
  98
  99 int
 100 gsl_combination_next (gsl_combination * c)
 101 {
 102   /* Replaces c with the next combination (in the standard lexicographical
 103    * ordering).  Returns GSL_FAILURE if there is no next combination.
 104    */
 105   const size_t n = c->n;
 106   const size_t k = c->k;
 107   size_t *data = c->data;
 108   size_t i;
 109
 110   if(k == 0)
 111     {
 112       return GSL_FAILURE;
 113     }
 114   i = k - 1;
 115
 116   while(i > 0 && data[i] == n - k + i)
 117     {
 118       i--;
 119     }
 120   if(i == 0 && data[i] == n - k)
 121     {
 122       return GSL_FAILURE;
 123     }
 124   data[i]++;
 125   for(; i < k - 1; i++)
 126     {
 127       data[i + 1] = data[i] + 1;
 128     }
 129   return GSL_SUCCESS;
 130 }
 131
 132 int
 133 gsl_combination_prev (gsl_combination * c)
 134 {
 135   /* Replaces c with the previous combination (in the standard
 136    * lexicographical ordering).  Returns GSL_FAILURE if there is no
 137    * previous combination.
 138    */
 139   const size_t n = c->n;
 140   const size_t k = c->k;
 141   size_t *data = c->data;
 142   size_t i;
 143
 144   if(k == 0)
 145     {
 146       return GSL_FAILURE;
 147     }
 148   i = k - 1;
 149
 150   while(i > 0 && data[i] == data[i-1] + 1)
 151     {
 152       i--;
 153     }
 154   if(i == 0 && data[i] == 0)
 155     {
 156       return GSL_FAILURE;
 157     }
 158   data[i++]--;
 159   for(; i < k; i++)
 160     {
 161       data[i] = n - k + i;
 162     }
 163   return GSL_SUCCESS;
 164 }
 165
 166 int
 167 gsl_combination_memcpy (gsl_combination * dest, const gsl_combination * src)
 168 {
 169    const size_t src_n = src->n;
 170    const size_t src_k = src->k;
 171    const size_t dest_n = dest->n;
 172    const size_t dest_k = dest->k;
 173
 174    if (src_n != dest_n || src_k != dest_k)
 175      {
 176        GSL_ERROR ("combination lengths are not equal", GSL_EBADLEN);
 177      }
 178
 179    {
 180      size_t j;
 181
 182      for (j = 0; j < src_k; j++)
 183        {
 184          dest->data[j] = src->data[j];
 185        }
 186    }
 187
 188    return GSL_SUCCESS;
 189 }