dcover/difference_cover.cpp

   1 /*
   2  * differerence_cover.cpp
   3  *
   4  * Copyright 2003 Max-Planck-institut fuer Informatik
   5  *
   6  */
   7
   8 //======================================================================
   9 // This file implements the computation of difference covers
  10 //======================================================================
  11
  12 #include <algorithm>
  13 #include <numeric>
  14 #include <stdexcept>
  15 #include <iostream>
  16
  17 #include "difference_cover.hpp"
  18
  19
  20 //----------------------------------------------------------------------
  21 // Precomputed difference covers.
  22 //
  23 // The covers from 0 to 6 are from
  24 //   Luk, Wong: Two new quorum base algorithms for distributed mutual
  25 //   exclusion. In Proc. 17th International Conference on Distributed
  26 //   Computing Systems, pp. 100-106. IEEE, 1997.
  27 // Covers 7 and 8 were found using an exhaustive search algorithm.
  28 // All except cover 8 are known to be optimal.
  29 //----------------------------------------------------------------------
  30 namespace {
  31   const unsigned max_precomputed_cover = 8;
  32   const unsigned coversizes[max_precomputed_cover+1] =
  33     {1,2,3,4,5,7,9,13,20};
  34   const unsigned cover0[] = {0};
  35   const unsigned cover1[] = {0,1};
  36   const unsigned cover2[] = {0,1,2};
  37   const unsigned cover3[] = {0,1,2,4};
  38   const unsigned cover4[] = {0,1,2,5,8};
  39   const unsigned cover5[] = {0,1,2,3,7,11,19};   //{0,7,8,10,14,19,23};
  40   const unsigned cover6[] = {0,1,2,5,14,16,34,42,59};
  41   const unsigned cover7[] = {0,1,3,7,17,40,55,64,75,85,104,109,117};
  42   const unsigned cover8[] = {0,1,3,7,12,20,30,44,65,80,89,96,114,122,
  43                              128,150,196,197,201,219};
  44   const unsigned * covers[] = { cover0, cover1, cover2, cover3, cover4,
  45                                 cover5, cover6, cover7, cover8 };
  46 }
  47
  48
  49 //----------------------------------------------------------------------
  50 // constructor of difference_cover
  51 //
  52 // Constructs a difference cover modulo a power of two.
  53 // (see difference_cover.hpp)
  54 //
  55 // Small difference covers have been precomputed (see above).
  56 // Larger difference covers are computed by the algorithm in
  57 //   C.J. Colbourn and A.C.H. Ling. Quorums from Difference Covers.
  58 //   Information Processing Letters 75(1-2):9-12, 2000
  59 //----------------------------------------------------------------------
  60 difference_cover::difference_cover(unsigned lv)
  61   : logmod(lv), mask((1<<lv)-1),
  62     coverrank(1<<lv), diff2pos(1<<lv,1<<lv)
  63 {
  64   if (logmod <= max_precomputed_cover) {
  65
  66     // use precomputed covers
  67     coversize = coversizes[logmod];
  68     cover.assign(covers[logmod], covers[logmod] + coversize);
  69
  70   } else {
  71
  72     // use the Colbourn-Ling algorithm
  73     int v = (1<<logmod);
  74     int r = 0;
  75     while (24*r*r+36*r+13 < v) ++r;
  76     coversize = 6*r+4;
  77     cover.resize(coversize);
  78     std::vector<unsigned>::iterator i = cover.begin();
  79     *i = 0; ++i;
  80     std::fill(i, i+r,         1); i+=r;
  81     *i = r+1; ++i;
  82     std::fill(i, i+r,     2*r+1); i+=r;
  83     std::fill(i, i+2*r+1, 4*r+3); i+=2*r+1;
  84     std::fill(i, i+r+1,   2*r+2); i+=r+1;
  85     std::fill(i, i+r,         1); i+=r;
  86     if (i != cover.end()) {
  87       throw std::logic_error("error in the Coulbourn-Ling algorithm");
  88     }
  89     std::partial_sum(cover.begin(), cover.end(), cover.begin());
  90
  91   }
  92
  93 #if DEBUG > 1
  94   std::cerr << "difference cover modulo " << (1<<logmod);
  95   std::cerr << " of size " << coversize << ": " << std::endl;
  96   std::copy(cover.begin(), cover.end(),
  97             std::ostream_iterator<unsigned>(std::cerr, " ") );
  98   std::cerr << std::endl;
  99 #endif
 100
 101   // compute the lookup tables
 102   unsigned i, j, modulus=1<<logmod;
 103   for (i=0, j=0; i<modulus; ++i) {
 104     coverrank[i] = j;
 105     if (j<coversize && cover[j] <= i) { ++j; }
 106   }
 107   for (i=coversize-1; i<coversize; --i) {
 108     for (j=0; j<coversize; ++j) {
 109       diff2pos[(cover[j]-cover[i])&mask] = cover[i];
 110     }
 111   }
 112
 113   // check that this is a difference cover
 114   for (i=0; i<modulus; ++i) {
 115     if (diff2pos[i] == modulus) {
 116       throw std::logic_error("bad difference cover");
 117     }
 118 #if DEBUG > 2
 119     std::cerr << i << " = " << ((diff2pos[i]+i)&mask);
 120     std::cerr << " - " << diff2pos[i];
 121     std::cerr << " (mod " << modulus << ")";
 122     std::cerr << std::endl;
 123 #endif
 124   }
 125 }