| 1 |
#ifndef POSITIONDB_H |
| 2 |
#define POSITIONDB_H |
| 3 |
|
| 4 |
#include <stdio.h> |
| 5 |
#include "bio++.H" |
| 6 |
#include "merStream.H" |
| 7 |
|
| 8 |
// The two existDB inputs can be either forward or canonical. If |
| 9 |
// canonical, we are smart enough to search exist/only with the |
| 10 |
// canonical mer. |
| 11 |
|
| 12 |
// Returns position in posn, resizing it if needed. Space is |
| 13 |
// allocated if none supplied. The following is valid: |
| 14 |
// |
| 15 |
// uint64 *posn = 0L; |
| 16 |
// uint64 posnMax = 0; |
| 17 |
// uint64 posnLen = 0; |
| 18 |
// if (get(somemer, posn, posnMax, posnLen)) { |
| 19 |
// do something with the positions |
| 20 |
// } |
| 21 |
// |
| 22 |
// exists() returns T/F if mer exists or not |
| 23 |
// count() returns the number of times that mer is present |
| 24 |
|
| 25 |
// Define this to use an uncompressed hash table when the width is 32 |
| 26 |
// bits or less. Doing so is A LOT faster in mismatch lookups, but |
| 27 |
// does use more memory. |
| 28 |
#undef UNCOMPRESS_HASH_TABLE |
| 29 |
|
| 30 |
// Define this to leave out references to getTime(), speedCounter() |
| 31 |
// and make the positionDB build very quietly. |
| 32 |
#undef SILENTPOSITIONDB |
| 33 |
|
| 34 |
// Define these to enable some debugging methods |
| 35 |
#undef DEBUGPOSDB |
| 36 |
#undef DEBUGREBUILD |
| 37 |
|
| 38 |
class existDB; |
| 39 |
class merylStreamReader; |
| 40 |
|
| 41 |
class positionDB { |
| 42 |
public: |
| 43 |
positionDB(char const *filename, |
| 44 |
uint32 merSize, |
| 45 |
uint32 merSkip, |
| 46 |
uint32 maxMismatch, |
| 47 |
bool loadData=true); |
| 48 |
|
| 49 |
positionDB(merStream *MS, |
| 50 |
uint32 merSize, |
| 51 |
uint32 merSkip, |
| 52 |
existDB *mask, |
| 53 |
existDB *only, |
| 54 |
merylStreamReader *counts, |
| 55 |
uint32 minCount, |
| 56 |
uint32 maxCount, |
| 57 |
uint32 maxMismatch, |
| 58 |
uint32 maxMemory, |
| 59 |
bool beVerbose); |
| 60 |
|
| 61 |
~positionDB(); |
| 62 |
|
| 63 |
private: |
| 64 |
void build(merStream *MS, |
| 65 |
existDB *mask, |
| 66 |
existDB *only, |
| 67 |
merylStreamReader *counts, |
| 68 |
uint32 minCount, |
| 69 |
uint32 maxCount, |
| 70 |
bool beVerbose); |
| 71 |
|
| 72 |
private: |
| 73 |
void reallocateSpace(uint64*& posn, |
| 74 |
uint64& posnMax, |
| 75 |
uint64& posnLen, |
| 76 |
uint64 len); |
| 77 |
|
| 78 |
void loadPositions(uint64 v, |
| 79 |
uint64*& posn, |
| 80 |
uint64& posnMax, |
| 81 |
uint64& posnLen, |
| 82 |
uint64& count); |
| 83 |
|
| 84 |
public: |
| 85 |
bool getExact(uint64 mer, |
| 86 |
uint64*& posn, |
| 87 |
uint64& posnMax, |
| 88 |
uint64& posnLen, |
| 89 |
uint64& count); |
| 90 |
bool existsExact(uint64 mer); |
| 91 |
uint64 countExact(uint64 mer); |
| 92 |
|
| 93 |
public: |
| 94 |
void filter(uint64 lo, uint64 hi); |
| 95 |
|
| 96 |
private: |
| 97 |
double setUpMismatchMatcher(uint32 nErrorsAllowed, uint64 approxMers); |
| 98 |
public: |
| 99 |
bool getUpToNMismatches(uint64 mer, |
| 100 |
uint32 maxMismatches, |
| 101 |
uint64*& posn, |
| 102 |
uint64& posnMax, |
| 103 |
uint64& posnLen); |
| 104 |
private: |
| 105 |
uint64 setCount(uint64 mer, uint64 count); |
| 106 |
|
| 107 |
// Save or load a built table |
| 108 |
// |
| 109 |
public: |
| 110 |
void saveState(char const *filename); |
| 111 |
bool loadState(char const *filename, bool beNoisy=false, bool loadData=true); |
| 112 |
|
| 113 |
void printState(FILE *stream); |
| 114 |
|
| 115 |
// Only really useful for debugging. Don't use. |
| 116 |
// |
| 117 |
void dump(char *name); |
| 118 |
|
| 119 |
|
| 120 |
bool checkREBUILD(uint64 m) { |
| 121 |
#define DEBUGREBUILD |
| 122 |
#ifdef DEBUGREBUILD |
| 123 |
uint64 h = HASH(m); |
| 124 |
uint64 c = CHECK(m); |
| 125 |
uint64 r = REBUILD(h, c); |
| 126 |
if (r != m) { |
| 127 |
fprintf(stderr, "shift1 = "uint32FMT"\n", _shift1); |
| 128 |
fprintf(stderr, "shift2 = "uint32FMT"\n", _shift2); |
| 129 |
fprintf(stderr, "M = "uint64HEX"\n", m); |
| 130 |
fprintf(stderr, "H = "uint64HEX"\n", h); |
| 131 |
fprintf(stderr, "C = "uint64HEX"\n", c); |
| 132 |
fprintf(stderr, "R = "uint64HEX"\n", r); |
| 133 |
return(false); |
| 134 |
} |
| 135 |
return(true); |
| 136 |
#else |
| 137 |
return(REBUILD(HASH(m), CHECK(m)) == m); |
| 138 |
#endif |
| 139 |
}; |
| 140 |
|
| 141 |
private: |
| 142 |
|
| 143 |
uint64 HASH(uint64 k) { |
| 144 |
return(((k >> _shift1) ^ (k >> _shift2) ^ k) & _mask1); |
| 145 |
}; |
| 146 |
|
| 147 |
uint64 CHECK(uint64 k) { |
| 148 |
return(k & _mask2); |
| 149 |
}; |
| 150 |
|
| 151 |
uint64 REBUILD(uint64 h, uint64 c) { |
| 152 |
// Decode a HASH and a CHECK to get back the mer. You'd better |
| 153 |
// bloody PRAY you don't break this (test/test-rebuild.C). It |
| 154 |
// was a headache++ to write. |
| 155 |
|
| 156 |
uint64 sha = _shift1 - _shift2; |
| 157 |
uint64 msk = uint64MASK(sha); |
| 158 |
|
| 159 |
// The check is exactly the mer....just not all there. |
| 160 |
uint64 mer = c; |
| 161 |
|
| 162 |
uint64 shf = sha - (_tableSizeInBits % 2); |
| 163 |
uint64 shg = 0; |
| 164 |
uint64 shh = _shift1; |
| 165 |
|
| 166 |
// Unrolling this is troublesome - we still need the tests, |
| 167 |
// bizarre merSize, tblSize combinations use lots of iterations |
| 168 |
// (when the merSize and tblSize are about the same, the CHECK is |
| 169 |
// small, and so we need to do lots of iterations). |
| 170 |
|
| 171 |
//fprintf(stderr, "shf="uint64FMTW(2)" shg="uint64FMTW(2)" shh="uint64FMTW(2)" mer="uint64HEX"\n", shf, shg, shh, mer); |
| 172 |
|
| 173 |
do { |
| 174 |
mer |= (((h >> shg) ^ (mer >> shg) ^ (mer >> shf)) & msk) << shh; |
| 175 |
//fprintf(stderr, "shf="uint64FMTW(2)" shg="uint64FMTW(2)" shh="uint64FMTW(2)" mer="uint64HEX"\n", shf, shg, shh, mer); |
| 176 |
|
| 177 |
shf += sha; |
| 178 |
shg += sha; |
| 179 |
shh += sha; |
| 180 |
} while ((shf < _merSizeInBits) && (shh < 64)); |
| 181 |
|
| 182 |
mer &= uint64MASK(_merSizeInBits); |
| 183 |
|
| 184 |
return(mer); |
| 185 |
}; |
| 186 |
|
| 187 |
void sortAndRepackBucket(uint64 b); |
| 188 |
|
| 189 |
uint32 *_bucketSizes; |
| 190 |
uint64 *_countingBuckets; |
| 191 |
uint64 *_hashTable_BP; // Bit packed |
| 192 |
uint32 *_hashTable_FW; // Full width |
| 193 |
uint64 *_buckets; |
| 194 |
|
| 195 |
uint64 *_positions; |
| 196 |
|
| 197 |
uint32 _merSizeInBases; |
| 198 |
uint32 _merSizeInBits; |
| 199 |
|
| 200 |
uint32 _merSkipInBases; |
| 201 |
|
| 202 |
uint64 _tableSizeInEntries; |
| 203 |
uint32 _tableSizeInBits; |
| 204 |
|
| 205 |
uint32 _hashWidth; // Hash bith |
| 206 |
uint32 _chckWidth; // Check bits |
| 207 |
uint32 _posnWidth; // Positions in the sequence |
| 208 |
uint32 _pptrWidth; // Pointers to positions |
| 209 |
uint32 _sizeWidth; // Extra number in the table |
| 210 |
|
| 211 |
uint64 _hashMask; |
| 212 |
|
| 213 |
uint32 _wCnt; |
| 214 |
uint32 _wFin; |
| 215 |
|
| 216 |
uint32 _shift1; |
| 217 |
uint32 _shift2; |
| 218 |
uint64 _mask1; |
| 219 |
uint64 _mask2; |
| 220 |
|
| 221 |
uint64 _numberOfMers; |
| 222 |
uint64 _numberOfPositions; |
| 223 |
uint64 _numberOfDistinct; |
| 224 |
uint64 _numberOfUnique; |
| 225 |
uint64 _numberOfEntries; |
| 226 |
uint64 _maximumEntries; |
| 227 |
|
| 228 |
// For sorting the mers |
| 229 |
// |
| 230 |
uint32 _sortedMax; |
| 231 |
uint64 *_sortedChck; |
| 232 |
uint64 *_sortedPosn; |
| 233 |
|
| 234 |
// For the mismatch matcher |
| 235 |
uint32 _nErrorsAllowed; |
| 236 |
uint32 _hashedErrorsLen; |
| 237 |
uint32 _hashedErrorsMax; |
| 238 |
uint64 *_hashedErrors; |
| 239 |
}; |
| 240 |
|
| 241 |
#endif // POSITIONDB_H |