sys/src/libsat/satrange.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <sat.h>
   4 #include "impl.h"
   5
   6 static SATSolve *
   7 satmin(SATSolve *s, int *a, int n, int *id, int *l, int m, int mul)
   8 {
   9         int i;
  10
  11         if(m > n) return s;
  12         for(i = 0; i < m; i++)
  13                 id[i] = i;
  14         for(;;){
  15                 for(i = 0; i < m; i++)
  16                         l[i] = a[id[i]] * mul;
  17                 s = satadd1(s, l, m);
  18                 for(i = m-1; i >= 0; i--){
  19                         if(++id[i] < n+i+1-m)
  20                                 break;
  21                         if(i == 0)
  22                                 return s;
  23                 }
  24                 while(++i < m)
  25                         id[i] = id[i-1]+1;
  26         }
  27 }
  28
  29 SATSolve *
  30 satrange1(SATSolve *s, int *a, int n, int min, int max)
  31 {
  32         int sz, na;
  33
  34         if(s == nil){
  35                 s = satnew();
  36                 if(s == nil)
  37                         saterror(nil, "satnew: %r");
  38         }
  39         if(n < 0)
  40                 for(n = 0; a[n] != 0; n++)
  41                         ;
  42         if(min > n || max < 0)
  43                 return sataddv(s, 0);
  44         if(min < 0) min = 0;
  45         if(max > n) max = n;
  46         sz = n+1-min;
  47         if(min == 0 || max != n && sz < max+1) sz = max+1;
  48         if(s->cflclalloc < 2*sz){
  49                 na = -(-2*sz & -CFLCLALLOC);
  50                 s->cflcl = satrealloc(s, s->cflcl, na * sizeof(int));
  51                 s->cflclalloc = na;
  52         }
  53         s = satmin(s, a, n, s->cflcl, s->cflcl+sz, max+1, -1);
  54         s = satmin(s, a, n, s->cflcl, s->cflcl+sz, n+1-min, 1);
  55         return s;
  56 }
  57
  58 SATSolve *
  59 satrangev(SATSolve *s, int min, int max, ...)
  60 {
  61         va_list va;
  62
  63         va_start(va, max);
  64         /* horrible hack */
  65         satvafix(va);
  66         s = satrange1(s, (int*)va, -1, min, max);
  67         va_end(va);
  68         return s;
  69 }