diff_sample.cpp

/*
 * Copyright 2011, Ben Langmead <langmea@cs.jhu.edu>
 *
 * This file is part of Bowtie 2.
 *
 * Bowtie 2 is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Bowtie 2 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Bowtie 2.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "diff_sample.h"

struct sampleEntry clDCs[16];
bool clDCs_calced = false; /// have clDCs been calculated?

/**
 * Entries 4-57 are transcribed from page 6 of Luk and Wong's paper
 * "Two New Quorum Based Algorithms for Distributed Mutual Exclusion",
 * which is also used and cited in the Burkhardt and Karkkainen's
 * papers on difference covers for sorting.  These samples are optimal
 * according to Luk and Wong.
 *
 * All other entries are generated via the exhaustive algorithm in
 * calcExhaustiveDC().
 *
 * The 0 is stored at the end of the sample as an end-of-list marker,
 * but 0 is also an element of each.
 *
 * Note that every difference cover has a 0 and a 1.  Intuitively,
 * any optimal difference cover sample can be oriented (i.e. rotated)
 * such that it includes 0 and 1 as elements.
 *
 * All samples in this list have been verified to be complete covers.
 *
 * A value of 0xffffffff in the first column indicates that there is no
 * sample for that value of v.  We do not keep samples for values of v
 * less than 3, since they are trivial (and the caller probably didn't
 * mean to ask for it).
 */
uint32_t dc0to64[65][10] = {
	{0xffffffff},                     // 0
	{0xffffffff},                     // 1
	{0xffffffff},                     // 2
	{1, 0},                           // 3
	{1, 2, 0},                        // 4
	{1, 2, 0},                        // 5
	{1, 3, 0},                        // 6
	{1, 3, 0},                        // 7
	{1, 2, 4, 0},                     // 8
	{1, 2, 4, 0},                     // 9
	{1, 2, 5, 0},                     // 10
	{1, 2, 5, 0},                     // 11
	{1, 3, 7, 0},                     // 12
	{1, 3, 9, 0},                     // 13
	{1, 2, 3, 7, 0},                  // 14
	{1, 2, 3, 7, 0},                  // 15
	{1, 2, 5, 8, 0},                  // 16
	{1, 2, 4, 12, 0},                 // 17
	{1, 2, 5, 11, 0},                 // 18
	{1, 2, 6, 9, 0},                  // 19
	{1, 2, 3, 6, 10, 0},              // 20
	{1, 4, 14, 16, 0},                // 21
	{1, 2, 3, 7, 11, 0},              // 22
	{1, 2, 3, 7, 11, 0},              // 23
	{1, 2, 3, 7, 15, 0},              // 24
	{1, 2, 3, 8, 12, 0},              // 25
	{1, 2, 5, 9, 15, 0},              // 26
	{1, 2, 5, 13, 22, 0},             // 27
	{1, 4, 15, 20, 22, 0},            // 28
	{1, 2, 3, 4, 9, 14, 0},           // 29
	{1, 2, 3, 4, 9, 19, 0},           // 30
	{1, 3, 8, 12, 18, 0},             // 31
	{1, 2, 3, 7, 11, 19, 0},          // 32
	{1, 2, 3, 6, 16, 27, 0},          // 33
	{1, 2, 3, 7, 12, 20, 0},          // 34
	{1, 2, 3, 8, 12, 21, 0},          // 35
	{1, 2, 5, 12, 14, 20, 0},         // 36
	{1, 2, 4, 10, 15, 22, 0},         // 37
	{1, 2, 3, 4, 8, 14, 23, 0},       // 38
	{1, 2, 4, 13, 18, 33, 0},         // 39
	{1, 2, 3, 4, 9, 14, 24, 0},       // 40
	{1, 2, 3, 4, 9, 15, 25, 0},       // 41
	{1, 2, 3, 4, 9, 15, 25, 0},       // 42
	{1, 2, 3, 4, 10, 15, 26, 0},      // 43
	{1, 2, 3, 6, 16, 27, 38, 0},      // 44
	{1, 2, 3, 5, 12, 18, 26, 0},      // 45
	{1, 2, 3, 6, 18, 25, 38, 0},      // 46
	{1, 2, 3, 5, 16, 22, 40, 0},      // 47
	{1, 2, 5, 9, 20, 26, 36, 0},      // 48
	{1, 2, 5, 24, 33, 36, 44, 0},     // 49
	{1, 3, 8, 17, 28, 32, 38, 0},     // 50
	{1, 2, 5, 11, 18, 30, 38, 0},     // 51
	{1, 2, 3, 4, 6, 14, 21, 30, 0},   // 52
	{1, 2, 3, 4, 7, 21, 29, 44, 0},   // 53
	{1, 2, 3, 4, 9, 15, 21, 31, 0},   // 54
	{1, 2, 3, 4, 6, 19, 26, 47, 0},   // 55
	{1, 2, 3, 4, 11, 16, 33, 39, 0},  // 56
	{1, 3, 13, 32, 36, 43, 52, 0},    // 57

	// Generated by calcExhaustiveDC()
	{1, 2, 3, 7, 21, 33, 37, 50, 0},  // 58
	{1, 2, 3, 6, 13, 21, 35, 44, 0},  // 59
	{1, 2, 4, 9, 15, 25, 30, 42, 0},  // 60
	{1, 2, 3, 7, 15, 25, 36, 45, 0},  // 61
	{1, 2, 4, 10, 32, 39, 46, 51, 0}, // 62
	{1, 2, 6, 8, 20, 38, 41, 54, 0},  // 63
	{1, 2, 5, 14, 16, 34, 42, 59, 0}  // 64
};